基于稀疏數據預處理的協同過濾推薦算法

陳宗言，顏 俊

(1.南京郵電大學 通信與信息工程學院，江蘇 南京 210003；2.寬帶無線通信與傳感網技術教育部重點實驗室，江蘇 南京 210003)

基于稀疏數據預處理的協同過濾推薦算法

陳宗言1,2，顏 俊1,2

(1.南京郵電大學 通信與信息工程學院，江蘇 南京 210003；2.寬帶無線通信與傳感網技術教育部重點實驗室，江蘇 南京 210003)

隨著推薦系統規模的不斷擴大,用戶-項目評分矩陣呈現出極端稀疏性,導致基于傳統相似性度量方法的協同過濾推薦系統推薦質量的下降。針對該問題,文中提出了一種基于項目特征屬性的稀疏數據集預處理方法來提高算法的推薦質量。首先,通過引入項目的特征屬性信息,根據項目間特征屬性相似度,初步預測用戶對未評分項目的評分,可以使得用戶-項目評分矩陣完全飽和。接著再對稀疏數據集的未評分項目進行混合填充預處理,避免了傳統均值填充法中的用戶對項目的評分不可能完全相同的問題以及眾數填充法中的“多眾數”和“無眾數”問題。實驗結果表明,文中提出的方法更能有效地提高推薦系統的推薦質量和推薦覆蓋率。

推薦系統；協同過濾；特征屬性；稀疏數據集；混合填充

1 概 述

隨著信息技術和互聯網的發展，人們逐漸從信息匱乏的時代步入了信息過剩的時代。在這個時代里，無論是信息的生產者或信息的消費者都面臨著巨大挑戰：作為信息生產者，如何讓自己的信息脫穎而出，受到廣大用戶的關注，是一件非常困難的事情；作為信息消費者，如何從海量的信息中找到自己感興趣的信息也是一件非常復雜的事情。因此，推薦系統成為互聯網技術研究的一個熱點。

推薦系統的任務就是聯系用戶和信息，一方面幫助用戶發現對自己有價值的信息，另一方面讓信息能夠展現在對它感興趣的用戶面前[1]。

為使推薦系統產生精確的推薦，保證推薦系統的實時性和有效性，研究人員提出了各式各樣的推薦算法。文獻[2-4]提出了通過對用戶(項目)進行聚類分析來進行個性化推薦的方法，該方法可以有效提高推薦系統的響應速度，但其推薦精度并沒有顯著改善；文獻[5]通過對用戶購買的商品進行關聯分析，發掘商品間關聯度并產生推薦，但在關聯過程中會產生較多的候選項目集，輸入輸出負載較大；文獻[6]提出了分類算法，通過對用戶(項目)進行分類，進而產生分類推薦，可以有效提高推薦的準確率；文獻[7-8]提出了協同過濾推薦算法，通過對用戶的歷史興趣進行分析，根據得到的預測結果為用戶提供推薦，顯著提高了推薦的精確性，并且其算法模型簡單、數據采集方便。

鑒于協同過濾算法在推薦系統方面體現出的巨大優勢，文中重點討論基于項目(Item-Based)的協同過濾推薦算法[9]。

協同過濾推薦主要有兩大類：基于模型的方法[10]和基于記憶的方法[11]。基于模型的方法通過系統已有的用戶-商品信息學習并產生一個模型，從而根據得到的模型進行預測推薦；基于記憶的方法主要通過計算用戶(項目)間的相關性，根據算法所設定的鄰居個數，尋找目標用戶(項目)的最近鄰，這些最近鄰居可由目標項目與其他項目相似值從高到低排列所得，并通過最近鄰為用戶(項目)進行推薦。

迄今為止，協同過濾技術在電子商務發展中得到了廣泛應用。以亞馬遜為代表的電子商務公司通過對目標用戶的歷史購買記錄進行分析，進而產生個性化推薦。據VentureBeat統計，亞馬遜公司每年至少有35%的銷售來自于推薦算法。著名視頻網站Netflix通過對用戶的歷史觀看記錄的分析，得到用戶的個人觀影喜好，進而為用戶推薦相似的電影。

