彭 石，周志彬，王國軍

(中南大學信息科學與工程學院，長沙 410083)

1 概述

隨著電子商務的發(fā)展，自動推薦商品已經成為提升銷售額的重要手段[1]。協(xié)同過濾算法是目前應用最廣泛的推薦算法之一。協(xié)同過濾算法的基本思想是尋找與目標用戶或目標項目相似的用戶集或項目集，用相似集合的特征預測目標的特征[2]。

隨著用戶和項目的數(shù)量急劇增長，用戶-項目評分矩陣變得極其龐大。同時由于個人的興趣和喜好等個性特征不同，因此用戶往往只會使用很少一部分項目，必然導致用戶對項目的評分數(shù)據(jù)稀少，很多系統(tǒng)中評分數(shù)據(jù)的比例小于 1%。這就是協(xié)同過濾推薦系統(tǒng)中存在的用戶-項目評分矩陣稀疏性問題[3]。

余弦相似度、調整余弦相似度、皮爾遜相關系數(shù)[4]等傳統(tǒng)相似度計算方法僅利用評分數(shù)據(jù)進行計算。在評分矩陣極其稀疏的情況下，2個有相同興趣的人可能因沒有共同評分而不能被發(fā)現(xiàn)。為了克服評分矩陣稀疏性問題，很多學者提出了評分矩陣預先填充的算法。

本文在分析傳統(tǒng)評分矩陣預先填充算法的基礎上，提出一種改進的算法，論述其特點，給出改進的協(xié)同過濾算法流程，分析實驗策略、實驗數(shù)據(jù)、評價標準和實驗結果。

2 相關工作

協(xié)同過濾算法可按照比較方式分為2類：基于用戶的協(xié)同過濾算法和基于項目的協(xié)同過濾算法。前者比較用戶之間的相似性；后者比較項目之間的相似性。本文在基于用戶的協(xié)同過濾算法基礎上，根據(jù)項目相似性對評分矩陣進行預先評分填充，提高矩陣稠密度。

令用戶集合 U={U1,U2,…,Un}，項目集合 I={I1,I2,…,In}，rx,i為用戶 Ux對項目 Ii的評分，所有的 rx,i構成一個矩陣，稱為用戶-項目評分矩陣，如表 1所示，其中，問號表示用戶未給對應項目評分。

表1 用戶-項目矩陣

大部分評分系統(tǒng)中的評價都設為5個等級，分別表示很不滿意、不滿意、一般、滿意、很滿意，對應于1～5的分值。數(shù)值越大表示評價越好，數(shù)值越小表示評價越差，問號則表示用戶未給予對應項目評分。

2.1 傳統(tǒng)相似度計算方法

傳統(tǒng)相似度計算方法主要有以下3種：

(1)皮爾遜相關系數(shù)。皮爾遜相關系數(shù)表示2組數(shù)據(jù)的線性相關度，可以描述2組數(shù)據(jù)的相似性。其計算公式為：

其中，n為樣本量；X、Y分別為 2組長度相同的數(shù)據(jù)。相關系數(shù)用r表示，r的絕對值越大表明相關性越強。r>0表示正線性相關，r<0表示負線性相關，r=0表示線性不相關，但可能存在其他曲線方式的相關性。

(2)余弦相似度。余弦相似度用2個向量的夾角余弦值表示相似程度，夾角越小相似度越大：

其中，n是向量的維度；xi、yi分別是X、Y對應的分量。

(3)調整余弦相似度。余弦相似度存在一些缺陷，為了盡量消除這種缺陷，有研究者提出調整余弦相似度計算方法：

2.2 傳統(tǒng)方法存在的問題

傳統(tǒng)相似度計算方法基于2個用戶的共同評分向量。在極其稀疏的評分矩陣中，2個用戶的共同評分項目更少，從而導致傳統(tǒng)算法推薦精度不高。

