基于標(biāo)簽和評(píng)分差值信息熵的協(xié)同過(guò)濾算法

侯繼昌，陳家琪

(上海理工大學(xué) 光電信息與計(jì)算機(jī)工程學(xué)院，上海 200093)

隨著信息時(shí)代的發(fā)展，人們逐漸步入了信息過(guò)載的時(shí)代，推薦系統(tǒng)應(yīng)運(yùn)而生。協(xié)同過(guò)濾算法[1-3]是推薦系統(tǒng)中最成功的技術(shù)，傳統(tǒng)的協(xié)同過(guò)濾算法僅僅考慮到用戶之間共同評(píng)分項(xiàng)的評(píng)分信息，沒(méi)有考慮到用戶的興趣，此外用戶共同評(píng)分項(xiàng)目較少，數(shù)據(jù)稀疏性[4]較大，因此通過(guò)傳統(tǒng)方法得到相似用戶集的準(zhǔn)確性和可靠性難以得到保證。

針對(duì)上述問(wèn)題，研究者們提出了很多解決方法。文獻(xiàn)[5]提出了基于信息熵的協(xié)同過(guò)濾算法，利用用戶評(píng)分信息熵來(lái)反映用戶評(píng)分分布和傾向程度；文獻(xiàn)[6]提出基于加權(quán)信息熵相似性的協(xié)同過(guò)濾算法，通過(guò)差異值和共同評(píng)價(jià)數(shù)目對(duì)信息熵進(jìn)行加權(quán)再進(jìn)行歸一化處理計(jì)算項(xiàng)目間的相似度。此外，很多學(xué)者開(kāi)始關(guān)注標(biāo)簽，認(rèn)為標(biāo)簽作為用戶興趣和資源特征的一種表達(dá)方式，可以展現(xiàn)出用戶興趣。文獻(xiàn)[7]提出基于社會(huì)化標(biāo)簽的協(xié)同過(guò)濾算法，利用群體智慧選擇流行標(biāo)簽對(duì)用戶和資源建模；文獻(xiàn)[8]提出基于標(biāo)簽和協(xié)同過(guò)濾的個(gè)性化資源推薦，依據(jù)標(biāo)簽計(jì)算用戶偏好程度和資源特征相似度；文獻(xiàn)[9]提出基于標(biāo)簽和協(xié)同過(guò)濾的個(gè)性化推薦算法，通過(guò)標(biāo)簽來(lái)學(xué)習(xí)用戶對(duì)于資源的興趣以及計(jì)算資源的相似度，再預(yù)測(cè)用戶對(duì)于其它資源的偏好值，最后實(shí)現(xiàn)資源推薦。

鑒于現(xiàn)有相似性度量方法存在的不足，本文探討一種基于標(biāo)簽和評(píng)分差值信息熵的協(xié)同過(guò)濾算法。從評(píng)分差值信息熵和用戶標(biāo)簽兩個(gè)方面來(lái)計(jì)算用戶評(píng)分和興趣相似度，來(lái)獲得更好的推薦效果，改善數(shù)據(jù)稀疏問(wèn)題。

1 相關(guān)工作

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

基于用戶的協(xié)同過(guò)濾算法[10]主要是找出目標(biāo)用戶的相似用戶集，為目標(biāo)用戶推薦Top-N的相似度用戶。

1.1.1 相似度計(jì)算

相似度計(jì)算是傳統(tǒng)協(xié)同過(guò)濾算法的關(guān)鍵。常見(jiàn)的相似度計(jì)算方法[11]有Pearson相似度、Jaccard相似度和Cosine相似度，如式(1) ～式 (3)所示。

(1)

(2)

(3)

1.1.2 傳統(tǒng)評(píng)分預(yù)測(cè)方法

傳統(tǒng)的預(yù)測(cè)目標(biāo)用戶u對(duì)未評(píng)分項(xiàng)目i的評(píng)分公式[12]為

(4)

1.2 信息熵定義

信息熵是衡量分布的混亂程度或分散程度的一種度量[13]。分布越分散，信息熵就越大；分布越有序，信息熵就越小。對(duì)于給定的樣本集X，其信息熵的計(jì)算公式為

(5)

