基于矩陣分解和層次聚類的協(xié)同過濾推薦算法

東苗 王啟宗

（1.上海行健職業(yè)學(xué)院 上海市 2000722 2.北京紅亞華宇科技有限公司 北京市 102209）

1 引言

隨著信息技術(shù)、大數(shù)據(jù)技術(shù)和人工智能的快速發(fā)展，個性化推薦技術(shù)已經(jīng)滲透到社會的各個方面，如音樂、電影、短視頻、圖書、廣告、旅游、電商等領(lǐng)域。在海量信息中能否快速找到最有價值的信息，最重要的環(huán)節(jié)是個性化推薦系統(tǒng)的核心即推薦算法。推薦算法主要有基于知識的推薦算法、基于內(nèi)容的推薦算法、協(xié)同過濾算法等，目前應(yīng)用范圍最廣且效果較好的推薦算法是協(xié)同過濾算法，協(xié)同過濾算法利用用戶的相似性來推薦用戶感興趣的信息，但由于協(xié)同過濾算法存在冷啟動、數(shù)據(jù)稀疏和可靠性不高的問題，導(dǎo)致推薦精準度不高。

針對上述問題，本文提出一種基于矩陣分解和層次聚類的協(xié)同過濾推薦算法。通過矩陣分解將原評分稀疏矩陣進行降維分解得到兩個低秩矩陣，數(shù)據(jù)填充得到不含缺省值的完整評分矩陣。再對樣本訓(xùn)練集上的用戶構(gòu)建層次聚類模型進行分類劃分。在協(xié)同過濾階段，對測試集中的用戶首先在聚類模型中找到該用戶所在的聚類，再在該聚類中進行最近鄰集選取、預(yù)測評分、選取TOP-N、生成列表、產(chǎn)生推薦。[1]

2 協(xié)同過濾推薦算法

協(xié)同過濾算法一般可以分為三個步驟：[2]

step1.構(gòu)建“用戶-項目”評分矩陣。定義矩陣Rm×n表示表示m 位用戶對n 個項目的評分數(shù)據(jù)。

度量用戶相似度的方法主要有：余弦相似度（Cosine Similarity）、Pearson 相關(guān)系數(shù)（Pearson Correlation Coefficient）和修正余弦相似度（Adjusted Cosine Similarity）。

（1）余弦相似度：把用戶對項目的評價看作一個n 維向量，兩個用戶間的相似度通過二者向量夾角的余弦來度量。設(shè)用戶i 和用戶j 的評分分別用向量Ii和向量Ij表示，可計算兩者間的余弦相似度sim(i,j)：

（2）Pearson 相關(guān)系數(shù)：皮爾森相關(guān)系數(shù)對變量進行均值化處理，降低了變量個體數(shù)值差異帶來的影響。設(shè)用戶i 和用戶j 共同評分的項目用集合Hij表示，則兩者間的相似度sim(i,j)可表示為：

其中，ri,c和rj,c分別表示用戶i 和用戶j 對項目c 的評分，與分別表示用戶i 和用戶j 對各項目的平均評分。

圖1：矩陣分解模型

圖2：AHC 流程圖

圖3：算法流程

（3）修正余弦相似度：余弦相似度未考慮到用戶不同的評價尺度問題，修正余弦相似度通過減去用戶對項目的平均評分來改善用戶評分的差異。設(shè)Hi和Hj分別表示用戶i 和用戶j 評分的項目集合，則兩者間的相似度sim(i,j)可表示為：

分別統(tǒng)計N(i)中的用戶對不同項目的興趣度的加權(quán)平均值，取其中N 個排在最前面且不屬于Hi（Hi表示用戶i 評分的項目集合）的項作為Top - N 推薦集。

傳統(tǒng)的協(xié)同過濾算法主要依賴于“用戶-項目”評分矩陣。但在實際應(yīng)用中評分矩陣往往是極其稀疏的，導(dǎo)致無法計算相似度或精度不高，找到的最近鄰不可靠，最終的推薦效果不理想。[3]

3 基于層次聚類和矩陣分解的協(xié)同過濾推薦算法