傳統(tǒng)相似度計算方法無法識別部分相似的用戶。以表1中的數(shù)據(jù)為例。U2和U3是有相似興趣的用戶，但用戶U2沒有對項目I1評分，用戶U3沒有對項目I2評分。傳統(tǒng)相似度計算的結果認為它們不相似。但項目I1與I4的評分特征非常相似，可以根據(jù)項目之間的相似性推測用戶 U2對項目 I1的評分為 3。有了這個預先填充的評分，通過傳統(tǒng)相似度計算的結果可以發(fā)現(xiàn)U2和U3是相似的。

為了解決用戶評分數(shù)據(jù)的極端稀疏性并更好地挖掘用戶的相似性，很多學者提出了預先對用戶-項目評分矩陣進行填充的算法。

簡單的辦法就是將未評分項目設為一個固定的缺省值。通常取用戶或項目的評分均值。這種改進方法確實可以提高推薦精度，但效果有限。

文獻[5]提出了基于項目評分預測的協(xié)同過濾算法，文獻[6]提出了基于概率知識的評分填充算法。文獻[7]提出了一種信任度傳播的評分填充算法。文獻[8]提出一種基于云模型的評分填充算法。文獻[9]提出了一種基于熵的協(xié)同過濾推薦模型。這些方法均有效提高了推薦精度，但沒有考慮項目的屬性，只考慮了評分。雖然有一定效果，但是還需要進一步改進。推薦項目往往具備多方面的屬性，如分類、顏色、價格。同一類型的項目屬性通常也有較高的相似性。結合評分相似度和屬性相似度能夠進一步提高評分填充的精度。文獻[10]提出了一種基于項目的協(xié)同過濾算法，結合了項目的評分相似度和項目的屬性相似度，有較好的推薦效果。

本文受此啟發(fā)，通過信息熵知識構造項目屬性的加權 Jaccard系數(shù)相似度，進而設計一種改進的結合項目屬性和評分的綜合相似度，提出一種依據(jù)項目的綜合相似度對評分矩陣進行預先填充的協(xié)同過濾算法。

3 基于信息熵的屬性相似度

3.1 基于屬性的相似度

令項目的屬性集合為A={a1,a2,…,am}。以電影推薦系統(tǒng)中的電影為例。假設 a1代表動作片，a2代表喜劇片，a3代表恐怖片，a4代表紀錄片，a5代表警匪片。一部電影可以同時屬于2個類型，見表2。

表2 電影屬性示例

傳統(tǒng)的計算集合的相似度可使用Jaccard系數(shù)。A代表 Ii的屬性集合，B代表 Ij的屬性集合。則Ii和 Ij的屬性相似度為：

其中，A∩B表示2個集合中的相同屬性個數(shù)；A∪B表示 2個屬性集合的元素總數(shù)。根據(jù)定義可知，J(A,B)∈[0,1]。本文認為，不同的屬性因為屬性值出現(xiàn)的概率不同，具有不同的影響力。為改進 Jaccard系數(shù)相似度，本文以屬性的信息熵作為屬性的加權，構造加權Jaccard系數(shù)相似度。

3.2 信息論

信息是抽象概念，信息量在香農提出信息論之前是無法衡量的東西。香農于1948年10月發(fā)表的論文《通信的數(shù)學理論》從概率統(tǒng)計角度給出了相關的定義。

3.2.1 信息量

自信息 I(x)是指信源中某一信號 x攜帶的信息量。信源中不同的信號都攜帶了一定量的信息，自信息根據(jù)信號出現(xiàn)的概率表示一個特定信號的信息量：

3.2.2 信息熵

信息熵定義為各信號的信息量的數(shù)學期望值，表示整個系統(tǒng)的平均信息量。信息熵從統(tǒng)計學角度描述了信源的特征，表示總體的不確定性程度：

3.3 改進的項目綜合相似度

Jaccard系數(shù)相似度并沒有考慮每個屬性的加權。有些屬性對商品的區(qū)分度大，有些區(qū)分度很小。舉個例子，如果推薦系統(tǒng)中所有電影的類型都是動作片，那么這個類型的屬性就沒有參與相似度計算的必要了，因為該屬性沒有區(qū)分能力。如果有一半的電影屬于喜劇片，一半的電影不屬于喜劇片，則該屬性對這個系統(tǒng)中的電影有很強的區(qū)分能力。

