改進的面向數據稀疏的協同過濾推薦算法

高 倩,何聚厚

(1.陜西師范大學 計算機科學學院，陜西 西安 710062;2.陜西師范大學 現代教學技術教育部重點實驗室，陜西 西安 710062)

改進的面向數據稀疏的協同過濾推薦算法

高 倩1,何聚厚2

(1.陜西師范大學 計算機科學學院，陜西 西安 710062;2.陜西師范大學 現代教學技術教育部重點實驗室，陜西 西安 710062)

用戶相似性和最近鄰集合是協同過濾算法中最重要的兩個步驟。傳統的協同過濾算法依靠用戶評分計算用戶相似性并尋找K個鄰居作為最近鄰的方法為用戶產生推薦，但是在數據稀疏的情況下，僅僅依靠用戶評分使得推薦效果不準確。針對以上問題，文中提出一種改進的面向數據稀疏的協同過濾推薦算法。該方法引入用戶屬性相似性和用戶興趣度相似性，并結合傳統的用戶評分相似性計算用戶間的相似度，通過多次實驗調整三者的權重，并且采用動態選取鄰居集合的方法確定用戶的最近鄰，從而為用戶推薦最合適的項目，增強了方法實用性，以此來緩解用戶數據稀疏性問題。實驗結果表明，文中方法能夠充分利用用戶的各類數據信息，提高了預測評分的準確性及推薦質量。

用戶相似性；屬性；興趣；動態；數據稀疏性

0 引 言

在互聯網越來越流行的今天，各種信息充斥著人們的生活。推薦系統隨之產生，旨在幫助人們找到最有用的信息。基于用戶的協同過濾推薦是在信息過濾和信息系統中一項很受歡迎的技術。其基本思想是根據用戶-項目評分矩陣中已有的評分值，計算用戶間的相似度，為目標用戶或項目尋找最近鄰，從而對未知的評分值進行估計[1]。由此可見，用戶的相似度計算方法和鄰居集的構造，對提高協同過濾推薦算法的推薦精度影響很大。目前的大部分協同過濾推薦算法，主要分為基于用戶的協同過濾(User-Based CF)[2]、基于物品的協同過濾(Item-Based CF)[3]。然而不管是哪種方法，隨著用戶和項目數量的增多，都依然存在數據稀疏性問題，這種問題會導致推薦精度降低。

為此，文獻[4]提出將Jaccard相似系數與傳統的相似性方法結合起來計算用戶之間的相似性，彌補了稀疏狀況下的不足，但它依然只考慮了用戶評分；文獻[5]提出將用戶興趣相似性與傳統的相似性方法相結合來計算用戶間相似性，從兩方面考慮了用戶間的相似性，在一定程度上提高了推薦質量，但效果不明顯；文獻[6]提出了基于降維技術如奇異值分解(SVD)來解決數據稀疏性問題。該方法采用將用戶-項目評分矩陣中無意義的評分刪除的方法對矩陣降維，但是對奇異值分解過程很難控制；文獻[7]提出綜合項目評分相似性和項目分類相似性的方法，但推薦系統數據稀疏問題依然有待改善。

針對以上問題，文中考慮到用戶選擇商品與用戶的屬性特征和興趣有很大關系，如用戶的年齡、職業，興趣等。提出一種新的相似性度量方法。引入用戶屬性相似度和用戶興趣相似度，并和用戶評分相似度相結合，有效地改善了數據稀疏情況下的推薦質量。

1 改進的User-based協同過濾推薦算法

在推薦系統中，用戶對所有產品的評價數據集包含用戶集合U={U1,U2,…,Us}和項目集合I={I1,I2,…,It}，用戶對項目的所有評分取值構成了用戶-項目評分矩陣R，例如用戶Ux對項目Iy評分為Rxy。

1.1 用戶相似度的改進

相似度計算是影響推薦質量的重要技術。傳統的相似度計算方法[8]主要包括：余弦相似性、相關相似性和修正余弦相似性。通過在MovieLens[9]數據集上多次實驗，發現修正余弦相似性的效果最好。因此文中算法是在修正余弦相似性的基礎上，結合用戶屬性和用戶興趣度進行改進的。

