結(jié)合貢獻(xiàn)度與時(shí)間權(quán)重的協(xié)同過(guò)濾推薦算法

賈俊康，李玲娟

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

0 引 言

隨著互聯(lián)網(wǎng)和信息技術(shù)的普及，人類(lèi)全面進(jìn)入web2.0時(shí)代以后，就面臨著“信息超載”[1]問(wèn)題，用戶(hù)想要從海量數(shù)據(jù)中篩選出滿(mǎn)意的結(jié)果變得愈加艱難。因此，作為信息過(guò)濾工具的推薦系統(tǒng)應(yīng)運(yùn)而生，它能夠根據(jù)用戶(hù)的需求，快速、準(zhǔn)確地向用戶(hù)進(jìn)行有效推薦。推薦算法作為推薦系統(tǒng)的核心[2]，直接決定了推薦效果。主流推薦算法包括基于內(nèi)容的推薦、協(xié)同過(guò)濾推薦和混合推薦三類(lèi)傳統(tǒng)的推薦算法，以及各種與深度學(xué)習(xí)結(jié)合的推薦算法[3-4]。其中，協(xié)同過(guò)濾推薦算法是應(yīng)用最為成功的推薦算法之一[5]。它又分為兩類(lèi)，一類(lèi)是基于模型的協(xié)同過(guò)濾，另一類(lèi)是基于內(nèi)存的協(xié)同過(guò)濾。后者又有基于用戶(hù)的協(xié)同過(guò)濾UserCF和基于項(xiàng)目的協(xié)同過(guò)濾ItemCF之分[3]。UserCF源于生活中的經(jīng)驗(yàn)假設(shè)：興趣愛(ài)好類(lèi)似的用戶(hù)，他們對(duì)同一項(xiàng)目可能有著相似的喜好程度[6]，這種算法不是分析用戶(hù)之間潛在的某種關(guān)系，而是從用戶(hù)歷史行為數(shù)據(jù)信息中計(jì)算用戶(hù)相似度，從中尋找相似用戶(hù)進(jìn)行推薦，思路簡(jiǎn)單，易于實(shí)現(xiàn)[7]。但是這種算法至少存在三方面的問(wèn)題：①未考慮時(shí)間因素，沒(méi)有將用戶(hù)不同時(shí)間的評(píng)分區(qū)別對(duì)待；②未考慮跟風(fēng)用戶(hù)帶來(lái)的影響；③未考慮不同用戶(hù)對(duì)同一個(gè)項(xiàng)目評(píng)分差異過(guò)大帶來(lái)的影響。

由于存在以上問(wèn)題，傳統(tǒng)的UserCF算法的推薦精度仍有待提高。為此，該文設(shè)計(jì)了一種結(jié)合貢獻(xiàn)度與時(shí)間權(quán)重的協(xié)同過(guò)濾推薦算法(collaborative filtering recommendation algorithm combining contribution and time weight)，命名為CTCF。該算法通過(guò)定義可信誤差閾值與貢獻(xiàn)度來(lái)減少不同用戶(hù)對(duì)同一項(xiàng)目評(píng)分差異過(guò)大對(duì)推薦結(jié)果產(chǎn)生的負(fù)面影響；通過(guò)在用戶(hù)相似度計(jì)算中引入擬合時(shí)間因子與貢獻(xiàn)度的時(shí)間權(quán)重來(lái)動(dòng)態(tài)模擬用戶(hù)興趣隨時(shí)間的變化；既充分利用了傳統(tǒng)的UserCF算法的優(yōu)勢(shì)，又避免其存在的問(wèn)題，進(jìn)一步提高了基于用戶(hù)的協(xié)同過(guò)濾推薦算法的精度。

1 相關(guān)技術(shù)

1.1 UserCF算法推薦過(guò)程

UserCF的推薦過(guò)程如圖1所示。

圖1 UserCF算法推薦過(guò)程

主要步驟為[8]：

①利用用戶(hù)的歷史行為數(shù)據(jù)構(gòu)建用戶(hù)-項(xiàng)目評(píng)分矩陣；

②使用用戶(hù)相似度計(jì)算方法計(jì)算用戶(hù)相似度，并找出目標(biāo)用戶(hù)的最近鄰；

③選擇最近鄰喜歡而目標(biāo)用戶(hù)未評(píng)分的項(xiàng)目；

④預(yù)測(cè)目標(biāo)用戶(hù)對(duì)第③步中得到的項(xiàng)目的評(píng)分，并將預(yù)測(cè)評(píng)分高(即喜歡程度高)的項(xiàng)目推薦給目標(biāo)用戶(hù)。

1.2 評(píng)分矩陣

