李永超, 羅 軍

?

基于用戶(hù)部分特征的協(xié)同過(guò)濾算法①

李永超, 羅 軍

(國(guó)防科技大學(xué)計(jì)算機(jī)學(xué)院, 長(zhǎng)沙 410073)

協(xié)同過(guò)濾算法作為推薦系統(tǒng)中應(yīng)用最廣泛的算法之一, 在大數(shù)據(jù)環(huán)境下面臨嚴(yán)重的數(shù)據(jù)稀疏問(wèn)題, 使得近鄰選擇的效果不佳, 直接影響了算法的推薦性能. 為了解決這一問(wèn)題, 本文提出了一種基于用戶(hù)部分特征的協(xié)同過(guò)濾算法(UPCF), 該算法首先基于評(píng)分偏差和項(xiàng)目流行度進(jìn)行矩陣缺失值填充, 隨后利用初始聚類(lèi)中心優(yōu)化的K-means算法對(duì)該填充矩陣進(jìn)行項(xiàng)目聚類(lèi), 并利用用戶(hù)在項(xiàng)目分類(lèi)下的局部特征進(jìn)行近鄰集合構(gòu)建, 最終采用基于用戶(hù)的協(xié)同過(guò)濾算法獲得推薦. 我們采用流行的MAE指標(biāo)對(duì)算法在MovieLens數(shù)據(jù)集上進(jìn)行評(píng)測(cè). 實(shí)驗(yàn)表明, 與目前流行的協(xié)同過(guò)濾算法相比, 提出的UPCF算法在沒(méi)有增加算法復(fù)雜性的前提下, 性能有近10%的提升.

項(xiàng)目流行度; 最近鄰選擇; 項(xiàng)目聚類(lèi); 協(xié)同過(guò)濾算法

1 引言

隨著互聯(lián)網(wǎng)的興起, 互聯(lián)網(wǎng)上的信息呈指數(shù)化增長(zhǎng), 人類(lèi)進(jìn)入了信息爆炸的大數(shù)據(jù)時(shí)代. 如何從浩瀚的數(shù)據(jù)信息中獲取自己感興趣的信息, 已成為人類(lèi)面臨的巨大難題. 于是無(wú)需用戶(hù)提供明確需求, 僅通過(guò)用戶(hù)歷史行為主動(dòng)幫助用戶(hù)快速有效篩選信息的推薦系統(tǒng)應(yīng)運(yùn)而生[1]. 我們?cè)诨ヂ?lián)網(wǎng)網(wǎng)站中看到的“猜你喜歡”, “大家都在看”, “看過(guò)的也看”, “你可能會(huì)感興趣”等都是推薦技術(shù)的實(shí)際應(yīng)用. 據(jù)報(bào)道, 早在2002 年, 在線(xiàn)購(gòu)物企業(yè)Amazon 總銷(xiāo)售額的20%便源自它的推薦系統(tǒng). 推薦技術(shù)在新聞?lì)I(lǐng)域更是產(chǎn)生了“今日頭條”這樣的不生產(chǎn)內(nèi)容, 僅依靠推薦引擎便擁有3.5 億注冊(cè)用戶(hù), 3500 萬(wàn)活躍用戶(hù)的新興科技媒體.

