一種巴氏系數改進相似度的協同過濾算法

武文琪 王建芳 張朋飛 劉永利

(河南理工大學計算機科學與技術學院 河南 焦作 454000)

?

一種巴氏系數改進相似度的協同過濾算法

武文琪 王建芳 張朋飛 劉永利

(河南理工大學計算機科學與技術學院 河南 焦作 454000)

針對傳統協同過濾算法中評分數據稀疏性及所造成推薦質量不高的問題，提出一種巴氏系數(Bhattacharyya Coefficient)改進相似度的協同過濾算法。在基于近鄰協同過濾算法基礎上，首先利用Jaccard相似性來計算用戶間的全局相似性；其次使用巴氏系數獲得評分分布的整體規律，并結合Pearson相關系數來計算其局部相似性；最后融合全局相似性和局部相似性得到最終的相似度矩陣。實驗結果表明，該算法在稀疏數據集上獲得更好的推薦結果，有效地緩解了評分數據稀疏性問題，提高了推薦的準確度。

協同過濾 數據稀疏性 巴氏系數 相似度計算

0 引 言

推薦系統幫助人們成功解決信息過載問題[1]，并且在過去的幾十年建立了電子商務的重要組成部分。推薦系統的首要任務是通過對大型項目空間的濾波為用戶提供項目或產品的個性化推薦。推薦算法在電子商務、數字圖書館、電子媒體和在線廣告等各種應用中發展，其中協同過濾算法在推薦系統中得到了廣泛的應用[2]。

基于近鄰的協同過濾作為協同過濾中重要的一類，其簡單、直觀、有效的特點被廣泛應用于電影、音樂、圖書等領域。其基本思想是采用一種相似性度量方法尋找最近鄰居集合；然后通過對最近鄰居集合的評分進行加權平均求和，從而產生推薦集[3]。相似性計算的準確性直接影響推薦質量，用戶之間的相似性是基于兩個用戶對相同項目的評分(共同評分)，同樣，項目之間的相似性是在對項目具有共同評分的用戶基礎上進行計算。但是，當數據極大稀疏無法保證足夠的共同評分數據，傳統的相似性計算方法其推薦效果不佳。即使沒有一個共同用戶，兩個項目也可以是相似的；用戶評價的項目不同，兩個用戶也可以是相似的，這些情況是傳統的相似性方法沒有考慮到的。因此，傳統的相似性計算方法并不適合于稀疏數據(共同用戶很少或者共同評價項目很少甚至沒有)。

文獻[4]在推薦系統中引入了用戶相似度的概念，改善了社交網絡中用戶好友推薦的問題。文獻[5]中提出了基于用戶模糊相似度的協同過濾算法，分別建立年齡和評分的梯形模糊模型，將用戶年齡和評分模糊化，進行相似度計算。文獻[6]基于搜索引擎日志，提出了一種基于流行性和相似性相結合的查詢推薦策略，為目標用戶產生推薦詞集合，改善推薦的多樣性和流行性。文獻[7]提出了一種結合Jaccard相似度和皮爾遜(Pearson)相關系數的改進相似性度量方法，在計算相似度時不但考慮共同評分還考慮共同評分的絕對數量，提供精確的評分預測。Bobadilla等提出了基于MSD(均方誤差)的相似度度量方法；并在此基礎上將評分數據結合上下文信息，提出Jaccard與MSD相結合的相似度來提高皮爾遜相關性的結果[8]。上述改進相似度計算方法在計算相似度時只考慮了相似性的全局信息，沒有考慮其局部相似性；適用于數據集相對集中(存在共同評分)，沒有共同評分時其推薦結果不佳，實際中用戶評價的項目只是項目空間中的九牛一毛，其共同評分更少甚至沒有。

針對上述問題，在基于近鄰協同過濾算法的基礎上，本文提出了一種利用巴氏系數改進相似度的協同過濾算法(BCCF)，通過改進相似度計算方法緩解數據稀疏性問題，以及數據稀疏導致無法計算相似度的問題。改進相似度計算重視用戶的每一個評分，在計算用戶之間相似性時，不僅考慮到用戶評分之間的相似性，還結合Jaccard和Pearson方法的優點，利用巴氏系數來發現用戶評分的分布規律。在Movielens數據集上的實驗表明，BCCF算法在相對稀疏的數據集上的表現更好，有效改善評分數據稀疏性問題，提高預測評分的準確性。

1 相關工作