可以用屬性的信息熵來描述每個屬性對項目的重要程度，構造一種加權Jaccard系數(shù)相似度。

對于一個屬性 am，其取值能夠構成一個集合V(am)={vm1,vm2,…,vmk}。vm1表示屬性m的第k個屬性值。部分屬性的取值空間可能是連續(xù)的實數(shù)空間。對于這種情況，可以對取值空間進行離散化，并對每一個子區(qū)間命名。例如，價格屬性屬于這種情況，可簡單地離散化為3個價位段：高端價位，中端價位，低端價位。

定義屬性值vmk的出現(xiàn)概率如下：

其中，count(vmk)表示系統(tǒng)中屬性am的值為vmk的項目總數(shù)量；total_count表示所有項目的總數(shù)量，進而定義屬性值vmk的信息量如下：

進一步可以得到屬性am的熵：

信息熵大的屬性對項目有更好的區(qū)分度，可以賦予更大的加權。構造項目屬性的加權 Jaccard系數(shù)相似度如下：

由定義可知，sim3(Ii, Ij)∈[0,1]。其中，maxm是推薦項目擁有的屬性數(shù)量；S(Ii,Ij, am)的定義如下：

其中，attr(Ii,am)表示項目Ii關于屬性am的值；S(Ii,Ij,am)比較項目 Ii和 Ij關于屬性 am的值，如果相同，則結果為1，否則，結果為0。

最后，通過線性加權結合基于項目評分的相似度與基于項目屬性的加權Jaccard系數(shù)相似度，構 造項目的綜合相似度計算公式：

其中，α是一個調節(jié)因子，調節(jié)項目評分相似度和項目屬性相似度的比重，α∈[0,1]。

4 協(xié)同過濾算法

本文的改進協(xié)同過濾算法在經典的協(xié)同過濾算法流程上增加了一個評分矩陣預先填充過程。

算法主要流程如下：

輸入 目標用戶Ux、用戶-項目矩陣

輸出 目標用戶Ux的推薦項目集合

(1)遍歷項目集合。

(2)對每一個項目 Ii，用式(12)計算與其他項目之間的綜合相似度，構造各項目的相似項目集合。

(3)基于項目Ii的相似項目集合，用式(13)對Ii的未知評分進行填充。

其中，predict(Ii,Ux)表示基于 Ii的相似項目集合預測的用戶Ux對項目Ii的評分；Nei(Ii)表示與Ii相似的項目集合。

(4)基于經過填充的評分矩陣，用式(3)計算目標用戶與其他用戶間的相似度，構造相似鄰居集合。

(5)根據(jù)目標用戶的相似用戶集合，用式(14)為目標用戶的未知項目預測評分，最后產生推薦：

其中，predict(Ux,II)表示基于用戶Ux的相似用戶集合預測的用戶Ux對項目Ii的評分值；Nei(Ux)表示Ux的相似用戶集合。

5 實驗與結果分析

5.1 實驗策略

本文在5種相似用戶集合規(guī)模(topn){4, 8, 12, 16,20}上，分別對經典的協(xié)同過濾算法(Classic Collaborative Filtering, CCF)、基于項目評分相似性進行評分填充的協(xié)同過濾(Collaborative Filtering Based on Rating Filling, CFBRF)算法及本文算法進行對比實驗。

5.2 測試數(shù)據(jù)集

本文選用了 grouplens小組提供的測試數(shù)據(jù)集。grouplens收集了 movielen電影評價網上的大量評分信息，整理成驗證數(shù)據(jù)包。眾多的協(xié)同過濾算法使用這幾個數(shù)據(jù)包來驗證算法的性能和精度。本文選擇的數(shù)據(jù)集包含943個用戶對1 682部電影的100 000條評分信息。

5.3 評估標準

首先對數(shù)據(jù)包進行隨機化混洗操作。然后采用5折交叉驗證法，將實驗數(shù)據(jù)集平均分成5個互不相交的數(shù)據(jù)子集，訓練集和測試集的數(shù)據(jù)比例為4：1。每次實驗選擇其中一個數(shù)據(jù)子集作為測試集，其余4個數(shù)據(jù)子集作為訓練集。如此循環(huán)5次，取每次實驗結果的平均值作為最終結果。5折交叉驗證法可以有效降低實驗誤差。

