楊文娟 金子馨

摘要：作為推薦系統(tǒng)中被普遍使用的算法之一，各大電商網(wǎng)站都會利用協(xié)同過濾算法來進行相應(yīng)物品的推薦。對協(xié)同過濾算法來說，推薦精度和時間效率兩個方面具有重要的研究價值。因此，如何結(jié)合這兩方面的優(yōu)勢，從而能設(shè)計一種時間效率較高，并且推薦精度很好的協(xié)同過濾推薦算法是一個很好的研究方向。為了應(yīng)對大數(shù)據(jù)時代的信息量過大的問題，聚類算法與協(xié)同過濾算法的結(jié)合屢見不鮮?；诖?，本文主要就各種聚類算法之間的不同，對聚類算法與協(xié)同過濾算法的不同結(jié)合方式進行了深入的討論，并就此進行了實驗對比分析。

關(guān)鍵詞：推薦系統(tǒng)；協(xié)同過濾；聚類；矩陣分解

中圖分類號：TP393 文獻標(biāo)志碼：A 文章編號：1009-3044（2018）16-0185-04

The Research on Collaborative Filtering Algorithm Based on Clustering

YANG Wen-juan， JIN Zi-xin

（School of Computer and Information， Hefei University of Technology， Hefei 230009， China）

Abstract： Collaborative Filtering （CF） is a popular way to build recommender systems and has been widely deployed by many e-commerce websites. For collaborative filtering algorithms， there are two parallel research directions on it， one is to improve the prediction accuracy of collaborative filtering algorithms， and others focus on reducing time cost of collaborative filtering algorithms. Nevertheless， the problem of how to combine the complementary advantages of these two directions， and design a collaborative filtering algorithm that is both effective and efficient remains pretty much open. In order to cope with the large amount of information in the era of big data， the combination of clustering algorithms and collaborative filtering algorithms is common. Based on this， the paper mainly discusses the different combinations of clustering algorithms and collaborative filtering algorithms. ， and conducted an experimental comparative analysis on this.

Key words： recommender systems； clustering； collaborative filtering algorithm； matrix factorization

互聯(lián)網(wǎng)的快速發(fā)展為信息時代的不同類型的用戶需求帶來了大量的信息。然而，它也帶來了一個新的問題，即信息過載問題。該問題給用戶選擇個人所需信息帶來困難，相應(yīng)地降低了信息的利用率。為了解決這個問題，推薦系統(tǒng)應(yīng)運而生[1，2]。

協(xié)同過濾算法是目前推薦系統(tǒng)領(lǐng)域許多電子商務(wù)網(wǎng)站使用最廣泛的算法之一[1，2，3]。該算法是利用與目標(biāo)用戶“品味”相類似的用戶，推薦這些用戶喜歡的物品給目標(biāo)用戶。協(xié)同過濾算法主要包括：基于鄰居的協(xié)同過濾[3]和基于模型的協(xié)同過濾算法[4，5，8]。基于鄰居的協(xié)同過濾時間復(fù)雜度低，但是對稀疏性和冷啟動問題較敏感?；谀Ｐ偷膮f(xié)同過濾算法能很好地解決這兩個問題，并且能得到很好的推薦精度，但是在時間效率方面仍有待提高。

因此，為了解決上述時間效率方面的問題，許多研究人員將聚類方法加入推薦系統(tǒng)中[6，7]。聚類算法可以將原有的用戶-項目評分矩陣聚類為多個子矩陣，由于每個子矩陣的屬性，這個子矩陣中的用戶和項目是具有強連接性質(zhì)的。然后，將傳統(tǒng)的協(xié)同過濾算法應(yīng)用到這些小矩陣的評分預(yù)測階段中。該方式不僅可以很好地解決時間效率問題，并且還能保證不錯的推薦精度。

因而，本文主要針對不同聚類算法與協(xié)同過濾算法的結(jié)合，在推薦精度方面進行了實驗對比分析。并且通過實驗得出結(jié)論，聚類算法與協(xié)同過濾算法的結(jié)合有助于提高推薦系統(tǒng)的實時性，對于在線系統(tǒng)來說是很有優(yōu)勢的。

1相關(guān)工作

