基于項目屬性和局部優(yōu)化的協(xié)同過濾推薦算法

劉慧婷，陳 超，吳共慶，趙 鵬

（1.安徽大學 計算機科學與技術學院，安徽 合肥 230601；2.合肥工業(yè)大學 計算機與信息學院，安徽 合肥 230009）

隨著Web 2.0技術的成熟，推薦作為一種獨立的概念被提出來并得到了深入的研究.推薦技術包括協(xié)同過濾推薦、基于內(nèi)容的推薦、組合推薦等.其中協(xié)同過濾技術是至今為止最成功的個性化推薦技術之一［1］，被廣泛地應用于電子商務的各個領域.協(xié)同過濾技術又可以分為基于項目的協(xié)同過濾和基于用戶的協(xié)同過濾.基于項目的協(xié)同過濾的基本思想是首先為目標項目尋找興趣最相似的k個鄰居項目，然后計算當前用戶對其鄰居的興趣程度，預測對目標項目的感興趣程度.

然而隨著電子商務站點用戶和商品的數(shù)量不斷增加，協(xié)同過濾面臨著嚴峻的數(shù)據(jù)稀疏性和實時性的挑戰(zhàn)，導致推薦系統(tǒng)質(zhì)量迅速下降.許多研究者提出了一些新的方法來改進協(xié)同過濾技術的不足.Crmonesi等［2］提出一種基于內(nèi)容的評分預測來填充偽評分項目，從而有效緩解數(shù)據(jù)稀疏性問題.Ma和黃等［3－4］利用項目的協(xié)同過濾和用戶的協(xié)同過濾線性組合方式預測評分進行推薦.Choi等［5］提出一種新的相似度計算方法，針對不同的目標項目選擇不同的鄰居.Jamali等［6］提出將用戶之間的信任關系進行深度搜索，尋找更深層次的相似性用戶來進行推薦，同時能夠解決冷啟動的問題.

圍繞著解決數(shù)據(jù)稀疏性問題，并在已有的研究基礎上，作者的主要貢獻是：引入改進jaccard的自適應系數(shù)來調(diào)節(jié)項目間的相似性值，獲得更加準確的項目相似性；利用拉普拉斯平滑方法對項目屬性的相似性進行優(yōu)化，在項目屬性特征很少時，能夠獲得較為準確的項目相似性；利用局部相似性有效地降低整體的預測誤差，并使誤差在一定程度上收斂于某一固定值.實驗結(jié)果表明：基于項目屬性和局部優(yōu)化選擇的協(xié)同過濾推薦算法CUCF對比用戶間多相似度推薦算法UMCF［7］（collaborative filtering recommendation algorithm based on user＇s multi－similarity，簡稱 UMCF）、基于項目屬性和云填充的協(xié)同過濾推薦算法IACF［8］（collaborative filtering recommendation algorithm based on item attribute and cloud model filling，簡稱IACF）和考慮項目屬性推薦模型（Sim1和Sim2）［9］，CUCF的預測準確率較高，有效地減小了數(shù)據(jù)稀疏性對推薦質(zhì)量的影響，提高了推薦系統(tǒng)的預測準確率.

1 問題描述與基本方法

推薦系統(tǒng)中用戶對項目的評分數(shù)據(jù)集中包含m個用戶的集合U和n個項目的集合I，其中用戶Um對項目In的評分為Rm，n，該評分體現(xiàn)了用戶Um對項目In的興趣程度.

1.1 傳統(tǒng)的相似性度量方法

相似性度量是協(xié)同過濾推薦模型中評分預測的基礎，其質(zhì)量直接影響著預測的準確率.傳統(tǒng)的相似性度量方法有以下2種：余弦相似性和Pearson相關相似性.

（1）余弦相似性：設項目i和項目j在m維對象空間上的評分表示為向量i，j，則項目i和項目j之間的相似性通過余弦相似性度量如公式（1）所示

（2）Pearson相關相似性：設項目i和項目j被共同評分的用戶集合用Uij表示，則Pearson相關相似性度量如公式（2）所示

文獻［10］中提出基于用戶的協(xié)同過濾的推薦算法中，Pearson相似性度量方法比其他用戶的協(xié)同方法更勝一籌，而基于項目的協(xié)同過濾推薦技術中，余弦相似度方法比Pearson相關性度量表現(xiàn)更好.所以論文后期實驗中均采用余弦相似性方法計算項目之間的相似性.

1.2 協(xié)同過濾的評分預測過程

在計算項目之間的相似性后，為用戶對于未評分的項目i尋找最相似的k個近鄰項目S（i），最后預測該用戶對項目i的評分，計算公式如（3）所示

