基于巴氏系數和Jaccard系數的協同過濾算法

楊家慧 劉方愛

摘要：針對傳統基于鄰域的協同過濾推薦算法存在數據稀疏性及相似性度量只能利用用戶共同評分的問題，提出一種基于巴氏系數和Jaccard系數的協同過濾算法（CFBJ）。在項目相似性度量中，該算法引入巴氏系數和Jaccard系數，巴氏系數利用用戶所有評分信息克服共同評分的限制，Jaccard系數可以增加相似性度量中共同評分項所占的比重。該算法通過提高項目相似度準確率來選取最近鄰，優化了對目標用戶的偏好預測和個性化推薦。實驗結果表明，該算法比平均值杰卡德差分（MJD）算法、皮爾森系數（PC）算法、杰卡德均方差（JMSD）算法、PIP算法誤差更小，分類準確率更高，有效緩解了用戶評分數據稀疏所帶來的問題，提高了推薦系統的預測準確率。

關鍵詞：

協同過濾；巴氏系數；杰卡德系數；相似性度量；矩陣稀疏性

中圖分類號： TP301.6 文獻標志碼：A

0引言

推薦系統[1]根據用戶的興趣特點和歷史記錄向用戶推薦感興趣的內容，有效解決信息過載問題，從而使用戶在海量數據中快速、準確地找到有價值的信息。協同過濾推薦[2]是推薦系統中最基本的算法之一，分為基于用戶的協同過濾推薦[3]和基于項目的協同過濾推薦[4]。協同過濾算法的基本思想是計算用戶或項目間相似度，然后根據相似度預測目標用戶對目標項目的評分并產生推薦集。

當前協同過濾推薦算法存在數據稀疏性[5]問題，當數據集項目較多時，用戶項目矩陣數據通常十分稀疏。傳統的相似性度量如皮爾森相關系數[6]和余弦相似性[7]等在計算用戶或項目間相似性時依賴于用戶對項目的共同評分。假設在評分矩陣中，用戶的評分數量較少或者有共同評分的項目很少，那么相似性度量就存在一定偶然性[8]，不適用于稀疏矩陣。為了解決數據稀疏性問題，相關研究引入了不同的相似性度量。例如，Luo等[9]通過引入局部用戶相似性和全局用戶相似性來解決稀疏數據中的相似性問題，利用每個用戶的奇異向量計算用戶之間的局部相似性，最后把局部近鄰和全局近鄰的預測進行線性擬合。Ahn等[10]提出了PIP（ProximityImpactPopularity）度量模型，通過分析皮爾遜相似性度量和余弦相似性度量的缺點，考慮用戶評分的三方面：接近、影響和普及，但這種相似性度量只考慮局部評分信息，不考慮用戶全局偏好。Herlocker等[11]提出加權Pearson相關系數解決傳統Pearson相關系數不考慮共同評分用戶規模的問題，引入鄰居置信度，共同評分項越高則置信度越高。Jamali等[12]對用戶之間的信任關系進行深度搜索，尋找更深層次的相似用戶來進行推薦。Bobadilla等[13]提出了一種結合了Jaccard和平均平方差的矩陣，假定這兩項措施可以互補。這些方法在一定程度上減少了矩陣稀疏性[14]對推薦算法的影響，但沒有從根本上解決協同過濾推薦算法中相似性度量受共同評分限制的問題。

本文提出了一種基于巴氏系數和Jaccard系數的協同過濾算法（Collaborative Filtering algorithm based on Bhattacharyya coefficient and Jaccard coefficient， CFBJ）。該方法通過巴氏系數和Jaccard系數度量項目間相似性。巴氏系數利用用戶間所有的評分信息，克服了共同評分的限制。Jaccard系數可以增加相似性度量中共同評分項所占的比重，將評分項目進行關聯，計算無共同評分項的用戶間相似度，進而預測目標用戶對目標項目的評分，為用戶進行推薦。該算法擺脫了傳統協同過濾算法在計算用戶相似性時共同評分的限制，有效緩解用戶評分數據極端稀疏情況下使用傳統度量方法帶來的問題，提高推薦系統的推薦質量。

