李 玲，王移芝

(北京交通大學(xué) 計算機與信息技術(shù)學(xué)院，北京 100044)

0 引 言

為了緩解“信息超載(information overload)”造成的影響，推薦系統(tǒng)應(yīng)運而生。推薦系統(tǒng)通過分析用戶的行為，可以發(fā)現(xiàn)用戶的潛在興趣以及為用戶提供個性化服務(wù)，例如Amazon的圖書推薦[1]、YouTube的視頻[2]等等。而協(xié)同過濾(collaborative filtering)是迄今為止應(yīng)用最成功的個性化推薦技術(shù)[3]。協(xié)同過濾推薦的基本思想是根據(jù)用戶之間的相似性預(yù)測用戶的喜好，然后進(jìn)行資源的推薦。因此，用戶歷史記錄越多，協(xié)同過濾產(chǎn)生的推薦效果越好。然而，由于信息數(shù)量日益增加，用戶對項目的評分?jǐn)?shù)據(jù)也日益稀疏，推薦的精確度大幅降低[4-5]。

傳統(tǒng)的協(xié)同過濾算法通常采用皮爾遜相關(guān)系數(shù)和余弦相似度度量用戶之間的相似度。然而，傳統(tǒng)的度量方法只考慮用戶間共同評分項的信息，忽略了惡意信息的影響，對找到用戶的近鄰產(chǎn)生一定干擾。為降低數(shù)據(jù)稀疏性對系統(tǒng)推薦質(zhì)量的影響，提高推薦精確度，針對上述問題，研究人員相繼提出了多種應(yīng)對辦法。文獻(xiàn)[6]提出使用sigmoid函數(shù)，提出SPCC方法強調(diào)共同評分項的重要性，評分項越多，用戶間的相似度越大。另外，余弦相似度計算忽略用戶的評分尺度，所以提出了改進(jìn)的余弦相似度度量，即ACOS(adjusted cosine)[7]。文獻(xiàn)[8]提出了一種結(jié)合項目時效性的算法，以緩解數(shù)據(jù)稀疏問題帶來的影響，為用戶推薦時效性高的項目。

盡管專家和學(xué)者們從不同角度提出了多種改進(jìn)方法[9-10],并取得了理想的效果，但是用戶關(guān)系的準(zhǔn)確刻畫仍然影響著推薦結(jié)果的精確度。因此，文中提出一種融合信息熵和加權(quán)相似度的協(xié)同過濾推薦算法。首先，根據(jù)用戶-項目評分矩陣計算所有用戶的信息熵，進(jìn)一步計算用戶的差異度信息熵值，再將用戶的差異度信息熵融入到相似度計算中，最后使用新的相似度計算公式計算用戶間的相似度，找到最合適的近鄰，進(jìn)行項目推薦。

1 傳統(tǒng)的協(xié)同過濾算法

1.1 基于用戶的協(xié)同過濾算法

傳統(tǒng)的基于用戶的協(xié)同過濾算法的步驟主要包括三部分[11]：用戶-項目評分矩陣；發(fā)現(xiàn)最近鄰居；產(chǎn)生推薦項目。

(1)用戶-項目評分矩陣。

協(xié)同過濾推薦算法的研究基于用戶的歷史記錄，這里用戶對項目的評分?jǐn)?shù)據(jù)用m×n的矩陣R表示。其中m表示用戶的數(shù)量，其用戶集合記為User={U1,U2,…,Ui,…,Um}，n表示項目數(shù)量,其項目集合記為Item={I1,I2,…,Ij,…,In},Rij表示用戶i對項目j的評分，如表1所示。

表1 用戶-項目評分矩陣

(2)發(fā)現(xiàn)最近鄰居。

根據(jù)上述矩陣R，計算用戶之間的相似度，將相似度按照降序的方式排列，前k個用戶即為目標(biāo)用戶的最近k個鄰居。

(3)產(chǎn)生推薦項目。

根據(jù)步驟2中找到的k個近鄰對項目的評分情況，對目標(biāo)用戶沒有過行為的項目按照公式1進(jìn)行預(yù)測評分，然后將評分結(jié)果進(jìn)行排序,將排名靠前的N個項目推薦給目標(biāo)用戶，即Top-N推薦。目標(biāo)用戶ut對項目j的預(yù)測評分公式如下：

