基于項(xiàng)目聚類和時(shí)間衰減的動(dòng)態(tài)協(xié)同過(guò)濾算法

劉 旭，李玲娟

(南京郵電大學(xué) 計(jì)算機(jī)學(xué)院，江蘇 南京 210023)

0 引 言

隨著互聯(lián)網(wǎng)的發(fā)展和進(jìn)步，人們?cè)谙硎芫W(wǎng)絡(luò) 資源極大便利的同時(shí)，也受到信息超載的困擾，推薦系統(tǒng)是解決信息過(guò)載問(wèn)題的主流方法。其中最著名的便是協(xié)同過(guò)濾推薦算法[1]。該算法有基于用戶的和基于項(xiàng)目的兩種類型，兩者都基于用戶的歷史記錄信息，前者結(jié)合與目標(biāo)用戶有類似偏好的其他用戶興趣，后者 基于項(xiàng)目間的相似性，把用戶可能感興趣的項(xiàng)目快速呈現(xiàn)。

盡管協(xié)同過(guò)濾推薦算法在個(gè)性化 推薦中有明顯的優(yōu)點(diǎn)：基于用戶行為和項(xiàng)目相似性，不需要先驗(yàn)知識(shí)，在用戶行為比較豐富的時(shí)候，推薦效果不錯(cuò)，但是有關(guān)用戶興趣隨時(shí)間變化的事實(shí)被忽略了。在基于項(xiàng)目的協(xié)同過(guò)濾算法中，計(jì)算最近鄰項(xiàng)目時(shí)，將不同時(shí)段的項(xiàng)目評(píng)分同等 對(duì)待，以致尋找到的目標(biāo)項(xiàng)目的最近鄰，有可能不是真正意義上的最近鄰居，使推薦結(jié)果存在較大偏差。另外，基于項(xiàng)目的協(xié)同過(guò)濾算法搜索目標(biāo)項(xiàng)目的最近鄰居時(shí)，需要遍歷整個(gè)項(xiàng)目空間，費(fèi)時(shí)又費(fèi)力[2]。

文中以基于項(xiàng)目的協(xié)同過(guò)濾算法為研究對(duì)象，設(shè)計(jì)了一種基于項(xiàng)目聚類和時(shí)間衰減的動(dòng)態(tài)協(xié)同過(guò)濾算法(dynamic collaborative filtering algorithm based on item clustering and time decay，ITDCF)。首先根據(jù)用戶的評(píng)分對(duì)項(xiàng)目進(jìn)行聚類，接下來(lái)在計(jì)算相似度時(shí)引入時(shí)間衰減因子反映用戶興趣的變化，在預(yù)測(cè)評(píng)分時(shí)也考慮時(shí)間衰減。最后，生成Top-N推薦列表，提高了推薦的準(zhǔn)確性和效率。

1 相關(guān)研究

1.1 協(xié)同過(guò)濾算法

協(xié)同過(guò)濾(collaborative filtering，CF)算法的基本思想是：基于過(guò)去的行為或現(xiàn)有用戶組的意見(jiàn)來(lái)預(yù)測(cè)數(shù)據(jù)，并使用與當(dāng)前用戶或當(dāng)前項(xiàng)目類似的鄰居數(shù)據(jù)來(lái)生成推薦結(jié)果[3]。該算法的輸入是用戶-項(xiàng)目評(píng)分矩陣，輸出數(shù)據(jù)一般分為兩類：當(dāng)前用戶對(duì)項(xiàng)目偏好的預(yù)測(cè)值和Top-N的推薦項(xiàng)目列表。其基本步驟包括：數(shù)據(jù)的收集與處理、生成用戶-項(xiàng)目評(píng)分矩陣、計(jì)算相似度、產(chǎn)生最近鄰、預(yù)測(cè)評(píng)分和產(chǎn)生Top-N推薦[3]。

基于用戶的協(xié)同過(guò)濾算法(UserCF)[4]的主要思想是：首先，輸入評(píng)分?jǐn)?shù)據(jù)集和當(dāng)前用戶ID，以查找出與當(dāng)前用戶有相似偏好的其他用戶，這些用戶被稱為最近鄰居；然后，利用鄰居用戶預(yù)測(cè)項(xiàng)目的評(píng)分；對(duì)所有項(xiàng)目的評(píng)分按照從大到小進(jìn)行排序，將評(píng)分居前的N個(gè)項(xiàng)目推薦給當(dāng)前用戶。

