王娜娜

(安徽理工大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，安徽 淮南 232001)

互聯(lián)網(wǎng)和信息技術(shù)的普及，使人們進(jìn)入信息化時(shí)代。然而，近幾年資源迷向、信息過(guò)載等現(xiàn)象日益嚴(yán)重。因此，為人們提供便利的推薦系統(tǒng)應(yīng)運(yùn)而生。在社交網(wǎng)絡(luò)、電子商務(wù)、電影、音樂(lè)、個(gè)性化郵件以及閱讀等領(lǐng)域應(yīng)用廣泛。推薦系統(tǒng)是一種信息過(guò)濾手段，其能有效根據(jù)用戶的需求，快速、準(zhǔn)確地為用戶推薦有用資源。

目前，推薦系統(tǒng)由三類(lèi)構(gòu)成，分別為基于內(nèi)容的、協(xié)同過(guò)濾的和混合的推薦。而基于協(xié)同過(guò)濾的推薦是最常用的個(gè)性化推薦技術(shù)。隨著推薦系統(tǒng)中用戶和項(xiàng)目的數(shù)量日益龐大，用戶冷啟動(dòng)、數(shù)據(jù)稀疏性、可擴(kuò)展性等問(wèn)題逐漸增多，而傳統(tǒng)的協(xié)同過(guò)濾算法在進(jìn)行個(gè)性化推薦過(guò)程中通過(guò)用戶—項(xiàng)目評(píng)分矩陣計(jì)算項(xiàng)目相似度或用戶相似度，未考慮項(xiàng)目類(lèi)型和時(shí)間距離這兩個(gè)因素給用戶興趣變化帶來(lái)的影響。

基于此，本文提出了一種基于時(shí)間權(quán)重和用戶興趣變化的協(xié)同過(guò)濾方法TACF(time and interests collaborative filtering)。首先，通過(guò)構(gòu)建的用戶興趣分布矩陣，得到用戶興趣分布向量，并采用修正的余弦相似度計(jì)算用戶間存在的興趣相似度；然后，引入時(shí)間權(quán)重函數(shù)，計(jì)算基于時(shí)間權(quán)重的用戶評(píng)分相似度；最后，將兩種相似度進(jìn)行線性加權(quán)，找出與目標(biāo)用戶最相似的k個(gè)鄰居并且預(yù)測(cè)未評(píng)分項(xiàng)目的評(píng)分值，產(chǎn)生Top-N推薦。流程圖主要分為3部分，具體挖掘流程如圖1所示。

圖1 ATCF算法流程圖

1 相關(guān)工作

目前，隨著推薦系統(tǒng)中用戶和項(xiàng)目數(shù)量的急劇增長(zhǎng)，在推薦系統(tǒng)應(yīng)用中，國(guó)內(nèi)外常采用的方法主要分為三類(lèi)。

1)基于內(nèi)容的推薦算法是從用戶信息中挖掘其潛在的興趣點(diǎn)；然后，把預(yù)推薦內(nèi)容與挖掘出的興趣點(diǎn)進(jìn)行相似度比較和分析，最后，將相似度高的內(nèi)容推薦給用戶。張桂平等人針對(duì)單一角度描述用戶興趣不全面，提出一種基于用戶行為和用戶主題興趣的文檔推薦方法[1]。Sedhain等人在協(xié)同過(guò)濾算法中引入人口統(tǒng)計(jì)學(xué)數(shù)據(jù)和社交信息，避免冷啟動(dòng)問(wèn)題[2]。李偉霖等人通過(guò)從用戶評(píng)論文本中提取用戶觀點(diǎn)，來(lái)修正協(xié)同過(guò)濾推薦算法[3]。蔣勝等人根據(jù)動(dòng)態(tài)社會(huì)行為和用戶背景信息，有效解決冷啟動(dòng)和數(shù)據(jù)稀疏問(wèn)題[4]。