1相似性度量定義

1.1巴氏系數相似度

1.2Jaccard相似性度量

Jaccard系數是兩個集合交集與并集的元素數目之比，用于測量兩個集合在共同項目上的重疊度。Jaccard系數計算符號度量或布爾值度量的個體間的相似度，不考慮用戶對項目的評分取值，僅關注用戶是否對該項目評過分。Jaccard系數值等于兩個用戶關聯項目數量的交集除于關聯項目數量的并集，形式化表示公式如下：

1.3修正的余弦相似性

通過向量間的余弦夾角計算相似性度量，為了修正不同用戶存在不同評分尺度的偏差，在標準余弦相似性的基礎上，減去用戶對所有項目的平均評分來改善這一缺陷。計算式如下：

2基于巴氏系數和Jaccard系數的本文協同過濾推薦算法

傳統協同過濾推薦算法通過用戶或項目內個體間的相互作用，來尋找對當前對象影響力最大的k個鄰居，為當前對象屬性作出預測[8]。使用合適的相似性度量找到目標用戶的鄰域是基于鄰域的協同過濾算法的最關鍵步驟。本文提出的相似性度量適于用戶評分數目少或沒有共同評分的稀疏數據集，巴氏系數通過用戶間所有評分計算兩個項目間的相關性，且使用局部信息計算用戶評分相關性，利用Jaccard系數增加相似性度量中共同評分項所占的比重。

2.1引入巴氏系數和Jaccard系數的相似性度量

傳統基于用戶或者基于項目的協同過濾算法，如果評分數據相當稀疏，在計算用戶或項目間的相似性時會過多考慮用戶間共同評分，與實際相似度存在較大偏差，導致推薦效果不理想。對此本文將巴氏相似度和用戶局部相似度結合進行改進。令IUa和IUb分別為用戶Ua和用戶Ub在所有項目上的評分集合，若用戶Ua和Ub之間無共同評分即IUa∩IUb=，用戶Ua和Ub之間的相似性度量定義為：

當用戶評分都在同一個項目上時，SimBC（Ii，Ii）=1，此時用戶間的相似性度量由局部相似度決定；當用戶評分在完全不相似的項目上時，SimBC（Ii，Ij）=0，此時用戶間的相似性度由Jaccard相似度決定。巴氏系數利用用戶間所有的評分信息，提高了數據集中評分利用率；Jaccard系數彌補傳統相似性度量側重用戶對項目的評分而忽略項目類別的不足，增加相似性度量中共同評分項所占的比重，優化對目標用戶的偏好預測和個性化推薦。該算法擺脫了傳統協同過濾算法在計算用戶相似性時共同評分的限制，有效緩解了用戶評分數據稀疏所帶來的問題，提高了推薦系統的預測準確率。

2.2產生推薦

通過本文提出的相似性度量得到目標用戶的最近鄰居，下一步需要產生相應的推薦。設用戶Ua的最近鄰居集合用N（a）表示，則目標用戶Ua對項目Ii的預測評分Rai此處的ui，u是否應該大寫，i作為u的下標？請明確。感覺描述不太恰當，沒有看到關于i的定義。，可通過用戶Ua對最近鄰居集合N（a）中項目的評分得到，計算方法如下：

Rai=Ua+[∑k∈N（a）Sim（Ua，Ub）*（Rki-ka）]/[∑k∈N（a）|Sim（Ua，Ub）|]（9）

其中：Ua表示用戶Ua對項目評分的平均值；Sim（Ua，Ub）表示用戶Ua和Ub之間的相似度取值；ka表示用戶Ua第k個近鄰評分的平均值，Rki表示第k個近鄰在i上的評分。

2.3算法描述

輸入：目標用戶Ua，目標項目Ii，用戶項目評分矩陣R（m×n）。

輸出：對目標項目的預測評分Rai。

