侯繼昌，陳家琪

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

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

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

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

1 相關(guān)工作

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

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

1.1.1 相似度計算

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

(1)

(2)

(3)

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

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

(4)

1.2 信息熵定義

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

(5)

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

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

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

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

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

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

(15)

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

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

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

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

(16)

其中，0≤m≤1,0

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

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

(17)

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

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

(18)

3 評分信息熵的相似度計算

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

3.1 計算用戶評分信息熵來過濾噪點數(shù)據(jù)

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

用戶評分之間的信息熵

(6)

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

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

3.2 計算用戶間評分差值信息熵

3.2.1 計算兩個用戶間的評分差值

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

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

(7)

其中，dk=ruik-rvik。

3.2 引入Jaccard函數(shù)改進用戶評分差值信息熵

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

(8)

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

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

f=1/J(u,v)

(9)

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

(10)

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

(11)

3.2.2 將用戶間評分差信息熵進行歸一化

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

(12)

3.3 結(jié)合PCC計算用戶評分的相似度

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

(13)

綜上，本文最終基于用戶評分的相似度計算方法為

(14)

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

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

(19)

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

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

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

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

輸出目標(biāo)用戶u對待評分項目i的預(yù)測評分。

a) 根據(jù)用戶項目評分信息利用式 (6) 來計算信息熵，設(shè)置閾值τ，來過濾噪點；

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

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

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

f) 通過集合Su和式 (4) 計算出目標(biāo)用戶u對項目i的評分，產(chǎn)生Top-N推薦

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

5.1 實驗數(shù)據(jù)

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

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

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

(20)

其中,Pui計算得出對項目i的預(yù)測評分值，tui為用戶對項目的實際評分值；N為待測集中的項目總數(shù)。

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

5.3.1 過濾噪點數(shù)據(jù)

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

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

5.3.2 實驗結(jié)果

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

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

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

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

圖4 不同算法MAE值比較

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

6 結(jié)束語

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

參考文獻(xiàn)

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

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

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

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

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

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

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

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

[9] 劉健,張琨,陳旋.基于標(biāo)簽和協(xié)同過濾的個性化推薦算法[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é)同過濾算法[J].計算機輔助工程,2007(2):89-95.

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

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