王兆國++謝峰++關(guān)毅 薛一波

術(shù)學(xué)院， 哈爾濱 150001； 2 清華大學(xué) 信息科學(xué)與技術(shù)國家實驗室， 北京 100084）

摘要： 關(guān)鍵詞： 中圖分類號： 文獻標(biāo)志碼： A文章編號： 2095-2163（2017）04-0001-05（1 School of Computer Science and Technology， Harbin Institute of Technology， Harbin 150006， China；

2 National Lab for Information Sci. & Tech， Tsinghua University， Beijing 100084， China）

Abstract： With the development of social media， Internet is not only people's tool to get information， but also a channel to share information. Usergenerated contents make people face overload information. So that a lot of really valuable information is difficult to be found. On the strength of lower user involvement， the personalized recommendation system has been considered as one of the most potential methods to solve information overload at present. However， currently the most mature and widely used collaborative filtering recommendation method is facing such problems as data sparseness， diversity and so on. Its recommended effect is not ideal. A recommendation method based on linear regression is proposed in this paper. A linear regression model is established by using the rating frequency information of the users or items to predict the uses' scores on nonscored items. The method has the advantages of low complexity， incremental updating， and high accuracy and so on.

Keywords：

基金項目：

作者簡介：

收稿日期： 0引言

近年來，社交網(wǎng)絡(luò)的普及和發(fā)展，改變了人們被動獲取信息的方式，用戶產(chǎn)生內(nèi)容呈爆炸式增長。對于普通用戶來說，面對海量的信息難以找到自己真正感興趣的部分，這就是信息過載問題＼[1＼]。門戶網(wǎng)站按照信息的屬性分門別類以幫助用戶快速索引，搜索引擎通過分析用戶輸入的查詢返回最相關(guān)的內(nèi)容。盡管兩者在很大程度上提高了用戶獲取信息的效率，但都需要用戶過多的參與，不能自動感知用戶的興趣，況且很多時候用戶根本不知道自己想要什么，或者不能有效運用關(guān)鍵詞描述自己的興趣。此外，分類和搜索技術(shù)返回的結(jié)果嚴(yán)重缺乏個性，用戶體驗不佳。推薦系統(tǒng)＼[2＼]通過分析用戶的歷史行為，為每一個用戶建立個性化的興趣模型，主動向用戶推送可能感興趣的內(nèi)容，這被認(rèn)為是解決信息過載最具潛力的設(shè)計研發(fā)方式。

目前居于應(yīng)用流行首位的個性化推薦系統(tǒng)所采用的推薦方法是協(xié)同過濾＼[3＼]，維基百科給協(xié)同過濾方法的定義是：“利用某興趣相投、擁有共同經(jīng)驗之群體的喜好來推薦使用者感興趣的資訊”。協(xié)同過濾方法主要分為2類＼[3＼]：基于啟發(fā)式的方法＼[4-9＼]和基于模型的方法＼[10-16＼]。其中，基于啟發(fā)式的方法利用用戶對物品的隱性或顯性行為得到用戶物品評分矩陣，然后計算用戶或物品間的相似度，最后根據(jù)鄰居用戶或物品的評分及相似度給出評分預(yù)測和結(jié)果推薦。根據(jù)相似性計算的主題是用戶還是物品，基于啟發(fā)式的方法可以進一步分為基于用戶的協(xié)同過濾方法＼[4＼]和基于物品的協(xié)同過濾方法＼[17＼]。目前，啟發(fā)式方法由于呈現(xiàn)的易部署、高效率的特性，已然廣泛應(yīng)用于商業(yè)系統(tǒng)中，如Amazon。然而，由于數(shù)據(jù)稀疏性、多樣性等問題則使得啟發(fā)式方法的推薦性能難以得到有效提升。

為了提高推薦準(zhǔn)確性，基于模型的方法利用用戶物品評分矩陣訓(xùn)練更為精準(zhǔn)的評分預(yù)測模型，比如：聚類＼[16，18＼]、貝葉斯信念網(wǎng)絡(luò)＼[6，19＼]、馬爾可夫決策過程＼[20＼]以及潛在語義模型＼[21＼]等。盡管基于模型的方法提高了預(yù)測準(zhǔn)確性，但卻也同樣面臨模型復(fù)雜、參數(shù)較多并且對數(shù)據(jù)集的統(tǒng)計特性依賴性較大等問題，這也是基于模型的方法難以應(yīng)用于實際推薦系統(tǒng)的重要原因。