基于模型的協(xié)同過濾算法具有較好的推薦性能，比較典型的有概率矩陣分解模型（PMF）[8]。為了進一步提高效率，研究人員開發(fā)了許多其他算法。例如，NHPMF [5]算法比PMF顯著提高了推薦的準(zhǔn)確性。即便如此，數(shù)據(jù)量呈指數(shù)形式的增長仍然讓基于模型的協(xié)同過濾算法“不堪重負”。因而，聚類算法應(yīng)用于協(xié)同過濾算法[6，16]成為一種有效解決方式。聚類的有效性主要體現(xiàn)在：通過聚類生成的類別的規(guī)模減小，聚類還可以減少評分的稀疏性。

起初，許多學(xué)者只考慮了將聚類應(yīng)用于項目[6，9]或用戶[10]以提高時間效率。但是，這些方法只考慮矩陣信息的一個維度而丟失另一維度信息。為了解決這個問題，有學(xué)者提出了基于聯(lián)合聚類的協(xié)同過濾算法[7]。與傳統(tǒng)的聚類方法相比，聯(lián)合聚類可以有效地找到用戶-項目評分矩陣的隱藏聚類結(jié)構(gòu)，同時對上述兩個維度進行聚類。聯(lián)合聚類算法將原始矩陣聚類成幾個小類別，每個小類別內(nèi)部密切相關(guān)。根據(jù)這種密切關(guān)系，評分預(yù)測階段可以獲得較少的計算量和較高的精度。

此前，文獻[11]提出了一種基于信息論的聯(lián)合聚類算法。后來，Agarwal [12]開發(fā)了一種利用廣義線性模型來平滑誤差函數(shù)的方法。隨后，研究人員提出了如何設(shè)置聚類類別數(shù)的參考標(biāo)準(zhǔn)[13]。但所有這些方法都是硬聚類[14]，即每個用戶、項目和評分只屬于一個單一的聚類類別。因此，有學(xué)者提出采用模糊聚類[15，17，18]來放寬對類別歸屬的限制。

雖然基于模型的協(xié)同過濾算法可以獲得高精度，但時間效率不高。聚類算法可以加速處理大規(guī)模數(shù)據(jù)集的過程，但是會犧牲推薦的準(zhǔn)確性。本文主要就不同聚類算法之間的差異，進行實驗對比分析。

2方法

假設(shè)我們想把用戶-項目評分矩陣聚類成K個類別。Agglomerative Clustering是一種自底向上的層次聚類方法，它是根據(jù)指定的相似度或者距離來進行類別的劃分的。主要按如下步驟進行：

1）將每個用戶（項目）當(dāng)作一個類別；

2）重復(fù)：每一輪合并指定距離最小的類別；

3）直到聚類的類別數(shù)等于K。

Spectral Clustering是一種使用很廣泛的聚類算法，該算法主要思想是將所有數(shù)據(jù)看作空間中的點，這些點通過邊來連接。每條邊上面有權(quán)重，權(quán)重的大小根據(jù)距離的遠近來決定，距離越近，權(quán)重越大，距離越遠，權(quán)重越小。通過對這一整個圖來進行劃分，切圖后，不同圖中的權(quán)值低，而同一圖中的權(quán)值較大。

Affinity Propagation聚類算法簡稱AP算法，基本思想是將所有數(shù)據(jù)點看作網(wǎng)絡(luò)中的節(jié)點，通過這些邊來傳遞消息，從而計算出聚類中心。吸引度和歸屬度是該聚類方法中的兩種消息。AP聚類算法根據(jù)每個節(jié)點的吸引度和歸屬度的更新來產(chǎn)生高質(zhì)量的聚類中心，同時將其他的不相似點聚類到別的類別中，從而完成整個聚類算法。

聯(lián)合聚類（Co-Clustering）將分別對所有的用戶、項目和評分進行聚類，并為它們分配概率，即每個聚類一個概率。然后，聯(lián)合聚類將這些獲得的軟分配結(jié)合起來，以改善下一輪聚類。上述過程將會重復(fù)，直到收斂。假設(shè)將用戶、項目和評分分配給類別[k]的概率為[p（k|ui，vj，rij）]。根據(jù)聯(lián)合聚類思想，我們可以將其表述為：

[p（k|ui，vj，rij）=AB] （1）

[A=p（k|ui）+a×p（k|vj）+b ×p（rij|k）+c] （2）

[B=k′=1Kp（k′|ui）+a×p（k′|vj）+b ×p（rij|k′）+c] （3）

其中，[k′]表示[K]個聚類中的某一個聚類，且[k′∈1，2，...，k，...K]；[a]，[b]，[c]是為了防止分母為零而設(shè)置的超參數(shù)，可根據(jù)具體環(huán)境設(shè)定，這里我們統(tǒng)一指定為1.0E-7。

