方　芳，嚴克文

(合肥工業(yè)大學 管理學院，安徽　合肥　230009)

基于增量更新的協(xié)同過濾推薦算法

方芳，嚴克文

(合肥工業(yè)大學 管理學院，安徽合肥230009)

摘要：為解決傳統(tǒng)協(xié)同過濾推薦算法相似度矩陣不能局部更新的問題，提出了一種基于增量更新的協(xié)同過濾推薦算法。該算法首先根據用戶評分數據構建用戶相異度矩陣，然后選取與目標用戶相異度較小且同現(xiàn)次數較多的若干用戶作為目標用戶最近鄰居并產生推薦。算法可以對相異度矩陣進行在線局部更新，無須離線導入全部數據重新計算，從而實現(xiàn)了算法的增量更新，使算法具備了良好的擴展性。進一步實驗表明，基于增量更新的協(xié)同過濾算法具有很高的推薦準確性。

關鍵詞：個性化推薦；協(xié)同過濾推薦；電子商務；用戶相異度；增量更新

一、引言

隨著互聯(lián)網的普及和電子商務的迅猛發(fā)展，“信息過載”問題變得越來越嚴重。一方面用戶很難從中找到自己感興趣的內容，另一方面大量有用的信息也很少被用戶觸及，成為網絡上的“暗信息”。個性化推薦作為解決“信息過載”的有效手段，逐漸成為互聯(lián)網，尤其是電子商務中的一個重要研究內容。目前，幾乎所有大型的電子商務系統(tǒng)，如淘寶、Amazon、京東、當當等都不同程度地使用了各種形式的個性化推薦系統(tǒng)。

根據推薦算法的不同，個性化推薦技術主要分為協(xié)同過濾推薦、基于內容的推薦、基于關聯(lián)規(guī)則的推薦和混合推薦[1-2]。其中，協(xié)同過濾推薦是目前應用最為廣泛的個性化推薦技術。協(xié)同過濾算法的基本思想是根據所有用戶對物品或者信息的偏好，發(fā)現(xiàn)與目標用戶興趣偏好相似的鄰居用戶群，然后，基于鄰居的歷史偏好信息，為目標用戶進行物品的推薦。

隨著電子商務規(guī)模的不斷擴大，用戶數量和商品數量越來越多，協(xié)同過濾算法面臨的擴展性問題變得越來越嚴重，從而也影響了推薦生成的速度和質量。很多學者及研究機構已經提出了很多方法改善協(xié)同過濾的擴展性問題，采用聚類、矩陣分解、數據集縮減等方法是改善擴展性問題的主要研究方向。文獻[3-6]均是通過聚類的方式減少最近鄰的搜尋空間，從而提高算法的可擴展性。文獻[7-8]則是采用矩陣分解的思想，主要通過奇異值分解(SVD)等方法將高階的用戶評分矩陣分解為幾個低階的子矩陣，并在低階矩陣上進行個性化推薦。文獻[9-10]則采用適當方法壓縮用戶評分矩陣，降低數據集規(guī)模，以應對擴展性問題。這些算法均部分地改進了協(xié)同過濾算法。

用戶和產品的信息是動態(tài)改變的(新用戶、新產品的加入，用戶選擇或評價已經存在的產品)，如果每次改變都需要重新計算，這個計算量是巨大的。比較可行的方案是設計某種近似的動態(tài)算法，每次都只是局部改變，而不需要完全的重新計算。而關于這方面算法的研究，現(xiàn)在還非常少?；诖?，本文提出一種基于增量更新的協(xié)同過濾算法(User-Based Collaborative Filtering with Incremental Updating, IU-UserCF)。IU-UserCF算法可基于發(fā)生變化的評分向量，對相異度矩陣進行在線局部更新，克服了以往算法更新矩陣需要導入全部數據重新計算的問題，使得算法具備良好的擴展性。

二、相關工作

1.傳統(tǒng)相似性度量方法

協(xié)同過濾算法進行推薦的基礎是構建一個相似度矩陣，這需要通過相似性度量方法進行計算得出。度量相似性的方法主要有如下三種：余弦相似性、修正的余弦相似性和皮爾遜相關系數。

(1)

修正的余弦相似性：在余弦相似性度量方法中沒有考慮不同用戶的評分尺度問題，修正的余弦相似性度量方法通過減去用戶對項目的平均評分來改善上述缺陷。設用戶i和用戶j共同評分的項目集合用Iij表示，Ii和Ij分別表示用戶i和用戶j評分的項目集合，則用戶i和j之間的用戶相似性sim(i,j)為：

sim(i,j)=

(2)