針對傳統(tǒng)協(xié)同過濾算法中存在的問題，本文提出基于層次聚類和矩陣分解的協(xié)同過濾推薦算法。首先通過矩陣分解模型對“用戶-項目”評分矩陣進行降維處理，矩陣填充以降低矩陣的稀疏性；再通過層次聚類對用戶屬性劃簇，以減少最近鄰的搜索范圍并增強其可靠性；最后進行協(xié)同過濾推薦。

3.1 矩陣分解模型

矩陣分解思想最初來源于信息檢索領(lǐng)域的隱語義索引（Latent Semantic Indexing,LSI）方法，LSI 使用了奇異值分解（Singular Value Decomposition,SVD）算法對“文檔-詞”矩陣進行分解。[4]但是SVD 應(yīng)用到推薦系統(tǒng)領(lǐng)域會存在對稀疏評分矩陣的預(yù)測不準確、可擴展性低的問題。矩陣分解（Matrix Factorization,MF）算法借鑒了SVD 的思想，通過對“用戶-項目”評分矩陣進行分解得到隱空間來分別表示用戶和物品。矩陣分解的數(shù)學(xué)表示如圖1所示。

在m 個用戶和n 個項目的評分矩陣Rm×n中，可將有評分的項設(shè)為1，無評分的項設(shè)為0。通常該交互矩陣是非常稀疏的。矩陣分解模型將高維的評分矩陣分解為低秩的用戶隱含信息矩陣Pm×k和項目隱含信息矩陣Qk×n，兩個低秩矩陣構(gòu)造的預(yù)測矩陣相乘盡可能地逼近原評分矩陣Rm×n。用戶對項目的喜好程度的預(yù)測值 可以表示為：

將TOP-N 推薦問題轉(zhuǎn)化為最小二乘問題求解：

輸出：P,Q

（5）for count in 1 to iters:

（6）for ＜user,item,rating＞ in T:

3.2 層次聚類

層次聚類(Hierarchical Clustering)屬于無監(jiān)督學(xué)習(xí)的一種聚類算法，通過對原始數(shù)據(jù)集在不同的層次進行劃分，直到達到某種條件為止，最后得到樹形的聚類結(jié)構(gòu)。按照分類原理的不同，可以分為凝聚式層次聚類(AHC)和分裂式層次聚類(DHC)，其中凝聚式的應(yīng)用比較廣泛。[5]首先將原始數(shù)據(jù)集中的每個樣本都單獨作為一個簇，原始的類中心為然后分別計算兩個簇之間的距離，按照相似度從高到低排序依次合并成簇，直到達到預(yù)先設(shè)定的聚類數(shù)目或者相似度閾值為止。如圖2所示。

本文采用Average Linkage 聚類法計算Ci和Cj兩簇間的距離式中|p-p'|表示樣本p 和p'之間的距離，ni和nj分別表示簇Ci和Cj中樣本數(shù)。

圖4：不同算法下的NDCG

圖5：不同算法下的RMSE

3.3 基于層次聚類和矩陣分解的協(xié)同過濾推薦算法

基于層次聚類和矩陣分解的協(xié)同過濾推薦算法將層次聚類與矩陣分解模型相結(jié)合，可以使結(jié)果更加準確。算法主要包括矩陣分解、層次聚類和協(xié)同推薦三個階段。

（1）通過矩陣分解將原“用戶-項目”評分稀疏矩陣分解成兩個低秩矩陣Pm×k和Qk×n，對P 和Q 分別進行迭代，使兩個低秩矩陣構(gòu)造的預(yù)測矩陣相乘盡可能地逼近原評分矩陣Rm×n；通過R=PQT得到不含缺省值的完整評分矩陣；

（2）根據(jù)得到的用戶矩陣，通過層次聚類對用戶進行劃分，最后形成k 個聚類，；

（3）協(xié)同過濾：由于已經(jīng)通過層次聚類將相似的用戶劃分為一個簇，當測試集中的用戶加入到系統(tǒng)中時計算該用戶與各簇中心點的距離，將其劃到距離最近的簇中并從該簇中選取N 個相似度較高的用戶作為其最近鄰居集，通過式（5）進行預(yù)測打分后選取評分位于前列的N 個項目，生成最終的列表TOP-N 返回給該用戶，算法流程如圖3所示。