基于項(xiàng)目的協(xié)同過(guò)濾算法(ItemCF)[4]的核心思想是：首先構(gòu)建一個(gè)項(xiàng)目相似度矩陣來(lái)描述兩個(gè)項(xiàng)目之間的相似性；找出與當(dāng)前項(xiàng)目相似的k個(gè)最近鄰項(xiàng)目，然后根據(jù)k個(gè)最近鄰計(jì)算當(dāng)前用戶沒(méi)有看到的每一項(xiàng)目i的用戶評(píng)分；最后，將用戶對(duì)所有項(xiàng)目的評(píng)分從大到小排序，向當(dāng)前用戶推薦所有項(xiàng)目中得分最高的前N項(xiàng)。

盡管UserCF算法在推薦領(lǐng)域得到了廣泛的應(yīng)用，但也面臨著很多挑戰(zhàn)。像電商網(wǎng)站，一方面，項(xiàng)目的數(shù)量比較穩(wěn)定，但用戶數(shù)目更新頻率較高，當(dāng)用戶數(shù)量遠(yuǎn)大于項(xiàng)目數(shù)量時(shí)，計(jì)算用戶間的相似性將越來(lái)越耗時(shí)并占用更多內(nèi)存[5]。另一方面，基于用戶的算法生成的推薦結(jié)果可解釋性較差[6]。而ItemCF算法時(shí)間復(fù)雜度相對(duì)較低，并能根據(jù)用戶的歷史行為做出推薦解釋，可以比較容易令用戶信服。

1.2 基于項(xiàng)目的協(xié)同過(guò)濾算法

基于項(xiàng)目的協(xié)同過(guò)濾算法(ItemCF)的基本步驟是：處理數(shù)據(jù)、生成用戶-項(xiàng)目評(píng)分矩陣、計(jì)算項(xiàng)目相似度、產(chǎn)生最近鄰、預(yù)測(cè)評(píng)分和產(chǎn)生Top-N推薦。

該算法利用式(1)所示的余弦相似度計(jì)算兩個(gè)項(xiàng)目之間的相似度。

(1)

其中，N(i)是評(píng)價(jià)了項(xiàng)目i的用戶，N(j)是評(píng)價(jià)了項(xiàng)目j的用戶，|N(i)|是評(píng)價(jià)了項(xiàng)目i的用戶數(shù)，|N(j)|是評(píng)價(jià)了項(xiàng)目j的用戶數(shù)，|N(i)∩N(j)|是同時(shí)評(píng)價(jià)了項(xiàng)目i和j的用戶數(shù)。相似性的范圍為[0,1]，值越接近1，越相似。

此外，基于所獲取的k個(gè)最近鄰項(xiàng)目后，用式(2)預(yù)測(cè)當(dāng)前用戶對(duì)目標(biāo)項(xiàng)目的興趣。

(2)

其中，N(u)是用戶u評(píng)價(jià)過(guò)的項(xiàng)目集合，S(i,k)包含了和項(xiàng)目i最相似的k個(gè)項(xiàng)目，項(xiàng)目j屬于和用戶評(píng)價(jià)過(guò)的最相似的項(xiàng)目的集合，sim(i,j)是項(xiàng)目i和j的相似度，ruj是用戶u對(duì)項(xiàng)目j的興趣。根據(jù)數(shù)據(jù)集的類型，這里的ruj=1。

雖然ItemCF算法在項(xiàng)目數(shù)明顯少于用戶數(shù)的場(chǎng)合，相對(duì)于UserCF算法有一定的優(yōu)勢(shì)，但是如果項(xiàng)目過(guò)多，計(jì)算項(xiàng)目之間的相似度矩陣的代價(jià)偏高，而且算法也忽略了用戶興趣隨時(shí)間變化對(duì)推薦效果產(chǎn)生的影響[7]。

2 ITDCF算法

文中為進(jìn)一步提升ItemCF算法效率而設(shè)計(jì)的基于項(xiàng)目聚類和時(shí)間衰減的動(dòng)態(tài)協(xié)同過(guò)濾推薦算法ITDCF包括：項(xiàng)目聚類、時(shí)間加權(quán)、產(chǎn)生最近鄰、預(yù)測(cè)評(píng)分、產(chǎn)生推薦等步驟。

2.1 項(xiàng)目聚類