2)協(xié)同過(guò)濾推薦可細(xì)分為基于項(xiàng)目和基于用戶的推薦，主要是根據(jù)相似的思想為用戶進(jìn)行推薦。范洪博等人針對(duì)無(wú)法對(duì)用戶進(jìn)行多興趣話題推薦，提出融合用戶背景和用戶人格信息的話題推薦方法[5]。徐蕾等人在協(xié)同過(guò)濾系統(tǒng)中的應(yīng)用博弈論的方法對(duì)用戶評(píng)分行為進(jìn)行分析，提出了基于均衡學(xué)習(xí)的算法[6]。李豪等人考慮項(xiàng)目屬性的不同是否會(huì)對(duì)用戶興趣變化產(chǎn)生影響，引入“興趣分布矩陣”，并設(shè)計(jì)啟發(fā)式評(píng)分方法[7]。Hernando等人通過(guò)采用用戶評(píng)分矩陣進(jìn)行分解的方式對(duì)用戶興趣進(jìn)行分析[8]。Patra等人通過(guò)結(jié)合Bhattacharyya系數(shù)的相似度計(jì)算方法，有效改善數(shù)據(jù)稀疏問(wèn)題[9]。

3)基于混合的推薦算法是通過(guò)組合不同類(lèi)型的算法，達(dá)到能夠在充分利用各自算法優(yōu)點(diǎn)的同時(shí)克服各自缺點(diǎn)的目的。楊武等人將基于內(nèi)容和基于協(xié)同過(guò)濾的推薦算法組合進(jìn)行新聞推薦，雖然能有效緩解數(shù)據(jù)稀疏性問(wèn)題，但是該方法應(yīng)用范圍有限[10]。趙文濤等人提出基于用戶多屬性和用戶興趣結(jié)合的方法，有效改善數(shù)據(jù)稀疏性和冷啟動(dòng)問(wèn)題[11]。Park等人提出一種K近鄰圖的快速協(xié)同過(guò)濾算法，該方法不僅能提高推薦準(zhǔn)確率，還能提高計(jì)算速度[12]。張玉連等人提出在融合用戶相似度和項(xiàng)目相似度的加權(quán)方法改進(jìn)Slope one算法[13]。董晨露等人將遺忘曲線和用戶評(píng)論引入?yún)f(xié)同過(guò)濾算法中，該算法能在稀疏數(shù)據(jù)集上獲得較好的推薦結(jié)果[14]。

綜上所述，上述研究均在其提出方法的基礎(chǔ)上提升了推薦系統(tǒng)的推薦質(zhì)量。但大部分學(xué)者研究范圍主要圍繞用戶屬性、項(xiàng)目評(píng)分等基本信息，鮮有學(xué)者考慮項(xiàng)目類(lèi)型和時(shí)間變化給用戶興趣波動(dòng)帶來(lái)的影響。因此，本文提出的TACF算法，主要是通過(guò)構(gòu)建用戶興趣分布矩陣和引入時(shí)間權(quán)重函數(shù)改進(jìn)協(xié)同過(guò)濾算法，實(shí)驗(yàn)表明該方法能為目標(biāo)用戶提供更加準(zhǔn)確的個(gè)性化推薦。

2 基于TACF算法設(shè)計(jì)

2.1 用戶—評(píng)分矩陣的建立

假設(shè)推薦系統(tǒng)中存在m個(gè)用U={u1,u2,u3,…,um}和n個(gè)項(xiàng)目I={i1,i2,i3,…,in}。用戶—項(xiàng)目評(píng)分矩陣Rmn={Rui}，用戶u對(duì)項(xiàng)目i的評(píng)分可表示為Rui。如下表所示。

表1 用戶—評(píng)分矩陣Rmn

2.2 用戶興趣相似度計(jì)算

2.2.1 用戶興趣變化分析

