融合信息熵與興趣度的協同過濾算法

石 坤 余 強 朱秋月

(西華大學計算機與軟件工程學院 成都 610039)

融合信息熵與興趣度的協同過濾算法

石 坤 余 強 朱秋月

(西華大學計算機與軟件工程學院 成都 610039)

為提高推薦系統的推薦質量,減小用戶評分數據稀疏性對推薦效果的不良影響,提出了一種結合加權信息熵與興趣度的協同過濾推薦算法。此算法全面考慮公共評分項目數、評分數值差異與數值變化趨勢三個方面的因素,結合加權信息熵與用戶興趣度,使度量用戶間相似度變得更加準確。仿真實驗結果表明:所提算法比基于Pearson相關性系數以及余弦相似性的推薦算法具有更小的平均絕對誤差,表明了其可行性和有效性。

協同過濾; 信息熵; 用戶興趣度; Pearson系數

Class Number TP391.3

1 引言

計算機科學技術的不斷進步,特別是互聯網的快速發展,加速了大數據時代的到來。面對互聯網上的海量信息,用戶從中得到自身所需的信息變得愈發困難,即信息過載。目前,解決信息過載[1]的技術主要為兩類,一類是信息檢索技術,其典型的代表為搜索引擎技術,另一類是信息過濾技術,其代表為推薦系統。推薦系統中推薦算法是其核心部分,其性能的好壞直接決定了推薦系統的推薦質量。協同過濾是推薦算法中應用最成功的推薦方法之一,它推動了推薦系統研究的快速發展[2]。協同過濾主要分為基于模型的算法和基于記憶的算法,基于模型的算法關鍵是建立預測用戶的推薦模型,算法比較復雜,時間開銷較大,所以后者的使用更為廣泛[3]。基于記憶的算法直接利用用戶的評分數據進行相似性的度量,產生推薦結果,其關鍵是相似度度量,而實際的應用場景中,評分矩陣非常稀疏,這直接導致了準確度量相似度的困難。

為了盡量消除相似度計算中由數據稀疏性所帶來的影響,Zeng等[4]提出了精選實例的方法,該方法不需要掃描整個數據集,能夠縮小鄰居搜索的范圍。Jiang等[5]將在線評論作為輔助信息初步估計出未知的評分用以降低評分矩陣的稀疏程度。這些方法都是通過降低矩陣的稀疏程度來減小稀疏性在相似度計算中的影響。此外,Yang等[6]利用社交網絡中朋友之間的查詢概率構建貝葉斯網絡應對數據的稀疏性。Massa等[7～8]將信任網絡引入用戶相似性的計算方法中,部分解決了稀疏性問題。這類方法則是直接改變相似度的計算方式來減小稀疏性的影響。

本文考慮了推薦系統中數據的稀疏性對相似度計算的準確度的影響,將用戶興趣度引入到協同過濾算法中,結合加權信息熵的相似度計算方法,讓目標用戶取得更好的最近鄰居集。從降低矩陣的稀疏程度和改變相似度的計算方式兩個方面降低稀疏性的影響,并克服傳統相似度計算不準確的問題,從而提高推薦系統的性能。

2 傳統推薦算法

傳統的協同過濾推薦算法第一步為獲得用戶評價信息,使用用戶-項目評分矩陣的形式展現出來;第二步計算各個用戶間的相似度,針對目標用戶,找出最近的鄰居集合;第三步預測目標用戶的評分,根據第二步中最近的鄰居集合中的評分來推測目標用戶對未知項目的評分,對預測出的評分進行降序排列,取前N項項目作為推薦列表展現給用戶[9]。

協同過濾算法中最核心的就是相似度的計算,它影響著整個推薦算法的精度。傳統度量相似度的方法有杰卡德系數、余弦相似性系數、調整余弦相似性系數和皮爾遜相關性系數[10]。目標用戶u對項目c的預測評分Pu,c如式(1)所示,選擇一種傳統的相似度計算方法計算出用戶u、v之間的相似度sim(u,v),然后按照其大小降序排列,選擇其中與目標用戶u最為相似的用戶構成鄰居集合K。

(1)

3 加權信息熵相似性計算

3.1 傳統相似性計算方法的局限

傳統的相似性度量方法被廣泛地使用,但卻不能夠準確地度量用戶之間的相似性。其中杰卡德系數考慮到了用戶的公共評分的項目數,但在數據極度稀疏度時,杰卡德系數太小,不能明顯地區分不同用戶[11]。余弦相似度系數或調整余弦相似度系數則單純從評分數值的差異進行用戶間相似性的度量,缺乏對公共評分項目數的考慮。

