基于信息熵和時效性的協同過濾推薦

劉江冬　梁剛　馮程　周泓宇

摘要：

針對協同過濾推薦算法存在的噪聲數據問題，提出了用戶信息熵模型。用戶信息熵模型結合信息論中信息熵的概念，采用信息熵的大小衡量用戶信息的含量，利用用戶評分數據得到用戶的信息熵，過濾信息熵低的用戶，從而達到過濾噪聲數據的目的。同時，將用戶信息熵模型和項目時效性模型相結合，項目時效性模型利用評分數據上下文信息獲得項目的時效性，能有效緩解協同過濾的數據稀疏性問題。實驗結果表明提出的算法能有效過濾噪聲數據，提高推薦精度，與基礎算法相比，推薦精度提高了1.1%左右。

關鍵詞：

推薦系統；協同過濾；噪聲數據；數據稀疏性；信息熵；時效性

中圖分類號：

TP181

文獻標志碼：A

Abstract：

Aiming at the noise data problem in collaborative filtering recommendation， a user entropy model was put forward. The user entropy model combined the concept of entropy in the information theory and used the information entropy to measure the content of user information， which filtered the noise data by calculating the entropy of users and getting rid of the users with low entropy. Meanwhile， combining the user entropy model with the item timeliness model， the item timeliness model got the timeliness of item by using the contextual information of the rating data， which alleviated the data sparsity problem in collaborative filtering algorithm. The experimental results show that the proposed algorithm can effectively filter out noise data and improve the recommendation accuracy， its recommendation precision is increased by about 1.1% compared with the basic algorithm.

英文關鍵詞Key words：

recommender system； collaborative filtering； noise data； data sparsity； information entropy； timeliness

0引言

隨著互聯網技術日新月異的發展，互聯網上擁有海量的信息，過量的信息造成了用戶選擇的困難，使得用戶無法有效獲取自身所需信息，這便是所謂的信息過載問題[1]。目前，解決信息過載問題的技術主要分兩類：第一類是以搜索引擎為代表的信息檢索技術；第二類是以推薦系統[2]為代表的信息過濾技術。搜索引擎在當今獲取網絡信息方面占據了十分重要的地位，它根據用戶提供的關鍵字匹配信息，匹配結果的好壞很大程度上依賴于用戶對信息描述的精準程度，且對于同樣的檢索輸入始終會展現同樣的搜索結果，無法實現用戶個性化的需求。與搜索引擎技術不同的是，推薦系統能夠通過分析用戶的歷史交易記錄或行為挖掘用戶興趣，自動為用戶產生滿足用戶興趣和需求的推薦。

推薦系統作為解決信息過載問題的一項重要技術，被廣泛應用到電子商務、社交網站等互聯網平臺，已成為Web 2.0應用中不可或缺的個性化信息服務形式。協同過濾算法[3]是一類重要的推薦算法，其實現簡單，無需獲取項目內容信息，推薦效果好，因而被廣泛地研究和應用，已成為Amazon、淘寶網、京東網和當當網等電子商務平臺廣泛采用的商品信息推薦方法。協同過濾的基本思想是相似用戶具有相同的興趣偏好，它首先根據用戶評分信息計算用戶之間的相似性，找出一組相似性最高的用戶作為鄰居用戶，然后根據鄰居用戶加權計算目標用戶對于還未產生評分的項目的預測評分，進而產生推薦；但協同過濾技術存在噪聲數據和數據稀疏性等問題，影響了其推薦結果的精確度[4]。推薦系統中的噪聲數據主要來源于兩方面：一是那些由商業利益驅動，為達到影響網絡民意、擾亂網絡環境等不正當目的，通過操縱軟件機器人或水軍賬號，在互聯網中制造和傳播的虛假意見和評分[5-6]；二是系統中部分真實用戶過于隨意的評分行為也會產生噪聲數據[7]，例如有些用戶習慣性地對所有商品都給最高評分或最低評分。評分數據非常稀疏往往是由于實際網站中項目的數量龐大且不斷增加，而用戶通常只對一小部分項目評分，一般不超過系統中項目總數的1%。

