張滬寅，段 維，葉 剛

ZHANG Huyin,DUAN Wei,YE Gang

武漢大學(xué) 計算機(jī)學(xué)院，武漢 430072

School of Computer,Wuhan University,Wuhan 430072,China

1 引言

在互聯(lián)網(wǎng)快速發(fā)展的今天，網(wǎng)絡(luò)信息量的大幅增長使得用戶很難從中獲得對自己真正有用的那部分信息，對信息的使用效率反而降低了，出現(xiàn)信息過載。解決信息過載一個非常有效的辦法就是個性化推薦，它根據(jù)用戶的信息需求、興趣等，將用戶感興趣的對象推薦給用戶。個性化推薦系統(tǒng)現(xiàn)已廣泛應(yīng)用于很多領(lǐng)域，比如網(wǎng)絡(luò)新聞、電子商務(wù)等。

推薦系統(tǒng)中最為核心的是推薦算法，協(xié)同過濾[1]又是最被大家熟悉和廣泛使用的推薦算法。協(xié)同過濾主要分為基于內(nèi)存和基于模型兩種[2]，其中基于內(nèi)存的協(xié)同過濾又分為基于用戶的協(xié)同過濾和基于項目的協(xié)同過濾，其基本思想類似于如果用戶身邊的很多朋友都選購某種商品，那么該用戶就會很大概率選擇該商品；或者用戶喜歡某類商品，當(dāng)看到和這類商品相似商品并且其他用戶對此類商品評價很高時，則購買的概率會很大，它依賴于用戶-項目評分矩陣。本文主要研究基于用戶的協(xié)同過濾的優(yōu)化改進(jìn)。

協(xié)同過濾中用戶相似度計算的準(zhǔn)確度非常重要，對推薦結(jié)果的準(zhǔn)確度有決定性的影響?，F(xiàn)有許多相似度計算方法，如余弦相似度（COSine similarity，COS）算法[3]、皮爾遜相關(guān)系數(shù)（PearsonCorrelation Coefficient，PCC）算法[4]等。其中PCC運(yùn)用最為廣泛，此外還有在PCC基礎(chǔ)上進(jìn)行改進(jìn)的WPCC[5]、SPCC[6]以及Jaccard[7]等相似度計算方法，但這些方法都只考慮了用戶間相同項目的評分或用戶間共同評分項目數(shù)，考慮條件較少，如果兩個用戶本身不相似但公共評分項目數(shù)很多，則不能讓相似度隨公共評分項目數(shù)的增加而增加。此外，本文認(rèn)為每個用戶都有自己的評分習(xí)慣，將評分項目數(shù)的多少作為相似度計算的權(quán)重有些不妥。

基于現(xiàn)有相似度計算方法存在的一些缺陷，本文提出基于多分段改進(jìn)PCC的協(xié)同過濾算法，將PCC根據(jù)條件作多級劃分并進(jìn)行計算，將用戶間共同項目數(shù)和相似度閾值作為劃分條件考慮，并以在PCC計算結(jié)果上加上一個正數(shù)值取代在PCC計算結(jié)果上用公共項目數(shù)加權(quán)的做法，最后通過實(shí)驗(yàn)和采用其他相似度方法的協(xié)同過濾進(jìn)行比較，結(jié)果表明基于多分段改進(jìn)PCC的協(xié)同過濾算法在推薦準(zhǔn)確度上有顯著提高。

2 相關(guān)工作

協(xié)同過濾推薦算法一般分為3個步驟，首先根據(jù)用戶-項目評分矩陣計算用戶之間的相似度；然后，從與當(dāng)前用戶相似度最高的用戶中選取一定數(shù)量作為最近鄰居，根據(jù)這些鄰居對某個項目的評分來預(yù)測當(dāng)前用戶對該項目的評分；最后，選取預(yù)測評分最高的若干項作為結(jié)果推薦給當(dāng)前用戶。其中，用戶相似度的計算結(jié)果對推薦結(jié)果有著至關(guān)重要的影響，大量的相似度計算方法也被眾多的研究者提出。

2.1 相似度計算常用方法

常用的相似度計算方法中，PCC運(yùn)用得最為廣泛，主要被用來體現(xiàn)任意兩個變量之間的線性相關(guān)水平，值的變化范圍從－1到1，值越大就代表用戶相似度越高。但PCC考慮條件單一，準(zhǔn)確度有待提高。計算公式如下所示：

其中，Iab代表用戶a和用戶b的公共項目，rat代表用戶a給系統(tǒng)中某個項目t的評分值，rbt代表用戶b給系統(tǒng)中某個項目t的評分值，-ra、-rb分別代表用戶a、b給系統(tǒng)中所有項目評分的平均值。