皮爾遜相關系數不受絕對數值大小的影響,可以準確檢測出數據的變化趨勢。如表1,從評分數值與趨勢上可以直觀地看到User1與User2更為相似,User3的趨勢與User1也相似,但絕對數值卻很低。使用皮爾遜相關系數計算它們之間的相似性User1與User2為0.9827,User1與User3為0.9827,User2與User3為0.9999。可以看到皮爾遜相關系數能有效檢測數據的變化趨勢,對絕對的數值不敏感,但是缺乏對用戶之間的公共評分項目數目與評分絕對數值大小因素的考慮,也會對計算相似度造成誤差。

表1 評分趨勢相近的用戶-項目

表2 各類相似度計算方法的比較

表2中對各種傳統的相似度計算方法進行了比較,√代表某一種方法所能反映的角度,×為其不能反映的角度,可以看到沒有一種方法能夠同時將公共評分項目數、評分數值差異與數值變化趨勢三個方面同時考慮進相似性的計算中,再加之數據的稀疏性的影響,從而造成不能準確地度量用戶之間的相似性,因此提出了基于加權信息熵的相似性計算方法。

3.2 加權信息熵的提出

通過兩個用戶間評分數值之間的差異的信息熵來衡量兩個用戶間的相似程度,信息熵越大則兩個用戶間的差異程度越大,兩個用戶越不相似;反之,信息熵越小,兩個用戶間越相似[12]。一個信息源X的信息熵計算公式如式(2)所示。

(2)其中n表示信息源X中有n個分類,pi表示信息源X中第i種分類出現的概率。信息熵越大表示信息源X的信息越無序,越小信息源X的信息越有序[13]。將兩個用戶的評分差異作為信息源,同時考慮評分差值的頻率分布與評分差值的絕對值大小,提出面向信息熵的相似性計算方法。將用戶u、v的公共評分項目的評分差值進行頻率分析并計算出信息熵,設用戶u、v的公共評分項目數為N,用戶u的評分Ru=(ru1,ru2,…,ruN),用戶v的評分Rv=(rv1,rv2,…,rvN),則兩者的評分差值可以用式(3)表示:

D(u,v)=|Ru-Rv|

(3)

對評分差值D(u,v)進行分類統計,假設有n個分類,其頻率分布用式(4)表示:

F(D(u,v))=(p1,p2,…,pn)

(4)

其中,p1,p2,…,pn表示每一分類的出現頻率,由此,F(D(u,v))的信息熵用式(5)表示:

(5)

由于該計算方式只考慮到了評分差值的頻率分布,相當于只考慮到了評分數值的變化趨勢,而沒有考慮到評分差值的數值大小,因此將|d(pi)|加入式(5)中,得到式(6)。

(6)

其中,|d(pi)|表示分布概率為pi的評分差值。最后,考慮到公共評分項目數,將杰卡德系數計算方式中的公共的評分項目數越多,兩個用戶相似的幾率越大的思想[14]引入到基于信息熵的相似性計算方法中,對其進行加權,形成加權信息熵的相似性計算方法。

simWH(u,v)=simH(u,v)·f(u,v)

(7)

f(u,v)為加權函數,N為用戶u、v的公共評分項目數,N越大,兩個用戶相似的概率越大,即f′(u,v)>0,此外當N增加相同幅度時,絕對數值較小的N對相似性的影響一定比絕對數值較大的N的影響大,即f″(u,v)<0。因此取f(u,v)為式(8):

(8)

其中,為了防止N較小時,f(u,v)增長過快,α的取值范圍為0<α<1。

4 結合興趣度的相似性度量

4.1 興趣相似性的引入

使用加權信息熵計算用戶間的相似性,要求公共評分項目數至少為2才行,否則f(u,v)的值就無意義了,在數據極度稀疏時,公共的評分項目數可能極小,甚至會出現都只有一個公共評分項目的情況,因此引入了用戶興趣度的相似性度量方法。當兩個用戶具有相同或者相近的興趣愛好即都對某一類別的項目給出了較高的評分,可以簡單地認為兩者之間的相似性較高,而且根據各個用戶的興趣進行個性化推薦也是推薦系統的趨勢。設用戶u的興趣度向量為

Interestu=(Iu,1,Iu,2,…,Iu,n)

(9)

Iu,i=wu,i/wu

(10)

其中,Iu,i表示用戶u對第i類別項目的興趣度,wu,i為用戶u評分高于其評分均值的第i類別項目的個數,wu代表評分高于其評分均值的各類項目的總數,使用余弦相似性衡量兩個用戶的興趣度的相似性,計算過程如式(11)所示:

