3.2 矩陣分解

矩陣分解（Matrix Factorization）簡(jiǎn)單說(shuō)就是將原始矩陣拆解為數(shù)個(gè)矩陣的乘積。在一些大型矩陣計(jì)算中，其計(jì)算量大，化簡(jiǎn)繁雜，使得計(jì)算非常復(fù)雜。如果運(yùn)用矩陣分解，將大型矩陣分解成簡(jiǎn)單矩陣的乘積形式，就可大大降低計(jì)算的難度以及計(jì)算量。這就是矩陣分解的主要目的。矩陣的秩問題、奇異性問題、特征值問題、行列式問題等都可以通過矩陣分解后清晰地反映出來(lái)。另一方面，對(duì)于那些大型的數(shù)值計(jì)算問題，矩陣的分解方式以及分解過程也可以作為計(jì)算的理論依據(jù)。MADlib 1.10提供了低秩矩陣分解和奇異值分解兩種矩陣分解方法。

3.2.1 低秩矩陣分解

1. 背景知識(shí)

矩陣中的最大不相關(guān)向量的個(gè)數(shù)叫作矩陣的秩，可通俗理解為數(shù)據(jù)有秩序的程度。秩可以度量相關(guān)性，而向量的相關(guān)性實(shí)際上又帶有矩陣的結(jié)構(gòu)信息。如果矩陣之間各行的相關(guān)性很強(qiáng)，就表示這個(gè)矩陣實(shí)際可以投影到更低維度的線性子空間，也就是用幾個(gè)特征就可以完全表達(dá)了，它就是低秩的。所以我們可以總結(jié)的一點(diǎn)是：如果矩陣表達(dá)的是結(jié)構(gòu)性信息，例如圖像、用戶推薦表等，那么這個(gè)矩陣各行之間存在著一定的相關(guān)性，這個(gè)矩陣一般就是低秩的。

如果A是一個(gè)m行n列的數(shù)值矩陣、rank(A)是A的秩，并且rank(A)遠(yuǎn)小于m和n，就稱A是低秩矩陣。低秩矩陣每行或每列都可以用其他的行或列線性表示，可見它包含大量的冗余信息。利用這種冗余信息，可以對(duì)缺失數(shù)據(jù)進(jìn)行恢復(fù)，也可以對(duì)數(shù)據(jù)進(jìn)行特征提取。

MADlib的lmf模塊可用兩個(gè)低秩矩陣的乘積逼近一個(gè)稀疏矩陣，逼近的目標(biāo)就是讓預(yù)測(cè)矩陣和原來(lái)矩陣之間的均方根誤差（Root Mean Squared Error, RMSE）最小，從而實(shí)現(xiàn)所謂“潛在因子模型”。lmf模塊提供的低秩矩陣分解函數(shù)就是為任意稀疏矩陣A找到兩個(gè)矩陣U和V，使得||A-UVT||2的值最小化，其中‖·‖2代表Frobenius范數(shù)。換句話說(shuō)，只要求得U和V，就可以用它們的乘積來(lái)近似模擬A。因此低秩矩陣分解有時(shí)也叫UV分解。假設(shè)A是一個(gè)m×n的矩陣，則U和V分別是m×r和n×r的矩陣，并且1≤r≤min(m,n)。

2. MADlib低秩矩陣分解函數(shù)

MADlib的lmf_igd_run函數(shù)能夠?qū)崿F(xiàn)低秩矩陣分解功能。本小節(jié)介紹MADlib低秩矩陣分解函數(shù)的語(yǔ)法和參數(shù)含義，下一小節(jié)用一個(gè)實(shí)例說(shuō)明該函數(shù)的具體用法。

（1）lmf_igd_run函數(shù)語(yǔ)法

     lmf_igd_run( rel_output,
                 rel_source,
                 col_row,
                 col_column,
                 col_value,
                 row_dim,
                 column_dim,
                 max_rank,
                 stepsize,
                 scale_factor,
                 num_iterations,
                 tolerance )

（2）參數(shù)說(shuō)明

lmf_igd_run函數(shù)參數(shù)說(shuō)明如表3-2所示。

表3-2 lmf_igd_run函數(shù)參數(shù)說(shuō)明

矩陣分解一般不用數(shù)學(xué)上直接分解的辦法，盡管直接分解出來(lái)的精度很高，但是效率實(shí)在太低！矩陣分解往往會(huì)轉(zhuǎn)化為一個(gè)優(yōu)化問題，通過迭代求局部最優(yōu)解。但是有一個(gè)問題——通常原矩陣的稀疏度很大，分解很容易產(chǎn)生過擬合（overfitting），簡(jiǎn)單說(shuō)就是為了遷就一些錯(cuò)誤的偏僻的值導(dǎo)致整個(gè)模型錯(cuò)誤的問題。所以現(xiàn)在的方法是在目標(biāo)函數(shù)中增加一項(xiàng)正則化（regularization）參數(shù)來(lái)避免過擬合問題。

