王竹婷，夏竹青，周艷玲

(合肥學(xué)院 計(jì)算機(jī)科學(xué)與技術(shù)系，合肥 230601)

?

動(dòng)態(tài)混合相似性度量下的協(xié)同過(guò)濾推薦算法

王竹婷，夏竹青，周艷玲

(合肥學(xué)院 計(jì)算機(jī)科學(xué)與技術(shù)系，合肥 230601)

協(xié)同過(guò)濾是個(gè)性化推薦系統(tǒng)中應(yīng)用于最為成熟的技術(shù)之一。其中基于用戶的協(xié)同過(guò)濾采用相似性度量方法尋找近鄰用戶，再使用近鄰用戶的評(píng)分預(yù)測(cè)目標(biāo)用戶未評(píng)分項(xiàng)的評(píng)分值。針對(duì)傳統(tǒng)的相似性度量方法在處理大規(guī)模稀疏性數(shù)據(jù)時(shí)的缺陷，提出一種新的改進(jìn)策略，將用戶評(píng)分習(xí)慣、群體相似性和評(píng)分值相似性三類因素納入用戶相似性度量方法中，并動(dòng)態(tài)調(diào)整三者的權(quán)重。根據(jù)在MovieLens數(shù)據(jù)集上的測(cè)試結(jié)果表明，該改進(jìn)策略可有效提高算法的推薦質(zhì)量。

推薦系統(tǒng)；協(xié)同過(guò)濾；相似度

0 引 言

推薦系統(tǒng)現(xiàn)已成功應(yīng)用于電子商務(wù)領(lǐng)域幫助用戶解決信息過(guò)載問(wèn)題。該系統(tǒng)主要作用是記錄并分析用戶的網(wǎng)上行為，挖掘出用戶感興趣的商品項(xiàng)目，并將商品快速推薦給相應(yīng)的用戶，同時(shí)提高電子商務(wù)網(wǎng)站產(chǎn)品的銷售量。推薦系統(tǒng)中常用技術(shù)包括基于內(nèi)容的推薦(content-based filtering, CBF)、協(xié)同過(guò)濾推薦(collaborative filtering, CF)、關(guān)聯(lián)規(guī)則(association rule, AR)和序列模式分析(sequential pattern analysis, SPA)，而CF推薦算法以其簡(jiǎn)單、高效的特性，在眾多推薦系統(tǒng)中得到了較好的應(yīng)用。[1]

CF算法大體上又可分為基于模型(model-based, MB_CF)和基于近鄰(neighborhood-based, NB_CF)的兩類。[2]MB_CF使用機(jī)器學(xué)習(xí)相關(guān)技術(shù)利用訓(xùn)練集數(shù)據(jù)產(chǎn)生推薦模型，再利用該模型進(jìn)行推薦[3]；NB_CF又分為基于用戶(user-based, UB_CF)和基于項(xiàng)目(item-based, IB_CF )的兩種方法，兩者都基于一個(gè)簡(jiǎn)單的思想，即興趣相投的用戶對(duì)同一項(xiàng)目的評(píng)分會(huì)比較相似，或者，相似度較高的項(xiàng)目被某一用戶同時(shí)喜愛(ài)的可能性也較高[4]。著名的Netflix競(jìng)賽結(jié)果告訴我們，MB_CF和NB_CF這兩種算法在處理不同的數(shù)據(jù)集時(shí)表現(xiàn)出來(lái)的性能也是有所差異的，沒(méi)有一種算法可以在所有情況下都取得更好的推薦效果。[5]本文重點(diǎn)研究UB_CF算法。

傳統(tǒng)的UB_CF算法在對(duì)目標(biāo)用戶進(jìn)行相關(guān)項(xiàng)目推薦時(shí)主要依賴于其近鄰用戶對(duì)該項(xiàng)目的興趣程度，因此，近鄰用戶的確定對(duì)于算法的推薦質(zhì)量有著至關(guān)重要的影響。[6]大多數(shù)協(xié)同過(guò)濾推薦系統(tǒng)則利用Pearson相關(guān)系數(shù)(Pearson correlation coefficient, PCC)、余弦相似性(cosine similarity, CS)來(lái)計(jì)算用戶相似度，這些方法都利用用戶共同評(píng)分項(xiàng)目的評(píng)分值計(jì)算得到結(jié)果，由于實(shí)際用戶評(píng)分?jǐn)?shù)據(jù)的稀疏性導(dǎo)致共同評(píng)分的項(xiàng)目個(gè)數(shù)更加稀少，極少數(shù)項(xiàng)目的評(píng)分相似并不能代表個(gè)體間的興趣相似，因此傳統(tǒng)的相似性度量方法過(guò)于單一，難以得到理想的推薦結(jié)果。本文提出一種新的混合相似性度量方法，將用戶評(píng)分習(xí)慣、共同興趣度和評(píng)分值相似度三類因素納入相似性度量方法中，并根據(jù)用戶評(píng)分習(xí)慣的不同，利用用戶評(píng)分標(biāo)準(zhǔn)差對(duì)評(píng)分結(jié)果進(jìn)行修正。

