張 瑤，陳維斌，傅順開

(華僑大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，福建 廈門 361000)

每天，人們都要面對(duì)很多的選擇，通常會(huì)以周圍人的意見作出選擇。然而，面對(duì)海量的網(wǎng)絡(luò)資源時(shí)，要從中作出最適合的選擇就變得非常困難。電子商務(wù)系統(tǒng)作為目前典型的成功互聯(lián)網(wǎng)應(yīng)用，提供了更豐富的物品。為幫助大家更快速準(zhǔn)確地定位自己的需求，推薦系統(tǒng)在電子商務(wù)系統(tǒng)中應(yīng)運(yùn)而生,例如知名的亞馬遜等平臺(tái)[1]。

目前，應(yīng)用于推薦系統(tǒng)的算法主要分三類：基于內(nèi)容的過濾推薦算法、協(xié)同過濾推薦算法及混合推薦算法。

基于內(nèi)容的過濾推薦算法[2]是對(duì)用戶的興趣進(jìn)行分析，構(gòu)成用戶配置文件，并將其和文件集中的文件用共同的特征變量表示。最后比較兩者的相似度來(lái)為用戶進(jìn)行推薦。隨后，通過用戶的反饋信息，不斷更新用戶配置文件，以此來(lái)動(dòng)態(tài)地為用戶推薦感興趣的信息[3]。

協(xié)同過濾推薦算法是通過用戶對(duì)項(xiàng)目的評(píng)分?jǐn)?shù)據(jù)，找到與目標(biāo)用戶或項(xiàng)目相似的對(duì)象作為候選推薦。當(dāng)前主要的協(xié)同過濾推薦算法有兩種：基于用戶(user-based)和基于項(xiàng)目(item-based)的協(xié)同過濾推薦算法?；谟脩舻膮f(xié)同過濾推薦算法認(rèn)為,如果用戶對(duì)一些項(xiàng)目的評(píng)分比較相似,那么他們對(duì)其他項(xiàng)目的評(píng)分也比較相似;基于項(xiàng)目的協(xié)同過濾推薦算法認(rèn)為,項(xiàng)目間的評(píng)分具有相似性,可以通過用戶對(duì)目標(biāo)項(xiàng)目的若干相似項(xiàng)目的評(píng)分來(lái)估計(jì)該項(xiàng)目的分值[4-5]。

混合推薦算法[6]是將基于內(nèi)容的過濾和協(xié)同過濾相結(jié)合的方法,既保留了用戶配置文件來(lái)代表用戶的興趣，同時(shí)又根據(jù)該配置文件來(lái)尋找相似的用戶，兩種方法互補(bǔ)完成推薦。

本文主要介紹協(xié)同過濾推薦算法,因?yàn)槟壳八膽?yīng)用最為普遍。

1 協(xié)同過濾推薦技術(shù)

協(xié)同過濾推薦技術(shù)之所以得到廣泛的應(yīng)用，主要得益于它獨(dú)立于被推薦對(duì)象的內(nèi)容，只依靠用戶對(duì)項(xiàng)目的評(píng)分或是喜好就可以為用戶推薦。同時(shí)，還可以幫助用戶發(fā)掘潛在的興趣。這些優(yōu)點(diǎn)使得它幾乎適用于所有領(lǐng)域。

1.1 當(dāng)前的協(xié)同過濾推薦算法

當(dāng)前最常用的協(xié)同過濾推薦算法是基于用戶和基于項(xiàng)目的算法?；谟脩舻膮f(xié)同過濾技術(shù)[7]首先獲取用戶對(duì)于項(xiàng)目的評(píng)分，然后通過用戶間的相似性尋找目標(biāo)用戶的最近鄰居，最后利用預(yù)測(cè)函數(shù)和鄰居用戶的評(píng)分來(lái)完成推薦；基于項(xiàng)目的協(xié)同過濾技術(shù)[5,8]則根據(jù)項(xiàng)目間相似性得到目標(biāo)項(xiàng)目的相似項(xiàng)目集合，然后通過預(yù)測(cè)函數(shù)和相似項(xiàng)目集合來(lái)產(chǎn)生推薦列表。

下文將詳細(xì)地介紹和討論以上兩種算法及其一些改進(jìn)算法。