simInterest(u,v)=Cos(Interestu,Interestv)

(11)

興趣度的引入主要是為了從項目類別方面入手,而不再是直接從用戶對單個項目的評分上面計算相似度,間接地降低了矩陣的稀疏程度[15]。將加權信息熵與興趣度相結合,能夠克服傳統相似性計算的缺陷,使得用戶之間的相似度計算更為準確,為目標用戶選擇出更好的鄰居集合。

Sim(u,v)=β·simWH(u,v)+(1-β)·simInterest(u,v)

(12)

其中β為調整參數,取值范圍為0.5≤β<1,加權信息熵相似性計算從數據集的全局考慮,涉及到所有用戶對所有項目的評分;而為了降低計算的復雜度,以及彌補加權信息熵要求公共評分項目數至少為2的缺陷,引入興趣度相似性計算對高于用戶評分均值的評分進行興趣統計。

4.2 算法描述

結合加權信息熵與興趣度的協同過濾算法的具體描述如下:

算法1 結合加權信息熵與興趣度的協同過濾推薦算法

輸入:用戶文件、評分文件、項目文件、參數α、參數β、鄰居個數k、目標用戶u。

輸出:目標用戶u的預測評分列表。

第1步:計算所有用戶的評分均值;

第2步:選取所有用戶的高于其評分均值的項目,形成興趣項目集合F;

第3步:除去用戶u的其余用戶集合為V,計算用戶u與其余用戶的公共評分項目數,形成公共評分數集合R;

第4步:遍歷V并從中取出vi,計算加權信息熵的相似性simWH(u,vi);計算用戶興趣度相似性simInterest(u,vi);計算結合加權信息熵與興趣度的相似性Sim(u,vi);

第5步:選取k個Sim(u,vi)最高的形成最近鄰居集,利用式(1)求出預測評分,形成預測評分列表。

5 實驗與分析

5.1 數據集

實驗數據集來自美國Minnesota大學GroupLens項目組公開的MovieLens數據集。其中有6064個用戶對3900部電影作出的1000209條評分記錄以及用戶與項目本身的基本信息,該數據集的稀疏程度為95.771%,數據非常稀疏。將此數據集隨機分成80%的訓練集與20%的測試集。

5.2 評價指標

協同過濾推薦系統中常用的評價指標是平均絕對誤差值(Mean Absolute Error,MAE),本實驗中使用平均絕對誤差值MAE作為評價指標。假設預測出的評分為{p1,p2,…,pn},與之對應的實際評分為{q1,q2,…,qn},計算MAE的公式如式(13)所示。

(13)

在測試集中使用算法1預測用戶評分,再根據測試集中的實際評分,計算出MAE值的大小,作為檢測推薦效果的指標。

5.3 結果與分析

圖1 不同α對應的加權函數取值

首先確定加權函數中參數α的取值,由于加權函數的目的是為了將杰卡德系數中的公共的評分項目數越多,兩個用戶相似的概率越大的思想引入到相似度的度量中,當0<α<1時,式(8)的部分取值如圖1所示。

由圖1可以看出,α取0.1或0.3時,加權函數曲線取得了更好的變化率,符合引入加權函數的初衷。因此,將之后實驗中的α取為0.1或者0.3。由圖2可以看出,當α取0.3時,加權信息熵的相似性計算方法的MAE曲線效果最佳,所以之后的實驗中的α取為0.3。

圖2 不同α對應的MAE曲線

將Pearson相關性系數、Cosine相似性系數這兩種方法與結合加權信息熵與興趣度的相似性計算方法在β取不同值條件下進行對比。圖3展示了β分別取0.5,0.7,0.9時以及使用Pearson相關系數、Cosine相似性計算時不同的MAE曲線,可知,在不同的參數、不同的鄰居數的情況下,本文所提出的協同過濾算法與傳統的基于皮爾遜相關系數以及余弦相似度系數的協同過濾算法相比,均有較小的MAE值,尤其在β取時0.7最優。因此,結合加權信息熵與興趣度的相似性計算方法可以有效地提高推薦的質量。

圖3 不同β取值實驗結果比對

6 結語

大數據時代加劇了“信息過載”問題,海量的數據使得傳統的相似性度量方法有了局限性。本文在分析比較了傳統的相似性度量方法的缺陷后,提出同時將公共評分項目數、評分數值差異與數值變化趨勢三個因素綜合考慮的加權信息熵并結合用戶興趣度的相似性計算方法,并在不同的參數下進行了實驗,分析比較了該算法的預測準確度。實驗結果表明結合加權信息熵與興趣度的協同過濾推薦算法,降低了數據稀疏對推薦性能的影響,具有良好的推薦效果。

