，章金平，徐啟南12

(1.安徽大學 計算智能與信號處理實驗室，安徽 合肥 230601； 2.安徽大學 計算機學院，安徽 合肥 230601)

根據(jù)中國互聯(lián)網絡信息中心(China Internet Network Information Center，CNNIC)最新發(fā)布的第40次《中國互聯(lián)網絡發(fā)展狀況統(tǒng)計報告》，截至2017年6月，我國網民規(guī)模達到7.51億，隨之信息也出現(xiàn)了爆炸式增長。人們逐漸從信息匱乏向信息過載轉變，信息給人們帶來利益的同時，也帶來了一定程度上的困擾。如何從大量的數(shù)據(jù)中選擇自己感興趣的數(shù)據(jù)，曾是很多人面臨的一道難題。搜索引擎的出現(xiàn)，一定程度上緩解了信息過載問題，但其必須依靠用戶的主動輸入且反饋的結果非個性化，因此存在著一定的局限性。后來，為了解決搜索引擎的局限性，推薦系統(tǒng)誕生了，它能夠根據(jù)用戶的歷史行為，為每個用戶建立自己的興趣模型，從而主動為用戶進行推薦?，F(xiàn)在典型推薦系統(tǒng)有：今日頭條、天貓、亞馬遜等。為了更好、更準確地進行推薦，推薦算法是推薦系統(tǒng)中的核心部分。協(xié)同過濾(Collaborative Filtering,CF)推薦算法是推薦系統(tǒng)中應用最廣泛、最成功的推薦技術之一[1]。然而，在面對眾多的項目和用戶時，協(xié)同過濾推薦算法會遇到的最大難題是數(shù)據(jù)稀疏性問題。其常會導致相似度計算不準確，最終影響預測精度。

為了提高推薦系統(tǒng)的預測精度，很多研究者基于該算法的相似性方面進行了研究。文俊浩等人[2]利用用戶共同評分和用戶所有評分之間的關系對用戶相似度進行改進。榮輝桂等人[3]引入用戶相似度概念，定義社交網絡中屬性相似度、相似度構成和計算方法，提出了一種改進的協(xié)同過濾推薦算法。于金明等人[4]提出了新的項目相似度度量方法，該項目相似性度量由評分相似性和結構相似性兩個部分構成。張俊等人[5]通過計算用戶興趣相似性，并使用用戶興趣相似性和評分相似性進行兩次融合，從而對傳統(tǒng)相似性度量僅僅依靠用戶評分進行相似性計算引起的誤差進行修正。李偉霖等人[6]提出了基于評論與評分的user-based協(xié)同過濾算法和基于評論與評分的item-based協(xié)同過濾算法。這些方法雖然改進了相似度計算方法,一定程度上提高了推薦系統(tǒng)的預測準確度。但都是在基于傳統(tǒng)的相似度度量方法的基礎上進行修正的。

本文提出了一種新的協(xié)同過濾推薦算法，將互信息作為度量項目之間的相似性方法，解決了Pearson相關系數(shù)一般情況下只考慮了線性相關性，對非線性的變量相關性效果一般問題。同時在互信息方法上引入了平滑系數(shù)因子，來緩解了余弦相似度方法對稀疏性數(shù)據(jù)比較敏感問題。

1 相關工作和定義

1.1 基于項目的協(xié)同過濾實現(xiàn)

基于項目的協(xié)同過濾推薦算法主要有3個步驟：① 構建用戶-項目評分矩陣；② 根據(jù)用戶-項目評分矩陣計算項目之間的相似度；③ 選取目標項最近鄰居集，并進行推薦。在整個推薦算法的過程中，相似度計算是該推薦算法的核心部分。因此，一個好的相似度計算方法顯得十分重要。

1.2 傳統(tǒng)的相似性度量方法

傳統(tǒng)的度量用戶間相似度方法有很多，其中最具有代表性的有余弦相似度、Pearson相關系數(shù)。

余弦相似度是一種常用的相似度度量方法，而且應用十分廣泛。它將n個用戶對項目i和項目j的評分看成是n維上的一個向量，通過計算向量之間的夾角余弦值來度量項目之間的相似性程度。其中Ru,i表示用戶u對項目i的評分，Iu,v表示共同評分項目i與項目j的用戶集[4]，計算公式為

(1)

(2)

在實際的推薦系統(tǒng)中，共同評分過的項目i與項目j的用戶數(shù)很少，因此，傳統(tǒng)的相似度方法就遇到了瓶頸。如果共同評分過項目i與項目j的用戶數(shù)為1，則余弦相似性的計算結果總是1，從而擴大的項目之間的相似度值。Pearson相關系數(shù)忽略了用戶的評分標準不一樣，導致針對每個項目的具體評分差異，會出現(xiàn)以下情況，如5個用戶對項目i與項目j的評分向量分別為(1,2,1,2,1)和(4,5,4,5,4)，用Pearson計算得到結果為1。所以，傳統(tǒng)的相似度方法計算項目之間的相似性時存在著一定的誤差。

