潘燕梅

黃山職業(yè)技術(shù)學(xué)院工業(yè)與財貿(mào)系，黃山，245200

隨著互聯(lián)網(wǎng)和電子商務(wù)的發(fā)展，個性化推薦系統(tǒng)得到了越來越多研究者的關(guān)注。而隨著“互聯(lián)網(wǎng)+”概念的提出以及目前人工智能的不斷發(fā)展，個性化推薦開始走向人們生活的各個領(lǐng)域，并且向著更深的方向發(fā)展[1]。目前,不管是簡單的利用搜索引擎上網(wǎng)搜索,還是利用網(wǎng)上購物平臺進(jìn)行購物，都能體會到個性化推薦系統(tǒng)給人們生活帶來的極大便利。

協(xié)同過濾推薦算法作為個性化推薦系統(tǒng)最早也是最重要的算法之一，其基本思想是基于相似用戶對項目進(jìn)行的評分，然后向目標(biāo)用戶產(chǎn)生推薦。由于相似用戶的喜好基本一致，因此目標(biāo)用戶對未知項目的評分可以根據(jù)近鄰用戶的評分來預(yù)測[2]。

然而，隨著系統(tǒng)規(guī)模的不斷擴(kuò)大，用戶-項目評分矩陣將極度稀疏，從而造成傳統(tǒng)算法在相似度度量、近鄰集選擇以及預(yù)測評分上產(chǎn)生更大的精度誤差，進(jìn)而導(dǎo)致推薦質(zhì)量急劇下降。為此，本文選取了三個典型的改進(jìn)型協(xié)同過濾推薦算法，并從上述三個方面對算法進(jìn)行綜合分析研究和實驗驗證。結(jié)果表明，基于熵的相似度計算、雙重閾值近鄰集查找以及用戶或者項目重要性程度因子對協(xié)同過濾推薦算法的準(zhǔn)確度均有明顯提升。

1 基于加權(quán)信息熵相似度的協(xié)同過濾推薦算法

1.1 改進(jìn)背景

傳統(tǒng)的協(xié)同過濾推薦算法相似度計算方法為Pearson相關(guān)系數(shù)[1-2]，用戶u和v的相似度可以表示為：

(1)

Pearson相關(guān)系數(shù)在一定程度上很好地刻畫了用戶間的相似度值，然而Pearson相關(guān)系數(shù)未考慮共同評分項目數(shù)量對相似度計算的影響，容易導(dǎo)致用戶間的相似度計算不是很合乎實際。

表1 用戶-項目評分矩陣示值例

考慮表1所示的用戶-項目評分矩陣，用戶1和用戶4只有共同評分項目8。根據(jù)Pearson相關(guān)系數(shù)可計算得到它們之間的相似度為1；而用戶5和用戶4的相似度卻只有0.610 8。結(jié)果表明，用戶1和用戶4比用戶5和用戶4更相似。然而，實際數(shù)據(jù)表明，用戶1與用戶4只有一個共同評分項目，而用戶5與用戶4一共有4個共同評分項目，其中3個共同項目的評分值是一樣的，且與項目10的評分差異也不是很大，理應(yīng)用戶5和用戶4更相似。因此，Pearson相關(guān)系數(shù)法在相似度計算上存在一定的不足。

1.2 基于加權(quán)信息熵的相似度度量

由信息熵概念可知，如果一個系統(tǒng)越簡單，那么它的熵值越??；反之，它的熵值越大。為此，可以引入熵的概念來描述用戶間的相似度[3]：若兩個用戶的評分差異熵值越小，則這兩個用戶相似度越大；反之，則這兩個用戶的相似度越小。同時為了保證相似度計算的準(zhǔn)確性，還應(yīng)考慮兩個因素，即若兩個用戶的評分差值越大，則其相似度越??；用戶之間共同評分項目數(shù)量n越少，相似度越低。該算法的具體計算步驟如下：

1.2.1 計算評分差值

為了計算用戶u和用戶v的相似度sim(u,v),開始根據(jù)用戶u和用戶v的共同評分向量ru=[ru1,ru2,…，run]和rv=[rv1,rv2,…，rvn]，計算用戶u和用戶v的共同評分差值:

Diff(u,v)=ru-rv

=(ru1-rv1,ru2-rv2,…,run-rvn)

=(d1,d2,…,dn)

(2)

1.2.2 計算評分差值熵

1.2.3 計算加權(quán)差值熵

為了考慮用戶間評分差值大小在計算相似度中對相似度的影響，引入加權(quán)因子|d(pi)|來計算用戶u和用戶v的共同評分差值熵：

(3)

其中，d(pi)表示用戶u和用戶v之間發(fā)生概率為pi的差值大小。

(4)

1.2.4 歸一化處理

(5)

其中，min(JWH)和max(JWH)分別表示JWH中的最小值和最大值。由公式(5)可知，用戶u和用戶v的NJWH值在0和1之間，NJWH值越小，兩者相似度越小，NJWH值越大，用戶u和用戶v越相似。

1.3 算法分析

圖1是比較了三種相似度計算方法對預(yù)測精度的影響結(jié)果，可以發(fā)現(xiàn)基于信息熵的相似性計算方法預(yù)測精度較其他方法高。

圖1 Sarwar的相似度計算方法比較

2 雙重閾值協(xié)同過濾算法

2.1 改進(jìn)背景

在近鄰集選擇上，傳統(tǒng)的協(xié)同過濾推薦算法大多采用Top-K[4]法進(jìn)行近鄰集的選擇，即按照與目標(biāo)用戶或目標(biāo)項目的相似度大小由大到小進(jìn)行排列，取最高的K個項目或者用戶作為鄰近集。為了研究方便，本節(jié)通過基于用戶的協(xié)同過濾算法來說明傳統(tǒng)的協(xié)同過濾算法中近鄰查找策略的不足。

目前，針對目標(biāo)用戶U1對項目P1評分預(yù)測的過程，選擇出目標(biāo)用戶U1的K個鄰近用戶通常有以下兩種方法。

方法一：全局考慮，直接按照和用戶U1相似度大小，選擇最高的K個用戶作為鄰近用戶集；

方法二：只考慮參與過項目P1評分的用戶，然后根據(jù)這些用戶與目標(biāo)用戶U1的相似度大小，選擇最高的K個用戶作為鄰近用戶集；

方法一考慮了與目標(biāo)用戶U1相似的條件，它從用戶集中選擇與目標(biāo)用戶最相似的K個用戶，然而，方法一選擇出來的最相似K個用戶會存在從未對項目P1進(jìn)行評分的用戶。若選取的K個用戶中只存在一個用戶對項目P1進(jìn)行過評分，那么真正參與到目標(biāo)用戶評分預(yù)測過程中的就只有一個用戶。顯然，這種方法就很容易放大個別用戶的作用權(quán)重。而方法二保證了每次能參與到目標(biāo)用戶U1評分預(yù)測過程中確實有K個用戶存在，但該方法容易導(dǎo)致不是和目標(biāo)用戶真正相似的用戶參與到目標(biāo)用戶的評分過程中來。

為了定量刻畫方法一與方法二的不足，引入用戶組相似度Nsim(u,m)和參考近鄰比例Neibr(u,m)兩個參數(shù)分別刻畫整個近鄰集的相似度大小和近鄰集中含有對目標(biāo)項目有過評分的用戶數(shù)量大小[5]，定義如下：

(6)

其中,N(u,m)表示真正參與到目標(biāo)用戶u對項目m評分過程中的近鄰集，sim(u,v)為用戶v與目標(biāo)用戶u的相似度，K為Top-K法中的K值。表2和表3是分別利用上述兩種方法基于MovieLens數(shù)據(jù)集，對不同的K值，針對編號為1的客戶對編號為273的項目的評分過程計算的用戶組相似度和參考近鄰比例值。MovieLens數(shù)據(jù)集是GroupLens項目組收集的用戶對電影評分?jǐn)?shù)據(jù)集，本文所使用數(shù)據(jù)集大小為1MB，包含了約6 000個用戶對4 000部電影的100萬個匿名評分，評分值限定為1～5之間的整數(shù)。

表2 近鄰選擇方法一

