杜茂康，王忠思，宋 強(qiáng)

(1.重慶郵電大學(xué) 電子商務(wù)與現(xiàn)代物流重點(diǎn)實(shí)驗(yàn)室，重慶 400065；2.重慶市通信管理局，重慶 401121)

0 引 言

隨著“信息過載”問題的日益突出，個性化推薦服務(wù)研究備受青睞。其中，協(xié)同過濾技術(shù)得到了廣泛的研究和應(yīng)用，在基于近鄰的協(xié)同過濾推薦算法中，相似度的計算至關(guān)重要[1-4]。G. Salton等[5]提出了運(yùn)用余弦方法計算信息相似度而檢索信息；B. Sarwar等[6]改進(jìn)了余弦相似度方法計算項(xiàng)目相似度，優(yōu)化了相似度的計算方法；U. Shardanand等[7]用評分值中位數(shù)替代評分值均值提高了皮爾遜系數(shù)度量相似度的準(zhǔn)確性，即CPC(constrained pearson correlation)算法；MSD(mean square difference)算法運(yùn)用均方位移表示相似度，但性能較差；J. Bobadilla等[8]結(jié)合CPC算法和Jaccard系數(shù)度量相似度方法提出了JMSD(combined Jaccard and MSD)算法，雖然解決了過度依賴共同評分項(xiàng)的問題，但仍然存在評分值利用率低的問題；Ahn等[9]提出了PIP(proximity impact popularity)相似度度量模型，考慮用于評分的接近、影響和普及3個方面計算用戶相似性，但沒有考慮用戶全局偏好。相似度方法及計算公式如表1所示。

表1 常用相似度計算方法

已有的研究表明，傳統(tǒng)的相似度計算方法存在過度依賴于共同評分項(xiàng)的問題。當(dāng)共同評分項(xiàng)少時，傳統(tǒng)方法不能準(zhǔn)確地計算用戶或項(xiàng)目之間的相似度。另外，在計算相似度時，上述方法利用的數(shù)據(jù)均為共同評分?jǐn)?shù)據(jù)，忽略了其他的評分信息，這也在一定程度上降低了計算用戶相似度的準(zhǔn)確性。因此，傳統(tǒng)方法在計算用戶或項(xiàng)目之間的相似度時局限性很大，準(zhǔn)確性有待改進(jìn)。

為了解決已有相似度度量方法依賴于共同評分項(xiàng)的問題，Bidyut Kr. Patra等[10]提出了基于Bhattacharyya系數(shù)的相似度度量方法。然而，當(dāng)項(xiàng)目之間相同評分值的絕對數(shù)量差異顯著以及相同評分值個數(shù)占評分值總數(shù)比重小時，運(yùn)用此方法得到相似度準(zhǔn)確性不高。

針對基于Bhattacharyya系數(shù)相似度計算方法存在項(xiàng)目間相同評分值絕對數(shù)量差異顯著的問題，本文運(yùn)用權(quán)重法對其修正；對于相同評分值個數(shù)占評分值總數(shù)比重小的問題，引入拉普拉斯(Laplace)校準(zhǔn)法解決。改進(jìn)后的Bhattacharyya系數(shù)(improved Bhattacharyya coefficient，IBC)能夠利用所有的評分信息，有效提升了相似度的準(zhǔn)確性。基于IBC相似度度量方法在解決基于Bhattacharyya系數(shù)相似度度量方法存在的問題的同時，也保證了較低的時間復(fù)雜度。另外，傳統(tǒng)相似度度量方法存在的數(shù)據(jù)稀疏性、冷啟動以及可擴(kuò)展性等問題嚴(yán)重影響了相似度計算的準(zhǔn)確性，解決這些問題成為相似度度量方法研究的主要趨勢。改進(jìn)的度量方法，有效地緩解了數(shù)據(jù)稀疏性的問題。通過真實(shí)數(shù)據(jù)集實(shí)驗(yàn)表明，IBC描述相似度的準(zhǔn)確性和性能更優(yōu)，更有實(shí)際運(yùn)用價值。

1 基于Bhattacharyya系數(shù)的相似度度量

Bhattacharyya系數(shù)在信號處理、圖像處理和模式識別研究領(lǐng)域已得到廣泛地應(yīng)用[10-12]。它主要用于度量2個概率分布之間的相似度。假設(shè)p1(x)和p2(x)分別表示連續(xù)的分布密度，那么，這2個分布密度之間的相似度，即Bhattacharyya系數(shù)為