由于傳統(tǒng)推薦算法大多根據(jù)用戶對(duì)項(xiàng)目的評(píng)分值多少，根據(jù)相似度公式計(jì)算用戶與用戶間的相似度，忽略項(xiàng)目類(lèi)型屬性對(duì)用戶興趣變化帶來(lái)的影響。而項(xiàng)目本身通常具有明顯的類(lèi)別屬性，例如音樂(lè)項(xiàng)目具有“鄉(xiāng)村”“流行”“古典”等屬性，電影項(xiàng)目具有“愛(ài)情”“喜劇”“科幻”等屬性。這些項(xiàng)目本身具有的屬性在一定程度上會(huì)影響用戶的評(píng)分，間接反映出用戶的興趣分布。

因?yàn)橛脩舻呐d趣愛(ài)好各不相同，所以通過(guò)歷史行為來(lái)挖掘用戶在某個(gè)屬性上的是否存在興趣。歷史行為可以分為用戶對(duì)該類(lèi)型項(xiàng)目的打分情況和標(biāo)記該類(lèi)型項(xiàng)目的數(shù)量。例如在電影項(xiàng)目中，若某用戶共標(biāo)記了280部電影，其中有190部為“喜劇”電影，25部為“科幻”電影，從評(píng)分?jǐn)?shù)據(jù)中看出喜劇評(píng)分為3.6，科幻評(píng)分為8.0。直觀地考慮，該用戶對(duì)喜劇更感興趣，因?yàn)橛^看喜劇數(shù)量較多。但是從打分情況考慮，用戶更滿意科幻電影。出現(xiàn)這種情況的常見(jiàn)原因可以理解為用戶雖然觀看數(shù)量少，但是其觀看的科幻電影均為口碑較好的電影，從打分情況看出用戶滿意度很高。因此，一個(gè)個(gè)性化推薦系統(tǒng)不僅要推薦用戶明顯感興趣的項(xiàng)目外，還要根據(jù)歷史信息挖掘其潛在興趣，上述情況喜劇和科幻項(xiàng)目類(lèi)型均應(yīng)該列入推薦列表，即評(píng)分和標(biāo)記數(shù)量均是反映用戶興趣的重要因素。

2.2.2 用戶興趣分布矩陣構(gòu)建

假設(shè)系統(tǒng)中項(xiàng)目本身的固有類(lèi)型有C個(gè)，Mi表示項(xiàng)目ji的類(lèi)型向量，用Mi={m1,m2,m3,…,mn}表示項(xiàng)目類(lèi)型向量集合，mn取值為0或1，其中0表示項(xiàng)目不存在此類(lèi)型，1表示存在此類(lèi)型。由于一個(gè)項(xiàng)目可以存在多個(gè)類(lèi)型，則所有項(xiàng)目的類(lèi)型矩陣表示為矩陣M=[M1M2M3…Mk]T

Ei=[Ei,1Ei,2Ei,3…Ei,c]

則所有用戶的興趣分布矩陣構(gòu)建為：

E=[E1E2E3…Ek]T

將用戶—評(píng)分矩陣R中不為零的值全部設(shè)置為1，即可得到用戶—標(biāo)記項(xiàng)目矩陣S。用戶標(biāo)記項(xiàng)目在C個(gè)類(lèi)型上標(biāo)記數(shù)量分布矩陣表示為Q，則:

Q=S×M

(1)

那么，用戶標(biāo)記的項(xiàng)目在C個(gè)類(lèi)型上的平均評(píng)價(jià)表示為矩陣H，則：

(2)

由于矩陣中不存在除法運(yùn)算，公式(2)中分子分母均為n×c矩陣，公式中的除法表示分子分母中對(duì)應(yīng)位置相除。

為了能使用戶間的比較更加方便，本文對(duì)矩陣Q、矩陣H中的每行向量進(jìn)行歸一化處理，其公式如下：

(3)

進(jìn)行歸一化處理后的矩陣分別記為Q′和H′，其中，矩陣Q′表示用戶興趣在C個(gè)類(lèi)型上的標(biāo)記數(shù)量分布，矩陣H′表示用戶興趣在C個(gè)類(lèi)型上的用戶評(píng)價(jià)分布，進(jìn)而得到用戶興趣分布矩陣計(jì)算公式為：

