改進(jìn)的基于用戶(hù)的協(xié)同過(guò)濾算法

張世顯，李平

（長(zhǎng)春理工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，長(zhǎng)春 130022）

隨著Internet的快速發(fā)展，網(wǎng)絡(luò)上的信息每天都以PB級(jí)別增長(zhǎng)?；ヂ?lián)網(wǎng)雖然給我們的生活帶來(lái)了方便，但是信息超載和信息迷航的問(wèn)題也隨之而來(lái)［1-2］。面臨著如此巨大的數(shù)據(jù)，人們?cè)趺礃硬拍艿玫阶约合胍男畔⒛?？搜索引擎便?yīng)運(yùn)而生，它不僅能夠促進(jìn)互聯(lián)網(wǎng)的服務(wù)質(zhì)量，同時(shí)還能減少用戶(hù)的搜索耗時(shí)，排除掉大量干擾和無(wú)關(guān)信息［3］。但是當(dāng)人們?cè)趯?duì)物品沒(méi)有意愿的情況下，它并不能解決人們的需求。為了解決這一問(wèn)題，個(gè)性化推薦系統(tǒng)應(yīng)運(yùn)而生，它是一種主動(dòng)性的信息過(guò)濾方式［4-5］。推薦系統(tǒng)可以根據(jù)用戶(hù)的歷史信息，在用戶(hù)沒(méi)有需求的情況下提供精準(zhǔn)的個(gè)性化推薦，從而引導(dǎo)用戶(hù)獲取有用的信息［6］。

協(xié)同過(guò)濾算法是目前發(fā)展比較成熟的個(gè)性化推薦算法，尤其是在電子商務(wù)中取得了非常好的效果。據(jù)悉亞馬遜通過(guò)推薦算法，將其銷(xiāo)售額提升了大約30%。但是，傳統(tǒng)的協(xié)同過(guò)濾算法在計(jì)算相似度和預(yù)測(cè)評(píng)分時(shí)太過(guò)粗糙，沒(méi)有考慮到評(píng)分對(duì)共現(xiàn)值的影響以及用戶(hù)的興趣遷移對(duì)評(píng)分的影響。針對(duì)這樣的情況，本文主要提出兩點(diǎn)改進(jìn)：首先通過(guò)決策樹(shù)模型找到評(píng)分與共現(xiàn)值之間的關(guān)系，實(shí)驗(yàn)中會(huì)通過(guò)多個(gè)模型分別測(cè)試，找出最優(yōu)模型；其次引入指數(shù)時(shí)間模型來(lái)解決用戶(hù)興趣遷移問(wèn)題，提高推薦的時(shí)效性。

1 相關(guān)研究

1.1 傳統(tǒng)的協(xié)同過(guò)濾算法

協(xié)同過(guò)濾算法是推薦系統(tǒng)中運(yùn)用最為成功的信息過(guò)濾算法［7］，主要提取用戶(hù)產(chǎn)生的歷史行為做出推薦［8］。傳統(tǒng)的協(xié)同過(guò)濾算法主要分為基于物品的協(xié)同過(guò)濾算法（ItermCF）和基于用戶(hù)的協(xié)同過(guò)濾算法（UserCF）。本論文以UserCF作為研究對(duì)象，對(duì)目標(biāo)用戶(hù)首先通過(guò)相似度找到K個(gè)最近鄰，然后把K個(gè)最近鄰產(chǎn)生行為而目標(biāo)用戶(hù)沒(méi)有產(chǎn)生行為的物品，通過(guò)TOP-N的方式推薦給目標(biāo)用戶(hù)。常見(jiàn)的相似度計(jì)算方法有歐氏距離相似度方法（式（1））、余弦相似度方法（式（2））、皮爾遜相似度方法（式（3））、Salton相似度方法（式（4））等。通過(guò)TOP-N推薦的預(yù)測(cè)評(píng)分公式如式（5）所示。本論文中采用Salton相似度方法來(lái)計(jì)算用戶(hù)的最近鄰。