1）在矩陣R（m×n）中，尋找對目標項目i評分的用戶，并統計該用戶數量n（i）及每個評分分值為v的用戶數量n（v），根據式（2）、（7）分別計算用戶巴氏系數相似度SimBC（Ii，Ij）和局部相似度Simrate（Ua，Ub）。

2）結合步驟1），根據式（5）計算用戶總體相似度Sim（Ua，Ub）。

3）根據式（3）和（7）計算用戶Jaccard系數相似度Sim′（Ua，Ub）Jaccard。

4）對用戶總體相似度進行調整，加入Jaccard相似度，根據式（8）計算得到用戶Ua與其他用戶間的最終總體相似度Sim′（Ua，Ub）。

5）根據最終的總體相似度，選取目標用戶最近K個鄰居集合N（a）。

6）根據式（9）計算目標用戶對目標項目的預測評分Rai。

3實驗設置

實驗數據集選用著名電影評分數據集MovieLens，該數據集包含3708萬條記錄，記錄了7000個用戶對3708部電影的評分，每個用戶至少對20部電影進行了評分，評分范圍為1～5。為了形式化描述用戶通過對電影的不同評分表達自己的興趣程度，5表示“perfect”（非常好），1表示“poor”（差）。本文將MovieLens數據集隨機分為兩個子集MLa和MLb，其中：MLa子集上有312個用戶只有一個共同評分項目，12個用戶有兩個共同評分項目；MLb子集上有28個用戶只有一個共同評分項目。為了驗證CFBJ的有效性，本文隨機搜索了5個相關項目作為用戶的目標項目。

為驗證CFBJ有效性，采用4種協同過濾算法與提出的方法進行實驗對比。對比實驗用到的算法如下：

1）平均值杰卡德差分（Mean Jaccard Difference， MJD）算法。本文實現文獻[18]中基于均值杰卡德差分協同過濾推薦算法，該算法考慮共同評分項中不同評價尺度問題。

2）皮爾森系數（Pearson Correlation， PC）相似度算法。本文實現文獻[19]中利用PC系數計算不同用戶間項目相似度。

3）杰卡德均方差（Jaccard and Mean Squared Difference， JMSD）算法。本文實現文獻[20]中基于Jaccard和平均平方差的協同過濾推薦算法，考慮Jaccard和平均平方差兩者之間互補的情況。

4）PIP（ProximityImpactPopularity）。本文實現了文獻[10]中提出的接近、影響和普及度量模型，該算法分析皮爾遜相似性度量和余弦相似性度量的缺點，考慮模型三方面要素。

3.1評價指標

評價推薦系統推薦質量的度量標準主要包括統計精度度量和決策支持精度度量兩類。其中，統計精度度量包括均方根誤差（Root Mean Squared Error， RMSE）和平均絕對誤差（Mean Absolute Error， MAE），衡量評分預測準確性的標準，反映算法的預測評分與用戶實際評分的貼近程度，值越小，算法的推薦性能越好。MAE公式定義：

MAE=1T∑Ua，i|Rai-rai|

其中：rai表示用戶Ua對項目Ii的實際評分；Rai表示相應的預測評分；T表示測試樣本的數量。同樣，RMSE計算式可以表示為：

RMSE=1T∑Ua，i（Rai-rai）2

決策支持精度度量包括準確率（precision）和召回率（recall）反映推薦系統對分類預測的準確程度，適合具有明確二分喜好的推薦系統。precision和recall定義為：

precision=|L∩L′|/|L|

recall=|L∩L′|/|L′|

其中：L表示推薦列表的長度；L′表示推薦列表中用戶評分較高的項目的數量，但存在precision和recall兩者相互矛盾的情況，本文采用F1measure綜合指標反映分類預測的準確程度。F1measure定義為：

F1measure=（2×precision×recall）/（precision+recall）

3.2實驗結果和分析

