基于聚類(lèi)的協(xié)同過(guò)濾算法的研究

楊文娟 金子馨

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

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

中圖分類(lèi)號(hào)：TP393 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：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ā)展為信息時(shí)代的不同類(lèi)型的用戶(hù)需求帶來(lái)了大量的信息。然而，它也帶來(lái)了一個(gè)新的問(wèn)題，即信息過(guò)載問(wèn)題。該問(wèn)題給用戶(hù)選擇個(gè)人所需信息帶來(lái)困難，相應(yīng)地降低了信息的利用率。為了解決這個(gè)問(wèn)題，推薦系統(tǒng)應(yīng)運(yùn)而生[1，2]。

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

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

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

1相關(guān)工作

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

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

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

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

2方法

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

1）將每個(gè)用戶(hù)（項(xiàng)目）當(dāng)作一個(gè)類(lèi)別；

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

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

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

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

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

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

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

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

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

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

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

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

其中，[ωij]為指標(biāo)函數(shù)，如果用戶(hù)[ui]評(píng)價(jià)了項(xiàng)目[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ù)由三部分組成。首先是實(shí)際評(píng)分與預(yù)測(cè)評(píng)分之間的關(guān)系；接下來(lái)的兩項(xiàng)是通過(guò)參數(shù)[λQ]和[λL]來(lái)進(jìn)行平滑處理的鄰居信息。[λQ]控制用戶(hù)鄰居信息的影響程度；[λL]控制項(xiàng)目鄰居的影響程度。為了達(dá)到方程（7）的最小值，對(duì)每個(gè)用戶(hù)和項(xiàng)目使用隨機(jī)梯度下降法，從而得到最優(yōu)值。

3.1 實(shí)驗(yàn)數(shù)據(jù)集

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

3.2 評(píng)價(jià)標(biāo)準(zhǔn)

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

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

3.3實(shí)驗(yàn)結(jié)果和分析

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

4總結(jié)

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

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

參考文獻(xiàn)：

[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.