基于共同評(píng)分項(xiàng)和權(quán)重計(jì)算的推薦算法研究

謝人強(qiáng)，陳 震

(福州外語(yǔ)外貿(mào)學(xué)院信息系，福建福州 350202)

基于共同評(píng)分項(xiàng)和權(quán)重計(jì)算的推薦算法研究

謝人強(qiáng)，陳 震

(福州外語(yǔ)外貿(mào)學(xué)院信息系，福建福州 350202)

產(chǎn)生推薦列表是基于用戶(hù)的協(xié)同過(guò)濾推薦算法的重要步驟，也是最終的結(jié)果。針對(duì)在基于用戶(hù)的協(xié)同過(guò)濾推薦算法中，“產(chǎn)生推薦列表”環(huán)節(jié)的研究相對(duì)較少的這一現(xiàn)象，為了改進(jìn)推薦算法的性能，通過(guò)權(quán)重計(jì)算和共同評(píng)分項(xiàng)方法來(lái)選定推薦項(xiàng)目，即首先將項(xiàng)目按照評(píng)分的近鄰用戶(hù)數(shù)量的多少進(jìn)行排序，然后對(duì)排序的項(xiàng)目進(jìn)行綜合權(quán)重計(jì)算，將其結(jié)果由高到低進(jìn)行再次排序，從而產(chǎn)生推薦列表。該算法經(jīng)MovieLens數(shù)據(jù)集測(cè)試，在測(cè)試中使用“平均絕對(duì)誤差”作為實(shí)驗(yàn)測(cè)評(píng)指標(biāo)，結(jié)果表明，在目標(biāo)用戶(hù)的相似用戶(hù)數(shù)為60時(shí)，該算法相較于不考慮共同評(píng)分項(xiàng)或綜合權(quán)重計(jì)算因素的算法，有著更低的平均絕對(duì)誤差，其值為0.77。該算法能夠在一定程度上提高推薦系統(tǒng)的準(zhǔn)確度。

協(xié)同過(guò)濾算法;評(píng)分項(xiàng);綜合權(quán)重;準(zhǔn)確度

1 概述

隨著互聯(lián)網(wǎng)信息技術(shù)的快速發(fā)展，以及網(wǎng)民數(shù)量的持續(xù)增加，使得互聯(lián)網(wǎng)的信息呈現(xiàn)爆炸式增長(zhǎng)態(tài)勢(shì)，用戶(hù)正面臨著越來(lái)越嚴(yán)重的“信息過(guò)載”問(wèn)題。目前，解決“信息過(guò)載”問(wèn)題的方法主要有兩種:一是信息檢索技術(shù)，該類(lèi)技術(shù)以搜索引擎為代表;二是信息過(guò)濾技術(shù)，該類(lèi)技術(shù)以推薦系統(tǒng)為代表。兩類(lèi)技術(shù)各有優(yōu)缺點(diǎn)，但當(dāng)用戶(hù)的需求不明確時(shí)，推薦系統(tǒng)能表現(xiàn)出更強(qiáng)的優(yōu)勢(shì)。在眾多推薦系統(tǒng)算法中，協(xié)同過(guò)濾技術(shù)應(yīng)用最為廣泛，且效果最好。所謂的協(xié)同過(guò)濾算法是通過(guò)分析、查找與目標(biāo)用戶(hù)相似的近鄰用戶(hù)或項(xiàng)目，根據(jù)近鄰用戶(hù)或項(xiàng)目的情況，為目標(biāo)用戶(hù)進(jìn)行個(gè)性化推薦［1］。

現(xiàn)有的協(xié)同過(guò)濾推薦算法主要分為基于模型與基于內(nèi)存兩類(lèi)。基于模型的推薦算法是建立評(píng)分模型進(jìn)行推薦，具體算法包括:基于聚類(lèi)的算法、基于分類(lèi)的算法、基于關(guān)聯(lián)規(guī)則的算法等［2］?；趦?nèi)存的推薦算法包含基于用戶(hù)的推薦算法和基于項(xiàng)目的推薦算法，文中以基于用戶(hù)的推薦算法為例。

基于用戶(hù)的協(xié)同過(guò)濾算法，大致包含以下幾個(gè)步驟:

(1)建立用戶(hù)-項(xiàng)目評(píng)分矩陣;

(2)計(jì)算用戶(hù)相似度;

(3)選擇k近鄰;

(4)產(chǎn)生推薦列表［3］。

