修正評分的協同過濾算法

賈俊杰,余欽科

1(西北師范大學 計算機科學與工程學院,蘭州 730070)2(西北師范大學,蘭州 730070)

1 引 言

隨著互聯網行業(yè)邁入大數據時代,網絡為人們提供了海量的信息資源,極大程度地滿足了用戶對各類信息的需求.帶來巨大便利的同時,網絡信息過載問題也變得日益突出,用戶在海量信息中找到自身所需信息的需求變得更為迫切.

在這樣的背景下,信息推薦技術[1]作為信息過濾的有效手段,逐漸成為計算機學術和應用領域的熱門研究對象,在互聯網系統(tǒng)中被廣泛地使用.推薦系統(tǒng)針對在用戶沒有明確的需求場景的情況下,通過采集用戶歷史信息和商品的特性,分析其中的關聯特性,推測用戶對潛在物品的個性化偏好情況,進而向用戶推薦最優(yōu)選擇,幫助用戶選擇所需要的商品,在極大方便網站用戶的同時,也有效提高了網站的運營效果和服務質量.

在眾多推薦技術中,協同過濾算法[2]是當前應用較為成熟的一項技術.協同過濾算法認為有近似選擇偏好的用戶一般可能會喜歡相同的物品,具體可以分為基于用戶的、基于項目的、基于模型的三類協同過濾算法[3].協同過濾算法的優(yōu)點首先是能夠過濾那些表達復雜的描述型內容,從而解決了難以進行自動內容分析信息過濾問題,另外還具有推薦新信息的功能.然而,協同過濾算法在數據量不斷增大的情況下也有其問題和局限性,典型的就是評分矩陣稀疏性問題和冷啟動問題[4]圍繞這些問題,近年來學術界進行不斷深入研究,提出了很多有效的改進方案.

本文為提高個性化推薦算法推薦過程的推薦精度以及改良協同過濾推薦算法矩陣稀疏性問題,選擇用戶聚類解決矩陣稀疏性問題.為了提高個性化推薦質量的目的下.本文算法先計算出聚類組中目標用戶和其他用戶之間的皮爾斯相關系數[1],設定閾值過濾掉弱相關的記錄生成推薦組.當推薦組中用戶再次發(fā)生購買行為,算法計算推薦組中目標用戶與其他用戶加權評分及置信度,用修正評分衡量推薦結果.經過實驗,結果表明該方法可以提高推薦的精確度.

2 協同過濾算法

協同過濾算法根據用戶-項目評分矩陣中已有的購買權重,利用用戶間或項目間的相關關系預測評分矩陣中缺失的評分,然后根據評分的高低衡量用戶對項目的偏好程度.其中最近鄰查詢的協同過濾算法是最基礎部分,聚類查詢是在最近鄰查詢的基礎上采用聚類尋找最近鄰來達到降低搜索空間,下面介紹最近鄰查詢和聚類查詢.

假設推薦系統(tǒng)中有m個用戶,用戶集合表示U{u1,u2,u3,…,um},購買商品集合表示為I{i1,i2,i3,…,in},用戶—商品之間的權重矩陣為rm*n,rij(i

表1 用戶-商品權重矩陣Table 1 User-commodity weight matrix

2.1 最近鄰查詢

基于鄰近關系的協同過濾推薦算法可分為基于用戶的協同過濾(User-based CF,UCF)算法和基于項目的協同過濾(Item-based CF,ICF)算法[5].前者的基本思想是,從用戶的行為和偏好中發(fā)現規(guī)律,并基于此給予推薦,相似的用戶有相似的行為偏好,因此向目標用戶推薦項目時,UCF算法查找與目標用戶最相似的用戶集,根據不同行為反映用戶喜好的程度將它們進行加權,得到用戶對于物品的總體喜好.為預測目標用戶的偏好程度,首先要找到用戶的相似鄰居集,計算用戶間相似度是協同過濾算法的關鍵.常用的相似性度量方法有余弦相似度[6]、Pearson 相關系數[7]和修正的余弦相似度[8].由于余弦相似度忽略了不同用戶之間的不同評分標準,學者們又提出了修正的余弦相似度計算方法,將用戶評分減去該用戶的平均評分之后,再進行相似度的計算,計算方法如公式(1):

(1)

再通過相似度計算得到目標用戶的最近鄰居集NN,通過公式(2)預測用戶u對商品Ii的加權評分pu,i.

(2)

根據上述方法預測目標用戶u對未評分項目的評分,并選取評分的前N個項目,將其推薦給目標用戶u.

2.2 聚類查詢

傳統(tǒng)基于鄰近關系的協同算法在進行推薦時,在所有用戶中查找與目標用戶最相似的 k 個用戶,算法的推薦效率隨著系統(tǒng)用戶數量的增加而降低,時間復雜度隨之升高.為此Sarwar等人提出基于用戶聚類的協同過濾算法[9],算法將推薦系統(tǒng)的中的所有用戶劃分為多個不相交的集合{Ui|∪Ui=U;∩=Ui=φ;i=1,2,…,l} 使得每個集合內用戶的關聯相似度盡可能高,而集合間的用戶的相似度盡可能低.僅需在目標用戶所屬的集合中采用基于用戶的協同過濾算法進行推薦,此舉縮小了用戶的查找范圍,提高了推薦系統(tǒng)的效率,時間復雜度降低.

2.3 傳統(tǒng)算法不足分析

1)在用戶數據量增大時,基于最近鄰查詢搜索空間巨大,時間復雜度增加,矩陣稀疏,影響推薦精度.