協(xié)同過(guò)濾作為推薦系統(tǒng)的主流技術(shù)之一, 主要包括基于用戶(hù)的協(xié)同過(guò)濾推薦、基于項(xiàng)目的協(xié)同過(guò)濾推薦和基于矩陣分解的協(xié)同過(guò)濾推薦[2]. 而其中基于用戶(hù)的協(xié)同過(guò)濾算法是目前在實(shí)際應(yīng)用中最為成功的算法. 該算法首先通過(guò)用戶(hù)間的共同評(píng)分項(xiàng)計(jì)算用戶(hù)間的相似度, 然后根據(jù)用戶(hù)間的相似度選擇目標(biāo)用戶(hù)的近鄰集合, 最后根據(jù)用戶(hù)近鄰集合對(duì)目標(biāo)用戶(hù)進(jìn)行推薦. 最近鄰選擇作為該算法中最關(guān)鍵的步驟, 直接決定了推薦的質(zhì)量. 然而在實(shí)際應(yīng)用中由于數(shù)據(jù)集中項(xiàng)目的維度巨大, 大多數(shù)用戶(hù)只會(huì)對(duì)極少數(shù)的項(xiàng)目進(jìn)行評(píng)價(jià), 從而導(dǎo)致用戶(hù)評(píng)分?jǐn)?shù)據(jù)的極端稀疏,不同用戶(hù)間的共同評(píng)分項(xiàng)極少,用戶(hù)間相似性計(jì)算的可靠性和準(zhǔn)確性難以得到保證, 推薦算法的效果大打折扣.

為了解決稀疏性問(wèn)題, 多種措施相繼被提出. Ungar LH等[3]首次提出基于用戶(hù)聚類(lèi)的協(xié)同過(guò)濾算法(UBCF), 通過(guò)用戶(hù)聚類(lèi)來(lái)降低最近鄰搜索的數(shù)據(jù)規(guī)模, 增加最近鄰可靠性. 黃裕洋等[4]根據(jù)評(píng)分?jǐn)?shù)據(jù)的稀疏性情況, 提出了一種動(dòng)態(tài)計(jì)算相似性的方法(HCFR). Xavier Amatriain[5]等提出在提前構(gòu)建的專(zhuān)家集合中尋找用戶(hù)近鄰集合, 以確保用戶(hù)的近鄰對(duì)待預(yù)測(cè)項(xiàng)目有過(guò)評(píng)分記錄. 黃創(chuàng)光等[6]提出了一種不確定近鄰的協(xié)同過(guò)濾推薦算法(UNCF). 該算法通過(guò)不確定近鄰因子及調(diào)和參數(shù)去計(jì)算基于用戶(hù)和產(chǎn)品的預(yù)測(cè)評(píng)分并產(chǎn)生推薦. Koren Y[7]通過(guò)將矩陣分解和最近鄰算法相結(jié)合, 大大提高了算法的推薦性能.

以上方法雖然從一定程度上減弱了數(shù)據(jù)稀疏對(duì)近鄰選擇帶來(lái)的影響, 提高了協(xié)同過(guò)濾的推薦質(zhì)量和效率, 但在最近鄰計(jì)算的過(guò)程中, 對(duì)用戶(hù)的相似性計(jì)算仍基于全局相似性, 沒(méi)有充分考慮用戶(hù)在不同項(xiàng)目類(lèi)別下的興趣差異. 正如世上沒(méi)有完全相同的兩片樹(shù)葉一樣, 在各個(gè)方面興趣都相似的用戶(hù)也難以尋找. 大多用戶(hù)可能只在某個(gè)領(lǐng)域內(nèi)興趣相仿, 在其他領(lǐng)域內(nèi)可能興趣完全相悖. 因此本文提出了一種基于用戶(hù)部分特征的協(xié)同過(guò)濾算法UPCF, 該算法首先對(duì)填充矩陣進(jìn)行項(xiàng)目聚類(lèi), 然后僅根據(jù)用戶(hù)在該項(xiàng)目分類(lèi)下的所有評(píng)價(jià)進(jìn)行相似度矩陣構(gòu)建, 降低數(shù)據(jù)維度的同時(shí)提升了最近鄰計(jì)算的可靠性, 最后根據(jù)相似性矩陣進(jìn)行近鄰集合構(gòu)建, 從而最終得到推薦結(jié)果.

2 問(wèn)題定義及基本方法

