基于評分矩陣預填充的協同過濾算法

彭 石，周志彬，王國軍

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

1 概述

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

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

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

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

2 相關工作

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

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

表1 用戶-項目矩陣

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

2.1 傳統相似度計算方法

傳統相似度計算方法主要有以下3種：

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

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

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

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

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

2.2 傳統方法存在的問題

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

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

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

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

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

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

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

3.1 基于屬性的相似度

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

表2 電影屬性示例

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

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

3.2 信息論

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

3.2.1 信息量

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

3.2.2 信息熵

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

3.3 改進的項目綜合相似度

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

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

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

定義屬性值vmk的出現概率如下：

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

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

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

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

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

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

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

4 協同過濾算法

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

算法主要流程如下：

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

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

(1)遍歷項目集合。

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

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

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

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

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

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

5 實驗與結果分析

5.1 實驗策略

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

5.2 測試數據集

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

5.3 評估標準

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

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

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

5.4 結果分析

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

圖1表明，當α接近0.9時，能夠接近最優值。

圖1 α參數對本文算法的影響

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

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

6 結束語

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

[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]孫小華.協同過濾系統的稀疏性與冷啟動問題研究[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]鄧愛林, 朱揚勇, 施伯樂.基于項目評分預測的協同過慮推薦算法[J].軟件學報, 2003, 14(9): 1621-1628.

[6]周軍鋒, 湯 顯, 郭景峰.一種優化的協同過濾推薦算法[J].計算機研究與發展, 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]余志虎, 戚玉峰.一種基于云模型數據填充的算法[J].計算機技術與發展, 2010, 20(12): 35-37.

[9]辛 羽, 黃佳進.基于熵的協同過濾推薦模型[C]//第十屆中國Rough集與軟計算、第四屆中國Web智能、第四屆中國粒計算聯合會議論文集.重慶: 中國計算機學會, 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.