[1] Borchers A, Herlocker J, Konstan J, et al. Ganging up on Information Overload[J]. Computer,1998,31(4):106-108.

[2] Koren Y. Collaborative filtering with temporal dynamics[J]. Communications of the Acm,2010,53(4):89-97.

[3] Breese J S, Heckerman D, Kadie C. Empirical Analysis of Predictive Algorithms for Collaborative Filtering[C]//Fourteenth Conference on Uncertainty in Artificial Intelligence,1998:43-52.

[4] Zeng C, Xing C X, Zhou L Z, et al. Similarity Measure and Instance Selection for Collaborative Filtering[J]. International Journal of Electronic Commerce,2004,8(4):115-129.

[5] Jiang C, Duan R, Jain H K, et al. Hybrid collaborative filtering for high-involvement products: A solution to opinion sparsity and dynamics[J]. Decision Support Systems,2015,79(C):195-208.

[6] Yang X, Guo Y, Liu Y. Bayesian-Inference-Based Recommendation in Online Social Networks[J]. IEEE Transactions on Parallel & Distributed Systems,2013,24(4):642-651.

[7] Massa P, Avesani P. Trust-Aware Collaborative Filtering for Recommender Systems[M]//On the Move to Meaningful Internet Systems 2004: CoopIS, DOA, and ODBASE. Springer Berlin Heidelberg,2004:492-508.

[8] Massa P, Avesani P. Trust Metrics on Controversial Users[J]. International Journal on Semantic Web & Information Systems,2009,3(1):39-64.

[9] Ke J, Hong S. Making recommendations from top-N user-item subgroups[J]. Neurocomputing,2015,165(C):228-237.

[10] Gan M, Jiang R. Improving accuracy and diversity of personalized recommendation through power law adjustments of user similarities[J]. Decision Support Systems,2013,55(3):811-821.

[11] 李婧.融合用戶差異度及信息熵的協同過濾推薦算法[D].西安:西安建筑科技大學,2015. LI jing. Fusion user difference degree and information entropy of collaborative filtering recommendation algorithm[D]. Xi’an: Xi’an University of Architecture and Technology,2015.

[12] Luo Q, Miao X J, Wei Q. Further Research on Collaborative Filtering Algorithm for Sparse Data[J]. Computer Science,2014,41(6):264-268.

[13] Ren K, Qian X. Research on User Similarity Measure Method in Collaborative Filtering Algorithm[J]. Computer Engineering,2015,41(8):18-22.

[14] 杜文剛.基于多屬性評分的協同過濾推薦算法研究[D].沈陽:遼寧大學,2015. DU Wengang. Research on Collaborative Filtering Recommendation Algorithm Based on Multi-attribute Rating[D]. Shengyang: Liaoning University,2015.

[15] 梁天一,梁永全,樊健聰,等.基于用戶興趣模型的協同過濾推薦算法[J].計算機應用與軟件,2014,31(11):260-263. LIANG Tianyi, LIANG Yongquan, FAN Jiancong, et al. Collaborative Filtering Recommendation Algorithm Based on User Interest Model[J]. Computer Applications and Software,2014,31(11):260-263.

A Collaborative Filtering Algorithm of Weighted Information Entropy and Rating of User Interests

SHI Kun YU Qiang ZHU Qiuyue

(School of Computer and Software Engineering, Xihua University, Chengdu 610039)

In order to improve the quality of the recommendation and reduce the negative impacts of sparse user rating data, a new collaborative algorithm is put forward based on weighted information entropy and the rating of user interests. The algorithm considers the number of common rating items,numerical differences and numerical change trend three factors, makes user similarity calculations to be more credible by combining the weighted information entropy with the rating of user interests. The simulation experiment results show that the proposed algorithm is better than the recommendation algorithm based on Pearson correlation and cosine similarity because of smaller Mean Absolute Error(MAE). In conclusion, the new algorithm is feasible and effective.

collaborative filtering, information entropy, user interest, Pearson correlation

2016年8月1日,

2016年9月18日

西華大學研究生創新基金項目(編號:ycjj2015192);四川省科技廳技術創新工程專項(編號:2014ZZ0026)資助。

石坤,男,碩士研究生,研究方向:分布式計算、智能信息處理。余強,男,博士,副教授,研究方向:無線傳感網絡、分布式計算。朱秋月,女,碩士研究生,研究方向:嵌入式系統、無線傳感網絡。

TP391.3

10.3969/j.issn.1672-9722.2017.02.026