其中，U表示用戶(hù)集合，I表示用戶(hù)u和v共同評(píng)分過(guò)物品的集合，rui表示用戶(hù)u對(duì)物品i評(píng)分，rvi表示用戶(hù)u對(duì)物品i的評(píng)分表示用戶(hù)u的評(píng)分均值表示用戶(hù)v的評(píng)分均值。

1.2 研究現(xiàn)狀

近幾年，有很多學(xué)者對(duì)這些問(wèn)題進(jìn)行了研究和改進(jìn)，都從不同程度上改善了這個(gè)算法的推薦準(zhǔn)確性。文獻(xiàn)［9］提出了一種復(fù)合指數(shù)函數(shù)作為評(píng)分權(quán)重的時(shí)間模型，在一定程度上改善了最終評(píng)分預(yù)測(cè)的結(jié)果，但是這個(gè)模型隨著時(shí)間的增長(zhǎng)下降過(guò)快不符合人類(lèi)的興趣遺忘規(guī)律。文獻(xiàn)［10］提出了一種Logistic時(shí)間函數(shù)和用戶(hù)特征相結(jié)合的方法，改善了推薦的準(zhǔn)確度。由于這個(gè)函數(shù)值域最小在0.5，最大也不趨近于1，所以用它作為權(quán)重也不符合實(shí)際。同樣文獻(xiàn)［11］采用線(xiàn)性回歸方式作為時(shí)間模型，分別對(duì)相似度和預(yù)測(cè)評(píng)分公式進(jìn)行改進(jìn)，最終也在推薦效果上有所提升，不過(guò)根據(jù)艾賓浩斯遺忘曲線(xiàn)，顯然它也不符合。還有很多忽略用戶(hù)興趣遷移的改進(jìn)［12-14］。

與上述改進(jìn)方法不同，本文是根據(jù)艾賓浩斯遺忘曲線(xiàn)，提出一個(gè)指數(shù)時(shí)間模型，并通過(guò)權(quán)重α來(lái)控制這個(gè)模型，最后實(shí)驗(yàn)會(huì)分組驗(yàn)證這個(gè)超參數(shù)，選取一個(gè)最優(yōu)的模型作為用戶(hù)評(píng)分的權(quán)重。其次還會(huì)討論選擇怎么樣的規(guī)則方式來(lái)映射評(píng)分和共現(xiàn)值之間的關(guān)系，從而改善Salton相似度，減少預(yù)測(cè)評(píng)分的平均絕對(duì)誤差。

2 改進(jìn)的基于用戶(hù)的協(xié)同過(guò)濾算法的研究

2.1 算法的提出

2.1.1 改進(jìn)Salton相似度方法

傳統(tǒng)的協(xié)同過(guò)濾算法用式（4）所示的Salton相似度來(lái)計(jì)算目標(biāo)用戶(hù)的最近鄰，在計(jì)算最近鄰時(shí)需要構(gòu)建用戶(hù)u到用戶(hù)v的共現(xiàn)矩陣。假如數(shù)據(jù)庫(kù)中存有一張用戶(hù)看電影的評(píng)分，如表1所示。

表1 不同用戶(hù)對(duì)看過(guò)電影的評(píng)分（單位為分）

對(duì)于表1這份數(shù)據(jù)，其中數(shù)字表示用戶(hù)對(duì)電影的評(píng)分，NA表示用戶(hù)對(duì)某電影沒(méi)做評(píng)分通過(guò)Salton相似度計(jì)算各個(gè)用戶(hù)之間的相似度時(shí)，將會(huì)得到如表2所示的用戶(hù)之間的共現(xiàn)矩陣。

表2 不同用戶(hù)之間的共現(xiàn)矩陣（單位為個(gè)）

