黃 皓，陳 荔

(上海理工大學管理學院, 上海 200240)

0 引 言

隨著互聯(lián)網(wǎng)的高速發(fā)展，信息的產(chǎn)生呈現(xiàn)了一種爆炸增長速度，造成了信息過載現(xiàn)象。信息過載是指數(shù)據(jù)過量，它導致的后果使得用戶難以在短時間內(nèi)接收到某一方面的全部相關(guān)信息，可能會使用戶在信息接收不全面的情況下造成錯誤的決定。當今社會解決此問題的主流方法有以下2種：第一類是以推薦系統(tǒng)為代表的信息過濾技術(shù)；第二類是谷歌百度等搜索引擎主要使用的信息檢索技術(shù)。但搜索引擎存在的最大問題是它很難提供個性化的推薦，它的主要方法是由用戶提供精準的文字來進行查找。相反，推薦系統(tǒng)使用用戶的歷史信息(比如購買、評分信息等)來推薦用戶潛在的需要信息，它能夠為用戶提供更加精準的服務。

協(xié)同過濾算法作為推薦系統(tǒng)最常用的方法，它也存在自己的問題：一是噪音數(shù)據(jù)，大規(guī)模地人為捏造數(shù)據(jù)等行為會造成數(shù)據(jù)的失真；二是數(shù)據(jù)稀疏性，隨著現(xiàn)代互聯(lián)網(wǎng)的發(fā)展，數(shù)據(jù)的數(shù)目一般是上千萬，但用戶評分的商品常常很少，導致評分矩陣中大量的空白，導致典型的類似數(shù)據(jù)集都相當稀疏。

國內(nèi)外在改進相似度上進行了很深的研究。蘇慶等[1]針對數(shù)據(jù)稀疏和準確率相對較低原因，提出了改進模糊劃分聚類的協(xié)同過濾算法(GIFP-CCF+),使用了時間差因子、熱門物品權(quán)重因子和冷門物品權(quán)重因子相結(jié)合的相似度計算結(jié)果，結(jié)合改進模糊劃分的算法。王運等[2]針對數(shù)據(jù)稀疏和評分項目差異的問題，提出了FunkSVD矩陣分解和相似度矩陣結(jié)合的推薦算法，利用相似度矩陣和FunkSVD生成新的用戶相似度矩陣。李容等[3]針對傳統(tǒng)相似度忽略共同評分和稀疏數(shù)據(jù)的問題，提出了一種2個修正因子的改進相似度推薦算法，同時改進了協(xié)同過濾算法。王留芳等[4]針對稀疏數(shù)據(jù)和冷啟動問題，提出了一種修正余弦相似度和用戶屬性的相似度算法加權(quán)混合的協(xié)同過濾算法。薛亞非[5]針對算法準確率低和耗時長的問題，提出了基于相似度的多重信息協(xié)同過濾算法，利用加權(quán)信息熵計算興趣相似度將其和評分矩陣相結(jié)合，獲得最終的相似度。刑長征等[6]針對稀疏的用戶評分矩陣方法，提出了一種改進的填補法和改進相似度相結(jié)合的推薦算法。羅辛等[7]針對k近鄰法的不足提出了一種相似度支持度優(yōu)化基于k近鄰的推薦算法。

