樊 利 林滿山

（北方工業(yè)大學(xué) 北京 100144）

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

樊 利 林滿山

（北方工業(yè)大學(xué) 北京 100144）

針對(duì)傳統(tǒng)Mahout提供的推薦算法中的噪音數(shù)據(jù)問(wèn)題，提出了用戶信息熵模型。用戶信息熵模型采用了信息論中信息熵的概念，利用信息熵的大小衡量用戶信息的含量，利用用戶評(píng)分?jǐn)?shù)據(jù)得到用戶的信息熵，過(guò)濾信息熵低的用戶以及它們的相關(guān)數(shù)據(jù)，從而達(dá)到過(guò)濾噪音數(shù)據(jù)的目的。利用Mahout提供的推薦算法，即基于用戶的協(xié)同過(guò)濾，基于物品的協(xié)同過(guò)濾以及Slope-One推薦算法對(duì)該模型進(jìn)行驗(yàn)證。實(shí)驗(yàn)結(jié)果表明，該模型可有效過(guò)濾噪音數(shù)據(jù)，并在平均絕對(duì)誤差上有了一定的降低。

噪音數(shù)據(jù)；信息熵模型；Mahout；推薦算法

1 引言

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

2 相關(guān)工作

1）Mahout作為 Apache Software Foundation 的一個(gè)開源項(xiàng)目，提供了大量的輕功能實(shí)現(xiàn)，其中實(shí)現(xiàn)了包括聚類、分類、關(guān)聯(lián)規(guī)則挖掘、回歸、降維、協(xié)同過(guò)濾、進(jìn)化編程、向量相似度計(jì)算、非MapReduce算法、集合方法擴(kuò)展等機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘領(lǐng)域的經(jīng)典算法，通過(guò)使用Apache Hadoop庫(kù)，Mahout可以擴(kuò)展到云中［3］。2008推出的開源Apache Mahout是基于Hadoop分布式框架的機(jī)器學(xué)習(xí)算法庫(kù)。其中cf.taste包實(shí)現(xiàn)了推薦算法引擎，它提供了一套完整的推薦算法工具集，同時(shí)規(guī)范了數(shù)據(jù)結(jié)構(gòu)，并標(biāo)準(zhǔn)化了程序開發(fā)過(guò)程［4］。Mahout是Hadoop的子項(xiàng)目。

Mahout框架包含了一套完整的推薦系統(tǒng)引擎，標(biāo)準(zhǔn)化的數(shù)據(jù)結(jié)構(gòu)，多樣的算法實(shí)現(xiàn)，簡(jiǎn)單的開發(fā)流程。Mahout推薦的推薦系統(tǒng)引擎是模塊化的，分為五個(gè)主要部分組成：數(shù)據(jù)模型，相似度算法，近鄰算法，推薦算法，算法評(píng)分器。

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

由式（1）可知，信息熵H（X）只與變量X的概率分布有關(guān)，而與其具體取值無(wú)關(guān)。這在某種程度上說(shuō)明信息熵能有效地避免噪聲數(shù)據(jù)的干擾，可以有效地過(guò)濾掉評(píng)分系統(tǒng)中評(píng)分信息含量少的用戶。

3）基于用戶的協(xié)同過(guò)濾［5］：它是基于鄰居用戶的興趣愛好預(yù)測(cè)目標(biāo)用戶的興趣偏好。算法先使用統(tǒng)計(jì)技術(shù)尋找與目標(biāo)用戶有相同喜好的鄰居，然后根據(jù)目標(biāo)用戶的鄰居的偏好產(chǎn)生向目標(biāo)用戶的推薦。它的基本原理［8］是利用用戶訪問(wèn)行為的相似性來(lái)互相推薦用戶可能感興趣的資源對(duì)當(dāng)前用戶，系統(tǒng)通過(guò)其歷史訪問(wèn)記錄及特定相似度函數(shù)，計(jì)算出與其訪問(wèn)行為（購(gòu)買的產(chǎn)品集合、訪問(wèn)的網(wǎng)頁(yè)集等）最相近的N個(gè)用戶作為用戶的最近鄰居集，統(tǒng)計(jì)的近鄰用戶訪問(wèn)過(guò)而目標(biāo)用未訪問(wèn)的資源生成候選推薦集，然后計(jì)算候選推薦集中每個(gè)資源對(duì)用戶的推薦度，取其中K個(gè)排在最前面的資源作為用戶的推薦集