(1)

如果X表示離散數(shù)據(jù)，則

(2)

(2)式中：p1(x)和p2(x)分別表示2個離散概率分布中x出現(xiàn)的頻率。項(xiàng)目I和J之間基于Bhattacharyya系數(shù)相似度可表示為

(3)

基于Bhattacharyya系數(shù)的相似度度量方法以評分值的概率密度作為計算相似度的重要依據(jù)。它能夠解決傳統(tǒng)相似度計算方法中存在的數(shù)據(jù)稀疏性和過度依賴共同評分項(xiàng)的問題，但是本文分析發(fā)現(xiàn)該方法仍然存在如下不足。

1)沒有充分考慮相同評分值占比小的問題。如果2個項(xiàng)目之間的共同評分值個數(shù)占所有評分值個數(shù)的比重很小，那么共同評分值不能夠表示2個項(xiàng)目的評分分布情況，項(xiàng)目相似度的準(zhǔn)確性也必然值得懷疑。例如項(xiàng)目I和J的評分分別為I=(1,0,2,0,4,0,4,0,4,0,4,0,4,0,4,0,4,0,4,0)T和J=(0,1,0,2,0,5,0,5,0,5,0,5,0,5,0,5,0,5,0,5)T。運(yùn)用Bhattacharyya系數(shù)計算項(xiàng)目I和J的相似度BC(I,J)為

根據(jù)項(xiàng)目I和J的評分分布情況可以看出，評分值(1,2)為其相同評分值，但其個數(shù)占所有評分值總數(shù)的比重很小，不能真實(shí)地表示項(xiàng)目I和J的評分值分布情況，所以，這種情況下基于Bhattacharyya系數(shù)的相似度度量方法計算項(xiàng)目I和J的相似度時會有偏差。

2)忽略了相同評分值的絕對數(shù)量差異。2個項(xiàng)目之間相同評分值絕對數(shù)量的顯著差異表明其評分值分布情況也存在顯著差異，這必然會對項(xiàng)目之間的相似度產(chǎn)生影響。例如，項(xiàng)目I和J的評分分別為I=(1,0,2,0,1,0,2,0,1,0,2,0,1,0,2,0,1,0,2,0)T和J=(0,1,0,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0)T。利用Bhattacharyya系數(shù)計算項(xiàng)目I和J的相似度BC(I,J)為

根據(jù)項(xiàng)目I和J的評分可以看出，相同評分值(1,2)在項(xiàng)目I和J中的絕對數(shù)量存在著顯著差異，在計算相似度時會產(chǎn)生相應(yīng)影響，項(xiàng)目I和J不完全相似，這與現(xiàn)實(shí)情況相符。

2 基于IBC相似度度量

為了解決基于Bhattacharyya系數(shù)相似度度量方法存在的不足，本文提出改進(jìn)的相似度度量方法，即IBC相似度度量方法。IBC相似度度量方法的具體改進(jìn)如下。

1)對于相同評分值占比小的問題，引入拉普拉斯校準(zhǔn)法。設(shè)項(xiàng)目屬性item=(R,NR,T),其中，R表示item的評分范圍，NR表示R中每個評分值的個數(shù)，T表示item評分用戶數(shù)。若評分值r?R，則R={R,r}，NR=NR+1,T=T+R。那么，項(xiàng)目之間的相似度可表示為

h=RI∩RJ

(4)

示例1itemI={R=(1,2,4),NR=(1,1,8),T=10}和itemJ={R=(1,2,5),NR=(1,1,8),T=10}。引入Laplace校準(zhǔn)法，則項(xiàng)目I和J的屬性變?yōu)閕temI={R=(1,2,4,5),NR=(2,2,9,1),T=14}和itemJ={R=(1,2,4,5),NR=(2,2,1,9),T=14}。由于項(xiàng)目I和J的相同評分值(1,2)占評分比重很小，而評分值4和5分別在項(xiàng)目I和J中占主要比重，所以在計算項(xiàng)目I和J的相似度時更應(yīng)該考慮評分值4和5的分布情況?；贗BC相似度度量方法，計算項(xiàng)目I和J的相似度IBC1(I,J)為

運(yùn)用基于IBC相似度度量方法計算項(xiàng)目I和J的相似度時，項(xiàng)目中所有的評分值均參與了相似度的計算，能夠更準(zhǔn)確地反映項(xiàng)目之間的相似度。

2)對于相同評分值絕對數(shù)量差異問題，運(yùn)用權(quán)重法進(jìn)行修正，權(quán)重值為