其中：sim（i，n）表示目標項目i與最近鄰居n之間的相似性，Ru，n表示用戶u對項目n的評分.和分別表示項目i和項目n的平均評分.通過公式（3）來預測用戶對所有未評分的項目的評分，最后選擇預測評分高的若干項目反饋給當前用戶.

2 CUCF算法

論文提出了CUCF方法，首先改進了項目之間相似性的計算；然后利用拉普拉斯平滑方法優(yōu)化了在項目屬性中計算項目間相似性，并線性結(jié)合兩方面相似性結(jié)果；最后利用局部優(yōu)化選擇方法選擇目標的近鄰對象作為推薦群.

2.1 基于評分的項目相似性改進

由于數(shù)據(jù)的稀疏性，利用余弦相似性公式計算時存在公共項目數(shù)量很少而相似度值很高的不合理現(xiàn)象.為了降低這種影響，考慮了公共評價項目的數(shù)量對項目之間相似性的作用，根據(jù)文獻［9］，選擇一種jaccard系數(shù)來自適應調(diào)節(jié)項目間的相似性值.如公式（4）所示

其中：ri和rj分別表示項目i、j被評分的用戶集合，｜｜表示集合中用戶的數(shù)量.jaccard系數(shù)能夠較好地反映用戶在評價方面的重疊情況，但是在實際中兩個項目被共同評分的用戶數(shù)量很少，設置為0，導致相似度值很低.提出一種新的改進公式，如公式（5）、（6）所示

可以看出，上式中Jaccard（i，j）的取值范圍為［0，1］，當兩個項目完全被相同的用戶評分時，值為1；相反，當完全被不同的用戶評分，值為0.它反映了兩個項目在獲得用戶評價方面的相對差異程度，同時對比jaccard（i，j）提高了相似度計算的值，更好地反映了用戶評分的重疊情況，修正了余弦相似性公式，最終獲得更加準確的項目相似性.

2.2 拉普拉斯平滑改進項目屬性中項目相似性

在可以得到任意兩個不同項目的屬性特征向量時，利用公式（1）余弦相似性公式計算出兩個項目的相似性.該方法在預測過程中時間復雜度很低，但是預測精度大大降低，這是由于特征屬性的數(shù)量較少和僅為0、1權(quán)重的限制.文獻［10］也提出基于項目屬性的推薦必須使用相對較大的特征集合才能提高預測準確率.

拉普拉斯平滑又被稱為加1平滑，主要為了解決零概率問題.針對論文中零概率問題就是由于項目的屬性特征分類數(shù)目較少，在利用項目特征矩陣計算兩個項目的相似性時會產(chǎn)生大量的零值，這時候得出這兩個項目之間無相關性，這顯然是不合理的，因為不能因為特征分類少，兩個項目之間沒有共同的屬性特征就判斷相似性為零.

使用拉普拉斯平滑后，項目屬性的相似性計算公式如（7）所示

即在分子上加上1、分母加上相關聯(lián)項目的個數(shù)K，其取值范圍為｛1，2，…，K｝.其中：ti和tj分別表示項目i、j相應的屬性特征向量.拉普拉斯平滑方法并不需要處理原始的項目屬性矩陣，時間復雜度較低，可以快速準確地計算項目相似性.

2.3 組合項目相似性

根據(jù)文獻［11］，利用simr（i，j）和simt（i，j）從不同的兩個角度度量了項目相似性，再進行線性組合，就可以獲得更為全面的項目相似性度量方法Sim（i，j），如公式（8）所示

其中：參數(shù)α為平衡因子，調(diào)節(jié)兩個方面的相似性對于Sim（i，j）的影響，取值范圍為［0，1］.

2.4 局部優(yōu)化選擇預測目標的近鄰對象

傳統(tǒng)的協(xié)同過濾方法在尋找相似性最大的k個鄰居后，當設置近鄰個數(shù)k太高時，而實際相似鄰居個數(shù)不夠，需要補充額外噪音，導致推薦結(jié)果準確性大大降低.論文采用局部優(yōu)化方法選擇預測目標，設置最小閾值參數(shù)μ，降低近鄰集合的規(guī)模，獲得最優(yōu)近鄰集合Su（i）.局部優(yōu)化選擇相似近鄰的計算方式sgi，j＊Sim（i，j）＞μ，其中：閾值μ為常量，μ不能設置過大，否則容易導致相似近鄰數(shù)目少，覆蓋率過低.sgij為重要性權(quán)重因子［10］，sgij傾向于有更多評分物品的對等者［11］.該方法利用局部的相似性有效地降低整體的預測誤差，當近鄰個數(shù)k設置較大時，可使得評分預測的誤差在一定程度上收斂于某一固定值，增強了推薦系統(tǒng)的穩(wěn)定性.

