龔 安 孫育紅

（中國石油大學(xué)（華東）計(jì)算機(jī)與通信工程學(xué)院 青島 266580）

1 引言

隨著電子商務(wù)的廣泛普及，推薦系統(tǒng)獲得了極大的發(fā)展并且已經(jīng)應(yīng)用于生活的方方面面。推薦算法是推薦系統(tǒng)的核心，目前常用的推薦算法有協(xié)同過濾推薦［1］、基于知識(shí)的推薦［2］、基于內(nèi)容的推薦［3］、基于圖模型的推薦［4］及混合推薦［5］等。這些推薦算法通過預(yù)測(cè)用戶對(duì)項(xiàng)目的評(píng)分來推薦項(xiàng)目給用戶并且已經(jīng)在各自相應(yīng)的文獻(xiàn)中證明了其有效性。然而在某些情況下，比如在為顧客推薦商品時(shí)，應(yīng)該挑選出特定數(shù)量的商品并將其排列順序給顧客，尤其在網(wǎng)上購物時(shí)，一個(gè)包含特定數(shù)量商品的排名列表更受顧客歡迎。這類情況下，項(xiàng)目的排名被認(rèn)為要比預(yù)測(cè)用戶對(duì)項(xiàng)目的評(píng)分更重要。因此研究找到排名前n位的項(xiàng)目推薦即TOP-N推薦［6～7］而不是單純預(yù)測(cè)用戶對(duì)項(xiàng)目的評(píng)分是很有必要的。

基于RWR的方法［8～9］就是一種TOP-N推薦，它將概率統(tǒng)計(jì)模型中的隨機(jī)游走算法引入到個(gè)性化推薦中，通過計(jì)算項(xiàng)目集和用戶集的用戶-項(xiàng)目排序矩陣來計(jì)算用戶對(duì)項(xiàng)目的偏好程度，在評(píng)估排名結(jié)果度量上明顯要優(yōu)于傳統(tǒng)的協(xié)同過濾算法。文獻(xiàn)［10］在隨機(jī)游走算法的基礎(chǔ)上進(jìn)行了改進(jìn)優(yōu)化，提出了一種基于項(xiàng)目-標(biāo)簽導(dǎo)向的隨機(jī)游走推薦模型，在一定程度上消減了數(shù)據(jù)稀疏性問題和冷啟動(dòng)問題。文獻(xiàn)［11～12］也對(duì)該算法進(jìn)行了不同的改進(jìn)優(yōu)化，有效地提高了精確度和項(xiàng)目的多樣性。然而，上述算法都只考慮了馬爾科夫場(chǎng)中均勻的結(jié)點(diǎn)卻未考慮異相的結(jié)點(diǎn)，一定程度上影響了推薦結(jié)果的精度，并且這些算法在矩陣分解時(shí)消耗的空間代價(jià)極大。

針對(duì)上述問題，將置信度傳播算法（Belief Propagation，BP）［13］引入到推薦系統(tǒng)中隱式地挖掘用戶對(duì)項(xiàng)目的偏好，BP算法利用信息在馬爾科夫場(chǎng)中結(jié)點(diǎn)間的傳遞來計(jì)算目標(biāo)結(jié)點(diǎn)的置信度，將其引入TOP-N推薦系統(tǒng)能避免上述問題。另外，考慮到BP算法在計(jì)算置信度時(shí)采用全局的結(jié)點(diǎn)，有較大的冗余計(jì)算，因此先將其優(yōu)化改進(jìn)，采用自適應(yīng)大小區(qū)域內(nèi)的結(jié)點(diǎn)計(jì)算置信度，然后引入推薦系統(tǒng)［14～15］建立新模型:將用戶集和項(xiàng)目集作為兩個(gè)結(jié)點(diǎn)集合建立二分圖，用戶對(duì)項(xiàng)目的評(píng)分作為用戶結(jié)點(diǎn)和項(xiàng)目結(jié)點(diǎn)的邊緣閾值，通過置信度在項(xiàng)目結(jié)點(diǎn)和用戶結(jié)點(diǎn)之間的傳遞來迭代計(jì)算目標(biāo)結(jié)點(diǎn)置信度，根據(jù)最終置信度大小生成排名列表。通過實(shí)驗(yàn)發(fā)現(xiàn)，改進(jìn)后的BP算法在不損失精度的前提下，效率遠(yuǎn)高于傳統(tǒng)BP算法，并且在Precision值和Recall值和MAP值三方面均優(yōu)于協(xié)同過濾算法和基于RWR的方法。