因此，一般的矩陣分解的目標(biāo)函數(shù)（也稱損失函數(shù)，loss function）為：

前一項(xiàng)是預(yù)測(cè)后矩陣和原矩陣的誤差，這里計(jì)算只針對(duì)原矩陣中的非空項(xiàng)。后一項(xiàng)就是正則化因子，用來(lái)解決過度擬合的問題。這個(gè)優(yōu)化問題求解的就是分解之后的U、V矩陣的潛在因子向量。

madlib.lmf_igd_run函數(shù)使用隨機(jī)梯度下降法（stochastic gradient descent）求解這個(gè)優(yōu)化問題，迭代公式為：

Udi=Udi+γ(EijVdj-λUdi)

Udj=Vdj+γ(EijUdi-λVdj)

其中，。

γ是學(xué)習(xí)速率，對(duì)應(yīng)stepsize參數(shù)；λ是正則化系數(shù)，對(duì)應(yīng)scale_factor參數(shù)。γ和λ這是兩個(gè)超參數(shù)，對(duì)于最終結(jié)果影響極大。在機(jī)器學(xué)習(xí)的上下文中，超參數(shù)是在開始學(xué)習(xí)過程之前設(shè)置值的參數(shù)，而不是通過訓(xùn)練得到的參數(shù)數(shù)據(jù)。通常情況下，需要對(duì)超參數(shù)進(jìn)行優(yōu)化，以提高學(xué)習(xí)的性能和效果。γ的大小不僅會(huì)影響到執(zhí)行時(shí)間，還會(huì)影響到結(jié)果的收斂性。γ太大的話會(huì)導(dǎo)致結(jié)果發(fā)散，一般都會(huì)把γ取得很小，不同的數(shù)據(jù)集取的值不同，但大概是0.001這個(gè)量級(jí)。這樣的話訓(xùn)練時(shí)間會(huì)長(zhǎng)一些，但結(jié)果會(huì)比較好。λ的值一般也比較小，大概取0.01這個(gè)量級(jí)。

迭代開始前，需要對(duì)U、V的特征向量賦初值。這個(gè)初值很重要，會(huì)嚴(yán)重地影響到計(jì)算速度。一般的做法是在均值附近產(chǎn)生隨機(jī)數(shù)作為初值。也正是由于這個(gè)原因，從數(shù)據(jù)庫(kù)層面看，madlib.lmf_igd_run函數(shù)是一個(gè)非確定函數(shù)，也就是說(shuō)，同樣一組輸入數(shù)據(jù)，多次執(zhí)行函數(shù)生成的結(jié)果數(shù)據(jù)是不同的。迭代結(jié)束的條件一般是損失函數(shù)的值小于某一個(gè)閾值（由tolerance參數(shù)指定）或者到達(dá)指定的最大迭代次數(shù)（由num_iterations參數(shù)指定）。

3. 低秩矩陣分解函數(shù)示例

我們將通過一個(gè)簡(jiǎn)單示例說(shuō)明如何利用madlib.lmf_igd_run函數(shù)實(shí)現(xiàn)潛在因子（Latent Factor）推薦算法。該算法的思想是：每個(gè)用戶（user）都有自己的偏好，比如一個(gè)歌曲推薦應(yīng)用中，用戶A喜歡帶有“小清新的”“吉他伴奏的”“王菲”等元素，如果一首歌（item）帶有這些元素，就將這首歌推薦給該用戶，也就是用元素去連接用戶和歌曲。每個(gè)人對(duì)不同的元素偏好不同，而每首歌包含的元素也不一樣。

（1）潛在因子矩陣

我們希望能找到這樣兩個(gè)矩陣：

?潛在因子–用戶矩陣Q，表示不同的用戶對(duì)于不同元素的偏好程度，1代表很喜歡，0代表不喜歡，如圖3-1所示。

圖3-1 潛在因子–用戶矩陣

?潛在因子–音樂矩陣P，表示每首歌曲含有各種元素的成分。比如圖3-2中，音樂A是一個(gè)偏小清新的音樂，含有“小清新”這個(gè)潛在因子的成分是0.9、“重口味”的成分是0.1、“優(yōu)雅”的成分是0.2等，如圖3-2所示。

圖3-2 潛在因子–音樂矩陣