表2中數(shù)字表示的是用戶(hù)之間的共現(xiàn)值大小，NA表示相同用戶(hù)不做比較即共現(xiàn)值為空。從表1和表2之間的映射關(guān)系就可以得出：兩個(gè)用戶(hù)對(duì)某個(gè)電影無(wú)論評(píng)分多少，其共現(xiàn)值就為1。因此，這五個(gè)用戶(hù)通過(guò)Salton相似度計(jì)算得出的相似度是一樣的，也就是說(shuō)用戶(hù)u5就可以把movieC推薦給用戶(hù)u1-u4。但是根據(jù)表1可以看出u1和u5根本不存在相似性，所以用傳統(tǒng)的Salton相似度直接計(jì)算用戶(hù)之間的相似性很粗糙。為了解決這種忽略用戶(hù)態(tài)度因素來(lái)計(jì)算共現(xiàn)值的方法，本文提出了一種決策樹(shù)模型來(lái)解決上述問(wèn)題。首先分析一下表1，從表1可以看出當(dāng)|rui-rvi|＜=1，其共現(xiàn)值可以為1；當(dāng)時(shí)|rui-rvi|=2，可以分三種情況：當(dāng)rui=5、rvi=3時(shí)，其共現(xiàn)值為δ∈{0.6，0.7，0.8}；當(dāng)rui=4、rvi=2時(shí)，其共現(xiàn)值為μ∈{0.1，0.2，0.3}，當(dāng)rui=3、rvi=1時(shí)，其共現(xiàn)值為0；當(dāng)|rui-rvi|＞2時(shí)，此時(shí)這兩個(gè)用戶(hù)對(duì)某個(gè)電影的態(tài)度相差太大，其共現(xiàn)值可以認(rèn)為為0。根據(jù)上述分析，首先可以統(tǒng)計(jì)分析用戶(hù)對(duì)電影的評(píng)分值構(gòu)建簡(jiǎn)單的決策樹(shù)，其次在每一條從根節(jié)點(diǎn)到葉節(jié)點(diǎn)的路徑上創(chuàng)建一個(gè)規(guī)則。對(duì)每一條路徑，從根節(jié)點(diǎn)到葉節(jié)點(diǎn)的父節(jié)點(diǎn)的所有條件用AND邏輯運(yùn)算連接起來(lái)形成規(guī)則的條件部分（IF部分）。存放類(lèi)預(yù)測(cè)的葉節(jié)點(diǎn)形成規(guī)則的后件（THEN部分）。本論文以用戶(hù)對(duì)電影的評(píng)分為例，可以抽取IF-THEN規(guī)則如下：

Rule1：IF|u-v|＜=1 THEN C=1

Rule2：IFu=5||v=3 THEN C=δ

Rule3：IFu=4||v=2 THEN C=μ

Rule4：IF 其他THEN C=0

根據(jù)上述的IF-THEN規(guī)則，可以構(gòu)造出如圖1所示的決策樹(shù)。

圖1 用戶(hù)評(píng)分和共現(xiàn)值關(guān)系決策樹(shù)

2.1.2 改進(jìn)的時(shí)間加權(quán)的預(yù)測(cè)評(píng)分模型

傳統(tǒng)的協(xié)同過(guò)濾算法在計(jì)算用戶(hù)的預(yù)測(cè)評(píng)分時(shí)并沒(méi)有對(duì)已產(chǎn)生行為物品的歷史評(píng)分做相應(yīng)權(quán)重處理，也就是說(shuō)沒(méi)有考慮時(shí)間對(duì)用戶(hù)興趣的影響。只有當(dāng)用戶(hù)在同段時(shí)間或相近時(shí)間，才能有效的找鄰居，進(jìn)行預(yù)測(cè)評(píng)分推薦，保持推薦的時(shí)效性。舉個(gè)簡(jiǎn)單的例子，假如一個(gè)人在童年時(shí)期特別喜歡看兒童類(lèi)電影，在成長(zhǎng)過(guò)程中又很少看電影，有一天他去豆瓣看電影，豆瓣會(huì)給他推薦什么電影呢？毫無(wú)疑問(wèn)大部分集中在兒童類(lèi)電影，顯然這樣是不合理的。為了解決這個(gè)問(wèn)題，必須把時(shí)間較久的歷史行為權(quán)重調(diào)低，通過(guò)一個(gè)動(dòng)態(tài)的時(shí)間權(quán)重格式化歷史行為，使推薦結(jié)果的更能反映用戶(hù)的近期興趣，達(dá)到推薦的時(shí)效性。