1 問(wèn)題描述及相關(guān)工作

1.1 基于用戶的協(xié)同過(guò)濾算法

協(xié)同過(guò)濾算法最早由GroupLens新聞組提出并被廣泛應(yīng)用于商業(yè)領(lǐng)域。該方法使用現(xiàn)有的評(píng)分?jǐn)?shù)據(jù)產(chǎn)生預(yù)測(cè)評(píng)分并為用戶生成推薦列表。本文令R={rui}M*N為推薦系統(tǒng)中特定的評(píng)分矩陣，rui為用戶u對(duì)項(xiàng)目i的評(píng)分值，當(dāng)rui=0時(shí)，表示用戶u未評(píng)分過(guò)項(xiàng)目i?；谟脩舻膮f(xié)同過(guò)濾算法的任務(wù)是通過(guò)矩陣R中的數(shù)據(jù)計(jì)算出用戶之間的相似度，選擇與目標(biāo)用戶相似度高的作為近鄰用戶，再利用近鄰用戶的評(píng)分?jǐn)?shù)據(jù)預(yù)測(cè)目標(biāo)用戶對(duì)未評(píng)分項(xiàng)目的評(píng)分值。[7]預(yù)測(cè)評(píng)分方法如公式(1)所示:

(1)

通過(guò)上述的評(píng)分預(yù)測(cè)方法不難得知，協(xié)同過(guò)濾算法預(yù)測(cè)的準(zhǔn)確性與用戶間的相似性計(jì)算和近鄰用戶的選擇密切相關(guān)。因此，為推薦系統(tǒng)設(shè)計(jì)一種高質(zhì)量的相似性度量方法尤為重要。

1.2 傳統(tǒng)的相似性度量方法

傳統(tǒng)的相似性度量方法包括余弦相似性(CS)、Pearson相關(guān)系數(shù)(PCC)、Jaccard 系數(shù)(JS)等。其中，余弦相似性和Pearson相關(guān)系數(shù)在推薦系統(tǒng)中的應(yīng)用最為頻繁。

余弦相似性在信息檢索領(lǐng)域應(yīng)用的較為成功，其將用戶在n個(gè)項(xiàng)目上的評(píng)分?jǐn)?shù)據(jù)看作成一個(gè)n維向量，通過(guò)計(jì)算用戶之間的n維空間向量夾角余弦值來(lái)度量相似性，[8]

(2)

Pearson相關(guān)系數(shù)在基于用戶的協(xié)同過(guò)濾算法中應(yīng)用最為成功，其通過(guò)用戶共同評(píng)分項(xiàng)目的評(píng)分值計(jì)算用戶之間的線性相關(guān)性，計(jì)算結(jié)果在[-1,+1]之間，其值大于0表示正相關(guān)，小于0為負(fù)相關(guān)，等于0則不相關(guān)。[9]計(jì)算方法如公式(3)所示：

(3)

1.3 傳統(tǒng)的相似性度量方法缺陷

余弦相似性沒(méi)有考慮到不同用戶評(píng)分尺度的差異性，而且其分子項(xiàng)是兩用戶共同評(píng)分項(xiàng)的乘積累加，分母項(xiàng)是用戶各自評(píng)分的方根乘積，由于共同的評(píng)分項(xiàng)目數(shù)遠(yuǎn)小于各自評(píng)分?jǐn)?shù)，因此分母項(xiàng)的值遠(yuǎn)大于分子項(xiàng)，計(jì)算得到的相似度值偏低，可選擇的近鄰用戶數(shù)量少，預(yù)測(cè)誤差較為明顯。修正的余弦相似性也只考慮到用戶評(píng)分尺度的問(wèn)題，卻未能有效增加近鄰用戶的數(shù)量。

Pearson相關(guān)系數(shù)雖然優(yōu)于余弦相似性，但也存在一些難以克服的缺陷，簡(jiǎn)要概括如下。

(1)沒(méi)有共同評(píng)分項(xiàng)：兩用戶可能有共同的興趣愛(ài)好，但由于同類型的項(xiàng)目繁多，而沒(méi)有購(gòu)買(mǎi)過(guò)同一種項(xiàng)目，此時(shí)包括Pearson相關(guān)系數(shù)和余弦相似性在內(nèi)的上述所有相似性度量方法失效；