表3 近鄰選擇方法二

從表2和表3的計算結(jié)果可知，方法一的近鄰選擇方法雖然能取得較大的相似度值，但是其參考近鄰比例很小。相反，方法二中參考近鄰比例都能保證為1，即所選擇的用戶都參與到用戶1的評分過程中。然而，其選擇的用戶相似度值不是很高。分析發(fā)現(xiàn)，近鄰集的選擇會嚴(yán)重關(guān)系到推薦精度的大小，如何克服輸入評分矩陣的稀疏性，查找出最佳鄰近集是協(xié)同過濾算法的關(guān)鍵。

2.2 雙重閾值近鄰選擇

通過前面分析發(fā)現(xiàn)，在選擇鄰近用戶集時，要想選擇出最佳的鄰近用戶集，就必須充分考慮參考鄰近比例Neibr(u,m)的大小以及用戶組相似度Nsim(u,m)的大小?；陔p重閾值的協(xié)同過濾算法過程如下：

(1)選擇相似度最大的M個用戶作為預(yù)選集C1，并進(jìn)行排序；

(2)計算預(yù)選集C1中的相似度平均值，以此值作為閾值γ，從C1中選出大于此值的所有用戶作為預(yù)選集C2，從C2中選出參與過項目P1評分的用戶，添加到預(yù)選集C3′中；

(3)若C3′的長度大于K，就從C3′中選出最大的K個用戶，作為最終的鄰近用戶集C3。若C3′的長度小于K，就從C2中選出那些相似度最高并且未入選鄰近用戶集C3′的用戶，作為用戶集C3″，和用戶集C3′一起添加到C3中，使得C3最終的長度為K；

(4)由于用戶集C3″中的用戶沒有對項目P1進(jìn)行過評分，為此計算C3″中用戶的平均評分值作為對項目P1的評分值。

2.3 算法分析

分析該算法的鄰近用戶集選擇策略，可以發(fā)現(xiàn)該算法首先考慮了相似度條件；其次，在相似度達(dá)到一定值的時候，算法優(yōu)先考慮那些對目標(biāo)項目有過評分的用戶，只有用戶對目標(biāo)項目已有過評分，才能利用這些評分對目標(biāo)用戶進(jìn)行評分預(yù)測。

根據(jù)雙重閾值協(xié)同過濾算法可計算得到用戶1對項目273預(yù)測評分中的用戶組相似度值和參考近鄰比例，如表4所示。

表4 雙重閾值法

對比表2、3和4可以發(fā)現(xiàn)雙重閾值方法兼顧了用戶組相似度和參考近鄰比例兩個條件。

3 基于重要性排名的協(xié)同過濾推薦算法

3.1 改進(jìn)背景

用戶-項目評分矩陣中不同的用戶u和項目p在這個評分矩陣中的重要性程度往往是不一致的。如網(wǎng)上書店的推薦系統(tǒng)，用戶ui買了1 000本不同的書，而用戶uj買了10本不同的書，顯然用戶ui在推薦過程中的作用要大于uj，即用戶ui的評分更具有權(quán)威性。因此在ui和uj與目標(biāo)用戶u具有同樣相似度時，用戶ui對目標(biāo)項目的評分作用要大于uj的評分作用。同樣如果一本書被越多的用戶購買過，它的重要性也越大。因此項目的重要性程度會對用戶的相似性產(chǎn)生一定作用[6-7]。

3.2 重要性程度因子

記用戶u的重要性程度因子UR(u)，項目i重要性程度因子IR(i)。越重要的用戶對推測評分結(jié)果的影響越大而越重要的項目對用戶相似度影響越小。進(jìn)而，改進(jìn)的相似度計算方法和評分預(yù)測方法可以表示為：

(7)

公式(7)說明了改進(jìn)的預(yù)測評分方法，從公式可知，要想計算得到用戶u對項目i的評分就必須計算出用戶u的重要性程度因子UR(u)和項目i的重要性程度因子IR(i)。

圖2 用戶和項目評分矩陣的二分圖

如圖2所示是用戶和項目評分矩陣的二分圖，其中有連接邊表示用戶對項目進(jìn)行過評分，a、b、c分別表示相應(yīng)項目的初始重要性程度值。