假設(shè)U={u1,u2,…,um}表示m個(gè)用戶(hù)，I={i1,i2,…,in}表示n個(gè)項(xiàng)目。用戶(hù)-項(xiàng)目評(píng)分矩陣可表示為Rm,n={Ru,i}，Ru,i是用戶(hù)u對(duì)項(xiàng)目i的評(píng)分。表1是5個(gè)用戶(hù)對(duì)6個(gè)項(xiàng)目的評(píng)分示例，其中“/”表示該用戶(hù)沒(méi)有對(duì)項(xiàng)目進(jìn)行過(guò)評(píng)分，評(píng)分值為1至5的整數(shù)，數(shù)值越大表示用戶(hù)對(duì)這個(gè)項(xiàng)目喜好程度越高。

表1 用戶(hù)對(duì)項(xiàng)目的評(píng)分示例

與之對(duì)應(yīng)的評(píng)分矩陣如下：

1.3 相似度計(jì)算方法

相似度的計(jì)算方法主要有余弦相似性[9]、歐幾里得相似度[10]、皮爾遜相關(guān)系數(shù)[11]等。余弦相似度是兩個(gè)評(píng)分向量夾角的余弦值。歐幾里得相似度指的是兩個(gè)點(diǎn)之間的真實(shí)距離。皮爾遜相關(guān)系數(shù)廣泛用于度量?jī)蓚€(gè)變量之間的相關(guān)性，其計(jì)算公式如下：

sim(a,b)=

(1)

2 CTCF算法設(shè)計(jì)

該文所設(shè)計(jì)的CTCF算法的核心內(nèi)容包括：可信誤差閾值與貢獻(xiàn)度的計(jì)算、擬合貢獻(xiàn)度與時(shí)間因子的時(shí)間權(quán)重的計(jì)算、用戶(hù)相似度的計(jì)算、評(píng)分的預(yù)測(cè)。

2.1 可信誤差閾值與貢獻(xiàn)度的計(jì)算方法設(shè)計(jì)

如前所述，傳統(tǒng)的UserCF算法，在計(jì)算用戶(hù)相似度時(shí)，可能會(huì)遇到不同用戶(hù)對(duì)同一項(xiàng)目評(píng)分差異較大的情況，例如表1中user1和user2雖然共同評(píng)分的項(xiàng)目占比為67.7%，但其中至少有75%的項(xiàng)目評(píng)分差異較大。這種不同用戶(hù)對(duì)共同項(xiàng)目的評(píng)分差異從一定程度上能夠反映出用戶(hù)興趣的差異，因此，在判斷當(dāng)前用戶(hù)對(duì)目標(biāo)用戶(hù)的價(jià)值時(shí)，應(yīng)該充分考慮這種差異。該文分別定義了可信誤差閾值與貢獻(xiàn)度，用可信誤差閾值來(lái)計(jì)算貢獻(xiàn)度，依據(jù)貢獻(xiàn)度來(lái)評(píng)定當(dāng)前用戶(hù)對(duì)目標(biāo)用戶(hù)的價(jià)值大小，從而為進(jìn)一步計(jì)算用戶(hù)相似度提供權(quán)重。

定義1 可信誤差閾值：是不同用戶(hù)對(duì)同一項(xiàng)目的評(píng)分差異的度量，計(jì)算方法如公式(2)所示：

(2)

(3)

定義2 貢獻(xiàn)度：是用戶(hù)間的參考價(jià)值度量，反映不同用戶(hù)的共同喜好程度高低，計(jì)算方法如公式(4)所示：

(4)

其中，t為|ga,i-gb,i|<χ的數(shù)目，|I(a)∪I(b)|為用戶(hù)a和用戶(hù)b評(píng)分項(xiàng)目的總數(shù)量?？梢钥闯鰏up∈[0,1]，且評(píng)分相近的項(xiàng)目越多(即共同喜好程度越高)，貢獻(xiàn)度sup就越大，彼此的參考價(jià)值越高。

2.2 擬合貢獻(xiàn)度與時(shí)間因子的時(shí)間權(quán)重計(jì)算方法設(shè)計(jì)

如前文所述，傳統(tǒng)的UserCF算法忽略了用戶(hù)興趣愛(ài)好會(huì)隨時(shí)間變化這一事實(shí)[12]，由此得出的最近鄰可能并不準(zhǔn)確。一般來(lái)講用戶(hù)近期的行為更能充分說(shuō)明其目前的興趣愛(ài)好。隨著時(shí)間推移，用戶(hù)會(huì)逐漸減弱對(duì)某個(gè)項(xiàng)目的喜好，這種趨勢(shì)呈現(xiàn)出先快后慢、最后趨于穩(wěn)定的特點(diǎn)，這與艾賓浩斯曲線(xiàn)[13]很相似。因此，該文進(jìn)一步將貢獻(xiàn)度與時(shí)間因子相結(jié)合來(lái)對(duì)艾賓浩斯曲線(xiàn)加以改進(jìn)，設(shè)計(jì)了擬合貢獻(xiàn)度與時(shí)間因子的時(shí)間權(quán)重，計(jì)算方法如公式(5)所示。

