基于用戶聚類與項目劃分的優化推薦算法①

申晉祥,鮑美英

(山西大同大學 計算機與網絡工程學院,大同 037009)

引言

在信息爆炸的大數據時代,互聯網中海量數據的出現使用戶想要獲取自己所需要的信息變的越來越不容易[1,2].面對大量的數據信息,如何有效改善“信息過載”問題[3,4],是目前大數據研究者的主要內容之一.比較成熟的信息過濾方法有網站導航、搜索引擎和推薦系統(Recommender Systems)[5,6],但是當用戶不能明確表達自己的需求時,前兩種方法就略顯無奈了.推薦系統正是因此而被廣泛使用的,成為現今大數據環境下一種非常有效的信息過濾手段.

推薦算法是推薦系統的核心技術[7],比較常用的有基于協同過濾推薦算法、基于內容推薦算法和混合推薦算法[8,9].其中協同過濾推薦算法因其可由已知用戶的偏好預測其可能感興趣的項目,不依賴具體項目的特征信息,對具體內容分析技術無過高要求等優點,使其在理論研究及實踐應用中有很大的發展.但該算法在大數據環境下所顯現出來的數據稀疏性、冷啟動和時效性等問題[10,11],需要對其進行有效完善.

目前國內外研究人員針對此問題提出了許多方法,以完善算法的推薦結果.丁少衡等人[12]提出基于用戶屬性和評分的協同過濾推薦算法,從用戶評分、用戶興趣變化等多個角度對相似度計算進行了改進,但因實際推薦過程中評分數據稀少使得相似度計算仍存在問題.楊尚君等人[13]提出基于AntClass 算法的協同過濾推薦方法,把用戶評分定義成數據流,采用AntClass 算法和預處理過的數據流進行融合,提高了推薦的精確度,但存在計算復雜度較高,耗時較長的問題.王穎等人[14]提出融合用戶自然最近鄰推薦算法,針對現有方法確定鄰居個數困難導致推薦準確率不高問題,通過自適應尋找自然最近鄰居集,采用融合的方法預測目標用戶評分,對推薦的準確率有所提高,但存在計算中忽略用戶和項目之間許多內在信息的問題.

基于以上研究及存在的問題,針對傳統協同過濾推薦算法沒有充分考慮用戶屬性及項目類別劃分等因素對相似度計算的影響,提出一種基于用戶屬性聚類與項目劃分的協同過濾推薦算法.算法對推薦準確度有重要影響的相似度計算進行了充分考慮,結合用戶屬性及項目類別劃分計算相似度,并且在項目最近鄰選取時采用閾值計算,提高了算法的準確度.

1 傳統協同過濾推薦算法原理

協同過濾推薦算法對用戶-項目評分矩陣的數據進行分析,根據喜好相似的用戶一般會對相同的物品有相近的喜好的原理,為用戶產生推薦.分為基于用戶的協同過濾推薦算法(user-based)和基于項目的協同過濾推薦算法(item-based).其實現過程分為三步：

(1)構建用戶-項目評分矩陣.可由m×n的評分矩陣表示,m和n分別表示用戶和項目的值,任一用戶i對任一項目j的評分用rij表示.當然,實際的評分矩陣是極稀疏的.

(2)最近鄰的選取.此步是協同過濾算法的核心,通過計算項目間或用戶間的相似度,選取與目標用戶最相似的最近鄰集合為目標用戶的最近鄰.余弦相似度及修正的余弦相似度和Pearson 相關相似度是常用的計算方法.余弦相似度計算如式(1)所示.

Pearson 相關相似度計算,以項目之間相似度計算為例如式(2)所示,用戶之間相似度計算同理.

式中,Uij表示對項目Ii和Ij同時共同評過分的用戶集,rui和ruj表示用戶u對項目Ii的評分和對項目Ij的評分,和表示全體用戶對項目Ii的評分平均值和對項目Ij的評分平均值.

(3)產生推薦結果.通過步驟(2)的計算結果,將未評分項目中的預測評分較高的N個項目作為推薦結果.

綜上所述,相似度的準確計算對推薦結果有重要影響,但傳統協同過濾算法未考慮用戶屬性聚類及項目類別劃分等因素對相似度計算的影響.為此,提出一種基于用戶聚類與項目劃分的優化推薦算法.

2 基于用戶屬性聚類的User-based 協同過濾推薦算法

2.1 問題分析及改進思路

