王竹婷

(合肥學院　計算機科學與技術系，合肥　230601)

?

關聯(lián)規(guī)則評分預測的協(xié)同過濾推薦算法

王竹婷

(合肥學院計算機科學與技術系，合肥230601)

摘要：協(xié)同過濾算法是目前應用于電子商務個性化推薦系統(tǒng)中的一種最成功的推薦算法。為緩解因數(shù)據(jù)稀疏性問題導致的算法推薦質(zhì)量下降，將關聯(lián)規(guī)則分析引入?yún)f(xié)同過濾算法中，預測部分未評分項目的評分值，再運用傳統(tǒng)的基于用戶的協(xié)同過濾算法實施推薦。實驗結果表明：與傳統(tǒng)的協(xié)同過濾算法相比，采用關聯(lián)規(guī)則預測評分可以一定程度提高算法推薦質(zhì)量。

隨著計算機網(wǎng)絡技術和電子商務的深入發(fā)展，個性化推薦系統(tǒng)在電子商務領域發(fā)揮的作用日益凸顯。該系統(tǒng)能夠記錄并分析用戶的網(wǎng)上行為，挖掘出用戶感興趣的商品項目，并將商品快速推薦給相應的用戶，同時提高電子商務網(wǎng)站產(chǎn)品的銷售量。而協(xié)同過濾算法作為目前應用最為成功的推薦算法之一，已廣泛應用于各類電子商務網(wǎng)站中。

協(xié)同過濾算法又分基于用戶的協(xié)同過濾[1](user_based CF)和基于項目的協(xié)同過濾[2](item_based CF)兩大類。前者通過用戶共同評分過的項目評分值計算不同用戶之間的相似程度，生成與目標用戶相似度較高的近鄰用戶集合，利用近鄰用戶對某一項目的評分值預測目標用戶的評分值；后者則利用同一用戶評分過的不同項目評分值計算項目之間的相似程度，再通過目標用戶已評分項目預測未評分項目。協(xié)同過濾無需對推薦項目進行內(nèi)容分析，直接通過用戶對項目的歷史評分數(shù)據(jù)就可以實施推薦，并可較好的實現(xiàn)跨類別項目的推薦。但隨著在線用戶規(guī)模和項目數(shù)量的劇增，傳統(tǒng)的協(xié)同過濾算法已無法適應新形勢下的需求，其中由于數(shù)據(jù)的稀疏性而導致的推薦質(zhì)量下降的問題日益突出。

為解決因數(shù)據(jù)稀疏性導致計算精度下降的問題，一些學者提出了基于協(xié)同過濾的填充算法[3]，最簡單的是利用用戶評分域中間值填充未評分項目，或采用某一用戶已有的平均評分填充未評分項目，再進行協(xié)同過濾推薦。這些方法一定程度上提高了協(xié)同過濾算法計算的精確度，但這種利用中間值或均值填充沒有考慮到用戶對不同項目的興趣差異。鄧愛林等人先利用基于項目的協(xié)同過濾算法預測出所有未評分項目的評分值，再利用基于用戶的協(xié)同過濾方法進行推薦[4]，這種算法的效果雖好于均值填充，但也存在大量數(shù)據(jù)預測偏差。

本文將提出一種關聯(lián)規(guī)則與協(xié)同過濾相結合的混合算法。首先，計算每一個項目的支持度和項目之間的置信度，以置信度為權重，根據(jù)用戶已評分項目值預測部分受歡迎程度較高且未評分項目的評分值填充到用戶項目矩陣中，再利用基于用戶的協(xié)同過濾算法，計算用戶間的相似度，選擇近鄰用戶實施項目推薦。

1傳統(tǒng)的基于用戶的協(xié)同過濾算法

基于用戶的協(xié)同過濾算法是基于這樣的推薦思想，如果不同的用戶對于某些項目具有共同的興趣愛好，那么他們對于其他的項目也應該具有相似的興趣愛好。該算法首先根據(jù)用戶之間共同擁有的項目評分情況計算出用戶之間的相似程度，根據(jù)用戶間的相似度尋找近鄰用戶，再通過近鄰用戶對某一項目的評分值預測目標用戶未評分項目，選擇評分值高的推薦給目標用戶。因此，在基于用戶的協(xié)同過濾算法中，用戶之間的相似度計算方法是非常重要的。