針對(duì)基于項(xiàng)目的協(xié)同過(guò)濾算法在尋找目標(biāo)項(xiàng)目的最近鄰居時(shí)，因需要遍歷整個(gè)項(xiàng)目空間而導(dǎo)致耗時(shí)大的問(wèn)題[7]，ITDCF算法先對(duì)項(xiàng)目進(jìn)行聚類，選擇評(píng)分?jǐn)?shù)量達(dá)到一定標(biāo)準(zhǔn)的項(xiàng)目為初始簇類中心，可以認(rèn)為這些初始中心就是最受用戶喜歡的項(xiàng)目；然后遍歷所有項(xiàng)目，計(jì)算其與初始中心的相似度，并歸入相似度最高的簇中，從而使目標(biāo)項(xiàng)目最近鄰居的計(jì)算從全局空間轉(zhuǎn)到簇內(nèi)空間，大大降低了計(jì)算量，提升推薦的時(shí)效性。

項(xiàng)目聚類的具體處理過(guò)程如下：

輸入：類簇的數(shù)目K和數(shù)據(jù)集合。

輸出：K個(gè)簇。

步驟1：選擇初始中心點(diǎn)。

根據(jù)構(gòu)建的用戶-項(xiàng)目評(píng)分矩陣R，從項(xiàng)目集合中檢索所有n個(gè)項(xiàng)目，計(jì)算每個(gè)item的評(píng)分?jǐn)?shù)量V。將所有的V值按降序排列，選擇前K個(gè)V值大的項(xiàng)目作為初始的聚類中心，得到K個(gè)聚類簇{C1,C2,…,Ck}。

步驟2：利用余弦相似度公式計(jì)算item分別到初始化聚類中心的距離。

步驟3：按照與聚類中心距離最近(相似度最高)的原則，將各個(gè)item分配到最鄰近的簇中，并記錄下item與每個(gè)聚類中心的相似度。

步驟4：算法結(jié)束，輸出聚類結(jié)果。

聚類時(shí)，以評(píng)價(jià)數(shù)量最多的K個(gè)item作為初始的聚類中心，減少了迭代次數(shù)，提高了算法效率。在這里，需要通過(guò)嘗試來(lái)確定最優(yōu)的K值。

采用余弦相似度公式，將項(xiàng)目間的相似度作為評(píng)判距離的標(biāo)準(zhǔn)，相似度越大則距離越近。采用余弦相似度公式還可以避免由于各屬性衡量單位的差異性而導(dǎo)致的“相似不相同”問(wèn)題[8]。

2.2 時(shí)間加權(quán)

考慮到用戶興趣會(huì)隨著時(shí)間而改變[9]，ITDCF算法將時(shí)間信息加入到推薦算法中，以在特定時(shí)間向用戶推薦其最感興趣的項(xiàng)目。ITDCF算法對(duì)基于項(xiàng)目的協(xié)同過(guò)濾推薦算法的改進(jìn) 有兩個(gè)方面：計(jì)算相似度時(shí)加入時(shí)間衰減因子和預(yù)測(cè)評(píng)分時(shí)加入時(shí)間衰減因子。其中時(shí)間衰減函數(shù)選擇的是艾賓浩斯曲線。

艾賓浩斯曲線是由德國(guó)心理學(xué)家艾賓浩斯發(fā)現(xiàn)的，描述了人類大腦忘記新事物的規(guī)律[10]。將之應(yīng)用到推薦系統(tǒng)上就是，用戶對(duì)越久遠(yuǎn)的項(xiàng)目越不感興趣，在向用戶進(jìn)行推薦時(shí)，將他以前看到過(guò)的項(xiàng)目進(jìn)行適當(dāng)?shù)亟禉?quán)。但是如果用戶最近又對(duì)其中一個(gè)項(xiàng)目進(jìn)行了操作，那么在推薦時(shí)就增加這類物品的權(quán)重。這樣得到的最近鄰項(xiàng)目更能符合用戶的興趣。

時(shí)間加權(quán)[11]的具體任務(wù)是：擬合艾賓浩斯曲線，編寫(xiě)加權(quán)函數(shù)。

隨著時(shí)間的變化，人的興趣會(huì)逐漸衰減，但衰減趨勢(shì)為先快后慢[12]。所以指數(shù)函數(shù)在一定程度上更符合興趣的衰減特性。擬合所依賴的帶參數(shù)指數(shù)函數(shù)為：

Wt=AeBx+CeDx

(3)

艾賓浩斯遺忘曲線的最終擬合公式為：

(4)

其中，Tui表示用戶u對(duì)項(xiàng)目i操作的時(shí)間，Tuj表示用戶u對(duì)項(xiàng)目j操作的時(shí)間，單位為min。

2.3 產(chǎn)生最近鄰