(2)只有一個(gè)共同評(píng)分項(xiàng)：如果用戶間僅有一個(gè)共同評(píng)分項(xiàng)，那么按照公式(3)的計(jì)算結(jié)果不是+1就-1，無(wú)衡量?jī)r(jià)值；

(3)所有評(píng)分值相同：例如用戶的評(píng)分值分別為(1,1,1)和(2,2,2)，此時(shí)公式(3)的分母項(xiàng)為0，該方法再次失效。[10]

上述所列雖為一些極端情況，但在實(shí)際推薦系統(tǒng)中，由于用戶和項(xiàng)目的數(shù)量都十分龐大，再加上用戶評(píng)分?jǐn)?shù)據(jù)的極度稀疏，導(dǎo)致以上問(wèn)題出現(xiàn)的幾率升高，也極大降低了協(xié)同過(guò)濾算法的推薦的準(zhǔn)確性。

2 動(dòng)態(tài)混合相似性度量方法

本文認(rèn)為傳統(tǒng)的相似性計(jì)算方法僅僅從用戶評(píng)分的相似性方面進(jìn)行度量，衡量的標(biāo)準(zhǔn)過(guò)于單一，在處理大規(guī)模稀疏數(shù)據(jù)時(shí)缺陷較為明顯。為提高相似性計(jì)算方法的精度，提出了一種新的混合相似性度量方法，分別從用戶評(píng)分值、群體相似性和評(píng)分習(xí)慣三個(gè)方面綜合度量。

2.1 群體相似性

如前一部分所述，傳統(tǒng)的用戶相似性只能夠在有共同評(píng)分項(xiàng)目的用戶之間衡量，對(duì)于沒(méi)有共同評(píng)分項(xiàng)目的用戶相似性默認(rèn)為0的處理方法難免有失偏頗。根據(jù)社交網(wǎng)絡(luò)SocialBased好友推薦算法的啟發(fā)，認(rèn)為用戶之間即使沒(méi)有共同的評(píng)分項(xiàng)目，但擁有相當(dāng)數(shù)量的共同好友說(shuō)明其處于相似的社會(huì)群體中，也具備共同的相似性特征，即群體相似性。因此，本文將社交網(wǎng)絡(luò)中用戶的群體相似性引入作為衡量用戶相似性的標(biāo)準(zhǔn)之一。

(4)

2.2 評(píng)分習(xí)慣相似性

推薦系統(tǒng)中不同用戶對(duì)某一項(xiàng)目給出了相同的評(píng)分值并不代表他們對(duì)該項(xiàng)目有著同樣的興趣，因?yàn)椴煌脩舻脑u(píng)分習(xí)慣也有所不同。有些用戶習(xí)慣性打高分，有些用戶打分則比較苛刻。因此，如何衡量用戶評(píng)分習(xí)慣的差異性是提高相似性計(jì)算精度的有效方法之一。本文擬采用Bhattacharyya系數(shù)衡量用戶在評(píng)分習(xí)慣上的相似性。

(5)

2.3 動(dòng)態(tài)混合相似性

用戶間的混合相似度通過(guò)對(duì)共同評(píng)分項(xiàng)目的評(píng)分相似性、群體相似性和評(píng)分習(xí)慣的相似性三方面共同衡量。其中，對(duì)于用戶共同評(píng)分項(xiàng)目的評(píng)分相似性本文采用Pearson相關(guān)系數(shù)衡量，群體相似性和評(píng)分習(xí)慣的相似性則分別采用上述Jaccard系數(shù)和Bhattacharyya系數(shù)衡量，并根據(jù)用戶共同評(píng)分項(xiàng)的數(shù)量動(dòng)態(tài)調(diào)整權(quán)重。當(dāng)共同評(píng)分項(xiàng)目數(shù)量較多時(shí)，通過(guò)Pearson相關(guān)系數(shù)計(jì)算用戶相似性結(jié)果較為準(zhǔn)確，應(yīng)適當(dāng)增加該項(xiàng)的權(quán)重；當(dāng)共同評(píng)分項(xiàng)目數(shù)量較少時(shí)，則減少該項(xiàng)權(quán)重。

(6)

(7)

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

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