首先在MLa子集上比較不同協同過濾算法的MAE和RMSE值，查看算法的預測評分與用戶實際評分的貼近程度，相應結果如圖1所示。由圖1可知，CFBJ、MJD、PC、JMSD和PIP算法隨著K最近鄰數量的變化，MAE和RMSE值隨之變化。其中，CFBJ在MAE和RMSE上的值一直比MJD、PC、JMSD和PIP算法的值都小，說明CFBJ利用用戶間所有的評分信息后，預測評分與用戶實際評分更貼近，算法的推薦性能更好。其他算法尋找最近鄰時不能利用用戶所有的評分信息，僅使用一個共同評分項，且目標用戶的近鄰只有一個，預測時錯誤數量超過了近鄰的最大數（MAE>0.805，RMSE>1.02，K∈[40，400]）。在預測精度方面，PIP算法的準確率比較接近CFBJ；但CFBJ的準確率更高（MAE>0.73，RMSE<1.00）。

在MLa子集上比較不同協同過濾算法的F1measure值，相應結果如圖2所示。由圖2可知，隨著最近鄰數目的遞增，每種協同過濾算法的F1measure都呈上升趨勢，但CFBJ的F1measure值基本上大于等于其他基于鄰域的協同過濾算法。當K=400時，CFBJ的F1measure接近0.67，MJD的F1measure接近0.57。CFBJ推薦的準確率比MJD高17%。PIP算法的表現與MJD算法相似，其他的協同過濾算法表現不佳。這也說明了傳統的相似性度量不能正確檢索相關項目。

接著在MLb子集上比較不同協同過濾算法的MAE和RMSE值變化，相應結果如圖3所示。由圖3可知，PIP算法在MAE和RMSE的值小于MJD、PC、JMSD算法，這些算法的相似性度量取決于用戶共同評分項，MLb子集上平均每16個用戶與目標用戶只有一個共同評分項，所以隨著最近鄰數量增加，這些協同過濾算法的精度不再提高。而CFBJ由于利用了用戶間所有的評分，不受共同評分項的影響，MAE和RMSE值隨著近鄰數目的增加而變化，且數值最低。說明CFBJ在共同評分項稀疏的情況下，推薦的準確性依然高于其他4個算法。

在MLb子集上執行不同協同過濾算法的F1measure情況，相應結果如圖4所示。由圖4可以看出，CFBJ的值一直高于其他算法，隨著最近鄰數目的增加F1measure值也保持增長。實驗中MLb子集用戶的平均評分為5.1分，CFBJ的F1measure接近0.47此處正文描述錯誤，應該是0.370.37，而其他算法得到的F1measure值不足0.1，說明CFBJ的推薦效果比其他算法準確。這表明MJD、PC、JMSD和PIP算法的相似性度量方法在評分數據稀疏且規定相關項目的情況下，對目標用戶進行推薦表現不佳。CFBJ能夠應對高度稀疏的評分數據集，為用戶提供更加準確的推薦。

4結語

針對協同過濾算法存在的數據稀疏性問題，本文提出的基于鄰域的CFBJ，在稀疏的評分數據集上，巴氏系數利用用戶間所有的評分信息擺脫共同評分的限制，Jaccard系數彌補傳統相似性度量側重用戶對項目的評分而忽略項目類別的不足，增加相似性度量中共同評分項所占的比重，為目標用戶提供更加準確有效的推薦。該算法最大的優點是擺脫了傳統相似性度量中用戶共同評分的限制，提高了用戶評分數據的利用率。實驗對比表明，CFBJ可以在高度稀疏的評分數據集上為用戶提供更準確的推薦。由于推薦系統中數據量龐大，系統的可擴展性問題尤為突出，今后將致力于把協同過濾算法遷移部署到云計算平臺中改善推薦系統的實時性。

參考文獻：

[1]

HERLOCKER J L， KONSTAN J A， TERVEEN L G， et al. Evaluating collaborative filtering recommender systems [J]. ACM Transactions on Information Systems， 2004， 22（1）： 5-53.

[2]