在單次實驗中，度量推薦系統(tǒng)的指標主要包括統(tǒng)計精度方法和決策支持精度方法。其中，統(tǒng)計精度方法——平均絕對誤差(Mean Absolute Error, MAE)為大多數(shù)推薦系統(tǒng)采用。平均絕對誤差用系 統(tǒng)預測值與實際用戶評分值之間的偏差來反映推薦的精確度。設預測的用戶評分值為{p1, p2, …, pn}，對應的實際評分值為{q1, q2, …, qn}，則MMAE的計算公式如下：

MMAE越小表示預測值與實際值的差異越小，推薦效果越好。

5.4 結果分析

首先分析在相似用戶集合為 4、8、12、16、20時，α參數(shù)對CFBWJI算法的影響。

圖1表明，當α接近0.9時，能夠接近最優(yōu)值。

圖1 α參數(shù)對本文算法的影響

圖2表明，經過評分矩陣填充的算法均優(yōu)于經典算法，本文的CFBWJI算法在優(yōu)化參數(shù)的情況下能夠進一步降低MMAE值，提供最精確的預測結果。

圖2 各算法的平均絕對誤差

6 結束語

傳統(tǒng)協(xié)同過濾算法面臨用戶-項目評分矩陣極其稀疏的問題，導致2個用戶的共同評分項目稀缺。傳統(tǒng)的相似度計算方法如余弦相似度、皮爾遜相關系數(shù)等基于2個用戶的共同評分，因此，推薦效果不理想。本文通過屬性的信息熵構造加權 Jaccard系數(shù)相似度，進而提出了結合項目的屬性和評分的綜合相似度，依據(jù)項目的綜合相似度預先對評分矩陣進行填充，能夠在一定程度上緩解矩陣稀疏性問題，同時挖掘出更多相似用戶。實驗結果表明，改進算法相比傳統(tǒng)算法有效地提高了推薦精度，用戶同樣擁有各種屬性信息。下一步工作將結合用戶的屬性等信息進行更精確的相似度計算。

[1]Linden G, Smith B, York J.Amazon.com Recommendations: Item-to-item Collaborative Filtering[J].IEEE Internet Computing, 2003, 7(1): 76-80.

[2]Herlocker J L, Konstan J A, Terveen L G, et al.Evaluating Collaborative Filtering Recommender Systems[J].ACM Transactions on Information Systems, 2004, 22(1): 5-53.

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

[4]Sarwar B, Karypis G, Konstan J, et al.Item-based Collaborative Filtering Recommendation Algorithms[C]//Proc.of the 10th International Conference on the World Wide Web.[S.l.]: IEEE Press, 2001: 285-295.

[5]鄧愛林, 朱揚勇, 施伯樂.基于項目評分預測的協(xié)同過慮推薦算法[J].軟件學報, 2003, 14(9): 1621-1628.

[6]周軍鋒, 湯 顯, 郭景峰.一種優(yōu)化的協(xié)同過濾推薦算法[J].計算機研究與發(fā)展, 2004, 40(10): 1843-1847.

[7]Massa P, Avesani P.Trust-aware Collaborative Filtering for Recommender Systems[C]//Proc.of Federated International Conference on Move to Meaningful Internet.[S.l.]: IEEE Press, 2004: 492-508.

[8]余志虎, 戚玉峰.一種基于云模型數(shù)據(jù)填充的算法[J].計算機技術與發(fā)展, 2010, 20(12): 35-37.

[9]辛 羽, 黃佳進.基于熵的協(xié)同過濾推薦模型[C]//第十屆中國Rough集與軟計算、第四屆中國Web智能、第四屆中國粒計算聯(lián)合會議論文集.重慶: 中國計算機學會, 2010.

[10]Wu Yueping, Zheng Jianguo.A Collaborative Filtering Recommendation Algorithm Based on Improved Similarity Measure Method[C]//Proc.of IEEE International Conference on Progress in Informatics and Computing.[S.l.]: IEEE Press, 2010: 246-249.