1.1傳統(tǒng)的用戶相似性度量方法

用戶間的相似性度量方法主要分為三種：余弦相似性、修正的余弦相似性、Pearson相關系數(shù)，其中Pearson相關系數(shù)被實驗證明是效果最好的一種計算相似性的方法[5]，下文將作重點介紹。

針對一個有m個用戶和n個項目的推薦問題，可以用一個m*n列的矩陣R表示用戶評分數(shù)據(jù)，如表1所示，矩陣中第i行第j列個元素Rij表示用戶i對項目j的評分值。

表1　用戶-項目評分矩陣

基于用戶的協(xié)同過濾算法首先要通過用戶評分數(shù)據(jù)計算用戶之間的相似度，如用戶i和用戶a之間的相似度用sim(i,a)表示。Pearson相關系數(shù)計算公式如公式(1)所示，Iui和Iua分別為用戶i和用戶a評分過的項目，Iui∩Iua表示用戶i和a共同評分過的項目，Ri表示用戶i的平均評分值，該公式通過統(tǒng)計用戶之間共同評分項目的評分差異確定他們的相似性。

(1)

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

計算Pearson相關系數(shù)，首先要尋找兩兩用戶之間共同評分過的項目。針對公式(1)不難發(fā)現(xiàn)，Pearson相關系數(shù)計算公式，在用戶共同評分項目較多，評分值比較相似的時候，計算出的相似程度較高；當用戶間評分差異較大時，計算得出的相似程度較低，能夠從一定程度上反映用戶之間興趣愛好的相似與否。但在實際應用中，推薦系統(tǒng)所處理的數(shù)據(jù)是極端稀疏的，某一個用戶的評分項目往往不超過項目總數(shù)的1%，兩兩用戶共同評分過的項目就更加稀少，采用Pearson相關系數(shù)計算用戶相似度會造成較大的誤差。比如，某兩個用戶，他們的興趣可以完全不相同，只有一到二個項目是共同評分過的，而且評分值非常接近，利用公式(1)計算相似度，那么這兩個用戶的相似度值可能接近于1，計算結果表示該兩名用戶屬于近鄰用戶，在這個基礎上進行推薦，推薦效果并不理想。

為降低因共同評分項目過少而帶來的負面因素，有學者提出在計算用戶相似度時先統(tǒng)計共同評分項目數(shù)，當共同評分的項目數(shù)過低時認為兩者的相似度為0，或加入懲罰因子，適當降低相似度值。這種方法可以一定程度上提高相似度值的可信賴程度，但可能導致整體近鄰用戶減少而降低預測的準確性。本文利用不同項目之間的相關性和用戶已有評分值預測出部分未評分項目評分值填充致稀疏矩陣，再通過基于用戶的協(xié)同過濾算法進行推薦，提出了一種基于關聯(lián)規(guī)則評分預測的協(xié)同過濾算法。

2基于關聯(lián)規(guī)則評分預測的協(xié)同過濾算法

關聯(lián)規(guī)則是數(shù)據(jù)挖掘領域研究的一項重要技術，可以挖掘出不同類別的項集之間的關聯(lián)關系[6]。在個性化推薦系統(tǒng)中，傳統(tǒng)的關聯(lián)規(guī)則挖掘通過計算項集的支持度和置信度，找出滿足最小支持度和置信度的強關聯(lián)規(guī)則集合，并以此為依據(jù)幫助用戶根據(jù)其已經(jīng)購買過的項目預測其可能喜歡的項目。

關聯(lián)規(guī)則挖掘最早應用于零售業(yè)，用于發(fā)現(xiàn)不同商品在銷售過程中的相關性，取得了較好的效果，也是個性化推薦技術中的重要方法之一。但是，由于其在處理大規(guī)模數(shù)據(jù)時，產(chǎn)生了大量的冗余規(guī)則，嚴重影響了算法的執(zhí)行效率，而且關聯(lián)規(guī)則只能挖掘出用戶偏愛的項目，無法預測評分值。本文則利用關聯(lián)規(guī)則分別挖掘一階和二階頻繁項集，再以二階頻繁項集的置信度為權值和用戶已選項目的評分值加權平均預測出部分未評分項目值，改善用戶評分數(shù)據(jù)的稀疏性，利用填充后的評分數(shù)據(jù)計算用戶相似性，根據(jù)近鄰用戶的相似性進行推薦。