其中，常見(jiàn)的計(jì)算用戶(hù)間相似度的算法有余弦相似性、修正的余弦相似性、相關(guān)相似性等［4］;選擇K近鄰主要有閾值法和Top-N法。

近些年，協(xié)同過(guò)濾算法得到了廣泛研究，眾多的模型與算法被提出。文中在此基礎(chǔ)上，充分考慮共同對(duì)項(xiàng)目評(píng)分的近鄰用戶(hù)數(shù)量、項(xiàng)目的權(quán)重計(jì)算方法兩個(gè)影響因素，提出協(xié)同過(guò)濾的改進(jìn)算法，并通過(guò)實(shí)驗(yàn)驗(yàn)證算法的性能。

2 基于用戶(hù)的協(xié)同過(guò)濾推薦算法的相關(guān)研究

為了提高推薦算法的性能，許多學(xué)者對(duì)該領(lǐng)域進(jìn)行了深入研究。例如，Reinders等充分利用用戶(hù)-項(xiàng)目評(píng)分矩陣信息，結(jié)合用戶(hù)相似性和項(xiàng)目相似性，使用了近鄰用戶(hù)對(duì)近鄰項(xiàng)目的評(píng)分信息［5］。George等提出歸一化評(píng)分項(xiàng)目的方法，將每個(gè)評(píng)分項(xiàng)目都添加一個(gè)歸一化因子，從而降低活躍用戶(hù)評(píng)價(jià)過(guò)的項(xiàng)目的重要性［6］。David等提出以概率模式為基礎(chǔ)的相似性計(jì)算方法［7］。Herlocker等提出了項(xiàng)目-評(píng)分矩陣中的評(píng)分信息的改進(jìn)方式，對(duì)那些與目標(biāo)用戶(hù)相似的近鄰用戶(hù)，如果沒(méi)有對(duì)目標(biāo)項(xiàng)目進(jìn)行評(píng)分，可以使用近鄰用戶(hù)的平均評(píng)分來(lái)參與相似度計(jì)算［8］。Xue G R等提出利用目標(biāo)用戶(hù)的近鄰用戶(hù)集的平均分值作為近鄰用戶(hù)缺失的評(píng)分信息［9］。Larson等提出了“細(xì)粒度”的計(jì)算方法［10］。Zhao S等提出了整合與充分利用近鄰用戶(hù)和相似項(xiàng)目的信息來(lái)提高精度［11］。另外，李紅梅等利用精確歐氏局部敏感哈希算法對(duì)用戶(hù)評(píng)分?jǐn)?shù)據(jù)進(jìn)行降維處理，然后構(gòu)建索引，從而快速獲取目標(biāo)用戶(hù)的近鄰用戶(hù)［12］。汪靜等提出基于共同評(píng)分和相似性權(quán)重的協(xié)同過(guò)濾推薦算法，使用共同評(píng)分?jǐn)?shù)據(jù)計(jì)算用戶(hù)的相似性，選擇被共同評(píng)分的數(shù)據(jù)計(jì)算項(xiàng)目的相似性，再結(jié)合相似性權(quán)重得出預(yù)測(cè)結(jié)果，該算法有效提高了推薦的準(zhǔn)確度［13］。

綜上所述，協(xié)同過(guò)濾推薦算法的改進(jìn)方法眾多，許多學(xué)者對(duì)改進(jìn)推薦系統(tǒng)的性能做出了重大貢獻(xiàn)，但總體而言，在基于用戶(hù)的協(xié)同過(guò)濾推薦算法的各步驟中，“用戶(hù)相似度計(jì)算”環(huán)節(jié)的改進(jìn)研究較多，而“產(chǎn)生推薦列表”環(huán)節(jié)的研究相對(duì)較少。文中將著眼于“產(chǎn)生推薦列表”環(huán)節(jié)，提出基于共同評(píng)分項(xiàng)和綜合權(quán)重計(jì)算的協(xié)同過(guò)濾推薦算法。

3 基于共同評(píng)分項(xiàng)和綜合權(quán)重計(jì)算的協(xié)同過(guò)濾推薦算法

3.1 算法說(shuō)明

設(shè)計(jì)的算法包括以下幾個(gè)步驟，例如要給目標(biāo)用戶(hù)u推薦K個(gè)項(xiàng)目。

(1)使用Pearson相關(guān)相似性算法計(jì)算u與其他所有用戶(hù)的相似度，并將相似度的值從高到低進(jìn)行排列。Pearson相關(guān)相似性算法如式(1)所示［14-15］:

其中，Ric表示用戶(hù)i對(duì)項(xiàng)目c的評(píng)分;Ri表示用戶(hù)i的平均評(píng)分;表示用戶(hù)j的平均評(píng)分;Rij表示用戶(hù)i和用戶(hù)j共同評(píng)分的項(xiàng)目集合。

(2)選取相似度最高的前N個(gè)用戶(hù)數(shù)據(jù)放入集合A中。

(3)將項(xiàng)目按集合A中用戶(hù)的共同評(píng)分?jǐn)?shù)量的多少進(jìn)行排序，用戶(hù)共同評(píng)分多的項(xiàng)目排在前，共同評(píng)分少的項(xiàng)目排在后，排序后項(xiàng)目集合為B。

(4)利用用戶(hù)間相似性的程度，計(jì)算集合B中各項(xiàng)目的權(quán)重，例如項(xiàng)目c的權(quán)重計(jì)算如下:

其中，TWeight(c) 為 項(xiàng) 目 c的 總 權(quán) 重; Sumsim(c)為對(duì)項(xiàng)目c進(jìn)行評(píng)價(jià)的，與目標(biāo)用戶(hù)u相似的所有用戶(hù)的相似值之和;Weight(c)為項(xiàng)目c的權(quán)重值;Ic為對(duì)項(xiàng)目c進(jìn)行評(píng)價(jià)的用戶(hù)集合;j為Ic中的某個(gè)用戶(hù);sim(u，j)表示目標(biāo)用戶(hù)u與用戶(hù)j的相似值。

(5)將各項(xiàng)目的權(quán)重，按從大到小進(jìn)行排序。

(6)選擇權(quán)重最大的前K個(gè)項(xiàng)目推薦給用戶(hù)。

3.2 算法分析

該算法具有較強(qiáng)的實(shí)用性，同時(shí)也具有一定的優(yōu)越性，具體表現(xiàn)在:

(1)步驟1和步驟2保證了參與計(jì)算的用戶(hù)都與目標(biāo)用戶(hù)有較高的相似度，從而保證了它們之間的相關(guān)性，因此獲得的推薦信息將會(huì)更準(zhǔn)確。

(2)通過(guò)步驟3，可以在一定程度上保證權(quán)重高的項(xiàng)目?jī)?yōu)先被推薦。因?yàn)楣餐u(píng)分多的項(xiàng)目，往往是因?yàn)橄嗨朴脩?hù)對(duì)該項(xiàng)目的興趣程度高。

(3)通過(guò)步驟4準(zhǔn)確計(jì)算步驟3得出的各項(xiàng)目的權(quán)重，然后將前K個(gè)項(xiàng)目進(jìn)行推薦，保證了推薦算法的準(zhǔn)確性。

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

根據(jù)前文的分析，基于雙重選擇的協(xié)同過(guò)濾推薦算法設(shè)計(jì)如圖1所示。

4 實(shí)驗(yàn)分析

4.1 實(shí)驗(yàn)數(shù)據(jù)與測(cè)評(píng)指標(biāo)

實(shí)驗(yàn)數(shù)據(jù)來(lái)源于GroupLens提供的MovieLens數(shù)據(jù)集，該數(shù)據(jù)集是一個(gè)評(píng)分?jǐn)?shù)據(jù)集，是用戶(hù)對(duì)自己看過(guò)的電影進(jìn)行評(píng)分，分值為1～5，不同的評(píng)分分值表達(dá)了用戶(hù)對(duì)某影片的不同喜好程度。MovieLens數(shù)據(jù)集包括三個(gè)大小不同的庫(kù)，評(píng)分?jǐn)?shù)據(jù)分別為10萬(wàn)條、1百萬(wàn)條、1千萬(wàn)條。為了計(jì)算方便，文中選取小規(guī)模的數(shù)據(jù)集，它包含943個(gè)用戶(hù)對(duì)1 682部電影的10萬(wàn)條評(píng)分?jǐn)?shù)據(jù)。

在實(shí)驗(yàn)過(guò)程中，將數(shù)據(jù)集按照8∶2的比例劃分為訓(xùn)練集和測(cè)試集，在訓(xùn)練集上按3.1節(jié)的算法建立相應(yīng)的模型，在測(cè)試集上對(duì)目標(biāo)用戶(hù)行為進(jìn)行預(yù)測(cè)。實(shí)驗(yàn)測(cè)評(píng)指標(biāo)使用平均絕對(duì)誤差(Mean Absolute Error，MAE)，它是一種統(tǒng)計(jì)度量方法。MAE通過(guò)計(jì)算目標(biāo)用戶(hù)在訓(xùn)練集上的評(píng)分與測(cè)試集上的評(píng)分之間的差值來(lái)度量算法及預(yù)測(cè)準(zhǔn)確性，見(jiàn)式(5)。

