基于云填充和混合相似性的協同過濾推薦算法的研究

成韻姿　陳曦　傅明

摘要：針對傳統推薦算法的相似性度量準確性不高及數據極端稀疏性等問題，提出一種基于云填充和混合相似性的協同過濾推薦算法。首先通過云模型填充用戶-項目評分矩陣，然后對相似性度量方法進行改進，將基于時間序列的用戶間影響力融合到基于Jaccard系數的相似性度量方法中。在MovieLens數據集上的驗證結果表明，改進后的算法提高了推薦精度同時在一定程度上克服了數據稀疏性的影響。

關鍵詞：協同過濾推薦算法；云填充；時序行為影響力；Jaccard系數

中圖分類號：TP391 文獻標識碼：A

Abstract：A collaborative filtering recommendation algorithm based on cloud model filling and hybrid similarity was proposed to measure the similarity of the traditional recommendation algorithm with low accuracy and extreme sparsity of data. First， the useritem rating matrix was filled by the cloud model， and then the similarity measure method was improved， and the influence of the user based on time series was fused to the similarity measure method based on the Jaccard coefficient. The validation results on MovieLens data sets show that the improved algorithm can improve the recommendation accuracy and overcome the influence of data sparsity to a certain extent.

Key words：collaborative filtering recommendation algorithm； cloud model filling； temporal behavior influence； Jaccard coefficients

1引言

隨著信息技術和互聯網的發展，信息的產生、加工、傳播變得越來越容易，人們每天都接觸大量的信息，進入了信息過載的時代。在這個時代，無論是消費者還是商家都遇到了很大挑戰：一方面，對于消費者來說，面對如此海量的數據信息，要從中剔除冗余信息、挑選出自己真正需要的信息，猶如大海撈針；另一方面，對于商家來說，要有針對性地推送商品信息，讓自己的商品受到廣大消費者的關注，也是一件非常困難的事情。在此背景下，電子商務推薦系統應運而生。

協同過濾推薦算法[1-2]是目前電子商務推薦系統中應用最廣泛最成功的推薦技術。它的主要思想是利用已有用戶群過去的行為或意見預測當前用戶最可能喜歡哪些東西或對哪些東西感興趣[3]。那么，整個推薦算法的關鍵是找出目標用戶的最近鄰居集合。然而，其歸根結底在于用戶或項目間相似性的度量[4-7]。因此，用戶或項目間的相似性度量是否準確，直接關系到整個推薦系統的推薦質量。傳統的相似性度量方法主要有：余弦相似性、相關相似性和修正的余弦相似都有其不足之處。在現實的數據中，由于用戶評分數據的極端稀疏性，導致用戶間相似性的度量不夠準確，推薦精度較低。而且，大部分的推薦算法并沒有考慮用戶相互之間的影響關系，導致推薦系統的推薦質量下降。

與上述相關工作不同，本文利用云模型填充用戶-項目評分矩陣，在分析基于時序行為的用戶影響力和基于Jaccard系數的相似性度量方法的基礎上，對用戶間相似性的計算方法進行改進。將改進后的算法在MovieLens數據集上進行了相應的實驗，實驗結果表明，改進后的算法提高了推薦精度，同時在一定程度上克服了數據稀疏性的影響。

當一個推薦系統搭建好后，需要解決的首要問題是如何判斷推薦系統的好壞。然而，推薦系統擁有多種評價標準，這些評價標準可用于評價推薦系統各方面的性能。由于不同的系統在不同的應用背景下表現不同，研究者們很難選取恰當的評價標準對系統的表現進行評估。大多數研究者選擇采用準確度來評價推薦算法的好壞。預測準確度是度量一個推薦算法的預測打分與用戶實際打分的相似程度，其中一個經典方法是度量預測打分與實際打分的平均絕對誤差。然而，標準平均絕對誤差[8]（Normalized Mean Absolute Error，簡稱NMAE）是平均絕對誤差在打分值區間內作標準化，從而方便在不同的數據集上對算法的效果進行比較。因此，標準平均絕對誤差的值越小表示該算法對用戶行為的預測越準確。本文選用標準平均絕對誤差的方法來評估推薦算法的優劣性。

2相關工作

2.1云填充

在實際生活中，用戶對商品的評分記錄是很少的，從而評分矩陣相當稀疏，導致推薦效果大大降低。為解決該問題，本文采用云填充[9-10]的方法解決稀疏問題。云模型[11]是李德毅院士提出的一種定性定量不確定性轉換模型，能夠實現定性概念與定量數值之間的不確定性轉換。云填充的基本思想是：先找出未評分的項目，采用云模型計算項目之間的相似性，找出該項目的相似項目， 利用用戶對相似項目的評分來預測未評分項目的評分，從而填充用戶項目矩陣。