(5)

不難看出，該時(shí)間權(quán)重既考慮了不同用戶(hù)對(duì)同一項(xiàng)目評(píng)分差異過(guò)大對(duì)推薦結(jié)果的影響，又動(dòng)態(tài)模擬了用戶(hù)興趣隨時(shí)間的變化。

2.3 改進(jìn)的用戶(hù)相似度計(jì)算方法設(shè)計(jì)

在計(jì)算用戶(hù)相似度時(shí)，該文對(duì)皮爾遜相關(guān)系數(shù)加以改進(jìn)，引入公式(5)的擬合貢獻(xiàn)度與時(shí)間因子的時(shí)間權(quán)重，同時(shí)考慮目標(biāo)用戶(hù)a評(píng)價(jià)過(guò)的項(xiàng)目可能包含某用戶(hù)b評(píng)價(jià)過(guò)的全部項(xiàng)目(即前者是后者的超集，如表1中user2與user4)的情況，因后者不能為目標(biāo)用戶(hù)提供有用的信息，將其視為跟風(fēng)用戶(hù)[14]，并將目標(biāo)用戶(hù)與跟風(fēng)用戶(hù)的相似度置零。改進(jìn)后的相似度計(jì)算方法如公式(6)所示：

sim(a,b)=

(6)

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

計(jì)算得到目標(biāo)用戶(hù)與其他用戶(hù)的相似度后，按照相似度降序排列，取前K個(gè)作為目標(biāo)用戶(hù)的近鄰集，產(chǎn)生近鄰評(píng)價(jià)過(guò)的項(xiàng)目集，并用公式(7)[15]對(duì)其中目標(biāo)用戶(hù)未評(píng)價(jià)的項(xiàng)目進(jìn)行評(píng)分預(yù)測(cè)。

(7)

最后，按照目標(biāo)用戶(hù)a的預(yù)測(cè)評(píng)分的降序?qū)?xiàng)目排序，取Top-N個(gè)加以推薦。

2.5 CTCF算法流程

CTCF算法的總體流程如圖2所示。

圖2 CTCF算法流程

具體步驟可描述如下：

算法：結(jié)合貢獻(xiàn)度與時(shí)間權(quán)重的協(xié)同過(guò)濾推薦算法。

輸入：用戶(hù)評(píng)分信息，目標(biāo)用戶(hù)a，推薦結(jié)果個(gè)數(shù)N；

輸出：推薦給目標(biāo)用戶(hù)a的項(xiàng)目列表。

Step1：首先，對(duì)用戶(hù)評(píng)分信息做預(yù)處理，用公式(8)將時(shí)間戳歸一化；其中，ti為當(dāng)前時(shí)間戳，tmin為最小時(shí)間戳，tmax為最大時(shí)間戳。

(8)

然后，構(gòu)建出用戶(hù)-項(xiàng)目評(píng)分矩陣與用戶(hù)-項(xiàng)目評(píng)分時(shí)間矩陣。

Step2：用公式(4)計(jì)算貢獻(xiàn)度sup，用公式(5)計(jì)算時(shí)間權(quán)重。

Step3：用公式(6)計(jì)算相似度矩陣，并產(chǎn)生目標(biāo)用戶(hù)a的近鄰集以及該近鄰集已評(píng)價(jià)的項(xiàng)目集I，在I中去除用戶(hù)a已評(píng)價(jià)過(guò)的項(xiàng)目，構(gòu)成I'。

Step4：用公式(7)預(yù)測(cè)目標(biāo)用戶(hù)a對(duì)I'中各個(gè)項(xiàng)目的評(píng)分。

Step5：將預(yù)測(cè)得到的評(píng)分由高到低排序，并將前N個(gè)項(xiàng)目作為目標(biāo)用戶(hù)a的推薦集。

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

為了測(cè)試CTCF算法的性能，做了相關(guān)實(shí)驗(yàn)。

3.1 實(shí)驗(yàn)數(shù)據(jù)及環(huán)境

實(shí)驗(yàn)所用的數(shù)據(jù)是MovieLens ml-100K數(shù)據(jù)集中u.data文件的數(shù)據(jù)，有943個(gè)用戶(hù)、1 652部電影、100 000個(gè)評(píng)分[16]。隨機(jī)選取其中的75%用作訓(xùn)練集，剩余的25%用作測(cè)試集，用戶(hù)的評(píng)分范圍為1～5，數(shù)值越大表示用戶(hù)興趣越大。

