基于聚類矩陣近似的協同過濾推薦研究

張 文, 崔楊波, 李 健, 陳進東

(1.北京工業大學 經濟管理學院,北京 100124; 2.北京化工大學 經濟管理學院,北京100029; 3.西安文理學院 信息工程學院,陜西 西安 710065; 4.北京信息科技大學 經濟管理學院,北京 100101)

0 背景介紹

隨著Web 2.0技術和電子商務的不斷發展，互聯網上充斥了海量的在線商品和服務的信息，使得網絡用戶獲取自己所需在線商品的成本不斷提升。為篩除無關信息以解決用戶信息過載問題，協同過濾方法被提出并被應用于在線商品推薦系統以根據用戶畫像向其推薦可能感興趣的商品[1]。一般來說，可將協同過濾方法分為兩種：基于最近鄰的協同過濾方法和基于矩陣分解的協同過濾方法[2,3]。前者通過用戶之間與商品之間的鄰近關系來為用戶推薦新的商品[3,4]；后者將用戶-商品評分矩陣分解為用戶潛在偏好向量與商品潛在特征向量并利用二者之間的內積來預測用戶對于商品的評分[2,3]。

近年來一系列基于矩陣分解的協同過濾推薦方法被提出并得到了學術界和工業界的一致認可。2006年Netflix Prize電影推薦競賽的結果表明了基于矩陣分解的協同過濾方法SVD++(Singular Value Decomposition++)要優于傳統的基于最近鄰的方法。SVD++方法將用戶-商品評分矩陣中隱含的附加反饋信息、個體行為信息與整體行為信息統一整合在了一起，因此其預測效果相比基于最近鄰的協同過濾方法要好[1]。盡管基于矩陣分解的協同過濾方法表現較好，但在實際的協同過濾的應用中，還存在以下兩方面問題亟需解決。

第一方面的問題來自于用戶-商品評分矩陣的稀疏性[5]。推薦系統中存在巨量的用戶和巨量的商品，然而巨量的用戶往往僅對少量的商品進行評分，這就導致用戶-商品評分矩陣中產生大量的評分缺失數據，即評分矩陣稀疏性。評分矩陣稀疏性將會導致無法準確度量用戶與用戶、商品與商品之間的相似性，因此也會降低對用戶-商品推薦的準確性。第二方面的問題來自于傳統推薦方法的計算可擴展性[6]。已有的基于矩陣分解的協同過濾方法大多直接采用線性代數方法或者概率統計方法來分解整個用戶-商品評分矩陣以得到用戶潛在偏好向量與商品潛在特征向量。然而，當面對巨量的商品和用戶時，對于用戶-商品評分矩陣的分解將變得難以計算[7]。

對于第一方面的用戶-商品平均矩陣稀疏性的問題，研究人員聚焦于如何通過缺失修復方法利用估算值去填充矩陣中評分為零的元素，從而消除矩陣中評分為零的元素，然后在此基礎之上利用填充后的矩陣進行協同過濾推薦[8]。Xia等人[9]利用均值填充(Mean Imputation)方法，將用戶未評分的商品賦以所有其它評分的平均值，然后使用填充后的數據進行商品協同過濾。Gong[10]采用基于案例推理方法CBR(Case-based reasoning)方法來填補空缺的評分，其基本思想是，對于一個具有商品評分缺失值的用戶，首先利用歐式距離鎖定與其相似用戶的集合，然后根據相似用戶的在對應商品上的評分來估算該缺失的商品評分。