利用這兩個(gè)矩陣，我們能得出張三對(duì)音樂A的喜歡程度是：張三對(duì)小清新的偏好*音樂A含有小清新的成分＋對(duì)重口味的偏好*音樂A含有重口味的成分＋對(duì)優(yōu)雅的偏好*音樂A含有優(yōu)雅的成分＋……即0.6*0.9+0.8*0.1+0.1*0.2+0.1*0.4+0.7*0=0.68。

對(duì)每個(gè)用戶每首歌都這樣計(jì)算可以得到不同用戶對(duì)不同歌曲的評(píng)分矩陣，如圖3-3所示。注意，這里的波浪線表示的是估計(jì)的評(píng)分，接下來(lái)我們還會(huì)用到不帶波浪線的R表示實(shí)際的評(píng)分矩陣。

圖3-3 估計(jì)的評(píng)分矩陣

因此我們對(duì)張三推薦四首歌中得分最高的B、對(duì)李四推薦得分最高的C，對(duì)王五推薦B。如果用矩陣表示即為：

（2）如何得到潛在因子

潛在因子是怎么得到的呢？面對(duì)大量用戶和歌曲，讓用戶自己給歌曲分類并告訴我們其偏好系數(shù)顯然是不現(xiàn)實(shí)的，事實(shí)上我們能獲得的只有用戶行為數(shù)據(jù)。假定使用以下量化標(biāo)準(zhǔn)：?jiǎn)吻h(huán)=5，分享=4，收藏=3，主動(dòng)播放=2，聽完=1，跳過=-2，拉黑=-5，則在分析時(shí)能獲得的實(shí)際評(píng)分矩陣R（也就是輸入矩陣）如圖3-4所示。

圖3-4 實(shí)際評(píng)分矩陣

推薦系統(tǒng)的目標(biāo)就是預(yù)測(cè)出空白對(duì)應(yīng)位置的分值。推薦系統(tǒng)基于這樣一個(gè)假設(shè)：用戶對(duì)項(xiàng)目的打分越高，表明用戶越喜歡。因此，預(yù)測(cè)出用戶對(duì)未評(píng)分項(xiàng)目的評(píng)分后，根據(jù)分值大小排序，把分值高的項(xiàng)目推薦給用戶。這是一個(gè)非常稀疏的矩陣，因?yàn)榇蟛糠钟脩糁宦犨^全部歌曲中很少一部分。如何利用這個(gè)矩陣去找潛在因子呢？這里主要應(yīng)用到的就是矩陣的UV分解，如圖3-5所示。

圖3-5 矩陣的UV分解

矩陣分解的想法來(lái)自于矩陣補(bǔ)全，即依據(jù)一個(gè)矩陣給定的部分?jǐn)?shù)據(jù)把缺失的值補(bǔ)全。一般假設(shè)原始矩陣是低秩的，我們可以從給定的值來(lái)還原這個(gè)矩陣。由于直接求解低秩矩陣從算法以及參數(shù)的復(fù)雜度來(lái)說(shuō)效率很低，因此常用的方法是直接把原始矩陣分解成兩個(gè)子矩陣相乘。例如，將圖3-5所示的評(píng)分矩陣分解為兩個(gè)低維度的矩陣，用Q和P兩個(gè)矩陣的乘積去估計(jì)實(shí)際的評(píng)分矩陣，而且我們希望估計(jì)的評(píng)分矩陣和實(shí)際的評(píng)分矩陣不要相差太多，也就是求解矩陣分解的目標(biāo)函數(shù)：

如前所述，實(shí)際應(yīng)用中，往往還要加上2范數(shù)的罰項(xiàng)，然后利用梯度下降法就可以求得P和Q兩個(gè)矩陣的估計(jì)值。例如，我們上面給出的那個(gè)例子可以分解成兩個(gè)矩陣，如圖3-6所示。

圖3-6 分解后得到的UV矩陣

這兩個(gè)矩陣相乘就可以得到估計(jì)的得分矩陣，如圖3-7所示。

圖3-7 預(yù)測(cè)矩陣

將用戶已經(jīng)聽過的音樂剔除后，選擇分?jǐn)?shù)最高的音樂推薦給用戶即可。這個(gè)例子里用戶7和用戶8有較強(qiáng)的相似性，如圖3-8所示。

圖3-8 評(píng)分相似的用戶

從推薦的結(jié)果來(lái)看，正好推薦的是對(duì)方評(píng)分較高的音樂，如圖3-9所示。

圖3-9 對(duì)相似用戶的推薦

該算法假定我們要恢復(fù)的矩陣是低秩的，實(shí)際上這種假設(shè)是十分合理的，比如一個(gè)用戶對(duì)某歌曲的評(píng)分是其他用戶對(duì)這首歌曲評(píng)分的線性組合。所以，通過低秩重構(gòu)就可以預(yù)測(cè)用戶對(duì)其未評(píng)價(jià)過的音樂的喜好程度，從而對(duì)矩陣進(jìn)行填充。