但是，隨著推薦系統規模的不斷擴大，用戶評分數據呈現出極端的稀疏性，比如：在大型商務系統中，用戶評分的項目一般不會超過項目總和的1%[12]。研究發現，協同過濾技術在對由用戶歷史信息得到的用戶-項目評分矩陣進行用戶(項目)相似度計算時，得到的結果不能讓人滿意。比如：一個用戶由于是新用戶或者其做出評分的項目過少，可能會導致該用戶和其他用戶之間的相似度無法計算，從而不能做出有效推薦，導致推薦算法精確度的下降。

針對上述問題，文獻[13-14]提出了相似性度量方法的優化算法，但由于其在計算項目(用戶)相似性時仍然是基于稀疏數據集，所以性能仍然提高不大。因此，在大型商務系統中，基于稀疏數據集的協同過濾推薦算法的相似度計算已經成為制約推薦系統性能的一個關鍵因素，如何在計算相似度之前對稀疏的數據集進行合適的處理則成為提高推薦效率的一個關鍵。

為此，文中提出了一種基于項目特征屬性的數據預處理技術。主要貢獻有以下兩點：

(1)通過引入項目的特征屬性信息，根據項目間特征屬性相似度，初步預測用戶對未評分項目的評分，再對稀疏數據集的未評分項目進行混合填充預處理，可以使得用戶-項目評分矩陣完全飽和。

(2)有效避免了文獻[15]所提出的均值填充法中的用戶對不同項目評分不可能完全一致以及眾數填充法中“多眾數”和“無眾數”的問題。

實驗結果表明，相對于對稀疏數據集的缺失項不進行填充和使用“眾數填充”的方法，文中所提方法更能有效地提高推薦系統的推薦質量和推薦的覆蓋率。

2 相關工作

目前，學術界對推薦算法的相似性度量和稀疏數據集的預處理已經開展了很多研究工作。

相似性的度量方法主要有三種：Pearson相關相似性、余弦相似性以及修正的余弦相似性。鑒于修正的余弦相似性原理與余弦相似性相同，只是公式上的略微變化，這里不做詳細介紹。前兩種方法的計算公式如下：

(1)

余弦相似性：項目所得評分被看做是n維用戶空間上的向量，如果用戶對項目沒有進行評分，則將該用戶對項目的評分設為0，項目間的相似性通過向量間的余弦夾角度量：

(2)

這兩種相似性方法可以有效計算用戶(項目)間的相似度，但如前文所述，如果一個用戶由于是新用戶或者其做出評分的項目過少，使得該用戶和其他用戶之間沒有共同的項，導致該用戶和其他用戶之間的相似度無法計算。因此，針對這種由用戶-項目評分矩陣極度稀疏引起的問題，研究人員又提出了各式各樣對稀疏數據集進行預處理的方法。

文獻[16-18]提出通過奇異值分解(SVD)算法估計未評分項目的評分來填充用戶-項目矩陣，奇異值分解在用戶-項目矩陣較為稠密的情況下會取得較高的準確度，在數據極度稀疏情況下，預測效果并不是很理想。文獻[19]提出對用戶未評分項目進行均值填充(meanfilling)及眾數填充(modefilling)等方法,但是這種賦予固定值的方法并不是很可信。比如采用眾數法時，利用一組數據中出現頻率最高的數來填充缺失值，會出現“多眾數”和“無眾數”的問題。采用均值法時，對用戶未評分的項目賦予項目或用戶的評分均值，同樣也存在用戶對項目的評分不可能完全相同的問題。更為重要的是，采用現有的相似度計算方法對此填充矩陣進行項目(用戶)相似度計算時，所得結果的可信度不高。

用戶-項目矩陣如表1所示。

表1 用戶-項目矩陣

如果對缺失項不進行填充或者采用平均值填充的方法，在使用相關相似度計算公式計算項目間相關性時(如式(1)所示)，會發現item2和其他項目的相關性無法計算(分子分母同時為0)。

在使用余弦相似性計算方法時(如式(2)所示)，將用戶未評分的項目假設為0，會發現item3與item4相似度恒為1,然而item3與item4的實際所得評分差距還是很大的。

所以，基于以上兩種的填充方法都不能得到令人滿意的效果。

3 文中方法

3.1 方法思路

