基于缺失值迭代預測填充的協同過濾推薦算法

盧　棪　劉應安

(南京林業大學信息科學技術學院　南京　210037)

基于缺失值迭代預測填充的協同過濾推薦算法

盧棪劉應安

(南京林業大學信息科學技術學院南京210037)

摘要推薦系統是目前在電子商務中用的較為廣泛的一種技術。伴隨著數據量的增大,評分矩陣的稀疏性成為了一大難題。對于評分數據較為稀疏的矩陣,提出了一種基于缺失值迭代預測填充的協同過濾算法。這種算法以迭代的方式對評分矩陣填充,直到缺失值個數恒定在某一數值。而在迭代的過程中,每一次用于填充計算的相似度度量又是依據均值填充后的相似度來動態計算的。說明該算法即可以降低數據稀疏性,又提高了用戶相似度計算精度的問題。實驗研究表明,利用該算法能夠提高評分矩陣的密度,并降低了系統的推薦誤差。

關鍵詞推薦系統; 協同過濾; 迭代; 預測; 相似度計算; 缺失值填充; 數據密度

Class NumberTP311

1引言

協同過濾是在電子商務系統中使用非常廣泛的一類推薦算法,其基本思想是在用戶群中找到指定用戶的相似(興趣)用戶,綜合這些相似用戶對某一信息的評價,形成系統對該指定用戶對此信息的喜好程度預測。

隨著電子商務系統的進一步擴大,用戶數目和項目數目日益劇增,這樣就會導致用戶評分的極度稀疏性。在這樣的情況下,系統的推薦質量就會急劇下降。通常,針對推薦系統數據稀疏的問題,有一種最簡單的方法就是對未評分的用戶設定一個為評分域中所有評分的均值的值,這種改進方法可以改善稀疏性并且提高提高推薦系統的推薦精度,但是用戶的主觀評分不可能完全相同,所以此方法在用戶評分數據稀疏的情況下計算相似性還是存在著一定的弊端。目前,已有很多研究者提出了更有效的解決數據稀疏性的方法。文獻[1]提出了一種通過計算項目相似度填充用戶評分矩陣的方法,有效緩解了數據的稀疏性。文獻[3]將奇異值分解技術應用到協同過濾中來,通過降低輸入矩陣的維數來降低數據的稀疏性。文獻[5]提出了基于用戶相似度傳遞的方法來緩解稀疏性。文獻[6]提出了一種解決數據稀疏性的迭代協同過濾算法,該算法根據項目評分的相似性來反復填充評分矩陣,雖然能夠很大程度上改善數據的稀疏性問題,但是卻沒有考慮到項目評分相似性不高,項目本身相似度很高的情況。文獻[7]提出了一種在稀疏數據集中使用巴氏距離計算相似度的方法來提高評分的相似性,但計算巴氏距離較為復雜,而且也沒有改善數據稀疏的問題。文獻[9]提出了一種基于云模型的方法來預測填充矩陣,該算法可以適用于任何數據集并且改善稀疏性,但是巨大的計算開銷還是需要考慮。文獻[10]提出了一種算法,該算法對相似性很高但卻沒有評分的用戶進行評分預測,從而降低稀疏性提高推薦質量。文獻[13]提出了一種基于神經網絡的方法,通過構建B-P神經網絡來填充評分矩陣中的缺失值,充分緩解數據稀疏性問題。但是B-P神經網絡模型的學習成本較大,計算效率的提高需要進一步考慮。文獻[14]提出了一種分布填充的協同過濾算法,該算法首先通過相似度和評分數量都達到一個特定值的用戶作為鄰居用戶,其次通過這些用戶來預測并填充為評分的項目,最后通過填充后的用戶評分矩陣來預測用戶的評分。這種方法能在降低數據稀疏性的同時提高推薦質量。

為了進一步緩解評分矩陣的稀疏性,本文提出了一種基于缺失值迭代預測填充的協同過濾算法,此算法以迭代的方式對評分矩陣填充直到缺失值個數恒定在某一數值。而在迭代的過程中,每一次用于填充計算的相似度度量又是依據均值填充后的相似度來動態計算的。即在降低數據稀疏性的同時又改善了在用戶評分極端稀疏情況下用戶相似性計算準確度的問題。

2協同過濾算法相關概念

2.1相似相關性

2.1.1項目類別相似性