1.2 基于用戶的協(xié)同過濾推薦算法

基于用戶的協(xié)同過濾算法是早期較傳統(tǒng)的一種自動(dòng)協(xié)同過濾技術(shù)。它主要依靠系統(tǒng)中的用戶評(píng)分矩陣來(lái)計(jì)算用戶間的相似性，再根據(jù)相似性來(lái)計(jì)算目標(biāo)用戶對(duì)于項(xiàng)目的預(yù)測(cè)評(píng)分。

定義 用戶評(píng)分矩陣

一個(gè)m×n的矩陣。m和n分別代表矩陣中的用戶數(shù)和項(xiàng)目數(shù)。矩陣中的元素代表用戶對(duì)項(xiàng)目的評(píng)分或偏好。

1.2.1 相似性計(jì)算方法

協(xié)同過濾推薦算法本質(zhì)上是基于近鄰的搜索算法，其核心是計(jì)算用戶/項(xiàng)目間的相似性。常用的相似性度量方法主要有三種[5,8]：余弦相似性度量方法、皮爾森相關(guān)相似度量方法、修正的余弦相似性度量方法。

余弦相似性度量方法：該方法把用戶對(duì)項(xiàng)目的評(píng)分看作是一個(gè)n維向量，則用戶間的相似性就由兩個(gè)用戶向量間的余弦夾角來(lái)決定。

修正的余弦相似性度量方法：該方法是對(duì)余弦相似性度量方法的改進(jìn)算法。它通過減去用戶對(duì)于項(xiàng)目的平均分來(lái)彌補(bǔ)不同用戶對(duì)項(xiàng)目的評(píng)分尺度不同的問題。

皮爾森相關(guān)相似性度量方法：在該方法中，用戶間的相似性的計(jì)算如下：

其中，Iij表示用戶i和j共同評(píng)分過的項(xiàng)目集合,Ri,c、Rj,c表示用戶 i、j對(duì)于項(xiàng)目 c 的評(píng)分， Ri、Rj表示用戶 i、j對(duì)于所有項(xiàng)目的平均評(píng)分。

1.2.2 評(píng)分預(yù)測(cè)

預(yù)測(cè)評(píng)分可由相似度作為權(quán)重，通過計(jì)算鄰居用戶對(duì)未評(píng)分項(xiàng)目的加權(quán)平均值來(lái)得出。

該方法的不足之處在于:(1)如果用戶評(píng)分的項(xiàng)目較少，推薦效果會(huì)比較差。對(duì)于一個(gè)新加入系統(tǒng)的用戶，這個(gè)方法完全無(wú)法“工作”。(2)為了反應(yīng)用戶最新狀態(tài)，需要在線計(jì)算詳盡用戶，這可能導(dǎo)致在線響應(yīng)速度低下。

1.3 基于項(xiàng)目的協(xié)同過濾推薦算法

基于項(xiàng)目的協(xié)同過濾算法[5]依賴的是項(xiàng)目間的相似性，這對(duì)更新的實(shí)時(shí)性要求較低，因此也是目前應(yīng)用較多的一種算法。該算法與基于用戶的協(xié)同過濾算法在過程上類似，只是在相似度上稍有不同。

在相似性度量方法上，1.2.1中提到的方法仍適用，只是此時(shí)計(jì)算相似度的對(duì)象不同。除此之外，針對(duì)項(xiàng)目間相似性的度量，還可使用條件概率度量方法[9]。之所以可以用它來(lái)計(jì)算相似度是因?yàn)?，如果選擇一個(gè)項(xiàng)目的用戶中也有很多用戶選擇另一個(gè)項(xiàng)目,則兩個(gè)項(xiàng)目相似。

1.4 協(xié)同過濾推薦改進(jìn)算法

1.4.1 基于項(xiàng)目評(píng)分預(yù)測(cè)的協(xié)同過濾推薦算法

[8]提出了一種對(duì)未評(píng)分項(xiàng)目預(yù)測(cè)評(píng)分的改進(jìn)算法。該算法先找出用戶i和j分別評(píng)分的項(xiàng)目集合的并集Iij,然后計(jì)算用戶i和j對(duì)于Iij中各自未評(píng)分項(xiàng)目的評(píng)分，最后利用基于用戶的協(xié)同過濾算法來(lái)計(jì)算用戶i和j的相似度，并產(chǎn)生相應(yīng)的推薦列表。

