劉江冬　梁剛　馮程　周泓宇

摘要：

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

關(guān)鍵詞：

推薦系統(tǒng)；協(xié)同過濾；噪聲數(shù)據(jù)；數(shù)據(jù)稀疏性；信息熵；時(shí)效性

中圖分類號：

TP181

文獻(xiàn)標(biāo)志碼：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.

英文關(guān)鍵詞Key words：

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

0引言

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

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

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

在利用時(shí)效性解決協(xié)同過濾中數(shù)據(jù)的稀疏性問題方面，文獻(xiàn)[10]提出了一種基于項(xiàng)目時(shí)效性的解決算法，該算法挖掘評分?jǐn)?shù)據(jù)的上下文信息，利用用戶對于項(xiàng)目的評分記錄構(gòu)建項(xiàng)目時(shí)效性模型，為當(dāng)前用戶推薦時(shí)效性高的項(xiàng)目。

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

2系統(tǒng)模型

2.1用戶信息熵模型

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

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

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

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

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

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

其中：C表示評分區(qū)間數(shù)目，在5分制的評分系統(tǒng)中C=5；puk是用戶u的評分落在區(qū)間k的概率。puk的計(jì)算過程如下：

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

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

為了過濾噪聲數(shù)據(jù)，需要確定系統(tǒng)中的信息熵閾值Ht，即當(dāng)H（u）

2.2項(xiàng)目時(shí)效性模型

文獻(xiàn)[10]為緩解數(shù)據(jù)極端稀疏性情況下的冷啟動(dòng)問題，通過評分上下文信息構(gòu)建項(xiàng)目時(shí)效性模型，融合到矩陣分解的推薦過程中，進(jìn)一步提高了矩陣分解算法的推薦性能。

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

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

其中：t表示當(dāng)前時(shí)間；tf表示項(xiàng)目i發(fā)布的時(shí)間；a代表的是信息老化率系數(shù)。

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

3實(shí)驗(yàn)結(jié)果及分析

3.1實(shí)驗(yàn)數(shù)據(jù)集

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

3.2評價(jià)指標(biāo)

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

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

3.3實(shí)驗(yàn)步驟

3.3.1過濾噪聲數(shù)據(jù)

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

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

別設(shè)置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個(gè)值，對于每一個(gè)Ht，通過十折交叉驗(yàn)證得到本文提出的融合用戶信息熵和項(xiàng)目時(shí)效性的矩陣分解（UEITMF）算法對應(yīng)的RMSE值（此時(shí)算法中隱含因子向量維度f取值為50）。不同Ht對應(yīng)的RMSE值如圖2所示。

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

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

3.3.2對比實(shí)驗(yàn)

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

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

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

4結(jié)語

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

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

參考文獻(xiàn)：

[1]

許海玲，吳瀟，李曉東，等.互聯(lián)網(wǎng)推薦系統(tǒng)比較研究[J].軟件學(xué)報(bào)，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]

孟祥武，劉樹棟，張玉潔，等.社會化推薦系統(tǒng)研究[J].軟件學(xué)報(bào)，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ìn).基于時(shí)效性的冷啟動(dòng)解決算法[J].現(xiàn)代計(jì)算機(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.