(1)

1.2 相似度計量方法

協(xié)同過濾算法的核心過程便是發(fā)現(xiàn)最近鄰居，對計算用戶之間的相似度起到了至關(guān)重要的作用。目前最常用的相似度計算方法有皮爾遜相關(guān)系數(shù)、余弦相似性和修正的余弦相似性[12]。具體如下：

(1)皮爾遜相關(guān)系數(shù)(Pearson correlation)。

sim(u,v)PCC=

(2)

(2)余弦相似度(cosine)。

(3)

(3)修正的余弦相似性(adjusted cosine)。

sim(u,v)ACO=

(4)

其中，C表示用戶u和v共同評分的項目集合。

2 融合信息熵和加權(quán)相似度的協(xié)同過濾算法

2.1 信息熵

信息熵的概念是由香農(nóng)(Claude Shannon)在1948年提出的，解決了信息的度量問題，主要通過隨機變量取值的不確定性程度來刻畫信息含量的多少[13]。

假設(shè)X是一個離散的隨機變量，取值為{x1,x2,…,xn},記P(X=xi)=p(xi)，則可以用信息熵來表示X的不確定程度，其計算公式為：

(5)

由式1可以看出，信息熵的大小與X的概率分布有關(guān)，而與具體的取值無關(guān)。當(dāng)p(x1)=p(x2)=…=p(xn)時，即對每一個用戶來說，對項目評分出現(xiàn)的次數(shù)都是相等時，信息熵H(X)獲得最大值。

文獻(xiàn)[14-15]提出基于用戶信息熵的協(xié)同過濾算法，首先計算用戶的信息熵，低于信息熵閾值的用戶信息屬于噪聲數(shù)據(jù)，然后過濾掉這些用戶的信息以降低數(shù)據(jù)的稀疏性。但是存在的問題是用戶的信息熵只與評分出現(xiàn)的次數(shù)有關(guān)，忽略了具體的評分值，這就導(dǎo)致有相同信息熵的用戶可能會存在明顯不同的評分傾向。例如，通過表2的計算可以發(fā)現(xiàn)，按照式5計算得到用戶U1和U4的信息熵是相同的,容易劃分為最近鄰居范圍。但是明顯U1評分普遍偏高，U4評分普遍偏低，說明用戶U1和U4可能不是最好的鄰居。

表2 用戶對項目的評分信息

針對上述問題，通過式6計算用戶評分差異的信息熵值代替單純的用戶信息熵。假設(shè)用戶U1和U2的共同評分項目集合為IC={I1,I2,…,In}，U1對共同項目的評分記為{U11,U12,…,U1n},U2對共同項目的評分記為{U21,U22,…,U2n}，則用戶U1和U2的評分差集D12={|U11-U21|,|U12-U22|,…,|U1n-U2n|}={d1,d2,…,dn},然后計算H(D12)，即U1和U2的評分差異信息熵。這個值越小，表示二者之間的差異越小，評分越接近，選為最近鄰居的可能性越大。

(6)

(7)

根據(jù)式7可知，信息差異熵的取值范圍是[0,+∞)，因此需要對其進(jìn)行歸一化處理，使得H(Dij)的取值范圍為[0,1],記為sim(u,v)WED。

2.2 加權(quán)相似度

考慮到不同用戶的評分尺度和用戶評分值對相似性的影響，增加度量用戶相似性的信息量，同樣可以降低數(shù)據(jù)稀疏性的影響。因此，采用加權(quán)相似度計算用戶之間的相似性，在皮爾遜相關(guān)性的基礎(chǔ)上引進(jìn)權(quán)重因子α，取值在0～1之間，則新的相似度計算公式如下：

sim(u,v)NEW=α*sim(u,v)PCC+(1-α)*

sim(u,v)WED

(8)

從公式可以看出，通過權(quán)重因子α的調(diào)節(jié)，采用加權(quán)相似度計算用戶的相似度，既提高了共同評分項目的重要性，也將用戶的興趣偏好考慮進(jìn)去，從而提高了發(fā)現(xiàn)鄰居的準(zhǔn)確性。

2.3 算法步驟