協(xié)同過濾算法作為常用的推薦算法，研究者也非常多。王玉珍等[8]為了減小算法的誤差，提高推薦的效率和質(zhì)量，提出了一種SGA-RBF遺傳算法優(yōu)化的神經(jīng)網(wǎng)絡與協(xié)同過濾算法相結(jié)合的推薦算法，使結(jié)果更加精確。王努努[9]針對用戶偏好挖掘不全面、冷啟動、數(shù)據(jù)稀疏的問題，提出了基于Softmax回歸和矩陣分解協(xié)同過濾算法，利用文本挖掘技術(shù)進行特征的情感強度分析，利用該算法進行運算。趙宇等[10]為了提高算法的精確度，提出馬爾可夫聚類和混合協(xié)同過濾的協(xié)同過濾算法，利用馬爾可夫聚類將人群劃分為不同人群然后挖掘不同人群的特征。岳希等[11]針對數(shù)據(jù)稀疏性，提出了一種將基于用戶和基于項目相結(jié)合的推薦方法。羅園等[12]提出了一種考慮到用戶興趣變化和用戶標注信息的推薦算法，引入了遺忘曲線、文本挖掘技術(shù)TF-IDF和混合余弦相似度和改進皮爾遜相似度的方法。袁泉等[13]針對算法只能考慮外部評價不能考慮電影內(nèi)部的相似度關(guān)系，提出構(gòu)建知識圖譜輔助計算電影內(nèi)部的相似度方法，并且引入了TransE模型和TransHR模型然后將使用混合相似度計算方法。劉國麗等[14]針對冷啟動、數(shù)據(jù)稀疏、可擴展性不高和不同社區(qū)簇之間存在相關(guān)性的問題，提出在考慮同社區(qū)簇內(nèi)專家信任基礎上結(jié)合不同社區(qū)簇專家信任的算法，將專家機制和推薦算法相結(jié)合提高算法的精確性。崔巖等[15]為了提高算法準確性，提出了XGBoost和協(xié)同過濾算法相結(jié)合的推薦算法，采用百度深度學習框架進行實驗。王井[16]為了給讀者提供優(yōu)質(zhì)服務，提出了一種基于訂閱記錄的圖書協(xié)同過濾算法，引入對訂閱權(quán)重的懲罰機制，增加了熱門訂閱的權(quán)重。張鋒等[17]針對推薦算法中數(shù)據(jù)稀疏的問題，將BP神經(jīng)網(wǎng)絡加入?yún)f(xié)同過濾算法中，避免了常規(guī)降維法的缺點也緩解了數(shù)據(jù)稀疏的問題。辛菊琴[18]提出了一種融合用戶偏好和BP神經(jīng)網(wǎng)絡的推薦算法，在MovieLens數(shù)據(jù)集上得到了很好的效果。楊遠奇[19]將注意力機制的神經(jīng)網(wǎng)絡算法和網(wǎng)絡中群組成員的個性化偏好相結(jié)合，更加突出用戶的個性化特征，加強了算法的準確性。張艷紅等[20]針對噪音數(shù)據(jù)和數(shù)據(jù)稀疏的問題，提出了一種基于噪音檢測修正和神經(jīng)網(wǎng)絡的top-k推薦算法，檢測用戶評分矩陣的奇異點，對奇異點進行修正處理，使用神經(jīng)網(wǎng)絡緩解數(shù)據(jù)稀疏問題。

國內(nèi)外關(guān)于信息熵方面的研究也有很多。劉江冬等[21]將信息熵和時效性結(jié)合同時解決了噪音問題和數(shù)據(jù)稀疏性問題；蘇夢珂等[22]提出了一種考慮信息熵和用戶行為一致性的算法，用信息熵解決噪音數(shù)據(jù)，考慮用戶行為的一致性將用戶分組來提高精確度。

本文從信息熵解決噪音數(shù)據(jù)角度，設計一種基于信息熵和面向數(shù)據(jù)稀疏的相似度的協(xié)同過濾算法，這種算法同時解決了噪音數(shù)據(jù)和數(shù)據(jù)稀疏性這2個協(xié)同過濾算法中比較重要的問題，提高了推薦算法的準確性。

1 相關(guān)工作

1.1 協(xié)同過濾算法