2)聚類查詢降低了最近鄰查詢的時間復雜度,但同樣遺留了推薦精度不足問題,傳統(tǒng)算法考慮了用戶與用戶之間的關聯,卻忽略商品與商品關聯,加權評分只考慮用戶與用戶間關聯,導致推薦精度不夠.

3)為保證推薦精度,推薦算法應考慮商品與商品的關聯,本文引入關聯規(guī)則中置信度概念.采用修正評分衡量推薦結果.

3 修正評分的協同過濾算法

為解決傳統(tǒng)推薦算法矩陣稀疏、推薦精度不足、用戶異常值問題,本文提出結合聚類和關聯規(guī)則協同過濾算法,采用修正評分代替加權評分衡量推薦結果.本文算法將用戶-商品購買記錄的商品權重作為原始數據,把整個推薦過程分為以下幾個步驟:

1)數據預處理:對用戶的商品數據字符重編碼,并對應用戶的商品權重.

2)用戶聚類:利用k-means聚類對用戶購買行為數據進行聚類,得到用戶聚類組.

表2 預處理后的數據
Table 2 Preprocessed data

用戶品牌分類權重系數u1a1b2c4542u2a3b1c9321u3a3b1c9112u4a1b2c4515u5a7b5c6355u6a3b1c9314u7a1b2c4313u8a1b2c4241u9a7b5c6142u10a7b5c6453u11a1b2c4552u12a3b1c9345u13a3b1c9541u14a7b5c6122u15a1b2c4524

3)協同過濾,計算聚類組中目標用戶和其他用戶之間的相關系數,構建推薦組.

4)考慮商品—商品的關聯,推薦組中計算目標用戶對商品的加權評分以及商品—商品的置信度,用新的衡量指標:修正評分,對商品進行推薦.

5)產生推薦結果:對商品修正評分降序排列推薦給目標用戶.

3.1 數據預處理

用戶-商品數據按字符格式重編碼,字母u組合不同數字表示不同用戶.字母a、b、c表示商品不同類別,組合不同數字表示該類別下不同商品,預處理后數據如表2所示.

3.2 聚類

對用戶-商品數據進行k-means[2]多維聚類,將用戶分為不同的聚類組.表3為聚類后的數據集,預處理后的數據聚類為3個組,品牌分類有3列表示3個維度用a、b、c表示.聚類組如表3所示.

表3 用戶聚類組
Table 3 U ser cluster group

聚類組1用戶品牌分類權重系數u1a1b2c4542u4a1b2c4515u7a1b2c4313u8a1b2c4241u11a1b2c4552u15a1b2c4524聚類組2用戶品牌分類權重系數u2a3b1c9321u3a3b1c9112u6a3b1c9314u12a3b1c9345u13a3b1c9541聚類組3用戶品牌分類權重系數u5a7b5c6355u9a7b5c6142u10a7b5c6453u14a7b5c6122

3.3 協同過濾

為對目標用戶做推薦預測,需對聚類后用戶更精細篩選構建推薦組.由此需對目標用戶協同過濾找到用戶的相似鄰居集.用戶間相似性的計算就成了協同過濾算法的關鍵之一.常用的相似性度量方法有余弦相似度、Pearson 相關系數和修正的余弦相似度.考慮到本文協同過濾需考慮用戶-商品數據權值,本文采用Pearson 相關系數對用戶協同過濾.皮爾斯相關系數如公式(3)所示:

(3)

其中:ui和uj表示的是兩個不同的用戶,Sui,Suj是ui和uj的樣品標準偏差.uii和uji表示用戶ui和uj對商品ii的購買權重.

表3中聚類組1經協同過濾后所產生推薦組如表4所示.

表4 用戶推薦組
Table 4 User recommendation group

用戶品牌分類權重系數u1a1b2c4542u4a1b2c4515u8a1b2c4241u11a1b2c4552u15a1b2c4524

3.4 商品組間關聯

傳統(tǒng)算法由于只考慮了用戶間關聯而忽略商品間關聯,考慮到商品組間的關聯,本文采用關聯規(guī)則中的置信度來衡量推薦算法中商品之間的關聯作用.

I{i1,i2,i3,…,in}是一個項目集合.T{t1,t2,t3,…,tn} 是一個事務集合每一個事務是用戶購買商品記錄.

由于本文用戶數據在經過聚類和協同過濾后,所構建的用戶推薦組中出現以目標用戶商品事務集頻繁的頻繁項集.例:目標用戶商品事務集為T{t1,t2,t3,t4},推薦組中會出現事務集合為T{t1,t2,t3,t4}的頻繁項集.所以本文不需要采用算法求取頻繁項集.

(4)

公式(4)中,mun(X)表示項目X的支持計數,數值為X在T出現的次數.

3.5 修正評分

傳統(tǒng)協同過濾算法采用加權評分對用戶進行產品推薦,但加權評分沒有考慮商品組間的關聯,當推薦組中用戶購買商品出現異常值,例如:用戶u1購買商品a1權重特別大,即使推薦組中其他用戶沒有購買a1商品,也會使a1加權評分靠前,導致推薦.加權評分無法解決異常值問題,考慮上述問題,本文結合置信度和加權評分提出修正評分,當推薦組中個別用戶再次出現某商品的異常值,該商品的置信度很小,置信度和加權評分的疊加使該商品修正評分靠后,不會被推薦.同時當推薦組中不存在異常值,加權評分相近,置信度修正推薦優(yōu)先級.經實驗驗證修正評分可以更好的衡量推薦結果.

用戶集合表示U{u1,u2,u3,…,um},用戶商品集合表示為I{i1,i2,i3,…,in},用戶商品權重集合R{r11,r12,r13,…,rmn}.

如矩陣I和R所示,I為用戶—商品記錄矩陣,0表示無購買記錄,1表示有購買記錄.R為用戶—商品權值矩陣,數字表示購買權值.

定義2.修正評分:修正評分作為商品推薦最終指標,表示為推薦組中除目標用戶外其他用戶對某商品的加權評分乘以推薦組中該商品組間置信度.置信度基于商品記錄矩陣I計算,表示某商品可能被購買的概率,衡量加權評分可信度.兩者相乘為修正評分,公式為(5):

(5)

rec(ii)表示目標用戶和推薦組中其他用戶對商品ii的修正評分.p(ui,uj) 表示用戶ui與uj的皮爾斯相關系數,ui為目標用戶,uj為推薦組中其他用戶,rji表示用戶uj對商品ii的購買權重.X為不包含商品ii的商品集合,Y為X∪ii的商品集合.目標用戶ui和商品ii無關聯,ui是用戶組中第i個用戶,ii為商品組中第i件商品,如果用戶ui購買商品組中第i件商品,對應權重則為rii,如表1所示.

3.6 產生推薦

產生推薦過程由表5所示.

表5 推薦結果
Table 5 Recommendation results

相關系數u1u4u8u11u150.8570.7090.9120.851商品權重a1b2c4d1e1u1552413推薦值d1e1基于聚類17.6913.47本文算法10.7112.04

表5中目標用戶u15購買e1商品權重高于d1,基于聚類的協同過濾算法優(yōu)先推薦d1,本文算法優(yōu)先推薦e1,可看出本文算法中采用修正評分衡量推薦結果更優(yōu)于基于聚類協同過濾算法采用加權評分衡量推薦結果.

3.7 算法描述

本算法包括用戶聚類、協同過濾、生成推薦三個步驟.

1)用戶聚類

輸入:用戶集合U{u1,u2,u3,…,um}數據.