針對現有的預處理方法在處理稀疏數據集時往往只是利用已有的用戶評分數據進行簡單的填充，卻沒有利用數據自身特征屬性的問題，文中所提方法充分利用特征屬性隱含的潛在價值，從相似度計算和填充方法這兩個角度出發，提出了基于項目特征屬性的稀疏數據預處理的混合填充預處理方法，具體包括項目特征屬性相似度計算和數據混合填充兩個步驟。

在任何商務領域，任意項目往往可以用若干個特征屬性來表示：電影可以通過戰爭、喜劇、文藝等屬性進行分類；商品則可以通過電器、食物、書籍等屬性進行分類。這些屬性信息可以從項目所屬的網頁或者推薦系統中用來記錄項目信息的數據集里抽取得到。

對此，為充分利用項目的特征屬性以及避免均值填充法和眾數填充法所帶來的問題，文中提出了一種新的數據填充方法，即結合項目自身的特征屬性，利用從這些屬性計算中所獲得的未評分項目的預測值結合項目均值對稀疏矩陣中未評分項進行混合填充(hybrid filling)。實驗結果表明，該混合填充方法無論是在預測精度或者推薦項目的覆蓋率方面，相對上述兩種方法，都有明顯的改善。

3.2 方法描述及流程

方法步驟如下所示：

(1)根據提取到的項目特征屬性信息，建立如表2的項目-特征屬性矩陣I-F。

(2)對不同的特征屬性賦予不同的權值，利用式(2)計算項目間特征屬性相似度，得到項目屬性相似度矩陣simf。

假設項目特征屬性矩陣如表2所示。其中，0表示項目不具有某項屬性，1表示項目具有某項屬性。

表2 項目特征屬性矩陣

(3)選取一定的閾值。得到滿足閾值的目標項目i的相似項目，進而得到用戶u在用戶-項目評分矩陣中已評分的數據集合R以及對應的特征屬性相似度值集合W。

由于每個項目是多標簽的，幾乎項目間都具有較強的相關性，所以閾值的選定對于稀疏數據集的填充很關鍵。文中閾值選取0.9，只有相似度值大于0.9的項目才能作為目標項目i的相似項目。

(4)計算未評分項目的預測評分。

由第三步可以得到所有未評分項目在用戶-項目矩陣中的評分數據集，通過式(3)計算出每個未評分項目的預測評分。其中，ru,j∈R，wi,j∈W。

(3)

(5)結合項目平均值，對稀疏數據集中的未評分項目進行混合填充。

由于用戶-項目數據集的極度稀疏性，可能獲取的目標項目i的相似項目的已評分值集合R是空集。對此，采用評分均值來填充，得到用戶u對項目i的評分，如式(4)所示：

(4)

最終，可以得到一個完整的用戶-項目評分矩陣U-I，再對矩陣U-I使用式(1)計算項目間的相關性，得到項目評分相似度矩陣simr，再將simr與simf組合后的相似性作為項目i，j的最終相似性。組合如公式(5)所示：

(5)

(6)

最終，可以得到對用戶u的所有項目的預測評分，并對預測評分進行排序，選擇分值較高且用戶實際未評分的項目向用戶進行推薦。

4 實 驗

4.1 數據集及實驗環境

文中實驗數據采用的是Minnesota大學(美國)提供的Movielens數據集[20]，其中包含了943名用戶對1 682部電影的100 000條評分數據，其數據稀疏度為0.94。該數據集已經在推薦系統中得到了廣泛的使用和測評。

Movielens數據集一共有三個數據集合：電影的屬性描述集合、評分用戶的個人信息集合以及用戶對電影的評分集合。文中用到了第一和第三個集合。電影的屬性描述集合記錄了電影的名稱、發行日期、電影所屬類別(喜劇、戰爭等)。文中所用到的特征屬性可以從這個集合中提取。用戶對電影的評分集合記錄了用戶對電影的評分和時間戳。評分分值是從1到5的整數并且每個用戶都評價了至少20部電影，每部電影至少都有一次以上的評價。整個數據集按8∶2的比例分成訓練集和測試集，訓練集數據作為算法輸入，而測試集用于測試改進后的算法性能。

算法的實驗環境：R語言編程軟件Rgui。

4.2 衡量指標