該算法在一定程度上解決了稀疏性的問題，使得兩個(gè)用戶共同評(píng)分的項(xiàng)目有所增加，同時(shí)在計(jì)算兩個(gè)用戶的相似性時(shí)，也不會(huì)出現(xiàn)用戶未評(píng)分項(xiàng)目為0的狀況，提高了推薦精度。但是，由于采用的是傳統(tǒng)的相似度量方法，算法的冷啟動(dòng)問題仍未得到根本的解決。

1.4.2 基于項(xiàng)目聚類的協(xié)同過濾推薦算法

參考文獻(xiàn)[4]是將項(xiàng)目以K均值方法進(jìn)行聚類，然后計(jì)算目標(biāo)項(xiàng)目與聚類中心的相似性，并選擇相似度大于e的聚類來(lái)作為搜索鄰居的項(xiàng)目空間，最終完成推薦。

該算法選擇若干個(gè)聚類來(lái)搜索項(xiàng)目的鄰居，可以減少搜索空間，提高搜索效率，但相似性閾值e的選取需進(jìn)行權(quán)衡。用戶需要不斷調(diào)整e來(lái)進(jìn)行聚類數(shù)量的控制，以此來(lái)調(diào)整精度。

1.4.3 基于項(xiàng)目類別相似性的協(xié)同過濾推薦算法[10]

參考文獻(xiàn)[10]同時(shí)考慮評(píng)分和類別相似性，并將類別表達(dá)成一顆類別樹(如圖1所示)來(lái)計(jì)算類別相似性，然后通過權(quán)重系數(shù)α將兩者進(jìn)行加權(quán)組合，得出綜合相似性。

該算法計(jì)算的是綜合相似性，從而在一定程度上提高了推薦精度，緩解了稀疏性問題。但它也有一定的缺點(diǎn)：(1)類別標(biāo)示一般需要人工標(biāo)注，工作量太大，并會(huì)造成一定的主觀偏見；(2)權(quán)重系數(shù)的選取一般只能靠經(jīng)驗(yàn)來(lái)定。

1.4.4 其他的改進(jìn)算法

隨著研究的深入，更多的改進(jìn)推薦算法被提出。如參考文獻(xiàn)[11]是在1.4.1中所提到算法的基礎(chǔ)上，通過引入類別相似性來(lái)改進(jìn)；參考文獻(xiàn)[12]是綜合評(píng)分相似度和類別相似度，并引入閾值來(lái)調(diào)整評(píng)分相似性和最近鄰的選?。粎⒖嘉墨I(xiàn)[13]也利用“組合”的思想，但不再是相似度組合，而是將用戶加權(quán)評(píng)分和項(xiàng)目加權(quán)評(píng)分進(jìn)行組合來(lái)達(dá)到與1.4.1中算法一樣的目的。這些算法都改進(jìn)了精度，緩解了稀疏性、冷啟動(dòng)等問題。

2 系統(tǒng)性能的評(píng)測(cè)

對(duì)推薦系統(tǒng)來(lái)說(shuō)，系統(tǒng)的性能直接影響用戶對(duì)系統(tǒng)的使用程度。因?yàn)橥扑]出來(lái)的項(xiàng)目不符合用戶的興趣，用戶對(duì)系統(tǒng)的信任度就會(huì)下降。常用的精度測(cè)評(píng)方法有平均絕對(duì)誤差MAE、規(guī)范化的平均絕對(duì)誤差NMAE方法和召回率—精度等方法。以前大家關(guān)注較多的是精度問題，現(xiàn)在評(píng)測(cè)一個(gè)系統(tǒng)的性能，除了精度之外，新穎性、多樣性、覆蓋率等更多指標(biāo)越來(lái)越受重視[14]。

多樣性可以分為系統(tǒng)用戶間多樣性和用戶內(nèi)多樣性[15]。前者反映了系統(tǒng)為不同用戶推薦不同項(xiàng)目的能力，可以通過計(jì)算用戶對(duì)之間的漢明距離，然后取均值來(lái)得出；后者反映了系統(tǒng)為一個(gè)用戶推薦不同種類項(xiàng)目的能力，可以通過計(jì)算某一用戶推薦列表中的項(xiàng)目間相似度的差距，最后取均值來(lái)得出。