其中，n代表樣本集X的分類數(shù)，p(xq)代表X中第i類元素出現(xiàn)的概率。信息熵越大表明樣本集X分類越分散，信息熵越小則表明樣本集X分類越集中。當(dāng)X中n個(gè)分類出現(xiàn)的概率一樣大時(shí)(都是i/n)，信息熵取最大值log2n；當(dāng)X只有一個(gè)分類時(shí)，信息熵取最小值0。

2 用戶標(biāo)簽興趣遺忘的相似度計(jì)算

標(biāo)簽可以作為用戶興趣的體現(xiàn)，可被用戶依照個(gè)人偏好進(jìn)行自由資源標(biāo)注。因此，本文在用戶間評(píng)分相似度的基礎(chǔ)上，把用戶標(biāo)簽作為用戶興趣體現(xiàn)點(diǎn)，同時(shí)考慮到用戶對(duì)標(biāo)簽的興趣會(huì)隨著時(shí)間的變化而漂移的。因此，利用非線性遺忘函數(shù)對(duì)用戶標(biāo)簽向量進(jìn)行改進(jìn)，然后利用Cosine相似度計(jì)算方法來(lái)計(jì)算用戶標(biāo)簽向量相似度，進(jìn)而獲取用戶興趣相似度。

2.1 引入非線性遺忘函數(shù)計(jì)算用戶標(biāo)簽向量

2.1.1 用戶的標(biāo)簽權(quán)重向量

用戶的標(biāo)簽特征向量是利用用戶常使用的標(biāo)簽來(lái)表示用戶的興趣特征，記為

(15)

其中，w(u,ti)=TFutiIDFuti，TFuti為用戶u對(duì)資源使用標(biāo)簽ti進(jìn)行標(biāo)注的頻率，即用戶u對(duì)資源標(biāo)注標(biāo)簽ti的次數(shù)除以用戶u標(biāo)注的總次數(shù)；IDFuti表示標(biāo)簽ti關(guān)于用戶的逆向文件頻率，即用戶總數(shù)m除以標(biāo)注標(biāo)簽ti的用戶總數(shù)，再對(duì)得到的商取對(duì)數(shù)。

2.1.2 引入的非線性逐步遺忘函數(shù)

用戶對(duì)標(biāo)簽的興趣不是不變的，根據(jù)心理學(xué)遺忘規(guī)律，用戶對(duì)標(biāo)簽的興趣是會(huì)隨著時(shí)間逐步衰減的。此外，人的遺忘過(guò)程不是簡(jiǎn)單的逐步遺忘。遺忘規(guī)律表明：在識(shí)記后的短時(shí)期內(nèi)遺忘進(jìn)行得較快，經(jīng)過(guò)足夠長(zhǎng)的時(shí)間間隔后遺忘進(jìn)行得比較緩慢，即遺忘過(guò)程是先快后慢，是非線性的。文獻(xiàn)[14]提出非線性逐步遺忘函數(shù)，來(lái)形容遺忘現(xiàn)象。因此，本文將非線性遺忘函數(shù)應(yīng)用到用戶對(duì)標(biāo)簽的興趣中去，來(lái)表示用戶的興趣變化。

基于用戶標(biāo)簽的非線性逐步遺忘函數(shù)為

(16)

其中，0≤m≤1,0

2.1.3 引入非線性遺忘函數(shù)后的用戶標(biāo)簽向量

引入非線性遺忘函數(shù)，得到修正的用戶標(biāo)簽向量

(17)

2.2 計(jì)算用戶標(biāo)簽向量相似度

本文采用余弦相似度來(lái)計(jì)算用戶之間的標(biāo)簽向量相似度如式(18)，以此來(lái)判斷用戶興趣相似度

(18)

3 評(píng)分信息熵的相似度計(jì)算