協(xié)同過濾算法是推薦算法中應用最廣泛的一個大類，在工業(yè)界等方面得到了廣泛應用?，F(xiàn)在的協(xié)同過濾算法細分為2個類別：基于模型的協(xié)同過濾和基于內(nèi)存的協(xié)同過濾。基于模型的協(xié)同過濾算法采用概率統(tǒng)計模型和機器學習等方式來解決問題，常見的有：非常熱門的矩陣分解、貝葉斯模型、隱語義模型等?；趦?nèi)存的協(xié)同過濾主要通過用戶評分矩陣計算相似度，然后找到它的鄰居，以此來推薦。它主要分為2大類：基于項目的協(xié)同過濾(item-cf)和基于用戶的協(xié)同過濾(user-cf)。而本文用的是基于用戶的協(xié)同過濾算法。常見的基于用戶的協(xié)同過濾算法一般情況下有3個步驟：形成用戶-項目評分矩陣、計算相似度尋找最近鄰集合N和依據(jù)相似度求未知項評分。以下是每一部分的具體過程。

1)形成用戶-評分矩陣。

用戶評分矩陣通常是用戶對項目的評分歷史記錄，可以表現(xiàn)用戶的興趣所在。設矩陣R為用戶-評分矩陣，R是一個m×n的矩陣。其中m表示顧客的數(shù)量，用戶集合U表示為U={u1,u2,…,um}。其中n表示項目的數(shù)量，項目集合I表示為I={i1,i2,…,in}。用戶a對項目b的評分分數(shù)由sab表示。具體表示見表1。

表1 用戶-評分矩陣R

2)計算相似度尋找最近鄰集合N。

在第二步尋找近鄰集合N的過程中，根據(jù)用戶評分矩陣R計算相似度，但相似度計算方法有多種，而每一種方法的效果不盡相同。所以選擇何種方法計算相似度是一門功夫。在下一節(jié)中會具體介紹不同的相似度以及它的具體計算公式。根據(jù)相關(guān)論文表明,在user-cf中，皮爾遜相似度計算方法的效果相比其他的計算方法更勝一籌。計算完相似度之后將通過排序取出前K個近鄰構(gòu)成最近鄰集合N，N=(n1,n2,n3,…,nK)。因為K不是一個確定的值，所以在第二章中會具體分析K的取值對結(jié)果的影響。

3)依據(jù)相似度求未知項評分。

在第2步中通過計算相似度找到近鄰集合N，在最后一步中要根據(jù)近鄰和相似度計算出最終的未知項評分。它的計算公式如下:

(1)

1.2 傳統(tǒng)相似度計算方法

在大部分協(xié)同過濾算法中，計算相似度可以說是算法的核心步驟。常見的相似度計算方法有以下幾種：

1)余弦相似度。

(2)

2)修正余弦相似度。

(3)

3)Pearson相似度。

(4)

2 結(jié)合信息熵和改進相似度的推薦算法

2.1 用戶信息熵

1948年，香農(nóng)提出信息熵這一概念，它解決了信息的度量問題。設X為一隨機變量，X取值為X的概率用p(x)表示，則可以用信息熵來表達其不確定性，其計算公式為：

(5)

由公式(5)可以看出，信息熵的值與實際的值無關(guān)，與它的概率分布有關(guān)。所以在推薦系統(tǒng)中，信息熵能在一定程度上有效地過濾部分噪音數(shù)據(jù)，同時過濾掉部分信息值較低的用戶，以此來提高推薦系統(tǒng)的精確性。

但是一般的信息熵只與評分出現(xiàn)的次數(shù)有關(guān)，而不與用戶的具體分數(shù)有關(guān)，所以本文引入了用戶信息熵模型。

設用戶A，其評分集合用Ra={r1,r2,…，rm,…，rn}表示，在評分系統(tǒng)中rm∈{1,2,3,4,5}，其中n=︱Ra︱表示用戶A在系統(tǒng)中產(chǎn)生的評分數(shù)。對用戶A，根據(jù)式(5)，其信息熵為：

(6)

其中，c表示評分單位的度量，在10分制的評分系統(tǒng)中c=10；Pak是表示用戶a的評分落在區(qū)間k的概率。Pak的計算過程為：