1.3 互信息方法

在信息論中，“信息熵”是度量樣本集合純度最常用的一種指標，可用H(X)表示：

(3)

式中，P(xi)為樣本xi的概率；q為可能的樣本數(shù)目。對此，引入X和Y的聯(lián)合熵H(X,Y)：

(4)

對于整個變量X，由于變量Y的發(fā)生及二者間的相關性，使其不確定性減少的熵值稱為互信息(Mutual Information)[7]，定義為

I(X;Y)=H(X)-H(X|Y)

(5)

又可以表示為

I(X;Y)=H(X)+H(Y)-H(X,Y)

(6)

綜合式(3)～式(6)，可以得到最終的互信息表達公式為

(7)

特別指出，互信息對變量X和Y的分布沒有任何特殊要求，它可以用來描述變量之間的線性相關關系或非線性相關關系。在此，為了使互信息的值在[0,1]之間，將其進行歸一化處理，即

(8)

將變量X看成為項目i被所有用戶評分的向量，記為I。變量Y看成為項目j被所有用戶評分的向量，記為J。則項目之間的相似度計算公式為

(9)

式中，I(I,J)為項目i和項目j的互信息值；H(I)為項目i的信息熵。

2 互信息項目協(xié)同過濾推薦算法

2.1 用戶對項目評分的相似性度量

表1為一個m×n的用戶-項目評分矩陣。m行代表m個用戶，n列代表n個項目。Rm,i代表第m個用戶對項目i的評分。

表1 用戶-項目評分矩陣

在真實的推薦系統(tǒng)中，數(shù)據(jù)稀疏性十分嚴重，導致共同評分的項目用戶數(shù)很少，考慮到互信息方法能夠更好地挖掘兩個隨機變量之間的關聯(lián)程度，即在已知一個隨機變量的前提下，使得另一個隨機變量不確定性減小的程度。同時引入了平滑系數(shù)因子，來緩解共同評分的項目用戶數(shù)過少，導致相似度計算不準確。如5個用戶對項目i與項目j的評分向量分別為(1,2,1,0,0)和(0,0,5,0,4)，用互信息方法，項目i和項目j的相似度值為0.1406，說明了兩個項目之間相關性很弱。在互信息方法上加入了平滑系數(shù)后，計算結果為0.0468，表明兩個項目相似性很低。相比于傳統(tǒng)的余弦相似度方法，提出的方法計算項目之間的相似度更加準確。其中平滑系數(shù)為

(10)

上述平滑系數(shù)的取值范圍為[0,1]，當項目i和j完全被相同的用戶評分時，此時取值為1。當項目i和j被完全不同的用戶評分時，此時取值為0。一般期望共同評價項目i和j的用戶數(shù)越多越好，即平滑系數(shù)值趨向于1時，此時相似度值的計算更加準確，從而提高推薦系統(tǒng)的預測精度。另外，平滑系數(shù)能夠很好地反映用戶打分的重疊部分，且能夠獲得項目i和j在用戶打分方面的相對差異程度，即|I|-|J|。根據(jù)式(9)和式(10)，可以得到用戶對項目評分的相似性度量為

simscore(i,j)=coefficient(i,j)·I*(I,J)

(11)

式中，i和j分別為兩個不同項目；|U|為共同評價項目i和j的用戶數(shù)；|I|為所有用戶對項目i評分用戶數(shù)；|J|為所有用戶對項目j評分用戶數(shù)；I*(I,J)為項目i和項目j之間經過歸一化后互信息值。

2.2 生成推薦集

設集合N(i)={I1，I2，I3，…,In}為目標項Ii的鄰居集合，Ii?I，集合I中元素Ij與目標項Ii之間相似性遞減。則預測目標項目Ii評分值計算公式為

(12)

2.3 算法描述

根據(jù)前幾節(jié)的新思想，將所提出方法中核心算法——基于互信息的項目協(xié)同過濾算法描述如下。

輸入：用戶-項目評分矩陣

輸出：目標項目的評分預測并產生推薦

開始

沃爾特·格羅佩斯（Walter Gropius,1883～1969）是 20 世紀最重要的現(xiàn)代設計家、設計理論家和設計教育的奠基人。他不僅在理論上和在設計實踐中提倡“功能追隨形式”的觀念，而且把現(xiàn)代主義的設計觀念從包豪斯帶到了美國，從而影響到全世界。格羅佩斯把“功能追隨形式”設計觀念更加明確表達為“功能第一，形式第二”。

步驟1:構建m×n的用戶-項目評分矩陣

步驟2:計算項目之間的相似度。