2 BP算法

置信度傳播算法是基于馬爾科夫隨機(jī)場(chǎng)的一種近似計(jì)算，馬爾科夫場(chǎng)中的結(jié)點(diǎn)是成對(duì)的，分為隱式和顯式兩個(gè)狀態(tài)。置信度傳播算法利用迭代的算法在結(jié)點(diǎn)與結(jié)點(diǎn)之間傳遞信息，從而利用這些信息及當(dāng)前結(jié)點(diǎn)的狀態(tài)來推斷相鄰結(jié)點(diǎn)的狀態(tài)，進(jìn)而更新當(dāng)前整個(gè)馬爾科夫場(chǎng)的標(biāo)記狀態(tài)，它可以解決概率圖模型的概率推斷問題，且所有問題并行實(shí)現(xiàn)，多次迭代后，所有結(jié)點(diǎn)的置信度不再發(fā)生變化，達(dá)到最優(yōu)狀態(tài)，此時(shí)的馬爾科夫場(chǎng)也達(dá)到收斂狀態(tài)。

馬爾科夫場(chǎng)的兩個(gè)關(guān)鍵過程:

1）加權(quán)乘積計(jì)算所有結(jié)點(diǎn)信息；

2）信息在隨機(jī)場(chǎng)中的傳遞。

一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)傳遞的信息叫做信息向量，向量中元素的個(gè)數(shù)等于該結(jié)點(diǎn)可能所處的狀態(tài)數(shù)目。信息向量的計(jì)算由式（1）獲得:

其中，mij(X)表示結(jié)點(diǎn)i傳遞給結(jié)點(diǎn)j的消息，表示在 X 狀態(tài)下，i對(duì)j的置信度。N（j）i表示結(jié)點(diǎn) j的MRF一階鄰域中不包含結(jié)點(diǎn)i的鄰域。Φi(Y)表示結(jié)點(diǎn)i處于Y狀態(tài)下的結(jié)點(diǎn)勢(shì)能。Ψij(Y,X)表示當(dāng)j的鄰結(jié)點(diǎn)i處于Y狀態(tài)時(shí)j處于X狀態(tài)的概率，由傳播矩陣獲得，傳播矩陣在4.3節(jié)中給出。

圖1演示信息傳遞過程。

圖1 信息傳遞機(jī)制

此時(shí)，結(jié)點(diǎn)i處于狀態(tài)X的置信度為式（2）所示:

其中，k是歸一化因子，最終的置信度代表結(jié)點(diǎn)處于相應(yīng)狀態(tài)的可能性。

3 改進(jìn)BP算法

在計(jì)算目標(biāo)結(jié)點(diǎn)的置信度時(shí)傳統(tǒng)BP算法考慮了整個(gè)馬爾科夫場(chǎng)中所有結(jié)點(diǎn)對(duì)當(dāng)前結(jié)點(diǎn)的影響，運(yùn)算效率低，而如果只考慮以該結(jié)點(diǎn)為中心，自適應(yīng)大小的區(qū)域內(nèi)結(jié)點(diǎn)對(duì)目標(biāo)結(jié)點(diǎn)的影響，則可以大大降低時(shí)間復(fù)雜度，從而提高算法效率。

信息在整個(gè)馬爾科夫場(chǎng)各結(jié)點(diǎn)之間傳遞時(shí)，結(jié)點(diǎn)之間相互的影響因結(jié)點(diǎn)與目標(biāo)結(jié)點(diǎn)距離而存在差異，與目標(biāo)結(jié)點(diǎn)距離較近的結(jié)點(diǎn)可能對(duì)目標(biāo)結(jié)點(diǎn)影響較強(qiáng)，距離較遠(yuǎn)的結(jié)點(diǎn)可能影響較弱，所以以目標(biāo)結(jié)點(diǎn)為中心，考慮不同大小區(qū)域半徑內(nèi)的結(jié)點(diǎn)對(duì)目標(biāo)結(jié)點(diǎn)的影響，結(jié)果如圖2所示。