事實(shí)上，人類(lèi)的遺忘規(guī)律和用戶(hù)興趣偏移規(guī)律是相似的［15］，因此時(shí)間模型可以參考遺忘函數(shù)給出。德國(guó)的著名心理學(xué)家艾賓浩斯對(duì)記憶的遺忘規(guī)律做了深入研究，并且繪制出了著名的“艾賓浩斯遺忘曲線(xiàn)”。該曲線(xiàn)展示了人類(lèi)記憶保留的非線(xiàn)性遞減的規(guī)律，本文受其啟發(fā)提出一個(gè)指數(shù)的時(shí)間模型，來(lái)反映用戶(hù)的興趣變化，此時(shí)間模型定義如下：

其中，t代表當(dāng)前時(shí)刻，tumin表示用戶(hù)u對(duì)其評(píng)價(jià)過(guò)物品的最小時(shí)間，tumax表示用戶(hù)u對(duì)其評(píng)價(jià)過(guò)物品的最大時(shí)間，（7）式中減去1是為了避免評(píng)分權(quán)重為1，α∈（0，1］表示時(shí)間權(quán)重因子，α越大說(shuō)明項(xiàng)目評(píng)分衰減速度越快，可以通過(guò)實(shí)驗(yàn)擬定一個(gè)合適的值。

將這個(gè)時(shí)間模型引入到式（5）中，以提高推薦的時(shí)效性，使推薦結(jié)果更傾向于當(dāng)前用戶(hù)的興趣。改進(jìn)后的式子如下所示：

2.2 算法的過(guò)程描述

根據(jù)上述對(duì)Salton相似度的改進(jìn)和利用時(shí)間加權(quán)對(duì)預(yù)測(cè)評(píng)分的改進(jìn)，可以總結(jié)出改進(jìn)的基于用戶(hù)的協(xié)同過(guò)濾算法（R_UserCF）過(guò)程如下：

算法 R_UserCF；

輸入 用戶(hù)集合U，物品集合I，鄰居個(gè)數(shù)K，推薦個(gè)數(shù)N，歷史行為Info；

輸出 預(yù)測(cè)評(píng)分矩陣M(U,I)。

Step1 根據(jù)Info信息得出用戶(hù)-項(xiàng)目的評(píng)分矩陣R(U,I)，再根據(jù)R(U,I)通過(guò)改進(jìn)的Salton相似度計(jì)算出用戶(hù)u和U中其他用戶(hù)的共現(xiàn)值，最后根據(jù)用戶(hù)彼此之間的共現(xiàn)值就得到了用戶(hù)-用戶(hù)的共現(xiàn)矩陣Q(U,U)；

Step2 對(duì)每一個(gè)u∈U，通過(guò)Q(U,U)和改進(jìn)的Salton相似度計(jì)算用戶(hù)u和U中其他用戶(hù)的相似度并寫(xiě)入用戶(hù)相似度矩陣similar(u,v)；

Step3 對(duì)每一個(gè)u∈U，選取出與u相似度最高的K個(gè)用戶(hù)，組成最近鄰Neighbors(u,v,K)；

Step4 選出Neighbors(u,v,K)中所有產(chǎn)生行為的物品集合Iterms(i)，并在Iterms(i)中刪除目標(biāo)用戶(hù)已經(jīng)產(chǎn)生行為物品；

Step5 對(duì)每個(gè)i∈Iterms(i)，通過(guò)最近鄰集合中的用戶(hù)i的評(píng)分，運(yùn)用公式（9）計(jì)算預(yù)測(cè)值rui，并將rui更新到M(U,I)；

Step6 返回M(U,I)，算法完成。

3 實(shí)驗(yàn)數(shù)據(jù)和結(jié)果分析

3.1 實(shí)驗(yàn)數(shù)據(jù)和評(píng)價(jià)指標(biāo)