實(shí)驗(yàn)采用 Minnesota 大學(xué)GroupLens研究小組提供的MovieLens數(shù)據(jù)集ml-100k對(duì)本文提出的動(dòng)態(tài)混合相似度量方法進(jìn)行評(píng)估測(cè)試，該數(shù)據(jù)集包括943名用戶對(duì)1 682部電影的100,000項(xiàng)評(píng)分?jǐn)?shù)據(jù)；其中，每位用戶至少評(píng)分過(guò)20部電影，用戶屬性描述包括年齡、性別和職業(yè)。電影類型19種，評(píng)分值的取值范圍為1—5，用戶評(píng)分矩陣的數(shù)據(jù)密度為6.3%；該數(shù)據(jù)集中共7組數(shù)據(jù)，每組數(shù)據(jù)分訓(xùn)練集和測(cè)試集，實(shí)驗(yàn)通過(guò)訓(xùn)練集數(shù)據(jù)預(yù)測(cè)用戶對(duì)未評(píng)分項(xiàng)目的評(píng)分值，再將預(yù)測(cè)結(jié)果與測(cè)試集數(shù)據(jù)作對(duì)比分析。

3.2 評(píng)估標(biāo)準(zhǔn)

本文以平均絕對(duì)偏差(Mean Absolute Error, MAE)為評(píng)估算法推薦質(zhì)量好壞的標(biāo)準(zhǔn)，其計(jì)算方法如公式(8)所示，pij是通過(guò)訓(xùn)練集產(chǎn)生的預(yù)測(cè)評(píng)分，qij是測(cè)試集提供的實(shí)際評(píng)分，Ni是測(cè)試集提供的用戶i的評(píng)分項(xiàng)目數(shù)量，MAEi是用戶i對(duì)Ni個(gè)項(xiàng)目預(yù)測(cè)評(píng)分的平均絕對(duì)偏差，公式(9)中M是全體用戶總數(shù)，MAE則是全體用戶的平均絕對(duì)偏差。從公式中不難看出，MAE的值越小，算法預(yù)測(cè)的結(jié)果與實(shí)際評(píng)分值越接近，算法推薦的準(zhǔn)確性越高。

(8)

(9)

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

實(shí)驗(yàn)首先驗(yàn)證混合相似性(Hybrid Similarity，HS)度量方法的有效性，分別將混合相似性、Pearson相關(guān)系數(shù)和余弦相似性三種方法用于基于用戶的協(xié)同過(guò)濾算法中，預(yù)測(cè)目標(biāo)用戶的評(píng)分，并計(jì)算MAE值。三種算法在7個(gè)數(shù)據(jù)集上的測(cè)試結(jié)果如圖1所示，橫坐標(biāo)為數(shù)據(jù)集名稱，縱坐標(biāo)為MAE值。通過(guò)測(cè)試結(jié)果得出本文提出的混合相似性度量方法在參數(shù)μ=0.4，α=0.3時(shí)效果最佳。在7個(gè)數(shù)據(jù)集上的預(yù)測(cè)結(jié)果均優(yōu)于傳統(tǒng)相似性度量方法。

圖1 三種算法在7個(gè)數(shù)據(jù)集上的預(yù)測(cè)結(jié)果

為驗(yàn)證權(quán)值動(dòng)態(tài)調(diào)整策略的有效性，將其與固定權(quán)值的混合算法進(jìn)行對(duì)比實(shí)驗(yàn)。固定權(quán)值的混合算法取最優(yōu)參數(shù)μ=0.4，α=0.3；動(dòng)態(tài)權(quán)值μ則依靠共同評(píng)分項(xiàng)目數(shù)和T參數(shù)調(diào)整，α同樣取0.3。實(shí)驗(yàn)結(jié)果如圖2所示，橫坐標(biāo)為T(mén)的取值情況，縱坐標(biāo)為7組數(shù)據(jù)的MAE均值。實(shí)驗(yàn)結(jié)果證明動(dòng)態(tài)混合相似性 (Dynamic Hybrid Similarity，DHS)度量方法對(duì)于預(yù)測(cè)結(jié)果的準(zhǔn)確性有較為明顯的改進(jìn)。當(dāng)T=8時(shí)，預(yù)測(cè)結(jié)果最優(yōu)。

圖2 固定權(quán)值和動(dòng)態(tài)權(quán)值的混合算法預(yù)測(cè)結(jié)果

4 結(jié)束語(yǔ)

本文針對(duì)傳統(tǒng)的協(xié)同過(guò)濾算法中相似性衡量方法過(guò)于單一，難以滿足實(shí)際推薦系統(tǒng)中處理數(shù)據(jù)量大和高稀疏性的特點(diǎn)，提出一種動(dòng)態(tài)混合相似性度量方法。該方法將用戶評(píng)分值、評(píng)分習(xí)慣和群體相似性通過(guò)加權(quán)平均的方法共同作為衡量用戶間相似性的指標(biāo)，并根據(jù)用戶共同評(píng)分?jǐn)?shù)量的多少動(dòng)態(tài)調(diào)整權(quán)重。通過(guò)在MovieLens數(shù)據(jù)集上的測(cè)試結(jié)果表明，本文提出的相似性度量方法明顯優(yōu)于傳統(tǒng)的余弦相似性和Pearson相關(guān)系數(shù)，可以有效提高協(xié)同過(guò)濾算法的推薦質(zhì)量。