本文提出了一種基于線性回歸的推薦方法。該方法利用用戶或物品的評分頻次信息，建立了用戶或物品的某次評分與其最高頻次評分的線性回歸模型，進而利用該模型對未知評分直接根據(jù)歷史評分頻次進行預(yù)測。與傳統(tǒng)方法相比，該方法極大地降低了計算復(fù)雜性，使得算法在Ω（n）的時間內(nèi)完成所有計算，便于應(yīng)用于實際的工業(yè)生產(chǎn)；利用群體智慧，采用統(tǒng)計信息估計模型參數(shù)，具有很好的抗噪聲能力；算法同時具有很好的增量更新能力，可以在常數(shù)時間內(nèi)對新產(chǎn)生的用戶行為完成更新，實時性能好。endprint

2.4實驗結(jié)果

為了比較不同方法對數(shù)據(jù)稀疏程度的容忍度，本節(jié)將MovieLens 1M數(shù)據(jù)集切分成不同比例的訓(xùn)練集和測試集。比例x%從10%以10%的步長增長到90%。分別比較了2.3節(jié)所述方法的評分預(yù)測準(zhǔn)確性、分類準(zhǔn)確性指標(biāo)，以及模型建立和預(yù)測時間的相應(yīng)結(jié)果對照，具體研究闡釋論述如下。

2.4.1預(yù)測準(zhǔn)確性

為了衡量基于線性回歸的推薦方法評分預(yù)測準(zhǔn)確性，本文采用了2.2節(jié)介紹的誤差指標(biāo)MAE和RMSE，其中RMSE在應(yīng)用上要更趨廣泛，這里，本文只給出了各方法在不同數(shù)據(jù)稀疏程度下的RMSE對比結(jié)果，如圖1所示。

圖1RMSE對比實驗

Fig. 1RMSE comparative experiment

從圖1可以看出基于線性回歸的推薦方法無論在何種比例的數(shù)據(jù)集劃分下的RMSE值均遠遠小于基于物品的協(xié)同過濾方法，即預(yù)測準(zhǔn)確性高。同時，也可以看出單純地以用戶的評分頻次以及物品評分頻次的加權(quán)值作為預(yù)測結(jié)果，其準(zhǔn)確性也較高，說明評分頻次信息對于評分預(yù)測具有較大的價值。盡管當(dāng)數(shù)據(jù)集更稀疏的情況下，圖中訓(xùn)練集的比例僅為10%的時候，基于線性回歸的推薦方法的RMSE值與物品平均評分很接近，但是隨著訓(xùn)練集比例不斷增加，基于線性回歸的推薦方法的評分預(yù)測準(zhǔn)確性則呈現(xiàn)出明顯性能優(yōu)勢。

2.4.2分類準(zhǔn)確性

評分預(yù)測準(zhǔn)確性衡量的是預(yù)測評分與實際評分之間的差距，而真實系統(tǒng)中由于只關(guān)心給用戶推薦出來的前N個物品是否符合用戶的興趣，因此，本文將預(yù)測評分和實際評分與評分喜好閾值（數(shù)據(jù)集采用5分制，這里閾值取3）進行比較，判斷預(yù)測用戶對物品的喜好是否與實際情況一致相符，也就是2.2節(jié)所討論的喜好分類指標(biāo)，其中，precision和recall值都不能單獨衡量預(yù)測結(jié)果的分類性能高低，本文僅給出了兩者合成指標(biāo)F值的對比，如圖2所示。

圖2F-Measrue比較實驗

Fig. 2F-Measure comparison experiment

從圖2可以看出，隨著訓(xùn)練集比例的增加，除基于物品的協(xié)同過濾方法外，其余方法的F值均有所增加，并且遠遠大于基于物品的協(xié)同過濾方法。此外，基于線性回歸的推薦方法在所有方法中獲得了最佳效果表現(xiàn)，其F值在訓(xùn)練集比例超過30%開始就大于基于物品平均評分的方法。

2.4.3時間性能

實際生產(chǎn)環(huán)境總是對推薦結(jié)果的響應(yīng)時間有一定的需求，特別是用戶和商品過億的大型真實系統(tǒng)對算法的耗時將更加敏感。本節(jié)給出了基于線性回歸的推薦方法與2.3節(jié)所介紹的方法的建模時間和預(yù)測時間的對比，結(jié)果如表2所示，其中，IA表示Item Average、IC表示Item Correlation、RF表示Rating Frequency、LR表示Linear Regression。