傳統的User-based 協同過濾推薦算法中因用戶對項目的評分數據過少,以至于評分矩陣過于稀疏,使得該算法在相似度計算時精確度不高,而且過于稀疏的用戶-項目評分矩陣數據完全不能反映相似度計算的結果.針對以上問題分析提出在計算中結合用戶屬性,思路是不同的用戶之間有相似的偏好或感興趣的內容與其身份屬性有很大的關聯,比如同齡人或相同職業的用戶偏好或感興趣的內容可能更相近.具體實現首先采用K-means 聚類算法對用戶身份屬性進行類別劃分,用戶身份屬性主要包括年齡、性別、職業、專業等等,按照屬性把用戶劃分到不同的類別,然后在此聚類基礎上實現協同過濾推薦算法.

2.2 改進算法的設計與實現

利用用戶身份屬性數據進行聚類,改進算法的具體步驟如下：

(1)用戶身份屬性數據預處理.用戶身份屬性數據主要包括年齡、性別、職業、專業等.年齡定義為數值數據.性別定義為二元數據,即輸入性別數據時,可以根據實際內容對應轉化為二元數據0 和1(輸入性別：男或1).職業、專業等數據定義為標稱型數據,使用數值標號的形式進行標準化.通過以上方式完成用戶身份屬性數據的預處理工作,用戶屬性表達形式為User=(35,1,12,6),表示用戶是年齡為35 左右從事數學專業的男教師.

(2)采用K-means 聚類算法實現用戶身份屬性聚類.主要實現流程如圖1所示.算法的時間復雜度T(n)=O(n×k×t),n代表對象總數,k代表類簇的個數,t代表迭代次數.

圖1 K-means 聚類算法的流程

(3)對用戶屬性數據聚類處理后,再進一步實現User-based 協同過濾推薦算法.

3 基于項目劃分的Item-based 協同過濾推薦算法

3.1 問題分析及改進思路

傳統的Item-based 協同過濾推薦算法所分析的用戶-項目評分矩陣數據客觀存在數據過于稀疏的問題,會影響相似度計算的準確性,另外也可能存在用戶在評分過程中會因為某種特殊原因給某個項目很高分或很低分,此情況的發生也會給相似度的計算造成偏差,而相似度計算的準確性是推薦結果質量的保障.

針對以上問題分析提出在相似度計算中結合項目劃分然后再與項目評分共同計算,引入綜合相似度概念.思路是對項目進行劃分類別的預處理,預處理過程主要是對項目類別進行定義,然后再計算其相似度.這樣處理后不僅能夠對用戶-項目評分矩陣進行較好的數據填充,還能有效的提高相似度計算的準確性.項目劃分類別對于項目之間有層次關系的可以定義項目類別樹,通過計算兩個項目距離共同父節點的長度計算彼此之間的類別相似度.對于彼此之間沒有層次關系的則可進行平行劃分,需要著重關注不同類別之間的相關性對計算項目類別相似度的影響,例如男生喜歡看武俠小說,女生喜歡看愛情小說,看似不同類,但相似度卻很高.綜合相似度就是融合了評分相似度與劃分類別相似度,通過加權系數綜合計算項目相似度.另外考慮到兩個項目共同評分的用戶數越多,其相似性越高,所以在計算時要加入共同評分用戶數的因素.最后關于目標用戶最近鄰個數的確定問題,考慮到用戶數較多對近鄰個數選取的影響,采用閾值法,動態選取最近鄰,避免了固定值法的負效應.

3.2 改進算法的設計與實現

由改進思路可得,綜合相似度計算如式(3)所示.

其中,Simr(Ii,Ij)表示項目評分相似度,Simc(Ii,Ij)表示項目劃分類別相似度,α是加權系數.

具體實現過程如下：

(1)項目劃分類別相似度計算.結合如上討論,將項目劃分的類別表示為p={p1,p2,p3,…,pm},項目Ii所屬類別Pi={px,py,…},項目之間同屬的相同類別越多相似性越近,但不同類別的相關性情況也要考慮,例如男生喜歡看武俠小說,女生喜歡看愛情小說,男生和武俠小說雖然不是同一類,但彼此之間的相似度顯然比同屬于一類的武俠小說與愛情小說的相似度更高,通過分析思考定義m×m的項目類別相似性矩陣Smm,如式(4)所示.

方陣中Sij為類別pi,pj的相似度,計算方式如式(5)所示.

其中,vi表示屬于類別pi的總個數,vj表示屬于類別pj的總個數,s(pi,pj)為同屬于類別pi,pj的個數與屬于類別pi或類別pj的個數的比值,項目劃分類別相似度計算如式(6)所示.

式(6)表示項目Ii所屬的類別Pi與項目Ij所屬的類別Pj,兩者沒有共同類別時,計算結果值為項目Ii與項目Ij分別所屬類別之間的相似度的最大值.

(2)考慮項目共同評分用戶數對相似度的影響,改進評分相似度計算.對傳統Pearson 相似度計算公式(2)結合共同評分用戶數,融入相似度計算如式(7)所示.

式中,Ui∩Uj是指對項目Ii和Ij共同評過分的用戶總數,Ui∪Uj是指對項目Ii或Ij所有評過分的用戶總數.