此外，在PCC的基礎(chǔ)上Jamali等人提出了帶權(quán)重的PCC（WPCC）[5]，如下式所示：

其中T代表用戶公共項目的數(shù)量的閾值。在Herlocker等人的實(shí)驗(yàn)中將T設(shè)置為50。如果用戶公共項目數(shù)量小于50，則相似度計算采用公式中第一行計算，否則采用第二行，即PCC計算相似度。

Koutrika等在2009年提出了基于曲線方程的PCC（SPCC）[6]，公式如下所示：

Jaccard方法[7]也是比較常用的相似度計算方法。Jaccard方法只考慮到了用戶共同評分物品的數(shù)量，沒有考慮用戶評分的數(shù)值，公式如下所示：

還有許多其他的相似度計算方法，比如Cacheda等人[8]于2011年提出基于用戶評分差別的平均平方差（MSD）方法；Shambour等人[9]于2013年提出利用模糊集理論給不同評分賦予不同權(quán)重的方法；劉海峰等人[10]于2014年提出將用戶的全局行為考慮進(jìn)相似度計算當(dāng)中；王偉等人[11]于2015年提出在協(xié)同過濾中用平均信息量來計算相似度的方法。但這些方法要么只考慮了用戶公共評分項目數(shù)，而沒有考慮用戶評分?jǐn)?shù)值；要么對用戶評分進(jìn)行加權(quán)，沒有考慮相似度閾值，精度有待提高。

2.2 預(yù)測評分

預(yù)測評分體現(xiàn)了當(dāng)前用戶對當(dāng)前項目的喜好程度。通常用K近鄰[12]方法來計算預(yù)測評分，即通過用戶相似度的計算選擇與當(dāng)前用戶最相似的K個用戶作為當(dāng)前用戶鄰居進(jìn)行計算，計算公式如下：

Top-N推薦集合是將預(yù)測值集合進(jìn)行降序排列，然后將排序在最前面的N個項目選取出來推薦給目標(biāo)用戶。

3 本文算法

針對PCC算法的不足，許多研究者對它做了改進(jìn)，大多數(shù)改進(jìn)都是通過將用戶間相同項目的評分或用戶間共同評分項目數(shù)考慮進(jìn)去，從而提高推薦結(jié)果的精度來實(shí)現(xiàn)的。有的改進(jìn)方法根據(jù)條件進(jìn)行分段計算，但劃分粒度較粗，考慮不全。本文提出方法是根據(jù)用戶公共項目數(shù)和相似度的不同對PCC進(jìn)行多分段計算。本文認(rèn)同PCC的求值特點(diǎn)，即用戶公共項目的評分越接近，用戶相似度就越高，同時也認(rèn)為用戶的PCC值達(dá)到一定閾值時，公共項目數(shù)越多，則相似度越大，但并不是通過在PCC計算結(jié)果賦上權(quán)重實(shí)現(xiàn)的，而是通過在PCC計算結(jié)果加上一個正數(shù)值實(shí)現(xiàn)。

本文提出的方法是在PCC的基礎(chǔ)上采用分段計算進(jìn)行改進(jìn)的，分段依據(jù)公共項目數(shù)和PCC的計算值兩個條件。相比于WPCC方法，本文采用更細(xì)粒度的劃分，并且增加了一個限制條件，力求結(jié)果更加精確。相似度的結(jié)果主要來自于PCC計算的結(jié)果，如果PCC的結(jié)果沒達(dá)到閾值y，即使公共項目數(shù)足夠多，也不能說明兩個用戶更相似，其相似度即PCC的計算結(jié)果。只有當(dāng)兩個用戶足夠相似時，公共項目數(shù)越多，他們才越相似，其相似度為在PCC計算結(jié)果上加上一個正數(shù)值，以增加他們之間的相似度。公式如下所示：

其中，Ia?Ib表示用戶a和用戶b的公共評分項目數(shù)；n1、n2、n3、n4是正整數(shù)且 n1＞n2＞n3＞n4＞0；x1、x2、x3、x4和y是正實(shí)數(shù)。如果兩對用戶的PCC計算結(jié)果一樣，第一對用戶的公共項目數(shù)比第二對用戶多，那么第一對用戶的相似度顯然應(yīng)該大于第二對用戶的相似度，所以公式中x1＞x2＞x3＞x4＞0。