對于用戶-項目評分矩陣R，用戶有未評分項目c，其評分頻度向量I=[I0，I1，I2，I3，I4，I5]，其中I0～I5表示6個評分等級出現的次數。通過逆向云發生器，即實現從定量值到定性概念的轉換，可以得到該項目的評分特征向量V=[Ex，En，He]，其中Ex、En、He分別為期望、熵、超熵。兩個項目之間的相似性由評分特征向量的夾角余弦來表示，如公式（1）。

sim（c，d）=VcVd‖Vc‖‖Vd‖ （1）

由此，找出用戶未評分項目的相似項目集D，未評分項目c的預測評分如公式（2），以此來填充用戶-項目評分矩陣R。

R（i，c）=∑d∈Dsim（c，d）×R（i，d）∑d∈D（sim（c，d）） （2）

其中，d表示未評分項目c的相似項目，sim（c，d）表示項目c和項目d的相似性，R（i，d）表示用戶i對項目d評分。

2.2時序行為影響力

雖然協同過濾推薦算法跟其他推薦算法相比取得了巨大的成功，但是其仍存在著諸多問題，其中很重要的一點是傳統的協同過濾推薦算法經常忽略興趣漂移問題。所謂興趣漂移，是指用戶對商品的興趣偏好會隨著時間的推移而變化。Koren等人[12]提出的TimeSVD++算法將時間信息加入到用戶（產品）的特征向量中，有效解決了興趣漂移問題，取得了良好的結果。

超市購物籃數據常常包含關于商品何時被用戶購買的時間信息，可以按照購買時間的先后次序，將用戶在一段時間內的購物事件拼接形成一個時間序列[13]。用戶或商品的消費時間信息可能會隱藏著一部分規律，利用這些規律可以在一定程度上識別系統的重要特征，或者預測特定事件的未來發生。基于時序信息的推薦算法通過將時序信息加入到現有的推薦模型中，使得模型能夠學習到數據的動態變化，從而優化推薦效果[14]。

社會網絡中的結點對應的對象之間存在著各種各樣的關系，通過這些關系，對象之間也相互影響[15-16]。以用戶的關系為例，用戶在消費某些商品時經常受到朋友關系的影響，研究表明，通過朋友購買的商品向目標用戶推薦商品，往往比簡單的利用相似度來推薦商品的方法更可靠[17-19]。

由于傳統的協同過濾推薦算法經常忽略了用戶之間的關系，基于用戶社會化關系挖掘的推薦算法是將用戶關系融入到現有的協同過濾算法中，以提高算法的準確度。

孫光福等人[14]提出了一種基于用戶間的時序消費行為建模的方法，只需要利用用戶的消費時間先后信息來挖掘用戶之間的相互隱含影響關系，就可以發現對當前用戶影響最大的鄰居集合。

在下面的例子中，形象地說明用戶間的影響關系，如圖1所示。

假設在一定時間段內，用戶甲消費了25個商品，用戶乙消費了85個商品，用戶甲與用戶乙消費商品的并集的個數是100個。根據用戶甲與用戶乙的消費時間先后信息形成序列，在用戶甲與用戶乙共同消費的商品中，有10件商品用戶甲的消費時間比用戶乙要早，即用戶甲先消費然后用戶乙才消費，說明用戶甲對用戶乙有一定的影響力。由此可得用戶甲對用戶乙的影響力為10/100=0.1，同理可得用戶乙對用戶甲的影響力為23/100=0.23。由圖可知，甲與丁、丁與丙、乙與丙以及丙與甲之間的影響關系是單向的，也就是說兩用戶之間的影響關系是不對稱的。那么用戶之間的影響力如公式（3）。

effect（i，j）=wijunionij （3）

其中，對于用戶i與用戶j共同消費過的商品，wij表示用戶i比用戶j先消費的商品數，unionij為用戶i和用戶j所消費商品的并集，effect（i，j）為用戶i對用戶j的有向影響力。根據計算出的影響力大小，可以找出影響力最大的k個鄰居用戶。

2.3Jaccard系數

Jaccard相似性系數也可以用作度量用戶相似性，如公式（4）。

sim（i，j）=Itemi∩ItemjItemi∪Itemj （4）

其中，Itemi、Itemj分別表示用戶i和用戶j評分過的項目集合。

3一種混合相似性的度量方法

3.1改進后的相似性