圖2 未收斂結(jié)點(diǎn)比例示意圖

由圖2可看出BP算法在馬爾科夫隨機(jī)場(chǎng)中不同區(qū)域半徑下的結(jié)點(diǎn)收斂情況。假設(shè)區(qū)域半徑為r，即只考慮與目標(biāo)結(jié)點(diǎn)距離小于等于r的結(jié)點(diǎn)，該區(qū)域內(nèi)所有結(jié)點(diǎn)對(duì)目標(biāo)結(jié)點(diǎn)傳遞信息后后者的置信度為mr，同時(shí)假設(shè)傳統(tǒng)BP算法所對(duì)應(yīng)的區(qū)域半徑為l，即r充分大的情況下，該區(qū)域內(nèi)所有結(jié)點(diǎn)對(duì)目標(biāo)的置信度為 ml，r=1，2，…，l，設(shè)定閾值 ε，當(dāng)‖mr-ml‖＜ε時(shí)即可認(rèn)為是收斂。由圖2可知，每一個(gè)結(jié)點(diǎn)只需較小區(qū)域內(nèi)的置信度更新即可收斂，所以自適應(yīng)區(qū)域大小的算法可以有效減少傳統(tǒng)BP算法中的冗余計(jì)算，所以僅更新未收斂結(jié)點(diǎn)的置信度信息，即當(dāng)‖mr- ml‖＜ε時(shí)，認(rèn)為已經(jīng)達(dá)到收斂狀態(tài)，此時(shí)不再擴(kuò)大置信度的更新范圍。ε的取值在4.4節(jié)中給出。

4 基于改進(jìn)BP算法的個(gè)性化推薦算法

4.1 二分圖模型的建立

創(chuàng)建一個(gè)用戶關(guān)于項(xiàng)目偏好的二分圖，將用戶集合和項(xiàng)目集合作為兩個(gè)結(jié)點(diǎn)集合，建立二分圖。結(jié)點(diǎn)的狀態(tài)分為喜歡和不喜歡兩個(gè)狀態(tài)。為了提高準(zhǔn)確度，設(shè)定當(dāng)評(píng)分高于某個(gè)閾值時(shí)認(rèn)為用戶喜歡該項(xiàng)目，否則認(rèn)為不喜歡該項(xiàng)目，當(dāng)評(píng)分高于這個(gè)閾值時(shí)建立用戶結(jié)點(diǎn)和該項(xiàng)目結(jié)點(diǎn)的邊，閾值的選擇在5.1節(jié)中給出。

4.2 結(jié)點(diǎn)勢(shì)能的計(jì)算

結(jié)點(diǎn)勢(shì)能是基于項(xiàng)目評(píng)分的。因?yàn)樵O(shè)定了兩種狀態(tài):喜歡和不喜歡，所以結(jié)點(diǎn)勢(shì)能也有兩種，每個(gè)結(jié)點(diǎn)勢(shì)能需分配0.1～0.9之間的某個(gè)值，并且一個(gè)結(jié)點(diǎn)的兩個(gè)結(jié)點(diǎn)勢(shì)能的和應(yīng)該為1。目標(biāo)用戶的評(píng)分越高，在喜歡狀態(tài)下的結(jié)點(diǎn)勢(shì)能就越大。結(jié)點(diǎn)勢(shì)能由式（3）獲得:

其中，lij表示喜歡狀態(tài)下的結(jié)點(diǎn)勢(shì)能，dij表示不喜歡狀態(tài)下的結(jié)點(diǎn)勢(shì)能，Score(i,j)表示目標(biāo)用戶i對(duì)項(xiàng)j的評(píng)分。常數(shù)p是歸一化因子。如果獲得的結(jié)點(diǎn)勢(shì)能低于0.1或高于0.9，用0.1或0.9代替。未被評(píng)分項(xiàng)目的結(jié)點(diǎn)勢(shì)能初始化時(shí)在兩種狀態(tài)下均分配為0.5。

4.3 傳播矩陣的建立