(3)確定最近鄰.采用綜合相似度計算公式分別計算目標項目Ii與其它所有項目的綜合相似度值Sim(Ii,Ij)(1≤j≤n,其中j≠i),結果進行排序并選取最相似的前K個項目為目標項目Ii的最近鄰居集合,顯然K值的選取直接影響推薦結果的質量.結合如上討論,采用項目相似性鄰居選取閾值β動態選取最近鄰,考慮平均相似度因素,得到最近鄰算法如式(8)所示.

確定最近鄰時選取與目標項目Ii的相似度大于平均相似度與β之和的項目為目標項目Ii的最近鄰居集合.

4 實驗結果及分析

4.1 實驗數據

本實驗使用GroupLens 提供的MovieLens 電影評分數據集,數據中有用戶特征信息、電影屬性信息、用戶對電影的評分信息等.評分數據的范圍是從1 到5 的整數,電影劃分為19(0-18)個不同類別.實驗采用1 MB 的數據集,其中包括6040 個用戶對3900 部電影的1000 209 條評分數據.

4.2 實驗評估標準

本實驗通過平均絕對偏差(MAE)值來評估推薦算法質量,MAE值越小,說明預測值和真實值之間的誤差越小,預測的準確度越高,推薦質量越優.用N表示實驗測試項目數,Pi表示預測評分值,Ri表示實際評分值,MAE的計算如式(9)所示.

4.3 實驗結果及分析

為了驗證提出的基于用戶聚類與項目劃分的協同過濾推薦算法的有效性,通過以下實驗驗證.

(1)基于用戶屬性聚類的User-based 協同過濾推薦算法,改進后是否能夠提高推薦質量,聚類個數K值及最近鄰居個數都需要通過實驗確定.實驗采用1 MB 的數據集,以MAE值作為推薦算法質量的衡量標準,確定K值實驗結果如圖2所示.

圖2 確定聚類個數K值

可以看出,K值的確定對推薦算法的推薦質量有直接影響,K值過小或過大都會引起MAE值的升高,也就是誤差增大.當K=25 時,推薦效果最優,平均絕對偏差MAE值最小.為了進一步確定最近鄰居個數,分別使用不同的K值比較最近鄰居個數和MAE值的大小,確定近鄰N值實驗結果如圖3所示.

實驗可得,近鄰個數的逐漸增加使平均絕對偏差MAE值先減小又逐漸增大.不同的K值和近鄰個數相比較可以看出當K取值為25 且近鄰個數為30 時,MAE值最低,推薦質量效果最好.

由以上實驗結論可進一步實驗驗證改進算法和傳統的User-based 協同過濾推薦算法的推薦結果比較,通過以上分析近鄰個數N值的不同會直接影響算法結果,所以實驗通過近鄰個數N的不同取值比較兩種算法的推薦效果,比較結果如圖4所示.

圖3 確定近鄰個數N值

圖4 傳統算法與改進算法推薦效果比較

實驗表明基于用戶屬性聚類的User-based 協同過濾推薦算法在不同近鄰個數的環境下比傳統的Userbased 協同過濾推薦算法MAE值都小,說明改進算法能夠有效的提高推薦質量.

(2)基于項目劃分的User-based 協同過濾推薦算法,改進后的算法采用綜合相似度的計算方法計算項目相似度,通過實驗確定系數α的權值,實驗結果如圖5.

由實驗結果可知,不同的數據集在加權系數α值增加過程中相應的MAE值均是先減小然后再增大,且影響表現一致,當α取值為0.2 時,各數據集的MAE值最低,達到最優推薦質量.說明綜合相似度計算中項目評分數據占的比重更高.

(3)將基于用戶屬性聚類與項目劃分的協同過濾推薦算法(即改進算法)與傳統的協同過濾推薦算法(CFRA),并同時選取文獻[8,15,16]提出的算法(分別簡寫為SCCF、CRF、UCSP)通過實驗與本文所提出的算法進行比較,各算法的推薦效果對比實驗結果見表1.

圖5 確定加權系數α 的值

表1 多種算法推薦效果對比結果表

對比結果可知,與其他算法相比,因本文提出的改進算法對推薦準確度有重要影響的相似度計算進行了充分考慮,結合用戶屬性及項目類別劃分計算相似度,并且在項目最近鄰選取時采用閾值計算,因此MAE的值均最小,有效提高推薦精度,能為用戶推薦更準確的項目.

5 結論

提出一種基于用戶屬性聚類與項目劃分的協同過濾推薦算法,實驗結果證明,所提算法能夠有效提高推薦精度,為用戶提供更加準確和優質的推薦項目.下一步將結合用戶興趣變化以及社交數據等因素對推薦算法完善進行研究.