對于第二方面的計算可擴展性問題，研究人員重點關注如何利用高效的線性代數和概率抽樣計算方法從觀測到的用戶-商品評分矩陣元素中抽取出用戶潛在偏好向量和商品潛在特征向量[8]。Chen和Peng[11]借鑒概率矩陣分解PMF(Probabilistic Matrix Factorization)的思想，認為現實的評分矩陣R中的數據疊加產生于兩個高斯分布隨機矩陣：一是商品是否對用戶進行了展示的隱性反饋數據；二是用戶對所展示商品的真實評分數據。前者通過用戶潛在因素矩陣U與商品展示潛在因素矩陣Z之間的乘積得到；后者通過用戶潛在因素矩陣U與商品評分潛在因素矩陣V之間的乘積得到。為計算上述的U矩陣，矩陣Z和矩陣V，他們對用戶已經評分(Positive正類)數據進行抽樣和未評分的(Negative負類)缺失數據進行隨機抽樣和概率推導，并由此提出了PMF+P+N(PMF with Positive and Negative feedbacks)方法。Xue等[12]利用深度學習方法對用戶-商品評分矩陣R進行分解，并提出了深度矩陣分解方法DMF(Deep Matrix Factorization)。其基本思想是利用矩陣的行向量pui作為學習用戶偏好潛在向量的輸入，并同時利用矩陣R的列向量作為學習商品特征潛在向量qgj的輸入。之后，以pui，qgj的內積與用戶ui在商品qj上的評分rij之間的差距RMSE(Root Mean Square Error)作為損失函數以進行深度學習用戶偏好潛在向量pui和商品特征潛在向量qgj。

為了解決上述推薦系統中的數據稀疏性和計算可擴展性問題，本文提出了一種基于聚類矩陣近似的方法CF-cluMA(Collaborative Filtering based on Clustered Matrix Approximation)以用于協同過濾。CF-cluMA方法首先對用戶-商品評分矩陣分別進行用戶(行)聚類和商品(列)聚類，將具有相似評分的用戶和商品在矩陣中的位置重新排列，以形成新的矩陣塊。然后，通過設定稠密閾值參數，CF-cluMA利用對稠密矩陣塊實施奇異值分解(Singular Value Decomposition，SVD)和對各個稠密矩陣塊奇異向量進行施密特正交化來重新近似原始的用戶-商品評分矩陣。最后，利用近似后的用戶-商品評分矩陣預測用戶對商品的未知評分。一方面，CF-cluMA方法在計算過程中采用稠密矩陣塊，降低了數據的稀疏性。另一方面，CF-cluMA方法在計算過程中同時對多個較小規模的稠密矩陣塊實施奇異值分解以近似原始用戶-評分矩陣，提高了矩陣分解方法的計算可擴展性。在EachMovie公開數據集上的實驗表明，與現有的基于矩陣計算的協同過濾方法相比較，CF-cluMA方法無論在推薦的準確性還是計算復雜度方面都能得到較好的結果。

1 問題描述

(1)

2 基于聚類矩陣近似的協同過濾方法—CF-cluMA

在當前的電商平臺上不同的用戶對于不同商品的興趣各不相同，因此構成了對于在線商品消費的不同群體，形成了用戶-商品的局部特性。大多數的用戶僅關注電商平臺上一小部分的商品，而大量的商品僅被少部分用戶所關注。在協同過濾推薦系統中，用戶與用戶、商品與商品之間存在群體劃分，在不同的用戶群體內部，他們對商品群體的偏好并不相同。CF-cluMA的基本思想正是利用了在線用戶對于在線商品的局部興趣，將原始的大規模的用戶-商品評分矩陣進行聚類分塊近似以提高協同過濾的計算準確性并降低計算復雜程度。CF-cluMA方法主要分為三個步驟：首先對用戶-商品評分矩陣進行用戶(行)聚類和商品(列)聚類以形成分塊矩陣；然后對稠密分塊矩陣逐個實施奇異值分解，并對奇異向量進行施密特全局正交化以近似原始用戶-評分矩陣；最后利用近似后的矩陣進行商品評分預測。

2.1 用戶聚類和商品聚類

