武文琪 王建芳 張朋飛 劉永利
(河南理工大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院 河南 焦作 454000)
?
一種巴氏系數(shù)改進(jìn)相似度的協(xié)同過濾算法
武文琪 王建芳 張朋飛 劉永利
(河南理工大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院 河南 焦作 454000)
針對傳統(tǒng)協(xié)同過濾算法中評分?jǐn)?shù)據(jù)稀疏性及所造成推薦質(zhì)量不高的問題,提出一種巴氏系數(shù)(Bhattacharyya Coefficient)改進(jìn)相似度的協(xié)同過濾算法。在基于近鄰協(xié)同過濾算法基礎(chǔ)上,首先利用Jaccard相似性來計算用戶間的全局相似性;其次使用巴氏系數(shù)獲得評分分布的整體規(guī)律,并結(jié)合Pearson相關(guān)系數(shù)來計算其局部相似性;最后融合全局相似性和局部相似性得到最終的相似度矩陣。實驗結(jié)果表明,該算法在稀疏數(shù)據(jù)集上獲得更好的推薦結(jié)果,有效地緩解了評分?jǐn)?shù)據(jù)稀疏性問題,提高了推薦的準(zhǔn)確度。
協(xié)同過濾 數(shù)據(jù)稀疏性 巴氏系數(shù) 相似度計算
推薦系統(tǒng)幫助人們成功解決信息過載問題[1],并且在過去的幾十年建立了電子商務(wù)的重要組成部分。推薦系統(tǒng)的首要任務(wù)是通過對大型項目空間的濾波為用戶提供項目或產(chǎn)品的個性化推薦。推薦算法在電子商務(wù)、數(shù)字圖書館、電子媒體和在線廣告等各種應(yīng)用中發(fā)展,其中協(xié)同過濾算法在推薦系統(tǒng)中得到了廣泛的應(yīng)用[2]。
基于近鄰的協(xié)同過濾作為協(xié)同過濾中重要的一類,其簡單、直觀、有效的特點被廣泛應(yīng)用于電影、音樂、圖書等領(lǐng)域。其基本思想是采用一種相似性度量方法尋找最近鄰居集合;然后通過對最近鄰居集合的評分進(jìn)行加權(quán)平均求和,從而產(chǎn)生推薦集[3]。相似性計算的準(zhǔn)確性直接影響推薦質(zhì)量,用戶之間的相似性是基于兩個用戶對相同項目的評分(共同評分),同樣,項目之間的相似性是在對項目具有共同評分的用戶基礎(chǔ)上進(jìn)行計算。但是,當(dāng)數(shù)據(jù)極大稀疏無法保證足夠的共同評分?jǐn)?shù)據(jù),傳統(tǒng)的相似性計算方法其推薦效果不佳。即使沒有一個共同用戶,兩個項目也可以是相似的;用戶評價的項目不同,兩個用戶也可以是相似的,這些情況是傳統(tǒng)的相似性方法沒有考慮到的。因此,傳統(tǒng)的相似性計算方法并不適合于稀疏數(shù)據(jù)(共同用戶很少或者共同評價項目很少甚至沒有)。
文獻(xiàn)[4]在推薦系統(tǒng)中引入了用戶相似度的概念,改善了社交網(wǎng)絡(luò)中用戶好友推薦的問題。文獻(xiàn)[5]中提出了基于用戶模糊相似度的協(xié)同過濾算法,分別建立年齡和評分的梯形模糊模型,將用戶年齡和評分模糊化,進(jìn)行相似度計算。文獻(xiàn)[6]基于搜索引擎日志,提出了一種基于流行性和相似性相結(jié)合的查詢推薦策略,為目標(biāo)用戶產(chǎn)生推薦詞集合,改善推薦的多樣性和流行性。文獻(xiàn)[7]提出了一種結(jié)合Jaccard相似度和皮爾遜(Pearson)相關(guān)系數(shù)的改進(jìn)相似性度量方法,在計算相似度時不但考慮共同評分還考慮共同評分的絕對數(shù)量,提供精確的評分預(yù)測。Bobadilla等提出了基于MSD(均方誤差)的相似度度量方法;并在此基礎(chǔ)上將評分?jǐn)?shù)據(jù)結(jié)合上下文信息,提出Jaccard與MSD相結(jié)合的相似度來提高皮爾遜相關(guān)性的結(jié)果[8]。上述改進(jìn)相似度計算方法在計算相似度時只考慮了相似性的全局信息,沒有考慮其局部相似性;適用于數(shù)據(jù)集相對集中(存在共同評分),沒有共同評分時其推薦結(jié)果不佳,實際中用戶評價的項目只是項目空間中的九牛一毛,其共同評分更少甚至沒有。
針對上述問題,在基于近鄰協(xié)同過濾算法的基礎(chǔ)上,本文提出了一種利用巴氏系數(shù)改進(jìn)相似度的協(xié)同過濾算法(BCCF),通過改進(jìn)相似度計算方法緩解數(shù)據(jù)稀疏性問題,以及數(shù)據(jù)稀疏導(dǎo)致無法計算相似度的問題。改進(jìn)相似度計算重視用戶的每一個評分,在計算用戶之間相似性時,不僅考慮到用戶評分之間的相似性,還結(jié)合Jaccard和Pearson方法的優(yōu)點,利用巴氏系數(shù)來發(fā)現(xiàn)用戶評分的分布規(guī)律。在Movielens數(shù)據(jù)集上的實驗表明,BCCF算法在相對稀疏的數(shù)據(jù)集上的表現(xiàn)更好,有效改善評分?jǐn)?shù)據(jù)稀疏性問題,提高預(yù)測評分的準(zhǔn)確性。
協(xié)同過濾算法的關(guān)鍵在于最近鄰居集合的選擇,推薦系統(tǒng)的性能直接依賴于目標(biāo)用戶(項目)鄰居的選擇,也就是依賴于用戶(項目)之間相似度的度量,因而改進(jìn)相似性計算方法成為提高推薦系統(tǒng)性能的有效途徑之一[9]。協(xié)同過濾中常用的相似性度量方法:余弦相似性、調(diào)整余弦相似性、Pearson相關(guān)系數(shù)和Jaccard相似性等[10],以基于用戶的協(xié)同過濾算法為例。
(1) 余弦相似度
將用戶的評分看作為一個向量,計算兩個用戶評分向量的夾角余弦值來衡量兩個用戶之間的相似度。
(1)
式(1)中Iu,v表示用戶u和v的共同評分項目集,ru,i和rv,i分別表示用戶u和用戶v對項目i的評分。
如ru= (1,1),rv= (5,5),simcos(u,v)=1,盡管兩個用戶的評分差距很大(一個非常滿意,一個非常不滿意),但兩個用戶的余弦相似度卻為1。余弦相似性過于關(guān)注向量之間的夾角而忽視向量的長度(共同評分項數(shù)量),且過于依賴兩個用戶的共同評分,這種方式對評分?jǐn)?shù)值不敏感。
(2)
(3) Pearson相關(guān)系數(shù)
(3)
Pearson相關(guān)系數(shù)用來度量兩個評分?jǐn)?shù)據(jù)集合之間的線性關(guān)系,但對數(shù)值之間的差距不敏感。令ru=(1,1,3,3,2),rv=(3,3,5,5,4)。simpear(u,v)=1。兩組數(shù)據(jù)的差異明顯,用戶u對項目的評分都較低,而用戶v對項目的評分都較高,很難看出兩者之間有相關(guān)性,其計算結(jié)果與理論分析完全相反。Pearson相關(guān)系數(shù)考慮到用戶評分的偏差,卻忽略了評分的全局信息和用戶共同評分的項目數(shù),所以線性相關(guān)系數(shù)并不能很好地度量相似性。
(4) Jaccard相似度
(4)
其中Iu表示用戶u評分的項目,Iv表示用戶v評分的項目。Jaccard相似度與Pearson相關(guān)系數(shù)不同,Jaccard相似度僅考慮了兩個用戶的共同評分?jǐn)?shù),但未考慮絕對評分,從而影響用戶相似度的準(zhǔn)確性。
針對上述相似性計算方法中存在的缺陷,本文在基于近鄰協(xié)同過濾算法的基礎(chǔ)上,提出了一種利用巴氏距離改進(jìn)相似性度量方法,充分利用用戶的每一個評分,即使沒有一個共同項目評分時,也可以計算兩個用戶之間的相似度。Jaccard相似度通過計算兩個用戶共同評分項目數(shù)的比重,能夠在全局上衡量兩個用戶的相似度,以此作為全局相似度,Pearson相關(guān)系數(shù)考慮到用戶評分偏差,并結(jié)合巴氏系數(shù)得到的評分整體規(guī)律,以此可以作為局部相似性,將全局和局部相似性進(jìn)行融合作為兩個用戶之間最終的相似度值。
2.1 巴氏系數(shù)
巴氏系數(shù)是對兩個評分?jǐn)?shù)據(jù)向量的重疊近似計算,可用來對兩個用戶之間評分的相關(guān)性進(jìn)行測量。已廣泛應(yīng)用于信號處理、模式識別研究領(lǐng)域。
在連續(xù)域兩個密度分布p1(x)和p2(x)之間的相似度用巴氏系數(shù)(BC)定義為:
(5)
在離散域上BC定義為:
(6)
其中p1(x)和p2(x)密度是已知的評分?jǐn)?shù)據(jù),用戶u和v的評分別用Puh和Pvh來評估其離散密度,計算用戶u和v之間的BC相似度為:
(7)
例如:評分在1~5之間,用戶u和v的評分向量:ru= (1,0,2,0,1,0,2,0,3,0)T,rv=(0,1,0,2,0,1,0,2,0,3)T,所以用戶u和v之間的BC系數(shù)為:
0+0=1
(8)
2.2 巴氏系數(shù)相似度
基于巴氏系數(shù)提出一種新的相似性度量方法——巴氏系數(shù)相似度,利用用戶的所有評分來計算兩個用戶之間的相似度。Jaccard相似性計算的是共同評分項目數(shù)所占的比重,利用式(4)描述兩個用戶評分之間的全局相似性;由于Pearson相似性不能區(qū)分?jǐn)?shù)值的差距,而巴氏系數(shù)是對相同評分?jǐn)?shù)值重疊的近似計算,可以用來計算評分分布規(guī)律相似度,將兩者相乘不僅可以發(fā)現(xiàn)評分分布規(guī)律還能區(qū)別評分?jǐn)?shù)值上的差距,互相彌補(bǔ)其缺陷。令用戶u和v評價的兩個項目分別為Iu和Iv,用戶u和v評價的兩項目之間的局部相似性定義如下。
(9)
設(shè)兩個用戶的評分向量為:ru=(1,1,3,3,2),rv=(3,3,5,5,4)。其simpear(u,v)=1,simloc(u,v)=0.16,其實這兩個用戶評分整體偏差較大,相似度較低,其局部相似性設(shè)計更為合理。
當(dāng)兩個用戶之間的共同評分?jǐn)?shù)為0即Iu∩Iv=?,巴氏系數(shù)相似度也可以計算用戶u和v之間的相似度,其相似度等于局部相似度,且數(shù)值往往很小,遠(yuǎn)遠(yuǎn)小于1,即sim(u,v)=simloc(u,v)<<1。當(dāng)兩個用戶之間存在共同評分?jǐn)?shù)時其整體相似度被分割成全局和局部相似性兩部分,且sim(u,v)>simJac(u,v)>simloc(u,v)。如果兩個用戶在全局角度上是相似的,則BC(u,v)提高用戶u和v的評分之間的局部相似性,另一方面,如果用戶u和v完全不相似,則BC(u,v)降低兩個用戶評分之間的局部相似度的重要性。局部相似性提供非常重要的用戶局部信息,局部相似性也必須提供用戶評分之間的正和負(fù)關(guān)系。
融合局部相似度和全局相似度得到最終的相似度值。當(dāng)BC(u,v)=1時局部相似度的作用最大,為相同項目提供最大的局部相似性;當(dāng)BC(u,v)=0時局部相似度為0,此時全局相似度就是最終的相似度值。
(10)
本文提出的巴氏系數(shù)相似度特點在于整合利用巴氏系數(shù)、Jaccard和Pearson相關(guān)系數(shù)互相彌補(bǔ)其缺陷,完美詮釋兩個用戶之間的相似性。考慮了用戶評分的全局信息和局部信息,不再僅依靠用戶對共同項目的評分,即使沒有也可以計算兩個用戶(項目)之間的相似性,不受數(shù)據(jù)稀疏性的影響。計算相似性時利用用戶對項目的所有評分,多方面的考慮可能影響用戶之間相似度的因素,考慮用戶評分的全局相似性和局部相似性。
2.3 BCCF算法
在基于近鄰協(xié)同過濾算法的基礎(chǔ)上,利用巴氏系數(shù)改進(jìn)相似度計算,BCCF的算法流程。
算法:BCCF算法
輸入:用戶——項目的評分矩陣Rm×n,最近鄰居數(shù)目k。
輸出:目標(biāo)用戶u對未知項目的預(yù)測評分集。
算法步驟:
步驟1由數(shù)據(jù)集得到評分矩陣Rm×n。
步驟2用式(4)計算用戶u和用戶v的全局相似度(當(dāng)u=v時令simJac(u,v)=0)。
步驟3利用式(7)來得到用戶u和用戶v分別評價項目的評分分布規(guī)律(當(dāng)u=v時令BC(u,v)=0)。
步驟4利用步驟3的計算結(jié)果,并通過式(9)計算用戶u和用戶v的局部相似度(當(dāng)u=v時令simloc(u,v)=0)。
步驟5根據(jù)步驟3和步驟4得到的全局相似度和局部相似度利用式(10)進(jìn)行融合,形成最終的相似度。
步驟6利用步驟5計算任意兩兩用戶之間的相似度,最終形成相似度矩陣,然后將目標(biāo)用戶u與其他用戶v之間的最終相似度遞減排序{sim(u,v1)>sim(u,v2)>…>sim(u,vm)},選擇相似度排序中前k個用戶作為目標(biāo)用戶u的最近鄰居,k個最近鄰居用戶構(gòu)成目標(biāo)用戶u的最近鄰居集合Iu={v1,v2,…,vk}。
步驟7已知評分矩陣R和最近鄰居集合Iu={v1,v2,…,vk},由k個最近鄰居用戶對未知項目i的評分,通過加權(quán)平均求和得到目標(biāo)用戶u對該項目的預(yù)測評分Pu,i,公式如下:
(11)
算法結(jié)束。
3.1 實驗數(shù)據(jù)集
為了檢驗提出方法的有效性,在Movielens_100K和Movielens_1M數(shù)據(jù)集上分別進(jìn)行驗證,數(shù)據(jù)集的具體參數(shù)如表1所示。
表1 實驗數(shù)據(jù)集的具體參數(shù)
本文實驗環(huán)境為:Windows 7操作系統(tǒng),內(nèi)存為4G,Intel(R)Core(TM)i3-4150 CPU3.5 GHz開發(fā)工具使用Matlab2013b。
3.2 評價標(biāo)準(zhǔn)
為了反映實際情況的預(yù)測誤差,本文采用平均絕對誤差MAE和均方根誤差RMSE從不同側(cè)重點來衡量算法的準(zhǔn)確性。設(shè)在訓(xùn)練集上得到用戶的預(yù)測評分集合為p={pu,1,pu,2,…,pu,n},用戶實際評分集合為r={ru,1,ru,2,…,ru,n},通過計算兩集合評分的平均差值或絕對平均差值來衡量推薦的精確率。則平均絕對誤差MAE定義為:
(12)
RMSE同樣用來衡量推薦的精確率,RMSE更側(cè)重于預(yù)測評分與實際評分差值的絕對值,相對MAE加大了懲罰力度,RMSE值越小,則MAE值越小,預(yù)測評分與實際評分越接近,推薦精確度越高。均方根誤差RMSE定義為:
(13)
3.3 實驗結(jié)果與分析
本實驗在Movielens不同大小的數(shù)據(jù)集上分別進(jìn)行驗證,將Movielens數(shù)據(jù)集按一定比例(本實驗采用8∶2比例)隨機(jī)分為訓(xùn)練集和測試集,同時進(jìn)行10次交叉實驗求得平均值作為最終結(jié)果。
(1) 在Movielens_100K數(shù)據(jù)集上傳統(tǒng)相似度比較
當(dāng)鄰居數(shù)目k從5~30變化時,比較Pearson相關(guān)系數(shù)、Jaccard相似度的MAE值。Jaccard在全局上計算共同評分所占比重,由巴氏系數(shù)取得評分分布并結(jié)合Pearson相關(guān)系數(shù)在局部上得到評分之間的相似性,由全部和局部相似性得到巴氏系數(shù)相似性;從圖1中可以看出:隨著用戶鄰居數(shù)目k的增大,本文提出的BCCF算法其MAE值總體趨于減少,當(dāng)鄰居數(shù)達(dá)到30時MAE值基本穩(wěn)定;相對于傳統(tǒng)的Jaccard和Pearson相關(guān)系數(shù)計算方法,BCCF算法的MAE值最低且相對穩(wěn)定。
圖1 巴氏系數(shù)相似度與傳統(tǒng)相似度的MAE比較
(2) Movielens_100K數(shù)據(jù)集上不同算法之間對比
實驗中最近鄰居數(shù)k分別取5、10、15、20、25和30,根據(jù)實驗(1)中選取巴氏系數(shù)相似性作為算法的相似度計算方法,本文提出的BCCF算法分別與文獻(xiàn)[7]中提出的改進(jìn)相似度算法(JPCC)、文獻(xiàn)[8]中提出的改進(jìn)算法 (JMSD) 在Movielens_100K數(shù)據(jù)集上進(jìn)行 MAE和RMSE值對比。
由圖2和圖3可以看出,在Movielens_100K數(shù)據(jù)集上改進(jìn)算法BCCF與傳統(tǒng)的JPCC算法相比MAE在趨于穩(wěn)定狀態(tài)下降低了6%、RMSE降低了2%;比JMSD算法相比MAE在趨于穩(wěn)定狀態(tài)下降低了10%、RMSE降低了5%。在Movielens_100K數(shù)據(jù)集上BCCF算法的精確性比上述所參照的經(jīng)典論文算法的精確度有所提高,從一個側(cè)面說明了在該數(shù)據(jù)集中實際存在著用戶對項目的共同評分很少的情況下進(jìn)行優(yōu)化的方案,即采用巴氏系數(shù)進(jìn)行用戶間所有的評分能夠進(jìn)一步提高算法的精度。
圖2 Movielens_100K數(shù)據(jù)集上三種算法的MAE對比
圖3 Movielens_100K數(shù)據(jù)集上三種算法的RMSE對比
(3) 在Movielens_1M數(shù)據(jù)集上不同算法之間對比
本節(jié)實驗中最近鄰居數(shù)k為 5~30,根據(jù)實驗(1)中選取巴氏系數(shù)改進(jìn)相似性作為算法的相似度計算方法,在Movielens_1M數(shù)據(jù)集上,本文提出的BCCF算法分別與JPCC算法、JMSD算法進(jìn)行 MAE和RMSE值對比。其效果分別如圖4、圖5所示。
圖4 Movielens_1M數(shù)據(jù)集上三種算法的MAE對比
圖5 Movielens_1M數(shù)據(jù)集上三種算法的RMSE對比
由圖4和圖5可以看出,在Movielens_1M數(shù)據(jù)集上改進(jìn)算法BCCF與傳統(tǒng)的JPCC算法相比在趨于穩(wěn)定狀態(tài)下MAE降低了20%、RMSE降低了17%,比JMSD算法相比在趨于穩(wěn)定狀態(tài)下MAE降低了10%、RMSE降低了4%。RMSE和MAE值越小則表示推薦質(zhì)量越好,且在Movielens_1M數(shù)據(jù)集上BCCF算法的RMSE和MAE值比在Movielens_100K數(shù)據(jù)集上實驗結(jié)果更小,說明數(shù)據(jù)集越稀疏其BCCF算法的MAE和RMSE性能越好,說明本文提出的一種巴氏系數(shù)改進(jìn)相似度的協(xié)同過濾算法能有效緩解評分?jǐn)?shù)據(jù)稀疏性問題及其帶來的推薦精度問題。
本文提出了一種基于巴氏系數(shù)的改進(jìn)相似度計算方法,考慮了用戶評分的全局和局部相似性,能更全面分析用戶之間的相似性,并在此基礎(chǔ)上設(shè)計了BCCF算法。通過與傳統(tǒng)協(xié)同過濾算法比較,實驗結(jié)果表明:BCCF算法不再僅依賴于共同評分,解決了推薦系統(tǒng)中數(shù)據(jù)極大稀疏時無法計算相似度,以及由數(shù)據(jù)稀疏性帶來的推薦精度問題;現(xiàn)實情況中用戶對項目的共同評分很少甚至沒有,故BCCF有很強(qiáng)的實用性,BCCF更適用于評分矩陣稀疏的數(shù)據(jù)集;BCCF合理利用用戶的每一個評分,根據(jù)用戶的評分來發(fā)現(xiàn)其內(nèi)在的相關(guān)性??紤]用戶的所有評分,造成計算相似度時其時間復(fù)雜度增加,對巴氏系數(shù)相似度計算進(jìn)行優(yōu)化,找到能降低其時間復(fù)雜度方法,進(jìn)一步提高算法性能。
[1] Bobadilla J,Ortega F,Hernando A,et al.Recommender systems survey[J].Knowledge-Based Systems,2013,46(1):109-132.
[2] Lien D T,Phuong N D.Collaborative filtering with a graph-based similarity measure[C]//Computing,Management and Telecommunications (ComManTel),2014 International Conference on.IEEE,Da Nang,2014:251-256.
[3] Han X,Wang L,Farahbakhsh R,et al.CSD:A multi-user similarity metric for community recommendation in online social network[J].Expert Systems with Applications,2016,53:14-26.
[4] 榮輝桂,火生旭,胡春華.基于用戶相似度的協(xié)同過濾推薦算法[J].通信學(xué)報,2014,35(2):16-24.
[5] 吳毅濤,張興明,王興茂.基于用戶模糊相似度的協(xié)同過濾算法[J].通信學(xué)報,2016,37(1):198-206.
[6] 孫達(dá)明,張斌,張書波,等.一種流行性與相似性結(jié)合查詢推薦策略[J].小型微型計算機(jī)系統(tǒng),2016,37(6):1121-1125.
[7] 鄭翠翠,李林.協(xié)同過濾算法中的相似性度量方法研[J].計算機(jī)工程與應(yīng)用,2014,50(8):147-149.
[8] Bobadilla J,Ortega F,Hernando A,et al.A similarity metric designed to speed up,using hardware,the recommender systems k-nearest neighbors algorithm[J].Knowledge-Based Systems,2013,51(1):27-34.
[9] Pirasteh P,Hwang D,Jung J E.Weighted similarity schemes for high scalability in user-based collaborative filtering[J].Mobile Networks & Applications,2015,20(4):497-507.
[10] Sun H F,Chen J L,Yu G,et al.JacUOD:A new similarity measurement for collaborative filtering[J].Journal of Computer Science & Technology,2012,27(6):1252-1260.
COLLABORATIVEFILTERINGALGORITHMBASEDONIMPROVEDSIMILARITYMEASUREWITHBHATTACHARYYACOEFFICIENT
Wu Wenqi Wang Jianfang Zhang Pengfei Liu Yongli
(SchoolofComputerScienceandTechnology,HenanPolytechnicUniversity,Jiaozuo454000,Henan,China)
Aiming at the problem of low-quality recommendation and data sparsity, we proposed a collaborative filtering algorithm based on improved similarity measure with Bhattacharyya coefficient. First, we use Jaccard similarity to calculate the global similarity between users based on neighbor cooperative filtering algorithm. Secondly, we use the Bhattacharyya coefficient to obtain the whole law of the grade distribution. And we combine the Pearson correlation coefficient to calculate the local similarity. Finally, we fuse the global similarity and local similarity to obtain final similarity metric. The experimental results show that algorithm can get better recommendation results on sparse data sets. It effectively mitigates the sparseness of scoring data and improves the recommended accuracy.
Collaborative filtering Data sparsity Bhattacharyya coefficient Similarity measure
2016-08-31。國家自然科學(xué)基金項目(61202286);河南省高等學(xué)校青年骨干教師資助計劃項目(2015GGJS-068)。武文琪,碩士生,主研領(lǐng)域:數(shù)據(jù)挖掘,推薦算法。王建芳,副教授。張朋飛,碩士生。劉永利,副教授。
TP391
A
10.3969/j.issn.1000-386x.2017.08.047