E=α×Q′+(1-α)×H′

(4)

其中α為可變參數(shù)，取值范圍為0～1，參數(shù)取值會(huì)通過(guò)多次實(shí)驗(yàn)?zāi)M選取使推薦結(jié)果最優(yōu)的值。

2.2.3 用戶間的興趣相似度計(jì)算

本文采用修正的余弦相似度計(jì)算用戶間的興趣相似度sim1(u,v)，具體計(jì)算公式如下：

走在路上看到的場(chǎng)景、幼兒園發(fā)生的沖突、動(dòng)畫(huà)片里看到的故事，我總是時(shí)不時(shí)這么問(wèn)她，然后和她討論思考。有的問(wèn)題孩子無(wú)法回答，我就會(huì)告訴她；有的問(wèn)題她有了自己一定的答案，我也會(huì)順勢(shì)引導(dǎo)。

(5)

2.3 基于時(shí)間權(quán)重的用戶評(píng)分相似度

2.3.1 用戶評(píng)分時(shí)間權(quán)重計(jì)算

在推薦系統(tǒng)中，時(shí)間信息是非常重要的一種信息[15]，其對(duì)用戶的個(gè)人興趣也產(chǎn)生了較大的影響。用戶的興趣和行為會(huì)隨時(shí)間的變化而變化。例如程序員用戶在工作初期比較傾向于選擇閱讀入門(mén)類(lèi)的書(shū)籍，但隨著工作時(shí)間的積累，逐漸從入門(mén)類(lèi)轉(zhuǎn)變?yōu)閷?zhuān)業(yè)類(lèi)書(shū)籍；另外，用戶對(duì)項(xiàng)目的行為還會(huì)受到季節(jié)效應(yīng)的影響，例如用戶在不同的季節(jié)對(duì)不同的衣服興趣度不同。通常，我們會(huì)認(rèn)為用戶最近訪問(wèn)的項(xiàng)目就為其感興趣的項(xiàng)目。因此，本文引入時(shí)間權(quán)重公式計(jì)算其對(duì)用戶評(píng)分的影響。

(6)

其中，t取值范圍為[0-1]，w(tu,i)取值范圍為(0-1)。由公式知，w(tu,i)函數(shù)是一個(gè)單調(diào)遞增函數(shù)，其值隨時(shí)間t增加而增加，但不會(huì)超過(guò)1；tu,i表示在時(shí)刻t時(shí)用戶u對(duì)項(xiàng)目i的評(píng)分值。實(shí)驗(yàn)前，本文通過(guò)標(biāo)準(zhǔn)公式將用戶評(píng)分的時(shí)間變量轉(zhuǎn)化為[0,1]。其中，時(shí)間變量的變化可以直觀的從權(quán)重上看出，可以通過(guò)權(quán)重大小精確地分析用戶興趣的變化，進(jìn)而達(dá)到為用戶提供更加準(zhǔn)確的個(gè)性化推薦的目的。

2.3.2 用戶評(píng)分相似度計(jì)算

本文采用pearson相關(guān)系數(shù)計(jì)算相似度的方法來(lái)計(jì)算用戶評(píng)分相似度sim2(u,v)，具體計(jì)算公式如下：

(7)

其中，sim2(u,v)表示用戶u和v之間基于時(shí)間權(quán)重的用戶評(píng)分相似度；w(tu,i)表示用戶u對(duì)項(xiàng)目i評(píng)分的時(shí)間權(quán)重。

3 基于組合相似度的推薦

3.1 用戶總相似度計(jì)算

組合基于用戶興趣和基于時(shí)間權(quán)重的相似度，通過(guò)計(jì)算得到用戶總相似度，使用線性加權(quán)方法進(jìn)行組合，具體公式如下：

sim(u,v)=λsim1(u,v)+(1-λ)sim2(u,v)

(8)

其中，γ、1-γ分別表示sim1(u,v)和sim2(u,v)相似度權(quán)重，且γ取值為[0-1]，在本文中由于兩種相似度方法占據(jù)比例相同，本文γ取值為0.5。