CF-cluMA方法采用了經典的矩陣譜聚類方法[13]來對用戶-商品評分矩陣中的用戶和商品實施聚類。在譜聚類中，給定用戶-商品評分矩陣R，構造無向圖N=(V,E)。其中V={1,2,…,|V|}是頂點的集合，代表商品和用戶；E={eij|如果邊{i,j}存在}是邊的集合，表示用戶和商品之間的評分關系；每條邊的權重為Eij，即用戶ui對商品gj的評分。在推薦系統中，用戶與用戶、商品與商品之間不存在關聯，因此在用戶集合和商品集合內部不存在邊，僅在單個用戶ui對單個商gj品有評分行為時存在邊，由此定義用戶-商品的鄰接矩陣M如式(2)，此時用戶-商品的鄰接矩陣M可以表示為式(3)。

(2)

(3)

在給定的用戶-商品評分矩陣R中尋找特定的用戶群所關心的特定的商品類別需要對用戶群體和商品群體進行同時聚類，也就是對用戶-商品評分矩陣R同時實施行聚類和列聚類。假設用戶聚類個數為c1，商品聚類個數為c2，不相關的用戶聚類集合可表示為{Ui|Ui∈U,1≤i≤c1}。同理，不相關的商品聚類集合可表示為{Gj|Gj∈G,1≤j≤c2}。對于給定一個用戶聚類集合Ui，如果其對應的商品聚類為Gj，那么這就意味著在對評分矩陣R實施聚類后的分塊矩陣上，用戶聚類集合Ui和商品聚類集合Gj所對應的矩陣分塊構成了一個稠密矩陣塊。Ui和Gj定義如公式(4)和公式(5)所示。

(4)

從式(4)和式(5)可以看出，商品的聚類集合影響著用戶的聚類集合，反過來，用戶的聚類集合也影響著商品的聚類集合。可以證明，最優的商品與用戶聚類集合在上述圖模型取最小割時取得[13]，即:

(6)

其中，v1,…,vk是上述無向圖G圖中任意的k個聚類。

為求得上述圖N模型的最小割，首先定義用戶-商品的拉普拉斯矩陣L，如式(7)所示。

(7)

根據以上定義可得L=D-M。其中M是鄰接矩陣，D是對角“度”矩陣，Dii=∑keik。根據譜圖聚類模型[13]，當廣義特征值問題Lz=λDz獲得求解時的第二大特征值對應的廣義特征向量即為圖中每個點的聚類表示向量，其中z為廣義特征向量，L和D分別由式(8)和式(9)分別表示。

(8)

(9)

(10)

假設D1和D2均為非奇異陣，那么式(10)可展開為式(11)和式(12)。

(11)

(12)

(13)

(14)

(15)

P(2,l+1)向量中的每行元素按順序代表原始矩陣R中行的位置，Q(2,l+1)向量中的每行元素按順序代表原始矩陣R中列的位置。之后，利用K-Means方法[15]對向量Z2進行聚類。最后，按照P(2,l+1)向量與Q(2,l+1)向量在聚類中的位置對原始評分矩陣R重新按行和按列排列以得到各個聚類對應的分塊矩陣。

2.2 矩陣近似

根據聚類結果重新調整評分矩陣R中用戶和商品的位置，使得屬于同一聚類的商品和用戶聚集在一起，形成新的評分矩陣R′。其具體表現形式為，原始評分矩陣R上給出了相似商品相似評分的用戶以及對應的商品聚集在一起，使得新的評分矩陣R′的某些塊評分比較密集，形成稠密矩陣塊，而剩下的不在聚類中的矩陣塊則較為稀疏。重新聚類后的評分矩陣R′的分塊矩陣形式(其中Rij為矩陣塊)如式(16)所示。其中，[Rij]表示稠密矩陣塊，其余為稀疏矩陣塊。

(16)

在式(16)的基礎之上，借鑒Savas[16]等人提出的聚類矩陣近似方法，對譜聚類后形成的稠密分塊矩陣進行矩陣近似，如式(17)所示。

(17)

(18)

Pi=orth([Pi,c1i,j,…,Pi,c1i,|CIi|]),

(i,c1i,1),…,(i,c1i,|RIi|)∈RIi

(19)

Qi=orth([Qc2j,1,j,…,Qc2j,|CIj|,j]),

(c2j,1,j),…,(c2j,|RIj|,j)∈CIj

