基于直接評分與間接評分的協(xié)同過濾算法

宋 威，陳利娟

（北方工業(yè)大學 信息工程學院，北京100144）

0 引 言

協(xié)同過濾［1－5］可主要分為兩類：一類是基于用戶的協(xié)同過濾算法，這類方法根據(jù)歷史評分的相似情況，將用戶分為不同的組群，若用戶屬于同一組群，表明他們以往偏好于類似的項目，而且他們對其它未評分項目也會做出相似的評價［6，7］；另一類是將相似性計算標準由用戶改為項目的方法，被稱為基于項目的協(xié)同過 濾算法［8，9］。Yamashita等［10］將基于用戶的算法和基于項目的算法融入于一個框架之內，通過調整權重的方式來體現(xiàn)用戶、項目在最終預測結果中的不同重要程度。

隨著網上購物行為的不斷深入普及，每位用戶、每種商品的評分在大型電子商務網站的總評分中所占比例越來越低，用戶評分稀疏性問題對改善推薦質量提出了越來越嚴峻的考驗。為解決這一問題，提出了一種基于直接評分與間接評分的協(xié)同過濾新算法DIRCF （direct and indirect rating for collaborative filtering），該算法的推薦結果融合了3方面因素，除了由基于用戶的評分和基于項目的評分構成的直接評分外，還融入了相似用戶對相似項目的評分。在DIRCF算法中，將基于直接推薦用戶與直接推薦項目的加權評分作為直接推薦結果，將相似用戶對相似項目的評分作為間接推薦結果，最終結果則通過對直接推薦結果與間接推薦結果做加權求和的方式產生。實驗結果表明，DIRCF算法能夠有效地提高推薦精度。

1 問題描述

協(xié)同過濾算法一般由用戶－項目評分矩陣描述，見表1。

表1 用戶－項目評分矩陣

表1中，每一行代表1個用戶對不同項目的評分，每一列代表不同用戶對1個項目的評分，每個元素代表該行對應的用戶對該列對應項目的評分，體現(xiàn)了用戶對項目的偏好程度。所謂協(xié)同過濾算法就是把預測評分最高的一組項目推薦給目標用戶。

2 DIRCF算法

提出的DIRCF 算法由直接評分和間接評分兩部分組成，其中：直接評分由基于用戶的評分和基于項目的評分的加權求和產生，而間接評分的依據(jù)則是相似用戶對相似項目的評分。

2.1 直接評分

2.1.1 基于用戶的評分

給定目標用戶ut，最少共同評分項目min＿item，則候選鄰居用戶集合定義為

式中：R （ut）、R （ux）——用戶ut和ux評分項目的集合，｜R （ut）∩R （ux）｜——集合R （ut）∩R （ux）中元素的個數(shù)。

在限定候選鄰居用戶之后，需要計算集合SCU（ut）中每個用戶ua與目標用戶ut的相似性程度，首先選擇余弦相似性作為度量用戶相似程度的基礎。給定目標用戶ut，用戶ua與ut間的余弦相似度定義為

式中：Ra，k和Rt，k——用戶ua和ut對項目ik的評分，n——項目的總數(shù)。

考慮到用戶－項目評分矩陣的稀疏性問題，我們提出了加權用戶相似性

式中：cos（ua，ut）——用戶ua和ut的余弦相似性，wU（a，t）——用戶評分權重，可由式 （4）計算得到

式中：Ia∩t和Ia∪t——用戶ua和ut評分項目集合的交集與并集，｜Ia∩t｜和｜Ia∪t｜——集合Ia∩t和Ia∪t中元素的數(shù)量。

由式 （3）可知，我們提出的加權用戶相似性度量標準一方面考慮了用戶整個評分向量之間的相似程度，另一方面也考慮了用戶間共同評分項目在各自評分項目中所占的比例，在傳統(tǒng)的余弦相似性和Pearson相關系數(shù)間找到了平衡點，從而更加適合于在不同稀疏程度的數(shù)據(jù)上進行推薦。

根據(jù)加權用戶相似性，目標用戶ut關于預測項目ij的直接推薦用戶集合為

式中：SU（ut）——根據(jù)式 （3）計算得到的前k 個相似用戶組成的集合。

對項目ij，稱ux∈DUj（ut）為直接推薦用戶；稱uy∈SU（ut）＼DUj（ut）為間接推薦用戶，記用戶ut相對于ij的間接推薦用戶集合為INDUj（ut）。

這樣，基于用戶的協(xié)同過濾評分結果PU（ut，ij）為

式中：simU（ua，ut）——由式 （3）計算的加權用戶相似性，和——用戶ua和ut的平均評分。

2.1.2 基于項目的評分

給定目標項目ij，最少共同評分用戶min＿user，則候選鄰居項目集合定義為

式中：R（ij）和R（ix）——評價項目ij和ix的用戶集合。為度量項目間的相似程度，提出了加權項目相似性