在加入時(shí)間權(quán)重后，認(rèn)為項(xiàng)目i和j相似是因?yàn)樵谕粫r(shí)間內(nèi)，二者同時(shí)被多個(gè)用戶選擇過(guò)[13]。考慮到艾賓浩斯遺忘曲線對(duì)用戶偏好的影響，用戶選擇時(shí)間間隔越短，項(xiàng)目間的相似度越高，文中采用余弦相似函數(shù)[14]來(lái)判斷兩個(gè)項(xiàng)目之間的相似度，得到計(jì)算項(xiàng)目i和j相似度的改進(jìn)公式為：

(5)

其中，N(i)是評(píng)價(jià)了項(xiàng)目i的用戶，N(j)是評(píng)價(jià)了項(xiàng)目j的用戶，|N(i)|是評(píng)價(jià)了項(xiàng)目i的用戶數(shù)，|N(j)|是評(píng)價(jià)了項(xiàng)目j的用戶數(shù)，用戶u屬于同時(shí)評(píng)價(jià)了項(xiàng)目i和項(xiàng)目j的用戶集合，新增的Wt為時(shí)間衰減函數(shù)。

因?yàn)樵谟?jì)算簇集的時(shí)候保存了每個(gè)項(xiàng)目和聚類中心的相似度，所以根據(jù)記錄直接將目標(biāo)項(xiàng)目劃分到相似度最大的類簇中；再取類簇內(nèi)與目標(biāo)項(xiàng)目最為相似的前K個(gè)項(xiàng)目作為最近鄰居。

2.4 預(yù)測(cè)評(píng)分

用戶最近的行為比用戶遠(yuǎn)期的行為更能反映用戶當(dāng)前的興趣[15]。通過(guò)項(xiàng)目相似性預(yù)測(cè)用戶對(duì)項(xiàng)目的興趣，并考慮用戶最近的行為。預(yù)測(cè)時(shí)采用如下公式：

(6)

其中，N(u)是用戶u評(píng)價(jià)過(guò)的項(xiàng)目集合，S(i,k)包含了和項(xiàng)目i最相似的k個(gè)項(xiàng)目，項(xiàng)目j屬于和用戶評(píng)價(jià)過(guò)的最相似的項(xiàng)目的集合，t0表示當(dāng)前時(shí)間，tuj代表用戶u操作項(xiàng)目j的時(shí)間；對(duì)于時(shí)間衰減參數(shù)α，不同數(shù)據(jù)集中的值是不同的[16]，用戶的興趣變化越快，值越大。

最后，根據(jù)預(yù)測(cè)評(píng)分公式和得到的K個(gè)最近鄰項(xiàng)目，預(yù)測(cè)用戶的興趣度，排序后得到Top-N推薦。

基于以上步驟，ITDCF算法的流程可歸納為圖1。

圖1 ITDCF算法的推薦流程

3 算法性能測(cè)試

3.1 實(shí)驗(yàn)數(shù)據(jù)集及劃分

MovieLens數(shù)據(jù)集[17]是研究人員廣泛使用的一種經(jīng)典數(shù)據(jù)集，用于測(cè)量推薦算法的精度。

文中主要使用U.data文件，其中用戶的評(píng)分值為1至5分，代表評(píng)價(jià)從低到高。timestamp是自1970年1月1日零點(diǎn)后到用戶提交評(píng)價(jià)的時(shí)間的秒數(shù)。

3.2 實(shí)驗(yàn)環(huán)境

文中的實(shí)驗(yàn)硬件環(huán)境如下：Windows7；intel(R)Core(TM) i5-6200U CPU @2.30 GHz 2.40 GHz；4G內(nèi)存；64位操作系統(tǒng)，基于x64的處理器。

實(shí)驗(yàn)在JetBrains PyCharm 5.0.3平臺(tái)下運(yùn)行；使用Python語(yǔ)言，環(huán)境為python3.6.3；Python包有：numpy、math、matplotlib.pyplot等。

3.3 實(shí)驗(yàn)方案

按照每個(gè)用戶選擇項(xiàng)目的時(shí)間先后對(duì)U.data的項(xiàng)目進(jìn)行排序，然后將用戶最后選擇的項(xiàng)目作為測(cè)試集，并把這之前用戶對(duì)項(xiàng)目的選擇記錄作為訓(xùn)練集。利用改進(jìn)后的算法構(gòu)建用戶興趣模型，向每個(gè)用戶推薦N個(gè)物品，并且利用準(zhǔn)確率、召回率和F1值對(duì)推薦算法的性能進(jìn)行評(píng)價(jià)。