(20)

2.3 聚類矩陣近似協同過濾推薦

(21)

從上述計算過程可以看出，CF-cluMA方法相比于最初的SVD方法的優點包括兩個方面。一方面，因為對原始用戶-評分矩陣R做了聚類處理，使得矩陣中相似的部分可以重新排列在一起，原始大規模矩陣的內在結構得到了局部優化。這一優點正好對應可推薦系統中用戶與商品的分群結構特點，即推薦系統中存在潛在用戶群體和潛在商品群體。另一方面，由于新的用戶-商品評分矩陣R′中的稠密矩陣塊Rij的秩遠遠小于原始矩陣用戶-商品評分矩陣R的秩，因此使得矩陣計算的復雜度大大降低，提高了計算的效率。除此之外，由于CF-cluMA方法只考慮新的用戶-商品評分矩陣R′中的稠密矩陣塊而不考慮稀疏矩陣塊，使得協同過濾推薦系統能夠充分利用已知的用戶對于商品的真實評分數據而較少將未知缺失數據納入推薦考慮范圍，減少了未知的確實數據對于推薦結果的干擾。

2.4 算法復雜度分析

3 實驗驗證

3.1 實驗數據及實驗設置

本文的實驗數據來自經典的EachMovie數據集[17]，它包括了72916個用戶對1628部電影的評分數據，共計2811983條數據。評分數據分為六個等級，分別為0，0.2，0.4，0.6，0.8和1.0。為了便于計算，本文在實驗時對評分進行了轉換，將六個等級由低到高分別轉換為1，2，3，4，5和6。同時為了保證數據的有效性，本文在實驗時剔除了一些極端數據。數據剔除標準為用戶評分數量小于3的電影和電影評分少于4個的用戶。經過上述預處理之后，本文將EachMovie數據集轉化為一個2584行1140列的用戶-電影評分矩陣，其行代表用戶，列代表電影。

3.2 推薦系統性能評價指標

(22)

3.3 實驗驗證

本文使用EachMovie數據集行進實驗，在對數據進行剔除和整理后，生成了一個2584x1140的用戶-電影評分矩陣。本文應用MATLAB軟件進行編程實現了CF-cluMA算法，并將該評分矩陣的數據實進行了可視化。

圖1與圖2分別展示了該評分矩陣在進行譜聚類前后的數據分布特征，圖中橫軸表示電影數量，本實驗中共1140部電影；縱軸表示用戶數量，本實驗中共2584個用戶。圖中NZ(none zero)表示矩陣中非零元素的個數，通過計算得出該矩陣的稠密度為3.36%，稠密矩陣塊展現了特定用戶群體與特定電影群體之間的強關聯性，體現了用戶-電影評分矩陣的內在局部結構。在通過參數設置對評分分塊矩陣完成主導性稠密矩陣塊篩選后[16]，CF-CluMA方法在這些主導性稠密矩陣塊內進行矩陣近似，并采用公式(21)進行商品評分預測。

圖1 用戶-電影評分矩陣數據分布圖

本文在進行實驗時取90%的數據作為訓練數據集，10%的數據作為測試數據集。為保證實驗結果的可靠性，本文采用10次10折交差驗證法。將推薦數據集隨機均分劃分為10等份，在每次的試驗中利用其中的9份作為訓練數據進行矩陣聚類近似，而取剩下的1份數據進行預測評分測試。在本實驗中取聚類個數為10，主導性稠密矩陣塊的閾值δ=20%，即每次將評分矩陣塊中非零數據密度小于20%的矩陣塊過濾掉，剩下的矩陣塊為主導性稠密矩陣塊。評分近似矩陣中矩陣塊的秩取1到10，針對不同的秩進行實驗。最后，利用公式(22)計算基于聚類矩陣近似的預測評分準確度，實驗結果如表1所示。同時，當為CF-cluMA方法設置不同秩的時候，其計算所需要消耗的時間(以秒計)也不相同，具體結果如表2所示。

表1 CF-cluMA方法評分預測準確度RMSE