根據(jù)式(11)計算項目之間在評分上相似度；

步驟3：選取目標項最近鄰居集

假設目標項為i，目標項的最近鄰居數(shù)為N，該用戶u已經評價過的項目集合為URDB。根據(jù)URDB中的項與目標項i之間的相似性，選擇相似度最高的前N個項目作為項目項的最近鄰N(i)。

步驟4：根據(jù)式(12)預測目標項目評分并產生推薦

結束

3 實驗結果及分析

3.1 數(shù)據(jù)集及數(shù)據(jù)的預處理

所采用的數(shù)據(jù)來自GroupLens研究組(http://www.grouplens.org)和Jester(http://eigentaste.berkeley.edu/dataset/)兩個數(shù)據(jù)集。該兩個數(shù)據(jù)集已經被廣泛應用在推薦系統(tǒng)的評測中。表2展示了這兩個數(shù)據(jù)集的一些記錄情況。分別在這兩個數(shù)據(jù)集上進行了實驗。將這兩個數(shù)據(jù)集分別按4∶1比例分成訓練集和測試集。

表2 實驗數(shù)據(jù)

3.2 評價指標

本文主要采用平均絕對偏差(MAE)和均方根誤差(RMSE)作為評價推薦系統(tǒng)的預測質量的評價指標。MAE和RMSE都是推薦系統(tǒng)中常用的方法，可以直觀地對預測質量進行衡量。(pi,qi)為用戶評分對，其中pi為預測項目的得分，qi為實際得分。MAE和RMSE的值越小，推薦系統(tǒng)的預測準確度越高。MAE、RMSE的計算公式為

(13)

(14)

3.3 實驗結果和分析

為了驗證所提方法可行性，分別在MovieLens和Jester數(shù)據(jù)集上進行了實驗。在基于項目的協(xié)同過濾前提下，分別選用相似性度量方法為余弦法(CC)、Pearson相關系數(shù)(PCC)、互信息(MI)、互信息+平滑系數(shù)(MICC)，即本文方法，用MAE和RMSE評價指標做了大量的對比實驗。以此來驗證本文方法(MICC)的有效性。

(1) MovieLens數(shù)據(jù)集下不同相似度方法下的MAE和RMSE比較。

表3為MovieLens數(shù)據(jù)集上不同相似性度量法下MAE和RMSE的實驗結果。從表3可以看出，隨著最近鄰數(shù)量的增加，MAE和RMSE值基本上逐漸減少。另外，互信息(MI)方法較傳統(tǒng)的相似度方法相比，MAE值降低了0.04左右。在互信息的基礎上引入平滑系數(shù)后(MICC)，較傳統(tǒng)的方法MAE值降低了0.1左右。同時，當最近鄰居數(shù)目比較少時(小于25)，MAE值明顯降低，最近鄰居數(shù)超過25時，MAE值降低的效果不明顯。則可以證明加入平滑系數(shù)能夠有效地緩解共同評分過少的項目之間相似度計算問題。

(2) Jester數(shù)據(jù)集下不同相似度方法下的MAE和RMSE比較。

表4為在Jester數(shù)據(jù)集上不同相似性度量法下MAE和RMSE的實驗結果。表4可以看出，由于該數(shù)據(jù)集項目數(shù)非常少，導致其鄰居數(shù)也很少。當鄰居數(shù)達到9時，隨著最近鄰居數(shù)量的增加，MAE和RMSE值基本上達到穩(wěn)定。同時，還可以看出，互信息方法(MI)較傳統(tǒng)的相似度方法MAE值降低了0.06左右，加入了平滑系數(shù)因子后，所提出的方法(MICC)較其他方法計算出MAE和RMSE都最小，證明了平滑系數(shù)對數(shù)據(jù)稀疏性帶來的相似度計算不準確有著一定的影響。

表3 MovieLens數(shù)據(jù)集下不同相似度方法下MAE和RMSE

表4 Jester數(shù)據(jù)集下不同相似度方法下的MAE和RMSE比較

4 結束語

本文主要針對推薦系統(tǒng)中數(shù)據(jù)稀疏性對傳統(tǒng)的相似度方法計算項目之間的相似度值不準確問題，提出了基于互信息的項目協(xié)同過濾算法，即利用互信息方法有效地挖掘不同項目之間的相關性強弱，同時，引入平滑系數(shù)因子來緩解共同評分過少的項目之間相似度度量問題。在MovieLens和Jester數(shù)據(jù)集上的測試實驗結果表明，互信息+平滑系數(shù)(MICC)方法在預測準確率方面比傳統(tǒng)的相似度方法有著一定的優(yōu)越性。在以后的工作中，應更深入研究推薦系統(tǒng)，考慮更多的項目信息和用戶社交網絡信息等，進一步提升推薦系統(tǒng)質量。