文中主要采用推薦的質量即精度(MAE)和推薦的范圍即覆蓋率(coverage)作為主要衡量指標，并分析了在鄰居個數固定情況下推薦數目對覆蓋率的影響。

(7)

(8)

式中，I代表電影的總數。

4.3 實驗結果及分析

為了檢驗文中算法的有效性，將混合填充方法和傳統的對未評分項不進行填充(non filling)以及對未評分項進行眾數填充(mode filling)的方法作比較。由于式(5)中的w為設定的用于調節項目相似性的平衡參數，所以w的取值對系統的推薦精度有影響。先計算在相同鄰居個數下不同w值對兩種算法的MAE值的影響，這里，設定鄰居個數k為10。實驗中w的取值從0.1到1，每次增加0.1，觀察w的變化對推薦系統效率的影響。實驗結果如圖1所示。

圖1 參數w對MAE的影響

從圖中可以看到，當w的取值從0.1到1時，文中提出的hybridfilling所獲得的MAE值遠低于nonfiling以及modefilling。當w取0.9時，三種方法的MAE都取得了最小值。再分析當w取0.9，推薦個數取10時，鄰居個數對推薦系統質量的影響。圖2為鄰居個數k從3增加到18，間隔為3時，三種方法的MAE值。

圖2 鄰居個數k對MAE的影響

由圖2可知，當推薦個數和w取值固定時,鄰居個數k從3增加到18的過程中，文中提出的hybridfilling相比于nonfilling和modefilling均具有最小的MAE值。再分析當w取值固定(0.9)和推薦個數為10時，三種方法的推薦覆蓋率(coverage)，如圖3所示。

由圖3可知，文中方法的推薦覆蓋率相比于其他兩種方法有了明顯的提高。

傳統的對稀疏數據集缺失項不進行填充以及賦予固定缺省值的方法，在數據矩陣極度稀疏的情況下，會使得大部分項目的相似項目無法計算或者都是相同的，故而會影響推薦的覆蓋率，而混合填充方法則主要利用由項目的特征屬性得到的預測值來填充，這會使得為同類型項目推薦更多相似的同類型項目，故而提高了推薦的覆蓋率。

圖3 鄰居個數k對推薦覆蓋率的影響

再分析w、k的取值固定時，推薦個數對推薦覆蓋率的影響(w取0.9，k取10)，結果如表3所示。

表3 推薦個數對推薦覆蓋率的影響 %

從表3可以看出，推薦個數越多，推薦的范圍就越廣，推薦的覆蓋率就越高。故而三種方法的推薦覆蓋率隨著推薦個數的增加而增大。

由上可知，文中所提出的混合填充方法，相比于對缺失項不作填充以及采用“眾數填充”的方法，有效提高了推薦系統的推薦質量和推薦的覆蓋率。

5 結束語

針對協同過濾算法的稀疏性問題，文中給出了一種新的填充方法，即充分利用由項目自身的特征屬性得到的預測值并結合項目均值對稀疏數據集進行混合填充處理，使用戶-項目評分矩陣得以飽和。通過實驗驗證了該方法相比于傳統的對缺失值不作處理以及對缺失值賦予固定缺省值的方法，無論是在推薦精度亦或是推薦的覆蓋率方面都有明顯的改善。下一步的工作將側重于對協同過濾算法進行改進，以提高推薦算法的質量、效率。

[1] 鞏 亮.推薦系統實踐[M].北京:人民郵電出版社,2012.

[2]ConnerM,HerlockerJ.Clusteringitemsforcollaborativefiltering[C]//ProceedingoftheACMSIGIRworkshoponrecommendersystems.[s.l.]:ACM,2001.

[3] 鄧愛林,左子葉,朱揚勇.基于項目聚類的協同過濾推薦算法[J].小型微型計算機系統,2004,25(9):1665-1670.

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

[5]SarwarB,KarypisG,KonstanJ,etal.AnalysisofrecommendationalgorithmsforE-commerce[C]//ProcofthesecondACMconferenceonelectroniccommerce.NewYork:ACMPress,2000:158-167.

[6]LeeJS,JunCH,LeeJ,etal.Classification-basedcollaborativefilteringusingmarketbasketdata[J].ExpertSystemwithApplications,2005,29(3):700-704.

