柳先輝，徐夢錦

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

?

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

柳先輝，徐夢錦

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

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

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

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

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

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

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

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

1)Pearson相關(guān)。

(1)

2)矢量余弦。

(2)

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

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

(3)

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

(4)

(5)

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

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

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

2.1　多級圖劃分算法

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

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

圖1　多級圖劃分基本原理

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

2.2　算法設(shè)計(jì)

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

圖2　算法設(shè)計(jì)

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

sim(i,j)=

(6)

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

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

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

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

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

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

第9步，對要做出推薦的用戶u，首先根據(jù)其以往的消費(fèi)記錄統(tǒng)計(jì)出用戶u在各個產(chǎn)品類別中所消費(fèi)的產(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)品矩陣計(jì)算用戶u與其他用戶的相似度。

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

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

3實(shí)驗(yàn)結(jié)果

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

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

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

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

4結(jié)束語

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

參考文獻(xiàn)：

[1]許海嶺，吳瀟，李曉東，等．互聯(lián)網(wǎng)推薦系統(tǒng)比較研究[J]．軟件學(xué)報(bào)，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ù)學(xué)院學(xué)報(bào)，2011, 22(5)：81-88.

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

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

[13] 鄧愛林，朱揚(yáng)勇，施伯樂，等．基于項(xiàng)目評分預(yù)測的協(xié)同過濾推薦算法[J]．軟件學(xué)報(bào)，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—)，男，浙江麗水人，同濟(jì)大學(xué)講師，博士，主要研究方向?yàn)閿?shù)據(jù)挖掘軟件工程。

基金項(xiàng)目：國家科技支撐計(jì)劃項(xiàng)目(2012BAF12B11)

收稿日期：2015-10-21

中圖分類號：TP391.1

文獻(xiàn)標(biāo)志碼：A

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

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