基于矩陣分解的協(xié)同過濾推薦算法

紀 平， 胡學友， 楊文娟 ，劉學亮

(1.合肥學院 先進制造工程學院,合肥 230601；2.合肥工業(yè)大學 計算機與信息學院,合肥 230009)

0 引 言

近年來，隨著互聯(lián)網(wǎng)的迅速革命，用戶可以獲得大量的信息，以滿足信息時代的各種需求。但它帶來了一個新的問題，即信息爆炸，這使得用戶很難搜索到他們想要的信息，從而降低了利用率。在此背景下，推薦系統(tǒng)的應運而生，為用戶選擇有用的信息提供了一種個性化的方式。[1-2]

為了解決這一問題，協(xié)同過濾被提出并成為目前許多推薦系統(tǒng)中最常用的解決方案之一。它首先根據(jù)屬性對用戶進行分類，然后找到一些具有相似偏好的活躍用戶[1,3]，系統(tǒng)將推送這些活動用戶首選的項目。如今，許多知名的互聯(lián)網(wǎng)公司如Google、Youtube、Flickr和Amazon已經(jīng)成功地將協(xié)同過濾算法應用到實際系統(tǒng)中，為他們的在線用戶提供推薦。[2]在這些解決方案中，主要有兩種不同類型的協(xié)同過濾，即基于近鄰的協(xié)同過濾[4]和基于模型的協(xié)同過濾。[5]基于近鄰的協(xié)同過濾算法簡單，易于理解。然而，由于在稀疏用戶項評分中很難找到穩(wěn)定可靠的近鄰，這些方法運行時間較長，預測精度不高?；谀Ｐ偷姆椒ǖ闹饕菍ふ乙粋€設計良好的潛在子空間來嵌入用戶和項目之間的關系，在這個子空間中可以計算出預測或評分。[5-6]這些基于模型的算法在過去幾年中取得了巨大的成功，但無法應用于數(shù)據(jù)量巨大的實際系統(tǒng)中，而且這些CF算法的推薦時間較長。因此，如何減少這些算法的運行時間是構建實際系統(tǒng)的一個重要研究方向。

在過去的幾年中，為了解決上述問題，許多研究者考慮并成功地將一些聚類方法應用到推薦系統(tǒng)中。[7-9]在這些算法中，通過預先定義的聚類將原始用戶項目評分矩陣分解為幾個特征維數(shù)較低的子矩陣。遵循經(jīng)典的推薦算法，可以在這些小矩陣中同時使用，以提高其效率。但最新研究表明，基于聚類的方法可能會降低最終預測結果的準確性。

本文主要研究如何提高現(xiàn)有協(xié)同過濾算法的有效性和效率。為此，提出了一種新的解決方案，將矩陣分解和協(xié)同聚類相結合來解決這一問題。該方法的核心思想是將聚類算法的特性應用到CF(Collaborative Filtering)算法中。具體地說，在MFCC算法中，首先提出了一種新的協(xié)同聚類算法，將原始的評分矩陣分解為低維的小矩陣。這種聚類后的矩陣與用戶之間保持著高度的關系。然后，嘗試用潛在分析法對每個子矩陣中的用戶或項目之間的內在聯(lián)系進行建模。在這個處理過程中，還可以確保不同集群中的每個用戶或項目更加接近。該方法不僅能顯著降低訓練階段的時間開銷，而且能保證最終預測結果的準確性，因此具有新穎性。在一個公共數(shù)據(jù)集MovieLens上進行了大量的實驗，結果表明所提出的MFCC方法在效率和有效性方面均有所改善。

1 相關工作

1.1 協(xié)同過濾算法

協(xié)同過濾作為推薦系統(tǒng)的重要組成部分，受到了業(yè)界和學術界的廣泛關注。[2,10-11]從運行方式來看，協(xié)同過濾主要包括基于近鄰的協(xié)同過濾和基于模型的協(xié)同過濾算法。

在給定用戶上預測項目的常用框架是基于近鄰的方法。收集用戶評分并估計平均評分的類似項目，作為對新項目的預測。完成這項任務有兩種方法，基于用戶的推薦和基于項目的推薦。[12-14]

與基于近鄰的推薦不同，基于近鄰的推薦是通過研究系統(tǒng)的評分來直接對項目進行排序并做出最終的決策，而基于模型的方法可以根據(jù)這些評分記錄學習一個模型。在這個解決方案中，用戶-項目交互是通過機器學習方法來描述的。從以前的記錄中訓練出一個模型后，它就可以用來為用戶排列新的項目。

1.2 協(xié)同過濾算法的效率