[1] Choi K, Suh Y.A New Similarity Function for Selecting Neighbors for Each Target Item Incollaborative Filtering[J]. Knowledge-Based Systems, 2013,37 :146-153.

[2] Ren Y, Li G, Zhang J, et.al. The Efficient Imputation Method for Neighborhood-based Collaborative Filtering[C]// Proceedings of the 21st ACM International Conference on Information and Knowledge Management, 2012:684-693.

[3] Yang H Q, Guang L,Yu X S,et.al. Boosting Response Aware Model-Based Collaborative Filtering[J]. IEEE Transactions on Knowledge & Data Engineering, 2015,8: 2064-2077.

[4] Su X Y, Khoshgoftaar T M.A Survey of Collaborative Filtering Techniques[J]. Advances in Artificial Intelligence,2009(12)：1-19.

[5] Bell R M, Koren Y. Lessons from the Netflix Prize Challenge[J].ACM SIGKDD Explorations Newsletter,2007,9(2):75-79.

[6] Ahn H J. A New Similarity Measure for Collaborative Filtering to Alleviate the New User Cold-starting Problem[J]. Information Sciences,2008,178(1): 37-51.

[7] Konstan J A, Miller B N, Maltz D, et.al. GroupLens: Applying Collaborative Filtering to Usenet News[J].Communications of the ACM,1997, 40 (3):77-87.

[8] Resnick P, Iacovou N, Suchak M, et.al. GroupLens: an Open Architecture for Collaborative Filtering of Netnews[C]//Proceeding of the ACM Conference on Computer Supported Cooperative Work, 1994:175-186.

[9] Adomavicius G, Tuzhilin A. Toward the Next Generation of Recommender Systems: a Survey of the State-of-the-art and Possible Extensions[J].IEEE Transactions on Knowledge and Data Engineering,2005,17(6): 734-749.

[10] Liu H F, Hu Z, Mian A, et.al. A New user Similarity Model to Improve the Accuracy of Collaborative Filtering[J]. Knowledge-Based Systems,2014,56:156-166.

[11] Guo G B, Zhang J, Thalmann D. Merging Trust in Collaborative Filtering to Alleviate Data Sparsity and Cold Start[J].Knowledge-Based Systems,2014,57:57-68.

[12] Patraac B K, Launonena R, Ollikainen V,et al. A New Similarity Measure Using Bhattacharyya Coefficient for Collaborative Filtering in Sparse Data[J]. Knowledge-Based Systems,2015,82:163-177.

[責(zé)任編輯：張永軍]

Collaborative Filtering Recommendation Algorithm Based on Dynamic Hybrid Similarity Measure

WANG Zhu-ting，XIA Zhu-qing，ZHOU Yan-ling

(Department of Computer Science and Technology ,Hefei University, Hefei 230601, China)

Collaborative filtering is one of the most mature technologies used in the personalized recommendation system. The collaborative filtering algorithm based on nearest neighbor has been widely used in many commercial fields with its simple and high efficiency. The key of this approach is to find similar users or items with similarity algorithms. Then predict the score of an item that has not been rated. The traditional methods are not effective when dealing with large sparse data sets. This paper presents a new user similarity model which uses rating habits, social similarity , rating similarity and we design dynamic weight. According to the test results on the MovieLens data set, the proposed strategy can effectively improve the recommendation quality of the algorithm.

recommendation system; collaborative filtering; similarity

2016-03-18

2016-07-20

安徽省教育廳自然科學(xué)資助項(xiàng)目(KJ2016A609)、安徽省創(chuàng)新創(chuàng)業(yè)訓(xùn)練計(jì)劃項(xiàng)目(201511059266)、合肥學(xué)院科研發(fā)展基金資助項(xiàng)目(14KY11ZR)、合肥學(xué)院重點(diǎn)建設(shè)學(xué)科項(xiàng)目(2016xk05)資助。

王竹婷(1984—)，女，安徽馬鞍山人，合肥學(xué)院計(jì)算機(jī)和科學(xué)與技術(shù)系助理實(shí)驗(yàn)師；研究方向：人工智能與數(shù)據(jù)挖掘。

TP301.6

A

2096-2371(2016)04-0059-05