基于時序行為的最近鄰建模方法是根據用戶消費時間先后信息構建用戶關系網絡圖，計算出用戶之間的相互影響力，可以找到對目標用戶影響最大的鄰居集合。Jaccard系數相似性是通過兩個用戶評分分布來度量兩個用戶之間的相似性，兩用戶共同評分的項目所占的比例越大，相似性越高。以上兩種方法的側重點不同，都在一定程度上提高了推薦質量，筆者希望找到一種融合方法，對上述兩種方法有所發展。

為了進一步提高相似度的準確性，將時序行為影響力融入到基于Jaccard的相似性度量中，得到改進后的用戶相似性如公式（5）。

simfinal（i，j）=αsim（i，j）+（1-α）effect（i，j） （5）

其中，effect（i，j）表示用戶i對用戶j的影響力，sim（i，j）表示用戶i與用戶j基于Jaccard系數的用戶相似性。

改進后的算法融合了兩種相似性度量方法的優點，適用范圍將更廣泛。改進后的方法考慮到不同用戶的關注項目集合的不同對相似性的影響，并且考慮了用戶的消費時間先后信息反映出的用戶間隱含影響關系，增加了度量用戶相似性的信息量，降低了數據稀疏性的影響，提高了相似度的準確性。但改進后的相似性度量方法較基于時序行為的影響力和基于Jaccard系數的相似性復雜，對算法的可擴展性造成一定影響。

3.2算法流程

基于云填充和混合相似性的協同過濾推薦算法的基本思想是：首先利用云模型對用戶-項目評分矩陣進行填充，從而降低數據稀疏性的影響；其次，建立用戶-項目評分時間矩陣，根據用戶對共同評分項目的評分時間先后順序，計算用戶之間的影響力；最后， 將時序行為影響力融入到基于Jaccard系數的相似性度量中，找出最近鄰居，產生推薦結果。

具體步驟如下：

步驟1：利用云模型填充用戶-項目評分矩陣R，得到R；

步驟2：由R根據公式（3）計算出用戶的影響力矩陣effect；

步驟3：由R根據公式（4）計算出基于Jaccard系數的相似性矩陣sim；

步驟4：根據公式（5）計算出改進后的用戶相似性矩陣simfinal；

步驟5：由simfinal計算出用戶k個最近鄰居，根據最近鄰居的偏好為目標用戶進行推薦。

4實驗結果及分析

4.1數據集和推薦質量的評價標準

為了測試改進的推薦算法的有效性，本文采用了GroupLens Research網站提供的包含100000個電影評分數據的MovieLens數據集，涉及943個用戶和1682部電影。該數據集中每個用戶都至少評價過20部電影，其評分值是從1到5的整數，評分數值越高表示用戶對該電影越喜歡。在實驗中，隨機地將80%的數據劃分為訓練集，剩余的20%的數據作為測試集。

常用的推薦質量評估方法有平均絕對誤差（Mean Absolute Error，簡稱MAE）[17]、平均平方誤差和標準平均絕對誤差NMAE[18-19] 。

對于用戶i，平均絕對誤差MAEi公式如式（6）。

MAEi=∑nic=1pic-ricni （6）

其中，ni表示用戶i在測試集中已經評分過的項目的個數（ni≤n），pic、ric分別為用戶i對項目c的預測評分及其對應的實際評分。

對于所有用戶的平均絕對誤差見公式（7），標準平均絕對誤差見公式（8）。

MAE=∑mi=1MAEim （7）

NMAE=MAErmax -rmin （8）

其中，rmax和rmin分別為用戶打分區間的最大值和最小值。

標準平均絕對誤差（NMAE）就是平均絕對誤差在打分值區間內作歸一化，從而方便在不同的數據集上對同一個算法的表現進行比較。NMAE能夠較為直觀地對推薦質量進行評估，容易理解。如果NMAE的值越小，那么推薦的準確性就越高。

4.2實驗結果及分析

實驗1 參數α對算法的影響。

本文中最終相似度由影響力和Jaccard系數兩部分組成，而參數α是平衡兩者的權重。α越大，說明基于Jaccard系數的相似性在最終相似性中的比重越大。實驗首先比較了本文算法在參數α的不同取值下的結果。在實驗中，分別設定了參數α的不同取值α=[0.1，0.2，0.3，0.4，0.5，0.6，0.7，0.8，0.9]，算法的其他參數均設置為使算法最優時的相應值。

比較不同的α值對NMAE值的影響，實驗結果如圖2所示。

根據結果可以看出，參數α對算法有較大的影響，隨著α的增加，本文算法的標準平均絕對誤差NMAE不斷增加，說明了引入基于時序行為的有向影響力對用戶間的相似性有更加重要的影響。同時發現，當α=0.5時變化趨于平緩。

實驗2 最近鄰居個數對算法的影響。

