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

李 玲，王移芝

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

0 引 言

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

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

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

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

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

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

(1)用戶-項(xiàng)目評(píng)分矩陣。

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

表1 用戶-項(xiàng)目評(píng)分矩陣

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

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

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

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

(1)

1.2 相似度計(jì)量方法

協(xié)同過(guò)濾算法的核心過(guò)程便是發(fā)現(xiàn)最近鄰居，對(duì)計(jì)算用戶之間的相似度起到了至關(guān)重要的作用。目前最常用的相似度計(jì)算方法有皮爾遜相關(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共同評(píng)分的項(xiàng)目集合。

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

2.1 信息熵

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

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

(5)

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

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

表2 用戶對(duì)項(xiàng)目的評(píng)分信息

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

(6)

(7)

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

2.2 加權(quán)相似度

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

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

sim(u,v)WED

(8)

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

2.3 算法步驟

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

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

輸入：用戶-項(xiàng)目評(píng)分矩陣R,α

輸出：MAE,RMSE

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

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

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

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

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

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

3 實(shí) 驗(yàn)

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

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

(9)

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

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

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

(10)

(11)

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

3.3.1 確定α的值

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

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

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

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

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

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

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

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

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

4 結(jié)束語(yǔ)

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

參考文獻(xiàn)：

[1] 張寧昳.Amazon個(gè)性化推薦系統(tǒng)的文本組織結(jié)構(gòu)研究[J].圖書與情報(bào),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é)同過(guò)

濾推薦算法[J].計(jì)算機(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).基于時(shí)效性的冷啟動(dòng)解決算法[J].現(xiàn)代計(jì)算機(jī),2016(5):3-6.

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

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

[11] 劉芳先,宋順林.改進(jìn)的協(xié)同過(guò)濾推薦算法[J].計(jì)算機(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] 劉江冬,梁 剛,馮 程,等.基于信息熵和時(shí)效性的協(xié)同過(guò)濾推薦[J].計(jì)算機(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.