(5)

(5)式中：cih和cjh分別表示項(xiàng)目I和J中評分為h的個數(shù)。如果項(xiàng)目I和J中相同評分值的絕對數(shù)量差異越大，則權(quán)值越小項(xiàng)目之間的相似度越?。环粗?，權(quán)值越大，項(xiàng)目之間的相似度越大。這與現(xiàn)實(shí)情況相符。

利用權(quán)重法計算第2節(jié)的示例二中項(xiàng)目I和J的相似度IBC2(I,J)如下

雖然項(xiàng)目I和J都只含有共有評分值(1,2)，但是相同評分值之間的絕對數(shù)量差異顯著，從現(xiàn)實(shí)情況看，運(yùn)用基于IBC相似度度量方法計算項(xiàng)目I和J之間的相似度更準(zhǔn)確。

綜上所述，基于IBC相似度度量方法計算項(xiàng)目之間的相似度為

(6)

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

基于IBC相似度度量方法不僅充分利用了項(xiàng)目的所有評分信息，而且解決了相同評分值在不同項(xiàng)目中絕對數(shù)量差異顯著的問題。為了驗(yàn)證基于IBC相似度度量方法的有效性，將該方法用于協(xié)同過濾推薦算法(improved Bhattacharyya coefficient in CF，IBCF)中，結(jié)合基于IBC相似度度量方法和改進(jìn)的余弦相似度度量方法得到最終用戶相似度為

(7)

如果項(xiàng)目I和J的相似度高，那么IBC(·)能夠提高用戶U和V的相似度；反之，IBC(·)降低用戶U和用戶V的相似度。其中，

(8)

(8)式中，rU,med和rV,med分別表示用戶U和V所有評分值的中位數(shù)。

在實(shí)驗(yàn)中，本文運(yùn)用現(xiàn)有相似度計算方法實(shí)現(xiàn)不同的基于用戶的協(xié)同過濾算法。傳統(tǒng)相似度計算方法(如CPC，JMSD,MSD(mean-squared difference))和PIP以及BCF(bhattacharyya coefficient in CF)，并以相似度計算方法名代替協(xié)同過濾算法名稱。

3.1 數(shù)據(jù)集

為了驗(yàn)證本文提出的IBC相似度度量方法的效果，實(shí)驗(yàn)選用由美國明尼蘇達(dá)大學(xué)GroupLens研究項(xiàng)目組搜集和整理的MovieLens數(shù)據(jù)集。選用的數(shù)據(jù)集包含6 040個用戶對3 799部電影1 060 000個評分信息，評分值越高，表示偏好程度越高。具體如表2。該實(shí)驗(yàn)選擇其中的80%作為訓(xùn)練集，20%作為測試集。

為驗(yàn)證算法的有效性，本文選用了較高稀疏程度的數(shù)據(jù)子集。數(shù)據(jù)集的稀疏度即為表3中K值，即所有評分所占百分比。

表2 實(shí)驗(yàn)數(shù)據(jù)集

表3 數(shù)據(jù)集稀疏性

3.2 評價標(biāo)準(zhǔn)

推薦系統(tǒng)的研究者構(gòu)建了幾類評估屬性比較推薦系統(tǒng)的質(zhì)量。這些評估屬性大致可以分為2類：預(yù)測準(zhǔn)確性和分類準(zhǔn)確性[13]。

預(yù)測準(zhǔn)確性：統(tǒng)計精度度量方法中的平均絕對誤差(mean absolute error, MAE)被廣泛用于評價協(xié)同過濾推薦系統(tǒng)的推薦質(zhì)量。因此，推薦質(zhì)量評價采用了常見的平均絕對誤差MAE。在測試集上首先運(yùn)用推薦系統(tǒng)預(yù)測出用戶的評分，然后根據(jù)測試集中用戶的實(shí)際評分，計算出2者的偏差，即為MAE的值。

