基于信息熵與Mahout的推薦算法的研究?

樊 利 林滿山

（北方工業大學 北京 100144）

基于信息熵與Mahout的推薦算法的研究?

樊 利 林滿山

（北方工業大學 北京 100144）

針對傳統Mahout提供的推薦算法中的噪音數據問題，提出了用戶信息熵模型。用戶信息熵模型采用了信息論中信息熵的概念，利用信息熵的大小衡量用戶信息的含量，利用用戶評分數據得到用戶的信息熵，過濾信息熵低的用戶以及它們的相關數據，從而達到過濾噪音數據的目的。利用Mahout提供的推薦算法，即基于用戶的協同過濾，基于物品的協同過濾以及Slope-One推薦算法對該模型進行驗證。實驗結果表明，該模型可有效過濾噪音數據，并在平均絕對誤差上有了一定的降低。

噪音數據；信息熵模型；Mahout；推薦算法

1 引言

隨著信息技術的突飛猛進，互聯網技術的朝夕更替，大數據時代的泡沫信息使得大量真實有用的信息被隱藏。過量的信息造成了用戶選擇的困難，使得用戶無法有效獲取自身所需信息，這既是所謂的信息過載問題［1］。數據挖掘中采集的數據可能會有各種噪聲，如缺失數據，或者是異常數據。去噪是非常重要的處理步驟，其目的是在最大化信息量時去除掉不必要的影響。在一般意義上，我們把噪音定義為在數據收集階段收集到的一些可能影響數據分析和解釋結果的偽造數據。在Mahout提供的包括協同過濾在內的多種推薦算法中，噪音數據的問題對算法精確度有著十分重要的影響。我們推斷通過預處理來提高數據質量能夠簡化算法的復雜度，優化系統性能，讓海量數據在“清洗”中得以現出真顏。針對協同過濾中噪音的數據問題，國內外學者進行了廣泛的研究，常見的有基于統計特征、分類和聚類等研究方法。如Bilge等［2］提出二分決策樹的方法，該方法通過迭代執行二分K-means聚類算法生成二分決策樹，從而將水軍賬號和正常用戶聚類到不同的簇，達到過濾噪音數據的目的。然而這些方法都需要較為復雜的模型。本文從信息論角度，根據推薦系統的環境中惡意噪聲的來源即［6］：網絡水軍，用戶過于隨意的評分等得出其評分極端、集中等特征，采用信息熵來衡量用戶評分所含信息量的多少，過濾信息熵較低的用戶，達到過濾噪音數據的目的。

2 相關工作

1）Mahout作為 Apache Software Foundation 的一個開源項目，提供了大量的輕功能實現，其中實現了包括聚類、分類、關聯規則挖掘、回歸、降維、協同過濾、進化編程、向量相似度計算、非MapReduce算法、集合方法擴展等機器學習和數據挖掘領域的經典算法，通過使用Apache Hadoop庫，Mahout可以擴展到云中［3］。2008推出的開源Apache Mahout是基于Hadoop分布式框架的機器學習算法庫。其中cf.taste包實現了推薦算法引擎，它提供了一套完整的推薦算法工具集，同時規范了數據結構，并標準化了程序開發過程［4］。Mahout是Hadoop的子項目。

Mahout框架包含了一套完整的推薦系統引擎，標準化的數據結構，多樣的算法實現，簡單的開發流程。Mahout推薦的推薦系統引擎是模塊化的，分為五個主要部分組成：數據模型，相似度算法，近鄰算法，推薦算法，算法評分器。

2）信息熵：1962年，香農（Claude Shannon）在他著名的論文“通信的數學原理”（The Mathematic Theory of Communication）中提出了“信息熵”的概念，解決了信息的度量問題，它主要通過隨機變量取值的不確定性程度來刻畫信息含量的多少。這里用X表示一個隨機變量，X取值為x的概率用p(x)表示，那么可以用信息熵表示它的不確定性程度，H(X)的計算如式（1）所示：

由式（1）可知，信息熵H（X）只與變量X的概率分布有關，而與其具體取值無關。這在某種程度上說明信息熵能有效地避免噪聲數據的干擾，可以有效地過濾掉評分系統中評分信息含量少的用戶。

3）基于用戶的協同過濾［5］：它是基于鄰居用戶的興趣愛好預測目標用戶的興趣偏好。算法先使用統計技術尋找與目標用戶有相同喜好的鄰居，然后根據目標用戶的鄰居的偏好產生向目標用戶的推薦。它的基本原理［8］是利用用戶訪問行為的相似性來互相推薦用戶可能感興趣的資源對當前用戶，系統通過其歷史訪問記錄及特定相似度函數，計算出與其訪問行為（購買的產品集合、訪問的網頁集等）最相近的N個用戶作為用戶的最近鄰居集，統計的近鄰用戶訪問過而目標用未訪問的資源生成候選推薦集，然后計算候選推薦集中每個資源對用戶的推薦度，取其中K個排在最前面的資源作為用戶的推薦集