2.1關聯(lián)規(guī)則的相關概念

對于一個有n個的不同項目的集合I={I1,I2,…,In},其中Ii表示編號為i的項目，多個項目的集合成為項集，k階項集則表示一個包含k個項目的集合。在推薦問題中，可以將每一位用戶曾經(jīng)購買過所有項目的集合作為一個事物T，每一個事物T是項集I的一個子集，所有m個用戶購買過的事物集合構成交易數(shù)據(jù)庫D。本文將利用交易數(shù)據(jù)庫D，使用強關聯(lián)規(guī)則挖掘出項目與項目之間的關聯(lián)程度。

支持度反映的是某一個或多個項集在數(shù)據(jù)庫D中同時出現(xiàn)的概率，例如項集A和項集B的支持度可以用P(A∪B)表示；置信度反映的是兩個項集之間相關聯(lián)的程度，例如項集A對項集B的支持度可以用P(B|A)表示，即項集A出現(xiàn)時同時項集B也出現(xiàn)的概率。

support(A?B)=P(A∪B)

(2)

confidence(A?B)=P(A|B)

(3)

設關聯(lián)規(guī)則的最小支持度和最小置信度分別為sup_min和conf_min。當規(guī)則R的支持度和可信度均不小于sup_min和conf_min，則稱為強關聯(lián)規(guī)則。關聯(lián)規(guī)則挖掘的目的就是找出滿足強關聯(lián)規(guī)則的集合，從而指導商家的決策。

2.2關聯(lián)規(guī)則評分預測

前面分析過傳統(tǒng)的Pearson相關系數(shù)度量方法在計算用戶相似度時由于用戶評分數(shù)據(jù)的極端稀疏導致計算精度下降。因為計算Pearson相關系數(shù)需要搜集用戶共同評分過的項目，不同的用戶之間共同評分的項目越多計算的準確率相對越高，但由于某一位用戶的實際購買能力是有限的，導致實際應用過程中絕大多數(shù)用戶之間共同評分的項目非常稀少。但用戶未購買不代表該項目用戶不喜歡，尤其對于一些用戶購買頻率較高的項目，其被新用戶的接受的可能性較大的，所以對這些項目進行評分預測是很有必要的。

為提高算法的執(zhí)行效率，本文不對所有滿足強關聯(lián)規(guī)則的項集進行挖掘，只挖掘到二階頻繁項集。首先，計算所有一階項目的支持度，選擇大于最小支持度閾值的一階頻繁項集，再在一階頻繁項集的基礎上尋找滿足最小支持度和置信度的二階頻繁項集。以二階頻繁項集的置信度為權值，利用用戶已有的評分項目預測出那些支持度較高但未被用戶購買過的項目評分值。

(4)

2.3基于關聯(lián)規(guī)則預測評分的協(xié)同過濾推薦

利用強關聯(lián)規(guī)則預測出的部分項目評分值填充至用戶_項目評分矩陣，再利用公式(1)計算出用戶與用戶之間的相似程度，根據(jù)用戶間的相似程度產(chǎn)生用戶a的最近鄰居集合NBua，通過用戶a的最近鄰居對項目i的評分預測用戶a對項目i的評分值Pai，計算方法如公式(5)所示。

(5)

3實驗仿真

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

本文采用MovieLens站點公開提供的標準數(shù)據(jù)集對傳統(tǒng)的基于用戶、基于項目的協(xié)同過濾算法和本文所提出的算法分別進行測試。筆者從中選取5組數(shù)據(jù)，每組數(shù)據(jù)分訓練集和測試集，其中訓練集中包括943名用戶對1 682部電影的100,000項評分數(shù)據(jù)；評分值的取值范圍為1-5；每位用戶至少有20個評分項。實驗通過訓練集數(shù)據(jù)預測測試集中用戶對項目的評分值，推薦效果越優(yōu)秀。

3.2度量標準