當(dāng)上述這些聚類過程通過迭代方法收斂時，每個類別中的元素都互為鄰居，構(gòu)成鄰居集合。同時，由于上述聯(lián)合聚類是軟聚類，即一個用戶（項目）可能屬于幾個類別。我們簡單地將用戶（項目）分配給具有最大概率的類別。然后，將用戶-項目評分矩陣劃分為K個類別，以便并行地評分預(yù)測在每個類別中進行計算。

通過聚類挖掘用戶與項目之間的相互影響關(guān)系，在評分預(yù)測階段，以聚類[k]為例。如圖1所示，[xk]表示該類別中用戶的數(shù)量，[yk]表示該類別中項目的數(shù)量。該模型確保用戶的行為與它的鄰居集合相類似，并且項目與其鄰居集合相似。提出的用戶[ui]與項目[vj]的特征向量方程如下：

[Qki=e∈Cksui，ue×Qki+?Qk ?Qk?N（0，σ2QJ） ] （4）

[Lkj=p∈Ckzvj，vp×Lkj+?Lk ?Lk?N（0，σ2LJ）] （5）

從上面的兩個公式可以看出，每個用戶（項目）的潛在特征向量由兩個項組成。第一項是用戶（項目）鄰居的加權(quán)平均值，[s]代表用戶和用戶之間的相似度，[z]表示項目與項目之間的相似度。第二項是通過方差[σ2Q]和[σ2L]來控制的用戶和項目之間的差異項。據(jù)此，計算出類別[Ck]的先驗分布如下：

[p（Rk|Qk，Lk，σ2）=i=1xkj=1yk[N（rkij|QkiTLkj，σ2）]ωij] （6）

其中，[ωij]為指標(biāo)函數(shù)，如果用戶[ui]評價了項目[vj]，則指標(biāo)函數(shù)[ωij]等于1，否則等于0；建立如下誤差平方和目標(biāo)函數(shù)：

[Ek=12i=1xkj=1ykωij（rkij-QkiTLkj）2 +12λQi=1xkQki-e∈Cksui，ue×QkeF +12λLj=1ykLkj-p∈Ckzvj，vp×LkpF ] （7）

在上面的等式中，[λQ=σ2σ2Q]，[λL=σ2σ2L]。顯然該目標(biāo)函數(shù)由三部分組成。首先是實際評分與預(yù)測評分之間的關(guān)系；接下來的兩項是通過參數(shù)[λQ]和[λL]來進行平滑處理的鄰居信息。[λQ]控制用戶鄰居信息的影響程度；[λL]控制項目鄰居的影響程度。為了達到方程（7）的最小值，對每個用戶和項目使用隨機梯度下降法，從而得到最優(yōu)值。

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

Movielens是最悠久的推薦系統(tǒng)之一，同時也是一個以研究為目的的非商業(yè)性質(zhì)的實驗性站點，主要就是向用戶推薦他們可能感興趣的電影。MovieLens數(shù)據(jù)集包含的影片種類和數(shù)量繁多，用戶的數(shù)量更是驚人，是各大學(xué)者實驗過程中的首選。為了最大化利用有效信息進行推薦，實驗數(shù)據(jù)集包含了評分信息，標(biāo)簽信息以及其他一些潛在信息。為此，本文選用了推薦系統(tǒng)中常用的Movielens 10M數(shù)據(jù)集。本文選取的數(shù)據(jù)集包含了71567位用戶對10681部電影的10000054個評分記錄（0.5～5），其中還包含95580個標(biāo)簽。

3.2 評價標(biāo)準(zhǔn)

本文采用均方根誤差（RMSE）作為評價標(biāo)準(zhǔn)[19]。文中RMSE通過計算預(yù)測評分與實際評分間的偏差來判斷預(yù)測準(zhǔn)確度。RMSE能夠很好地反映出測量的精度，因而廣泛用于推薦系統(tǒng)中。具體地，RMSE越小，表示評分預(yù)測準(zhǔn)確度越高。假設(shè)算法對[N]部電影預(yù)測的評分向量表示為[{p1，...，pN}]，對應(yīng)實際評分向量為[{r1，...，rN}]，則該算法的RMSE表示為：

[RMSE=i=1N（pi-ri）2N] （8）

3.3實驗結(jié)果和分析