雖然CF方法已經(jīng)得到廣泛的分析，但是隨著在線數(shù)據(jù)量的迅速增加，這些需要更多時間運行的算法效率不高，不能滿足用戶的需求。在實際應用中，有兩種方法可以解決這個問題：降維方法和聚類方法。

第一種解決方案是降維方法[15-18]，將用戶和項目的表示轉換到一個嵌入的潛在特征空間中，在該空間中可以捕捉到最具代表性的特征。在這種高級特征空間中，用戶與項目元素之間的關系可以計算出來，而在低維特征空間中，用戶與項目元素之間的關系可以得到更合理的利用。Badrul Sarwar等人[19]探索了基于項目的協(xié)同過濾技術以產(chǎn)生高質量的推薦。該方法利用奇異值分解模型對用戶和項目評分矩陣進行降維處理，得到潛在表示。

第二種方法是聚類，它用于對大規(guī)模數(shù)據(jù)集進行分割，將稀疏數(shù)據(jù)分成多個相似度高、數(shù)據(jù)量小的數(shù)據(jù)集。將聚類應用于CF[7,19]有許多不同的優(yōu)點，如：加快數(shù)據(jù)處理速度、降低評分矩陣的稀疏性等。目前許多研究都是先對項目[7,20]或用戶[21]應用聚類算法來減少運行時間。

然而，在這些方法中，研究者一般只利用了評分矩陣的一個維度，而忽略了另一個維度，沒有對其進行研究。針對這一問題，本文提出了一種將協(xié)同聚類方法應用于協(xié)同過濾的解決方案。[9]與以往的聚類方法相比，協(xié)同聚類不僅能發(fā)現(xiàn)用戶項目評分矩陣中的潛在模式，而且能同時有效地從上述兩個維度對信息進行聚類。為了使分配更加柔和，一些新的方法被提出，即利用軟聚類策略[22-25]進一步挖掘類別屬性。例如文獻[9]和[27]分析了基于協(xié)同聚類多個數(shù)據(jù)集的不同CF算法的實驗結果。

如上所述，雖然基于模型的協(xié)同過濾算法可以很好地對數(shù)據(jù)集中的模式進行建模，并在預測過程中獲得較高的精度，但是它們需要更多的時間來運行，因此效率不夠高。同時，協(xié)同聚類[8]解決方案可以加快大規(guī)模數(shù)據(jù)集的處理過程，但準確度會同時降低。本文提出了一個將協(xié)同聚類和矩陣分解相結合的解決方案，來設計一個兼顧算法效率和精度的MFCC方法。

2 解決方案

如圖1所示，MFCC方法有兩個步驟。第一步是協(xié)同聚類，其目標是找到一種將評分矩陣分解為幾個低維矩陣的方法，以提高效率；第二步是建立評分模型，是從這些小矩陣中并行地建立評分模型，并根據(jù)獲得的評分結果有效地推薦項目。

圖1 MFCC推薦方法框架

2.1 提出的算法

表1列出了本文涉及的相關符號及其意義，大寫字母表示數(shù)據(jù)集，小寫字母表示用戶或項目。在求解過程中，首先使用協(xié)同聚類算法將原始矩陣分解為幾個低維矩陣。分割后的子矩陣之間有著密切的聯(lián)系，因此在第二步中可以得到更少的計算量和更高的精度。

表1 符號約定

其目的是將用戶-項目評分矩陣聚類到基于軟分配策略的k個小矩陣。與傳統(tǒng)的硬聚類方法不同，在每次迭代中，該方法首先對所有用戶、項目和評分進行聚類，以每個聚類一個概率的方式對其進行賦值。然后將這些軟指派應用于協(xié)同聚類，以提高下一輪的準確度。聚類過程中，前后兩次軟分配的差異不斷減小，當兩次軟分配結果的差異小于給定值時，算法終止。

從數(shù)學上講，設p(k|u,v,r)是用戶u、項目v和評分r分別分配到聚類k的概率。軟協(xié)同聚類算法可以表述為：

(1)

其中P(k|u)和P(k|v)是元素分配到聚類k中的概率。此外，等式(1)中的a、b和c被設置為一個小值，以避免分母為零。此外，等式(1)可計算如下：

(2)

(3)

(4)

由式(2)、式(3)和式(4)可知，當這個協(xié)同聚類過程經(jīng)過優(yōu)化處理迭代收斂時，群中的元素彼此接近，可以建立一個近鄰集。同時，因為上述聚類分配是有概率的，則一個用戶可以屬于多個聚類。在這項工作中，用戶被軟分配到一個具有最大概率P(k|v)的聚類中。最后，通過這樣的處理將用戶-項目評分矩陣劃分為k個聚類。接下來就可以并行處理每個聚類中的評分。