本實(shí)驗(yàn)使用由Grouplens提供的100K的MovieLens數(shù)據(jù)集。數(shù)據(jù)集包含了10萬(wàn)條記錄，共943名用戶(hù)對(duì)1682部電影進(jìn)行5個(gè)等級(jí)的評(píng)分，評(píng)分?jǐn)?shù)值為1-5。其中1代表“poor”，5表示“perfect”，其他數(shù)據(jù)則表示中間值，他們代表了用戶(hù)對(duì)電影興趣的不同程度。在試驗(yàn)中該數(shù)據(jù)集80%作為訓(xùn)練數(shù)據(jù)集20%作為測(cè)試數(shù)據(jù)集。

預(yù)測(cè)準(zhǔn)確度是用來(lái)衡量一個(gè)推薦系統(tǒng)推薦能力的重要指標(biāo)，本論文采用平均絕對(duì)誤差（MSE）.假設(shè)原始評(píng)分集合為M={r1,r2,…,rn}，預(yù)測(cè)評(píng)分集合為N={p1,p2,…,pn}，則MAE的計(jì)算公式如下所示：

其中，N表示測(cè)試集中電影的總數(shù)。MAE的值越小，說(shuō)明預(yù)測(cè)的準(zhǔn)確率越高，產(chǎn)生的推薦效果越好，即推薦結(jié)果越準(zhǔn)確。

3.2 實(shí)驗(yàn)參數(shù)設(shè)定

3.2.1 選取最優(yōu)決策樹(shù)規(guī)則

根據(jù)前面的分析，需要對(duì)三個(gè)決策樹(shù)模型分別測(cè)試其平均絕對(duì)誤差，來(lái)選取最優(yōu)模型，此次試驗(yàn)選取N=20，K=10，試驗(yàn)結(jié)果如表3所示。

表3 不同模型及其MAE

其中A，B，C，D分別圖1中的根節(jié)點(diǎn)值，從上述表中數(shù)據(jù)MAE值可以得出第二個(gè)模型是最優(yōu)模型。

3.2.2 時(shí)間模型中的超參α

此試驗(yàn)主要驗(yàn)證時(shí)間權(quán)重因子在取何值時(shí)推薦效果達(dá)到最優(yōu)，此模型選取上述模型，試驗(yàn)結(jié)果如圖2所示。

圖2 不同α所對(duì)應(yīng)的平均絕對(duì)誤差

從上圖可以明顯的看出α為0.1時(shí)其平均絕對(duì)誤差最小，即選取此值推薦系統(tǒng)得到的推薦結(jié)果達(dá)到最優(yōu)。

3.3 實(shí)驗(yàn)對(duì)比和實(shí)驗(yàn)結(jié)果分析

通過(guò)上面對(duì)改進(jìn)基于用戶(hù)的協(xié)同過(guò)濾算法（R_UserCF）參數(shù)的優(yōu)化，已經(jīng)能夠得出一個(gè)最優(yōu)模型，下面將在不同鄰居下用這個(gè)模型和傳統(tǒng)算法（UserCF）作對(duì)比，如圖3所示。

圖3 UserCF和R_UserCF算法的比較

從圖3可以看出改進(jìn)的基于用戶(hù)的協(xié)同過(guò)濾算法在同等條件下平均絕對(duì)誤差都小于傳統(tǒng)的算法，可見(jiàn)改進(jìn)的算法在推薦中更加高效實(shí)用。

4 結(jié)論