1.1.1 用戶評分相似性

由于用戶對項目的評分是最直接反映用戶對項目喜好程度的指標，所以實驗采用修正余弦相似性對用戶間評分相似性進行計算。用戶間的評分相似性simr(x,y)為：

simr(x,y)=

(1)

1.1.2 用戶屬性相似性

用戶數量較多的時候，并不是每個用戶都會對項目有評分，即數據稀疏的情況下，僅使用項目評分來判斷用戶的相似性未免過單一。由于每個用戶都包含一定的屬性，包括性別、職業、地址、年齡等，在選擇項目時，這些屬性對用戶的選擇和喜好會有一定的影響。

假設用戶的屬性特征個數為n，則用戶x的屬性特征集合為Cx={Cx1,Cx2,…,Cxn}，其中Cxn表示用戶x的第n個屬性特征。然后，要對用戶的屬性特征進行量化。例如，對用戶的性別進行量化：性別為男的量化值為1，性別為女的量化值為0；對年齡進行量化：量化值為0～9，其中，令0～10歲=0，10～20歲=1等等。最后將所有用戶的屬性特征進行量化后就構成了用戶-屬性矩陣[10]。由上述得出的用戶屬性矩陣C表示為：

其中：s行代表s個用戶；n列代表每個用戶有n個屬性；Cxa代表用戶x的第a個屬性量化值。

假設用戶x和用戶y的第a個屬性值相同，認為Cxa∩Cya=1,否則Cxa∩Cya=0。則用戶x和用戶y的屬性相似度simc(x,y)[11]為：

simc(x,y)=α*Cx1∩Cy1+β*Cx2∩Cy2+…+γ*Cxn∩Cyn

(2)

其中，α,β,…,γ為權重因子，并且α+β+…+γ=1。

1.1.3 用戶興趣相似性

一般來說，某一類項目被用戶評價的次數越多，證明用戶對這類項目越感興趣。假設項目種類數目為x，由用戶-項目評分矩陣可計算得出用戶-項目種類評分數目矩陣N：

其中：s行代表用戶數目；k列代表項目種類數；Nsk代表用戶s評價過k類項目的數目。

實驗中設定k=19，即19種不同的項目種類。

用戶對某類項目的興趣度可表示為：

(3)

其中：Nxi表示用戶x對a類項目的評價總數；Nx表示用戶x的評價總數。

則兩個用戶的興趣相似度[5]為：

(4)

其中：n為項目的種類數；Ixa表示用戶x對a類項目的興趣度。

1.1.4 用戶整體相似性

實驗采用用戶評分相似度、用戶屬性相似度和用戶興趣相似度結合的方法得到用戶間整體相似度，即：

sim(x,y)=μ*simr(s,y)+ρ*simc(x,y)+τ*simn(x,y)

(5)

其中，μ，ρ，τ分別為權重因子，μ+ρ+τ=1。

1.2 最近鄰選取

傳統的協同過濾算法選取k個鄰居用戶組成最近鄰集合，但是在數據稀疏的情況下，可能并沒有k個與目標用戶很相似的鄰居，這樣就會產生不準確的最近鄰集合，因此會導致推薦結果的不準確。

定義1 鄰居候選集合C給定推薦目標用戶Ux，如果評分矩陣中?Ux∈U，使得Rx∩Ry≠?，那么用戶y就為目標用戶x的候選用戶，候選集合Cx表示為：

實驗采用動態選取鄰居集合的方法，在為目標用戶x選取最近鄰的過程中，需要選定一個相似度閾值[12]simε(x),表示為：

(6)

其中：sim(x,y)表示目標用戶x與候選用戶y的相似度；Cx表示目標用戶x的候選集合。

因此，目標用戶x的最近鄰集合表示為：

Sx={y|sim(x,y)>simε(x),y∈Cx}

(7)

1.3 產生推薦