式中：wI（a，j）——項目評分權重，由式 （9）計算；cos（ia，ij）——項目ia和ij的余弦相似性，由式 （10）計算

式中：Ua∩j——同時評價項目ia和ij的用戶集合，Ua∪j——評價項目ia或ij的用戶集合，｜Ua∩j｜和｜Ua∪j｜——集合Ua∩j和Ua∪j的元素數(shù)量

式中：Rk，a和Rk，j——用戶uk對項目ia和ij的評分，m——用戶的總數(shù)。

定義目標項目ij關于用戶ut的直接推薦項目集合為

式中：SI（ij）——由式 （8）計算得到的前k個相似項目組成的集合。

對項目ij，稱ix∈DIt（ij）為直接推薦項目；稱iy∈SI（ij）＼DIt（ij）為間接推薦項目，記項目ij相對于用戶ut的間接推薦項目集合為INDIt（ij）。

這樣，基于項目的協(xié)同過濾評分結果PI（ut，ij）為

式中：simI（ia，ij）——由式 （8）計算得到的加權項目相似性，和——項目ij和ia的平均評分。

2.1.3 直接評分結果

給定目標用戶ut和項目ij，假設PU（ut，ij）是基于用戶的算法得到的評分，PI（ut，ij）是基于項目的算法得到的評分，則用戶ut對項目ij的最終評分可由式 （13）得到

其中：0≤λ≤1。當λ＝0時，即為基于項目的算法的結果；當λ＝1時，即為基于用戶的算法的結果。

與文獻 ［10］的方法不同，DIRCF 算法由式 （14）來計算直接評分權重λ，而不是在 ［0，1］區(qū)間內隨機取值

式中：｜DUj（ut）｜和｜DIt（ij）｜——直接推薦用戶集合DUj（ut）和直接推薦項目集合DIt（ij）的元素數(shù)量。

2.2 間接評分

除直接推薦用戶與直接推薦項目外，我們還使用了相似用戶對相似項目的評價，作為間接評分。

對用戶ut和項目ij，假設間接推薦用戶集合INDUj（ut）中用戶的數(shù)量為p，間接推薦項目集合INDIt（ij）中項目的數(shù)量為q，矩陣Rp×q表示由INDUj（ut）中的用戶和INDIt（ij）中的項目構成的矩陣，則相似評分集合定義為

在此基礎上，定義評分相似性為

式中：simU（ux，ut）——由式 （3）定義的加權用戶相似性，simI（iy，ij）——由式 （8）定義的加權項目相似性。

這樣，相似用戶對相似項目的間接評分定義為

其中，simU，I（ia，ij）是由式 （16）定義的評分相似性。

2.3 綜合評分結果

基于直接與間接評分結果，最終形成的用戶ut對項目ij的綜合評分結果為

式中：綜合評分權重ω由式 （19）計算

2.4 算法描述

本節(jié)給出基于直接評分與間接評分的協(xié)同過濾算法DIRCF。

3 實驗結果與分析

在電影評分數(shù)據(jù)集MovieLens［11］上，用平均絕對偏差（mean absolute error，MAE）作為主要標準比較了提出的DIRCF算法與基于用戶的協(xié)同過濾算法 （記作UBCF）［6］、基于項目的協(xié)同過濾算法 （記作IBCF）［8］、基于用戶和項目相融合的協(xié)同過濾算法 （記作UICF）［10］的推薦精度。MAE由式 （20）計算

式中： ｛p1，p2，…，pN｝是計算得到的用戶評分集合，｛q1，q2，…，qN｝是用戶實際的評分集合，N 表示評分項目的數(shù)量。

圖1給出了最近鄰用戶 （項目）個數(shù)k 分別取不同值時，4種算法的MAE比較結果。由圖1可知，在不同數(shù)量最近鄰的情況下，提出的DIRCF算法的MAE 均優(yōu)于其它3種算法。

圖1 不同最近鄰數(shù)量下4種算法MAE對比結果

由于最近鄰數(shù)量會對協(xié)同過濾算法的準確性產生重要影響，因此我們還比較了不同最近鄰數(shù)量下DIRCF算法的MAE變化情況，結果如圖2所示。

圖2 不同最近鄰數(shù)量下MAE的變化情況

由圖2可知，在最近鄰數(shù)量由10增加到80的過程中：MAE值先是呈現(xiàn)出逐漸降低的趨勢，當最近鄰數(shù)量為40時，達到了最低值0.735；一旦最近鄰數(shù)量超過了40，MAE值則呈現(xiàn)出了逐漸上升的趨勢。因此DIRCF 算法在最近鄰數(shù)量為40時可以達到最佳性能。

將4種算法的最近鄰數(shù)量確定為40后，我們對原始的MovieLens數(shù)據(jù)集做了5次隨機抽樣，得到5組數(shù)據(jù)集分別記為DS1、DS2、DS3、DS4、DS5，每組數(shù)據(jù)都將80%作為訓練集，其余的20%作為測試集。在這5組數(shù)據(jù)上的推薦精度比較結果如圖3 所示，可以看出在不同的數(shù)據(jù)中，DIRCF算法的MAE同樣均優(yōu)于其它3種算法。

