趙廣艷，李禹生，韓 昊

(武漢輕工大學(xué)數(shù)學(xué)與計算機學(xué)院，湖北武漢430023)

協(xié)同過濾個性化推薦是電子商務(wù)個性化推薦中應(yīng)用最多的技術(shù)之一。近年來，國內(nèi)外學(xué)者對協(xié)同過濾算法做了大量研究工作，并取得了豐碩成果，許多大型電子商務(wù)網(wǎng)站，如 Amazon，Ebay，Levis，阿里巴巴，當當網(wǎng)上書店等都采用了各種形式的推薦系統(tǒng)功能。伴隨著電子商務(wù)規(guī)模的增大，用戶與項目的數(shù)量急劇上升，協(xié)同過濾算法面臨的關(guān)鍵挑戰(zhàn)是數(shù)據(jù)稀疏性，算法的可擴展性。由于算法的計算量大，導(dǎo)致算法的性能急劇下降?；谟脩艟垲惖膮f(xié)同過濾推薦算法［1］，與傳統(tǒng)的協(xié)同過濾算法相比，提高了推薦速度和質(zhì)量，但是只考慮了用戶相似性。王輝等提出了個性化服務(wù)中基于用戶聚類的協(xié)同過濾推薦［2］，該算法對可擴展性和數(shù)據(jù)型稀疏性方面進行了一定改進，但是效率和準確度還有待提高。

在協(xié)同過濾推薦算法中，需要處理的數(shù)據(jù)都是根據(jù)用戶-項目評分矩陣來進行的。針對協(xié)同過濾算法存在的可擴展性和數(shù)據(jù)稀疏性，筆者引入聯(lián)合聚類(BlockClust，簡稱BC)和帶正則化的迭代最小二乘法(alternating-least-squares with weighted-regularization，簡稱AW)，提出了一種基于BC-AW的協(xié)同過濾推薦算法，有效緩解了傳統(tǒng)算法難以并行化、可擴展性差的問題，整個算法主要分為兩步:①在原始評分矩陣中進行用戶—項目兩個維度的聯(lián)合聚類，聚類后生成具有相同模式評分塊的若干子矩陣，聯(lián)合聚類后的子矩陣規(guī)模遠小于原始評分矩陣，大幅度降低預(yù)測階段計算量。②在聯(lián)合聚類后生成的每個子矩陣上分別利用帶正則化的迭代最小二乘法的協(xié)同過濾算法來預(yù)測子矩陣中的未知評分，進而進行推薦。

1 聯(lián)合聚類

怎樣處理大量并且很稀疏的訓(xùn)練數(shù)據(jù)是協(xié)同過濾算法面臨的關(guān)鍵問題，因此通過聯(lián)合聚類的方法將原始訓(xùn)練數(shù)據(jù)劃分成數(shù)據(jù)規(guī)模較小、相似度較高的子矩陣是一種有效的方法。對于協(xié)同過濾算法問題，聯(lián)合聚類算法應(yīng)用到協(xié)同過濾算法有兩大優(yōu)勢:①需要處理的數(shù)據(jù)規(guī)模大量減少，算法的復(fù)雜操作會變得相對容易;②有效緩解評分稀疏性。

協(xié)同過濾算法，就是處理用戶—項目評分矩陣，聯(lián)合聚類的目的就是縮小子矩陣內(nèi)部評分數(shù)據(jù)間的差異。以評分模式為標準的聯(lián)合聚類［3］采用的思路是掃描用戶—項目評分矩陣中已經(jīng)有的評分，進行行聚類與列聚類兩個步驟進行概率計算，每次迭代都需要重新評估計算用戶、項目、評分這三者屬于每個子矩陣的概率直至收斂。將每個評分分配到所求概率最大的那個子矩陣，不同的子矩陣可能包含同一個用戶—項目。每個子矩陣的用戶、項目、評分會組成新矩陣，此時的新矩陣已經(jīng)是高相似性評分的子矩陣，可以快速有效應(yīng)用計算。

聯(lián)合聚類后原來非常稀疏的用戶—項目評分矩陣轉(zhuǎn)變成為K個規(guī)模較小的子矩陣，每個子矩陣的內(nèi)部評分相似度較高并且相對稠密，從而可以進行有效的降維。在下一階段的評分預(yù)測也會變更容易、更準確。

對評分模式為標準的聯(lián)合聚類，掃描評分矩陣，計算每個評分屬于某子矩陣的概率p(k|u，v，r)，要判定一個評分屬于某子矩陣，需要考慮與評分所關(guān)聯(lián)的用戶—項目屬于該子矩陣的概率分別為p(k|u)與p(k|v)，以及該評分值出現(xiàn)在這個子矩陣中的概率p(r|k)。計算公式如下:

其中，u為當前用戶，v為當前項目，r為評分值，r'為1到5的整數(shù)，k為當前聚類，k'為累加時的當前聚類，U(v)為給項目v評過分的所有用戶集合，V(u)為用戶u已評過分的所有項目集合，為了防止分母為0需要設(shè)置超參數(shù)α，β，θ，可根據(jù)具體情況設(shè)定，在下面的實驗中統(tǒng)一設(shè)為0.000 000 1。

2 帶正則化的迭代最小二乘法的矩陣分解

在預(yù)測階段，評分預(yù)測可以選用很多種矩陣填充方法，例如簡單的k-最近鄰模型預(yù)測方法，基于傳統(tǒng)的矩陣分解模型的方法。通過考慮，這里采用改進的矩陣分解算法(alternating-least-squares with weighted-regularization，簡稱 AW)［4］來進行評分預(yù)測。對于聯(lián)合聚類后的子矩陣，AW方法可以在極短的時間內(nèi)收斂到局部最小。

給定一個矩陣R，Rij為矩陣的元素，Ri·為矩陣R的第i行，R·j為矩陣的第j列，RT為矩陣R的轉(zhuǎn)置。R－1為矩陣的逆。矩陣 A∈Cm×d、B∈Cn×d分別為用戶和項目矩陣的特征矩陣，I為一個d×d的單位矩陣。

為了能夠找到低秩矩陣X來最大程度的接近矩陣R，最小化下面損失函數(shù)

其中，X=ABT，d為特征數(shù)目，一般情況下d＜＜r，r為矩陣R 的秩，r≤min(m，n)，Xij為X 矩陣的元素。

式(5)中(Rij－Xij)2是低秩逼近中常見平方誤差項，由X=ABT把式(5)改成有效并且快速的求解最優(yōu)化問題。

給式(6)加上正則化項來預(yù)防過擬合現(xiàn)象，則式(6)可以改寫成:

固定 B，對 Ai·求導(dǎo)，得到求解 Ai·的公式如式(8)所示。

同理，根據(jù)式(8)固定A，可以得到Bj.的公式為:

3 基于BC-AW的協(xié)同過濾推薦算法

為了預(yù)測評分矩陣中的未知項，采用兩階段算法。具體算法如下:

第1階段聯(lián)合聚類

輸入:用戶—項目評分矩陣R，子矩陣個數(shù)K。

輸出:K個子矩陣

Step1:隨機初始化用戶u，項目v，評分r共同屬于聚類k的概率p(k|u，v，r)，使得

Step2:根據(jù)式(2)計算用戶u屬于聚類k的概率p(k|u);

Step3:根據(jù)式(3)計算用戶v屬于聚類k的概率p(k|v);

Step4:根據(jù)式(4)計算分值概率p(r|k);

Step5:根據(jù)式(1)計算 p(k|u，v，r)，并選取概率最大的k作為該評分的子矩陣;

Step6:跳轉(zhuǎn)到Step2，直至收斂，否則結(jié)束程序。

第2階段:基于AW的協(xié)同過濾評分預(yù)測

輸入:子矩陣所對應(yīng)的用戶-項目評分矩陣;

輸出:預(yù)測評分矩陣X;

Step1:隨機初始化A、B;

Step2:用式(8)、式(9)反復(fù)迭代更新A、B，直到收斂或迭代次數(shù)足夠多而結(jié)束迭代;

分析基于BC-AW的協(xié)同過濾推薦算法，可以看出該算法的第2階段的關(guān)鍵步驟是Step2，運用公式反復(fù)迭代更新A和B直到收斂或迭代次數(shù)足夠多而結(jié)束迭代。通過式(8)、式(9)可分析出，可以對矩陣A、B進行分割，因為每次調(diào)用公式只是計算更新矩陣A、B的一行值。把矩陣A、B分成多個具有相同列長的矩陣來進行并行運算，從而緩解了傳統(tǒng)的基于矩陣分解的協(xié)同過濾算法難以并行化、可擴展性差的問題。

4 實驗結(jié)果分析

4.1 實驗數(shù)據(jù)集和度量標準

該文選取MovieLens數(shù)據(jù)集評估改進算法的性能，MovieLens是美國的明尼蘇達州立大學(xué)(University of Minnesota)的GroupLens研究小組搜集的電影評價數(shù)據(jù)集。該數(shù)據(jù)集中包括943位用戶對1682部電影的十萬條評分數(shù)據(jù)(評分值為1到5的整數(shù))，5表示評分最好，1表示評分最差，每個用戶至少給出20個評分。