4）基于物品的協同過濾［7］：基于物品的協同過濾算法與基于用戶的協同過濾算法很像，將商品和用戶互換。通過計算不同用戶對不同物品的評分獲得物品間的關系。基于物品間的關系對用戶進行相似物品的推薦。這里的評分代表用戶對商品的態度和偏好。簡單來說就是如果用戶A同時購買了商品1和商品2，那么說明商品1和商品2的相關度較高。當用戶B也購買了商品1時，可以推斷他也有購買商品2的需求。

5）slope-one推薦算法：Slope One是一系列應用于協同過濾的算法的統稱。由Daniel Lemire和Anna Maclachlan于2005年發表的論文中提出。有爭議的是，該算法堪稱基于項目評價的non-trivial協同過濾算法最簡潔的形式。該系列算法的簡潔特性使它們的實現簡單而高效，而且其精確度與其它復雜費時的算法相比也不相上下。

3 基于信息熵和Mahout的推薦算法

3.1 信息熵模型

在一般的推薦系統中，通常會包含兩個實體：用戶實體與項目實體，分別表示為U={u1，u2，u3，…，um-1，um} 與 I={i1，i2， i3， …， in-1，in}來表示所有用戶與項目的ID集合，變量m，n分別表示用戶與項目的數目。而我們將用戶對項目的評價數據集表示為一個m×n的矩陣R，rui表示用戶u對項目i的實際評分。為了使Mahout提供的推薦算法的準確度有所提高，我們引入了用戶信息熵模型，對于用戶u，其評分集用Su={s1，s1，s1，…，sp} 來表示，在本文情境下的評分系統，其值域為Sm∈{1 ， 2，3，4，5} ，其中 p= | Su|表示用戶u在系統中產生的評分個數。對于用戶u，由信息熵的定義可對應得到其信息熵為

其中C表示評分區間數目，本實驗的數據采用5分制，即C=5。 puk是用戶u的評分落在區間k的概率，puk的計算過程如下

其中I{*}為指示函數，I{t r ue}=1，I{ f alse}=0。由式（2～3）兩式即可得到用戶的信息熵。為了過濾噪音數據，需要確定系統中的信息熵閾值Ht，即當H(u)＜Ht時，則可以過濾掉u的評分信息，以及在用戶集中過濾該用戶，而Ht的選擇可通過十折交叉驗證法來獲取，Ht的合理選擇對推薦算法的推薦精度有著較大影響。原數據處理完成后，由原始評分矩陣R得到的新的評分矩陣RN，顯而易見RN的數據質量更高。

3.2 協同過濾推薦算法

協同過濾推薦算法主要有基于用戶的協同過濾，基于item的協同過濾以及SlopeOne推薦算法［9］。基于用戶的協同過濾，通過不同用戶對物品的評分來評測用戶之間的相似性，基于用戶之間的相似性做出推薦。簡單來講就是：給用戶推薦和他興趣相似的其他用戶喜歡的物品。計算上，就是將一個用戶對所有物品的偏好作為一個向量來計算用戶之間的相似度，找到K鄰居后，根據鄰居的相似度權重以及他們對物品的偏好，預測當前用戶沒有偏好的未涉及物品，計算得到一個排序的物品列表作為推薦。基于item的協同過濾，通過用戶對不同item的評分來評測item之間的相似性，基于item之間的相似性做出推薦。簡單來講就是：給用戶推薦和他之前喜歡的物品相似的物品。基于ItemCF的原理和基于UserCF類似，只是在計算鄰居時采用物品本身，而不是從用戶的角度，即基于用戶對物品的偏好找到相似的物品，然后根據用戶的歷史偏好，推薦相似的物品給他。從計算的角度看，就是將所有用戶對某個物品的偏好作為一個向量來計算物品之間的相似度，得到物品的相似物品后，根據用戶歷史的偏好預測當前用戶還沒有表示偏好的物品，計算得到一個排序的物品列表作為推薦。基于物品的協同過濾算法可分為三個步驟，步驟1：建立物品的同現矩陣，按用戶分組，找到每個用戶所選的物品，單獨出現計數及兩兩一組計數。步驟2：建立用戶對物品的評分矩陣，按用戶分組，找到每個用戶所選的物品及評分。步驟3：矩陣計算推薦結果，推薦結果是同現矩陣和評分矩陣的乘積，即同現矩陣×評分矩陣=推薦結果。SlopeOne是一種簡單高效的協同過濾算法。通過均差計算進行評分。其基本思想是采用平均加權計算。Slope One的核心優勢是在大規模的數據上，它依然能保證良好的計算速度和推薦效果。

3.3 Mahout環境下的推薦開發模型

圖1 Mahout環境下的開發模型

4 實驗與結果分析

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

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

圖2 用戶信息熵分布圖

為了過濾噪音數據，對信息熵的閾值Ht，我們選取了0、0.5、0.8、1.0、1.1、1.2、1.3、1.4這八個值，對每一個值通過十折交叉驗證法結合本文提到的Mahout提供的協同過濾推薦算法進行驗證，對其均方誤差和召回率、準確率做了對比，驗證可得在Ht=1.3時，均方誤差較小，召回率、準確率最好，Ht=1.4時，均方誤差最小，但召回率［10］有所降低。