通過文中提出的相似度改進方法，結合動態選取最近鄰集合，根據式(5)可計算出用戶間的相似度，根據式(7)可得出目標用戶的最近鄰集合，進而產生推薦。具體過程如下：

輸入：用戶-項目評分矩陣、用戶屬性矩陣、項目屬性矩陣；

輸出：推薦項目集。

Step1：根據用戶評分矩陣和項目屬性矩陣，計算得出用戶-項目種類評分數目矩陣N。

Step2：計算用戶相似度矩陣。分別用式(1)、式(2)和式(4)計算出用戶評分相似度、用戶屬性相似度和用戶興趣相似度，選取一定的權重因子，根據式(5)，計算出用戶相似度矩陣sim。

Step3：最近鄰選取。采用動態選取鄰居集合的方法，根據式(7)，找出目標用戶的最近鄰集合S。

Step4：產生推薦。根據用戶評分矩陣R，目標用戶的最近鄰集合S，可計算出目標用戶x對目標項目a的預測評分[13]Pxa：

(8)

2 實驗設計與分析

2.1 數據集

選取的數據集為MovieLens數據集,其中包含三種規模的數據集，每種規模都包含用戶評分數據、用戶信息數據以及電影的屬性數據。參數如表1所示。

表1 三種規模數據集

實驗選擇用戶數為943的數據集，其中一個用戶至少對20部電影進行了評價，評分范圍為[1,5]，然后將數據集分成了80%的訓練集和20%的測試集。

2.2 度量標準

實驗采用平均絕對偏差(MAE)作為度量標準，MAE越小說明評價質量越高。MAE[3]的計算公式為：

(9)

其中：Pi表示用戶預測評分；Qi表示用戶實際評分；N表示總的評分數目。

2.3 實驗結果

2.3.1 用戶屬性相似性的權重因子的測定

根據MovieLens提供的用戶屬性信息，提取用戶的性別、年齡、職業、郵編四種信息進行量化，將量化后的用戶屬性矩陣加入到實驗中，判斷各特征屬性的重要性。此時用戶相似性使用單一的用戶屬性相似性，結果如圖1所示。

圖1 各屬性對MAE值的影響

由圖1可以看出，性別屬性對預測結果影響最大，其次分別是年齡、職業、郵編。經過反復實驗，具體的權重因子設定如表2所示。

表2 權重因子設定

2.3.2 各相似性權重因子的測定

將用戶評分相似性矩陣、用戶屬性相似性矩陣和用戶興趣度矩陣計算出來之后，需要設定不同的權重來表示它們的重要程度，結果如圖2所示。

圖2 三種相似度對MAE的影響

由圖2可以看出，用戶興趣度相似性對預測結果影響最大，其次是用戶屬性相似性和用戶評分相似性。經過反復實驗，將用戶興趣度相似性的權重設定為0.55，用戶評分相似性設定為0.15，用戶屬性相似性設定為0.3，這樣可以使預測結果MAE達到最小。

為了檢驗文中實驗的有效性，采用傳統的基于用戶的協同過濾推薦算法(UCF)和文獻[5]提出的方法作為對照，鄰居個數從5開始遞增到30，間隔為5，然后與文中提出的方法進行對比。實驗結果見圖3。

圖3 三種推薦效果對比

從圖3可以看出，在鄰居個數不同的情況下，文中提出的算法相比UCF和文獻[5]提出的方法，都能取得更好的推薦質量。并且不會受到鄰居個數的影響，從而具有更好的通用性。

3 結束語

文中提出的方法與傳統的協同過濾算法最大的不同在于，考慮到數據稀疏情況下，用戶評分相似性的不準確，從而加入用戶屬性相似性和用戶興趣相似性，并且采用動態選取鄰居集合的方法，避免了沒有推薦能力的用戶加入到最近鄰集合中，有效地改善了用戶評分稀疏的不足。實驗結果表明，該方法具有一定的改進效果。

[1] 桑治平,何聚厚.基于Hadoop的多特征協同過濾算法研究[J].計算機應用研究,2014,31(12):3621-3624.