分段算法的計算步驟如下：如果用戶間的公共項目數(shù)大于等于n1，并且用戶間的PCC相似度值大于等于y，則用戶的相似度為PCC計算的結(jié)果加上x1；如果用戶間的公共項目數(shù)小于n1，大于等于n2，并且用戶間的PCC相似度值大于等于y，則用戶的相似度為PCC計算的結(jié)果加上x2；如果用戶間的公共項目數(shù)小于n2，大于等于n3，并且用戶間的PCC相似度值大于等于y，則用戶的相似度為PCC計算的結(jié)果加上x3；如果用戶間的公共項目數(shù)小于n3，大于等于n4，并且用戶間的PCC相似度值大于等于y，則用戶的相似度為PCC計算的結(jié)果加上x4；否則，用戶相似度值為PCC計算結(jié)果值。算法流程圖如圖1所示。

圖1 基于多分段改進(jìn)PCC算法流程

4 實(shí)驗(yàn)結(jié)果及分析

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

本文實(shí)驗(yàn)采用的數(shù)據(jù)集是來自美國的GroupLens研究小組建立的MovieLens[13]的百萬（MovieLens 1 million）數(shù)據(jù)集。這個MovieLens數(shù)據(jù)集包含了6 040名用戶對3 900部電影的100萬條評分記錄，其中每個用戶都至少給20部電影評過分。由于該數(shù)據(jù)集的信息真實(shí)可靠，而且大部分協(xié)同過濾算法都是在這個數(shù)據(jù)集上進(jìn)行驗(yàn)證的，便于對結(jié)果進(jìn)行比對。

4.2 評估標(biāo)準(zhǔn)

為了衡量協(xié)同過濾推薦算法的準(zhǔn)確度，本文采用MAE（Mean Absolute Error），即平均絕對誤差進(jìn)行誤差計算，用于預(yù)測評分和實(shí)際評分之間的誤差。公式如下：

其中，pi是預(yù)測評分，ri是實(shí)際評分。MAE的值越低預(yù)測效果越好。

本文對比實(shí)驗(yàn)使用Top-N推薦。準(zhǔn)確率和召回率能夠衡量Top-N推薦的質(zhì)量。準(zhǔn)確率表示推薦列表中用戶喜歡的項目和所有被推薦項目的比率，計算方法如下：

召回率表示推薦列表中用戶喜歡的項目與系統(tǒng)中用戶喜歡的所有項目的比率，計算方法如下：

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

分段改進(jìn)的PCC算法中的參數(shù)中，x1、x2、x3、x4是相似度的增值，從大到小依次遞減，兩兩之間差值不能過大或過小，過大則分段計算時不同段之間的差別將非常大，過小則對相似度影響很小，本文將x1、x2、x3、x4依次設(shè)置為0.5、0.375、0.25、0.125。參數(shù) y 是PCC的閾值，表示兩個用戶足夠相似和不相似的臨界點(diǎn)，值較大或太小對分段計算的效果都不好，本文將y值設(shè)為0.3。參數(shù)n1、n2、n3、n4代表用戶間的公共項目數(shù)的閾值，當(dāng)用戶間公共項目數(shù)足夠多，大于等于n1時，用戶間相似度用PCC計算準(zhǔn)確度較高，相似度的增值將保持不變；當(dāng)用戶間公共項目數(shù)很少，小于n4時，用戶間相似度用PCC計算準(zhǔn)確度較低，相似度不賦予增值；參考WPCC中Herlocker在實(shí)驗(yàn)中把代表用戶間公共項目數(shù)足夠多的參數(shù)T設(shè)置為50，本文將n1設(shè)置為50，n2、n3、n4的值依次設(shè)置為25、10、5。對比的方法分別是PCC、WPCC和SPCC。實(shí)驗(yàn)結(jié)果如圖2至圖6所示。

圖2展示的是MAE的結(jié)果，k代表用戶的最近鄰居數(shù)，分別取了10、20、30、40、50、60、70、80等8組數(shù)進(jìn)行實(shí)驗(yàn)。橫軸是k的取值，縱軸是MAE值?？梢钥闯鲭S著最近鄰居數(shù)的增大，所有方法的MAE值逐漸降低，效果變好。而本文的方法MAE值指標(biāo)明顯優(yōu)于其他三種方法。

圖2 k取不同值時的MAE值

圖3至圖6展示的是準(zhǔn)確率和召回率的結(jié)果，k代表用戶的最近鄰居數(shù)，r代表向用戶推薦的項目數(shù)。圖3表示鄰居數(shù)為5，推薦5個項目時四種方法準(zhǔn)確率的值，圖4表示鄰居數(shù)為10，推薦10個項目時四種方法準(zhǔn)確率的值，圖5表示鄰居數(shù)為5，推薦5個項目時四種方法召回率的值，圖6表示鄰居數(shù)為10，推薦10個項目時四種方法召回率的值。可以看出，隨著鄰居數(shù)和推薦數(shù)的增大，推薦的質(zhì)量也變得更好，而本文方法的推薦質(zhì)量無論在準(zhǔn)確率還是召回率都明顯優(yōu)于其他三種方法。