基于用戶(hù)的協(xié)同過(guò)濾算法基于以下假設(shè): 如果用戶(hù)之間對(duì)一些項(xiàng)目的評(píng)分比較相似, 則他們對(duì)其它項(xiàng)目的評(píng)分也將會(huì)比較相似. 協(xié)同過(guò)濾推薦系統(tǒng)首先搜索目標(biāo)用戶(hù)的若干近鄰, 然后根據(jù)最近鄰對(duì)項(xiàng)目的評(píng)分去預(yù)測(cè)目標(biāo)用戶(hù)對(duì)項(xiàng)目的評(píng)分, 從而產(chǎn)生推薦列表. 作為算法的輸入, 數(shù)據(jù)源=(,,), 其中={u,u,···,u}是基本用戶(hù)的集合,;{i,i,···,i}是項(xiàng)目集合,.階矩陣是用戶(hù)對(duì)各項(xiàng)目的評(píng)分矩陣, 其中的元素r表示中第個(gè)用戶(hù)對(duì)中第個(gè)項(xiàng)目的評(píng)分. 基于用戶(hù)的協(xié)同過(guò)濾算法主要包括以下三個(gè)步驟.

2.1 評(píng)分矩陣預(yù)處理

由于在實(shí)際應(yīng)用中, 項(xiàng)目集的維數(shù)很大, 用戶(hù)只能對(duì)極少數(shù)項(xiàng)目進(jìn)行評(píng)價(jià), 因此評(píng)分矩陣十分稀疏, 這對(duì)后面的相似性計(jì)算提出了很大的挑戰(zhàn). 合理的矩陣缺失值預(yù)測(cè)填充可以從一定程度上緩解稀疏性問(wèn)題.

目前常用的缺失值預(yù)測(cè)方法包括評(píng)分中值、眾數(shù)、用戶(hù)評(píng)分均值、項(xiàng)目評(píng)分均值、采用奇異值分解填補(bǔ)近鄰評(píng)分缺失值[7]以及基于近似項(xiàng)目預(yù)測(cè)評(píng)分值[8]等.

2.2 用戶(hù)近鄰集合構(gòu)建

接下來(lái), 我們?cè)陬A(yù)處理過(guò)的用戶(hù)評(píng)分矩陣上采用相似度計(jì)算方法, 計(jì)算用戶(hù)之間的相似度, 形成用戶(hù)的相似度矩陣. 協(xié)同過(guò)濾算法研究中最常用的相似度計(jì)算方法是相關(guān)相似度、余弦相似度和修正的余弦相似度, 它們的計(jì)算公式分別如下:

相關(guān)相似度:

余弦相似度:

修正的余弦相似度:

各公式中表示用戶(hù)、.r表示用戶(hù)對(duì)項(xiàng)目的評(píng)分,表示用戶(hù)的平均評(píng)分,I、I表示用戶(hù)已經(jīng)評(píng)價(jià)過(guò)的項(xiàng)目集合,I表示用戶(hù)和用戶(hù)的共同評(píng)分項(xiàng)目集合.

相似矩陣構(gòu)建結(jié)束后, 便可根據(jù)用戶(hù)指定的最近鄰篩選規(guī)則構(gòu)建近鄰集合, 常用的篩選規(guī)則包括指定近鄰數(shù)量和設(shè)置相似度閾值.

2.3 物品推薦

利用上一步計(jì)算得到的近鄰集合, 找到這個(gè)集合中的用戶(hù)喜歡且目標(biāo)用戶(hù)沒(méi)有聽(tīng)說(shuō)過(guò)的物品推薦給用戶(hù). 具體而言, 我們利用公式(4)計(jì)算用戶(hù)對(duì)指定項(xiàng)目的預(yù)測(cè)評(píng)分.

其中N為用戶(hù)的最近鄰集合, sim()為用戶(hù)、的相似度, 其余符號(hào)與前面定義一致. 最終便得到了用戶(hù)關(guān)于項(xiàng)目i的預(yù)測(cè)評(píng)分.

3 基于用戶(hù)部分特征的協(xié)同過(guò)濾算法(UPCF)