實驗首先比較最近鄰居個數對不同的相似性度量方法的影響。在實驗中，選擇的相似性度量方法分別為本文算法、余弦相似性、修正的余弦相似性、相關相似性。實驗從不同的最近鄰居個數比較算法的推薦質量，測試鄰居個數分別為5、10、15、20、25、30、35，實驗結果如圖3所示。

從實驗結果可以看出：①隨著鄰居個數的增加，在一定程度上增加了運算的復雜度，標準平均絕對誤差NMAE有所上升，當鄰居個數增加到一定的值時這種變化趨于平緩。②本文中改進的相似性度量方法與傳統的相似性度量方法有較大提高，進一步說明基于時序行為的用戶有向影響力與基于Jaccard系數相似性相結合的方法能比較有效提高協同過濾算法的推薦精度。

5結束語

本文對傳統的協同過濾算法中度量用戶間相似性的方法進行改進。首先比較傳統算法中度量用戶間相似性的方法，然后將基于時間序列的用戶間影響力融合到基于Jaccard系數的相似性度量方法中。改進的方法考慮到了用戶共同評分項目個數對相似性的影響，并且考慮了用戶間的隱含影響關系，增加了時效性，從而提高了相似度的準確性，在某種程度上降低了數據稀疏性的影響并且提高了推薦結果的準確性。接下來將會對如何更好地選取參數α以及如何考慮空間、任務等因素更好地完成推薦進行研究。

參考文獻

[1]馬宏偉， 張光衛， 李鵬. 協同過濾推薦算法綜述[J]. 小型微型計算機系統， 2009， 30（7）： 1282-1288.

[2]LIU Q，CHEN E H，XIONG H，et al.Enhancing collaborative filtering by user interests expansion via personalized ranking[J]. IEEE Trans. on Systems， Man and Cybernetics—B， 2012， 42（1）： 218-233.

[3]JANNACH D，ZANKER M，FELFERNING A，et al.推薦系統[M]. 蔣凡，譯. 北京：人民郵電出版社， 2013.

[4]SU J H， YEH H H， YU P S， et al. Music recommendation using content and context information mining[J]. IEEE Intelligent Systems， 2010， 25（1）： 16-26.

[5] 冷亞軍， 陸青， 梁昌勇. 協同過濾推薦技術綜述[J]. 模式識別與人工智能， 2014， 27（8）： 720-734.

[6]王立才， 孟祥武， 張玉潔. 上下文感知推薦系統[J]. 軟件學報， 2012， 23（1）： 1-20.

[7]孟祥武， 胡勛， 王立才， 等. 移動推薦系統及其應用[J]. 軟件學報， 2013， 24（1）： 91-108.

[8]劉建國， 周濤， 郭強， 等. 個性化推薦系統評價方法綜述[J]. 復雜系統與復雜性科學， 2009， 6（3）： 1-10.

[9]張光衛，李德毅，李鵬，等.基于云模型的協同過濾推薦算法[J].軟件學報，2007，18（10）：2403-2411.

[10]毛志勇，趙盼盼.基于云填充和蟻群聚類的協同過濾圖書推薦算法[J].現代情報，2015，35（5）.

[11]李德毅，杜鹢.不確定性人工智能[M].北京：國防工業出版社，2005，143-144.

[12]KOREN Y. Collaborative filtering with temporal dynamics[C].In： Proc. of the ACM SIGKDD Conf. on Knowledge Discovery and Data Mining. ACM Press， 2009. 89-97.

[13]TAN Pangning，STEINBACH M，kUMAR V.數據挖掘導論[M]. 范明， 范宏建， 等， 譯. 北京：人民郵電出版社， 2011.

[14]孫光福，吳樂，劉淇，等.基于時序行為的協同過濾推薦算法[J].軟件學報，2013，24（11）：2721-2733.

[15]劉紅巖. 社會計算：用戶在線行為分析與挖掘[M]. 北京：清華大學出版社， 2014.

[16]郭強， 劉建國. 在線社會系統的用戶行為分析研究進展[J]. 復雜系統與復雜性科學， 2015， 12（2）： 97-102.

[17]孟祥武， 劉樹棟， 張玉潔， 等. 社會化推薦系統研究[J]. 軟件學報， 2015， 26（6）： 1356-1372.

[18]WANG Z，SUN L F，ZHU W W，et al.Joint social and content recommendation for usergenerated videos in online social network[J]. IEEE Trans. on Multimedia， 2013， 15（3）： 698-710.

[19]QUIJANOSANCHEZ L，RECIOGARCIA J， DIAZAGUDO B. Social factors in group recommender systems[J]. ACM Trans. on Intelligent Systems and Technology， 2013， 4（1）： Article No.8.