表2建模時間和預(yù)測時間的對比分析

Tab. 2Comparison of modeling time and forecast time

訓(xùn)練集比例IAICRFLR20%T建模0.16729.0190.1590.250T預(yù)測4.0289.1070.95416.63940%T建模0.30259.1330.2680.441T預(yù)測3.1799.0960.67421.92860%T建模0.45584.8340.3700.689T預(yù)測2.1535.5770.46222.13380%T建模0.585110.3680.4741.136T預(yù)測1.1216.4300.25613.485基于物品平均評分的方法在建模的過程中只需要計算各物品的平均評分，而基于用戶和物品評分頻次的方法同樣只需要簡單計算每個用戶的最高頻次評分和物品的最高頻次評分，因此這2種方法的建模時間非常短。建模耗時最長的是基于物品的協(xié)同過濾方法，該方法需要計算兩兩物品之間的Pearson相關(guān)系數(shù)，即物品相似度，然后為每一個物品選擇一定數(shù)量的最相似的物品構(gòu)成鄰居物品集合，最終在評分預(yù)測過程中利用用戶對未評分物品的鄰居物品集合中的物品的評分加權(quán)得到預(yù)測結(jié)果?？傮w來說，基于線性回歸的推薦方法的建模時間和預(yù)測時間具有較強的競爭力，能夠滿足真實系統(tǒng)對預(yù)測時間性能的要求。

3結(jié)束語

本文提出了基于線性回歸的推薦方法，該方法巧妙地利用用戶的評分頻次以及物品的評分頻次信息，分別構(gòu)建了基于用戶的線性回歸模型和基于物品的線性回歸模型，利用這2個模型同時預(yù)測用戶對未評分物品的評分，最終將兩者加權(quán)得到預(yù)測結(jié)果。在公開數(shù)據(jù)集上的實驗結(jié)果表明，基于線性回歸的推薦方法不僅預(yù)測準(zhǔn)確性高于現(xiàn)有的主流方法（基于物品的協(xié)同過濾方法），而且分類準(zhǔn)確性也表現(xiàn)得更優(yōu)。此外，基于線性回歸的推薦方法的時間性能遠遠高于基于物品的協(xié)同過濾方法，能夠為更大規(guī)模的真實系統(tǒng)所采納使用。未來工作中，研究將進一步改進基于線性回歸的推薦方法，利用增量更新方式建立線性回歸模型，并部署配置到真實的系統(tǒng)中檢驗其設(shè)計推薦效果。

參考文獻：

[1] 劉建國， 周濤， 汪秉宏. 個性化推薦系統(tǒng)的研究進展[J]. 自然科學(xué)進展， 2009， 19（1）：1-15.

[2] RESNICK P， VARIAN H R. Recommender systems＼[J＼]. Communications of the ACM， 1997， 40（3）：56-58.

[3] ADOMAVICIUS G， TUZHILIN A. Toward the next generation of recommender systems： A survey of the state-of-the-art and possible extensions＼[J＼]. Knowledge and Data Engineering， IEEE Transactions on， 2005， 17（6）：734-749.endprint

[4] 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. Chapel Hill， North Carolina， USA：ACM， 1994： 175-186.

[5] SHARDANAND U， MAES P. Social information filtering： Algorithms for automating “word of mouth”＼[C＼]//Proceedings of the SIGCHI conference on human factors in computing systems. Denver，USA：ACM Press， 1995： 210-217.

[6] BREESE J S， HECKERMAN D， KADIE C. Empirical analysis of predictive algorithms for collaborative filtering＼[C＼]// Proceedings of the Fourteenth conference on uncertainty in artificial intelligence. Madison， Wisconsin：ACM， 1998： 43-52.

[7] DELGADO J， ISHII N. Memorybased weighted majority prediction for recommender systems[C]//ACM SIGIR 1999 Workshop on Recommender Systems： Algorithms and Evaluation.Berkeley UC：Citeseer， 1999：1-5.

[8] NAKAMURA A， ABE N. Collaborative filtering using weighted majority prediction algorithms＼[C＼]//ICML '98 Proceedings of the Fifteenth International Conference on Machine Learning.San Francisco， CA， USA： Morgan Kaufmann Publishers Inc，1998： 395-403.