協同過濾算法的關鍵在于最近鄰居集合的選擇，推薦系統的性能直接依賴于目標用戶(項目)鄰居的選擇，也就是依賴于用戶(項目)之間相似度的度量，因而改進相似性計算方法成為提高推薦系統性能的有效途徑之一[9]。協同過濾中常用的相似性度量方法：余弦相似性、調整余弦相似性、Pearson相關系數和Jaccard相似性等[10]，以基于用戶的協同過濾算法為例。

(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。余弦相似性過于關注向量之間的夾角而忽視向量的長度(共同評分項數量)，且過于依賴兩個用戶的共同評分，這種方式對評分數值不敏感。

(2)

(3) Pearson相關系數

(3)

Pearson相關系數用來度量兩個評分數據集合之間的線性關系，但對數值之間的差距不敏感。令ru=(1,1,3,3,2)，rv=(3,3,5,5,4)。simpear(u,v)=1。兩組數據的差異明顯，用戶u對項目的評分都較低，而用戶v對項目的評分都較高，很難看出兩者之間有相關性，其計算結果與理論分析完全相反。Pearson相關系數考慮到用戶評分的偏差，卻忽略了評分的全局信息和用戶共同評分的項目數，所以線性相關系數并不能很好地度量相似性。

(4) Jaccard相似度

(4)

其中Iu表示用戶u評分的項目，Iv表示用戶v評分的項目。Jaccard相似度與Pearson相關系數不同，Jaccard相似度僅考慮了兩個用戶的共同評分數，但未考慮絕對評分，從而影響用戶相似度的準確性。

針對上述相似性計算方法中存在的缺陷，本文在基于近鄰協同過濾算法的基礎上，提出了一種利用巴氏距離改進相似性度量方法，充分利用用戶的每一個評分，即使沒有一個共同項目評分時，也可以計算兩個用戶之間的相似度。Jaccard相似度通過計算兩個用戶共同評分項目數的比重，能夠在全局上衡量兩個用戶的相似度，以此作為全局相似度，Pearson相關系數考慮到用戶評分偏差，并結合巴氏系數得到的評分整體規律，以此可以作為局部相似性，將全局和局部相似性進行融合作為兩個用戶之間最終的相似度值。

2 一種巴氏系數改進相似度的協同過濾算法

2.1 巴氏系數

巴氏系數是對兩個評分數據向量的重疊近似計算，可用來對兩個用戶之間評分的相關性進行測量。已廣泛應用于信號處理、模式識別研究領域。

在連續域兩個密度分布p1(x)和p2(x)之間的相似度用巴氏系數(BC)定義為：

(5)

在離散域上BC定義為：

(6)

其中p1(x)和p2(x)密度是已知的評分數據，用戶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系數為：

0+0=1

(8)

2.2 巴氏系數相似度

基于巴氏系數提出一種新的相似性度量方法——巴氏系數相似度，利用用戶的所有評分來計算兩個用戶之間的相似度。Jaccard相似性計算的是共同評分項目數所占的比重，利用式(4)描述兩個用戶評分之間的全局相似性；由于Pearson相似性不能區分數值的差距，而巴氏系數是對相同評分數值重疊的近似計算，可以用來計算評分分布規律相似度，將兩者相乘不僅可以發現評分分布規律還能區別評分數值上的差距，互相彌補其缺陷。令用戶u和v評價的兩個項目分別為Iu和Iv，用戶u和v評價的兩項目之間的局部相似性定義如下。

(9)

設兩個用戶的評分向量為：ru=(1,1,3,3,2)，rv=(3,3,5,5,4)。其simpear(u,v)=1，simloc(u,v)=0.16，其實這兩個用戶評分整體偏差較大，相似度較低，其局部相似性設計更為合理。

當兩個用戶之間的共同評分數為0即Iu∩Iv=?，巴氏系數相似度也可以計算用戶u和v之間的相似度，其相似度等于局部相似度，且數值往往很小，遠遠小于1，即sim(u,v)=simloc(u,v)<<1。當兩個用戶之間存在共同評分數時其整體相似度被分割成全局和局部相似性兩部分，且sim(u,v)>simJac(u,v)>simloc(u,v)。如果兩個用戶在全局角度上是相似的，則BC(u,v)提高用戶u和v的評分之間的局部相似性，另一方面，如果用戶u和v完全不相似，則BC(u,v)降低兩個用戶評分之間的局部相似度的重要性。局部相似性提供非常重要的用戶局部信息，局部相似性也必須提供用戶評分之間的正和負關系。

融合局部相似度和全局相似度得到最終的相似度值。當BC(u,v)=1時局部相似度的作用最大，為相同項目提供最大的局部相似性；當BC(u,v)=0時局部相似度為0，此時全局相似度就是最終的相似度值。

(10)

本文提出的巴氏系數相似度特點在于整合利用巴氏系數、Jaccard和Pearson相關系數互相彌補其缺陷，完美詮釋兩個用戶之間的相似性。考慮了用戶評分的全局信息和局部信息，不再僅依靠用戶對共同項目的評分，即使沒有也可以計算兩個用戶(項目)之間的相似性，不受數據稀疏性的影響。計算相似性時利用用戶對項目的所有評分，多方面的考慮可能影響用戶之間相似度的因素，考慮用戶評分的全局相似性和局部相似性。

2.3 BCCF算法

在基于近鄰協同過濾算法的基礎上，利用巴氏系數改進相似度計算，BCCF的算法流程。

算法：BCCF算法

輸入：用戶——項目的評分矩陣Rm×n，最近鄰居數目k。

輸出：目標用戶u對未知項目的預測評分集。

算法步驟：

步驟1由數據集得到評分矩陣Rm×n。

步驟2用式(4)計算用戶u和用戶v的全局相似度(當u=v時令simJac(u,v)=0)。

步驟3利用式(7)來得到用戶u和用戶v分別評價項目的評分分布規律(當u=v時令BC(u,v)=0)。

步驟4利用步驟3的計算結果，并通過式(9)計算用戶u和用戶v的局部相似度(當u=v時令simloc(u,v)=0)。

步驟5根據步驟3和步驟4得到的全局相似度和局部相似度利用式(10)進行融合，形成最終的相似度。

步驟6利用步驟5計算任意兩兩用戶之間的相似度，最終形成相似度矩陣，然后將目標用戶u與其他用戶v之間的最終相似度遞減排序{sim(u,v1)>sim(u,v2)>…>sim(u,vm)}，選擇相似度排序中前k個用戶作為目標用戶u的最近鄰居，k個最近鄰居用戶構成目標用戶u的最近鄰居集合Iu={v1,v2,…,vk}。

步驟7已知評分矩陣R和最近鄰居集合Iu={v1,v2,…,vk}，由k個最近鄰居用戶對未知項目i的評分，通過加權平均求和得到目標用戶u對該項目的預測評分Pu,i，公式如下：

(11)

算法結束。

3 實驗與分析

3.1 實驗數據集

為了檢驗提出方法的有效性，在Movielens_100K和Movielens_1M數據集上分別進行驗證，數據集的具體參數如表1所示。

表1 實驗數據集的具體參數

本文實驗環境為：Windows 7操作系統，內存為4G，Intel(R)Core(TM)i3-4150 CPU3.5 GHz開發工具使用Matlab2013b。

3.2 評價標準

為了反映實際情況的預測誤差，本文采用平均絕對誤差MAE和均方根誤差RMSE從不同側重點來衡量算法的準確性。設在訓練集上得到用戶的預測評分集合為p={pu,1,pu,2,…,pu,n}，用戶實際評分集合為r={ru,1,ru,2,…,ru,n}，通過計算兩集合評分的平均差值或絕對平均差值來衡量推薦的精確率。則平均絕對誤差MAE定義為：

(12)

RMSE同樣用來衡量推薦的精確率，RMSE更側重于預測評分與實際評分差值的絕對值，相對MAE加大了懲罰力度，RMSE值越小，則MAE值越小，預測評分與實際評分越接近，推薦精確度越高。均方根誤差RMSE定義為：

(13)

3.3 實驗結果與分析

本實驗在Movielens不同大小的數據集上分別進行驗證，將Movielens數據集按一定比例(本實驗采用8∶2比例)隨機分為訓練集和測試集，同時進行10次交叉實驗求得平均值作為最終結果。

(1) 在Movielens_100K數據集上傳統相似度比較

當鄰居數目k從5～30變化時，比較Pearson相關系數、Jaccard相似度的MAE值。Jaccard在全局上計算共同評分所占比重，由巴氏系數取得評分分布并結合Pearson相關系數在局部上得到評分之間的相似性，由全部和局部相似性得到巴氏系數相似性；從圖1中可以看出：隨著用戶鄰居數目k的增大，本文提出的BCCF算法其MAE值總體趨于減少，當鄰居數達到30時MAE值基本穩定；相對于傳統的Jaccard和Pearson相關系數計算方法，BCCF算法的MAE值最低且相對穩定。

圖1 巴氏系數相似度與傳統相似度的MAE比較

(2) Movielens_100K數據集上不同算法之間對比

實驗中最近鄰居數k分別取5、10、15、20、25和30，根據實驗(1)中選取巴氏系數相似性作為算法的相似度計算方法，本文提出的BCCF算法分別與文獻[7]中提出的改進相似度算法(JPCC)、文獻[8]中提出的改進算法 (JMSD) 在Movielens_100K數據集上進行 MAE和RMSE值對比。

由圖2和圖3可以看出，在Movielens_100K數據集上改進算法BCCF與傳統的JPCC算法相比MAE在趨于穩定狀態下降低了6%、RMSE降低了2%；比JMSD算法相比MAE在趨于穩定狀態下降低了10%、RMSE降低了5%。在Movielens_100K數據集上BCCF算法的精確性比上述所參照的經典論文算法的精確度有所提高，從一個側面說明了在該數據集中實際存在著用戶對項目的共同評分很少的情況下進行優化的方案，即采用巴氏系數進行用戶間所有的評分能夠進一步提高算法的精度。

圖2 Movielens_100K數據集上三種算法的MAE對比

圖3 Movielens_100K數據集上三種算法的RMSE對比

(3) 在Movielens_1M數據集上不同算法之間對比

本節實驗中最近鄰居數k為 5～30，根據實驗(1)中選取巴氏系數改進相似性作為算法的相似度計算方法，在Movielens_1M數據集上，本文提出的BCCF算法分別與JPCC算法、JMSD算法進行 MAE和RMSE值對比。其效果分別如圖4、圖5所示。

圖4 Movielens_1M數據集上三種算法的MAE對比

圖5 Movielens_1M數據集上三種算法的RMSE對比

由圖4和圖5可以看出，在Movielens_1M數據集上改進算法BCCF與傳統的JPCC算法相比在趨于穩定狀態下MAE降低了20%、RMSE降低了17%，比JMSD算法相比在趨于穩定狀態下MAE降低了10%、RMSE降低了4%。RMSE和MAE值越小則表示推薦質量越好，且在Movielens_1M數據集上BCCF算法的RMSE和MAE值比在Movielens_100K數據集上實驗結果更小，說明數據集越稀疏其BCCF算法的MAE和RMSE性能越好，說明本文提出的一種巴氏系數改進相似度的協同過濾算法能有效緩解評分數據稀疏性問題及其帶來的推薦精度問題。

4 結 語

本文提出了一種基于巴氏系數的改進相似度計算方法，考慮了用戶評分的全局和局部相似性，能更全面分析用戶之間的相似性，并在此基礎上設計了BCCF算法。通過與傳統協同過濾算法比較，實驗結果表明：BCCF算法不再僅依賴于共同評分，解決了推薦系統中數據極大稀疏時無法計算相似度，以及由數據稀疏性帶來的推薦精度問題；現實情況中用戶對項目的共同評分很少甚至沒有，故BCCF有很強的實用性，BCCF更適用于評分矩陣稀疏的數據集；BCCF合理利用用戶的每一個評分，根據用戶的評分來發現其內在的相關性。考慮用戶的所有評分，造成計算相似度時其時間復雜度增加，對巴氏系數相似度計算進行優化，找到能降低其時間復雜度方法，進一步提高算法性能。

[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] 榮輝桂,火生旭,胡春華.基于用戶相似度的協同過濾推薦算法[J].通信學報,2014,35(2):16-24.

[5] 吳毅濤,張興明,王興茂.基于用戶模糊相似度的協同過濾算法[J].通信學報,2016,37(1):198-206.

[6] 孫達明,張斌,張書波,等.一種流行性與相似性結合查詢推薦策略[J].小型微型計算機系統,2016,37(6):1121-1125.

[7] 鄭翠翠,李林.協同過濾算法中的相似性度量方法研[J].計算機工程與應用,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。國家自然科學基金項目(61202286)；河南省高等學校青年骨干教師資助計劃項目(2015GGJS-068)。武文琪，碩士生，主研領域：數據挖掘，推薦算法。王建芳，副教授。張朋飛，碩士生。劉永利，副教授。

TP391

A

10.3969/j.issn.1000-386x.2017.08.047