皮爾遜相關系數：又稱相關相似性，計算時首先找到兩個用戶的共同評分項目集，設用戶i和用戶j共同評分的項目集合用Iij表示，則用戶i和用戶j之間的相似性sim(i,j)為：

sim(i,j)=

(3)

通過用戶相似性計算，并對計算結果整合，則得到用戶相似度矩陣?；谟脩粝嗨贫染仃?，推薦算法找到目標用戶的鄰居用戶，并根據鄰居用戶評分數據對目標用戶產生推薦。

2.傳統(tǒng)相似性度量方法存在的問題

顯然，基于所有評分數據對相似度矩陣進行完全更新代價太大，尤其是在具有海量用戶和海量商品的系統(tǒng)中，問題會更加嚴重。為此，本文從算法增量更新的角度進行研究，提出了一個可以對矩陣進行在線局部更新的協(xié)同過濾算法。該方法可以只使用發(fā)生變化了的評分向量，而不需要其他的評分向量的參與，通過一定的運算對矩陣進行在線局部更新。此方法在保證算法準確性的基礎上大大提高了算法的可擴展性。

三、基于增量更新的協(xié)同過濾算法

1. 用戶相異度

本文將提出一個新的概念——用戶相異度，其理論基礎來源于Daniel在2005年提出的Slope One算法。在文獻[11]中，Daniel提出了“物品相異度”的概念，而“用戶相異度”是對它的一個變形。

物品相異度是用于衡量物品相異程度的指標，它基于同一用戶對不同物品的評價，通過評分相減計算得出。給定一個訓練集x，以及任意兩個物品i和j,用戶u對它們的打分分別為ui和uj，Sj,i(x)表示訓練集中同時對物品i和j打過分的用戶集，u∈Sj,i(x)，card(Sj,i(x))表示用戶數量，則物品i與j的物品相異度計算如下：

(4)

可見，對于物品i和j，假如若干用戶對它們的打分均十分接近，則它們的物品相異度小，反之則大。物品相異度是對用戶評分矩陣從用戶維度上進行分析得到的一個結果。如果從物品維度上來看，將得到用戶相異度。

用戶相異度：用于衡量用戶偏好相異程度的指標，它基于不同用戶對同一物品的評價，通過評分相減取絕對值計算得出。給定一個訓練集，以及任意兩個用戶a和b，用戶a和b都對物品i打過分,用戶a對物品i的打分為ai，用戶b對物品i的打分為bi，Sb,a(x)表示訓練集中同時被用戶a和b打過分的物品集，i∈Sb,a(x)，card(Sb,a(x))表示物品數量，則用戶a與b的用戶相異度計算如下：

(5)

可見，對于任意兩位用戶，假如他們在若干個物品上的評分都十分相近，那么他們的用戶相異度就小，反之則大。當兩兩用戶間的相異度都計算出來之后，則得到用戶相異度矩陣。

2.算法流程

(1)輸入數據

算法的輸入數據為用戶—物品評分數據集，該評分數據集是一個m*n階的矩陣，記為A(m,n)。行代表m個用戶，列代表n個物品。第i行第j列的元素ri,j表示用戶i對物品j的打分，見表1。

表1　用戶—物品評分矩陣

表2　用戶相異度矩陣

(2)構建用戶相異度矩陣

通過公式(5)可以計算出兩兩用戶間的相異度，從而得到用戶相異度矩陣,如表2。其中dev表示用戶相異度，count表示同現(xiàn)次數(即兩個用戶同時打分過的物品的數量)。這是一個對稱矩陣，可以只存儲上三角或下三角以優(yōu)化性能。

(3)在線推薦

通過相異度矩陣可以得到目標用戶的最近鄰居，選擇最近鄰可以通過設定閾值的方式進行，比如選取用戶相異度小于1并且同現(xiàn)次數大于5的用戶作為最近鄰。下一步就是根據鄰居用戶的評分對目標用戶產生相應的推薦。設用戶u的最近鄰居集為NNu，則用戶u對項目i的預測評分pu,i可以通過用戶u的最近鄰居集NNu中的項目評分得到，計算方法如下：

(6)

公式中使用同現(xiàn)次數count作為權重，ru’i表示鄰居用戶u’對項目i的評分。最后將預測結果按降序排序，產生Top-N推薦。

3.算法的增量更新

增量更新是指在進行更新操作時，只更新需要改變的地方，不需要更新或者已經更新過的地方則不會重復更新，增量更新與完全更新是相對的概念。