不同于“地平線2020”根據(jù)不同領(lǐng)域的研究主題招標(biāo)，通過專家評審擇優(yōu)立項(xiàng)形成項(xiàng)目，“地平線歐洲”將在計劃下推行任務(wù)/使命導(dǎo)向性的項(xiàng)目執(zhí)行和評估方式，提出了“面向任務(wù)的研究和創(chuàng)新”，通過任務(wù)目標(biāo)統(tǒng)領(lǐng)不同研究領(lǐng)域的研究問題，鼓勵跨學(xué)科、跨領(lǐng)域的聯(lián)合研究和創(chuàng)新實(shí)現(xiàn)既定任務(wù)目標(biāo)?！叭蝿?wù)/使命導(dǎo)向性”的項(xiàng)目設(shè)立、執(zhí)行和評估方式，有利于“地平線歐洲”計劃更有效地針對經(jīng)濟(jì)、社會亟待解決的問題提出有效的科學(xué)、技術(shù)解決方案，也將更加有效地發(fā)揮歐盟研發(fā)框架計劃的影響力。

假設(shè)預(yù)測用戶評分值為{p1,p2,…,pn}，對應(yīng)的實(shí)際評分值為{q1,q2,…,qn}，則MAE的計算公式為

(9)

類似的，均方根誤差RMSE(root mean square error)的計算公式為

(10)

分類準(zhǔn)確性：分類準(zhǔn)確性主要測量推薦系統(tǒng)的質(zhì)量性能。常用的評估分類準(zhǔn)確性的屬性主要有：準(zhǔn)確率和召回率。準(zhǔn)確率和召回率的計算公式分別為

(11)

(12)

(11)—(12)式中：Lr表示推薦給目標(biāo)用戶的項(xiàng)目列表；Lrev表示數(shù)據(jù)集中相關(guān)項(xiàng)目列表。

另外，這2種評估屬性必須有所取舍。例如，增加Lr，Recall增加，Precision就會減少。因此，將2種屬性結(jié)合在一起對推薦系統(tǒng)進(jìn)行評估，此種方法稱作F1值，其計算公式為

(13)

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

本文分析了數(shù)據(jù)集子集的特征，并且認(rèn)為每個用戶均為活躍用戶。圖1和圖2分別表示利用數(shù)據(jù)集子集ML中不同協(xié)同過濾算法所得到的MAE和RMSE，圖中K-nearest表示目標(biāo)用戶最近鄰居個數(shù)。從圖1和圖2中可以看出，本文提出的協(xié)同過濾相似度計算方法與現(xiàn)有的協(xié)同過濾相似度計算方法相比，誤差減少，現(xiàn)有的協(xié)同過濾相似度計算方法在計算活躍用戶的近鄰時只考慮共同評分項(xiàng)目的評分，不能完全利用評分信息。因此，基于現(xiàn)有相似度計算方法的協(xié)同過濾算法在預(yù)測時出現(xiàn)較大誤差。雖然BCF算法很大程度上顯著減少了預(yù)測誤差，但是其在計算相似度方面仍可改進(jìn)。

圖1 MAE隨K-nearest的變化趨勢Fig.1 MAE vs K-nearest numbers

圖2 RMSE隨K-nearest的變化趨勢Fig.2 RMSE vs K-nearest numbers

不同協(xié)同過濾算法的F1值如圖3所示。從圖3中可以看出，IBCF推薦算法的性能比其他現(xiàn)有協(xié)同過濾算法更穩(wěn)定。IBCF算法的F1值在K=300處約為0.7，BCF算法的F1值約為0.64，PIP相似度計算方法的F1值與MSD方法接近。傳統(tǒng)的相似度計算方法(CPC)性能最差，F(xiàn)1值均不高于0.5。由此可以看出，IBC相似度計算方法更能準(zhǔn)確地計算相關(guān)項(xiàng)目的相似度。

圖3 F1值隨K-nearest的變化趨勢Fig.3 F1 vs K-nearest numbers

3.4 時間復(fù)雜度分析

表4 IBCF與BCF時間復(fù)雜度比較

從表4可以看出，本文提出的相似度度量方法沒有增加BCF算法的時間復(fù)雜度。

4 結(jié) 論

由于現(xiàn)有的基于近鄰的協(xié)同過濾相似度計算方法在尋找活躍用戶的近鄰時不能充分利用稀疏數(shù)據(jù)的評分信息，所以不能夠進(jìn)行可靠有效的推薦。本文提出的基于IBC相似度度量方法引入Laplace校準(zhǔn)法和權(quán)重法，充分利用所有評分信息，改進(jìn)了基于BC相似度計算方法的不足，提高了推薦的可靠性。此方法充分利用了項(xiàng)目的所有評分信息以及解決了相同評分值在不同項(xiàng)目中絕對數(shù)量差別顯著的問題。通過MovieLens數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)可知，基于IBC相似度度量方法在高稀疏性數(shù)據(jù)集中能夠提高相似度的計算準(zhǔn)確性。