（3）利用madlib.lmf_igd_run函數(shù)實(shí)現(xiàn)

① 建立輸入表并生成輸入數(shù)據(jù)

說(shuō)明：

?從前面的解釋可以看到，推薦矩陣的行列下標(biāo)分別表示用戶和歌曲。然而在業(yè)務(wù)系統(tǒng)中，userid和musicid很可能不是按從1到N的規(guī)則順序生成的，因此通常需要建立矩陣下標(biāo)值與業(yè)務(wù)表ID之間的映射關(guān)系，這里使用HAWQ的BIGSERIAL自增數(shù)據(jù)類型對(duì)應(yīng)推薦矩陣的索引下標(biāo)。

?在生成原始數(shù)據(jù)時(shí)對(duì)圖3-4的例子做了適當(dāng)?shù)男薷摹Ｓ脩舯碇衭5和u10用戶沒有給任何歌曲打分，而音樂表中的m10、m14、m15無(wú)評(píng)分。我們希望看到的結(jié)果是，除了與打分行為相關(guān)的用戶和歌曲以外，也能為u5、u10推薦歌曲，并可能將m10、m14、m15推薦給用戶。

② 調(diào)用lmf_igd_run函數(shù)分解矩陣

說(shuō)明：

?最大行列數(shù)可以大于實(shí)際行列數(shù)，如這里傳入的參數(shù)是11和16，而實(shí)際的用戶數(shù)與歌曲數(shù)是10和15。

?max_rank參數(shù)為最大秩數(shù)，要小于min(row_dim, column_dim)，否則函數(shù)會(huì)報(bào)錯(cuò)：

NOTICE:  Matrix lmf_data to be factorized: 11 x 16
ERROR:  plpy.SPIError: Function "madlib.lmf_igd_transition(double
precision[],integer,integer,double precision,double
precision[],integer,integer,integer,double precision,double precision)":
Invalid parameter: max_rank >= row_dim || max_rank >= column_dim
(plpython.c:4663)

?最大秩數(shù)實(shí)際可以理解為最大的潛在因子數(shù)，也就是例子中的最大量化指標(biāo)個(gè)數(shù)。本例中共有7個(gè)指標(biāo)，因此max_rank參數(shù)傳7。

?stepsize和scale_factor參數(shù)對(duì)于結(jié)果的影響巨大，而且不同的學(xué)習(xí)數(shù)據(jù)，參數(shù)值也不同。也就是說(shuō)超參數(shù)的值是與輸入數(shù)據(jù)相關(guān)的。在本例中，使用默認(rèn)值時(shí)RMSE很大。經(jīng)過反復(fù)測(cè)試，對(duì)于測(cè)試矩陣，stepsize和scale_factor分別為0.1和1時(shí)誤差相對(duì)較小。

函數(shù)執(zhí)行結(jié)果的控制臺(tái)輸出如下：

可以看到，均方根誤差值為0.0033。

③ 檢查結(jié)果

從上一步的輸出看到，lmf_igd_run()函數(shù)返回的模型ID是1，需要用它作為查詢條件。

select array_dims(matrix_u) as u_dims, array_dims(matrix_v) as v_dims
  from lmf_model
 where id=1;

結(jié)果：

結(jié)果表中包含分解成的兩個(gè)矩陣，U（用戶潛在因子）矩陣11行7列，V（音樂潛在因子）矩陣16行7列。

④ 查詢結(jié)果值

select matrix_u, matrix_v from lmf_model where id=1;

⑤ 矩陣相乘生成推薦矩陣

MADlib的矩陣相乘函數(shù)是matrix_mult，支持稠密和稀疏兩種矩陣表示。稠密矩陣需要指定矩陣對(duì)應(yīng)的表名、row和val列，稀疏矩陣需要指定矩陣對(duì)應(yīng)的表名、row、col和val列。現(xiàn)在要將lmf_igd_run函數(shù)輸出的矩陣裝載到表中再執(zhí)行矩陣乘法。這里使用稀疏形式，只要將二維矩陣的行、列、值插入表中即可。

結(jié)果：

這兩個(gè)矩陣（11×3與16×3）相乘生成的結(jié)果表是稠密形式的11×16矩陣，這就是我們需要的推薦矩陣。為了方便與原始的索引表關(guān)聯(lián)，將結(jié)果表轉(zhuǎn)為稀疏表示。

結(jié)果：