傳統(tǒng)協(xié)同過(guò)濾算法僅利用評(píng)分?jǐn)?shù)值信息來(lái)刻畫用戶之間的相似性，但是，由于用戶評(píng)分?jǐn)?shù)據(jù)極端稀疏，因此傳統(tǒng)的相似度計(jì)算對(duì)于刻畫用戶之間的相似性準(zhǔn)確度較低。本文提出基于評(píng)分信息熵的相似度計(jì)算方法，來(lái)改善數(shù)據(jù)稀疏問(wèn)題并提高推薦質(zhì)量。首先計(jì)算用戶評(píng)分的信息熵，過(guò)濾噪點(diǎn)數(shù)據(jù)，其次引入Jaccard系數(shù)(用戶之間共同評(píng)分項(xiàng)目所占比)計(jì)算用戶評(píng)分差值信息熵并結(jié)合PCC方法來(lái)計(jì)算用戶評(píng)分之間相似度。

3.1 計(jì)算用戶評(píng)分信息熵來(lái)過(guò)濾噪點(diǎn)數(shù)據(jù)

定義1[13]假設(shè)用戶u的評(píng)分是一個(gè)離散的評(píng)分集Ru={Ru1,Ru2,Ru3,…,Run}，Rui為用戶u其中一個(gè)評(píng)分，在此限定評(píng)分范圍為1 ～ 5，則用戶u上評(píng)分為Rui的概率分布函數(shù)p(Rui)等于評(píng)分為Rui的項(xiàng)目個(gè)數(shù)占用戶u已評(píng)分項(xiàng)總個(gè)數(shù)的比率。

用戶評(píng)分之間的信息熵

(6)

由式(6)可知，評(píng)分的信息熵H(Ru)只與評(píng)分值Rui的概率分布有關(guān)，而與評(píng)分值無(wú)關(guān)。因此，利用用戶評(píng)分信息熵過(guò)濾評(píng)分信息較少的用戶，避免噪聲數(shù)據(jù)的干擾，例如：評(píng)分為(1，1，… ，1)的用戶數(shù)據(jù)。系統(tǒng)中的用戶對(duì)推薦引擎的作用效果不同，有的用戶提供的評(píng)分所含的信息量多有的信息量少，過(guò)濾信息量少的用戶可以有效提升推薦精度。

為了過(guò)濾掉噪聲數(shù)據(jù)，首先確定一個(gè)評(píng)分信息熵閾值τ，即當(dāng)H(Ru) <τ時(shí)，則可以過(guò)濾掉用戶u的評(píng)分信息。τ需要通過(guò)實(shí)驗(yàn)驗(yàn)證獲得，合理地選擇τ可以有效提高推薦精度。

3.2 計(jì)算用戶間評(píng)分差值信息熵

3.2.1 計(jì)算兩個(gè)用戶間的評(píng)分差值

記用戶u和用戶v的共同評(píng)分項(xiàng)目集合為Iuv={i1,i2,i3,i4,…,in}，用戶u共同項(xiàng)目評(píng)分?jǐn)?shù)據(jù)為ru={rui1,rui2,rui3,…,ruin,}，用戶 共同項(xiàng)目評(píng)分?jǐn)?shù)據(jù)為rv={rvi1,rvi2,rvi3,…,rvin,}。則這兩個(gè)用戶的評(píng)分?jǐn)?shù)據(jù)的差值集合D-value(rui,rvi)可以定義為

D-value(rui,rvi)={d1,d2,…,dn}

(7)

其中，dk=ruik-rvik。

3.2 引入Jaccard函數(shù)改進(jìn)用戶評(píng)分差值信息熵

用戶之間評(píng)分差值信息熵D-value(rui,rvi)為

(8)

其中，p(dk)代表在D-value(rui,rvi)中dk的概率大小。

信息熵是反映數(shù)據(jù)分散程度的一種度量，因此，當(dāng)用戶間評(píng)分差值信息熵越小時(shí)，用戶間的評(píng)分傾向越一致；反之，若信息熵越高，說(shuō)明這兩個(gè)用戶評(píng)分傾向越不一致。此外，當(dāng)兩個(gè)用戶共同評(píng)分的項(xiàng)目數(shù)很小時(shí)，即使他們的評(píng)分差值信息熵很小，也不代表二者一定相似，即用戶之間的相似度也和共同評(píng)分項(xiàng)目有關(guān)。因此，考慮到用戶評(píng)分交集的影響，本文引入?yún)?shù)f，計(jì)算公式如下

f=1/J(u,v)

(9)