4 算法的測試和評價

4.1 數(shù)據(jù)集

本文實驗基于2 個數(shù)據(jù)集。第一個數(shù)據(jù)集是電影評分歷史數(shù)據(jù)集，包含105,339 個樣本。第二個數(shù)據(jù)集是電影信息數(shù)據(jù)集，由美國運輸局收集整理，包含10,329 個樣本。

4.2 評價指標

本文中采用兩種方式對推薦算法進行評估。第一種是由推薦算法預(yù)測每個用戶評分最高的前k 個電影列表，與該用戶實際評分的電影做對比，計算根據(jù)排名加權(quán)的重合度。第二種是由推薦算法預(yù)測每個用戶已評分的電影的評分，與真實值做對比計算誤差。

（1）歸一化衰減累積增益（NDCG）

歸一化衰減累積增益定義為：

其中，L 是按推薦評分降序排列的電影列表，Lideal是按用戶真實評分降序排列的電影列表，u 是用戶，i 是排名，rui是用戶u 對排在第i 位電影的評分。

（2）均方根誤差（Root Mean Square Error,RMSE）

均方根誤差通過計算預(yù)測評分與實際評分之間誤差的均方根來衡量推薦結(jié)果的準確度，RMSE 越小，說明推薦的精度越高。假設(shè)預(yù)測的用戶評分集合表示為對應(yīng)的實際用戶評分集合為則均方根誤差RMSE 定義為：

4.3 測試流程

4.3.1 數(shù)據(jù)預(yù)處理

將數(shù)據(jù)集分為5 組訓(xùn)練集和測試集做5 折交叉驗證。在推薦系統(tǒng)中分割訓(xùn)練集和測試集時按照用戶做分割，具體方法為：

step1.將用戶分割成5 組測試集用戶；

step2.對于每組測試集用戶，再進一步抽取這些用戶20%的評分樣本作為測試集；

step3.創(chuàng)建對應(yīng)的訓(xùn)練集，包含該組測試集用戶得其余80%的評分樣本以及所有非測試集用戶的評分樣本。

4.3.2 候選推薦數(shù)據(jù)準備

合并所有的測試集，為后續(xù)模型性能評估做準備。在給用戶做電影推薦時，需要提供一個候選推薦列表。數(shù)據(jù)集中有部分電影只有極少數(shù)的評分，因此并不穩(wěn)定，這里排除所有評分少于5 條的電影。

4.4 實驗結(jié)果分析

為與傳統(tǒng)的推薦算法進行對比，本文選取基于個性化平均評分的推薦和基于電影相似度的協(xié)同過濾推薦做對照實驗。繪制3 種推薦算法用于推薦列表的NDCG。可以看出，基于個性化平均評分的推薦最差，基于矩陣分解的協(xié)同過濾推薦最好。如圖4所示。

繪制3 種推薦算法用于預(yù)測評分的均方根誤差。可以看出，基于個性化平均評分的推薦最差，基于矩陣分解的協(xié)同過濾推薦最好。如圖5所示。

5 結(jié)束語

綜上所述，為了避免由于評分矩陣數(shù)據(jù)稀疏、高維度帶來的計算誤差及協(xié)同過濾過程中帶來大量的數(shù)據(jù)冗余，提高推薦算法的效率和精度，本文提出了一種基于層次聚類和矩陣分解的協(xié)同過濾算法。首先利用矩陣分解技術(shù)對評分矩陣進行降維及數(shù)據(jù)填充，減少了由于數(shù)據(jù)稀疏性帶來的推薦誤差；然后使用分解得到的用戶矩陣，利用層次聚類算法對用戶進行聚類劃分，最后進行協(xié)同過濾處理，根據(jù)項目評分預(yù)測產(chǎn)生TOP-N 推薦列表。對比實驗結(jié)果驗證了該算法的準確度和有效性明顯優(yōu)于傳統(tǒng)協(xié)同過濾推薦算法。