SARWAR B， KARYPIS G， KONSTAN J， et al. Itembased collaborative filtering recommendation algorithms [C]// Proceedings of the 10th International Conference on World Wide Web. New York： ACM， 2001： 285-295.

[3]

GONG S. A collaborative filtering recommendation algorithm based on user clustering and item clustering [J]. Journal of Software， 2010， 5（7）： 745-752.

[4]

DESHPANDE M， KARYPIS G. Itembased topn recommendation algorithms [J]. ACM Transactions on Information Systems， 2004， 22（1）： 143-177.

[5]

HUANG Z， CHEN H， ZENG D. Applying associative retrieval techniques to alleviate the sparsity problem in collaborative filtering [J]. ACM Transactions on Information Systems， 2004， 22（1）： 116-142.

[6]

ADLER J， PARMRYD I. Quantifying colocalization by correlation： the Pearson correlation coefficient is superior to the Manders overlap coefficient [J]. Cytometry Part A， 2010， 77（8）： 733-742.

[7]

ANAND S S， MOBASHER B. Intelligent techniques for Web personalization [C]// Proceedings of the 2003 International Conference on Intelligent Techniques for Web Personalization. Berlin： Springer， 2003： 1-36.

[8]

黃創光，印鑒，汪靜，等.不確定近鄰的協同過濾推薦算法[J].計算機學報，2010，33（8）：1369-1377.（HUANG C G， YIN J， WANG J， et al. Uncertain neighbors collaborative filtering recommendation algorithm [J]. Chinese Journal of Computers， 2010， 33（8）： 1369-1377.）

[9]

LUO H， NIU C， SHEN R， et al. A collaborative filtering framework based on both local user similarity and global user similarity [J]. Machine Learning， 2008， 72（3）：231-245.

[10]

AHN H J. A new similarity measure for collaborative filtering to alleviate the new user coldstarting problem [J]. Information Sciences， 2008， 178（1）：37-51.

[11]

HERLOCKER J L， KONSTAN J A， BORCHERS A， et al. An algorithmic framework for performing collaborative filtering [C]// Proceedings of the 22nd Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. New York： ACM， 1999： 230-237.

[12]

JAMALI M， ESTER M. Trustwalker： a random walk model for combining trustbased and itembased recommendation [C]// Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM， 2009： 397-406.

[13]

BOBADILLA J， ORTEGA F， HERNANDO A， et al. A similarity metric designed to speed up， using hardware， the recommender systems knearest neighbors algorithm [J]. KnowledgeBased Systems， 2013， 51： 27-34.

[14]

BOBADILLA J， ORTEGA F， HERNANDO A. A collaborative filtering similarity measure based on singularities [J]. Information Processing & Management， 2012， 48（2）： 204-217.

[15]

PATRA B K， LAUNONEN R， OLLIKAINEN V， et al. Exploiting Bhattacharyya similarity measure to diminish user coldstart problem in sparse data [M]// Discovery Science. Berlin： Springer， 2014： 252-263.

[16]

KAILATH T. The divergence and Bhattacharyya distance measures in signal selection [J]. IEEE Transactions on Communication Technology， 1967， 15（1）： 52-60.

[17]

JAIN A K. On an estimate of the Bhattacharyya distance [J]. IEEE Transactions on Systems Man & Cybernetics， 1976， SMC6（11）： 763-766.

[18]

BOBADILLA J， ORTEGA F， HERNANDO A， et al. A collaborative filtering approach to mitigate the new user cold start problem [J]. KnowledgeBased Systems， 2012， 26： 225-238.

[19]

BREESE J S， HECKERMAN D， KADIE C. Empirical analysis of predictive algorithms for collaborative filtering [C]// Proceedings of the Conference on Uncertainty in Artificial Intelligence. San Francisco： Morgan Kaufmann， 1998： 43-52.

[20]

BOBADILLA J， SERRADILLA F， BERNAL J. A new collaborative filtering metric that improves the behavior of recommender systems [J]. KnowledgeBased Systems， 2010， 23（6）：520-528.