基于用戶聚類與項目劃分的優(yōu)化推薦算法①

申晉祥,鮑美英

(山西大同大學(xué) 計算機與網(wǎng)絡(luò)工程學(xué)院,大同 037009)

引言

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

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

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

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

1 傳統(tǒng)協(xié)同過濾推薦算法原理

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

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

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

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

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

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

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

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

2.1 問題分析及改進思路

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

2.2 改進算法的設(shè)計與實現(xiàn)

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

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

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

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

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

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

3.1 問題分析及改進思路

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

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

3.2 改進算法的設(shè)計與實現(xiàn)

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

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

具體實現(xiàn)過程如下：

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

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

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

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

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

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

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

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

4 實驗結(jié)果及分析

4.1 實驗數(shù)據(jù)

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

4.2 實驗評估標(biāo)準(zhǔn)

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

4.3 實驗結(jié)果及分析

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

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

圖2 確定聚類個數(shù)K值

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

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

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

圖3 確定近鄰個數(shù)N值

圖4 傳統(tǒng)算法與改進算法推薦效果比較

實驗表明基于用戶屬性聚類的User-based 協(xié)同過濾推薦算法在不同近鄰個數(shù)的環(huán)境下比傳統(tǒng)的Userbased 協(xié)同過濾推薦算法MAE值都小,說明改進算法能夠有效的提高推薦質(zhì)量.

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

由實驗結(jié)果可知,不同的數(shù)據(jù)集在加權(quán)系數(shù)α值增加過程中相應(yīng)的MAE值均是先減小然后再增大,且影響表現(xiàn)一致,當(dāng)α取值為0.2 時,各數(shù)據(jù)集的MAE值最低,達到最優(yōu)推薦質(zhì)量.說明綜合相似度計算中項目評分數(shù)據(jù)占的比重更高.

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

圖5 確定加權(quán)系數(shù)α 的值

表1 多種算法推薦效果對比結(jié)果表

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

5 結(jié)論

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