最后與原始的索引表關(guān)聯(lián)，過濾掉用戶已經(jīng)聽過的歌曲，選擇分?jǐn)?shù)最高的歌曲推薦。

結(jié)果：

這就是為每個(gè)用戶推薦的歌曲。可以看到，m12、m8分別推薦給了用戶u5、u10，m14、m15分別推薦給了用戶u3、u4。

MADlib的低秩矩陣分解函數(shù)可以作為推薦類應(yīng)用的算法實(shí)現(xiàn)。從函數(shù)調(diào)用角度看，madlib.lmf_igd_run函數(shù)是一個(gè)非確定函數(shù)，也就是說(shuō)，同樣一組輸入數(shù)據(jù)，函數(shù)生成的結(jié)果數(shù)據(jù)卻不同（對(duì)于同樣的輸入數(shù)據(jù)，每次的推薦可能不一樣）。在海量數(shù)據(jù)的應(yīng)用中，推薦可能需要計(jì)算的是一個(gè)“幾億”ד幾億”的大型矩陣，如何保證推薦系統(tǒng)的性能將成為巨大的挑戰(zhàn)。

3.2.2 奇異值分解

1. 背景知識(shí)

低秩矩陣分解是用兩個(gè)矩陣的乘積近似還原一個(gè)低秩矩陣。MADlib還提供了另一種矩陣分解方法，即奇異值分解。奇異值分解簡(jiǎn)稱SVD（Singular Value Decomposition），可以理解為將一個(gè)比較復(fù)雜的矩陣用更小更簡(jiǎn)單的三個(gè)子矩陣的相乘來(lái)表示，這三個(gè)小矩陣描述了原矩陣重要的特性。

要理解奇異值分解，先要知道什么是特征值和特征向量。m×n矩陣M的特征值和特征向量分別是標(biāo)量值λ和向量u，它們是如下方程的解：

Mu=λu

換言之，特征向量（eigenvector）是被M乘時(shí)除量值外并不改變的向量。特征值（eigenvalue）是縮放因子。該方程也可以寫成(M-λE)u=0，其中E是單位矩陣。

對(duì)于方陣，可以使用特征值和特征向量分解矩陣。假設(shè)M是n×n矩陣，具有n個(gè)獨(dú)立的（正交的）特征向量u1,…,un和n個(gè)對(duì)應(yīng)的特征值λ1,…,λn。設(shè)U是矩陣，它的列是這些特征向量，即U=[u1,…,un]；并且Λ是對(duì)角矩陣，它的對(duì)角線元素是λi，1≤i≤n。則M可以被表示為：

M=UΛU-1

這樣，M可以被分解成三個(gè)矩陣的乘積。U稱為特征向量矩陣（eigenvector matrix），而Λ稱為特征值矩陣（eigenvalue matrix）。

更一般地，任意矩陣都可以用類似的方法分解。對(duì)于一個(gè)M×N（M≥N）的矩陣M，存在以下的SVD分解：

Mm×n=Um×m∑m×n(Vn×n)T

其中，U是m×m矩陣，∑是m×n矩陣，V是n×n矩陣。U和V是標(biāo)準(zhǔn)正交矩陣，即它們的列向量都是單位長(zhǎng)度，并且相互正交。這樣，UUT=Em，VVT=En，E是單位矩陣。∑是對(duì)角矩陣，其對(duì)角線元素非負(fù)，并且被排好序，使得較大的元素先出現(xiàn)，即σi,i≥σi+1,i+1。

V的列向量V1,…,Vn是右奇異向量（right singular vector），U的列向量是左奇異向量（left singular vector）。奇異值矩陣（singular value matrix）∑的對(duì)角線元素通常記作σ1,…,σn，稱為M的奇異值（singular value）。最多存在rank(M)≤min(m,n)個(gè)非零奇異值。

矩陣的奇異值分解也可以用下面的等式表示，其結(jié)果是秩為1的m×n矩陣。

這種表示的重要性是每個(gè)矩陣都可以表示成秩為1矩陣的以奇異值為權(quán)重的加權(quán)和。由于以非遞增順序排列的奇異值通常下降很快，因此有可能使用少量奇異值和奇異值向量得到矩陣的很好的近似。這對(duì)于維歸約是很有用的。

矩陣的SVD分解具有如下性質(zhì)。

?屬性中的模式被右奇異向量（V的列）捕獲。

?對(duì)象中的模式被左奇異向量（U的列）捕獲。

?矩陣A可以通過依次取公式中的項(xiàng)，以最優(yōu)的方式不斷逼近。也就是說(shuō)，奇異值越大，該奇異值和相關(guān)聯(lián)的奇異向量決定矩陣的比例越大。