為考察算法在不同稀疏程度的數(shù)據(jù)上的表現(xiàn)，我們還引入了用戶－項目評分矩陣的稀疏等級SL （sparsity level）的概念［12］，定義為

式中：E——用戶－項目評分矩陣中非空元素的數(shù)量，m 和n——評分矩陣行和列的數(shù)量。例如，MovieLens數(shù)據(jù)集記錄了943個用戶對1682部電影的100000條評分，則該數(shù)據(jù)集的稀疏等級為

圖3 5組數(shù)據(jù)集上4種算法MAE對比結果

我們分別隨機去除原始數(shù)據(jù)集中一定數(shù)量的評分，得到了3組更加稀疏的數(shù)據(jù)，分別記作D1、D2 和D3，表2分別給出了這3組數(shù)據(jù)集的特征，3組對比實驗的結果如圖4所示。

表2 數(shù)據(jù)集特性

圖4 不同稀疏等級下推薦質量比較

由圖4可以看出，在用戶數(shù)量成倍增加、稀疏等級不同的情況下，提出的DIRCF算法在3組實驗中均可以得到更低的MAE值，這說明該算法可以在一定程度上緩解由于數(shù)據(jù)稀疏性而造成的最近鄰選擇不準確的問題，從而提高了推薦質量。

4 結束語

提出了一種基于直接評分與間接評分的協(xié)同過濾算法。通過定義加權用戶相似性和加權項目相似性，構造了直接推薦用戶 （項目）集合與間接推薦用戶 （項目）集合，分別作為直接評分與間接評分的用戶 （項目）來源。此外，在直接推薦用戶 （項目）集合的基礎上，定義了直接評分與綜合評分的權重計算方法。這樣，通過對基于用戶的評分、基于項目的評分做加權求和的方式得到直接評分結果，再由相似用戶對相似項目的評分得到間接評分結果，最終由直接評分和間接評分得到綜合評分結果。實驗結果表明，提出的算法不但具有較高的推薦精度，而且能夠適用于不同稀疏程度的數(shù)據(jù)。

［1］Gedikli F.Recommender systems and the social Web：Leveraging tagging data for recommender systems ［M］.Wiesbaden：Springer Vieweg，2013.

［2］HUANG Liwei，LI Deyi.A review of information recommendation in social media ［J］.CAAI Transactions on Intelligent Systems，2012，7 （1）：1－8（in Chinese）.［黃立威，李德毅.社交媒體中的信息推薦 ［J］.智能系統(tǒng)學報，2012，7 （1）：1－8.］

［3］Davoodi E，Kianmehr K，Afsharchi M.A semantic social network－based expert recommender system ［J］.Applied Intelligence，2013，39 （1）：1－13.

［4］Cai Y，Leung HF，Li Q，et al.Typicality－based collaborative filtering recommendation ［J］.IEEE Transactions on Knowledge and Data Engineering，2014，26 （3）：766－779.

［5］WU Yueping，ZHENG Jianguo.Improved collaborative filte－ring recommendation algorithm ［J］.Computer Engineering and Design，2011，32 （9）：3019－3021 （in Chinese）. ［吳月萍，鄭建國.協(xié)同過濾推薦算法 ［J］.計算機工程與設計，2011，32 （9）：3019－3021.］

［6］Mu X，Chen Y，Yang J，et al.An improved similarity algorithm based on hesitation degree for user－based collaborative filtering ［C］//Proceedings of the 5th International Symposium on Advances in Computation and Intelligence，2010：261－271.

［7］Li Y，Zhai CX，Chen Y.Exploiting rich user information for one－class collaborative filtering ［J］.Knowledge and Information Systems，2014，38 （2）：277－301.

［8］Wang W，Yang J，He L.An improved collaborative filtering based on item similarity modified and common ratings ［C］//Proceedings of the International Conference on Cyberworlds，2012：231－235.

［9］YU Hong，MENG Lingmin.Collaborative filtering recommendation method considering asymmetry of items＇dependence level［J］.Computer Engineering and Design，2013，34 （1）：298－302 （in Chinese）.［于洪，孟令民.考慮項目依賴不對稱性的協(xié)同過濾推薦方法 ［J］.計算機工程與設計，2013，34 （1）：298－302.］

［10］Yamashita A，Kawamura H，Suzuki K.Adaptive fusion method for user－based and item－based collaborative filtering［J］. Advances in Complex Systems，2011，14 （2）：133－149.

［11］GroupLens Research Lab.MovieLens data sets ［EB/OL］.［2014－05－05］.http：//www.grouplens.org/node/12.

［12］Pan W，Xiang EW，Liu NN，et al.Transfer learning in collaborative filtering for sparsity reduction ［C］//Proceedings of the Twenty－Fourth AAAI Conference on Artificial Intelli－gence，2010：230－235.