新穎度指系統(tǒng)可以為用戶推薦的非流行項(xiàng)目的能力。較常使用的是計(jì)算一個(gè)用戶推薦列表中商品的平均度[16],商品的平均度越低證明商品的新穎度越高。

覆蓋率可以體現(xiàn)出系統(tǒng)為用戶推薦的項(xiàng)范圍的大小，若覆蓋率太低，推薦范圍太窄，用戶滿意度就可能會(huì)下降。較常用的為推薦覆蓋率[14]，用來(lái)計(jì)算推薦項(xiàng)占全部項(xiàng)的比例。

3 推薦系統(tǒng)面臨的問題

3.1 稀疏性問題

推薦系統(tǒng)中，由于用戶瀏覽的項(xiàng)目有限，導(dǎo)致用戶評(píng)分矩陣非常稀疏，從而使得推薦精度不高。參考文獻(xiàn)[4,8,11]的出發(fā)點(diǎn)都是希望緩和矩陣稀疏性問題。因?yàn)槿绻麅蓚€(gè)用戶沒有共同評(píng)分的項(xiàng)目，那將無(wú)法計(jì)算他們的相似度。同樣的，如果兩個(gè)項(xiàng)目共同評(píng)分的用戶交集為空，則項(xiàng)目之間的相似度也無(wú)法得出。目前解決稀疏性問題效果較好的是奇異值分解（SVD）的技術(shù)[17]。在推薦時(shí)，可以先使用SVD方法計(jì)算出項(xiàng)目評(píng)分，然后再計(jì)算相似度最終得出預(yù)測(cè)。SVD的方法在評(píng)分預(yù)測(cè)上不依賴相似度方法進(jìn)行計(jì)算，并且通過維數(shù)化簡(jiǎn)來(lái)得到密集的矩陣。雖然解決了數(shù)據(jù)稀疏性問題，但是在化簡(jiǎn)過程中丟失掉了一些數(shù)據(jù)信息，精度也會(huì)受到一定的影響。

3.2 冷啟動(dòng)問題

冷啟動(dòng)問題[7,17]分為新項(xiàng)目和新用戶問題。參考文獻(xiàn)[10-13]的出發(fā)點(diǎn)就是為了解決冷啟動(dòng)問題。因?yàn)楫?dāng)一個(gè)系統(tǒng)增加一個(gè)新的項(xiàng)目并且該項(xiàng)目沒有任何用戶對(duì)其進(jìn)行評(píng)分時(shí)，這個(gè)項(xiàng)目就無(wú)法被推薦出去，新項(xiàng)目問題就產(chǎn)生了。新用戶問題的產(chǎn)生是由于系統(tǒng)的用戶增多，當(dāng)用戶沒有對(duì)系統(tǒng)中的項(xiàng)目進(jìn)行評(píng)價(jià)時(shí)，系統(tǒng)無(wú)法分析出用戶的偏好，也就無(wú)法產(chǎn)生推薦。

目前對(duì)于冷啟動(dòng)問題的解決有兩種方法：眾數(shù)法和信息熵法。

一般而言，大部分用戶對(duì)于喜愛和不喜愛的項(xiàng)目評(píng)分較為相似，所以評(píng)分的數(shù)值分布在一定范圍內(nèi)的概率較大。因此可以使用眾數(shù)法來(lái)對(duì)新項(xiàng)目或新用戶對(duì)項(xiàng)目的評(píng)分進(jìn)行預(yù)測(cè)。

對(duì)于冷啟動(dòng)問題也可采用信息熵法來(lái)解決。對(duì)于新項(xiàng)目問題，排序計(jì)算所得的信息熵，選取其中信息熵較大的用戶，通過預(yù)測(cè)這些用戶對(duì)該項(xiàng)目的平均評(píng)分來(lái)作為新項(xiàng)目的預(yù)測(cè)評(píng)分。對(duì)于新用戶問題，排序用戶信息熵值，然后選擇其中較大熵值的用戶來(lái)預(yù)測(cè)新用戶對(duì)某一項(xiàng)目的評(píng)分。

