王子政 姚衛(wèi)東(北京信息控制研究所,北京 100048)
一種改進(jìn)的組合推薦算法研究
王子政姚衛(wèi)東
(北京信息控制研究所,北京100048)
推薦系統(tǒng)是解決目前信息過(guò)載問(wèn)題的有效工具和方法,而在各種推薦算法中,協(xié)同過(guò)濾推薦算法的應(yīng)用最為廣泛。但是,基于協(xié)同過(guò)濾的推薦算法存在稀疏矩陣的問(wèn)題,即:當(dāng)矩陣過(guò)于稀疏時(shí),其推薦結(jié)果誤差較大。針對(duì)這一問(wèn)題,提出了一種基于內(nèi)容和協(xié)同過(guò)濾的組合推薦算法,并通過(guò)實(shí)驗(yàn)的方式與傳統(tǒng)的協(xié)同過(guò)濾推薦算法進(jìn)行了比較。實(shí)驗(yàn)數(shù)據(jù)表明,這種組合推薦算法具有較高的效率。
推薦系統(tǒng),協(xié)同過(guò)濾,內(nèi)容,組合推薦
隨著互聯(lián)網(wǎng)及信息技術(shù)的飛速發(fā)展,信息過(guò)載問(wèn)題越來(lái)越突出,獲取有用信息變得越來(lái)越困難。為了能夠準(zhǔn)確地找到所需的信息,人們需要付出更多的時(shí)間和精力。而推薦系統(tǒng)的出現(xiàn),有效地緩解了這一問(wèn)題?;谟脩舻膮f(xié)同過(guò)濾推薦算法在推薦系統(tǒng)中應(yīng)用最為廣泛,這種推薦算法基于用戶—項(xiàng)目(user-item)矩陣進(jìn)行計(jì)算,但是其前提是用戶項(xiàng)目矩陣能夠提供足夠的信息。對(duì)于稀疏矩陣,采用這種推薦算法則會(huì)造成推薦質(zhì)量下降、推薦結(jié)果誤差較大等問(wèn)題。
本文針對(duì)協(xié)同過(guò)濾推薦算法中存在的矩陣稀疏的問(wèn)題,提出了一種基于內(nèi)容和協(xié)同過(guò)濾的組合推薦算法,并將其與現(xiàn)有的協(xié)同過(guò)濾推薦算法進(jìn)行了比較,以驗(yàn)證該組合推薦算法的可行性。
本文將基于內(nèi)容和協(xié)同過(guò)濾的組合推薦算法分為降低矩陣稀疏度模塊,以及TopN鄰居推薦模塊等兩個(gè)子模塊單獨(dú)進(jìn)行討論。
(1)降低矩陣稀疏度模塊:為了降低矩陣的稀疏程度,合理增加用戶—項(xiàng)目矩陣中的非零值,采用基于項(xiàng)目的協(xié)同過(guò)濾推薦算法,將未評(píng)價(jià)項(xiàng)目的評(píng)分值計(jì)算出來(lái),填充到用戶—項(xiàng)目矩陣中。
(2)相似鄰居推薦模塊:采用基于用戶的協(xié)同過(guò)濾推薦算法,將用戶的喜好信息預(yù)測(cè)出來(lái),對(duì)項(xiàng)目的預(yù)測(cè)值進(jìn)行排序,選取TopN個(gè)資源,形成推薦集合。
1.1降低矩陣稀疏度子模塊算法流程設(shè)計(jì)
為了降低矩陣的稀疏度,同時(shí)增強(qiáng)其稠密性,直觀上必須增加用戶對(duì)項(xiàng)目的評(píng)價(jià)信息,但是在用戶—項(xiàng)目評(píng)分矩陣中可以利用的歷史信息是非常有限的。在評(píng)分矩陣中,歷史數(shù)據(jù)越豐富,利用協(xié)同過(guò)濾推薦算法進(jìn)行計(jì)算的結(jié)果就越精確,推薦效果也就越好。在有限的評(píng)分信息條件下,本文提出了采用基于項(xiàng)目的協(xié)同過(guò)濾推薦算法來(lái)增強(qiáng)矩陣稠密性的方法。算法過(guò)程設(shè)計(jì)如下:
輸入(INPUT):用戶—項(xiàng)目矩陣Rm×n,待推薦項(xiàng)目數(shù)量NI,鄰居個(gè)數(shù)N。
輸出(OUTPUT):一個(gè)稀疏程度降低的用戶—項(xiàng)目矩陣R’m×n。
運(yùn)算流程(PROCESS):對(duì)于每個(gè)未被所有用戶評(píng)價(jià)過(guò)的項(xiàng)目i,都執(zhí)行下面的操作:(1)首先計(jì)算項(xiàng)目i與其它項(xiàng)目之間的相似度,并選出與其相似度最高的前N個(gè)項(xiàng)目作為其鄰居項(xiàng)目。(2)根據(jù)項(xiàng)目i已經(jīng)存在的用戶評(píng)分信息,利用(1)中得到的N個(gè)鄰居項(xiàng)目信息,對(duì)i中的評(píng)分信息進(jìn)行計(jì)算預(yù)測(cè)。按照預(yù)測(cè)值大小進(jìn)行排序,選擇前NI個(gè)項(xiàng)目值作為其推薦評(píng)價(jià)集合。(3)將(2)中得到的項(xiàng)目預(yù)測(cè)值填入原用戶—項(xiàng)目矩陣Rm×n中,形成一個(gè)新的用戶—項(xiàng)目矩陣R’m×n。至此,完成降低矩陣稀疏程度子模塊算法的設(shè)計(jì)。
1.2相似鄰居推薦子模塊算法流程設(shè)計(jì)
經(jīng)過(guò)降低矩陣的稀疏程度處理之后,得到一個(gè)更加稠密的用戶—項(xiàng)目矩陣R’m×n。在此之上,采用基于用戶的協(xié)同過(guò)濾推薦算法,對(duì)于m個(gè)用戶中的每個(gè)用戶,產(chǎn)生其相應(yīng)的推薦結(jié)果集合。算法設(shè)計(jì)如下:
輸入(INPUT):一個(gè)經(jīng)過(guò)降低稀疏處理之后的矩陣R’m×n,鄰居用戶數(shù)量UN,推薦項(xiàng)目的數(shù)量IN。
輸出(OUTPUT):推薦項(xiàng)目的集合RS。
運(yùn)算過(guò)程(PROCESS):對(duì)于每個(gè)被推薦的目標(biāo)用戶u,都執(zhí)行以下操作:(1)計(jì)算目標(biāo)用戶u與其它用戶之間的相似度,并選擇與其相似度最高的前UN個(gè)作為其相似鄰居用戶。(2)根據(jù)用戶u已經(jīng)存在的評(píng)價(jià)信息和(1)中得到的相似鄰居用戶信息,對(duì)未評(píng)價(jià)過(guò)的項(xiàng)目進(jìn)行預(yù)測(cè)。(3)對(duì)所有未評(píng)價(jià)過(guò)的項(xiàng)目的預(yù)測(cè)評(píng)分值進(jìn)行排序,選取評(píng)分值最高的前IN個(gè)項(xiàng)目進(jìn)行形成用戶u的推薦集合。至此,完成TopN鄰居推薦子模塊算法的設(shè)計(jì)。
1.3算法整體流程設(shè)計(jì)
以上對(duì)推薦算法模塊的兩個(gè)子模塊進(jìn)行了分析和設(shè)計(jì),下面介紹組合推薦算法的整體思路和步驟。按照算法設(shè)計(jì)的總體思路及其運(yùn)行步驟,從算法的輸入、輸出和運(yùn)算流程等三個(gè)方面進(jìn)行介紹。
算法具體流程如下:
輸入(INPUT):(1)用戶—項(xiàng)目矩陣Rm×n,其中包含m個(gè)用戶、n個(gè)項(xiàng)目,矩陣中每個(gè)元素ri, j表示用戶i對(duì)項(xiàng)目j的評(píng)分信息;(2)用戶相似性閾值Usim;(3)項(xiàng)目相似性閾值Isim;(4)矩陣極大稀疏度NP;(4)矩陣可計(jì)算稀疏度MP(NP>MP);(5)鄰居數(shù)目閾值NH;(6)推薦項(xiàng)目數(shù)量N;(7)預(yù)測(cè)評(píng)分閾值RV。
輸出(OUTPUT):RS。
2.1實(shí)驗(yàn)數(shù)據(jù)與評(píng)價(jià)標(biāo)準(zhǔn)
實(shí)驗(yàn)數(shù)據(jù)采用明尼蘇達(dá)大學(xué)公開(kāi)的數(shù)據(jù)集,此數(shù)據(jù)集由GroupLens項(xiàng)目組負(fù)責(zé)收集整理,可以從互聯(lián)網(wǎng)站http:// grouplens.org/datasets/movielens/下載。網(wǎng)站中提供了不同大小的數(shù)據(jù)集合,為了實(shí)驗(yàn)方便,下載了100kB的數(shù)據(jù)集并進(jìn)行算法的驗(yàn)證。在100kB的數(shù)據(jù)集合中包含943個(gè)用戶、1682個(gè)項(xiàng)目(電影)。在不影響實(shí)驗(yàn)結(jié)果的前提下,為了計(jì)算方便,從全部數(shù)據(jù)集中選取78720條記錄作為所有實(shí)驗(yàn)的數(shù)據(jù)集,其中包含400個(gè)用戶和1361個(gè)項(xiàng)目(電影),也即在用戶—項(xiàng)目評(píng)分矩陣Rm×n中,m=400,n=1361。矩陣Rm×n的稀疏度Sparsity=1-78720÷(400×1361)=0.8554。
在評(píng)價(jià)推薦系統(tǒng)的準(zhǔn)確度時(shí),有關(guān)文獻(xiàn)提出,用平均絕對(duì)偏差(Mean Absolute Error,MAE)來(lái)衡量推薦系統(tǒng)的預(yù)測(cè)值與實(shí)際值之間的偏差。MAE是一個(gè)在統(tǒng)計(jì)領(lǐng)域經(jīng)常使用的準(zhǔn)確性評(píng)價(jià)指標(biāo),其核心思想就是計(jì)算預(yù)測(cè)值與實(shí)際值之間的偏差,偏差值越小則說(shuō)明實(shí)驗(yàn)值與實(shí)際值之間的差距越小,也就說(shuō)明實(shí)驗(yàn)值更加接近實(shí)際值,實(shí)驗(yàn)算法的效率更高。MAE的計(jì)算由下式定義:
其中,pi表示預(yù)測(cè)值,qi表示實(shí)際評(píng)分值。N代表預(yù)測(cè)項(xiàng)目的個(gè)數(shù)。
2.2實(shí)驗(yàn)過(guò)程與結(jié)果分析
為了驗(yàn)證本文設(shè)計(jì)的組合推薦算法的推薦效果,對(duì)各種算法進(jìn)行了對(duì)比。本實(shí)驗(yàn)中,分別對(duì)比了“改進(jìn)的組合推薦算法”、“基于用戶的協(xié)同過(guò)濾推薦算法”、“基于項(xiàng)目的協(xié)同過(guò)濾推薦算法”等三種算法的MAE值大小,以對(duì)推薦算法的有效性進(jìn)行驗(yàn)證。為了消除稀疏程度對(duì)推薦結(jié)果的影響,本文選取實(shí)驗(yàn)集中75%的數(shù)據(jù)進(jìn)行預(yù)測(cè)計(jì)算,剩余的25%留作與預(yù)測(cè)結(jié)果結(jié)合計(jì)算平均絕對(duì)偏差MAE。實(shí)驗(yàn)結(jié)果如圖1所示。
圖1 改進(jìn)的組合推薦算法與傳統(tǒng)協(xié)同過(guò)濾推薦算法比對(duì)
從圖1中可以看到,無(wú)論鄰居數(shù)目如何變化,“改進(jìn)的組合推薦算法”都較傳統(tǒng)的協(xié)同過(guò)濾推薦算法具有更優(yōu)的推薦準(zhǔn)確度,從算法思路上來(lái)看,對(duì)于稀疏程度極大的矩陣,并不直接使用基于協(xié)同過(guò)濾的推薦算法,而是采用基于內(nèi)容的推薦算法,此時(shí)由于矩陣的稀疏度較大,相應(yīng)的記錄較少,在使用基于內(nèi)容的推薦算法時(shí)能夠獲得更高的推薦效率。另外,對(duì)于稀疏的矩陣,采用了基于項(xiàng)目的協(xié)同過(guò)濾推薦算法,首先進(jìn)行了降低稀疏度處理,增強(qiáng)矩陣的稠密度,以便能夠使用協(xié)同過(guò)濾推薦算法進(jìn)行預(yù)測(cè)計(jì)算。
本文中提出的基于內(nèi)容和協(xié)調(diào)過(guò)濾的組合推薦算法在一定程度上綜合了兩種算法的優(yōu)點(diǎn),發(fā)揮了各自的優(yōu)勢(shì),降低了矩陣的稀疏程度,提高了推薦質(zhì)量。與傳統(tǒng)的、單一的推薦算法相比,該組合推薦算法的推薦質(zhì)量明顯提升。
1Bawden D, Holtham C, Courtney N. Courtney N. Perspectives on information overload[J]. Aslib Proceedings, 1999,51(8): 249
2Schafer J B,Konstan J A, Riedl J. E-Commerce Recommendation Applications[J]. Data Mining and Knowledge Discovery, 2001, 5(1~2): 115~153
3Jonathan L., Herlocker, JosePh A, et al. Evaluating Collaborative Filtering Recommender Systems[J]. ACM Transactionson InformationSystems, 2004, 22(1): 5~53
4張丙奇. 基于領(lǐng)域知識(shí)的個(gè)性化推薦算法研究[J]. 計(jì)算機(jī)工程, 2005, 31(21): 7~9
1009-8119(2015)12(1)-0046-02