Pak=[∑rm∈RaI{rm=k}]/|Ra|

(7)

其中，I{x}為指示函數(shù)。綜合式(5)和式(6)即可計算用戶的評分信息熵。

當然，計算用戶的信息熵的目的是為了消除噪音數(shù)據(jù)，在這當中就免不了確定信息熵的閾值F，當H(u)

2.2 改進相似度計算方法

在推薦系統(tǒng)中一直存在一些比較明顯的問題，而最有名的便是冷啟動和數(shù)據(jù)稀疏的問題，專家學者針對這一問題一直在考慮很多的解決方法。在基于內(nèi)存的協(xié)同過濾算法中計算相似度是不可或缺的一個步驟，普通的協(xié)同過濾相似度計算方法依賴用戶的共同評分項來計算相似度，但因為數(shù)據(jù)稀疏使得共同評分項數(shù)據(jù)很少存在，導致在計算相似度上存在比較大的誤差問題。所以本文使用了一種面向數(shù)據(jù)稀疏的相似度計算方法。這種方法改進了馮軍美等[23]在論文中提出的方法，使用全部評分數(shù)據(jù)也不依靠共同的評分項計算來解決數(shù)據(jù)稀疏問題。

定義用戶a和用戶b在所有評分項目的集合為Ia、Ib，用戶a和用戶b相似度計算方法如下：

(8)

其中，︱Ia︱、︱Ib︱用來表示用戶a和用戶b的總評分個數(shù)，用戶a在評分矩陣中第k個的評分數(shù)值為ra，k，用戶b在評分矩陣中第w個的評分數(shù)值為rb,w，max(ra,k,rb,w)和min(ra,k,rb,w)分別表示ra,k、rb,w中的最大值和最小值。

計算完相似度之后尋找最近鄰居，然后以此來計算用戶x未知項i的評分預測為Px,i，它的計算公式見公式(1)。

2.3 結(jié)合信息熵和改進相似度的推薦算法步驟

推薦算法的處理流程如下：

Step1輸入goodbooks數(shù)據(jù)集，通過去除重復值等數(shù)據(jù)處理方式進行數(shù)據(jù)預處理，形成用戶評分矩陣R。

Step2在用戶評分矩陣R的基礎上結(jié)合公式(6)、公式(7)計算所有用戶的用戶信息熵H(x)。

Step3通過數(shù)據(jù)建模實驗可視化分析信息熵閾值F與RMSE和MAE的關(guān)系，確定信息熵閾值F。

Step4當用戶信息熵H(x)<信息熵閾值F時，去除該組用戶評分數(shù)據(jù)，得到新的用戶評分矩陣Rnew。

Step5計算改進相似度simnew(a,b)。

Repeat

Step5.1逐個計算用戶的總評分個數(shù)︱Ia︱。

Step5.2max(ra,k,rb,w)和min(ra,k,rb,w)分別表示(ra,k、rb,w)中的最大值和最小值。

Step5.3通過公式(8)計算改進相似度simnew(a,b)。

Step6通過數(shù)據(jù)建模方法、實驗分析方法確定最近鄰K的數(shù)值，盡量找到能夠達到較優(yōu)解的K的數(shù)值。

Step7尋找用戶x的相似度最高的K個近鄰集合。

Step8通過公式(1)可求出對未知項目的預測評分。

Step9通過對用戶的預測評分來計算出RMSE、MAE的結(jié)果，并進行可視化分析。

圖1為算法的流程圖。

圖1 算法流程圖

3 實 驗

3.1 實驗數(shù)據(jù)集

本文采用的是來源于goodreads網(wǎng)站的goodbooks圖書數(shù)據(jù)集，它的評分方法是讓用戶對圖書打出1～5分中間的一個分數(shù)，分數(shù)間隔為1,分數(shù)越高則表示用戶越喜歡。該數(shù)據(jù)集中包含了53424個用戶對10000本圖書進行的評分，總共有981756條評分數(shù)據(jù)。它的稀疏度通過計算為：