傳統(tǒng)的基于用戶(hù)的協(xié)同過(guò)濾算法在計(jì)算最近鄰的過(guò)程中使用了用戶(hù)的所有評(píng)分記錄, 考察了用戶(hù)的全局相似性. 然而在全部項(xiàng)目集上興趣都相似的用戶(hù)并不常見(jiàn), 大多用戶(hù)可能只在某一主題下興趣相似, 而在其余項(xiàng)目分類(lèi)中喜好完全不同. 因此傳統(tǒng)的近鄰集合構(gòu)建往往選擇了全局相對(duì)相似而舍棄了在某些領(lǐng)域內(nèi)興趣高度契合的用戶(hù). 為了解決這個(gè)問(wèn)題, 本文提出了一種基于用戶(hù)部分特征的協(xié)同過(guò)濾算法, 使得在最近鄰選擇時(shí)所需的相似度僅根據(jù)用戶(hù)在該項(xiàng)目所在類(lèi)內(nèi)的評(píng)價(jià)信息計(jì)算獲得. 算法詳細(xì)流程如下所示.

3.1 未評(píng)分項(xiàng)目預(yù)測(cè)填充

為了緩解在項(xiàng)目聚類(lèi)時(shí)矩陣的稀疏問(wèn)題, 我們首先對(duì)評(píng)分矩陣進(jìn)行缺失值預(yù)測(cè)填充. 考慮到熱門(mén)項(xiàng)目對(duì)用戶(hù)特征貢獻(xiàn)度不大, 以及相對(duì)冷門(mén)項(xiàng)目而言, 用戶(hù)接觸到熱門(mén)項(xiàng)目的概率大得多, 而如果用戶(hù)未對(duì)熱門(mén)項(xiàng)目進(jìn)行反饋評(píng)價(jià), 很可能是因?yàn)橛脩?hù)對(duì)該項(xiàng)目并不感興趣. 而在推薦系統(tǒng)中, 項(xiàng)目流行度是衡量項(xiàng)目熱門(mén)程度的主要指標(biāo), 它是指項(xiàng)目被用戶(hù)反饋的總次數(shù), 被反饋的次數(shù)越多代表項(xiàng)目流行度越高. 因此為了能夠從一定程度上合理懲罰未評(píng)分熱門(mén)項(xiàng)目, 我們引入了項(xiàng)目流行度權(quán)重系數(shù),在此次試驗(yàn)中, 我們采用以下公式計(jì)算項(xiàng)目流行度, 其中()表示項(xiàng)目已被評(píng)分的總次數(shù).

項(xiàng)目被評(píng)分總次數(shù)()越大則對(duì)應(yīng)權(quán)重越小, 預(yù)測(cè)評(píng)分則會(huì)相應(yīng)降低.最終我們采用如下方法進(jìn)行缺失值預(yù)測(cè)填充.

3.2 項(xiàng)目聚類(lèi)

缺失數(shù)據(jù)處理過(guò)后, 我們便可對(duì)項(xiàng)目進(jìn)行聚類(lèi), 本次我們采用聚類(lèi)算法中最經(jīng)典的K-means算法進(jìn)行項(xiàng)目聚類(lèi). 而傳統(tǒng)的K-means算法對(duì)初始聚類(lèi)中心非常敏感, 聚類(lèi)結(jié)果隨不同的初始輸入而有較大波動(dòng). 為消除這種敏感性, 本文采用袁方等提出的優(yōu)化初始聚類(lèi)中心的改進(jìn)K-means算法[9]進(jìn)行聚類(lèi)計(jì)算. 與傳統(tǒng)聚類(lèi)算法不同的是, 該算法在選取初始聚類(lèi)中心時(shí)計(jì)算每個(gè)數(shù)據(jù)對(duì)象所在區(qū)域的密度, 選擇相互距離最遠(yuǎn)的個(gè)處于高密度區(qū)域的點(diǎn)作為初始聚類(lèi)中心. 實(shí)驗(yàn)表明改進(jìn)后的K-means算法能產(chǎn)生質(zhì)量較高的聚類(lèi)結(jié)果, 并且消除了對(duì)初始輸入的敏感性.