[9] YANG J M， LI K F. Recommendation based on rational inferences in collaborative filtering＼[J＼]. KnowledgeBased Systems， 2009， 22（1）：105-114.

[10]GOLDBERG K， ROEDER T， GUPTA D， et al. Eigentaste： A constant time collaborative filtering algorithm＼[J＼]. Information Retrieval， 2001， 4（2）：133-151.

[11]BILLSUS D， PPZZANI M J. Learning collaborative information filters＼[C＼]//Proceeding ICML'98 proceedings of the Fifteenth International Conference on Machine Learning.San Francisco， CA， USA：Morgan Kaufmann Publishers Inc，1998：46-54.

[12]GETOOR L， SAHAMI M. Using probabilistic relational models for collaborative filtering＼[C＼]// Workshop on Web Usage Analysis and User Profiling （WEBKDD'99）. New York， NY， USA：Citeseer， 1999：1-6.

[13]HOFMANN T. Collaborative filtering via gaussian probabilistic latent semantic analysis＼[C＼]// Proceedings of the 26th annual international ACM SIGIR conference on Research and development in information retrieval. Toronto， Canada：ACM， 2003： 259-266.

[14]MARLIN B M. Modeling user rating profiles for collaborative filtering＼[C＼]// Advances in neural information processing systems. Vancouver and Whistler， British Columbia， Canada：DBLP， 2003：1-8.

[15]PAVLOV D X， PENNOCK D M. A maximum entropy approach to collaborative filtering in dynamic， sparse， highdimensional domains＼[C＼]//Advances in neural information processing systems.Cambridge， MA， USA：MIT Press， 2002： 1441-1448.endprint

[16]UNGAR L H， FOSTER D P. Clustering methods for collaborative filtering＼[C＼]// AAAI workshop on recommendation systems.Menlo Park， California， AAAI Press， 1998：1-16.

[17]SARWAR B， KARYPIS G， KONSTAN J， et al. Itembased collaborative filtering recommendation algorithms＼[C＼]//Proceedings of the 10th international conference on World Wide Web. Hong Kong ：ACM， 2001： 285-295.

[18]CHEE S H S， HAN J， WANG K. Rectree： An efficient collaborative filtering method＼[M＼]// KAMBAYASHI Y， WINIWARTER W， ARIKAWA M. Data Warehousing and Knowledge Discovery.DaWaK 2001. Lecture Notes in Computer Science. Berlin： Springer， 2001： 141-151.

[19]SU X， KHOSHGOFTAAR T M. Collaborative filtering for multiclass data using belief nets algorithms[C]//Tools with Artificial Intelligence， 2006. ICTAI'06. 18th IEEE International Conference on.Arlington， VA： IEEE， 2006： 497-504.

[20]SHANI G， HECKERMAN D， BRAFMAN R I. An mdpbased recommender system＼[J＼].The Journal of Machine Learning Research，2005，6：1265-1295 .

[21]HOFMANN T. Latent semantic models for collaborative filtering＼[J＼]. ACM Transactions on Information Systems （TOIS）， 2004， 22（1）：89-115.

[22]SARWAR B， KARYPIS G， KONSTAN J， et al. Analysis of recommendation algorithms for ecommerce＼[C＼]// Proceedings of the 2nd ACM conference on Electronic commerce.Minneapolis， Minnesota， USA ： ACM， 2000： 158-167.

[23]KARATZOGLOU A， AMATRIAIN X， BALTRUNAS L， et al. Multiverse recommendation： Ndimensional tensor factorization for contextaware collaborative filtering＼[C＼]// Proceedings of the fourth ACM conference on Recommender systems. Barcelona， Spain：ACM，2010： 79-86.

[24]JAMALI M， ESTER M. A matrix factorization technique with trust propagation for recommendation in social networks＼[C＼]// Proceedings of the fourth ACM conference on Recommender systems.Barcelona， Spain ：ACM， 2010： 135-142.

[25]CREMONESI P， KOREN Y， TURRIN R. Performance of recommender algorithms on topn recommendation tasks＼[C＼]//Proceedings of the fourth ACM conference on Recommender systems.Barcelona， Spain： ACM， 2010： 39-46.

[26]Sarwar B， Karypis G， Konstan J， et al. Application of dimensionality reduction in recommender system-a case study＼[R＼]. Minneapolis： University of Minnesota， 2000.endprint