其中，n為評(píng)分總數(shù);ric為用戶(hù)i對(duì)項(xiàng)目c的實(shí)際評(píng)分;r^ic為用戶(hù)i對(duì)項(xiàng)目c的預(yù)測(cè)評(píng)分;MAE數(shù)值與推薦的預(yù)測(cè)準(zhǔn)確性呈反比，MAE越小，推薦效果越好。

為了比較文中所描述算法的性能，引入另外兩種算法進(jìn)行比較，分別命名為UBCF-1、UBCF-2，文中算法命名為UBCF-3。三種算法的具體計(jì)算思路如表1所示。

由表1可以看出，相比于UBCF-1，UBCF-2改進(jìn)了項(xiàng)目權(quán)重的計(jì)算方法，UBCF-3相比UBCF-2，考慮了共同評(píng)分項(xiàng)的因素。

4.2 測(cè)評(píng)結(jié)果

對(duì)MovieLens數(shù)據(jù)集進(jìn)行測(cè)評(píng)，當(dāng)使用UBCF-1時(shí)，與目標(biāo)用戶(hù)的相似用戶(hù)數(shù)選取值N發(fā)生變化時(shí)，得到如圖2所示的MAE變化圖。

UBCF-2使用了文中介紹的權(quán)重計(jì)算公式(見(jiàn)式(2)～(4))，通過(guò)程序運(yùn)行，得出了如圖3所示的MAE變化圖。

從圖3可以看出，UBCF-2中MAE數(shù)值有了大幅降低，即推薦系統(tǒng)的準(zhǔn)確率得到了大幅提高。在UBCF-2的基礎(chǔ)上，UBCF-3考慮了項(xiàng)目共同評(píng)分的數(shù)量，該算法MAE變化圖如圖4所示。

從圖4可以看出，UBCF-3的總體性能相對(duì)于UBCF-2又有了一定程度的提升，當(dāng)N=60，即目標(biāo)用戶(hù)的相似用戶(hù)數(shù)為60時(shí)，UBCF-3算法的MAE值最小。通過(guò)圖5，可以顯而易見(jiàn)地得到UBCF-3相對(duì)UBCF-1、UBCF-2有著更好的性能。

圖4 UBCF-3的MAE變化圖

UBCF-3算法給目標(biāo)用戶(hù)推薦的項(xiàng)目數(shù)不同，MAE值也會(huì)產(chǎn)生相應(yīng)的變化，如圖6所示。

5 結(jié)束語(yǔ)

文中提出了一種基于共同評(píng)分項(xiàng)和綜合權(quán)重計(jì)算的協(xié)同過(guò)濾推薦算法?？紤]了共同評(píng)分用戶(hù)數(shù)對(duì)產(chǎn)生最終推薦列表的影響，一般情況下，共同評(píng)分越多的項(xiàng)目，往往是因?yàn)橄嗨朴脩?hù)對(duì)該項(xiàng)目的興趣程度越高，因而對(duì)它進(jìn)行推薦，準(zhǔn)確度就越高;也考慮了綜合權(quán)重計(jì)算對(duì)推薦列表產(chǎn)生的影響，并提出了綜合權(quán)重的計(jì)算公式。在MovieLens數(shù)據(jù)集上的測(cè)試結(jié)果表明，基于共同評(píng)分項(xiàng)和綜合權(quán)重計(jì)算的協(xié)同過(guò)濾推薦算法能夠提高推薦系統(tǒng)的準(zhǔn)確度，獲得更好的推薦質(zhì)量。

［1］ 朱麗中，徐秀娟，劉 宇.基于項(xiàng)目和信任的協(xié)同過(guò)濾推薦算法［J］.計(jì)算機(jī)工程，2013，39(1):58-62.

［2］ 劉宇軒.混合協(xié)同過(guò)濾算法研究［D］.北京:北京郵電大學(xué)，2013.

［3］ 碩良勛，柴變芳，張新東.基于改進(jìn)最近鄰的協(xié)同過(guò)濾推薦算法［J］.計(jì)算機(jī)工程與應(yīng)用，2015，51(5):137-141.