兩結(jié)點(diǎn)間勢(shì)函數(shù)值Ψij（Y，X）由傳播矩陣獲得，表示當(dāng)j的鄰結(jié)點(diǎn)i處于Y狀態(tài)時(shí)j處于X狀態(tài)的概率。在推薦算法中，將兩個(gè)狀態(tài)分別設(shè)定為喜歡和不喜歡，表1是一個(gè)傳播矩陣的例子，為避免數(shù)字下溢，α設(shè)定為一個(gè)很小的值。

表1 傳播矩陣示例

4.4 置信度消息的更新

大部分馬爾科夫場(chǎng)中的結(jié)點(diǎn)在受到其某一鄰域范圍內(nèi)結(jié)點(diǎn)的信息傳遞后其置信度是趨于收斂的，改進(jìn)BP算法僅更新尚未收斂結(jié)點(diǎn)的置信度而忽略這些收斂結(jié)點(diǎn)。因此在計(jì)算置信度過程中無需計(jì)算整個(gè)馬爾科夫場(chǎng)中所有結(jié)點(diǎn)的置信度，而只要在計(jì)算前對(duì)結(jié)點(diǎn)進(jìn)行收斂判斷，若收斂，則不用計(jì)算，若不收斂，則迭代計(jì)算其置信度。收斂閾值的選取就顯得尤為重要。如果選取閾值過大，一些尚未收斂的結(jié)點(diǎn)會(huì)被錯(cuò)誤判定為收斂結(jié)點(diǎn)而停止計(jì)算，導(dǎo)致計(jì)算結(jié)果精度降低；如果選取閾值過小，因?yàn)樵诿看胃轮眯哦葧r(shí)都需要判斷是否收斂，所以會(huì)增加計(jì)算量，而不能有效提高算法效率。綜上所述，選擇合理的閾值是非常必要的。

為了降低實(shí)驗(yàn)復(fù)雜度，對(duì)‖mr- ml‖＜ε稍作修改，改為判定每個(gè)結(jié)點(diǎn)在相鄰兩次信息傳遞后的誤差值小于某個(gè)特定閾值，即‖bi+1(X)-bi(X)‖＜ω，經(jīng)過多次實(shí)驗(yàn)驗(yàn)證當(dāng)ω=1和ω=2時(shí)，該算法最優(yōu)，在實(shí)驗(yàn)部分給出說明。在迭代計(jì)算完成后，根據(jù)最終置信度大小排名生成列表，選取TOP-N項(xiàng)目列表推薦給目標(biāo)用戶。

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

實(shí)驗(yàn)數(shù)據(jù)是由美國明尼蘇達(dá)大學(xué)GroupLeans項(xiàng)目提供的開源MovieLens數(shù)據(jù)集，包含72000名用戶對(duì)10000部電影的1000萬條評(píng)分?jǐn)?shù)據(jù)，對(duì)電影的評(píng)分取1～5之間的整數(shù)值，從中選取了包含943個(gè)用戶對(duì)1682個(gè)電影的10000條評(píng)分?jǐn)?shù)據(jù)進(jìn)行實(shí)驗(yàn)。實(shí)驗(yàn)數(shù)據(jù)劃分為訓(xùn)練集和測(cè)試集，訓(xùn)練集和測(cè)試集的比例為4∶1，傳播矩陣中α的取值為0.0001。

5.1 邊緣閾值

在實(shí)驗(yàn)數(shù)據(jù)集中，用戶對(duì)項(xiàng)目的評(píng)分值是1到5之間的整數(shù)，所以需在該區(qū)域內(nèi)選取值作為結(jié)點(diǎn)與結(jié)點(diǎn)之間邊緣閾值，為了在實(shí)驗(yàn)中得到更精確的結(jié)果，考慮1和5之間（不包含1和5）的整數(shù)以及評(píng)分的算術(shù)平均值和幾何平均值（GM）作為邊緣閾值進(jìn)行實(shí)驗(yàn)觀察其各項(xiàng)評(píng)測(cè)指標(biāo)，實(shí)驗(yàn)結(jié)果如表2所示。

表2 不同邊緣閾值下性能比較

上述實(shí)驗(yàn)為傳統(tǒng)BP算法實(shí)驗(yàn)結(jié)果，這是因?yàn)?，?duì)于改進(jìn)BP算法或者傳統(tǒng)BP算法，閾值的選擇是可以一致的，從表2可以看出，邊緣閾值取算術(shù)平均值和幾何平均值的結(jié)果最好，相比之下選取算術(shù)平均值作為邊緣閾值。

