鄰域線性最小二乘擬合的推薦支持度模型

孫忱,奚宏生,高榮,2

(1.中國科學技術大學自動化系,230027,合肥;2.廣西財經學院信息與統計學院,530003,南寧)

?

鄰域線性最小二乘擬合的推薦支持度模型

孫忱1,奚宏生1,高榮1,2

(1.中國科學技術大學自動化系,230027,合肥;2.廣西財經學院信息與統計學院,530003,南寧)

針對協同過濾推薦系統在稀疏數據集條件下推薦準確度低的問題,提出了推薦支持度模型以及用于該模型計算的鄰域線性最小二乘擬合的推薦支持度評分算法(linear least squares fitting, LLSF)。該模型描述用戶對被推薦項目更感興趣的可能性,通過用高支持度的評分估計取代傳統的期望估計法來找出用戶更喜歡的項目,從而提高推薦的準確度,并從理論上論述了該算法在稀疏數據集條件下相對其他算法具有更強的抗干擾能力。該模型還易于與其他推薦模型融合,具有很好的可拓展性。實驗結果表明:LLSF算法顯著提升了推薦的準確性,在MovieLens數據集上,F1分數可達到傳統的kNN算法的3倍多,對于越是稀疏的數據集,準確率提升幅度越大,在Book-Crossing數據集上,當稀疏度由91%增加到99%時,F1分數的改進由22%提高到125%。同時該方法不會犧牲推薦覆蓋率,可以保證長尾項目的挖掘效果。

協同過濾;推薦系統;鄰域線性最小二乘擬合;推薦支持度

隨著互聯網的迅速發展,推薦系統已被越來越多地運用到各種網站和電子商務系統中,它不需要用戶提供明確的需求,而是通過分析用戶的歷史行為給用戶的興趣建模,從而主動給用戶推薦能夠滿足他們興趣和需求的個性化信息[1]。協同過濾算法是最重要的推薦系統技術之一,其原理是根據用戶或項目的相似性來預測并推薦當前用戶沒有進行過評分、購買或瀏覽等行為,但是很可能會感興趣的信息[2]?；卩徲虻膮f同過濾推薦由于計算實時性好、可擴展性高、意義清晰易于解釋等特點,應用最為廣泛[3]。數據稀疏性問題是絕大部分電子商務推薦系統面臨的最大挑戰,這是因為相似度的計算是基于用戶或項目的共同歷史行為的,當數據非常稀疏時,就會使得相似度計算不可靠,從而影響基于鄰域的協同過濾推薦的準確性[4]。

研究人員提出了各種方法來提高數據稀疏條件下協同過濾推薦的準確性。Sarwar等研究了不同相似度計算方法及不同數據稀疏度對準確性的影響[5]。黃創光等通過自適應選擇近鄰數目的方法來緩解數據稀疏帶來的問題[6]。羅辛等把共同評分的數目轉化為相似度支持度的概念來引入計算[7]。這些方法通過提升預測的準確性來提高推薦的準確性,但是提升效果有限。Adamopoulos另辟蹊徑,通過高百分比的加權計算法,改變了通常的平均加權評分預測方式,大大提高了推薦準確性[8]。然而,Adamopoulos所使用的線性插值方法容易受到數據擾動的影響,當數據稀疏時推薦效果急劇降低。

注意到雖然推薦以預測為基礎,但側重點并不相同。本文專注于解決稀疏數據條件下提高推薦效果的問題,在現有研究的基礎上,提出推薦支持度的概念,選擇合適的推薦支持度實現更有效的推薦,同時設計一種新的鄰域線性最小二乘擬合的方法來進行計算。實驗結果表明,本文提出的方法能大幅度提高推薦的準確性,同時還可略微提升或至少不會犧牲推薦的覆蓋率。當數據越是稀疏時,本文方法所能提供的改進就越明顯。

1 相關工作

目前廣泛研究和應用的推薦系統技術絕大多數都是由基于鄰域的協同過濾方法拓展或融合而來,而Adamopoulos進一步提出了加權百分比的方法來提高推薦準確度。

1.1 基于鄰域的協同過濾推薦

基于鄰域的協同過濾算法[1-5,9-10]分為基于用戶的算法和基于項目的算法,兩者計算原理相同,只是考察維度相互對換,下面以基于用戶的算法為例進行介紹。