(9)

通過上式可以看出稀疏程度相當高，該數(shù)據(jù)集主要包括4個部分：圖書標簽、圖書詳細信息(包括作者、語言、年份等)、用戶意向閱讀的圖書(即用戶當前或以后感興趣的圖書)和評分數(shù)據(jù)。

3.2 評價指標

在推薦系統(tǒng)中常用的評價指標為平均絕對誤差(MAE)、均方根誤差(RMSE)、召回率、準確率、F1值等。本文選用MAE、RMSE作為評估指標。其計算公式分別為：

(10)

(11)

3.3 實驗結(jié)果與分析

3.3.1 信息熵的計算及閾值的確定

根據(jù)之前的算法步驟，先輸入評分矩陣，這一步驟比較簡單先省略過去。第二步是計算用戶的信息熵H(x)。主要使用公式(6)、公式(7)來計算，計算結(jié)果如圖2所示。使用Python計算用戶的信息熵，橫軸為用戶的編號(userId)，縱軸為用戶的信息熵(information entropy)。從圖中可以看出絕大多數(shù)數(shù)據(jù)的信息熵處在0.8～2.2，圖中上半部分的數(shù)據(jù)很緊湊，將上半部的圖表遮蓋得嚴嚴實實，當然還有零零散散的一些用戶處在0.8以下，可以認為絕大多數(shù)處于0.8以下的數(shù)據(jù)為噪音數(shù)據(jù)。

圖2 信息熵分布圖

算法的第三步是確定信息熵閾值F，當用戶信息熵H(x)

觀察表2可以看出，當設置閾值F為0時RMSE的值為0.867，當閾值在0～0.8的范圍中增大時RMSE隨著它的增大而減小。當閾值設置為0.8時閾值達到了最小值0.859,。當閾值在0.8～1.6的范圍中增大時，可以明顯看出RMSE在回升，當閾值設置為1.2時可以看出RMSE已經(jīng)超過當設置為0的時候，當然之后RMSE繼續(xù)增長，算法效率越來越低?？梢愿爬ǖ卣f當閾值在0～0.8范圍中增加時，RMSE逐漸降低，算法精確度逐漸上升，當閾值F=0.8時，RMSE達到最低值0.859，當閾值在0.8～1.6中增長時，RMSE逐漸上升，算法精確度逐漸下降。從表2中可以看出當閾值F=0.8時RMSE最小，精確度最高，所以之后將閾值F設置為0.8。

表2 不同閾值F的RMSE

3.3.2 對比實驗

圖3 不同相似度下最近鄰K與RMSE關(guān)系圖

圖4 不同相似度下近鄰數(shù)K與MAE關(guān)系圖

圖3、圖4是選用上文4種相似度的情況下，使用基于KNN的協(xié)同過濾算法隨著最近鄰K變化產(chǎn)生的RMSE變化趨勢圖，最近鄰設置為[0,100]，步長為1。從圖3可以看出，在近鄰K值取0時，4種相似度下RMSE由大到小依次為皮爾遜>改進余弦>歐氏距離>余弦相似度，RMSE越小時算法準確度越高，所以剛開始時準確度和RMSE大小相反；可以看出在(0,10]這個區(qū)間變化時，4個相似度下的RMSE值都處于快速下降的趨勢，當K在10左右時，4條曲線的斜率都變得非常??；在K=10時，4種相似度下RMSE由大到小依次為歐氏距離>皮爾遜>改進余弦>余弦，可以看出在K=10時余弦相似度的準確度相對較高；在(10,100]這個區(qū)間，4種相似度下RMSE的變化幅度相對較小，但還是有變化的，可以看出最后幾種算法的準確度為皮爾遜≈改進余弦>余弦>歐氏距離；則表示在使用goodbooks數(shù)據(jù)集KNN算法下，皮爾遜和改進余弦相似度準確度最高，而余弦相似度則稍微差一點，歐氏距離可能差得更多一點。

