楊家慧 劉方愛

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

關(guān)鍵詞：

協(xié)同過濾；巴氏系數(shù)；杰卡德系數(shù)；相似性度量；矩陣稀疏性

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

0引言

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

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

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

1相似性度量定義

1.1巴氏系數(shù)相似度

1.2Jaccard相似性度量

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

1.3修正的余弦相似性

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

2基于巴氏系數(shù)和Jaccard系數(shù)的本文協(xié)同過濾推薦算法

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

2.1引入巴氏系數(shù)和Jaccard系數(shù)的相似性度量

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

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

2.2產(chǎn)生推薦

通過本文提出的相似性度量得到目標用戶的最近鄰居，下一步需要產(chǎn)生相應(yīng)的推薦。設(shè)用戶Ua的最近鄰居集合用N（a）表示，則目標用戶Ua對項目Ii的預(yù)測評分Rai此處的ui，u是否應(yīng)該大寫，i作為u的下標？請明確。感覺描述不太恰當，沒有看到關(guān)于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）。

輸出：對目標項目的預(yù)測評分Rai。

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

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

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

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

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

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

3實驗設(shè)置

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

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

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

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

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

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

3.1評價指標

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

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

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

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

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

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

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

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

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

3.2實驗結(jié)果和分析

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

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

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

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

4結(jié)語

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

參考文獻：

[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]

黃創(chuàng)光，印鑒，汪靜，等.不確定近鄰的協(xié)同過濾推薦算法[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.