在用軟協(xié)同聚類方法對用戶和項目集之間的關系進行建模時，我們以聚類k為例來說明訓練實例。如圖1所示，讓xk和yk分別是聚類中的用戶和項目號。該模型假設用戶i和項目j具有與其近鄰相似的模式?；谶@樣的假設，我們可以對每個項目和用戶的特征建模如下：

(5)

(6)

(7)

(8)

將公式(7)和(8)與評分數(shù)據(jù)R相結合，可以定義如下方程：

(9)

其中ω是一個指標，當用戶i對項目j評分時，該指標設為1；如果用戶i對項目j不評分，則該指標設為0。我們對等式(7)、等式(8)和等式(9)進行貝葉斯推斷，可以得到以下方程：

(10)

(11)

為了求解方程(11)并求出最小值，根據(jù)方程(7)和(8)，對每個用戶和每個項目使用隨機梯度下降法。所以偏導數(shù)可以計算如下：

(12)

(13)

2.1 效率分析與討論

新的算法主要分為三個部分。第一部分是協(xié)同聚類，其時間復雜度為O(iter1×L×K)，其中iter1為協(xié)同聚類中的迭代次數(shù)，L為評分矩陣中的非零值，k為聚類數(shù)。第二部分計算用戶和項目的相似度，時間復雜度為O(M2+N2)。第三部分是評分模型訓練。但是，由于首先進行協(xié)同聚類，所以在訓練評分模型時，可以并行計算每個聚類的協(xié)同聚類。因此，根據(jù)等式(12)和(13)，用戶和項目的偏導數(shù)的時間復雜度分別為O(iter2×(L×D+xMD)/k))和O(iter2×(L×D+yND)/k))。在該部分中，時間復雜度為O(iter2×(L×D+xMD+yND)/k))，其中iter2、D、x和y分別表示訓練過程中的迭代次數(shù)、特征維數(shù)、每個用戶的個數(shù)和項目簇。

3 實驗和分析

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