本小節(jié)的運行時間是聚類過后，在預(yù)測階段的一次迭代所消耗的時間。通過運行的時間比較可以得到結(jié)論，Spectral Clustering算法的運行時間相對較長，這是因為該算法聚類的結(jié)果不佳，導(dǎo)致在評分預(yù)測階段的尋找鄰居過程耽誤較多時間，因而導(dǎo)致時間消耗相對較多。Affinity Propagation算法不需要指定類別數(shù)，自適應(yīng)得到聚類類別，用戶與項目類別數(shù)不一致，并不能得到各自不相關(guān)的類別，因而并行處理不適用，時間效率較低。實驗結(jié)果表明，Co-Clustering算法的時間效率最高。

4總結(jié)

在本文中，我們主要針對目前出現(xiàn)的信息量呈指數(shù)式增長的問題，分析比較了不同聚類算法應(yīng)用于協(xié)同過濾算法的效果，并主要從時間效率和推薦精度兩方面進行了實驗對比分析。MovieLens數(shù)據(jù)集的實驗結(jié)果分析表明，聯(lián)合聚類算法和一般的聚類算法

比較而言，更能發(fā)現(xiàn)評分矩陣中隱藏的結(jié)構(gòu)，進而在評分預(yù)測階段得到更高的推薦精度。

參考文獻：

[1] Adomavicius G ，Tuzhilin A. Toward the Next Generation of Recommender Systems： A Survey of the State-of-the-Art and Possible Extensions. IEEE TKDE， pages 734-749， 2005.

[2] Linden G， Smith B and York J. Amazon.com Recommendations： Item-to-Item Collaborative Filtering. IEEE Internet Computing， pages 76-80， 2003.

[3] Sarwar B， Karypis G and Konstan J， et al. Item-based collaborative filtering recommendation algorithms. WWW， pages 285-295， 2001.

[4] Koren Y， Bell R and Volinsky C. Matrix Factorization Techniques for Recommender Systems. Computer， pages 30-37， 2009.

[5] Wu L， Chen E and Liu Q， et al. Leveraging tagging for neighborhood-aware probabilistic matrix factorization. CIKM， pages 1854-1858， 2012.

[6] Najafabadi M K， Mahrin M N and Chuprat S， et al. Improving the accuracy of collaborative filtering recommendations using clustering and association rules mining on implicit data. Computers in Human Behavior， pages 113-128， 2017.

[7] Wu Y， Liu X and Xie M， et al. Improving Collaborative Filtering via Scalable User-Item Co-Clustering. WSDM， pages 73-82， 2016.

[8] Mnih A and Salakhutdinov R R. Probabilistic Matrix Factorization. NIPS， pages 1257-1264， 2007.

[9] Wang Z， Wang X and Qian H. Item Type Based Collaborative Algorithm. CSO， pages 387-390， 2010.

[10] Shi X Y， Ye H W and Gong S J. A Personalized Recommender Integrating Item-Based and User-Based Collaborative Filtering. ISBIM， pages 264-267， 2008.

[11] Dhillon I S， Mallela S and Modha D S. Information-theoretic co-clustering. KDD， pages 89-98， 2003.

[12] Agarwal D and Merugu S. Predictive discrete latent factor models for large scale dyadic data. SIGKDD， pages 26-35， 2007.

[13] Xiao-Guang L I， Ge Y U， Wang D L， et al. Latent Concept Extraction and Text Clustering Based on Information Theory*： Latent Concept Extraction and Text Clustering Based on Information Theory[J]. Journal of Software， 2008， 19（9）：2276-2284.

[14] Geiger B C and Amjad R A. Hard Clusters Maximize Mutual Information， 2016.

[15] Hu L and Chan K C C. Fuzzy Clustering in a Complex Network Based on Content Relevance and Link Structures. TFS， pages 456-470， 2016.

[16] Hu W U， Wang Y J and Wang Z， et al. Two-Phase Collaborative Filtering Algorithm Based on Co-Clustering. JSW， pages 1042-1054， 2010.

[27] Mei J P， Wang Y and Chen L， et al. Large scale document categorization with fuzzy clustering. TFS， pages 1， 2016.

[18] Bu J， Shen X and Xu B， et al. Improving Collaborative Recommendation via User-Item Subgroups. TKDE， pages 2363-2375， 2016.

[19] Chai T and Draxler R R. Root mean square error （RMSE） or mean absolute error （MAE）？ - Arguments against avoiding RMSE in the literature. GMD， pages 1525-1534， 2014.