協(xié)同過濾推薦算法改進(jìn)分析研究

潘燕梅

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

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

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

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

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

1.1 改進(jìn)背景

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

(1)

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

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

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

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

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

1.2.1 計(jì)算評(píng)分差值

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

Diff(u,v)=ru-rv

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

=(d1,d2,…,dn)

(2)

1.2.2 計(jì)算評(píng)分差值熵

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

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

(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是比較了三種相似度計(jì)算方法對(duì)預(yù)測(cè)精度的影響結(jié)果，可以發(fā)現(xiàn)基于信息熵的相似性計(jì)算方法預(yù)測(cè)精度較其他方法高。

圖1 Sarwar的相似度計(jì)算方法比較

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

2.1 改進(jìn)背景

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

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

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

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

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

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

(6)

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

表2 近鄰選擇方法一

表3 近鄰選擇方法二

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

2.2 雙重閾值近鄰選擇

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

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

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

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

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

2.3 算法分析

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

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

表4 雙重閾值法

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

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

3.1 改進(jìn)背景

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

3.2 重要性程度因子

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

(7)

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

圖2 用戶和項(xiàng)目評(píng)分矩陣的二分圖

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

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

(8)

(9)

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

3.3 算法分析

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

(10)

其中，Pu,i是用戶u對(duì)項(xiàng)目i的預(yù)測(cè)評(píng)分，Ru,i是用戶u對(duì)項(xiàng)目i的真實(shí)評(píng)分，M是測(cè)試集。

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

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

4 結(jié) 論

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

參考文獻(xiàn):

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

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

[3]劉文龍.基于加權(quán)信息熵相似度的協(xié)同過濾算法研究[D].天津：天津師范大學(xué)計(jì)算機(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]蔡觀洋.個(gè)性化推薦中協(xié)同過濾算法的改進(jìn)研究[D].吉林：吉林大學(xué)計(jì)算機(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ì)算機(jī)工程與設(shè)計(jì),2013,34(8):2750-2753