為了檢驗(yàn)ITDCF算法的性能，文中將之與Popular算法和基于項(xiàng)目的協(xié)同過(guò)濾算法ItemCF進(jìn)行對(duì)比，其中的Popular算法是按照物品的流行度高低向用戶推薦當(dāng)天最受歡迎物品的算法。

給定時(shí)間T，項(xiàng)目i最近的流行度pi(T)可以定義為：

(7)

其中，三元組(u,i,t)表示用戶u在t時(shí)刻評(píng)價(jià)了項(xiàng)目i，Train是測(cè)試集數(shù)據(jù)集，α是時(shí)間衰減參數(shù)。

通過(guò)試驗(yàn)取最佳類簇?cái)?shù)7；設(shè)定目標(biāo)項(xiàng)目的最近鄰項(xiàng)目的閾值參數(shù)從0增加到45，增加的間隔為5；進(jìn)行10次實(shí)驗(yàn)；觀察召回率、準(zhǔn)確率和F1值的變化趨勢(shì)。

召回率為推薦列表中預(yù)測(cè)的用戶感興趣的項(xiàng)目與系統(tǒng)中用戶真喜歡的所有項(xiàng)目的百分比[18]。計(jì)算公式為：

(8)

其中，R(u,N)是給用戶u提供的長(zhǎng)度為N的推薦列表，T(u)是測(cè)試集中用戶評(píng)價(jià)過(guò)的項(xiàng)目集合。

準(zhǔn)確率為推薦列表中用戶喜歡的項(xiàng)目在所有被推薦的項(xiàng)目中所占的百分比[18]，計(jì)算公式為：

(9)

其中，R(u,N)表示算法給用戶u提供的長(zhǎng)度為N的推薦項(xiàng)目列表，T(u)為測(cè)試集中用戶喜歡的物品集合。

召回率Recall說(shuō)明了推薦列表的覆蓋性，Precision說(shuō)明了推薦列表的準(zhǔn)確率，都是衡量推薦性能的重要參數(shù)[18]。用F1值來(lái)擬合Precision與Recall，其中P為Precision，R為Recall。F1值越大，表明算法的推薦效果越好。計(jì)算公式如下：

(10)

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

Popular算法、ItemCF算法和ITDCF算法在不同推薦項(xiàng)目數(shù)N值下的準(zhǔn)確率、召回率和F1值分別如圖2至圖4所示。

圖2 MovieLens數(shù)據(jù)集上各算法在不同N值下的準(zhǔn)確率

圖3 MovieLens數(shù)據(jù)集上各算法在不同N值下的召回率

圖4 MovieLens數(shù)據(jù)集上各算法在不同N值下的F1值

由圖2可以看出，對(duì)MovieLens數(shù)據(jù)集，ITDCF算法在不同推薦項(xiàng)目數(shù)下的準(zhǔn)確率都更高，這是由于用戶的興趣隨時(shí)間而改變，在計(jì)算相似度時(shí)考慮了用戶對(duì)項(xiàng)目的遺忘，因此提高了預(yù)測(cè)項(xiàng)目評(píng)分的準(zhǔn)確性。同時(shí)可以看出選擇合適的推薦項(xiàng)目數(shù)N，可以獲得最好的推薦效果。

由圖3和圖4可以看出，ITDCF算法的召回率和F1值在整體上也比Popular、ItemCF高。

4 結(jié)束語(yǔ)

以提高推薦的準(zhǔn)確率為目標(biāo)，基于協(xié)同過(guò)濾和流行度推薦的思想，引入聚類和進(jìn)一步考慮興趣隨時(shí)間的變化因素，設(shè)計(jì)了一種基于項(xiàng)目聚類和時(shí)間衰減的動(dòng)態(tài)協(xié)同過(guò)濾推薦算法。該算法根據(jù)評(píng)分?jǐn)?shù)量選擇初始簇類中心，減少了迭代次數(shù)，并縮小了尋找目標(biāo)項(xiàng)目最近鄰的候選集；通過(guò)在基于項(xiàng)目的協(xié)同推薦算法中加入時(shí)間衰減因子提高了推薦的精度。MovieLens數(shù)據(jù)集上對(duì)ITDCF算法、Popular算法和ItemCF算法的準(zhǔn)確率、召回率和F1值的對(duì)比實(shí)驗(yàn)結(jié)果表明，ITDCF算法在推薦的準(zhǔn)確性和效率方面有所提高。