一般地,把用戶u對項目i的評分rui作為該用戶對該項目感興趣的程度,基于用戶的算法通過找出與某用戶u最相似的k個用戶(稱為用戶u的k-近鄰)來估計用戶u對其沒有做過評分項目的可能評分。

不同用戶u與v之間的相似性是一個測度,一般可以選用皮爾遜相似度

(1)

(2)

這就是通常所說的kNN估計。以用戶和項目為兩個維度的評分矩陣也稱為效用矩陣,評分預測問題可以看作是填充效用矩陣中的空白元素。取得評分預測后,便可將用戶最可能感興趣的項目推薦給用戶,一般采用Top-N推薦[11-12],即把用戶u評分估計最高的N個項目推薦給該用戶。

上面式子中的累加運算表示對用戶全集中的所有用戶u進行計算,Ru表示推薦給用戶u的項目集合,Tu表示測試集中用戶u做出評分的項目集合,|A|表示集合A中元素的個數。

此外,統計學中還使用F1分數(記作F1)來兼顧準確率和召回率,作為綜合準確性指標,F1=2pPpR/(pP+pR)。

覆蓋率指標反映推薦系統對長尾項目的挖掘能力,也就是考察推薦物品的分布,這個分布越平均,則長尾挖掘能力越好,覆蓋率越高;反之,若分布越陡峭,則推薦集中于部分物品,長尾挖掘能力差,覆蓋率低。覆蓋率指標可以用比較粗略的覆蓋率來描述,記作cC=|∪Ru|/|I|。

1.2 基于線性插值法的加權百分比的推薦方法

由式(2)可見,通常的基于鄰域的協同過濾方法在計算用戶u對項目i評分估計時,實際上是把近鄰集合Nk,u中的每一個用戶v對i的評分,按照該用戶與u的相似度進行加權平均。也就是說,若把每個近鄰v與u的相似度占所有近鄰相似度總和的比值當成u對i的評分可能等于的概率,則u對i的評分估計取值為所有近鄰對i的評分期望。

從另一方面看,推薦的基本原理是將用戶最可能感興趣的項目推薦給用戶,基于這種考慮,加權百分比的推薦方法[8]不采用上述的期望計算法來評估用戶對項目的興趣,而是提出了一種高概率百分比的推薦,通過評估用戶會以高概率(大于50%)對項目感興趣的程度來實現推薦。

算法1 加權百分比估計。

步驟1 將r1,r2,…,rk按從小到大排序,并對應變化w1,w2,…,wk的順序,仍然記為w1,w2,…,wk;

2 鄰域線性擬合的推薦置信度模型

2.1 推薦支持度模型

在加權百分比推薦方法的基礎上,本文完整地提出了推薦支持度模型來推薦更趨向于給出用戶最感興趣的項目。

(3)

推薦支持度模型中,一般選取p為大概率數值,從而描述了用戶可能更趨向于喜歡某項目的程度,大大提高了推薦的準確性指標。

2.2 鄰域線性擬合算法

本文提出采用鄰域線性最小二乘擬合的方法實現數據濾波,減小擾動影響。

算法2 鄰域線性最小二乘擬合估計。

輸入 (rvi,wuv),v∈Nk,u,推薦支持度p。

步驟1 對輸入元組集合排序及歸一化處理后得到序列(r1,w1),(r2,w2)…,(rk,wk);

下面,通過一個例子來解釋p-支持度評分估計的方法。設用戶u的鄰域大小為5,鄰居們與u的相似度分別為0.05,0.075,0.1,0.2,0.075,且已知他們對項目A的評分為4,4,5,6,10,按評分排序并對相似度歸一化處理后得到元組序列為{(4,0.1),(4,0.15),(5,0.2),(6,0.4),(10,0.15)},把這些元組標識的點繪制在坐標軸上,如圖1所示,可以得到線性插值法(Interpolation,IP)的折線和鄰域最小二乘線性擬合法(linear least squares fitting,LLSF)的擬合直線。由圖可見,p=0.8時的p-支持度評分估計是:線性插值法為5.875,而鄰域最小二乘線性擬合法計算得到7.339。