J(u,v)為用戶之間的置信度函數(shù)，本文用Jaccard相似度計(jì)算公式表示為

(10)

由上式可知，當(dāng)用戶之間的評(píng)分項(xiàng)目交集越小時(shí)，置信度函數(shù)值J(u,v)越小，進(jìn)而參數(shù)f越大，對(duì)應(yīng)的評(píng)分差信息熵值應(yīng)該越大，用戶之間的相似性越小。因此，用戶之間的評(píng)分差信息熵修正為

(11)

3.2.2 將用戶間評(píng)分差信息熵進(jìn)行歸一化

式(11)計(jì)算所得的評(píng)分差信息熵值不在零到一之間，為了后續(xù)計(jì)算用戶之間的相似度，本文采用反余切函數(shù)轉(zhuǎn)換來(lái)做歸一化處理，如下

(12)

3.3 結(jié)合PCC計(jì)算用戶評(píng)分的相似度

本文添加對(duì)用戶間評(píng)分分值相似度的計(jì)算。本文采用PCC相似度計(jì)算方法，如式(13)所示。

(13)

綜上，本文最終基于用戶評(píng)分的相似度計(jì)算方法為

(14)

4 基于信息熵和標(biāo)簽的協(xié)同過(guò)濾算法

結(jié)合基于用戶評(píng)分的相似度和用戶之間的興趣相似度，得到最終的用戶相似度計(jì)算公式

(19)

式 (19) 中：入的值在0 ～ 1變化，simend(u,v)代表用戶之間的最終相似度。用式 (4) 來(lái)預(yù)測(cè)用戶對(duì)未評(píng)分的項(xiàng)目的評(píng)分，產(chǎn)生Top-N推薦。

基于信息熵和標(biāo)簽的協(xié)同過(guò)濾算法的流程如圖1所示。

圖1 基于信息熵和標(biāo)簽的協(xié)同過(guò)濾算法的流程

輸入用戶的標(biāo)簽信息，用戶項(xiàng)目的評(píng)分信息。

輸出目標(biāo)用戶u對(duì)待評(píng)分項(xiàng)目i的預(yù)測(cè)評(píng)分。

a) 根據(jù)用戶項(xiàng)目評(píng)分信息利用式 (6) 來(lái)計(jì)算信息熵，設(shè)置閾值τ，來(lái)過(guò)濾噪點(diǎn)；

b) 利用用戶u與其他用戶v之間的評(píng)分差值計(jì)算差值信息熵，并結(jié)合PCC來(lái)獲取最終的基于評(píng)分的相似度simrate(u,v)；

c) 利用用戶的標(biāo)簽信息，引入非線性遺忘函數(shù)來(lái)構(gòu)建用戶標(biāo)簽向量；

e) 利用式 (19) 計(jì)算用戶最終的相似度simend(u,v)形成目標(biāo)用戶u的候選鄰居集合Su；

f) 通過(guò)集合Su和式 (4) 計(jì)算出目標(biāo)用戶u對(duì)項(xiàng)目i的評(píng)分，產(chǎn)生Top-N推薦

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

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

本文采用GroupLens 站點(diǎn)提供的 MovieLens 10 MB數(shù)據(jù)集驗(yàn)證基于信息熵和標(biāo)簽的協(xié)同過(guò)濾的推薦算法。數(shù)據(jù)集中用戶數(shù)超過(guò)70 000，標(biāo)簽數(shù)超過(guò)90 000個(gè)，評(píng)分?jǐn)?shù)據(jù)集較大，因此本文抽取其中6 000名用戶的評(píng)分記錄和標(biāo)簽標(biāo)注記錄進(jìn)行實(shí)驗(yàn)。實(shí)驗(yàn)中，先計(jì)算用戶評(píng)分信息熵過(guò)濾噪點(diǎn)數(shù)據(jù)，剩余數(shù)據(jù)隨機(jī)分為訓(xùn)練集和測(cè)試集，其中訓(xùn)練集占90%，測(cè)試集占10%。

5.2 推薦質(zhì)量度量標(biāo)準(zhǔn)

平均絕對(duì)誤差(Mean Absolute Error，MAE)[16]。 MAE用項(xiàng)目預(yù)測(cè)評(píng)分和實(shí)際評(píng)分間的偏差度量算法的準(zhǔn)確性，公式為