［4］ 馬宏偉，張光衛(wèi)，李 鵬.協(xié)同過(guò)濾推薦算法綜述［J］.小型微型計(jì)算機(jī)系統(tǒng)，2009(7):1282-1288.

［5］ Wang Jun，Vries A P，Reinders M J T.Unifying user-based and item-based collaborative filtering approaches by similarity fusion［C］//Proceedings of ACM SIGIR’06.［s.l.］:ACM，2006:501-508.

［6］ Karypis G.Evaluation of item-based Top-N recommendation algorithms［C］//Proceedings of the tenth international conference on information and knowledge management.［s.l.］:［s. n.］，2001:247-254.

［7］ Kits B，F(xiàn)reed D，Vrieze M.Cross-sell:a fast promotion-tunable customer-item recommendation method based on conditionally independent probabilities［C］//Proceeding of the sixth ACM SIGKDD international conference on knowledge discovery data mining.［s.l.］:ACM，2000:437-446.

［8］ Herlocker J L，Konstan J A，Borchers A，et al.An algorithmic framework for performing collaborative filtering［C］//Proceedings of ACM IGIR’99.［s.l.］:ACM Press，1999:230-237.

［9］ Xue G R，Lin C，Yang Q，et al.Scalable collaborative filtering using cluster-based smoothing［C］//Proceedings of SIGIR. ［s.l.］:［s.n.］，2005.

［10］ Shi Yue，Larson M，Hanjalic A.Exploiting user similarity based on rated-item pools for improved user-based collaborative filtering［C］//Proceedings of the third ACM conference on recommender systems.［s.l.］:ACM，2009:125-132.

［11］Ding S，Zhao S，Yuan Q，et al.Boosting collaborative filtering based on statistical prediction errors［C］//Procedding of ACM conference on recommender systems.［s.l.］:ACM，2008:3-10.

［12］李紅梅，郝文寧，陳 剛.基于精確歐氏局部敏感哈希的協(xié)同過(guò)濾推薦算法［J］.計(jì)算機(jī)應(yīng)用，2014，34(12):3481-3486.

［13］汪 靜，印 鑒，鄭利榮，等.基于共同評(píng)分和相似性權(quán)重的協(xié)同過(guò)濾推薦算法［J］.計(jì)算機(jī)科學(xué)，2010，37(2):99-104.

［14］孫遠(yuǎn)帥，陳 垚，劉向榮，等.基于項(xiàng)目層次相似性的推薦算法［J］.山東大學(xué)學(xué)報(bào):工學(xué)版，2014，44(3):8-14.

［15］胡 勛，孟祥武，張玉潔，等.一種融合項(xiàng)目特征和移動(dòng)用戶(hù)信任關(guān)系的推薦算法［J］.軟件學(xué)報(bào)，2014，25(8):1817-1830.

Research on Recommendation Algorithm Based on Co-rating and Weight Calculation

XIE Ren-qiang，CHEN Zhen
(Department of Information Technology，F(xiàn)uzhou University of International Studies and Trade，F(xiàn)uzhou 350202，China)

The recommended list is an important step of the user-based collaborative filtering recommendation algorithm and is also the final result.According to the phenomenon of less research on the“generation of recommendation list”in collaborative filtering recommendation algorithm based on user，in order to improve the performance of it，the recommended items are selected by weight calculation and the method of co-rating number.Firstly the co-rating items is sorted by the number of nearest neighbor.Then，the ranking items are calculated by comprehensive weight，and the results are sorted by high to low，and the recommended list is generated.The algorithm is tested by MovieLens data set.It uses the“Mean Absolute Error”as the evaluation index in the test.The results show that when the target user’s similar user number is 60，the algorithm has a lower mean absolute error compare with those calculation algorithms which don’t consider the factors of common rating items or comprehensive weight，and the value is 0.77.The algorithm can improve the accuracy of the recommendation system to a certain extent.

collaborative filtering algorithm;co-rating;comprehensive weight;accuracy

TP391

A

1673-629X(2016)09-0069-04

10.3969/j.issn.1673-629X.2016.09.016

2015-08-12

2015-12-10< class="emphasis_bold">網(wǎng)絡(luò)出版時(shí)間:

時(shí)間:2016-08-23

2014年福建省教育科技計(jì)劃項(xiàng)目(JB14129)

謝人強(qiáng)(1982-)，男，副教授，研究生，研究方向?yàn)殡娮由虅?wù)、信息管理與信息系統(tǒng)。

http://www.cnki.net/kcms/detail/61.1450.TP.20160823.1343.026.html