圖1 p-支持度評分估計示例圖

由圖2可見,A評分始終高于B評分。分段插值法下,p1和p3為A評分與B評分的交點,推薦支持度選在區間(p1,p3)內時,B評分大于A評分,將會推薦B,其他推薦支持度時則推薦A。鄰域最小二乘法計算p2為A評分與B評分的交點,當推薦支持度選擇大于p2的值時,B評分大于A評分,系統應推薦B,否則推薦A。

圖2 推薦支持度模型示例圖

2.3 針對稀疏數據集的分析

下面,分析鄰域線性擬合算法對于處理稀疏數據集的優勢。數據的稀疏度對推薦準確率有很大影響的主要原因在于,稀疏的數據集使得兩用戶之間的共同評分項目變得很少。由式(1)可知,兩用戶的相似度wuv是通過其共同評分的項目Iu∩Iv計算的,所以當共同評分的項目越少時,相似度計算受擾動的影響就越大。我們稱共同評分項目很少時計算出來的相似度為不可信相似度。例如,若兩個用戶只有一部共同評分的電影,而他們在這部電影上恰好評分相同(若使用皮爾遜相似度,確切地說,應該是相對平均值的評分差相同),則兩個用戶具有很大的相似度。實際上,很可能這兩個用戶興趣根本不同(從他們很少評價同一部電影就可以看出)。不可信相似度用戶的評分可能會對推薦結果造成很大的誤導,形成錯誤的推薦。

最后,分析鄰域線性擬合法的抗擾動能力。根據算法2步驟2,可以計算出

a=(k∑xjrj-∑xj∑rj)/

(4)

(5)

因此有

(6)

其中與rm有關的因式是

(7)

其系數受到更多因素的制約,故抗干擾能力更強。

2.4 模型的融合與拓展

當前推薦系統已發展出大量的模型與算法,除了本文應用到的協同過濾推薦,還有基于內容的推薦、基于模型的推薦[2]等,每一大類又有很多的優化方法。每種模型各有其優缺點,在實際應用中,通常是融合多種模型來提高推薦的性能。

3 實驗評估

3.1 實驗方案

分別使用MovieLens數據集和Book-Crossing數據集對本文提出的鄰域最小二乘線性擬合推薦支持度模型進行Top-N推薦離線測試,評估其對推薦準確度的提升效果,并同時考查推薦覆蓋率指標的滿足情況。

為防止過擬合,實驗采用以下步驟來進行。

步驟1 將數據集隨機分成M份,第1份作為測試集,另外M-1份作為訓練集;

步驟2 使用訓練集來訓練模型,使用測試集來檢測得到待評估的指標;

步驟3 更換隨機數種子,返回步驟1再次開始,共重復M次;

步驟4 把M次實驗計算的指標值進行平均,得到最后的指標評估。

本文中的實驗選取M=5,并且使用傳統kNN算法及前面介紹的線性插值算法進行數據對比研究。

3.2 MovieLens數據集實驗

MovieLens數據集[13](簡寫為ML)是由明尼蘇達大學GroupLens研究小組提供的電影評分數據集,本文使用其大小為10萬條記錄的數據集進行離線測試,數據稀疏度為93.7%。

首先測試了不同算法在不同鄰域大小時對推薦準確率的影響,并使用F1分數來評估準確率。實驗結果如圖3所示,圖3的4個子圖分別給出了鄰域k選取5、15、30、50時的推薦結果。推薦集大小N作為坐標橫軸,實驗計算了N取3、5、10、30、50、100時的推薦F1分數,F1分數作為坐標縱軸,實驗對比了kNN算法、分段線性插值(IP)的加權百分比算法(選取p=0.8)、鄰域最小二乘線性擬合(LLSF)的推薦支持度算法(分別選取p=0.5,0.8,0.9)。

由圖3可知,鄰域k為15、30、50時,IP算法與LLSF算法的推薦準確率都優于kNN算法,LLSF算法又顯著優于IP算法。對于LLSF算法來說,p=0.9時效果最佳,特別地,k=15且N=50時,取得最高推薦準確率。當k=5時,IP算法準確率反而低于kNN算法,當N較小時LLSF算法仍然優于kNN算法,只有當N較大時推薦效果才比kNN算法差。