[2] Resnick P,Iacovou N,Suchak M,et al.GroupLens:an open architecture for collaborative filtering of netnews[C]//Proceedings of the 1994 ACM conference on computer supported cooperative work.[s.l.]:ACM,1994:175-186.

[3] Sarwar B,Karypis G,Konstan J,et al.Item-based collaborative filtering recommendation algorithms[C]//Proceedings of the 10th international conference on World Wide Web.[s.l.]:ACM,2001:285-295.

[4] Adomavicius G, Tuzhilin A. Towards the next generation of recommender systems:a survey of the state-of-the-art and possible extensions[J].IEEE Transactions on Knowledge and Data Engineering,2005,17(6):734-749.

[5] 嵇曉聲,劉宴兵,羅來明.協同過濾中基于用戶興趣度的相似性度量方法[J].計算機應用,2010,30(10):2618-2620.

[6] Billsus D,Pazzani M.Learning collaborative information filters[C]//Proceedings of the 15th international conference on machine learning.[s.l.]:[s.n.],1998.

[7] Zhou K.Combining item rating similarity and item classification similarity for better recommendation quality[J].Advanced Materials Research,2012,461:289-292.

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

[9] Miller B N,Albert I,Lam S K,et al.MovieLens unplugged:experiences with occasionally connected recommender system[C]//Proceedings of the 8th international conference on intelligent user interfaces.New York:ACM,2003:263-266.

[10] 劉 聰,張 璇,王黎霞,等.改進的基于用戶數據的協同過濾推薦方法[J].計算機應用與軟件,2014,31(8):245-248.

[11] 李鵬飛,吳為民.基于混合模型推薦算法的優化[J].計算機科學,2014,41(2):68-71.

[12] 黃創光,印 鑒,汪 靜,等.不確定近鄰的協同過濾推薦算法[J].計算機學報,2010,33(8):1369-1377.

[13] 許海玲,吳 瀟,李曉東,等.互聯網推薦系統比較研究[J].軟件學報,2009,20(2):350-362.

An Improved Collaborative Filtering Recommendation Algorithm for Data Sparsity

GAO Qian1,HE Ju-hou2

(1.School of Computer Science,Shaanxi Normal University,Xi’ an 710062,China;2.Key Laboratory of Modern Teaching Technology of Ministry of Education,Shaanxi Normal University,Xi’ an 710062,China)

User similarity and nearest neighbor set is two important steps in acollaborative filtering algorithm.The traditional Collaborative Filtering (CF) computes user similarity only relying on user rating and findsKneighborsasnearestneighbortoproducerecommendationforusers,butinthecaseofsparsedata,onlyrelyingonuserratingcalculationmakestherecommendationeffectinaccurate.Tosolvetheproblems,animprovedcollaborativefilteringrecommendationalgorithmfordatasparsityisproposed,whichintroducesthesimilarityofuserattributesanduserinterest,combinedwithtraditionaluserratingsimilaritytocomputesimilaritybetweenusers.Theweightsofthreeisadjustedthroughseveralexperiments,andthedynamicmethodisusedtosearchtheuser’snearestneighbortorecommendsuitableitemsforusers,inordertoalleviateuserdatasparsityproblem.Experimentalresultsshowthatthismethodcanmakefulluseofallkindsofusers’datainformation,improvingtheaccuracyofpredictedratingsandqualityofrecommendation.

user similarity;attribute;interest;dynamic;data sparsity

2015-06-28

2015-09-30

時間：2016-02-18

中央高校基本科研業務費專項資金資助項目(GK201002028，GK201101001);陜西師范大學學習科學交叉學科培育計劃資助項目

高 倩(1990-)，女，碩士研究生，研究方向為知識工程與智能教學系統；何聚厚,博士,副教授,研究方向為知識工程與智能系統。

http://www.cnki.net/kcms/detail/61.1450.TP.20160218.1636.074.html

TP

A

1673-629X(2016)03-0063-04

10.3969/j.issn.1673-629X.2016.03.015