根據(jù)以上描述，設(shè)計算法如下：

算法：融合信息熵和加權(quán)相似度的協(xié)同過濾算法

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

輸出：MAE,RMSE

Step1:對用戶-項目評分矩陣R,根據(jù)式5計算所有用戶的信息熵Hi(1≤i≤m);

Step2根據(jù)式7計算多用戶之間的差異信息熵H(Duv);

Step3:根據(jù)式8計算目標(biāo)用戶與參考用戶的相似度，找到目標(biāo)用戶的最近鄰居集合N;

Step4:根據(jù)式1，并參考最近鄰居集合N，計算目標(biāo)用戶對未評分項目的預(yù)測評分值;

Step5:將預(yù)測評分值降序排列，產(chǎn)生推薦項目集;

Step6:根據(jù)推薦結(jié)果和式10、11，計算MAE的值。

3 實 驗

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

應(yīng)用于推薦系統(tǒng)研究的數(shù)據(jù)集包括公開的MovieLens,Netflix以及Jester等，不同數(shù)據(jù)集的稀疏度是不一樣的。采用由明尼蘇達(dá)大學(xué)GroupLens研究院小組提供的MovieLens_100K數(shù)據(jù)集，其評分尺度是從1到5的整數(shù)，數(shù)值越高，表明用戶對該電影的偏愛程度越高，反之則表示用戶對該電影不感興趣。選用的數(shù)據(jù)集包括943個用戶對1 682部電影的100 000條評分記錄，每位用戶至少對20部不同的電影進(jìn)行過評分。該數(shù)據(jù)集的稀疏度為：

(9)

可見數(shù)據(jù)非常稀疏。數(shù)據(jù)集的內(nèi)容共4列，分別是用戶ID、電影ID、用戶對電影的評分、時間戳。該數(shù)據(jù)集主要由兩部分組成：base數(shù)據(jù)集和test數(shù)據(jù)集。其中base數(shù)據(jù)集作為樣本數(shù)據(jù)集，經(jīng)過訓(xùn)練后可以得到目標(biāo)用戶對未評分電影的預(yù)測評分；test數(shù)據(jù)集是用戶對電影的實際評分，通過預(yù)測評分和實際評分的對比，可以得到推薦精度。

3.2 評價指標(biāo)

推薦算法實驗中常用的度量指標(biāo)有均方根誤差(RMSE)、平均絕對誤差(MAE)、準(zhǔn)確率、召回率等，文中采用MAE來度量，表示預(yù)測評分與實際評分之間的差距。計算公式如下：

(10)

(11)

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

3.3.1 確定α的值

根據(jù)式8可知，參數(shù)α的值在相似度計算中起到了重要作用。為了獲取最佳參數(shù)值，分別取參數(shù)的值為0.1,0.2,0.3,0.4,0.5,0.6,0.7,0.8,0.9,1.0,計算每個參數(shù)值相對應(yīng)的MAE和RMSE，結(jié)果如圖1和圖2所示。圖中四條折線分別表示近鄰個數(shù)在取5，10，20，30時不同的結(jié)果。圖1和圖2表明，雖然近鄰個數(shù)取不同的值，但是都在α=0.1時MAE和RMSE取得最小值，即當(dāng)α=0.1時取得最佳推薦效果。

圖1 不同α值對應(yīng)的MAE

圖2 不同α值對應(yīng)的RMSE

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

根據(jù)以上所述，在使用加權(quán)后的相似度計算公式時，取α=0.1。接下來通過仿真實驗，將傳統(tǒng)的協(xié)同過濾算法(PCC)、使用信息差異熵作為相似度計算的協(xié)同過濾算法(WED)與提出的融合信息熵和加權(quán)相似度的協(xié)同過濾算法(NEW)進(jìn)行對比，以驗證該算法的有效性。圖3和圖4分別表示三種算法在不同近鄰個數(shù)情況下的MAE值和RMSE值。

如圖所示，不同的近鄰個數(shù)也影響其MAE和RMSE的值。因為在適當(dāng)?shù)泥従臃秶鷥?nèi)，推薦效果可以達(dá)到最佳，近鄰個數(shù)太少，沒有參考價值；相反近鄰個數(shù)太多，會混入其他的噪聲數(shù)據(jù)，因此選擇適當(dāng)?shù)慕弬€數(shù)也是必要的。