系統(tǒng)中所有的節(jié)點將自己的重要性程度平均傳遞給與之相連接的節(jié)點(鄰居節(jié)點)。首次重要性傳送過程中，各個項目節(jié)點將本身的重要性程度平均傳送給鄰居節(jié)點，如圖2(a)所示。再次重要性傳送過程中，各個用戶將自己的重要性程度平均傳送給鄰居節(jié)點，如圖2(b)所示。這兩次傳遞稱之為一次迭代過程，并循環(huán)往復(fù)進(jìn)行迭代，直至每個節(jié)點的重要性程度收斂到某一特定值。這兩次重要性程度傳遞過程可以用公式(8)和(9)分別表示為用戶u的重要性程度值UR(u)和項目v的重要性程度值IR(i)：

(8)

(9)

其中，N(i)為與項目i相聯(lián)系的用戶數(shù)量，Iu為與用戶u相聯(lián)系的項目集；N(u)為與用戶u有聯(lián)系的項目個數(shù)，U(i)為與項目i有聯(lián)系的用戶集。

3.3 算法分析

為了驗證引入重要性程度因子帶來的性能提升，本文以MovieLens 1M數(shù)據(jù)集為研究對象，隨機(jī)選擇不同大小的子矩陣，并以平均均方誤差(Mean Square Error, MSE)作為指標(biāo)進(jìn)行測試驗證。平均均方誤差的定義如下：

(10)

其中，Pu,i是用戶u對項目i的預(yù)測評分，Ru,i是用戶u對項目i的真實評分，M是測試集。

圖3所示是基于重要性程度因子算法和傳統(tǒng)算法性能指標(biāo)對比圖，可以看出基于重要性程度因子算法的均方誤差明顯小于傳統(tǒng)算法，預(yù)測性能有較大提升。

圖3 MSE指標(biāo)對比

4 結(jié) 論

本文針對協(xié)同過濾推薦算法的三大核心：相似度計算、近鄰集選擇以及預(yù)測評分對改進(jìn)算法進(jìn)行了詳細(xì)的分析和實驗驗證。分析和實驗結(jié)果表明，基于熵的相似度計算能夠有效克服傳統(tǒng)算法未考慮共同評分項目數(shù)量帶來的影響、雙重閾值近鄰集選擇有效克服了傳統(tǒng)算法在近鄰集選擇上無法選出最相似且對評分作用最大近鄰的弊端，以及基于重要性排名算法可通過引入重要性程度因子進(jìn)一步提升協(xié)同過濾算法的精度。因此，下一步工作是如何綜合上述三種算法的優(yōu)點，對傳統(tǒng)算法進(jìn)行聯(lián)合改進(jìn)設(shè)計，以此進(jìn)一步提升個性化推薦質(zhì)量。

參考文獻(xiàn):

[1]項亮.推薦系統(tǒng)實踐[M].北京：人民郵電出版社,2012:23-28

[2]鄧愛林,朱揚勇,施伯樂.基于項目評分預(yù)測的協(xié)同過濾推薦算法[J].軟件學(xué)報,2003,14(9):1621-1628

[3]劉文龍.基于加權(quán)信息熵相似度的協(xié)同過濾算法研究[D].天津：天津師范大學(xué)計算機(jī)與信息工程學(xué)院,2013：38-43

[4]Hurley N,Zhang M.Novelty and diversity in top-nrecommendation-analysis and evaluation[J].ACM Transactions on Internet Technology (TOIT),2011,10(4):14

[5]蔡觀洋.個性化推薦中協(xié)同過濾算法的改進(jìn)研究[D].吉林：吉林大學(xué)計算機(jī)學(xué)院,2013：36-39

[6]Zeng W,Zhu Y X,Lü L,et al.Negative ratings play a positive role in information filtering[J].Physica A:Statistical Mechanics and its Applications, 2011,390(23):4486-4493

[7]王斌斌,蔡照鵬,白培發(fā).基于重要性排名的協(xié)同過濾推薦算法[J].計算機(jī)工程與設(shè)計,2013,34(8):2750-2753