基于多級圖劃分的協(xié)同過濾算法研究

柳先輝，徐夢錦

(同濟大學電子與信息工程學院CAD研究中心，上?！?01804)

?

基于多級圖劃分的協(xié)同過濾算法研究

柳先輝，徐夢錦

(同濟大學電子與信息工程學院CAD研究中心，上海201804)

摘要：為克服傳統(tǒng)協(xié)同過濾推薦算法中存在的局限性，提出了基于多級圖劃分的協(xié)同過濾推薦算法。該算法在對系統(tǒng)中存在的產(chǎn)品使用多級圖劃分算法進行聚類的基礎上應用協(xié)同過濾推薦算法對用戶進行推薦。實驗結(jié)果證明，該算法可以在對推薦準確率影響較小的同時有效提高推薦系統(tǒng)的效率。

關(guān)鍵詞：協(xié)同過濾；多級圖劃分；聚類

推薦算法作為一種信息過濾技術(shù)，已經(jīng)成為當下解決互聯(lián)網(wǎng)上信息過載的一種有效工具[1]。在眾多推薦方法中，協(xié)同過濾是推薦系統(tǒng)中應用最為成功的技術(shù)之一[2]。采用協(xié)同過濾推薦技術(shù)的應用十分廣泛，其中Tapestry[3]是最早的推薦系統(tǒng)之一，系統(tǒng)記錄每個用戶閱讀文章的觀點，并根據(jù)這些觀點對用戶進行推薦。典型的個性化推薦系統(tǒng)包括Amazon[4]購書推薦、Ebay的購物推薦、MovieLens的電影推薦等。

協(xié)同過濾系統(tǒng)普遍存在3大問題：數(shù)據(jù)稀疏性、冷啟動和可擴展性。為了提高系統(tǒng)的推薦精度，國內(nèi)外學者提出了許多改進的啟發(fā)式推薦算法。Park等[5]通過將協(xié)同過濾與搜索工具相結(jié)合提升了雅虎推薦結(jié)果的準確度；Koren等[6]提出了基于矩陣分解技術(shù)的推薦算法，可以有效提高推薦質(zhì)量；Sandvig等[7]將數(shù)據(jù)挖掘技術(shù)與協(xié)同過濾算法相結(jié)合，提出一種基于關(guān)聯(lián)規(guī)則挖掘的協(xié)同過濾算法，以降低推薦精度為代價獲得了較強的魯棒性。隨著大數(shù)據(jù)時代的到來，協(xié)同過濾系統(tǒng)所需處理的數(shù)據(jù)急劇增多，可擴展性已成了限制協(xié)同過濾系統(tǒng)發(fā)展的主要因素，本文提出的基于多級圖劃分的協(xié)同過濾推薦算法可以有效解決系統(tǒng)的可擴展性問題，并減少系統(tǒng)的運行時間，能滿足對實時性要求較高的系統(tǒng)的需求。

1協(xié)同過濾推薦算法

協(xié)同過濾的基本假設是如果用戶x和y對n個產(chǎn)品的評價或行為是相似的，那么他們對其他產(chǎn)品所持有的觀點很可能也是相似的。其具體說明如下：假設有用戶集合U={u1,u2,…,un}，產(chǎn)品集合C={c1,c2,…,cm}，ru,c表示用戶u對項目c的評分，由ru,c構(gòu)成的矩陣表示用戶對應產(chǎn)品的行為數(shù)據(jù)，稱為用戶-產(chǎn)品(user-item)矩陣[8-9]。算法首先根據(jù)用戶以往的打分記錄計算用戶之間的相似度進而得出該用戶的鄰居用戶。常用的相似度計算方法有Pearson相關(guān)和矢量余弦。

Cx和Cy分別為用戶x和用戶y評價過的項目集，Cxy=Cx∩Cy，表示用戶x和用戶y共同評分過的項目的集合，則用戶x和用戶y之間的相似度計算方法如下[10]：

1)Pearson相關(guān)。

(1)

2)矢量余弦。

(2)

相似度計算完成后，系統(tǒng)進行預測，計算完成的相似度一般作為權(quán)重使用，常用的計算方法有以下兩種[11-13]：

1)簡單加權(quán)平均。

(3)

2)改進的加權(quán)平均——評分差加權(quán)平均。

(4)

(5)

式中：Cu={c∈C|ru,c≠0}。在實際應用中，為了減少系統(tǒng)的計算量,通常選取相似度排名前k的用戶作為鄰居用戶進行計算，其中k稱為活動用戶的鄰居規(guī)模。

2基于多級圖劃分的協(xié)同過濾算法

現(xiàn)有的面向聚類的推薦算法一般都是根據(jù)產(chǎn)品的描述信息對產(chǎn)品進行分類，如Usenet[14]，它將新聞根據(jù)內(nèi)容分為不同的類別，如對于處于幽默類別中的用戶組只對其推薦處于幽默分類下的新聞。但是在實際應用中，可以用于分類的產(chǎn)品信息往往不容易獲得[15]，并且針對不同的推薦，需要應用不同的基于內(nèi)容的分類算法來對產(chǎn)品進行分類。筆者使用多級圖劃分算法對產(chǎn)品進行聚類，該算法使用產(chǎn)品的相似度矩陣作為聚類依據(jù)，可以很方便地用于各種協(xié)同過濾推薦系統(tǒng)中而不需改變原有算法。