將原數(shù)據(jù)集分為訓(xùn)練集與測試集，從原數(shù)據(jù)集中隨機抽取80%的評分數(shù)據(jù)作為一個訓(xùn)練集，記為Train80;原評分數(shù)據(jù)中除Train80以外的數(shù)據(jù)集構(gòu)成測試集，記為Test20;把Train80中的評分數(shù)據(jù)集中的1/2抽取出來作為另一個訓(xùn)練集，記為Train40。通過訓(xùn)練集生成模型，對測試集進行評分預(yù)測，根據(jù)預(yù)測評分的結(jié)果與原實際評分之間的偏差來度量預(yù)測的準確性。本文采用的評估方法為均方根誤差 RMSE［5］(Root Mean Square Error)的方法，RMSE值越小，代表準確度越高。假設(shè)n表示將要評估預(yù)測評分的項目數(shù)量，用戶對n個項目的預(yù)測評分值集合為 {p1，p2，...，pn}，實際評分值集合為 {q1，q2，...qn}，RMSE 的計算公式如下:

4.2 結(jié)果分析

評價推薦系統(tǒng)推薦質(zhì)量的度量標準采用式(10)統(tǒng)計度量方法中的均方根誤差 RMSE。對MovieLens進行評分預(yù)測，算法的超參數(shù)設(shè)置如下:α=β=θ=0.000 000 1。對于子矩陣個數(shù)K的設(shè)置做了一組實驗，實驗結(jié)果如圖1所示。

圖1 子矩陣個數(shù)K與RMSE的關(guān)系

由圖1可知，在各種實驗條件下，在訓(xùn)練集為Train80類別數(shù)為50的情況下RMSE最小，系統(tǒng)推薦質(zhì)量最好。在以下的實驗中，采用類別數(shù)K為50。

將基于BC-AW的協(xié)同過濾算法的有效性進行對比實驗，參與對比實驗的算法包含Hofmann提出的潛在語義模型協(xié)同過濾算法(LSM)［6］和基于矩陣分解的協(xié)同過濾算法(ALS-WR)。各個算法均分別在Train80，Train40訓(xùn)練集上訓(xùn)練，在Test20上測試得到RMSE值，實驗數(shù)據(jù)如圖2所示。

圖2 不同算法性能比較結(jié)果

從圖2可以看出，本算法的均方根誤差較小，說明推薦準確度得到了一定的提升。

5 結(jié)束語

該文提出了基于聯(lián)合聚類和迭代最小二乘法的兩階段協(xié)同過濾算法。首先對原始評分數(shù)據(jù)進行基于用戶—項目的聯(lián)合聚類，即以評分值為標準，尋找具有相同模式的評分塊，從而把原始評分矩陣劃分成為相互可能有交叉的評分子塊，聚類后的矩陣規(guī)模遠小于原始評分矩陣，可快速靈活的進行評分預(yù)測。在評分預(yù)測階段，采用基于AW的協(xié)同過濾算法的評分預(yù)測，并分析了其可擴展性及抗稀疏性問題。分別在Train80，Train40的訓(xùn)練集下采用不同類別數(shù)K下，比較了均方根誤差，找出了效果最好的條件。在效果最好的條件下，和幾個經(jīng)典協(xié)同過濾算法進行比較。實驗結(jié)果表明，BC-AW算法優(yōu)于幾個經(jīng)典的協(xié)同過濾算法。

［1］李濤，王建東，葉飛躍，等.一種基于用戶聚類的協(xié)同過濾推薦算法［J］.系統(tǒng)工程與電子技術(shù)，2007，29(7):1178-1182.

［2］王輝，高利軍，王聽忠.個性化服務(wù)中基于用戶聚類的協(xié)同過濾推薦［J］.計算機應(yīng)用，2007，27(5):1225-1227.

［3］吳湖，王永吉，王哲，等.兩階段聯(lián)合聚類協(xié)同過濾算法［J］.軟件學(xué)報，2010，21(5):1042-1054.

［4］李改，李磊.基于矩陣分解的協(xié)同過濾算法［J］.計算機工程與應(yīng)用，2011，47(30):4-7.

［5］Koren Y.Factorization meets the neighborhood:A multifaceted collaborative filtering model［C］//Proc of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，2008:426-434.

［6］Hofmann T.Latent semantic models for collaborative filtering［J］.ACM Trans actions on Information Systems，2004，22:89-115.