輸出:用戶聚類組U′ 、U″ 、U″′.

處理流程:

a)用戶-商品數據重編碼,采用聚類算法進行聚類,得到不同的用戶聚類組U′ 、U″ 、U″′.

2)協同過濾

輸入:用戶聚類組U′

處理流程:

a)確定皮爾斯相關系數p(ui,uj)閾值為p′.

3)生成推薦

輸出:商品推薦序列I′{…ii…in…}.

處理流程:

b)結合矩陣I和R計算目標用戶ui和推薦組中其他用戶對商品中I{i1,i2,i3,…,in} 可能被推薦商品的修正評分rec(…ii…in…).

c)按修正評分rec(…ii…in…)降序排序得到商品推薦序列I′{…ii…in…}進行商品推薦.

4 實驗分析

為提高實驗說服力,本文實驗數據來自明尼蘇達大學 GroupLens 研究小組通過MovieLens 網站收集的MovieLens100K 數據集[10],該數據集包含了 943 位用戶對1682 部電影的 100000 條 1～5 的評分數據,每位用戶至少對 20 部電影進行了評分.數據預處理后將數據隨機分為兩個部分,80%歸為訓練集,20%歸為測試集.

實驗采用平均絕對誤差(Mean Absolute Error,MAE)[11]和時間復雜度兩種評價指標來度量算法的推薦質量.MAE 是一種常用的用于衡量統(tǒng)計的準確性和比較的度量方法,能夠準確地反應推薦質量的好壞.它用來衡量預測的用戶偏好與實際用戶偏好之間的誤差,MAE 值越小,推薦準確度越高,假設系統(tǒng)預測的用戶興趣集合為(p1,p2,…,pn),用戶的實際興趣集合為(q1,q2,…,qn)計算方法如公式(6):

(6)

時間復雜度是推薦系統(tǒng)為目標用戶推薦其感興趣項目所需要的時間,算法運營時間越短,時間復雜度越低,效果越好.

相關系數選擇為測試目標用戶與其他用戶形成推薦組時,隨相關系數閾值的不同,MAE值得變化.相關系數取值范圍為0.3～0.9.實驗如圖1所示為MAE值隨著皮爾遜相關系數的變化.

圖1 MAE值隨pearson相關系數變化Fig.1 MAE value varies with pearson correlation coefficient

圖1描述MAE值的變化曲線,初始MAE值隨pearson相關系數的增大而降低,當pearson相關系數為0.6時MAE值達到最小,隨之增大,所以本文的pearson相關系數選擇為0.6.

實驗對比了在用戶數量逐漸增加時,基于用戶的協同過濾算法[12]和基于logistic用戶特征[13]以及本文算法的平均絕對誤差(MAE)值的變化,同時通過三種算法時間復雜度的比較來確定算法的優(yōu)越性.

圖2 不同用戶數量下的MAE值的變化Fig.2 Changes in MAE values for different user numbers

圖2描述了三種推薦算法隨著用戶數量的變化,MAE值的變化情況,三種算法都是隨著用戶數量的逐漸增加MAE值逐漸降低M至趨于穩(wěn)定.由圖知本文算法在MAE上優(yōu)于上述兩種算法.

圖3 不同用戶數量下的時間復雜度變化Fig.3 Time complexity changes under different user numbers

圖3可知隨著用戶數量的逐漸增加三種推薦算法的運行時間也隨之增加,當用戶數量少三種算法的運行時間沒有明顯差距.當用戶數量逐漸增加時本文算法在算法運行時間上優(yōu)于上述兩種算法.

綜上實驗結果表明,新算法相較文獻[12]算法和文獻[13]算法具有明顯的優(yōu)勢,特別是樣本的數量增大后新算法的絕對平均誤差 MAE 值同等較小,時間復雜度同等較低.

5 結束語

推薦系統(tǒng)作為一個熱門的研究領域,本文從降低數據維度和減少計算量以及推薦的準確性考慮,提出修正評分的協同過濾算法,算法先對用戶聚類提高矩陣搜索空間效率,降低時間復雜度.修正評分代替加權評分解決異常值問題,提高推薦算法的準確性.該推薦算法因數據的特殊性,在數據預處理階段需要按照本文要求處理數據并對原始數據重編碼,降低推薦算法的計算量的同時也增加了預處理階段的工作量.下一步考慮的是如何更好的對原始數據進行統(tǒng)一編碼,減少預處理過程的計算量.