過(guò)程1. 基于項(xiàng)目的kmeans聚類(lèi) 輸入: 聚類(lèi)數(shù)目k, 最大迭代次數(shù)iter_num和用戶(hù)評(píng)分?jǐn)?shù)據(jù)填充矩陣R輸出: k個(gè)聚類(lèi) 1) 計(jì)算以項(xiàng)目集I中每個(gè)項(xiàng)目ij為中心, 包含常數(shù)Minpts個(gè)數(shù)據(jù)對(duì)象的半徑, 記為ij的密度參數(shù). 越大, 說(shuō)明數(shù)據(jù)對(duì)象所處區(qū)域的數(shù)據(jù)密度越低. 反之則說(shuō)明數(shù)據(jù)對(duì)象所處區(qū)域的數(shù)據(jù)密度越高. 選取滿(mǎn)足的點(diǎn)ij為高密度區(qū)域D. 取D中處于最高密度區(qū)域的點(diǎn)作為第1個(gè)聚類(lèi)中心rl; 取D中距離rl最遠(yuǎn)的點(diǎn)作第2個(gè)聚類(lèi)中心r2; 計(jì)算D中各數(shù)據(jù)對(duì)象ij到rl, r2的距離d(ij, r1), d(ij, r2), r3為滿(mǎn)足max(min(d(ij, r1), d(ij, r2)),j=1,2···n的數(shù)據(jù)對(duì)象ij; rm為滿(mǎn)足max(min(d(ij, r1), d(ij, r2)...d(ij, rm-1)),j=1,2···n的數(shù)據(jù)對(duì)象ij,ij∈D. 依此得到k個(gè)初始聚類(lèi)中心. 記為集合centerold={r1, ···, rk}; 2) k個(gè)聚類(lèi)簇cluster1, ···clusterk均初始化為空, 記為集合Cluster=(cluster1, ···clusterk)3) REPEATFOR each item i in I:FOR each center rjin centerold : 計(jì)算項(xiàng)目i和聚類(lèi)中心rj的相似性; sim(i,rm)=max(sim(i,r1),sim(i,r2),···,sim(i,rk))EndforFor each clusterm in Cluster: 計(jì)算clusterm的均值, 生成新的聚類(lèi)中心cnewm. Centernew={cnew1,cnew2,···, cnewk}EndforUTILCenterold=(c1, ···ck)和Centernew=(c1, ···ck)相同或達(dá)到最大迭代次數(shù)iter_num.4) 返回Cluster.

3.3 推薦生成

為了保證預(yù)測(cè)的精確性, 避免提前引入誤差, 我們?cè)谠u(píng)分預(yù)測(cè)階段采用原始用戶(hù)評(píng)價(jià)矩陣而非填充矩陣. 并使用公式(1)計(jì)算待推薦用戶(hù)在待推薦項(xiàng)目所在類(lèi)內(nèi)與其余用戶(hù)的相似度, 構(gòu)建用戶(hù)相似性矩陣. 查找與用戶(hù)相似度最大的個(gè)最近鄰. 使用公式(4)計(jì)算用戶(hù)預(yù)測(cè)評(píng)分, 得到最終評(píng)分預(yù)測(cè)值, 算法過(guò)程如下.

過(guò)程2. 評(píng)分預(yù)測(cè) 輸入: 原始用戶(hù)評(píng)價(jià)矩陣R, 最近鄰個(gè)數(shù)n, 待預(yù)測(cè)評(píng)分用戶(hù)u, 項(xiàng)目i, 項(xiàng)目i所在聚類(lèi)簇clusterj=[il,ij,···,ip]. 輸出: 評(píng)分預(yù)測(cè)值 1) simDict={}2) For user v in U: IF v!=u: simDict[v]=sim(u,v) Endif Endfor3) Nu=sort(simDict)[:n]4)