實驗以平均絕對偏差MAE為判斷算法的推薦質(zhì)量的標準，其計算方法如公式(6)所示，pij是通過訓練集產(chǎn)生的預測評分，qij是測試集提供的的實際評分，Ni是測試集所提供的用戶i的評分項目數(shù)量，MAEi是用戶i對Ni個項目預測評分的平均絕對偏差，公式(7)中M是全體用戶總數(shù)，MAE則是全體用戶的平均絕對偏差。從公式中不難看出，MAE的值越小，算法預測的結果與實際評分值越接近，算法推薦的準確性越高。

(6)

(7)

3.3實驗結果

實驗中選用的5組數(shù)據(jù)訓練集中都有80 000條評分記錄，用戶_項目評分矩陣的數(shù)據(jù)密度為5.04%。利用三種算法的預測結果和測試集中的實際數(shù)據(jù)分別計算MAE值，如圖1所示，圖中縱坐標為算法衡量標準MAE值，橫坐標為MovieLens提供的5組數(shù)據(jù)集的名稱。實驗結果證明，本文所提出的改進協(xié)同過濾算法MAE值最小，推薦質(zhì)量最優(yōu)。

圖1　三種協(xié)同過濾算法測試結果比較

4結論

針對傳統(tǒng)協(xié)同過濾算法因數(shù)據(jù)稀疏性而導致的推薦質(zhì)量下降問題，提出了一種基于關聯(lián)規(guī)則評分預測算法，利用項目之間的相關性和用戶已評分項目值預測部分受歡迎程度較高的未評分項填充至稀疏矩陣，再基于用戶的協(xié)同過濾進行推薦，實驗測試結果表明，本文提出的改進算法其推薦質(zhì)量優(yōu)于傳統(tǒng)的協(xié)同過濾算法。

參考文獻：

[1]HerlokcerJ L, KOnstan J A,Borhcesr A,et al. An Algorithmic Framework for Performing Collaborative Filtering[C]//Porceedings of ACM SIGIR,ACM Press,1999:230-237.

[2]Sarwar B,Karypis G,Konstan J, et al.Item-Based Collaborative Filtering Recommendation Algorithms[C]//Proceedings of the 10th International World Wide Web Conference,2001:285-295.

[3]Breese J,Hecherman D,Kadie C.Empirical Analysis of Predictive Algorithms for Collaborative Filtering[C]//Proceedings of the 14th Conference on Uncertainty in Artificial Intelligence,1998:43-52.

[4]鄧愛林,朱揚勇,施伯樂.基于項目評分預測的協(xié)同過濾推薦算法[J].軟件學報，2003.14(9):1621-1628.

[5]Herlocker L J,Konstan A J,Riedl T J.Empirical Analysis of Design Choices in Neighborhood-based Collaborative Filtering Algorithms[J].Information Retrieval,2002,5(4):287-310.

[6]李杰，徐勇，王云峰，等.面向個性化推薦的強關聯(lián)規(guī)則挖掘[J].系統(tǒng)工程理論與實踐，2009,29(8):144-152.

[責任編輯：張永軍]

Collaborative Filtering Recommendation Algorithm Based on Association Rule Score Prediction

WANG Zhu-ting

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

Abstract:Collaborative filtering algorithm is one of the most successful recommendation algorithms applied to the personalized recommendation system of E-commerce.In order to alleviate the problem of the algorithm recommendation quality decline that caused by the data sparse,the association rule analysis is introduced into the collaborative filtering algorithm,which predicts the item ratings of the non rating items,and then uses the traditional user_based collaborative filtering algorithm to implement the recommendation.The experimental results show that compared with the traditional collaborative filtering algorithm,the algorithm uses association rules to predict the item ratings can improve the recommended quality.

Key words:recommendation system;collaborative filtering;association rules

中圖分類號：TP301.6

文獻標識碼：A

文章編號：1673-162X(2016)01-0065-05

作者簡介：王竹婷(1984—)，女，安徽馬鞍山人，合肥學院計算機科學與技術系助理實驗師，碩士；研究方向：人工智能、數(shù)據(jù)挖掘。

基金項目：合肥學院2014年度科研發(fā)展基金一般項目(14KY11ZR)資助。

收稿日期：2015-07-01修回日期：2015-12-12

關鍵字：推薦系統(tǒng)；協(xié)同過濾；關聯(lián)規(guī)則