3.2 改進(jìn)的評(píng)分公式

計(jì)算用戶總相似度，選取前k個(gè)最近鄰居，得到最近鄰居集合后，對(duì)目標(biāo)用戶進(jìn)行項(xiàng)目推薦。在推薦系統(tǒng)中，用戶影響力是影響推薦結(jié)果的重要因素之一，人們更傾向于采納經(jīng)驗(yàn)豐富的人提出觀點(diǎn)。例如一位觀影量超過(guò)3000部的用戶提出的觀點(diǎn)與普通用戶觀點(diǎn)更具有權(quán)威性，即在進(jìn)行推薦時(shí)，應(yīng)該首先被考慮。因此，改進(jìn)的評(píng)分預(yù)測(cè)公式如下：

(9)

3.3TACF 算法描述

通過(guò)上述討論，本文設(shè)計(jì)了一個(gè)簡(jiǎn)潔的算法來(lái)幫助理解如何進(jìn)行個(gè)性化推薦。

算法：TACF算法設(shè)計(jì)

輸入：用戶-評(píng)分?jǐn)?shù)據(jù)

輸出：推薦列表

1:輸入用戶-評(píng)分矩陣

2: do

3: {

4: for(矩陣不為空)

5: {對(duì)用戶進(jìn)行聚類(lèi)，再根據(jù)公式(1)～(4)計(jì)算用戶興趣分布矩陣}

6: end if

7: for(根據(jù)興趣分布向量)

8: {根據(jù)公式(5)計(jì)算用戶間的興趣相似度}

9: end if

10： for(矩陣不為空)

11： {根據(jù)公式(6) ～(7)計(jì)算基于時(shí)間權(quán)重的評(píng)分相似度}

12: end if

13: for(矩陣不為空)

14: {根據(jù)公式(8)計(jì)算基于兩者線性組合的總相似度，根據(jù)公式(9)進(jìn)行評(píng)分預(yù)測(cè)，產(chǎn)生推薦列表}

15: }

16: end

算法設(shè)計(jì)說(shuō)明：

1)第一個(gè)判斷，即step2-step6，判斷用戶—評(píng)分矩陣是否為空，若不為空則進(jìn)行下一步操作反之則終止。

2)第二個(gè)判斷，即step7-step9，根據(jù)構(gòu)建的用戶興趣矩陣，得到用戶興趣分布向量，計(jì)算用戶間的興趣相似度。

3)第三個(gè)判斷，即step10-step12, 根據(jù)構(gòu)建的用戶-評(píng)分矩陣計(jì)算基于時(shí)間權(quán)重的評(píng)分相似度。

4)第四個(gè)判斷，即step13-step16,采用線性加權(quán)的方法計(jì)算總的相似度，并使用改進(jìn)的評(píng)分公式進(jìn)行評(píng)分預(yù)測(cè)。

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

4.1 實(shí)驗(yàn)數(shù)據(jù)

本次實(shí)驗(yàn)采用網(wǎng)上開(kāi)源的MovieLens站點(diǎn)提供的100 K數(shù)據(jù)集，通過(guò)943對(duì)用戶根據(jù)1682個(gè)電影項(xiàng)目打分產(chǎn)生的10萬(wàn)條評(píng)分?jǐn)?shù)據(jù)，計(jì)算得數(shù)據(jù)稀疏度約為94%，且每隊(duì)用戶評(píng)分電影數(shù)量不少于20部。評(píng)分等級(jí)分為1分至5分，分值越高表示用戶對(duì)該部電影興趣度越高。將實(shí)驗(yàn)數(shù)據(jù)平均分為五組，采用隨機(jī)法選取其中一組作為訓(xùn)練集，剩下的四組作為測(cè)試集。

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

選擇平均絕對(duì)誤差(MAE)作為本次實(shí)驗(yàn)的評(píng)價(jià)指標(biāo)。表示系統(tǒng)預(yù)測(cè)評(píng)分與真實(shí)評(píng)分之間的誤差，以此衡量算法推薦的準(zhǔn)確度。