[7]ResnickP,IacovouN,SuchakM,etal.Grouplens:anopenarchitectureforcollaborativefilteringofnetnews[C]//Proceedingofthe1994ACMConferenceoncomputersupportedcooperativework.NewYork,USA:ChapelHillPress,1994:175-186.

[8]BresseJ,HechermanD,KadieC.Empiricalanalysisofpredictivealgorithmsforcollaborativefiltering[C]//Proceedingofthe14thconferenceonuncertaintyinartificialintelligence.[s.l.]:[s.n.],1998:43-52.

[9]LindenG,SmithB,YorkJ.Amazon.comrecommendationsitem-to-itemcollaborativefiltering[J].IEEEInternetComputing,2003,7(1):76-80.

[10]MarlinB.Modelinguserratingprofilesforcollaborativefiltering[C]//Advancesinneuralinformationprocessingsystems.Toronto,Canada:MITPress,2003.

[11]DelgadoJ,IshiiN.Memory-basedweighted-majoritypredictionforrecommendersystems[C]//ProceedingofACMSIGIR’99workshoponrecommendersystems.UC,USA:BerkeleyPress,1999:251-257.

[12]SarwarB,KarypisG,KonstanJ,etal.Item-basedcollaborativefilteringrecommendationalgorithms[C]//Procofthetenthinternationalconferenceonworldwideweb.NewYork:ACMPress,2001:285-295.

[13] 張忠平,郭獻麗.一種優化的基于項目評分預測的協同過濾推薦算法[J].計算機應用研究,2008,25(9):2658-2660.

[14] 徐 翔,王煦法.協同過濾算法中的相似度優化方法[J].計算機工程,2010,36(6):52-54.

[15]DasuT,JohnsonT.Exploratorydatamininganddatacleaning[M].[s.l.]:WileyPress,2003.

[16] 余 剛,王知衍,邵 璐,等.基于奇異值分解的個性化評論推薦[J].電子科技大學學報,2015,44(4):605-610.

[17] 霍淑華,杜永萍,黃 亮,等.融入用戶與物品特征信息的動態RSVD算法[J].山西大學學報:自然科學版,2015,38(1):24-30.

[18] 孫小華,陳 洪,孔繁勝.在協同過濾中結合奇異值分解與最近鄰方法[J].計算機應用研究,2006,23(9):206-208.

[19] 夏建勛,吳 非,謝長生.應用數據填充緩解稀疏問題實現個性化推薦[J].計算機工程與科學,2013,35(5):15-19.

[20]LeeH,KwonJ.SimilarUserclusteringbasedonMovieLensdataset[J].AdvancedScienceandTechnologyLetters,2014,51(8):32-35.

Collaborative Filtering Recommendation Algorithm Based on Sparse Data Pre-processing

CHEN Zong-yan1,2，YAN Jun1,2

(1.College of Communication & Information Engineering，Nanjing University of Posts& Telecommunications，Nanjing 210003，China；2.Key Lab of Broadband Wireless Communication and Sensor Network Technology of Ministry of Education,Nanjing 210003,China)

With the continuous expansion of recommender systems,the sparsity of the user-item matrix can deteriorate the performance of the traditional similarity calculation based collaborative filtering recommendation approaches.In order to overcome this drawback,a new sparse data pre-processing algorithm based on item feature is proposed to mitigate this effect.First,considering the item characteristics information,the ratings of the unrated items are predicted through the similarities between each item.It can lead to saturated matrix and overcome the drawback of the sparsity matrix.Next,the hybrid filling method is utilized to process the unrated items in the sparse data sets,which can avoid the problem of full no consistency of different items for traditional mean-filling method and the multiple mode and no mode for the mode-filling approaches.The simulation demonstrates that the proposed algorithm can improve the recommended quality and coverage dramatically.

recommender system；collaborative filtering；item characteristics；sparse data set；hybrid filling

2015-10-24

2016-01-27

時間：2016-06-22

國家自然科學基金資助項目(61372122)

陳宗言(1991-),男,碩士研究生,研究方向為大數據挖掘；顏 俊,副教授,博士,研究方向為數據挖掘、壓縮感知技術及其應用。

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

TP311

A

1673-629X(2016)07-0059-06

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