圖3 三種算法對應(yīng)的MAE值

圖4 三種算法對應(yīng)的RMSE值

另外，在近鄰個數(shù)相同的情況下，提出的協(xié)同過濾算法相較于傳統(tǒng)的協(xié)同過濾算法和基于信息差異熵的算法，其MAE和RMSE值均低于后兩者，因此該算法可以有效提高推薦質(zhì)量，緩解數(shù)據(jù)稀疏帶來的問題。

4 結(jié)束語

在傳統(tǒng)基于用戶的協(xié)同過濾算法的基礎(chǔ)上，通過引入用戶間的差異信息熵值，可以在一定程度上有效緩解數(shù)據(jù)的稀疏性帶來的影響。在此基礎(chǔ)上，通過使用加權(quán)相似度的方式強化共同評分用戶的作用，提高最近鄰居的識別度。實驗結(jié)果證明，融合信息熵和加權(quán)相似度的協(xié)同過濾算法有效提高了推薦效果。在提高推薦效果的基礎(chǔ)上，進(jìn)一步降低時間復(fù)雜度、縮短計算時間將是下一步的研究方向。

參考文獻(xiàn)：

[1] 張寧昳.Amazon個性化推薦系統(tǒng)的文本組織結(jié)構(gòu)研究[J].圖書與情報,2013(5):103-106.

[2] BALUJA S,SETH R,SIVAKUMAR D,et al.Video suggestion and discovery for Youtube:taking random walks through the view graph[C]//Proceedings of the 17th international conference on world wide web.[s.l.]:[s.n.],2008:895-904.

[3] 邢春曉,高鳳榮，戰(zhàn)思南，等. 適應(yīng)用戶興趣變化的協(xié)同過

濾推薦算法[J].計算機研究與發(fā)展,2007,44(2):296-301.

[4] SYMEONIDIS P,NANOPOULOS A,PAPADOPOULOS A,et al.Collaborative filtering based on user trends[M]//Studies in classification data analysis & knowledge organization.Berlin:Springer,2008:375-382.

[5] BOBADILLA J,ORTEGA F,HEMANDO A,et al.Recommender systems survey[J].Knowledge-Based Systems,2013,46:109-132.

[6] JAMALI M,ESTER M.Trustwalker:a random walk model for combining trust-based and item-based recommendation[C]//Proceedings of the 15th ACM SIGKDD international conference on knowledge discovery and data mining.New York,NY,USA:ACM,2009:397-406.

[7] SARWAR B,KARPIS G, KONSTAN J,et al. Item-based collaborative filtering recommendation[C]//Proceedings of the 10th international conference on world wide web.[s.l.]:[s.n.],2001:285-295.

[8] 劉江東,梁 剛,楊 進(jìn).基于時效性的冷啟動解決算法[J].現(xiàn)代計算機,2016(5):3-6.

[9] 黃創(chuàng)光,印 鑒,汪 靜,等.不確定近鄰的協(xié)同過濾推薦算法[J].計算機學(xué)報,2010,33(8):1369-1377.

[10] 李 聰,梁昌勇,馬 麗.基于領(lǐng)域最近鄰的協(xié)同過濾推薦算法[J].計算機研究與發(fā)展,2008,45(9):1532-1538.

[11] 劉芳先,宋順林.改進(jìn)的協(xié)同過濾推薦算法[J].計算機工程與應(yīng)用,2011,47(8):72-75.

[12] MULLER K R,MIKA S,RTSCH G,et al.An introduction to kernel-based learning algorithms[J].IEEE Transactions on Neural Network,2001,12(2):181-201.

[13] SHANNON C E A.A mathematical theory of communication[J].ACM SIGM-OBILE Mobile Computing & Communications Review,2001,5(1):3-55.

[14] 劉江冬,梁 剛,馮 程,等.基于信息熵和時效性的協(xié)同過濾推薦[J].計算機應(yīng)用,2016,36(9):2531-2534.

[15] KALELI C.An entropy-based neighbor selection approach for collaborative filtering[J].Knowledge-Based Systems,2014,56:273-280.