基于多分段改進PCC的協(xié)同過濾算法

張滬寅，段 維，葉 剛

ZHANG Huyin,DUAN Wei,YE Gang

武漢大學 計算機學院，武漢 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é)同過濾，其基本思想類似于如果用戶身邊的很多朋友都選購某種商品，那么該用戶就會很大概率選擇該商品；或者用戶喜歡某類商品，當看到和這類商品相似商品并且其他用戶對此類商品評價很高時，則購買的概率會很大，它依賴于用戶-項目評分矩陣。本文主要研究基于用戶的協(xié)同過濾的優(yōu)化改進。

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

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

2 相關(guān)工作

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

2.1 相似度計算常用方法

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

其中，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等人的實驗中將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年提出將用戶的全局行為考慮進相似度計算當中；王偉等人[11]于2015年提出在協(xié)同過濾中用平均信息量來計算相似度的方法。但這些方法要么只考慮了用戶公共評分項目數(shù)，而沒有考慮用戶評分數(shù)值；要么對用戶評分進行加權(quán)，沒有考慮相似度閾值，精度有待提高。

2.2 預(yù)測評分

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

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

3 本文算法

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

本文提出的方法是在PCC的基礎(chǔ)上采用分段計算進行改進的，分段依據(jù)公共項目數(shù)和PCC的計算值兩個條件。相比于WPCC方法，本文采用更細粒度的劃分，并且增加了一個限制條件，力求結(jié)果更加精確。相似度的結(jié)果主要來自于PCC計算的結(jié)果，如果PCC的結(jié)果沒達到閾值y，即使公共項目數(shù)足夠多，也不能說明兩個用戶更相似，其相似度即PCC的計算結(jié)果。只有當兩個用戶足夠相似時，公共項目數(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ù)。如果兩對用戶的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 基于多分段改進PCC算法流程

4 實驗結(jié)果及分析

4.1 實驗數(shù)據(jù)集

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

4.2 評估標準

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

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

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

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

4.3 實驗結(jié)果

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

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

圖2 k取不同值時的MAE值

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

圖3 k=5,r=5時準確率的對比

圖4 k=10,r=10時準確率的對比

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

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

5 結(jié)束語

盡管協(xié)同過濾推薦算法在推薦系統(tǒng)中使用非常廣泛，也是比較成熟的推薦算法，但其推薦精度仍有提高的空間。傳統(tǒng)基于PCC或改進PCC的協(xié)同過濾大多是通過用戶公共項目評分差，增加權(quán)值或參數(shù)進行改進，考慮不夠全面。本文提出的采用多分段改進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ù)自己的實際情況評分，這種用戶對推薦的精度產(chǎn)生了非常負面的影響，應(yīng)該提前鑒別并剔除。

參考文獻：

[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].計算機學報，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.