取k=30、N=50為考察維度,不同算法的準確率指標和覆蓋率指標結果如表1所示。IP算法雖然準確度(準確率和召回率)高于kNN算法,但是覆蓋率指標(覆蓋率和信息熵)偏低,而LLSF算法不但準確率明顯優于kNN和線性插值算法,覆蓋率也沒有很大損失,可以保證對長尾項目的挖掘能力。

(a)鄰域大小為5 (b)鄰域大小為15

(c)鄰域大小為30 (d)鄰域大小為50圖3 ML數據集不同鄰域大小時各算法的F1分數

算法準確率召回率F1分數覆蓋率信息熵kNN0.0270.0630.0380.7149.47IP(p=0.8)0.0440.1040.0620.3076.68LLSF(p=0.5)0.0570.1360.0810.6208.80LLSF(p=0.8)0.0800.1890.1130.5398.50LLSF(p=0.9)0.0830.1970.1170.5278.49

3.3 Book-Crossing數據集實驗

Book-Crossing數據集[14](簡寫為BX)是由Ziegler等爬取www.bookcrossing.com社區獲得的書籍評分數據集。本文對原始數據集進行處理,剔除評分數過少的用戶后,形成不同稀疏度的4個數據集,數據稀疏度分別是BX1為90.9%,BX2為95.2%,BX3為98.2%,BX4為99.3%。

圖4給出了對不同稀疏度的BX數據集進行離線實驗,幾種算法在選取鄰域k=30時所得到的推薦準確度指標F1分數與推薦數量N的關系。由圖可見,在不同稀疏度條件下,大支持度(p=0.8,0.9)的LLSF算法推薦準確度都優于kNN和IP算法。IP算法雖然在稀疏度較低時推薦準確度較好,但當數據稀疏度上升時,準確度迅速下降,甚至低于基本的kNN算法。

(a)BX1數據集 (b)BX2數據集

(c)BX3數據集 (d)BX4數據集圖4 BX數據集不同稀疏度時各算法的F1分數

不同稀疏度BX數據集實驗中各算法的推薦效果比較見表2。對于準確率指標,N0為使得F1分數達到最大值的推薦數量,F1(N0)為當前算法的最大準確率,即Top-N0推薦的F1分數,F1優化率為當前算法對比kNN算法的最大準確率提升的百分比;對于覆蓋率指標,信息熵為當前算法對于N取3、5、10、30、50、100時的信息熵均值。

表2 不同稀疏度BX數據集各算法推薦指標分析

由表2可見,隨著數據集稀疏度的增大,LLSF算法所提供的準確率改進就越大。同時,LLSF算法的覆蓋率指標犧牲很小,大大優于IP算法的覆蓋率,可以滿足長尾項目的挖掘要求。

4 結 論

盡管推薦系統主要有預測和推薦兩類應用,但Top-N推薦是其實際中最廣泛的應用方式[1]。然而,目前絕大部分的研究還是集中在預測領域,針對提升推薦準確率的研究還較少。本文所描述的鄰域最小二乘線性擬合的推薦支持度模型可以大幅度提升推薦準確率,特別是對于稀疏數據集效果更顯著,同時也沒有犧牲推薦的覆蓋率,保證了對長尾項目的挖掘能力。

本文所描述的方法還可以與其他模型融合以進一步提升推薦效果,具有良好的算法拓展能力。下一步,我們將具體研究本文方法與其他模型融合時涉及的模型選擇、參數選擇和實驗效果等問題,特別是融合基于內容的推薦,從而更好地處理冷啟動問題,提升算法的實際應用性能。

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

[2]ADOMAVICIUS G, TUZHILIN A.Toward 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.

[3]LINDEN G, SMITH B, YORK J.Amazon.com recommendations: item-to-item collaborative filtering [J].IEEE Internet Computing, 2003, 7(1): 76-80.

[4]SU Xiaoyuan, KHOSHGOFTAAR T M.A survey of collaborative filtering techniques [J].Advances in Artificial Intelligence, 2009, 2009: 421425.

[5]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.New York, USA: ACM, 2001: 285-295.

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

HUANG Chuangguang, YIN Jian, WANG Jing, et al.Uncertain neighbors’ collaborative filtering recommendation algorithm [J].Chinese Journal of Computers, 2010, 33(8): 1369-1377.