很多情況下，前10%甚至更少的奇異值的平方就占全部奇異值平方的90%以上了，因此可以用前k個(gè)奇異值來(lái)近似描述原矩陣：

Mm×n≈Um×k∑k×k(Vn×k)T

k的取值由下面的公式?jīng)Q定：

其中，percentage稱為“奇異值平方和占比的閾值”，一般取90%，k是一個(gè)遠(yuǎn)小于m和n的值，這樣也就達(dá)到了降維的目的。

2. MADlib奇異值分解函數(shù)

MADlib的SVD函數(shù)可以對(duì)稠密矩陣和稀疏矩陣進(jìn)行奇異值因式分解，并且提供了一個(gè)稀疏矩陣的本地高性能實(shí)現(xiàn)函數(shù)。

（1）稠密矩陣的SVD函數(shù)

語(yǔ)法如下：

     svd( source_table,
         output_table_prefix,
         row_id,
         k,
         n_iterations,
         result_summary_table );

參數(shù)如表3-3所示。

表3-3 SVD函數(shù)參數(shù)說(shuō)明

source_table表中含有一個(gè)row_id列標(biāo)識(shí)每一行，從數(shù)字1開始。其他列包含矩陣的數(shù)據(jù)。可以使用兩種稠密格式的任何一個(gè)，例如下面示例的2×2矩陣。

格式一：

格式二：

（2）稀疏矩陣的SVD函數(shù)

表示為稀疏格式的矩陣使用此函數(shù)。為了高效計(jì)算，在奇異值分解操作之前，輸入矩陣會(huì)被轉(zhuǎn)換為稠密矩陣。

語(yǔ)法如下：

參數(shù)如表3-4所示。

表3-4 svd_sparse函數(shù)參數(shù)說(shuō)明

（3）稀疏矩陣的本地實(shí)現(xiàn)SVD函數(shù)

此函數(shù)在計(jì)算SVD時(shí)使用本地稀疏表示（不跨節(jié)點(diǎn)），能夠更高效地計(jì)算稀疏矩陣，適合高度稀疏的矩陣。

語(yǔ)法如下：

參數(shù)同svd_sparse函數(shù)。

（4）輸出表

三個(gè)SVD函數(shù)的輸出都是以下三個(gè)表：

?左奇異矩陣表：表名為<output_table_prefix>_u。

?右奇異矩陣表：表名為<output_table_prefix>_v。

?奇異值矩陣表：表名為<output_table_prefix>_s。

左右奇異向量表的格式為：

?row_id：INTEGER類型。每個(gè)特征值對(duì)應(yīng)的ID，降序排列。

?row_vec：FLOAT8[]類型。該row_id對(duì)應(yīng)的特征向量元素，數(shù)組大小為k。

由于只有對(duì)角線元素是非零的，奇異值表采用稀疏表格式，其中的row_id和col_id都是從1開始。奇異值表具有以下列：

?row_id：INTEGER類型，第i個(gè)奇異值為i。

?col_id：INTEGER類型，第i個(gè)奇異值為i（與row_id相同）。

?value：FLOAT8類型，奇異值。

除了矩陣分解得到的三個(gè)輸出表外，奇異值分解函數(shù)還會(huì)輸出一個(gè)結(jié)果摘要表，存儲(chǔ)函數(shù)執(zhí)行的基本情況信息具有以下列：

?rows_used：INTEGER類型，計(jì)算SVD使用的行數(shù)。

?exec_time：FLOAT8類型，計(jì)算SVD使用的總時(shí)間。

?iter：INTEGER類型，迭代運(yùn)行次數(shù)。

?recon_error：FLOAT8類型，質(zhì)量得分（近似精度）。計(jì)算公式為：

?relative_recon_error：FLOAT8類型，相對(duì)質(zhì)量分?jǐn)?shù)。計(jì)算公式為：

（5）聯(lián)機(jī)幫助

可以執(zhí)行下面的查詢獲得SVD函數(shù)的聯(lián)機(jī)幫助。

select madlib.svd();
-- 用法
select madlib.svd('usage');
-- 示例
select madlib.svd('example');

3. 奇異值分解函數(shù)示例

下面我們使用稀疏SVD函數(shù)解決前面低秩矩陣分解示例中的歌曲推薦問題。

（1）建立輸入表并生成輸入數(shù)據(jù)

推薦矩陣的行列下標(biāo)分別表示用戶和歌曲。然而在業(yè)務(wù)系統(tǒng)中，userid和musicid很可能不是按從1到N的規(guī)則順序生成的，因此需要建立矩陣下標(biāo)值與業(yè)務(wù)表ID之間的映射關(guān)系，這里使用HAWQ的BIGSERIAL自增數(shù)據(jù)類型對(duì)應(yīng)推薦矩陣的索引下標(biāo)。

