基于Bhattacharyya系數(shù)的改進(jìn)相似度度量方法

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

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

0 引 言

隨著“信息過(guò)載”問(wèn)題的日益突出，個(gè)性化推薦服務(wù)研究備受青睞。其中，協(xié)同過(guò)濾技術(shù)得到了廣泛的研究和應(yīng)用，在基于近鄰的協(xié)同過(guò)濾推薦算法中，相似度的計(jì)算至關(guān)重要[1-4]。G. Salton等[5]提出了運(yùn)用余弦方法計(jì)算信息相似度而檢索信息；B. Sarwar等[6]改進(jìn)了余弦相似度方法計(jì)算項(xiàng)目相似度，優(yōu)化了相似度的計(jì)算方法；U. Shardanand等[7]用評(píng)分值中位數(shù)替代評(píng)分值均值提高了皮爾遜系數(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)算法，雖然解決了過(guò)度依賴(lài)共同評(píng)分項(xiàng)的問(wèn)題，但仍然存在評(píng)分值利用率低的問(wèn)題；Ahn等[9]提出了PIP(proximity impact popularity)相似度度量模型，考慮用于評(píng)分的接近、影響和普及3個(gè)方面計(jì)算用戶(hù)相似性，但沒(méi)有考慮用戶(hù)全局偏好。相似度方法及計(jì)算公式如表1所示。

表1 常用相似度計(jì)算方法

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

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

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

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

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

(1)

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

(2)

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

(3)

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

1)沒(méi)有充分考慮相同評(píng)分值占比小的問(wèn)題。如果2個(gè)項(xiàng)目之間的共同評(píng)分值個(gè)數(shù)占所有評(píng)分值個(gè)數(shù)的比重很小，那么共同評(píng)分值不能夠表示2個(gè)項(xiàng)目的評(píng)分分布情況，項(xiàng)目相似度的準(zhǔn)確性也必然值得懷疑。例如項(xiàng)目I和J的評(píng)分分別為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ù)計(jì)算項(xiàng)目I和J的相似度BC(I,J)為

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

2)忽略了相同評(píng)分值的絕對(duì)數(shù)量差異。2個(gè)項(xiàng)目之間相同評(píng)分值絕對(duì)數(shù)量的顯著差異表明其評(píng)分值分布情況也存在顯著差異，這必然會(huì)對(duì)項(xiàng)目之間的相似度產(chǎn)生影響。例如，項(xiàng)目I和J的評(píng)分分別為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ù)計(jì)算項(xiàng)目I和J的相似度BC(I,J)為

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

2 基于IBC相似度度量

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

1)對(duì)于相同評(píng)分值占比小的問(wèn)題，引入拉普拉斯校準(zhǔn)法。設(shè)項(xiàng)目屬性item=(R,NR,T),其中，R表示item的評(píng)分范圍，NR表示R中每個(gè)評(píng)分值的個(gè)數(shù)，T表示item評(píng)分用戶(hù)數(shù)。若評(píng)分值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的相同評(píng)分值(1,2)占評(píng)分比重很小，而評(píng)分值4和5分別在項(xiàng)目I和J中占主要比重，所以在計(jì)算項(xiàng)目I和J的相似度時(shí)更應(yīng)該考慮評(píng)分值4和5的分布情況?；贗BC相似度度量方法，計(jì)算項(xiàng)目I和J的相似度IBC1(I,J)為

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

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

(5)

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

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

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

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

(6)

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

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

(7)

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

(8)

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

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

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

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

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

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

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

3.2 評(píng)價(jià)標(biāo)準(zhǔn)

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

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

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

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

(9)

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

(10)

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

(11)

(12)

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

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

(13)

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

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

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

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

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

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

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

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

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

4 結(jié) 論

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