(10)

其中，rui、r′ui分別表示用戶對(duì)項(xiàng)目的實(shí)際評(píng)分值和推薦算法計(jì)算出的預(yù)測(cè)評(píng)分值；n表示測(cè)試集中的項(xiàng)目個(gè)數(shù)。

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

為使推薦算法能在最優(yōu)參數(shù)下對(duì)用戶進(jìn)行推薦，最重要的一點(diǎn)就是確定參數(shù)值。在α分別取0.1至0.9的情況下，測(cè)試TACF算法在不同α值下的MAE值。

從圖2可以看出，隨著α值得不斷增大，MAE值呈現(xiàn)波動(dòng)，當(dāng)α為0.5時(shí)，MAE值取得最小值，即此時(shí)算法的推薦質(zhì)量最高，具體數(shù)據(jù)如下所示。

圖2 TACF算法在不同α值下的MAE值

為驗(yàn)證本文提出算法的推薦準(zhǔn)確率，將本文提出的算法(TACF)和基于物品的(IBCF)以及基于用戶的(UBCF)推薦算法在不同K最近鄰數(shù)量的情況下進(jìn)行對(duì)比分析，實(shí)驗(yàn)數(shù)據(jù)如下所示。

圖3 不同算法的MAE值對(duì)比

從圖3看出，隨著K值得不斷增大，三種方法的MAE值逐漸減小，即算法預(yù)測(cè)結(jié)果更加準(zhǔn)確，但是在真實(shí)測(cè)試數(shù)據(jù)中，由于存在用戶冷啟動(dòng)、數(shù)據(jù)稀疏性等問(wèn)題，從圖中可以直觀地看出K增加到一定數(shù)值時(shí)，MAE值逐漸趨于穩(wěn)定，即準(zhǔn)確度提升程度減緩甚至有下降趨勢(shì)。當(dāng)K為70時(shí)，MAE值趨于穩(wěn)定且明顯低于UBCF方法和IBCF方法。實(shí)驗(yàn)表明，本文方法可以顯著提高推薦準(zhǔn)確率，并為用戶提供更加令人滿意的個(gè)性化推薦列表。

5 總結(jié)

本文在傳統(tǒng)推薦算法中增加了用戶興趣分布矩陣以及基于時(shí)間的權(quán)重函數(shù)，能夠有效解決用戶—評(píng)分矩陣數(shù)據(jù)稀疏性和推薦準(zhǔn)確度低等問(wèn)題。計(jì)算用戶間的興趣相似度時(shí)，本文通過(guò)挖掘用戶歷史數(shù)據(jù)對(duì)評(píng)價(jià)過(guò)的項(xiàng)目類(lèi)型進(jìn)行分類(lèi)，研究項(xiàng)目類(lèi)型對(duì)用戶興趣度的反映；另外，在用戶評(píng)價(jià)過(guò)程中，提出基于時(shí)間權(quán)重的用戶評(píng)分相似度計(jì)算，根據(jù)評(píng)價(jià)時(shí)間的先后，可以判斷用戶近期興趣變化趨勢(shì)；本文將兩者進(jìn)行線性加權(quán)，在相似度計(jì)算過(guò)程中，通過(guò)動(dòng)態(tài)調(diào)整兩者所占比例，使相似度組合達(dá)到最優(yōu)。最終尋找出與目標(biāo)用戶最相似的前K個(gè)最近鄰進(jìn)行評(píng)分預(yù)測(cè)，進(jìn)而使用Top-N算法產(chǎn)生推薦列表。本次實(shí)驗(yàn)結(jié)果顯示，本文提出的推薦算法能夠有效提高用戶間的相似度，顯著提高推薦準(zhǔn)確度，在數(shù)據(jù)稀疏的情況下，能較好地提高推薦質(zhì)量。下一步可以嘗試在TACF算法的基礎(chǔ)上融入用戶多屬性分析，從而達(dá)到更高的推薦精確度。