根據文獻[15]可知,通過項目間的類別距離度量項目類別相似性如式(1)所示:

(1)

其中,l(i,j)為返回項目i和j節點到達公共雙親的最長路徑長度,H為項目類別樹的樹高。

2.1.2用戶相似性

設Iuv表示用戶u和用戶v共同評分項目集,則用戶u和v的相似性sim(u,v)如下式:

(2)

通過上述方法可以基于用戶對項目的評分作相似性的判斷。

2.2產生推薦

目標用戶對任意項目i的評分:設目標用戶的最近鄰集合為Nu={vi1,…,vik},u?N,則目標用戶u對項目i的預測評分Pui如下式所示。

(3)

式中,rv和ru分別表示用戶v和u對項目的平均評分值。

3基于缺失值迭代預測填充的協同過濾算法

3.1評分矩陣缺失值的預測及填充

為了有效地解決評分矩陣極端稀疏的情況下相似度可信度不高的問題,本文提出對評分矩陣的缺失值進行預測并填充的方法。

設項目中未評分的缺失值集合為Nup,對任意項目p∈Nuj,使用如下方法預測用戶u對項目p的評分Pu,p。

1) 計算所有項目之間的相似性

對于項目本身而言,存在項目類別的相似性和項目評分的相似性。在計算項目類別的相似性時,考慮到若某個項目可能存在多個類別。為了解決此問題,本文對式(1)的方法進一步改進。如式(4)所示:

(4)

其中,若只存在一個公共父節點,就取最長路徑長度。若存在多個公共父節點,就取距離項目i和j節點最短的公共父節點中最長路徑長度。

故可用式(5)來動態加權計算項目之間的相似性,

(5)

其中,sim(i,j)*是最終加權得出的相似性結果,sim(i,j)是項目評分之間的相似性,s(i,j)是項目類別之間的相似性,simaverage(i,j)是均值填充所計算的項目的相似性,α為權重系數并與simaverage(i,j)有關,具體關聯如式(6)所示

(6)

2) 缺失值的預測

通過上述方法處理后便得到項目之間的相似性,將相似性最高的若干項目作為p的鄰居項目集合。即在整個項目空間中查找與項目p相似度最高的項目集合Kp={I1,I2,…,In},并且sim(p,I1)最高,sim(p,I2)次之,依次類推。

得到Kp后,采用文獻中[4]提出的方法預測用戶u對項目p的評分Pu,p:

(7)

其中,Ru,n表示用戶u對相似度最高的項目集合中項目n的評分,simp,n表示項目p和項目n的相似性。

3) 缺失值的填充

通過上述方法處理后,對整個項目空間中的任意項目的評分Ru,j則可以表示為

圖1　預測值填充流程

經過如上方法后可以對評分矩陣的缺失值進行填充。

具體填充方法如圖1所示。

3.2迭代預測及填充

隨著迭代的次數增加,填充的值可能會趨向某一固定的數值,這樣就導致填充的值失去真實性。故需要引入一個修正值來動態控制填充值的大小。通過用戶屬性的相似度來預測缺失值,并以此預測值為基準來動態的調整迭代后的預測的值。用以下公式進行調整:

(8)

其中,Pcorrrect為修正后的填充值,Piterate為迭代后的填充值,Pproperty為基于用戶屬性的填充值。α則是用來控制修正范圍大小的參數,即當Piterate與Pproperty相差較大時,則修正的范圍較大。反之,當Piterate與Pproperty相差較小時,則修正的范圍較小。并且當Piterate與Pproperty相同時,則說明當前迭代后的填充值為離真實值最接近的填充值。對于系數k的判定,則根據評分制度來判定,則k的大小始終與評分的最大值相同。比如,評分標準為5分制,k就為5,若為3分制,k就為3。

通過上述的方法就能動態的對填充值進行修正。

故加入修正值后的具體迭代方法如圖2所示。

圖2　迭代流程

通過上述方法,可以有效地降低原始評分矩陣的稀疏性,并改善在用戶評分極端稀疏情況下用戶相似性計算準確度的問題。

4實驗結果與分析

4.1數據來源