這里從業(yè)務(wù)數(shù)據(jù)生成有過打分行為的9個(gè)用戶以及被打過分的8首歌曲。注意，查詢中排序子句的作用是便于業(yè)務(wù)ID與矩陣?yán)锏男辛蠭D對(duì)應(yīng)。

之所以要用用戶行為表作為數(shù)據(jù)源，是因?yàn)榫仃囍邪杏羞^打分行為的用戶和被打過分的歌曲，但不包括與沒有任何打分行為相關(guān)的用戶和歌曲。與低秩矩陣分解不同的是，如果包含無(wú)行為記錄的用戶或歌曲，就會(huì)在計(jì)算余弦相似度時(shí)出現(xiàn)除零錯(cuò)誤。正因如此，如果要用奇異值分解方法推薦沒有被評(píng)過分的歌曲，或者為沒有評(píng)分行為的用戶形成推薦，就需要做一些特殊處理，比如將一個(gè)具有特別標(biāo)志的虛擬用戶或歌曲用平均分?jǐn)?shù)賦予初值，手工添加到評(píng)分矩陣表中。

（2）執(zhí)行SVD

選擇svd_sparse_native函數(shù)的原因是測(cè)試數(shù)據(jù)比較稀疏，矩陣實(shí)際數(shù)據(jù)只占1/3（25/72），該函數(shù)效率較高。這里給出的行、列、奇異值個(gè)數(shù)分別為9、8、7。svd_sparse_native函數(shù)要求行數(shù)大于等于列數(shù)，而奇異值個(gè)數(shù)小于等于列數(shù)，否則會(huì)報(bào)錯(cuò)。結(jié)果U、V矩陣的行數(shù)由實(shí)際的輸入數(shù)據(jù)所決定，例如測(cè)試數(shù)據(jù)最大行值為9、最大列值為8，則結(jié)果U矩陣的行數(shù)為9、V矩陣的行數(shù)為8，而不論行、列參數(shù)的值是多少。U、V矩陣的列數(shù)、S矩陣的行列數(shù)均由奇異值個(gè)數(shù)參數(shù)所決定。

-- 查看SVD結(jié)果
select array_dims(row_vec) from svd_u;
select * from svd_s order by row_id, col_id;
select array_dims(row_vec) from svd_v;
select * from svd_summary;

結(jié)果：

從中可以看出，結(jié)果U、V矩陣的維度分別是9×7和8×7，奇異值是一個(gè)7×7的對(duì)角矩陣。這里還有一點(diǎn)與低秩矩陣分解函數(shù)不同，低秩矩陣分解函數(shù)由于引入了隨機(jī)數(shù)，是不確定函數(shù)，因此相同參數(shù)的輸入可能得到不同的輸出結(jié)果矩陣。但奇異值分解函數(shù)是確定的，只要輸入的參數(shù)相同，輸出的結(jié)果矩陣就是一樣的。

（3）對(duì)比不同奇異值個(gè)數(shù)的逼近程度

讓我們按k的取值公式計(jì)算一下奇異值的比值，驗(yàn)證k設(shè)置為6、8時(shí)的逼近程度。

-- k=8
drop table if exists svd8_u, svd8_v, svd8_s, svd8_summary cascade;
select madlib.svd_sparse_native
('svd_data', 'svd8', 'row_id', 'col_id', 'val', 9, 8, 8, NULL,
'svd8_summary');
-- k=6
drop table if exists svd6_u, svd6_v, svd6_s, svd6_summary cascade;
select madlib.svd_sparse_native
('svd_data', 'svd6', 'row_id', 'col_id', 'val', 9, 8, 6, NULL,
'svd6_summary');
-- 對(duì)比逼近程度
select * from svd6_summary;
select * from svd_summary;
select * from svd8_summary;
select s1/s3, s2/s3
  from (select sum(value*value) s1 from svd6_s) t1,
       (select sum(value*value) s2 from svd_s) t2,
       (select sum(value*value) s3 from svd8_s) t3;

結(jié)果：

可以看出，隨著k值的增加，誤差越來(lái)越小。在本示例中，奇異值個(gè)數(shù)為6、7的近似度分別為97.7%和99.7%，當(dāng)k等于8時(shí)并沒有降維，分解的矩陣相乘等于原矩陣。后面的計(jì)算都使用k等于7的結(jié)果矩陣。

（4）基于用戶的協(xié)同過濾算法UserCF生成推薦

所謂UserCF算法，簡(jiǎn)單說(shuō)就是依據(jù)用戶的相似程度形成推薦。

說(shuō)明：