針對協同過濾中噪聲數據的問題，國內外學者進行了廣泛的研究，常見的有基于統計特征、分類和聚類等研究方法。Chirita等[7]分析了惡意用戶的評分行為統計特征，如用戶評分標準偏差（Standard Deviation in Users Ratings）和TopN相似用戶的平均相似度（Degree of Similarity with Top Neighbors）等特征，再利用這些統計特征來構建分類模型識別惡意用戶；Bilge等[8]提出二分決策樹的方法，該方法通過迭代執行二分Kmeans聚類算法生成二分決策樹，從而將水軍賬號和正常用戶聚類到不同的簇，達到過濾噪聲數據的目的；Cao等[9]提出一種新的半監督學習算法（SemiShilling Attack Detection， SemiSAD），該算法先在少量有標記的用戶集中訓練得到一個貝葉斯分類器（Bayes），然后在大量無標記的用戶集中采用期望最大化（Expectation Maximization， EM）算法優化初始得到的貝葉斯分類器。以上這些研究方法都采用了機器學習的相關算法，也能取得比較好的效果，但是都需要訓練出復雜的模型。本文從信息論的角度，根據文獻[7]中指出的水軍用戶具有評分集中性、評分極端性和針對特定目標等特征，直接采用信息熵衡量用戶評分所含信息量的多少，過濾信息熵低的用戶，達到過濾噪聲數據的目的。

在利用時效性解決協同過濾中數據的稀疏性問題方面，文獻[10]提出了一種基于項目時效性的解決算法，該算法挖掘評分數據的上下文信息，利用用戶對于項目的評分記錄構建項目時效性模型，為當前用戶推薦時效性高的項目。

為進一步提高推薦系統性能，本文綜合考慮用戶信息熵模型和項目時效性模型，提出了融合用戶信息熵和項目時效性的矩陣分解算法（Matrix Factorization combining User Entropy and Item Timeliness， UEITMF），進一步提高了推薦系統的推薦精度。

2系統模型

2.1用戶信息熵模型

1962年，香農（Claude Shannon）在他著名的論文“通信的數學原理”（The Mathematic Theory of Communication）中提出了“信息熵”的概念，解決了信息的度量問題，它主要通過隨機變量取值的不確定性程度來刻畫信息含量的多少[12]。

這里用X表示一個隨機變量，X取值為x的概率用p（x）表示，那么可以用信息熵表示它的不確定性程度，H（X）的計算如式（1）所示：

H（X）=-∫xp（x） lb p（x）dx（1）

由式（1）可知，信息熵H（X）只與變量X的概率分布有關，而與其具體取值無關。這在某種程度上說明信息熵能有效地避免噪聲數據的干擾，可以有效地過濾掉評分系統中評分信息含量少的用戶。系統中的用戶對推薦引擎的作用效果不同，有的用戶提供的評分所含的信息量多些，而有的少些，因而有效地過濾信息量少的用戶可以有效提升推薦精度。

本文為了在推薦系統中引入用戶信息熵模型，對于用戶u，其評分集合用Ru={r1，r2，…，rm，…，rp}表示，在1到5分的評分系統中rm∈{1，2，3，4，5}，其中p=Ru表示用戶u在系統中產生的評分數。對用戶u，根據式（1），其信息熵為：

H（u）=∑Ck=1-puk lb（puk）（2）

其中：C表示評分區間數目，在5分制的評分系統中C=5；puk是用戶u的評分落在區間k的概率。puk的計算過程如下：

puk=[∑rm∈RuI{rm=k}]/Ru；k∈{1，2，3，4，5}（3）

其中：I{*}為指示函數，I{true}=1，I{false}=0。聯合式（2）和式（3）即可根據用戶的評分值計算其信息熵。本文從信息論的角度，根據產生噪聲數據的水軍用戶或少量正常用戶具有評分集中性、評分極端性等特征，直接采用信息熵衡量用戶評分所含信息量的多少，過濾信息熵低的用戶，達到過濾噪聲數據的目的。例如，在1到5分的評分系統中，用戶u評價了20個項目，評分從1到5分別有4個，則其信息熵H（u）=∑51-420 lb（420）≈2.32，其信息熵達到最大值，因為其評分均勻分布，可以表示其對于相應項目的評分更加謹慎和客觀。再看一種極端情況，用戶u對所有項目的評分都為1分，即pu1=1，代入公式計算可得H（u）=0，所以用戶信息熵達到最低值，屬于噪聲數據，從直觀上也可以看出這個用戶的評分行為過于隨意和極端，可信度較低。

為了過濾噪聲數據，需要確定系統中的信息熵閾值Ht，即當H（u）

2.2項目時效性模型

文獻[10]為緩解數據極端稀疏性情況下的冷啟動問題，通過評分上下文信息構建項目時效性模型，融合到矩陣分解的推薦過程中，進一步提高了矩陣分解算法的推薦性能。