(20)

其中,Pui計(jì)算得出對(duì)項(xiàng)目i的預(yù)測(cè)評(píng)分值，tui為用戶對(duì)項(xiàng)目的實(shí)際評(píng)分值；N為待測(cè)集中的項(xiàng)目總數(shù)。

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

5.3.1 過(guò)濾噪點(diǎn)數(shù)據(jù)

計(jì)算出實(shí)驗(yàn)數(shù)據(jù)集中各個(gè)用戶的評(píng)分信息熵，設(shè)置閾值過(guò)濾噪點(diǎn)[15]。為了更加準(zhǔn)確的確定信息熵閾值，合理地選擇信息熵閾值，實(shí)驗(yàn)統(tǒng)計(jì)出不同信息熵值所對(duì)應(yīng)的用戶總數(shù)如圖2所示。橫軸為信息熵，豎軸為用戶個(gè)數(shù)。實(shí)驗(yàn)發(fā)現(xiàn)用戶聚集的疏密分界線的信息熵值約為1.0。因此圖2信息熵從0.6開(kāi)始取值，每次遞增0.1，直到1.2為止?？梢钥闯鲂畔㈧刂翟?.6～0.9之間，用戶數(shù)很少，但當(dāng)信息熵值>0.9時(shí)，用戶數(shù)量明顯增多。因此，設(shè)置閾值τ為0.9。過(guò)濾掉信息熵小于0.9的用戶達(dá)到過(guò)濾噪點(diǎn)數(shù)據(jù)的目的,過(guò)濾后數(shù)據(jù)集用戶總數(shù)為5 653。

圖2 信息熵對(duì)應(yīng)的用戶數(shù)

5.3.2 實(shí)驗(yàn)結(jié)果

將本文算法和傳統(tǒng)的基于用戶的協(xié)同過(guò)濾算法進(jìn)行比較，MAE值越小，推薦質(zhì)量越高。但是為了能獲取更為準(zhǔn)確的推薦，首先需要確定用戶相似度計(jì)算公式中的λ值，然后，使用最優(yōu)的λ值進(jìn)行實(shí)驗(yàn)，改變相似用戶集k的數(shù)量，來(lái)觀察傳統(tǒng)基于用戶的算法和本文中非線性衰減函數(shù)的m值，根據(jù)先前研究定為0.6。接下來(lái)，用過(guò)濾后的數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)。

首先，確定λ值。通過(guò)改變用戶相似鄰居個(gè)數(shù)k，來(lái)觀察不同λ值下的MAE值，MAE值越小，推薦質(zhì)量就越高。實(shí)驗(yàn)在相似鄰居集k為10,20,50的情況下進(jìn)行，如圖3橫軸為λ取值，范圍是從0到1。豎坐標(biāo)為MAE值。從圖中可以看出，隨著λ值得增大，MAE值逐漸減小，當(dāng)λ值為0.80時(shí)，不同k值得曲線的MAE值都達(dá)到了最小值，之后，λ值在增大，不同曲線對(duì)應(yīng)的MAE值又開(kāi)始增大。因此，當(dāng)λ值為0.80時(shí)，MAE最小，推薦效果最好，因此，設(shè)置λ值為0.80。

圖3 k為10、20、50時(shí)，不同λ值下MAE比較

在不同k值的情況下，計(jì)算傳統(tǒng)基于用戶的協(xié)同過(guò)濾算法、基于項(xiàng)目的協(xié)同過(guò)濾算法和本文改進(jìn)算法的MAE值的大小，判斷相比于傳統(tǒng)算法，本文所改進(jìn)的推薦算法在推薦質(zhì)量上是否有所提升。如圖4所示，橫軸代表相似用戶集的k值，縱坐標(biāo)代表MAE值?？梢钥闯?，不同k值得情況下，本文改進(jìn)算法的MAE值均小于傳統(tǒng)算法，當(dāng)k為70時(shí)，本文改進(jìn)算法的MAE值最小，推薦效果最好，但當(dāng)k值逐漸增大，MAE值逐漸增大，推薦效果變差，但仍比傳統(tǒng)算法推薦效果好。