將完成的數據集作為新的數據集，導入Mahout平臺下的推薦算法中，進行實驗。本次實驗采用的評價指標是平均絕對誤差（MAE）。平均絕對誤差［11］是所有單個觀測值與算術平均值的偏差的絕對值的平均。與平均誤差相比，平均絕對誤差由于離差被絕對值化，不會出現正負相抵消的情況，因而，平均絕對誤差能更好地反映預測值誤差的實際情況。其定義為

其中 fi為預測值，yi為真實值，ei= ||fi-yi為絕對誤差。

圖3 過濾后的用戶信息熵分布圖

經過七種算法組合的測試，平均絕對誤差有所降低。七種算法組合為

結果如圖4所示。

圖4 MAE對比圖

5 結語

本文提出了用戶信息熵模型，解決了一般協同過濾推薦算法中存在的噪音數據問題，同時將用戶信息熵模型應用于Mahout平臺下的推薦推薦算法，利用該平臺提供的多種推薦算法的的組合對該模型進行驗證實驗結果表明該模型在平均絕對誤差上有著良好的表現。然而在過濾噪音數據的過程中，采取的是直接刪除噪音數據用戶的方式，但是其中不可避免地存在誤分類的正常用戶，如何能夠降低誤識率是進一步的研究方向。

［1］許海玲，吳瀟，李曉東，等.互聯網推薦系統比較研究［J］.軟件學報，2009，20（2）：350-362.XU Hailing，WU Xiao，LI Xiaodong，et al.Comparisonstudy of Internet recommendation system［J］.Journal of Software，2009，20（2）：350-362.

［2］ALPER B，ZEYNEP O，HUSEYIN P.A novel shilling attack detection method［J］.Procedia Computer Science，2014，31：165-174.

［3］ANIL R，DUNNING T，FRIEDMAN E.Mahout in action［M］.USA：Manning，2011：66-86.

［4］朱倩.淺談基于Mahout推薦引擎的構建［J］.數字技術與應用，2015（4）：44-45.ZHU Qian.Discussion on the construction of the recommendation engine based on Mahout［J］.Digital technology and Application，2015（4）：44-45.

［5］周濤，李華.基于用戶情景的協同過濾推薦［J］.計算機應用，2010（4）：1076-1082.ZHOU Tao，LI Hua.User context based Collaborative Filtering recommendation［J］.Journal of Computer Applications，2010（4）：1076-1082.

［6］CHIRITA P A，NEJDL W，ZAMFIR C.Preventing shilling attacks in online recommender systems［C］//WIDM 2005：Proceedings of the 2005 7th annual ACM international workshop on Web information and data management.New York：ACM，2005：67-74.

［7］樊哲.Mahout算法解析與案例實戰［M］.北京：機械工業出版社，2015：412-116.FAN Zhe.Mahout in Action：Algorithm and Cases［M］.Beijing：China Machine Press，2015：412-116.

［8］ ARM.Cortex-M0+Technical Reference Manual Rev．r0p0［R.2012.

［9］ KOREN Y.Factorizationmeetstheneighborhood：Amulti-faceted collaborativefilteringmodel［C］//Proceedingsofthe14th ACM SIGKDD International Conference onKnowledge Discovery and Data Mining.NewYork：ACM，2008：426-434.

［10］SONG J，LEE S，KIM J.Spam filtering in Twitter using sender-receiver relationship［C］//RAID 2011：Proceedings of the 2011 Recent Advances in Intrusion Detection.Heidelberg：Springer-Verlag，2011，301-317.

［11］李文海，許舒人.基于Hadoop的電子商務推薦系統的設計與實現［J］.計算機工程與設計，2014（1）：130-143.LI Wenhai，XU Shuren.Design and implementation of recommendation system for E-commerce on Hadoop［J］.Computer Engineering and Design，2014（1）：130-143.

Research on Recommendation Algorithm Based on Information Entropy and Mahout

FAN LiLIN Manshan
（North China University of Technology，Beijing 100144）

Aiming at the noise data problem in recommendation algorithm offered by Mahout，the user entropy model is put forward.The user entropy model combines the concept of entropy in the information theory and uses the information entropy to measure the content of user information，which filters the noise data by calculating the entropy of users and getting rid of the users with low entropy.The proposed model is validated by using Mahout algorithm including user based collaborative filtering，collaborative filtering based on articles and Slope-One recommendation algorithm.The experimental results show that the proposed model can effectively filter out noise data，and the mean absolute error hava been decreased.

noisedata，information entropy model，Mahout，recommendation

TP301

10.3969/j.issn.1672-9722.2017.10.003

Class Number TP301

2017年4月7日，

2017年5月11日

樊利，女，碩士研究生，研究方向：數據挖掘。林滿山，男，高級工程師，研究方向：數據挖掘。