2.1　多級圖劃分算法

對圖的劃分是一個NP完全問題，雖然現(xiàn)有的很多算法都對圖的劃分提出了解決方案，但大多數(shù)算法的時間復雜度都很高，或者劃分較粗糙，多級圖劃分算法在縮短運行時間的基礎上依舊能得到較好的劃分，是現(xiàn)今應用廣泛的圖劃分算法。

多級圖劃分算法在滿足相應目標函數(shù)的基礎上將圖劃分為大致相等的k部分，其基本過程如下(如圖1所示)。首先通過簡化(coarsening)階段，將圖G0的邊和頂點進行合并，依次得到圖G1,G2,…,Gm，其中圖Gm為一個擁有原圖特性的但只有很少的頂點的最簡圖；然后在滿足圖劃分目標函數(shù)的情況下將小圖Gm平均劃分成大致相等的k部分，存儲在Pm中，Pm為存儲各個頂點所屬類別的向量；最后將Pm經(jīng)過投射依次還原成中間劃分Pm-1,Pm-2,…,P0，并且在每一個中間階段根據(jù)目標函數(shù)重新調(diào)整劃分，使其劃分更精確，其中P0為圖G0所對應的原劃分[16-18]。

圖1　多級圖劃分基本原理

用于限制劃分的目標函數(shù)一般為最小化邊割(edge-cut)，其中劃分的邊割為圖中跨越不同分區(qū)的邊的權(quán)值之和。

2.2　算法設計

基于多級圖劃分的協(xié)同過濾算法，首先依據(jù)產(chǎn)品之間的相似性使用多級圖劃分算法對產(chǎn)品進行聚類；然后根據(jù)用戶以往的購買記錄計算出用戶購買最多的產(chǎn)品屬于哪一類別，并在該類別的產(chǎn)品中計算用戶之間的相似性；最后根據(jù)鄰居用戶的購買喜好對該用戶進行推薦(如圖2所示)，其具體流程如下：

圖2　算法設計

第1步，根據(jù)原有數(shù)據(jù)集構(gòu)建產(chǎn)品-用戶矩陣，使用式(6)計算產(chǎn)品的相似度矩陣[4]。

sim(i,j)=

(6)

第2步，將產(chǎn)品的相似度矩陣作為多級圖劃分算法的輸入，即為多級圖劃分算法中的原圖G0(圖的數(shù)學表達形式為矩陣)。

第3步，找到圖G0中的極大匹配(maximal matching)并將匹配中的頂點合并成超頂點(multinode)，得到簡化后的圖G1。其中圖的匹配是任意兩條邊不存在共同頂點的邊的集合。

第4步，重復第3步，使圖經(jīng)過G2,G3,…,Gm-1最終得到最簡圖Gm。

第5步，將最簡圖Gm在滿足最小化邊割的要求下劃分成k部分，劃分的結(jié)果存儲在向量Pm中，Pm為存儲圖中各個頂點所屬類別的向量。

第7步，調(diào)整投射后的劃分Pm-1，移動各個分區(qū)中的頂點使Pm-1滿足最小化邊割的要求。

第8步，重復第6、第7步，經(jīng)過Pm-2,Pm-3,…,P1最終得到存儲原圖G0劃分結(jié)果的向量P0。

第9步，對要做出推薦的用戶u，首先根據(jù)其以往的消費記錄統(tǒng)計出用戶u在各個產(chǎn)品類別中所消費的產(chǎn)品的數(shù)量ni(i∈{1,2,..,k})。

第10步，選取ni排名前2位的產(chǎn)品類別，使用這2個類別的產(chǎn)品構(gòu)造用戶-產(chǎn)品矩陣。

第11步，使用第10步中構(gòu)造的用戶-產(chǎn)品矩陣計算用戶u與其他用戶的相似度。

第12步，選取相似度排名前k位的用戶作為用戶u的鄰居用戶，為每個用戶u未消費而其鄰居用戶已消費的產(chǎn)品使用式(3)計算其預測評分。

第13步，選取預測評分排名前m的產(chǎn)品推薦給用戶u。

3實驗結(jié)果

本實驗采用的數(shù)據(jù)集為movielens網(wǎng)站提供的由943個用戶對1 682部電影的100 000條評分記錄。實驗中使用多級圖劃分算法將產(chǎn)品分為8類，鄰居用戶數(shù)目為20，為每個用戶推薦10個產(chǎn)品，并根據(jù)測試數(shù)據(jù)計算推薦的命中率。在不同大小的測試集上運行的結(jié)果如圖3,4所示。

從圖3、圖4中可以看出，基于產(chǎn)品聚類的協(xié)同過濾推薦算法雖然在命中率上與原有的協(xié)同過濾算法存在輕微差距，而其運行時間比原有的算法少很多，并且隨著測試集的加大，兩者之間命中率的差距在減少，而運行時間的差距在拉大，說明基于產(chǎn)品聚類的協(xié)同過濾推薦算法的穩(wěn)定性較高、系統(tǒng)伸縮性好。