其中, 此處,的特征向量為=(,,···,),= (,, ··· ,). sim(,)我們采用公式(1)所提供的相關(guān)相似性計(jì)算. 算法的復(fù)雜度為. 至此, 我們便可獲得指定用戶(hù)對(duì)指定項(xiàng)目的評(píng)分預(yù)測(cè)值, 為隨后的推薦提供支持.

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

本次實(shí)驗(yàn)的硬件平臺(tái)是配置Intel pentium E58003.2 GHz CPU, 4G RAM, 操作系統(tǒng)為ubuntu 14.04的個(gè)人計(jì)算機(jī), 所有程序均由python實(shí)現(xiàn).

4.1 數(shù)據(jù)集

本文采用的實(shí)驗(yàn)數(shù)據(jù)集是目前衡量推薦算法質(zhì)量常用的著名電影評(píng)分?jǐn)?shù)據(jù)集MovieLens中的100k數(shù)據(jù)集(http://grouplens.org/datasets/movielens), 該數(shù)據(jù)集由美國(guó)明尼蘇達(dá)大學(xué)GroupLens研究小組創(chuàng)建并維護(hù). 該實(shí)驗(yàn)數(shù)據(jù)集共包含930個(gè)用戶(hù)對(duì)1682部電影的100000條評(píng)價(jià)信息, 其中每個(gè)用戶(hù)至少對(duì)20部電影進(jìn)行了評(píng)分, 每個(gè)電影也都收到了用戶(hù)評(píng)論. 該數(shù)據(jù)集的稀疏性為1-100000/(943*1682) = 0.937. 數(shù)據(jù)集中用戶(hù)評(píng)分范圍是1-5, 數(shù)值越大代表用戶(hù)對(duì)該電影的興趣越大. 本次實(shí)驗(yàn)按照80%和20%的比例隨機(jī)的將數(shù)據(jù)集劃分成為訓(xùn)練集和測(cè)試集, 隨后進(jìn)行5-折交叉實(shí)驗(yàn), 取五次試驗(yàn)的平均值作為最終結(jié)果.

4.2 評(píng)價(jià)標(biāo)準(zhǔn)

平均絕對(duì)誤差MAE(mean absolute error)是目前學(xué)術(shù)研究中應(yīng)用廣泛的推薦系統(tǒng)推薦質(zhì)量評(píng)價(jià)標(biāo)準(zhǔn). 其主要通過(guò)公式(7)計(jì)算測(cè)試集中用戶(hù)實(shí)際評(píng)分和推薦算法根據(jù)訓(xùn)練集的訓(xùn)練預(yù)測(cè)值的差的絕對(duì)值均值, 平均絕對(duì)誤差MAE越小, 推薦算法的質(zhì)量越高. 其中表示測(cè)試集的數(shù)據(jù)個(gè)數(shù),p為預(yù)測(cè)評(píng)分值,r為測(cè)試集中的實(shí)際評(píng)分值.

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

我們首先研究聚類(lèi)個(gè)數(shù)對(duì)本文算法性能的影響. 實(shí)驗(yàn)結(jié)果如圖1所示, 其中橫坐標(biāo)表示聚類(lèi)個(gè)數(shù), 縱坐標(biāo)表示MAE值, 最近鄰個(gè)數(shù)統(tǒng)一取=30.

圖1 聚類(lèi)個(gè)數(shù)對(duì)MAE值的影響

通過(guò)圖1我們可以清晰看到剛開(kāi)始, 隨著聚類(lèi)族數(shù)的增多, 算法性能不斷提升, 當(dāng)項(xiàng)目聚類(lèi)個(gè)數(shù)為50時(shí), 算法取得了最好的性能, 此后聚類(lèi)族數(shù)的增多反而引起算法性能的下降. 接下來(lái), 我們通過(guò)將本文所提出算法UPCF與傳統(tǒng)的基于用戶(hù)聚類(lèi)的協(xié)同過(guò)濾算法(UBCF)[3]、綜合用戶(hù)和項(xiàng)目因素的協(xié)同過(guò)濾推薦算法(HCFR)[4]、基與不確定近鄰的協(xié)同過(guò)濾算法(UNCF)[6]的平均絕對(duì)誤差MAE進(jìn)行對(duì)比觀(guān)測(cè)試驗(yàn)性能. 為了縮短算法的運(yùn)行時(shí)間, 聚類(lèi)個(gè)數(shù)均設(shè)置為20.

圖2 算法性能比較

由圖2可以看出, 本文算法與其他算法在MAE值上有了10%左右的提高, 特別是當(dāng)近鄰個(gè)數(shù)比較少的時(shí)候, 本文算法體現(xiàn)了非常好的推薦效果, 性能優(yōu)勢(shì)明顯更好, 這充分說(shuō)明本文提出算法最近鄰選擇的高效合理性. 我們也可以觀(guān)察到, 當(dāng)最近鄰個(gè)數(shù)達(dá)到一定數(shù)量后, 所有算法的MAE性能趨于平穩(wěn), 這也反映出當(dāng)近鄰相似度不斷減小時(shí), 該近鄰對(duì)算法的性能提升沒(méi)有顯著的影響.

此外, 本文算法在提高推薦質(zhì)量的同時(shí)并沒(méi)有帶來(lái)算法復(fù)雜性的提升. 數(shù)據(jù)的預(yù)填充和項(xiàng)目聚類(lèi)均可提前離線(xiàn)完成, 僅需根據(jù)需求隔一段時(shí)間更新. 而評(píng)分預(yù)測(cè)由于不再依賴(lài)用戶(hù)全局特征, 單個(gè)評(píng)分預(yù)測(cè)的復(fù)雜性由變?yōu)? 其中表示用戶(hù)總個(gè)數(shù),表示項(xiàng)目總個(gè)數(shù),表示項(xiàng)目聚類(lèi)個(gè)數(shù). 用戶(hù)還可根據(jù)實(shí)際需求, 并行的在各個(gè)項(xiàng)目類(lèi)內(nèi)進(jìn)行用戶(hù)評(píng)分預(yù)測(cè).