[7]羅辛, 歐陽元新, 熊璋, 等.通過相似度支持度優化基于K近鄰的協同過濾算法 [J].計算機學報, 2010, 33(8): 1437-1445.

LUO Xin, OUYANG Yuanxin, XIONG Zhang, et al.The effect of similarity support in K-nearest-neighborhood based collaborative filtering [J].Chinese Journal of Computers, 2010, 33(8): 1437-1445.

[8]ADAMOPOULOS P, TUZHILIN A.Recommendation opportunities: improving item prediction using weighted percentile methods in collaborative filtering systems [C]∥Proceedings of the 7th ACM Conference on Recommender Systems.New York, USA: ACM, 2013: 351-354.

[9]呂紅亮, 王勁林, 鄧峰, 等.多指標推薦的全局鄰域模型 [J].西安交通大學學報, 2012, 46(11): 98-105.

Lü Hongliang, WANG Jinlin, DENG Feng, et al.A global neighborhood-based model with multi-criteria recommendation [J].Journal of Xi’an Jiaotong University, 2012, 46(11): 98-105.

[10]KOREN Y.Factor in the neighbors: scalable and accurate collaborative filtering [J].ACM Transactions on Knowledge Discovery from Data, 2010, 4(1): 1-24.

[11]DESHPANDE M, KARYPIS G.Item-based top-N recommendation algorithms [J].ACM Transactions on Information Systems, 2004, 22(1): 143-177.

[12]ADAMOPOULOS P.On discovering non-obvious recommendations: using unexpectedness and neighborhood selection methods in collaborative filtering systems [C]∥Proceedings of the 7th ACM International Conference on Web Search and Data Mining.New York, USA: ACM, 2014: 655-660.

[13]GROUPLENS.MovieLens datasets [DB/OL].(2011-03-01)[2014-06-20].http:∥www.grouplens.org/datasets/movielens/.

[14]ZIEGLER C N, FREIBURG D.Book-crossing datasets [DB/OL].(2004-06-01)[2014-06-20].http:∥www2.informatik.uni-freiburg.de/～cziegler/BX/.

(編輯 武紅江)

A Recommendation-Support Model Using Neighborhood-Based Linear Least Squares Fitting

SUN Chen1, XI Hongsheng1, GAO Rong1,2

(1.Department of Automation, University of Science and Technology of China, Hefei 230027, China;2.School of Information and Statistics, Guangxi University of Finance and Economics, Nanning 530003, China)

A recommendation-support model and a neighborhood-based linear least squares fitting (LLSF) algorithm for the calculation of recommendation-support rating are proposed to solve the low accuracy problem of collaborative filtering based recommender systems on sparse data sets.The model focuses on the probability of users’ more interests on the recommended items, and uses the estimation with high recommendation-support rating to replace the traditional expecta-tion estimation so that users’preferred items are found and the accuracy of recommendation is improved.A theoretical analysis shows that the anti-interference ability of the LLSF algorithm is better than those of other algorithms under the condition of sparse data sets.The model is also expansible by integrating other models.Experimental results show that the LLSF algorithm improves the recommendation accuracy remarkably.TheF1score is 3 times of that of the traditionalkNN algorithm on the MovieLens data set.The more sparse the data set is, the more the improvement on accuracy obtains.When the sparsity grows from 91% to 99% on the Book-crossing data set, the improvement onF1scores increases from 22% to 125%.Moreover, the algorithm can guarantee the ability of long tail mining without loss of recommendation coverage.

collaborative filtering; recommender system; neighborhood-based linear least squares fitting; recommendation-support model

2014-08-18。 作者簡介:孫忱(1981—),女,博士生;奚宏生(通信作者),男,教授,博士生導師。 基金項目:國家自然科學基金重點資助項目(61233003);國家自然科學基金資助項目(61262002);廣西省自然科學基金資助項目(2013GXNSFBA019274);廣西省社科規劃研究資助項目(13BXW007)。

時間:2015-03-23

http:∥www.cnki.net/kcms/detail/61.1069.T.20150323.1713.002.html

10.7652/xjtuxb201506013

TP391;TP274

A

0253-987X(2015)06-0077-07