3 實驗評估與分析

3.1 數(shù)據(jù)集及評價標準

論文實驗數(shù)據(jù)集取自MovieLens站點，從用戶評分數(shù)據(jù)庫中選擇100 000條評分數(shù)據(jù)作為實驗數(shù)據(jù)集，實驗數(shù)據(jù)集中共包含943個用戶和1 682部電影，其中每個用戶至少對20部電影進行評分.整個實驗數(shù)據(jù)集需要進一步劃分為訓練集和測試集，整個數(shù)據(jù)集的80%作為訓練集，20%作為測試集.除此之外，數(shù)據(jù)集中還包含了電影的屬性特征如動作、喜劇、犯罪、動畫等18種.

為了度量整個數(shù)據(jù)的稀疏性，引入稀疏等級的概念，其定義為用戶評分數(shù)據(jù)矩陣中未評分的條目所占的百分比.現(xiàn)在的電影數(shù)據(jù)集的稀疏度等級為：1－100 000／（943＊1 682）＝0.937 95.

統(tǒng)計精度度量方法中的平均絕對誤差（mean absolute error，簡稱MAE）法被廣泛用于評價協(xié)同過濾推薦系統(tǒng)的推薦質(zhì)量.MAE是對比預測值和實際值之間偏差來預測準確性的，其定義為MAE＝，其中：pi為預測的用戶評分，ri為實際的用戶評分，N是測試集中的項目數(shù).

3.2 評分的相似性計算改進效果實驗

該實驗是一組對比實驗，從預測準確度MAE方面，對3.1闡述的評分的相似性計算公式改進效果，分別在基于項目的協(xié)同過濾方法和局部優(yōu)化的協(xié)同過濾方法中進行驗證，結(jié)果如圖1所示.

圖1 LCF與jaccardCF及JaccardCF對比Fig.1 Comparison of LCF，jaccardCF with JaccardCF

圖1中，LCF為傳統(tǒng)的基于項目的協(xié)同過濾的方法，jaccardCF為利用jaccard系數(shù)改進了相似性度量的協(xié)同過濾方法，該方法避免了一些公共項目數(shù)目少而相似度值高的不合理現(xiàn)象，降低評分預測的誤差.JaccardCF方法是在基于項目的協(xié)同過濾方法中對jaccard系數(shù)的改進，進一步降低預測的誤差.

3.3 拉普拉斯平滑改進相似性的實驗

該實驗是對文中3.1提出的拉普拉斯平滑改進的有效性驗證，結(jié)果如圖2所示.

圖2 LaUCR方法與CosUCR方法的對比Fig.2 Comparison of LaUCR with CosUCR

圖2中，CosUCR是利用余弦相似性，在項目屬性關系中進行局部優(yōu)化選擇方法.LaUCR是論文提出的利用拉普拉斯平滑方法，在同一條件下，對項目屬性中項目相似性的改進.實驗結(jié)果表明，拉普拉斯平滑方法大大降低了預測的誤差，在項目屬性關系中利用拉普拉斯平滑方法可以快速高效地計算項目相似性.同時利用局部優(yōu)化的方法，當k趨于一定數(shù)值時，MAE收斂于一個固定值.

3.4 結(jié)合項目相似性的局部優(yōu)化CUCF方法效果實驗

3.4.1 參數(shù)α的最優(yōu)取值

論文中線性組合Jaccard系數(shù)改進和拉普拉斯平滑兩個角度度量的項目相似性.在MovieLens100k數(shù)據(jù)集中，調(diào)節(jié)參數(shù)α的最優(yōu)值，α的取值范圍［0.1，0.2，0.3，0.4，0.5，0.6，0.7，0.8，0.9，0.95，1.0］，并選擇k＝20進行對比實驗.實驗結(jié)果如圖3所示.

從圖3可知，當α取0.9時，CUCF算法能夠獲得最優(yōu)的準確率，使得整體的預測誤差最小.當然，參數(shù)對于不同的數(shù)據(jù)集設置有所不同.

圖3 k＝20時調(diào)節(jié)參數(shù)α的對比實驗Fig.3 MAE of prediction rating withα when k＝20

3.4.2 CUCF方法與JaccardUCF及LaUCR方法的比較

該實驗驗證了線性結(jié)合項目相似性的局部優(yōu)化方法CUCF對于片面的JaccardUCF方法和LaUCR方法的有效性，結(jié)果如圖4所示.

圖4 CUCF與LaUCR和JaccardUCF對比實驗Fig.4 Comparison of LaUCR，jaccardUCF with CUCF