上文已經分析了傳統(tǒng)相似度矩陣的更新方式，它是完全更新的過程。而用戶相異度矩陣則是一個增量更新的矩陣，它可以在線局部更新。矩陣的每次更新最少可以只使用一個評分向量，而不需要與其他評分向量相互運算。若新增評分，則評分向量發(fā)生變化，此時系統(tǒng)對變化的評分向量進行標記，同時算法程序對被標記的向量進行調用，然后運算并局部更新矩陣。其具體更新策略如下:

那么對a與b之間的用戶相異度的更新方法如下：

devb,a=dev'b,a+|bi-ai|

(7)

dev'b,a為舊的用戶相異度。devb,a更新后，countb,a同時加1。處理完一個向量后取消標記并處理下一個被標記的評分向量。當然，也可以根據需要一次處理若干個或所有標記向量。但不管怎樣，對于矩陣的更新，已經不再需要運用所有評分數據來進行完全更新了，而是基于變化的評分向量的局部更新，從而實現(xiàn)了算法的增量更新，大大提高了算法的可擴展性。

四、實驗結果和分析

1.實驗數據集

實驗數據采用美國明尼蘇達大學GroupLens項目組提供的MovieLens100K數據集(http://grouplens.org/)。MovieLens是一個基于Web的研究型推薦系統(tǒng)，通過用戶對電影的評分進行電影推薦。MovieLens100k包含943位用戶對1 682部電影的十萬條評分數據，其中每個用戶至少對20部電影進行了評分，評分值為1～5的整數。本次實驗采用五折交叉驗證法，把數據集分成五份，輪流取一份做測試集，其他四份做訓練集。

2.度量標準

評價推薦系統(tǒng)質量的度量標準主要包括統(tǒng)

計精度度量方法和決策支持精度度量方法。統(tǒng)計精度度量方法中的平均絕對誤差(Mean Absolute Error，MAE)易于理解和計算，可以直觀地對推薦質量進行度量，是最常用的一種推薦質量度量方法。本文將采用MAE作為度量標準。設目標用戶的預測評分集合為{p1,p2,…,pn}，對應的實際評分集合為{q1,q2,…,qn}，則平均絕對誤差MAE定義為：

可見，MAE是通過計算目標用戶的預測評分與實際評分之間的偏差，來度量預測的準確性。因此，MAE值越小，說明預測評分與實際評分越相近，預測精度越高。

3.結果及分析

IU-UserCF算法中存在兩個變量：用戶相異度dev和同現(xiàn)次數count。依據單一變量原則，實驗需測定：①在DEV一定的情況下，count變化對結果的影響；②在count不變的情況下，dev變化對結果的影響；③通過實驗確定一組閾值，并將其得出的MAE值與其他算法進行比較。

(1) 同現(xiàn)次數對結果的影響

表3　同現(xiàn)次數對IU-UserCF預測結果的影響

從表3 average列可以看出，在dev不變的情況下，隨著count的遞增，MAE值呈下降趨勢。因為同現(xiàn)次數越大，得到的鄰居用戶與目標用戶會越相似，對預測能產生積極的影響，這從實驗結果也能體現(xiàn)出來。但需要注意的是，同現(xiàn)次數不宜設置過大，過大的同現(xiàn)次數可能會使部分用戶無法找到鄰居。實際使用中應根據數據集的特點進行調整，以取得一個最優(yōu)值。

(2)用戶相異度對結果的影響

表4　用戶相異度對IU-UserCF預測結果的影響

從表4 average列可以看出MAE值呈逐步上升的趨勢。因為用戶相異度設置過大，找到的鄰居會比較多，其中摻雜較多并非很相似的鄰居，從而影響預測的準確性。而在用戶相異度較小的時候，找到的鄰居相似度極高，因此預測精度高。但即便如此，也并非說用戶相異度取值越小越好，因為過小的用戶相異度可能會使部分用戶無法找到鄰居，從而也無法對其產生推薦。實際使用中應結合具體情況進行調整。

(3)算法MAE比較

本組實驗使用IU-UserCF算法與幾種常見推薦算法進行比較。根據之前實驗，本文算法將采用閾值為：dev≤0.5 count≥35，即作為目標用戶鄰居的條件是：與目標用戶的相異度小于等于0.5，并且與目標用戶共同評價過35個及以上的相同物品。IU-UserCF算法在該閾值下得到的MAE值為0.6573168。參與比較的算法包括：基于項目的協(xié)同過濾(ItemCF)、Slope One加權算法(WEIGHTED Slope One)[11]、基于用戶的協(xié)同過濾(UserCF)(近鄰數為20)[12]和基于奇異值分解的推薦算法(SVD)[13]。實驗結果如圖1所示。

從圖1可以看出，本文提出的IU-UserCF算法MEA值是最低的，在預測準確性上高于其他幾種算法。由此可知，本文提出的算法不但可以增量更新，具備良好擴展性，并且具有很高的推薦準確性，可以有效提高推薦系統(tǒng)的性能及推薦質量。

圖1　IU-UserCF與其他算法準確性比較

五、結語

傳統(tǒng)的協(xié)同過濾推薦算法使用余弦相似性、皮爾遜相關系數等相似性度量方法構建矩陣，但這會存在著矩陣不能在線局部更新的問題。每一次對矩陣的更新都是基于所有數據的計算然后完全更新，這勢必會對推薦系統(tǒng)造成嚴重的擴展性問題。針對此問題，本文提出了一種基于增量更新的協(xié)同過濾推薦算法IU-UserCF。IU-UserCF算法不但可以基于變化的評分向量在線局部更新矩陣，并且經實驗證明具有很高的推薦準確性，很好地解決了推薦系統(tǒng)面臨的擴展性問題。另外，由于本文中的鄰居集是基于閾值的設定動態(tài)生成的，可能會造成部分用戶鄰居很多，部分用戶鄰居則較少甚至沒有鄰居的情況。因此，下一步的工作可以考慮從固定鄰居數、動態(tài)閾值等角度出發(fā)，進一步優(yōu)化目標用戶鄰居集，以取得更高的推薦準確性。

參考文獻：

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

[2]冷亞軍, 陸青, 梁昌勇. 協(xié)同過濾推薦技術綜述. 模式識別與人工智能, 2014,27(8): 720-734.

[3]Herlocker J.Clustering Items for Collaborative Filtering.Proceedings of the Acm Sigir Workshop on Recommender Systems,1999.

[4]Sarwar B M, Karypis G,Konstan J,et al.Recommender systems for large-scale e-commerce: Scalable neighborhood formation using clustering. Conference on Computer and Information Technology，2002.

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

[6]Tao L I,WANG Jian dong,YE Fei yue, et al.Collaborative filtering recommendation algorithm based on clustering basal users.Systems Engineering & Electronics,2007,29(7):1178-1182.

[7]Vozalis M G,Margaritis K G.Using SVD and demographic data for the enhancement of generalized Collaborative Filtering. Information Sciences,2007,177(15):3017-3037.

[8]Chen G,Wang F,Zhang C.Collaborative Filtering Using Orthogonal Nonnegative Matrix Tri-factorization.Data Mining Workshops,2007.Seventh IEEE International Conference on.IEEE,2007:303-308.

[9]Yu K, Schwaighofer A, Tresp V, et al. Probabilistic memory-based collaborative filtering. Ranaon on Nowldg & Daa Ngnrng, 2004,16(1):56-69.

[10]Acilar A M, Arslan A. A collaborative filtering method based on artificial immune network.Expert Systems with Applications, 2009, 36(4):8324-8332.

[11]Lemire D, Maclachlan A. Slope One Predictors for Online Rating-Based Collaborative FilteringSDM. 2005,(5): 1-5.

[12]董麗,邢春曉,王克宏.基于不同數據集的協(xié)作過濾算法評測.清華大學學報:自然科學版,2009,49(4):590-594.

[13] Anil R, Dunning T, Friedman E. Mahout in action. Shelter Island:Manning,2011.

責任編校：田旭，馬軍英

Collaborative Filtering Recommendation Algorithm Based on Incremental Updating

FANG Fang, YAN Ke-wen

(School of Management, Hefei University of Technology, Hefei 230009, China)

Abstract:In order to solve the problem that the similarity matrix of the traditional collaborative filtering recommendation algorithm cannot update partial. A collaborative filtering recommendation algorithm based on incremental updating is proposed. First, the algorithm constructs user-deviation matrix according to the user rating data. And then it selects a number of users whose user-deviation with target user is small and the co-occurrence times is high as nearest neighbor and generates recommendations. This algorithm can update partial for the deviation matrix online. It doesn't have to import all the data to recalculate offline. It implements the incremental updating of the algorithm, which makes it has a good scalability. The experiment result shows that the collaborative filtering algorithm proposed by this paper has very high recommendation accuracy.

Key words:personalized recommendation; collaborative filtering recommendation; E-commerce; user-deviation; incremental update

收稿日期：2016-04-05

基金項目：國家自然科學基金面上項目(61474035)；安徽省科技攻關項目(1206c0805039)；教育部博士點新教師基金(20130111120030)

作者簡介：方芳，女，安徽合肥人，博士，講師，研究方向為決策優(yōu)化、系統(tǒng)芯片測試。

DOI:10.19327/j.cnki.zuaxb.1007-9734.2016.03.019

中圖分類號：F713.36

文獻標識碼：A

文章編號：1007-9734(2016)03-0112-06