4）基于物品的協(xié)同過(guò)濾［7］：基于物品的協(xié)同過(guò)濾算法與基于用戶的協(xié)同過(guò)濾算法很像，將商品和用戶互換。通過(guò)計(jì)算不同用戶對(duì)不同物品的評(píng)分獲得物品間的關(guān)系?；谖锲烽g的關(guān)系對(duì)用戶進(jìn)行相似物品的推薦。這里的評(píng)分代表用戶對(duì)商品的態(tài)度和偏好。簡(jiǎn)單來(lái)說(shuō)就是如果用戶A同時(shí)購(gòu)買了商品1和商品2，那么說(shuō)明商品1和商品2的相關(guān)度較高。當(dāng)用戶B也購(gòu)買了商品1時(shí)，可以推斷他也有購(gòu)買商品2的需求。

5）slope-one推薦算法：Slope One是一系列應(yīng)用于協(xié)同過(guò)濾的算法的統(tǒng)稱。由Daniel Lemire和Anna Maclachlan于2005年發(fā)表的論文中提出。有爭(zhēng)議的是，該算法堪稱基于項(xiàng)目評(píng)價(jià)的non-trivial協(xié)同過(guò)濾算法最簡(jiǎn)潔的形式。該系列算法的簡(jiǎn)潔特性使它們的實(shí)現(xiàn)簡(jiǎn)單而高效，而且其精確度與其它復(fù)雜費(fèi)時(shí)的算法相比也不相上下。

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

3.1 信息熵模型

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

其中C表示評(píng)分區(qū)間數(shù)目，本實(shí)驗(yàn)的數(shù)據(jù)采用5分制，即C=5。 puk是用戶u的評(píng)分落在區(qū)間k的概率，puk的計(jì)算過(guò)程如下

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

3.2 協(xié)同過(guò)濾推薦算法

協(xié)同過(guò)濾推薦算法主要有基于用戶的協(xié)同過(guò)濾，基于item的協(xié)同過(guò)濾以及SlopeOne推薦算法［9］。基于用戶的協(xié)同過(guò)濾，通過(guò)不同用戶對(duì)物品的評(píng)分來(lái)評(píng)測(cè)用戶之間的相似性，基于用戶之間的相似性做出推薦。簡(jiǎn)單來(lái)講就是：給用戶推薦和他興趣相似的其他用戶喜歡的物品。計(jì)算上，就是將一個(gè)用戶對(duì)所有物品的偏好作為一個(gè)向量來(lái)計(jì)算用戶之間的相似度，找到K鄰居后，根據(jù)鄰居的相似度權(quán)重以及他們對(duì)物品的偏好，預(yù)測(cè)當(dāng)前用戶沒(méi)有偏好的未涉及物品，計(jì)算得到一個(gè)排序的物品列表作為推薦?；趇tem的協(xié)同過(guò)濾，通過(guò)用戶對(duì)不同item的評(píng)分來(lái)評(píng)測(cè)item之間的相似性，基于item之間的相似性做出推薦。簡(jiǎn)單來(lái)講就是：給用戶推薦和他之前喜歡的物品相似的物品?；贗temCF的原理和基于UserCF類似，只是在計(jì)算鄰居時(shí)采用物品本身，而不是從用戶的角度，即基于用戶對(duì)物品的偏好找到相似的物品，然后根據(jù)用戶的歷史偏好，推薦相似的物品給他。從計(jì)算的角度看，就是將所有用戶對(duì)某個(gè)物品的偏好作為一個(gè)向量來(lái)計(jì)算物品之間的相似度，得到物品的相似物品后，根據(jù)用戶歷史的偏好預(yù)測(cè)當(dāng)前用戶還沒(méi)有表示偏好的物品，計(jì)算得到一個(gè)排序的物品列表作為推薦。基于物品的協(xié)同過(guò)濾算法可分為三個(gè)步驟，步驟1：建立物品的同現(xiàn)矩陣，按用戶分組，找到每個(gè)用戶所選的物品，單獨(dú)出現(xiàn)計(jì)數(shù)及兩兩一組計(jì)數(shù)。步驟2：建立用戶對(duì)物品的評(píng)分矩陣，按用戶分組，找到每個(gè)用戶所選的物品及評(píng)分。步驟3：矩陣計(jì)算推薦結(jié)果，推薦結(jié)果是同現(xiàn)矩陣和評(píng)分矩陣的乘積，即同現(xiàn)矩陣×評(píng)分矩陣=推薦結(jié)果。SlopeOne是一種簡(jiǎn)單高效的協(xié)同過(guò)濾算法。通過(guò)均差計(jì)算進(jìn)行評(píng)分。其基本思想是采用平均加權(quán)計(jì)算。Slope One的核心優(yōu)勢(shì)是在大規(guī)模的數(shù)據(jù)上，它依然能保證良好的計(jì)算速度和推薦效果。