?最內(nèi)層查詢調(diào)用madlib.cosine_similarity函數(shù)返回指定用戶與其他用戶的余弦相似度。

?外面一層查詢按相似度倒序取得排名。

select r2,s,row_number() over (order by s desc) rn from …

?外面一層查詢?nèi)〉米钕嘟?個(gè)用戶，同時(shí)排除相似度為1的用戶，因?yàn)橄嗨贫葹?說(shuō)明兩個(gè)用戶的歌曲評(píng)分一模一樣，而推薦的應(yīng)該是用戶沒有打過分的歌曲。

select r2,s from … where rn <=5 and s < 1

?外面一層查詢?nèi)〉孟嗨朴脩舸蚍衷?及其以上的歌曲索引ID。

select r2,s,col_id,val from … where t1.r2=t2.row_id and t2.val >=3

?外面一層查詢?nèi)〉酶枨饕齀D的排名，目的是去重，避免相同的歌曲推薦多次，并且過濾掉被推薦用戶已經(jīng)打過分的歌曲。

select r2,s,col_id,val,
       row_number() over (partition by col_id order by col_id) rn
  from … where col_id not in (select col_id from svd_data where row_id=$1)

?最外層查詢關(guān)聯(lián)歌曲索引表取得歌曲業(yè)務(wù)主鍵，并按相似度和打分推薦前5個(gè)歌曲。

通常輸入的用戶ID是業(yè)務(wù)系統(tǒng)的ID，而不是索引下標(biāo)，因此定義一個(gè)接收業(yè)務(wù)系統(tǒng)的ID函數(shù)，內(nèi)部調(diào)用fn_user_cf函數(shù)生成推薦。

-- 測(cè)試推薦結(jié)果
select * from fn_user_recommendation('u1');
select * from fn_user_recommendation('u3');
select * from fn_user_recommendation('u9');

結(jié)果：

因?yàn)閡3和u9的評(píng)分完全相同、相似度為1，所以為他們生成的推薦也完全相同。

（5）基于歌曲的協(xié)同過濾算法ItemCF生成推薦

所謂ItemCF算法，簡(jiǎn)單說(shuō)就是依據(jù)歌曲的相似程度形成推薦。

說(shuō)明：

?最內(nèi)層查詢調(diào)用madlib.cosine_similarity函數(shù)返回指定用戶打過分的歌曲與沒打過分的歌曲的相似度。

?外面一層查詢按相似度倒序取得排名。

select t1.*, row_number() over (partition by r1 order by s desc) rn …

?外面一層查詢?nèi)〉门c每個(gè)打分歌曲相似度排前三的歌曲，并以歌曲索引ID分區(qū)，按相似度倒序取得排名，目的是去重，避免相同的歌曲推薦多次。

select t1.r2,t1.s,row_number() over (partition by r2 order by s desc) rn
from … where rn <=3

?最外層查詢關(guān)聯(lián)歌曲索引表取得歌曲業(yè)務(wù)主鍵并推薦。

通常輸入的用戶ID是業(yè)務(wù)系統(tǒng)的ID，而不是索引下標(biāo)，因此定義一個(gè)接收業(yè)務(wù)系統(tǒng)的ID函數(shù)，內(nèi)部調(diào)用fn_item_cf函數(shù)生成推薦。

-- 測(cè)試推薦結(jié)果
select * from fn_item_recommendation('u1');
select * from fn_item_recommendation('u3');
select * from fn_item_recommendation('u9');

結(jié)果：

因?yàn)閡3和u9的評(píng)分作品完全相同、相似度為1，所以按作品相似度為他們生成的推薦也完全相同。

（6）為新用戶尋找相似用戶

假設(shè)一個(gè)新用戶u10的評(píng)分向量為'{0,4,5,3,0,0,-2,0}'，要利用已有的奇異值矩陣找出該用戶的相似用戶。

確認(rèn)從評(píng)分向量計(jì)算svd_u向量的公式：

u10[1:8]×svd_v[8:7]×svd_s[7:7]^-1

根據(jù)公式，將（4）、（5）兩步的結(jié)果矩陣相乘。注意：（4）的結(jié)果mat_r_10是一個(gè)稠密矩陣，（5）的結(jié)果svd_s_10是一個(gè)稀疏矩陣。

查詢與u10相似的用戶：

結(jié)果：

u10與u4的相似度高達(dá)99%，從原始的評(píng)分向量可以得到驗(yàn)證：

u4：'{0,4,4,3,0,0,-2,0}'
u10：'{0,4,5,3,0,0,-2,0}'

將結(jié)果向量插入svd_u矩陣：

insert into svd_u
select user_idx, row_vec from matrix_r_10, tbl_idx_user where userid='u10';