本文在計(jì)算相似度時(shí)增加了人們的態(tài)度即通過(guò)決策樹(shù)策略得出了評(píng)分和共現(xiàn)值的關(guān)系，并且為了應(yīng)對(duì)用戶(hù)的興趣遷移問(wèn)題提出了加權(quán)的時(shí)間模型，最后通過(guò)Movielens數(shù)據(jù)集驗(yàn)證了改進(jìn)的算法在整體上都優(yōu)于傳統(tǒng)的算法。但是該算法也有兩點(diǎn)不足之處，首先在整個(gè)算法過(guò)程中涉及到很多矩陣轉(zhuǎn)換問(wèn)題以及又增加了一個(gè)時(shí)間維度，因此加大了內(nèi)存的開(kāi)銷(xiāo)，增加了計(jì)算的時(shí)間。其次數(shù)據(jù)集采用的是電影領(lǐng)域，因此該算法在應(yīng)用場(chǎng)合上有一定的局限性。接下來(lái)主要針對(duì)這兩點(diǎn)不足之處進(jìn)行改進(jìn)，嘗試加入聚類(lèi)模型以及選取多個(gè)領(lǐng)域的數(shù)據(jù)集分別進(jìn)行測(cè)試實(shí)驗(yàn)。

［1］余力，劉魯，羅章華.我國(guó)電子商務(wù)推薦策略的比較分析［J］.系統(tǒng)工程理論與實(shí)踐，2004，24（8）：96-101.

［2］顧洪博，趙萬(wàn)平.數(shù)據(jù)挖掘算法性能優(yōu)化的研究與應(yīng)用［J］.長(zhǎng)春理工大學(xué)學(xué)報(bào)：自然科學(xué)版，2010，33（1）：164-166，163.

［3］Linden G，Smith B，York J.Amazon.com Recommendations：item-to-item collaborativefiltering［J］.IEEE Internet Computing，2003（1）：76-80.

［4］邱寧佳，郭暢，楊華民，等.基于MapReduce編程模型的改進(jìn)KNN分類(lèi)算法研究［J］.長(zhǎng)春理工大學(xué)學(xué)報(bào)：自然科學(xué)版，2017，40（1）：110-114.

［5］劉建國(guó)，周濤，王秉宏.個(gè)性化推薦系統(tǒng)的研究進(jìn)展［J］.自然科學(xué)進(jìn)展，2009，19（1）：1-15.

［6］Ricci F，Rokach L，Shapira B，et al.Recommender systems handbook［M］.New York：Springer，2011.

［7］黃武漢，孟祥武，王立才.移動(dòng)通信網(wǎng)中基于用戶(hù)社會(huì)化關(guān)系挖掘的協(xié)同過(guò)濾算法［J］.電子與信息學(xué)報(bào)，2011，33（12）：3002-3007.

［8］范家兵，王鵬，周渭博，等.在推薦系統(tǒng)中利用時(shí)間因素的方法［J］.計(jì)算機(jī)應(yīng)用，2015，35（5）：1324-1327.

［9］Lai W，Deng H.An improved collaborative filtering algorithm adapting to user interest changes［C］.Information Science and Service Science and Data Mining.IEEE，2012：598-602.

［10］趙文濤，成亞飛，王春春.基于Logistic時(shí)間函數(shù)和用戶(hù)特征的協(xié)同過(guò)濾算法［J］.計(jì)算機(jī)應(yīng)用與軟件，2017，34（2）：285-289，312.

［11］鄭先榮，曹先彬.線(xiàn)性逐步遺忘協(xié)同過(guò)濾算法的研究［J］.計(jì)算機(jī)工程，2007，33（6）：72-73.

［12］Kharrat FB，Elkhleifi A，F(xiàn)aiz R.Improving collaborative filtering algorithms［C］.Proceedings of12th International Conference on Semantics，Knowledge and Grids，2016，36（5）：109-114.

［13］劉江東，梁剛，馮程，等.基于信息熵和時(shí)效性的協(xié)同過(guò)濾推薦［J］.計(jì)算機(jī)應(yīng)用，2016，36（9）：2531-2534.

［14］張佳，林耀進(jìn)，林夢(mèng)雷等.基于信息熵的協(xié)同過(guò)濾算法［J］.山東大學(xué)學(xué)報(bào)：工學(xué)版，2016，46（2）：43-50.

［15］于洪，李轉(zhuǎn)云.基于遺忘曲線(xiàn)的協(xié)同過(guò)濾算法［J］.南京大學(xué)學(xué)報(bào)：自然科學(xué)版，2010，46（5）：520-527.