圖3 k=5,r=5時準(zhǔn)確率的對比

圖4 k=10,r=10時準(zhǔn)確率的對比

圖5 k=5,r=5時召回率的對比

圖6 k=10,r=10時召回率的對比

5 結(jié)束語

盡管協(xié)同過濾推薦算法在推薦系統(tǒng)中使用非常廣泛，也是比較成熟的推薦算法，但其推薦精度仍有提高的空間。傳統(tǒng)基于PCC或改進(jìn)PCC的協(xié)同過濾大多是通過用戶公共項目評分差，增加權(quán)值或參數(shù)進(jìn)行改進(jìn)，考慮不夠全面。本文提出的采用多分段改進(jìn)PCC方法根據(jù)不同的情況采取不同的計算方式，并在PCC結(jié)果加上一個不同的值，提高了協(xié)同過濾的推薦精度。

本文的工作是分段對PCC計算結(jié)果加上一個值，未來的工作將研究在某種特定情況下對PCC計算的結(jié)果減去一個值。分段的數(shù)量以及分段的條件也可能根據(jù)數(shù)據(jù)集的不同而動態(tài)調(diào)整。另外，噪聲用戶的檢測和刪除也非常重要，在推薦系統(tǒng)中，尤其是電子商務(wù)的系統(tǒng)過濾系統(tǒng)中，很多用戶都是隨意評分，并沒有根據(jù)自己的實(shí)際情況評分，這種用戶對推薦的精度產(chǎn)生了非常負(fù)面的影響，應(yīng)該提前鑒別并剔除。

參考文獻(xiàn)：

[1]Yang X，Guo Y，Liu Y，et al.A survey of collaborative filtering based social recommender systems[J].Computer Communications，2014，41（5）：1-10.

[2]Cacheda F，Carneiro V，F(xiàn)ernndez D，et al.Comparison of collaborative filtering algorithms：Limitations of current techniques and proposals for scalable，high-performance recommender systems[J].ACM Transactions on the Web，2011，5（1）：1-33.

[3]Adomavicius G，Tuzhilin A.Toward the next generation of recommender systems：A survey of the state-of-the-art and possible extensions[J].IEEE Transactions on Knowledge and Data Engineering，2005，17（6）：734-749.

[4]Resnick P，Iacovou N，Suchak M，et al.Group lens：An openarchitecture for collaborative filtering of netnews[C]//Proceedings of the ACM Conference on Computer Supported Cooperative Work（CSCW）.New York：ACM，1994：175-186.

[5]Jamali M，Ester M.Trust walker：A random walk model for combining trust-based and item-based recommendation[C]//Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining（KDD）.New York：ACM，2009：397-406.

[6]Koutrika G，Bercovitz B，Garcia-molina H.FlexRecs：Expressing and combining flexible recommendations[C]//Proceedings of the 2009 ACM SIGMOD International Conference on Management of Data.New York：ACM，2009：745-758.

[7]Herlocker J L，Konstan J A，Borchers A，et al.An algorithmic framework for performing collaborative filtering[C]//Proceedings of the Twenty Second Annual International ACM SIGIR Conference on Research and Development in Information Retrieval，1999：230-237.

[8]Cacheda F，Carneiro V，F(xiàn)ernández D，et al.Comparison of collaborative filtering algorithms：Limitations of current techniques and proposals for scalable，high-performance recommender systems[J].ACM Transactions on the Web（TWEB），2011，5（1）：1-33.

[9]Lu J，Shambour Q，Xu Y，et al.A web-based personalized business partner recommendation system using fuzzy semantictechniques[J].Computational Intelligence，2013，29（1）：37-69.

[10]Liu H，Hu Z，Mian A，et al.A new user similarity model to improve the accuracy of collaborative filtering[J].Knowledge-Based Systems，2014，56：156-166.

[11]Wang W，Zhang G，Lu J.Collaborative filtering with entropy-driven user similarity in recommender systems[J].International Journal of Intelligent Systems，2015，30（8）：854-870.

[12]羅辛，歐陽元新，熊璋，等.通過相似度支持度優(yōu)化基于K近鄰的協(xié)同過濾算法[J].計算機(jī)學(xué)報，2010，33（8）：1437-1445.

[13]Miller B N，Albert I，Lam S K，et al.MovieLens unplugged：Experience with an occasionally connected recommender system[C]//Proceedings of the 8th Interntional Conference on Intelligent User Interfaces，New York，2003：263-266.