實(shí)驗(yàn)環(huán)境：CPU為Intel Core i7，主頻為2.2 GHz，內(nèi)存為16 GB；操作系統(tǒng)是macOS 10.13；編程語(yǔ)言是Python3.7。

3.2 評(píng)價(jià)指標(biāo)

該文采取目前比較主流的推薦算法評(píng)價(jià)指標(biāo)召回率(recall)和精度(precision)來(lái)評(píng)估算法。分別用公式(9)和公式(10)進(jìn)行計(jì)算。

(9)

(10)

其中，R(a)表示算法推薦給用戶(hù)a的項(xiàng)目集合，I'(a)表示用戶(hù)a實(shí)際喜歡的項(xiàng)目集合，U表示測(cè)試集中所有用戶(hù)的集合。

為了比較全面地評(píng)價(jià)算法，還采用F-Measure作為評(píng)價(jià)指標(biāo)，F(xiàn)-Measure公式如下：

(11)

當(dāng)參數(shù)α=1時(shí)，就是最常用的F1值，即：

(12)

F1的值越大表示算法的綜合表現(xiàn)越好。

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

(1)可信誤差閾值(χ)的有效性實(shí)驗(yàn)。

為驗(yàn)證定義的可信誤差閾值(χ)的有效性，在χ取常數(shù)(0、1、2、3、4)以及用公式(2)進(jìn)行動(dòng)態(tài)計(jì)算的情況下，測(cè)試CTCF算法的F1值，結(jié)果如圖3所示。

圖3 不同可信誤差閾值對(duì)F1值的影響

從圖3可以看出，隨著近鄰數(shù)的增加，F(xiàn)1值不斷增大，然后趨于穩(wěn)定，而且采用該文定義的可信誤差閾值時(shí)，F(xiàn)1明顯高于其他幾種情況。

(2)CTCF算法總體性能實(shí)驗(yàn)。

為驗(yàn)證CTCF算法能有效提升推薦質(zhì)量，將其與采用皮爾遜相似度的UserCF、使用了改進(jìn)皮爾遜相似度的文獻(xiàn)[17]的算法作對(duì)比，統(tǒng)計(jì)三種算法的precision、recall和F1值，結(jié)果如圖4至圖6所示。

圖4 不同近鄰數(shù)N對(duì)應(yīng)的precision

圖5 不同近鄰數(shù)N對(duì)應(yīng)的recall

圖6 不同近鄰數(shù)N對(duì)應(yīng)的F1

從圖4和圖5可以看出，不同近鄰數(shù)下，CTCF算法對(duì)recall和precision有了明顯的提升。從圖6可以看出，CTCF算法的F1值始終高于另外兩種算法。

時(shí)間復(fù)雜度也是評(píng)價(jià)一個(gè)算法優(yōu)劣的重要指標(biāo)，CTCF算法與UserCF類(lèi)似，最耗時(shí)的階段是用戶(hù)相似度計(jì)算，時(shí)間復(fù)雜度是O(n2)，n為用戶(hù)數(shù)；文獻(xiàn)[17]算法的時(shí)間復(fù)雜度是O(n3)。為對(duì)比三種算法的時(shí)間開(kāi)銷(xiāo)，進(jìn)行了相關(guān)實(shí)驗(yàn)，結(jié)果如圖7所示。

由圖7可知，CTCF算法與傳統(tǒng)的協(xié)同過(guò)濾算法耗時(shí)相近，遠(yuǎn)遠(yuǎn)小于文獻(xiàn)[17]算法。綜上，CTCF算法在不增加時(shí)間復(fù)雜度的前提下，提升了推薦精度。

圖7 三種算法對(duì)應(yīng)不同近鄰數(shù)N的時(shí)間開(kāi)銷(xiāo)

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

以提高推薦精度為目標(biāo)，該文設(shè)計(jì)了一種結(jié)合貢獻(xiàn)度與時(shí)間權(quán)重的協(xié)同過(guò)濾算法CTCF，該算法對(duì)傳統(tǒng)的基于用戶(hù)的協(xié)同過(guò)濾推薦算法做了改進(jìn)，在用戶(hù)相似度計(jì)算中引入貢獻(xiàn)度與時(shí)間因子，降低了不同用戶(hù)對(duì)相同項(xiàng)目評(píng)分差異過(guò)大帶來(lái)的影響，同時(shí)在一定程度上增大了用戶(hù)近期反饋行為的權(quán)重，對(duì)用戶(hù)早期的行為信息權(quán)重進(jìn)行了衰減，客觀(guān)地反映了用戶(hù)興趣隨時(shí)間的動(dòng)態(tài)變化。在MovieLens數(shù)據(jù)集上與類(lèi)似算法的對(duì)比實(shí)驗(yàn)結(jié)果表明，設(shè)計(jì)的CTCF算法能有效提高推薦質(zhì)量。