圖4 不同算法MAE值比較

通過(guò)實(shí)驗(yàn)分析得出，本文改進(jìn)的算法相比傳統(tǒng)的協(xié)同過(guò)濾算法，提高了推薦的精度，具有更好的推薦效果。

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

本文引入信息熵和用戶標(biāo)簽，并考慮用戶對(duì)標(biāo)簽的興趣變化，提出一種基于信息熵和標(biāo)簽的協(xié)同過(guò)濾算法。該算法更深層地挖掘用戶評(píng)分信息，并且利用用戶標(biāo)簽來(lái)表示用戶的興趣，通過(guò)引入遺忘函數(shù)來(lái)表示用戶興趣的漂移，充分考慮到了用戶評(píng)分偏好等多個(gè)因素。實(shí)驗(yàn)結(jié)果表明，該算法在一定程度上改善了數(shù)據(jù)稀疏的問(wèn)題，提高了推薦精度。此外，對(duì)非線性遺忘函數(shù)中的參數(shù)對(duì)推薦效果的影響本實(shí)驗(yàn)并沒(méi)有做更多探討，動(dòng)態(tài)選取參數(shù)最優(yōu)值是否能獲取更好的推薦效果，這將是下一步的研究工作。

參考文獻(xiàn)

[1] 高娜,楊明.一種改進(jìn)的結(jié)合標(biāo)簽和評(píng)分的協(xié)同過(guò)濾推薦算法[J].南京師大學(xué)報(bào):自然科學(xué)版,2015,38(1):98-103.

[2] 畢孝儒.項(xiàng)目子相似度融合的協(xié)同過(guò)濾推薦算法[J].計(jì)算機(jī)系統(tǒng)應(yīng)用,2015,24(1):147-150.

[3] 郝立燕,王靖.基于項(xiàng)目流行度的協(xié)同過(guò)濾 Top-N 推薦算法[J].計(jì)算機(jī)工程與設(shè)計(jì),2013,34(10):3497-3501.

[4] 王興茂,張興明.基于貢獻(xiàn)因子的協(xié)同過(guò)濾推薦算法[J].計(jì)算機(jī)應(yīng)用研究,2015,32(12):3551-3554.

[5] 張佳,林耀進(jìn),林夢(mèng)雷,等.基于信息熵的協(xié)同過(guò)濾算法[J].山東大學(xué)學(xué)報(bào):工學(xué)版,2016(2):43-50.

[6] 劉文龍,張桂蕓,陳喆,等.基于加權(quán)信息熵相似性的協(xié)同過(guò)濾算法[J].鄭州大學(xué)學(xué)報(bào):工學(xué)版,2012(5):118-120.

[7] 王寶林,韓帥帥,張德海.一種基于社會(huì)化標(biāo)簽的協(xié)同過(guò)濾推薦算法[J].電子科技,2015,28(7):90-93.

[8] 蔡強(qiáng),韓東梅,李海生,等.基于標(biāo)簽和協(xié)同過(guò)濾的個(gè)性化資源推薦[J].計(jì)算機(jī)科學(xué),2014(1):69-71.

[9] 劉健,張琨,陳旋.基于標(biāo)簽和協(xié)同過(guò)濾的個(gè)性化推薦算法[J].計(jì)算機(jī)與現(xiàn)代化,2016(2):62-65.

[10] Zhao X,Niu Z,Chen W.Interest before liking: two-step recommendation approaches[J]. Knowledge-Based Systems,2013,48(2):46-56.

[11] Gan M,Jiang R.Improving accuracy and diversity of personalized recommendation through power law adjustments of user similarities[J].Decision Support Systems,2013,55(3):811-821.

[12] Li X,Roth D.Learning question classifiers: the role of semantic information[C].Beijing:International Conference on Design Automation Conference,2002.

[13] 鄭先榮,湯澤瀅,曹先彬.適應(yīng)用戶興趣變化的非線性逐步遺忘協(xié)同過(guò)濾算法[J].計(jì)算機(jī)輔助工程,2007(2):89-95.

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

[15] Medo M,Yeung H C.Recommender systems[J].Physics Reports,2012,519(1):1-49.