本文采用MovieLens站點提供的數據集(http://movielens.umn.edu/)。它由美國Minnesota大學計算機科學與工程學院的GroupLens項目組創辦,并且用于接收用戶對電影的評分并提供相應的電影推薦列表。目前,該Web站點的用戶評分的電影超過3500部,用戶已經超過43000人。但實際評分數據的密度為100000/(943*1682)=6.3%,說明此數據是相當稀疏的。我們從用戶評分數據庫中隨機選取了三組數據,每組數據包括150個用戶,1682部電影,并將每組數據進一步劃分為訓練集和測試集。整個數據集的80%作為訓練集,20%作為測試集。

4.2推薦質量的度量標準

評價推薦系統推薦質量的度量標準主要包括統計精度度量方法和決策支持精度度量方法兩類。統計精度度量方法中的平均絕對偏差(Mean Absolute Error,MAE)是最常用的一種推薦質量度量方法,該方法是通過計算預測的用戶評分與實際的用戶評分之間的偏差度量預測的準確性。若MAE越小,則說明推薦質量越高。反之,說明推薦質量越低。

設預測的用戶評分集合表示為{p1,p2,…,pn},對應的實際用戶評分集合為{q1,q2,…,qn},則平均絕對偏差MAE定義為

(9)

4.3實驗結果

為了檢驗本文提出算法的有效性,分別以傳統的基于用戶的協同過濾推薦算法(UBCF),均值填充的協同過濾算法(AFCF)以及本文提出的基于缺失值迭代的協同過濾算法(IFCF)來做比較,計算其MAE值,鄰居個數從5增加到30,間隔為5。實驗結果如圖3～圖5所示。

圖3　不同鄰居數對MAE的影響(數據1)

其中圖3為第一組數據的三種算法的比較,圖4為第二組數據,圖5為第三組數據,可以觀察出當鄰居個數越大時,算法的推薦精度就越好。

5結語

本文通過分析傳統協同過濾面臨的數據稀疏性問題及現有的解決方法,提出了一種基于缺失值迭代預測填充的協同過濾算法。利用項目和用戶的相似性來預測缺失值,并利用迭代的方式來進一步緩解評分矩陣的稀疏性。由于每一次都是基于上一次填充后的矩陣進行迭代,因此也改善了在用戶評分極端稀疏情況下用戶相似性計算準確度的問題。實驗結果表明,基于缺失值迭代預測填充的協同過濾算法可以有效的解決用戶評分數據的稀疏性問題,提高推薦的準確度。

圖4　不同鄰居數對MAE的影響(數據2)

圖5　不同鄰居數對MAE的影響(數據3)

參 考 文 獻

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

DENG Ailing, ZHU Yangyong, SHI Bole. Collaborative filtering recommendation algorithm based on item score prediction[J]. Journal of Software,2003,14(9):1621-1628.

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

DENG Ailing, ZUO Ziye, ZHU Yangyong. Collaborative filtering recommendation algorithm based on item clustering[J]. Journal of Chinese Computer Systems,2004,25(9):1665-1670.

[3] Sarwar BM, Karypis, Konstan JA, Riedl J. Application of dimensionality reduction in recommender system-A case study[C]//ACM WebKDD 2000 Workshop,2000:80-90.

[4] Sarwar B, Karypis, Konstan J, Riedl J. Item-Based collaborative filtering recommendation algorithms[C]//Proceedings of the 10thInternational World Wide Web Conference,2001:285-295.

[5] HUETE J F, FEMANDEZ-LUNA J M, De CAMPOS L M, et al. Using past-prediction accuracy in recommender systems[J]. Information Science: an International Journal,2012,199(9):78-92.

[6] Zhuo Zhang, Paul Cuff, Sanjeev Kulkarni. Iterative collaborative filtering for recommender systems with sparse data[C]//2012 IEEE International Workshop On Machine Learning For Signal Process,2012,SEPT:23-26.

[7] Bidyut Kr. Patra, Raimo Launonen, Ville Ollikainen, et al. A new similarity measure using Bhattacharyya coefficient for collaborative filtering in sparse data[J]. Knowledge-Based Systems,2015,82:163-177.

[8] Mohsen Ramezani, Parham Moradi, Fardin Akhlaghian. A pattern mining approach to enhance the accuracy of collaborative filtering in sparse data domains[J]. Physica A,2014,408:72-84.

[9] 張光衛,李德毅,李鵬,等.預計云模型的協同過濾算法[J].軟件學報,2007,18(10):2403-2411.ZHANG Guangwei, LI Deyi, LI Peng, et al. Cloud model based collaborative filtering algorithm[J]. Journal of Software,2007,18(10):2403-2411.

[10] 張學勝.面向數據稀疏的協同過濾推薦算法研究[D].合肥:中國科技大學,2011.

ZHANG Xuesheng. Research on Collaborative Filtering Recommendation Algorithm Based on data sparse[D]. Hefei: University of Science and Technology of China,2011.

[11] 楊炎.基于項目聚類的協同過濾推薦算法的研究[D].吉林:東北師范大學,2005.

YANG Yan. Research on Collaborative Filtering Recommendation Algorithm Based on item clustering[D]. Jilin: Northeast Normal University,2005.

[12] 李濤,王建東,葉飛躍,等.一種基于用戶聚類的協同過濾推薦算法[J].系統工程與電子技術,2007,29(7):1176-1182.

LI Tao, WANG Jiandong, YE Feiyue, et al. Collaborative filtering recommendation algorithm based on user clustering[J]. Systems Engineering and Electronics,2007,29(7):1176-1182.

[13] 張鋒,常學友.使用BP神經網絡緩解協同過濾推薦算法的稀疏性問題[J].計算機研究與發展,2006,43(4):667-672.

ZHANG Feng, CHANG Xueyou. Sparsity problem of collaborative filtering recommendation algorithm based on BP neural network[J]. Computer Research and Development,2006,43(4):667-672.

[14] 張玉芳,代金龍,熊忠陽.分步填充緩解數據稀疏性的協同過濾算法[J].計算機應用研究,2013,30(9):2603-2605.

ZHANG Yufang, DAI Jinglong, XIONG Zhongyang. Collaborative filtering algorithm for sparse data filtering by step filling[J]. Application Research of Computers,2013,30(9):2603-2605.

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

HUANG Chuangguang, YIN Jian, WANG Jing. Collaborative filtering algorithm for uncertain nearest neighbor[J]. Chinese Journal of Computers,2010,33(8):1369-1377.

[16] Sarwar B, Karypis G, Konstan J, et al. Analysis of recommendation algorithm for E-commerce[C]//Proc. Of the 2ndACM Conference on Electronic Commerce. New York: ACMPress,2000:158-167.

[17] 吳一帆,王浩然.結合用戶背景信息的協同過濾推薦算法[J].計算機應用,2008,28(11):2973-2975.WU Yifan, WANG Haoran. Collaborative filtering recommendation algorithm based on user background information[J]. Computer Application,2008,28(11):2973-2975.

[18] 黃霞,韋素云,業寧,等.基于用戶屬性和項目類別的協同過濾算法[J].計算機與數字工程,2012,40(10):5-8.

HUANG Xia, WEI Suyun, YE Ning, et al. Collaborative filtering algorithm based on user attributes and item categories[J]. Computer & Digital Engineering,2012,40(10):5-8.

[19] STOLCK A, ZHENG Jing, WANG Wen, et al. SRILM at sixteen:update and outlook[C]//Proc of IEEE Workshop on Speech Hecognition and UnderStanding,2011.

A Collaborative Filtering Algorithm Based on Predicting and Filling Missing-Data by Iterated

LU YanLIU Ying’an

(College of Information Science and Technology, Nanjing Forestry University, Nanjing210037)

AbstractRecommendation system is a widely used technology in the electronic commerce. Along with the increase of the amount of data, sparsity of rating data become a big question. To improve sparsity of rating data more effectively, a collaborative filtering algorithm based on predicting and filling miss-data by interated is proposed. This method fills the rating data by iterated until the number of missing-data stably. During the iterating, the method of similarity analysis based on the result-data at last step. So not only this method improves sparsity of rating data more effectively, but else efficiently improves the accuracy of similarity analysis under the exreme sparsity of rating data.The experimental results show that this method can improve the quality of recommendation.

Key Wordsrecommendation, collaborative filtering, iteration, prediction, similarity computing, filling missing-data, data density

收稿日期:2015年12月7日,修回日期:2016年1月30日

基金項目:國家自然科學基金(編號:11471161)資助。

作者簡介:盧棪,男,碩士研究生,研究方向:數據挖掘。劉應安,男,博士,教授,研究方向:數據挖掘,統計診斷,林業統計分析。

中圖分類號TP311

DOI:10.3969/j.issn.1672-9722.2016.06.002