申晉祥,鮑美英

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

引言

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

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

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

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

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

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

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

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

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

式中,Uij表示對(duì)項(xiàng)目Ii和Ij同時(shí)共同評(píng)過(guò)分的用戶(hù)集,rui和ruj表示用戶(hù)u對(duì)項(xiàng)目Ii的評(píng)分和對(duì)項(xiàng)目Ij的評(píng)分,和表示全體用戶(hù)對(duì)項(xiàng)目Ii的評(píng)分平均值和對(duì)項(xiàng)目Ij的評(píng)分平均值.

(3)產(chǎn)生推薦結(jié)果.通過(guò)步驟(2)的計(jì)算結(jié)果,將未評(píng)分項(xiàng)目中的預(yù)測(cè)評(píng)分較高的N個(gè)項(xiàng)目作為推薦結(jié)果.

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

2 基于用戶(hù)屬性聚類(lèi)的User-based 協(xié)同過(guò)濾推薦算法

2.1 問(wèn)題分析及改進(jìn)思路

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

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

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

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

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

圖1 K-means 聚類(lèi)算法的流程

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

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

3.1 問(wèn)題分析及改進(jìn)思路

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

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

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

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

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

具體實(shí)現(xiàn)過(guò)程如下：

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

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

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

式(6)表示項(xiàng)目Ii所屬的類(lèi)別Pi與項(xiàng)目Ij所屬的類(lèi)別Pj,兩者沒(méi)有共同類(lèi)別時(shí),計(jì)算結(jié)果值為項(xiàng)目Ii與項(xiàng)目Ij分別所屬類(lèi)別之間的相似度的最大值.

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

式中,Ui∩Uj是指對(duì)項(xiàng)目Ii和Ij共同評(píng)過(guò)分的用戶(hù)總數(shù),Ui∪Uj是指對(duì)項(xiàng)目Ii或Ij所有評(píng)過(guò)分的用戶(hù)總數(shù).

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

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

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

4.1 實(shí)驗(yàn)數(shù)據(jù)

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

4.2 實(shí)驗(yàn)評(píng)估標(biāo)準(zhǔn)

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

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

為了驗(yàn)證提出的基于用戶(hù)聚類(lèi)與項(xiàng)目劃分的協(xié)同過(guò)濾推薦算法的有效性,通過(guò)以下實(shí)驗(yàn)驗(yàn)證.

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

圖2 確定聚類(lèi)個(gè)數(shù)K值

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)論

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