圖5 不同相似度下數(shù)據(jù)稀疏度與RMSE的關(guān)系圖

為了驗證改進相似度對于數(shù)據(jù)稀疏性的提升效果，圖5在KNN算法下選擇了改進相似度、皮爾遜相似度、改進余弦相似度，探究稀疏度越來越高的情況下RMSE的變化情況；當數(shù)據(jù)稀疏度為97%時，可以看出對算法的準確度來說，改進相似度>改進余弦相似度>皮爾遜相似度，但改進相似度和其他2個相似度差距并不大，當然皮爾遜相似度準確度將近0.99，精確性不理想；隨著數(shù)據(jù)稀疏度在(97.0,99.0]上增加，相似度變化規(guī)律并不大，皮爾遜相似度隨著稀疏度增大它的RMSE增加，導致準確度越來越差，而其他2個相似度差不多但增長率并沒有皮爾遜大；當數(shù)據(jù)稀疏度達到99.5時，3種相似度的RMSE飛速增長，但它們的算法準確度還是保持改進相似度>改進余弦相似度>皮爾遜相似度，這時改進相似度和其他2種相似度的準確度有較大的差距，顯示出該相似度在數(shù)據(jù)稀疏的情況下的優(yōu)越性；當數(shù)據(jù)稀疏度為99.9%時，此時更可以看出改進相似度和另外2種相似度相比，它的準確度更精準。通過該圖可以看出，改進相似度對數(shù)據(jù)稀疏度的影響有緩解效果。

算法下一步是找出最近鄰居然后計算預測評分來計算RMSE。就像上文提到的近鄰的數(shù)量對于結(jié)果有著很大的影響。接下來將設置幾個對照組來對比分析近鄰對實驗的影響。并且將本文算法與李容等[3]提出的基于改進相似度的協(xié)同過濾算法(算法1)、邢長征等[6]提出的填補法和改進相似度相結(jié)合的協(xié)同過濾算法(算法2)進行對比實驗，在研究近鄰的影響的同時與普通的協(xié)同過濾算法進行比較。如表3所示。

表3 不同近鄰數(shù)K對RMSE的影響

從表3可以明顯看出，本文算法相比上述的基于改進相似度的協(xié)同過濾算法都有所提升，3種算法的性能依次對比為本文算法>算法1>算法2。在近鄰數(shù)K依次增長的情況下RMSE在逐漸減小。K的值的選取確實對于算法的精確性有非常大的影響。

本文在計算相似度時，改進了馮君美等[23]的改進相似度計算方法，為了驗證該算法的優(yōu)越性，將本文算法與馮君美等提出的算法進行對比實驗。其中將馮君美等提出的算法稱做算法3。

圖6是對比實驗圖，從圖中可以看出，本文算法在初始時，MAE的值差距相當大，但當K值逐漸變大之后，本文算法變動區(qū)間相對較小，而算法3變動區(qū)間比較大，但本文算法在該數(shù)據(jù)集下它的MAE值一直小于算法3，可以看出本文算法的優(yōu)越性。

圖6 不同算法對比實驗圖

4 結(jié)束語

本文采用了一種將用戶信息熵和面向數(shù)據(jù)稀疏的相似度相結(jié)合的推薦算法，分別用以解決協(xié)同過濾算法中噪音數(shù)據(jù)和數(shù)據(jù)稀疏性的問題，并通過實驗表明本文的算法準確性比普通的協(xié)同過濾算法有了一定的提升。

但本文對噪音數(shù)據(jù)影響的研究是通過比較直接的方法，或許會在某種程度上進行錯誤判斷。在這個方面還有待提升，這是以后筆者可以進一步研究發(fā)展的方向。