表2 不同秩條件下的CF-cluMA方法的計算消耗時間(單位：秒)

3.4 對比實驗

在目前的推薦系統領域，主流的協同過濾算法包括SVD++[1]，PMF+P+N[11]和DMF[12]。在對比試驗中，SVD++方法的秩分別取為5，10，15和20。DMF方法的降維向量長度D分別取為5，10，15和20。PMF+P+N方法的向量維數分別取值為5，10，15和20，迭代次數t為20。表3和表4分別展示了對比實驗中SVD++，PMF+P+N和DMF方法的預測RMSE評分準確度和計算所消耗的時間(以秒計)。

通過對比實驗可以看出，SVD++方法的預測評分準確度與CF-cluMA方法的預測評分準確度比較接近，DMF方法的預測評分準確度效果次之，PMF+P+N方法的效果最差。總體上，SVD++方法和CF-cluMA模型的準確度較高。對于CF-cluMA方法，當其秩取1到8時，準確度平均高于SVD++方法(超過4%)。而當秩的設置大于等于9時，SVD++方法的準確度較高，其可能解釋是，當秩取1到8時，較小的秩使得SVD++和CF-cluMA模型損失掉了一些信息。然而，CF-cluMA方法在對非稠密矩陣塊進行矩陣近似時采用的是主導性稠密矩陣塊奇異向量的正交化后的奇異向量，可以捕捉到大量的矩陣局部信息，因而準確度較高。當秩逐步增大超過8以后，對原始矩陣的近似程度越來越來高，局部結構的特點不再格外明顯時，SVD++方法的準確度要高于CF-cluMA方法。對于DMF方法和PMF+P+N方法，當它們取秩較小的時候，其性能可以被顯著地改善。但是，其效果依然比本文所提出的CF-cluMA方法差。

表3 對比方法的預測評分準確度RMSE

表4 對比實驗組計算所消耗的時間(單位：秒)

在計算復雜度方面，DMF方法計算復雜度最低，耗時最少。PMF+P+N方法次之，SVD++方法隨著秩的增加，計算復雜度也隨之急劇增加。CF-cluMA方法的計算耗時是最少的，而SVD++，PMF+P+N和DMF方法的耗時均較高，而對比預測準確度較高的SVD++方法，其每次計算所需消耗的時間至少是CF-cluMA方法的十倍以上。而且，隨著秩的增加，SVD++方法的消耗時間成指數級增長。因此本文認為，盡管CF-cluMA方法和SVD++方法的預測評分誤差相對較小，但是前者的計算耗時較少。因此，從總體上來說，本文所提出的CF-cluMA方法要優于SVD++方法。

4 結論

本文針對推薦系統協同過濾方法中存在的數據稀疏性、可擴展性差問題提出了新的解決方法，即基于聚類矩陣近似的協同過濾推薦方法CF-cluMA。CF-cluMA方法借助于歷史用戶-商品評分數據進行評分預測，它通過對數據進行聚類，識別數據的內在局部結構，形成分塊矩陣，并借助于稠密分塊近似進行用戶-商品評分預測。該方法有三個優點：一是通過在分塊矩陣內部進行矩陣分解，達成了降低計算數據維度的目的；二是通過在分塊矩陣內存進行預測推薦提升了推薦系統的可擴展性，降低了推薦系統的復雜度；三是在分塊矩陣內進行推薦降低了不必要數據的干擾性，提高了推薦系統的預測評分準確性。與其它方法相比較，本文所提出的CF-cluMA方法的預測評分準確率高于DMF方法與PMF+P+N方法，與SVD++方法接近，并且在秩較小時優于SVD++方法。本文所提出的CF-cluMA方法的復雜度也小于現有的DMF方法、PMF+P+N方法和SVD++方法。在未來的工作中，本文將進一步研究如何選取商品和用戶同時聚類個數的參數優化，同時在矩陣分解中進一步考慮用戶-商品隱式評分和用戶實時行為[20,21]，以期實現更好的推薦效果。