由于在協(xié)同過濾評分中的廣泛應用，我們選擇MovieLens 10M數(shù)據(jù)集(http://www.movielens. org)作為評估數(shù)據(jù)集。這個數(shù)據(jù)集有71 567個用戶，10 681部電影和10 000 054個評分記錄。

3.2 評價標準

在這項工作中，均方根誤差(RMSE)被用來評估該方法的準確性。[6]RMSE越小，預測精度越高。如果預測的等級向量為{p1,...,pN}，對應的真實評分向量為{r1,...,rN}，則算法的RMSE為：

(14)

3.3 比較方法

在這項工作中，為了評估該方法的有效性和效率，我們將其與以下四種評級方法進行比較。

(1)PMF：它是在文獻[26]中提出的，是一種基于低維因子模型的經(jīng)典協(xié)同過濾算法。具體地說，與SVD相似，該算法是一個圖形模型，它表明評分矩陣可以分解為兩個低階的潛在矩陣，即用戶和項目矩陣，隨后的推薦由兩個矩陣執(zhí)行。雖然該算法是有效的，但它在實際應用中并不是有效的。

(2)Co-Clustering：這個算法是在文獻[27]中提出的，通過聚類將評分矩陣分解成幾個小矩陣。在每個集群中，所有的元素(用戶或項目)彼此更接近。然后利用矩陣分解對未知的評分進行預測。該方法在處理大規(guī)模數(shù)據(jù)集時具有良好的性能，但運行時間較長。

(3)協(xié)同聚類與PMF的結合(表示為CCPMF)：該方法將PMF與協(xié)同聚類相結合，分為兩個階段。首先將評分矩陣分解為小規(guī)模的潛在子評分矩陣。在第二階段中，利用PMF分解每個聚類中的用戶和項目矩陣。然后用兩個矩陣對缺失值進行預測。由于該方法是協(xié)同聚類與PMF相結合的方法，其有效性有待提高。

(4)NHPMF: NHPMF是在文獻[19]中提出的，旨在提高推薦系統(tǒng)的預測精度。它首先利用額外的信息來獲得每個用戶或項目的近鄰關系。然后對用戶和項目特征矩陣采用矩陣分解算法進行最終決策。該方法運行速度快，但預測精度不高。

3.4 實驗結果及詳細分析

3.4.1 參數(shù)的算法

在實驗中，首先評估參數(shù)λ，該參數(shù)表示算法中用戶或項目受其鄰居影響的程度。當維度D的配置設置為10到25的范圍內時，λ=λU=λV。從圖2可以看出，λ對結果有著巨大的影響。算法的性能隨著λ的增加而提高。但是，當λ大于10時，算法的精度會下降，這說明λ過大會導致過擬合。所以我們在隨后的評估中設置λ=10。此外，隨著λ的增加，需要更多的迭代來使RMSE滿足最小值。換句話說，當λ增加時，需要更多的時間來訓練模型，如圖3所示。

圖2 RMSE中的

圖3 與的迭代

3.4.2 性能評價與其他方法的比較

比較了MFCC和其他四種算法的性能，結果如表2所示。在本節(jié)中，將特征向量的維數(shù)D分別設置為5、10、15、20和25。

表2 不同方法的RMSE結果

從結果可以看出，MFCC方法在精度上優(yōu)于PMF方法和協(xié)同聚類方法。究其原因，用戶和項目之間的關系沒有用PMF和協(xié)同聚類來建模。此外，為了提高準確度，MFCC利用外部信息，包括標簽和近鄰關系。由于相似的原因，CCPMF的精度也低于MFCC。與NHPMF相比，MFCC獲得了可比的性能，在協(xié)同聚類過程中，MFCC的近似計算可能會對聚類精度產(chǎn)生負面影響。然而，如表4所示，MFCC的運行速度比NHPMF快。在大數(shù)據(jù)時代，它可以廣泛應用于許多實際應用中。

3.4.3 運行時間

在這一部分中，分析了MFCC與其他方法的運行時間，也就是每種算法在訓練期間迭代所需的時間。實驗運行在win10系統(tǒng)下，采用3.00GHZ的Intel i5 CPU 和12G內存。

不同聚類下的訓練時間見表3。

從表3可以看出，隨著聚類簇的增加，協(xié)同過濾算法需要更多的運行時間。這可能是因為在協(xié)同聚類中，時間復雜度為O(iter1×L×K)與K成線性關系。

表3 不同K值的運行時間

當設置λU=λV=λ，D為10時，每個算法使用的運行時間如表4所示。

表4 不同算法的運行時間

從表4可以看出，PMF和MFCC算法比其他方法更有效。這是由于PMF算法不用建立近鄰關系模型，其時間復雜度只取決于要預測的條目數(shù)。NHPMF算法不僅要對近鄰關系建模，而且還要對標簽信息進行建模，因此需要很長的運行時間。MFCC算法源于NHPMF，理論上其時間復雜度也高于其他方法。但由于協(xié)同聚類后的并行計算機制，其運行速度比NHPMF算法快40倍，效率得到了顯著提升。

3.4.4 不同的聚類算法

為了深入分析所提出的方法，本文還比較了不同聚類算法的影響。特別地，我們使用凝聚聚類、光譜聚類和親和力傳播。凝聚聚類是一種層次聚類策略，它以自下而上的方式形成集群。光譜聚類是通過度量項目間的相似度來對數(shù)據(jù)進行聚類。通常對從相似矩陣中得到的拉普拉斯矩陣的特征向量使用一種簡單的聚類方法(如k-means)。親和力傳播是另一種流行的基于數(shù)據(jù)點間消息傳遞處理的聚類算法。在運行算法之前，它不需要預先定義的集群數(shù)量。所有這些聚類方法在許多任務中都得到了廣泛的應用。

在實驗中使用這些算法作為聚類的基礎，RMSE評估的結果如表5所示。

表5 不同聚類方法的RMSE比較

在表5中可以發(fā)現(xiàn)與其他方法相比，譜聚類的性能最差。與光譜聚類相比，親和傳播和凝聚聚類具有更好的精度。在這些方法中，協(xié)同聚類由于充分利用了用戶和項目之間的關系而具有最好的性能。在這個表中，還可以得出這樣的結論：維度越高，性能越好。當D=25時，所有方法均達到最佳效果。

除了準確度外，還評估了每種聚類方法的時間開銷和預測過程中每個循環(huán)的運行時間。結果見表6。從表中可以看出，與其它方法相比，協(xié)同聚類是非常有效的。具體來說，譜聚類沒有很好的聚類性能，而且需要花費大量的時間來尋找每個數(shù)據(jù)點的鄰居。相似性傳播不需要預定義的簇號作為輸入，但是查找簇號需要花費大量的時間。通過與兩種聚類方法的比較，得出結論：與兩種聚類方法的聚類結果進行了比較。

表6 不同聚類方法的運行時間

4 結 論

本文針對協(xié)同聚類算法的有效性和效率問題，提出了一種在保證預測精度的前提下減少運行時間的MFCC方法。在我們的解決方案中，結合了協(xié)同聚類和矩陣分解，可以同時發(fā)揮這兩種算法的優(yōu)勢。通過大量的實驗，對所提出的方法進行了有效性和效率的評估，結果表明我們的方法優(yōu)于其它推薦算法。