5.2 ω的選擇

將傳統(tǒng)BP算法和參數(shù)ω=1，2的改進(jìn)BP算法的運(yùn)算時(shí)間做對(duì)比，即在不同區(qū)域半徑下對(duì)比三種算法的運(yùn)算時(shí)間，實(shí)驗(yàn)結(jié)果如表3所示。

從表3中可以看出:隨著區(qū)域半徑的變大，BP算法的運(yùn)算時(shí)間呈線性增長，而改進(jìn)BP算法的運(yùn)算時(shí)間增長較緩；ω=2的改進(jìn)BP算法表現(xiàn)效果更好一些（下文均用ω=2的改進(jìn)BP算法）。

表3 不同半徑區(qū)域下的各算法運(yùn)算時(shí)間比較

5.3 與傳統(tǒng)BP算法的性能比較

將改進(jìn)BP算法應(yīng)用到推薦系統(tǒng)后與傳統(tǒng)BP算法性能比較，實(shí)驗(yàn)結(jié)果如表4所示。

表4 與傳統(tǒng)BP算法的性能比較

從表4可以看出，考慮全局結(jié)點(diǎn)的傳統(tǒng)BP算法與改進(jìn)BP算法在各項(xiàng)性能指標(biāo)中并無明顯差別，但是結(jié)合表3可知，在運(yùn)算時(shí)間上后者明顯優(yōu)于前者。

5.4 不同推薦算法的性能比較

將基于項(xiàng)目的協(xié)同過濾算法中的參數(shù)k設(shè)置為30，此時(shí)該算法的精確度能達(dá)到最優(yōu)。對(duì)于基于RWR的方法，將高于用戶平均評(píng)分的評(píng)分設(shè)為邊緣閾值，給目標(biāo)用戶的重啟向量元素設(shè)為1，其他用戶的設(shè)為0，重啟概率設(shè)為0.15，三種算法在精確度、召回率和MAP值指標(biāo)的比較如圖3所示。

圖3 不同推薦算法的性能比較

由圖3可看出，基于RWR的方法在精確度、召回率和MAP值三個(gè)指標(biāo)上均遠(yuǎn)高于基于項(xiàng)目的算法，這是因?yàn)榛赗WR的方法采用迭代隨機(jī)游走，能夠推斷結(jié)點(diǎn)之間的隱式關(guān)系。這也是基于項(xiàng)目的算法的一個(gè)缺陷。而改進(jìn)BP算法要優(yōu)于基于RWR的方法，因?yàn)楹笳咧豢紤]均勻的結(jié)點(diǎn)，而BP同時(shí)考慮了均勻和異相［16］。另一方面，改進(jìn)BP算法既計(jì)算了目標(biāo)用戶偏好結(jié)點(diǎn)的可能性，也計(jì)算了不喜歡結(jié)點(diǎn)的可能性。因此，基于改進(jìn)BP算法的推薦算法優(yōu)于基于項(xiàng)目的協(xié)同過濾算法和基于RWR的方法。

6 結(jié)語

將概率統(tǒng)計(jì)中的置信度傳播算法改進(jìn)優(yōu)化后引入到個(gè)性化推薦系統(tǒng)中建立了新的推薦模型，把用戶集合和項(xiàng)目集合分別作為結(jié)點(diǎn)集合建立二分圖，通過置信度在馬爾科夫場(chǎng)中的傳遞規(guī)律來獲取用戶的偏好，然后根據(jù)最終置信度大小排名生成了一個(gè)推薦列表給用戶。用自適應(yīng)大小區(qū)域內(nèi)的結(jié)點(diǎn)計(jì)算目標(biāo)結(jié)點(diǎn)置信度，比傳統(tǒng)BP算法運(yùn)算時(shí)間更少，同時(shí)避免了基于RWR的方法存在的一些不足，又不失推薦項(xiàng)目的多樣性。通過實(shí)驗(yàn)將提出的算法分別與傳統(tǒng)BP算法、基于項(xiàng)目的算法和基于RWR的方法做比較，結(jié)果表明，提出的算法在各項(xiàng)評(píng)測(cè)指標(biāo)方面表現(xiàn)更好，是一種有效的算法。