3.3 Mahout環(huán)境下的推薦開發(fā)模型

圖1 Mahout環(huán)境下的開發(fā)模型

4 實(shí)驗(yàn)與結(jié)果分析

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

首先計(jì)算數(shù)據(jù)集中每一個(gè)用戶的信息熵，得到用戶信息熵分布圖，如圖2所示，橫軸表示數(shù)據(jù)集中用戶的ID，縱軸表示用戶的信息熵值。觀察圖1中用戶的信息熵分布，可以發(fā)現(xiàn)絕大部分用戶的信息熵值大于1.1，可以認(rèn)為信息熵偏低的用戶的評(píng)分?jǐn)?shù)據(jù)為噪音數(shù)據(jù)。

圖2 用戶信息熵分布圖

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

將完成的數(shù)據(jù)集作為新的數(shù)據(jù)集，導(dǎo)入Mahout平臺(tái)下的推薦算法中，進(jìn)行實(shí)驗(yàn)。本次實(shí)驗(yàn)采用的評(píng)價(jià)指標(biāo)是平均絕對(duì)誤差（MAE）。平均絕對(duì)誤差［11］是所有單個(gè)觀測(cè)值與算術(shù)平均值的偏差的絕對(duì)值的平均。與平均誤差相比，平均絕對(duì)誤差由于離差被絕對(duì)值化，不會(huì)出現(xiàn)正負(fù)相抵消的情況，因而，平均絕對(duì)誤差能更好地反映預(yù)測(cè)值誤差的實(shí)際情況。其定義為

其中 fi為預(yù)測(cè)值，yi為真實(shí)值，ei= ||fi-yi為絕對(duì)誤差。

圖3 過(guò)濾后的用戶信息熵分布圖

經(jīng)過(guò)七種算法組合的測(cè)試，平均絕對(duì)誤差有所降低。七種算法組合為

結(jié)果如圖4所示。

圖4 MAE對(duì)比圖

5 結(jié)語(yǔ)

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

［1］許海玲，吳瀟，李曉東，等.互聯(lián)網(wǎng)推薦系統(tǒng)比較研究［J］.軟件學(xué)報(bào)，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，F(xiàn)RIEDMAN E.Mahout in action［M］.USA：Manning，2011：66-86.

［4］朱倩.淺談基于Mahout推薦引擎的構(gòu)建［J］.數(shù)字技術(shù)與應(yīng)用，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］周濤，李華.基于用戶情景的協(xié)同過(guò)濾推薦［J］.計(jì)算機(jī)應(yīng)用，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算法解析與案例實(shí)戰(zhàn)［M］.北京：機(jī)械工業(yè)出版社，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的電子商務(wù)推薦系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)［J］.計(jì)算機(jī)工程與設(shè)計(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日

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