將所有用戶對項目的評分記錄作為考察集S，把集合S以項目為單位進行子集劃分，從而將集合S劃分成一系列的子集si。對于項目i，si={t1，t2，t3，…，tk，…，tq}，其中q表示系統中對項目i產生過評分行為的用戶數，tk表示某用戶對項目i產生評分行為的具體時刻，在t時刻項目i的時效性表示為Ci（t），其計算式如下：

Ci（t）=e-a（t-tf）（4）

其中：t表示當前時間；tf表示項目i發布的時間；a代表的是信息老化率系數。

本文將用戶信息熵模型和項目時效性模型融合到矩陣分解法中，融合了用戶信息熵模型和項目時效性模型的損失函數為：

3實驗結果及分析

3.1實驗數據集

本文采用的實驗數據為MovieLens（1M）數據集，該數據集由明尼蘇達大學（University of Minnesota）GroupLens研究院小組提供，其中包含6040名用戶和3900部電影，用戶評分范圍為1～5分，每位用戶至少對20部不同的電影進行過評分，總的評分次數為1000209次。數據集的每一行（rating.dat）由用戶ID、項目ID、項目評分值與評分時間4個字段構成，數據集被隨機分為訓練集和測試集。

3.2評價指標

本文實驗算法的評價標準為均方根誤差（Root Mean Squared Error， RMSE），它通過計算預測的用戶評分與實際的用戶評分之間的偏差來度量預測的準確性。RMSE能夠直觀地衡量推薦質量，是最常用的一種推薦質量度量方法，在Netflix大賽中被廣泛采用。推薦算法整體RMSE越小，則推薦的質量越高。測試數據集用RT表示，rui∈RT表示用戶u對項目i的實際評分，ui表示推薦系統中用戶u對于項目i的預測評分，RMSE的計算為式（8）：

RMSE=[∑rui∈RT（rui-ui）2]/RT（8）

3.3實驗步驟

3.3.1過濾噪聲數據

首先計算數據集中每一個用戶的信息熵，得到用戶信息熵分布圖，如圖1所示，橫軸表示數據集中用戶的ID，縱軸表示用戶的信息熵值。觀察圖1中用戶的信息熵分布，可以發現絕大部分用戶的信息熵值大于1.0，可以認為信息熵偏低的用戶的評分數據為噪聲數據。

為了過濾噪聲數據，需要確定信息熵閾值Ht，合理地選擇信息熵閾值，對于提高最終的推薦精度有很大影響。本文分

別設置Ht為0，0.5，0.6，0.7，0.8，0.9，1.0，1.1，1.2，1.3，1.4，1.5這12個值，對于每一個Ht，通過十折交叉驗證得到本文提出的融合用戶信息熵和項目時效性的矩陣分解（UEITMF）算法對應的RMSE值（此時算法中隱含因子向量維度f取值為50）。不同Ht對應的RMSE值如圖2所示。

觀察圖2，當信息熵閾值Ht取為1.1左右時，UEITMF算法的RMSE值達到最小值，這也與圖1中用戶的信息熵分布圖相吻合，圖1中絕大部分用戶的信息熵值都分布在1.1以上，所以信息熵值低于1.1的用戶評分數據即可以認為是噪聲數據，過濾這部分噪聲數據可以有效地提高推薦精度。當Ht取值小于1.1時，隨著Ht的增加，RMSE值逐漸減小，這說明在一定范圍內，過濾的噪聲數據越多，越能有效提高推薦精度。當Ht取值大于1.1時，隨著Ht的增加，RMSE值快速地增長，這是因為當信息熵閾值過大時，在過濾掉噪聲數據的同時，也會大量地丟失正常用戶評分數據，進一步加劇數據的稀疏性，從而使得算法的RMSE值偏大。對于不同的數據集，用戶的信息熵會有不同的分布，達到最優效果的信息熵閾值也會不同，所以信息熵閾值的選取要考察實際的數據集。

對過濾的噪聲數據進行統計分析，可以得到所有噪聲數據用戶的評分總次數為1957次，其中評分為5分的次數是1279次，評分為4分的次數是366次，評分為1分的次數是255次，所以評分為5分、4分和1分的總次數有1900次，占到噪聲數據評分總次數的97%，這充分說明了噪聲數據用戶具有評分極端性的特征。這些極端的評分對于推薦算法具有更大的影響，因而有效過濾這部分數據能夠提高推薦精度。

3.3.2對比實驗