5 總結(jié)

針對(duì)傳統(tǒng)協(xié)同過(guò)濾算法中最近鄰計(jì)算時(shí)所面臨的稀疏性和準(zhǔn)確性挑戰(zhàn), 本文提出了一種基于用戶(hù)部分特征的協(xié)同過(guò)濾算法. 該算法采用基于評(píng)分偏差與項(xiàng)目流行度的思想進(jìn)行缺失值填充, 并在最近鄰構(gòu)建時(shí)僅考慮用戶(hù)在該項(xiàng)目分類(lèi)下的特征, 動(dòng)態(tài)的根據(jù)待預(yù)測(cè)項(xiàng)目篩選用戶(hù)最近鄰, 從而提高了推薦的質(zhì)量. 此外, 由于僅需考慮用戶(hù)類(lèi)內(nèi)特征, 該算法實(shí)現(xiàn)了一定程度的降維, 降低了算法的復(fù)雜性. 并可根據(jù)需要, 分布并發(fā)的計(jì)算各個(gè)類(lèi)內(nèi)用戶(hù)的預(yù)測(cè)評(píng)分值, 一定程度上提高了算法的實(shí)時(shí)性.

但算法中項(xiàng)目分類(lèi)以及用戶(hù)最近鄰選擇時(shí)特征選擇的準(zhǔn)確性仍需要進(jìn)一步研究改良, 所使用的聚類(lèi)算法K-means的聚類(lèi)效果仍不是十分理想. 此外, 在此次研究前期對(duì)推薦算法的了解中, 我們發(fā)現(xiàn)目前針對(duì)各種推薦算法模型的融合以及算法并行化的研究也成為業(yè)界的新熱點(diǎn). 而能夠更好地反應(yīng)用戶(hù)興趣的用戶(hù)社交關(guān)系的引入[10,11]大大提高了協(xié)同過(guò)濾算法的近鄰可靠性和準(zhǔn)確性, 為算法的改良提供了新的方向. 如何將用戶(hù)社交關(guān)系引入本文提出的算法, 進(jìn)一步改善本文算法的性能, 將是下一階段研究的重點(diǎn).