本文介紹了協(xié)同過濾推薦算法的傳統(tǒng)算法和改進(jìn)算法。最后對(duì)于系統(tǒng)的性能評(píng)測(cè)做了詳細(xì)介紹，對(duì)系統(tǒng)常見問題也進(jìn)行了分析研究。

很多研究者提出的改進(jìn)算法都是用來(lái)解決系統(tǒng)的稀疏性和冷啟動(dòng)問題，并且在一定程度上緩解了這些問題?？梢娤∈栊院屠鋯?dòng)問題對(duì)于推薦系統(tǒng)的精度影響尤為重要。另外，一個(gè)系統(tǒng)的推薦性能是否良好，也需要一定的策略來(lái)評(píng)估。這些方面也是繼續(xù)改進(jìn)的研究方向。

參考文獻(xiàn)

[1]LINDEN G,SMITH B，YORK J.Amazon.com recommendations item-to-item collaborative filtering[J].IEEE Computer Society,2003(1-2):76-80.

[2]METEREN R V.M.v.S.using content-based filtering for recommendation[C].In CML/MLNET Workshop on Machine Learning and the New Information Age,Baecelona,2000:47-56.

[3]黃萱菁，夏迎炬,吳立德.基于向量空間模型的文本過濾系統(tǒng)[J].軟件學(xué)報(bào),2003，14(3):435-442.

[4]鄧愛林，左子葉，朱揚(yáng)勇.基于項(xiàng)目聚類的協(xié)同過濾推薦算法[J].小型微型計(jì)算機(jī)系統(tǒng),2004,25(9):1665-1670.

[5]Badrul Sarwar,G.K.,KONSTAN J,et al.Item based collaborative filtering recommendation algorithms[C].Proceedings of the 10th International World Wide Web Conference,2001.

[6]曹毅.基于內(nèi)容和協(xié)同過濾的混合模式推薦技術(shù)研究[D].長(zhǎng)沙：中南大學(xué)，2007.

[7]EKSTRAND M D,RIDEL J T,KONSTAN J A.Collaborative filtering recommender systems[M].Hanover:Now Publishers Inc,2010:81-173.

[8]鄧愛林，朱揚(yáng)勇，施伯樂.基于項(xiàng)目評(píng)分預(yù)測(cè)的協(xié)同過濾推薦算法[J].軟件學(xué)報(bào),2003,14(9):1621-1628.

[9]周軍鋒,湯顯，郭景峰.一種優(yōu)化的協(xié)同過濾推薦算法[J].計(jì)算機(jī)研究與發(fā)展,1994，41(10):1842-1847.

[10]李聰，梁昌勇，董珂.基于項(xiàng)目類別相似性的協(xié)同過濾推薦算法[J].合肥工業(yè)大學(xué)學(xué)報(bào)(自然科學(xué)版),2008，31(3)：360-363.

[11]張忠平，郭獻(xiàn)麗.一種優(yōu)化的基于項(xiàng)目評(píng)分預(yù)測(cè)的協(xié)同過濾推薦算法[J].計(jì)算機(jī)應(yīng)用研究,2008,25(9):2658-2660.

[12]汪靜，印鑒.一種優(yōu)化的Item-based協(xié)同過濾推薦算法[J].小型微型計(jì)算機(jī)系統(tǒng),2010,31(22):2337-2342.

[13]馬麗.基于組合加權(quán)評(píng)分的Item-based協(xié)同過濾推薦系統(tǒng)[J].現(xiàn)代圖書情報(bào)技術(shù),2008(11):60-64.

[14]朱郁筱，呂琳媛.推薦系統(tǒng)評(píng)價(jià)指標(biāo)綜述[J].電子科技大學(xué)學(xué)報(bào),2012,41(2):163-175.

[15]Zhou Tao,Jiang Luoluo,Su Riqi,et al.Effect of initial configuration on network-based recommendation[J].Euro-physics Letters,2008(81):58004-58007.

[16]Zhang Zike,Liu Chuang,Zhang Yicheng,et al.Solving the cold-start problem in recommender systems with social tags[J].Europhysics Letters,2010,92(2):28002-28007.

[17]孫小華.協(xié)同過濾系統(tǒng)的稀疏性與冷啟動(dòng)問題研究[D].杭州：浙江大學(xué)，2005.