為了充分考察本文提出的融合用戶信息熵和項目時效性的矩陣分解算法（UEITMF）的有效性，本文將UEITMF算法與文獻[10]中提出的基于項目時效性的冷啟動解決（Timelinessbased Algorithm for Cold Start， TACS）算法，以及帶有偏項的矩陣分解 （Matrix Factorization combining Biases， BMF）算法[11]進行對比實驗。在矩陣分解算法中，用戶和項

目隱含因子向量維度f的選擇對于實驗精度有重大影響，本文分別選取f值為10、20、50、80、100進行對比實驗（UEITMF算法中Ht取值均為1.1），這里訓練集占80%，測試集占20%，實驗結果如表2所示。

觀察表2可得，在相同f取值下，RMSE取值由小到大依次為UEITMF、TACS和BMF，說明本文提出的UEITMF算法能有效提高推薦精度，在f依次取值為10、20、50、80、100時，UEITMF相對于BMF的精度提升依次為1.08%、1.03%、1.07%、1.09%、1.09%（精度提升的計算公式為（BMF-UEITMF）/BMF×100% ，BMF和UEITMF分別代表在同樣的f下對應的RMSE值），這些數值說明在不同的隱含因子維度f取值下UEITMF的精度提升在一定范圍內是穩定的。進一步觀察表2中數據可得，在同等f取值下，UEITMF相對于TACS的精度提升基本上都大于TACS相對于BMF的精度提升，這說明噪聲數據對于精度提升有更大的影響。

4結語

本文提出了用戶信息熵模型，解決了協同過濾推薦中存在的噪聲數據問題，同時將用戶信息熵模型和項目時效性模型相結合，提出融合用戶信息熵和項目時效性的矩陣分解算法，實驗結果表明本文提出的算法能有效提高推薦精度。

在過濾噪聲數據的過程中，采取的是直接刪除噪聲數據用戶的方式，但是其中不可避免地存在誤分類的正常用戶，如何既為噪聲數據用戶產生推薦同時又消除噪聲數據對于推薦結果的影響，是進一步的研究方向。

參考文獻：

[1]

許海玲，吳瀟，李曉東，等.互聯網推薦系統比較研究[J].軟件學報，2009，20（2）：350-362.（XU H L， WU X， LI X D， et al. Comparison study of Internet recommendation system [J]. Journal of Software， 2009， 20（2）： 350-362.）

[2]

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

[3]

CHU W， PARK S T. Personalized recommendation on dynamic contents using predictive bilinear models [C]// WWW 2009： Proceedings of the 2009 18th International Conference on World Wide Web. New York： ACM， 2009： 691-700.

[4]

孟祥武，劉樹棟，張玉潔，等.社會化推薦系統研究[J].軟件學報，2015，26（6）：1356-1372.（MENG X W， LIU S D， ZHANG Y J， et al. Research on social recommender systems [J]. Journal of Software， 2015， 26（6）： 1356-1372.）

[5]

WANG G， XIE S， LIU B， et al. Review graph based online store review spammer detection [C]// ICDM 2011： Proceedings of the 2011 International Conference on Data Mining. Washington， DC： IEEE Computer Society， 2011： 1242-1247.

[6]

SONG J， LEE S， KIM J. Spam filtering in twitter using senderreceiver relationship [C]// RAID 11： Proceedings of the 2011 14th International Conference on Recent Advances in Intrusion Detection. Berlin： Springer， 2011： 301-317.

[7]

CHIRITA P A， NEJDL W， ZAMFIR C. Preventing shilling attacks in online recommender systems [C]// WIDM 05： Proceedings of the 2005 7th Annual ACM International Workshop on Web Information and Data Management. New York： ACM， 2005： 67-74.

[8]

BILGE A， ZDEMIR Z， POLAT H. A novel shilling attack detection method [J]. Procedia Computer Science， 2014， 31： 165-174.

[9]

CAO J， WU Z， MAO B， et al. Shilling attack detection utilizing semisupervised learning method for collaborative recommender system [J]. World Wide Web， 2013， 16（5/6）： 729-748.

[10]

劉江冬，梁剛，楊進.基于時效性的冷啟動解決算法[J].現代計算機，2016（2）：3-6. （LIU J D， LIANG G， YANG J. Timelinessbased algorithm for cold start [J]. Modern Computer， 2016（2）： 3-6.）

[11]

KOREN Y， BELL R， VOLINSKY C. Matrix factorization techniques for recommender systems [J]. Computer， 2009， 42（8）： 30-37.