1 Park DH, Kim HK, Choi IY, Kim JK. A literature review and classification of recommender systems research. Expert Systems with Applications, 2012, 39(11): 10059–10072.

2 Bobadilla J, Ortega F, Hernando A, Gutiérrez A. Recommender system survey. Knowledge-Based Systems. 2013, 46: 109–132.

3 Ungar LH, Foster DP. Clustering methods for collaborative filtering. AAAI Workshop on Recommendation Systems, 1998, 1: 114–129.

4黃裕洋,金遠(yuǎn)平.一種綜合用戶(hù)和項(xiàng)目因素的協(xié)同過(guò)濾推薦算法.東南大學(xué)學(xué)報(bào)(自然科學(xué)版),2010,40(5):917–921.

5 Amatriain X, Lathia N, Pujol JM, Kwak H, Oliver N. The wisdom of the few: A collaborative filtering approach based on expert opinions from the web. Proc. of the 32nd International ACM SIGIR Conference on Research and Development in Information Retrieval. ACM. 2009. 532–539.

6 黃創(chuàng)光,印鑒,汪靜,劉玉葆,王甲海.不確定近鄰的協(xié)同過(guò)濾推薦算法.計(jì)算機(jī)學(xué)報(bào),2010,33(8):1369–1377.

7 Koren Y. Factorization meets the neighborhood: A multifaceted collaborative filtering model. Proc. of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2008. 426–434.

8 鄧愛(ài)林,朱揚(yáng)勇,施伯樂(lè).基于項(xiàng)目評(píng)分預(yù)測(cè)的協(xié)同過(guò)濾推薦算法.軟件學(xué)報(bào),2003,14(9):1621–1628.

9袁方,周志勇,宋鑫.初始聚類(lèi)中心優(yōu)化的K-means算法.計(jì)算機(jī)工程,2007,33(3):65–66.

10 Daly EM, Geyer W. Effective event discovery: Using cation and social information for scoping event recommendations. Proc. of the 5th ACM Conference on Recommender Systems. ACM. 2011. 277–280.

11 Guy I. Social recommender systems. Recommender Systems Handbook. Springer US, 2015: 511–543.

Collaborative Filtering Algorithm Based on User Partial Feature

LI Yong-Chao, LUO Jun

(Department of Computer Science, National University of Defense Technology, Changsha 410073, China)

As one of the most widely used algorithms in recommender system, the traditional collaborative filtering algorithm faces serious data sparseness problem in the big data trend, which leads to the ineffective in nearest neighbor selection, and restricts the performance of the algorithm. To address this problem, this paper proposes a collaborative filtering algorithm based on user partial feature(UPCF). In our method, it first rates the missing values based on rating bias and item popularity; and then clusters the items in the filled matrix with a K-means clustering algorithm of meliorated initial center. At last, it uses the user-based collaborative filtering algorithm with the user feature in item class to get the recommendations. The MAE measures on the MovieLens dataset shows that compared with the current popular algorithms, the performance of our UPCF algorithm improves about 10% without any increase of algorithm complexity.

item popularity; nearest neighbor selection; item clustering; collaborative filtering algorithm

2016-07-01;

2016-08-31

[10.15888/j.cnki.csa.005704]