由圖4可以看出，當k太小，預測質(zhì)量將會受到影響.文獻［10］指出，對于MovieLens數(shù)據(jù)集，在大多數(shù)實際情況下，選取20～50個近鄰比較合理.線性組合的項目相似性CUCF方法比從兩個不同的角度度量了項目相似性即LaUCR方法和JaccardUCF方法，更能提高整體預測的準確率.

3.4.3 CUCF方法與其他方法的比較

為了驗證推薦算法在不同項目近鄰數(shù)目下的具體性能，該實驗將從MAE方面，選擇UMCF［7］、IACF［8］和考慮項目屬性推薦方法（Sim1和Sim2）［9］與論文提出的CUCF方法作對比，比較結(jié)果如表1和圖5所示.

表1 不同算法在k取值不同時的MAE值Tab.1 Comparison of MAE in five algorithms

圖5 CUCF與其他4種推薦方法對比實驗Fig.5 Comparison of CUCF with other four algorithms

在表1和圖5中可以看出，CUCF方法當k取20時獲得最優(yōu)預測準確率.論文提出的CUCF方法對比其他4種方法，在預測準確率方面可以達到較好的效果，有效地減小了數(shù)據(jù)稀疏性對推薦質(zhì)量的影響.對比UMCF方法準確率提高15.5%，對比效果較好的Sim2方法準確率提高7.1%.同時，當鄰居個數(shù)k逐漸增大時，CUCF方法的預測準確率會小幅度下降并趨于穩(wěn)定值.

4 結(jié)束語

論文分析了傳統(tǒng)協(xié)同過濾方法面臨數(shù)據(jù)高度稀疏的問題，提出一種基于項目屬性和局部優(yōu)化選擇的協(xié)同過濾推薦算法CUCF.首先改進基于評分的項目相似性，然后深入分析項目屬性的關系，通過拉普拉斯平滑方法計算項目屬性中項目相似性.最后線性結(jié)合兩方面的項目相似性結(jié)果，并利用局部優(yōu)化方法選擇目標的近鄰對象作為推薦群，有效地降低整體的預測誤差，使預測誤差在一定程度上收斂于某一固定值.實驗結(jié)果表明，與現(xiàn)有的基于用戶、基于項目和考慮項目屬性的改進協(xié)同過濾方法相比，CUCF方法對推薦系統(tǒng)的預測準確率方面具有優(yōu)越性.下一步的研究工作是利用爬蟲技術獲取更多的相關電影的屬性特征來提高系統(tǒng)的推薦質(zhì)量.此外，還可以將社交網(wǎng)絡加入到推薦系統(tǒng)中，通過分析獲得更加完善且精確的用戶或項目之間的相關性，同樣是一個很有前景的研究方向，這樣不僅可以提供推薦的高質(zhì)量性，還能有效避免推薦系統(tǒng)的冷啟動問題.

［1］Adomavicius G，Tuzhilin A.Toward the next generation of recommender systems：a survey of the state－of－theart and possible extensions［J］.Knowledge and Data Engineering，IEEE Transactions，2005，17（6）：734－749.

［2］Cremonesi P，Turrin R，Airoldi F.Hybrid algorithms for recommending new items［C］／／Proceedings of the 2nd International Workshop on Information Heterogeneity and Fusion in Recommender Systems，ACM，2011：33－40.

［3］Ma H，King I，Lyu M R.Effective missing data prediction for collaborative filtering［C］／／Proceedings of the 30th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval，ACM，2007：39－46.

［4］黃創(chuàng)光，印鑒，汪靜，等.不確定近鄰的協(xié)同過濾推薦算法［J］.計算機學報，2010，33（8）：1369－1377.

［5］Choi K，Suh Y.A new similarity function for selecting neighbors for each target item in collaborative filtering［J］.Knowledge－Based Systems，2013，37：146－153.

［6］Jamali M，Ester M.Trustwalker：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，ACM，2009：397－406.

［7］范波，程久軍.用戶間多相似度協(xié)同過濾推薦算法［J］.計算機科學，2012，39（1）：23－26.

［8］孫金剛，艾麗蓉.基于項目屬性和云填充的協(xié)同過濾推薦算法［J］.計算機應用，2012，32（3）：658－660.

［9］楊興耀，于炯，吐爾根丒依布拉音，等.考慮項目屬性的協(xié)同過濾推薦模型［J］.計算機應用，2013，33（11）：3062－3066.

［10］Dietmar J.推薦系統(tǒng)［M］.蔣凡，譯.北京：人民郵電出版社，2013.

［11］項亮.推薦系統(tǒng)實踐［M］.北京：人民郵電出版社，2013.