圖3　算法命中率隨測試集大小變化曲線

圖4　算法執(zhí)行時間隨測試集大小變化曲線

4結(jié)束語

本文提出的基于多級圖劃分的協(xié)同過濾推薦算法相對于原有算法，能夠在算法性能上獲得較大的提高，并且只對算法的準確率產(chǎn)生輕微影響，同時算法在穩(wěn)定性上有提升，在實時推薦的系統(tǒng)中具有較好的應用前景。

參考文獻：

[1]許海嶺，吳瀟，李曉東，等．互聯(lián)網(wǎng)推薦系統(tǒng)比較研究[J]．軟件學報，2009，20(2)：350-362.

[2]Ricci F，Rokach L，Shapira B，et al．Recommender Systems Handbook[M]．Berlin：Springer，2011：145-186.

[3]Goldberg D，Nichols D，Oki B，et al．Using collaborative filtering to weave an information tapestry[J]．Communications of the ACM，1992，35(12)：61-70.

[4]Linden G，Smith B，York J．Amazon.com recommendations: Item-to-item collaborative filtering[J]．IEEE Internet Computing，2003，7(1)：76-80.

[5]Park S-T，Pennock D M．Applying collaborative filtering techniques to movie search for better ranking and browsing[C]//Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and DataMining．San Jose，California，United States：ACM，2007：550-559.

[6]Koren Y，Bell R，Volinsky C．Matrix factorization techniques for recommender system[J]．Computer，2009，42(8)：30-37.

[7]Sandvig J，Mobasher B，Burke R．Robustness of collaborative recommendation based on association rule mining[C]//Proc of the 2007 ACM Conf on Recommender Systems．New York：ACM，2007：105-112.

[8]Schafer B，F(xiàn)rankowski D，Herlocker J，et al．Collaborative Filtering Recommender Systems[M]．Heidelberg：Springer Berlin，2007：291-324.

[9]Sarwar B，Karypis G，Konstan J，et al．Item-based collaborative filtering recommendation algorithms[C]//Proceedings of the 10th International World Wide Web Conference．New York：ACM，2001：285-295.

[10] 姚曜，趙洪利，楊海濤，等．協(xié)同過濾技術(shù)研究綜述[J]．裝備指揮技術(shù)學院學報，2011, 22(5)：81-88.

[11] 黃創(chuàng)光，印鑒，汪靜，等．不確定近鄰的協(xié)同過濾推薦算法[J]. 計算機學報，2010，33(8)：1369-1377.

[12] 賈冬艷，張付志．基于雙重鄰居選取策略的協(xié)同過濾推薦算法[J]．計算機研究與發(fā)展，2013，50(5)：1076-1084.

[13] 鄧愛林，朱揚勇，施伯樂，等．基于項目評分預測的協(xié)同過濾推薦算法[J]．軟件學報，2002，14(9)：1621-1628.

[14] Resnick P，Iacovou N，Suchak M，et al．GroupLens：an open architecture for collaborative filtering of netnews[C]//ACM Conference on Computer Supported Cooperative Work．Cambridge：MIT Center for Coordination Science，1994：175-186.

[15] O′ConnerM，HerlockerJ．Clustering items for collaborative filtering[C]//Proceedings of the ACM SIGIR Workshop on Recommender Systems．Berkeley：UC，1999：128.

[16] KarypisG，Kumar V. Multilevel k-way partitioning scheme for irregular graphs[J]. Journal of Parallel and Distributed Computing，1998，48(1)：96-129.

[17] George K，Vipin K.A fast and highly quality multilevel scheme for portioning irregular graphs[J].SIAM Journal on Scientific Computing，1999，20(1)：359-392.

[18] Karypis G，Kumar V．Multilevel k-way hypergraphpartitioning[J]. Vlsi Design，1998，11(3)：285-300.

Research on collaborative filtering algorithm

based on multilevel k-way graph partitioning

LIU Xianhui,XU Mengjin

(College of Electronic and Information Engineering,

Tongji University, Shanghai, 201804, China)

Abstract：To solve the limitations of the collaborative filtering, it proposes collaborative filtering algorithm based on multilevel k-way graph partitioning. This algorithm uses multilevel k-way graph partitioning to cluster items, predictions are then computed independently within each partition. The experiment shows that this algorithm can greatly improve the efficiency of system by slightly decrease the accuracy of prediction.

Key words：collaborative filtering; multilevel k-way partitioning; clustering

作者簡介：柳先輝(1979—)，男，浙江麗水人，同濟大學講師，博士，主要研究方向為數(shù)據(jù)挖掘軟件工程。

基金項目：國家科技支撐計劃項目(2012BAF12B11)

收稿日期：2015-10-21

中圖分類號：TP391.1

文獻標志碼：A

文章編號：2095-509X(2015)12-0014-04

DOI:10.3969/j.issn.2095-509X.2015.12.004