李敬兆 朱東郡 譚大禹

1(安徽理工大學(xué)電氣與信息工程學(xué)院 安徽 淮南 232001)2(安徽理工大學(xué)計算機(jī)科學(xué)與工程學(xué)院 安徽 淮南 232001)

動態(tài)多源時間認(rèn)知推薦算法研究

李敬兆1,2朱東郡2譚大禹2

1(安徽理工大學(xué)電氣與信息工程學(xué)院 安徽 淮南 232001)2(安徽理工大學(xué)計算機(jī)科學(xué)與工程學(xué)院 安徽 淮南 232001)

一個好的推薦算法在如今的智能Web應(yīng)用中變得十分重要。給出一種具有時間認(rèn)知的推薦算法。傳統(tǒng)的推薦算法通常不加選擇地使用早期和近期的評價，隨著時間的推移而忽略了用戶興趣的變化，且用戶的興趣在短期的時間間隔內(nèi)保持穩(wěn)定但在長期間隔內(nèi)是有所改變的。在已有的協(xié)同過濾推薦算法基礎(chǔ)上加入了時間向量因子用來激勵近期記錄或減弱早期記錄，以達(dá)到更有效分類相似興趣的用戶的目的。結(jié)果表明應(yīng)用該方法能有效提高在智能Web中推薦的準(zhǔn)確率及效率。

智能Web 時間向量因子 協(xié)同過濾推薦 用戶興趣變化

0 引 言

隨著互聯(lián)網(wǎng)的不斷發(fā)展，大量的信息出現(xiàn)在人們的視野中[8]。信息的爆炸使得用戶很難獲取到對自己有用的信息。雖然搜索引擎可以幫助人們從海量信息中檢索出需要的信息，但同時也要求用戶提供必要的關(guān)鍵詞。當(dāng)查詢結(jié)果不能讓用戶滿意時，用戶還需提供更合適的關(guān)鍵詞重新查詢。如果查詢關(guān)鍵詞不能夠恰當(dāng)?shù)胤从吵鏊阉餍枨?，那么查詢的結(jié)果就很令人失望。因此只有在用戶能很好地用關(guān)鍵詞描述自己的需求時，搜索引擎才能更好地體現(xiàn)其功能。而當(dāng)用戶對自身的需求比較模糊時，使用搜索引擎將很難查詢出稱心的結(jié)果。

然而推薦系統(tǒng)正是為解決這類問題而出現(xiàn)的。推薦系統(tǒng)通過分析用戶的歷史數(shù)據(jù)來建模用戶興趣[7]，發(fā)現(xiàn)用戶的可能存在的一些需求，并對其進(jìn)行分析，根據(jù)分析結(jié)果為用戶推薦相應(yīng)的信息。

隨著對推薦系統(tǒng)研究的深入，研究者們針對不同的需求提出了不同的推薦算法，其中包括基于內(nèi)容的推薦、協(xié)同過濾推薦、基于聚類算法的推薦以及基于產(chǎn)品到產(chǎn)品的專利推薦等[7]。而協(xié)同過濾推薦是使用最為普遍和成功的。

協(xié)同過濾CF(Collaborative Filtering)是向用戶推薦與其具有相似愛好的用戶喜歡的產(chǎn)品[7]。它通過用戶對產(chǎn)品的評價計算出與目標(biāo)用戶的愛好相似的用戶，然后把他們喜歡的產(chǎn)品推薦給目標(biāo)用戶。協(xié)同過濾的假設(shè)是：多個用戶對一些產(chǎn)品給予相似的評價，那么對另一些產(chǎn)品也會給予相似評價[7]。就像人們時常喜歡與愛好相同的朋友相互推薦和分享有趣的事物一樣，這種推薦和分享更容易被人所接受。

但是目前的協(xié)同過濾算法在相似度計算中往往不加選擇地使用早期和近期記錄。而用戶瀏覽記錄是和用戶自身的行為邏輯，興趣特點有緊密聯(lián)系的。由于用戶習(xí)慣的變化以及用戶與用戶之間的不同，推薦系統(tǒng)在瀏覽時間和評價時間的數(shù)據(jù)獲取上存在不確定性、多源性。其數(shù)據(jù)在時間軸上表現(xiàn)出實時的動態(tài)變化。因此如果不考慮時間因素，忽略了用戶興趣的變化。隨著時間的推移推薦系統(tǒng)就不能更精確地給用戶推薦信息。而且用戶的興趣一般在短期的時間間隔內(nèi)保持穩(wěn)定，但在長期時間跨度內(nèi)，不同用戶的興趣變化是不確定的甚至雜亂無章的。因此在用戶相似度的計算中，用戶對產(chǎn)品的評價時間就顯得非常重要。比如用戶A和用戶B在評價記錄中都對看過探險類的電影評價很高，但用戶A是2年以前的評價，用戶B是最近的評價。傳統(tǒng)的KNN相似度算法就會認(rèn)為用戶A、B都喜歡看探險的電影，他們倆是偏好相似的用戶。然而事實上用戶A早在一年前就不看探險類的電影，而且認(rèn)為其沒有意思。所以近期來看用戶A與B就探險類電影而言不能認(rèn)為是具有相似偏好的用戶。基于此，本文提出了融合時間向量算子的協(xié)同過濾算法。其核心思想是：某些用戶在同一時期內(nèi)對某些產(chǎn)品給出的評價相似，那么在這個時期內(nèi)他們對另一些產(chǎn)品所給出的評價很大程度上也會相似。所以在用戶相似度計算中多個用戶在不同時期內(nèi)對一些產(chǎn)品給予相似的評價，這種評價是不穩(wěn)定的，需要在時間上進(jìn)行衰減，而在同一時期內(nèi)對一些產(chǎn)品給予相似的評價，在這種評價是有效，需要在時間上進(jìn)行激勵。從而讓用戶的相似度變得更加精確。

1 協(xié)同過濾推薦中常見的相似度算法

1.1 向量夾角余弦相似度計算

協(xié)同過濾可以分為基于產(chǎn)品或基于用戶?；诋a(chǎn)品的協(xié)同過濾算法(Item-based CF)是通過分析與某一產(chǎn)品相似的一些產(chǎn)品的評分，推測目標(biāo)用戶對這一產(chǎn)品的喜好程度。而基于用戶的協(xié)同過濾算法(User-based CF)是通過與目標(biāo)用戶興趣相似的用戶對某一產(chǎn)品評分來推測目標(biāo)用戶對此產(chǎn)品的喜好度，本文主要討論基于用戶的協(xié)同過濾。

基于用戶的協(xié)同過濾預(yù)測可以分成兩部分:一是用戶相似度的計算，即找出最相似的鄰近用戶。二是計算鄰近的相似用戶對產(chǎn)品評分的均值，預(yù)測目標(biāo)用戶的評分[7]。其中向量夾角余弦相似度計算是其中常用的方法。

假設(shè)包含了n個用戶的集合U={U1,U2,…,Un)和m個產(chǎn)品的集合I={I1,I2,…,Im)。用矩陣表示如下。見表1所示。

表1 用戶-產(chǎn)品矩陣(User-Item Matrix)

表1中rn,m表示用戶n對產(chǎn)品m的評價。如果rn,m=?則表示用戶n沒有評價過產(chǎn)品m。

關(guān)于用戶之間相似度的計算，設(shè)用戶Uw和Uv共同評價過n個產(chǎn)品，那么這n個產(chǎn)品可以被看成n維向量空間，用戶Uw和Uv可以看成這空間中的兩個向量，通過向量夾角余弦(COS)[6]可以表示他們之間的相似度，如式(1):

(1)

式中Sim(Uw,Uv)代表用戶Uw與Uv的相似度，Iw和Iv代表用戶Uw和Uv各自評價過的產(chǎn)品(item)的集合，而用戶Uw、Uv對產(chǎn)品i的評分則用rwi、rvi表示。由此定義看出Sim(Uw,Uv)的值在 [0,1]區(qū)間，值越大表明用戶Uw與用戶Uv越相似。

1.2 皮爾遜相關(guān)系數(shù)相似度計算

皮爾遜相關(guān)系數(shù)PCC(PearsonCorrelationCoefficient)[5]同樣在相似度的計算中經(jīng)常被用到?；诒?，PCC被定義為：

(2)

式中Sim(Uw,Uv)為用戶Uw與Uv的相似度，Iw和Iv代表用戶Uw和Uv各自評價過的產(chǎn)品(item)的集合，而用戶Uw、Uv對產(chǎn)品i的評分則用rwi、rvi表示。據(jù)此定義，用戶相似度Sim(Uw,Uv)的值落在 [0,1] 區(qū)間,并且其值越大表明用戶Uw與用戶Uv越相似。

COS和PCC被提出來之后，Candillier[2]及一些研究者提出，COS和PCC相似度算法僅考慮了兩個用戶之間共同評價的部分。這有可能出現(xiàn)兩個用戶只共同評價過1個商品但卻是相似用戶的假象(例如，某一個用戶喜歡探險電影，另一個用戶喜歡科幻電影，他們之間沒有共同看過的電影，因此他們不是相似用戶。然而之后很巧他倆都看了一部相同的科幻探險類電影且都非常喜歡，那么通過COS相似度算法計算得出他們倆個是相似用戶。為了解決此問題，Candillier等人[2]在相似度的計算上融入兩個向量之間交疊程度并用式(3)卡德系數(shù)表示：

(3)

式中的Iw、Iv分別為用戶Uw、Uv評價過的產(chǎn)品(item)構(gòu)成的集合。通過將jaccard系數(shù)分別與PCC、COS相乘，CandilHer等人[2]演化出兩種相似度計算方法(以下簡稱JPCC、JCOS)。實驗證明了JPCC優(yōu)于其他三種相似度，這里給出JPCC的表達(dá)式：

(4)

1.3PIP相似度算法

為了緩解協(xié)同過濾的冷啟動問題，Ahn等人提出了PIP(Proximity-Impact-Popularity)[3,7]相似度算法。所謂冷啟動指的是在一個推薦系統(tǒng)中當(dāng)有新的產(chǎn)品或用戶或加入時，由于用戶沒有對產(chǎn)品有過評價，新的產(chǎn)品也很少被用戶評價過，造成產(chǎn)品不能被很好推薦給用戶，而用戶得不到好的推薦產(chǎn)品。PIP相似度算法表達(dá)式如式(5):

popularity(rw,i,rv,i)

(5)

其中proximity(rw,i,rv,i)是在兩個評分rwi,rvi的算術(shù)差值的基礎(chǔ)上，判斷兩個評分值是否相似，不相似時對這兩個用戶的相似度值進(jìn)行懲罰；impact(rw,i,rv,j)是在用戶w和用戶v對產(chǎn)品i喜歡(或討厭)程度的基礎(chǔ)上，判斷其對產(chǎn)品i喜歡(或討厭)程度，如果他們都對產(chǎn)品表現(xiàn)出很明顯的相同偏好，則對這兩個用戶的相似度值進(jìn)行獎勵；popularity(rw,i,rv,i)考慮了當(dāng)用戶對產(chǎn)品i評分值與其平均值差距較大時，則增大這兩個用戶的相似度值。

以下為式(5)中proximity(rw,i,rv,i)、impact(rw,i,rv,j)、popularity(rw,i,rv,i)3個因子的表達(dá)式。其中式(7)-式(9)中的agreement(rw,i,rw,i)的取值如式(6)所示：

(6)

(7)

(9)

根據(jù)Ahn等人的實驗結(jié)果，PIP對冷啟動問題的解決很有效，但在其他時候效果不佳[3,7]。

2 基于杰卡德皮爾遜相似度推薦算法的改進(jìn)

目前的協(xié)同過濾算法在相似度計算中通常不加選擇地使用早期和近期評價，而推薦系統(tǒng)在瀏覽記錄的時間數(shù)據(jù)獲取上存在不確定性、多源性。因此如果不考慮時間因素，忽略了用戶興趣的變化。那么隨著時間的推移推薦系統(tǒng)就不能更好地為給用戶提供有用的信息。為了解決這類問題，本文提出了杰卡德時間向量皮爾遜相似度算法JTVP(Jaccard Time Vector Pearson Similiarity Measurent)。JTVP基于同一時間向量空間中兩個時間向量之間的距離對用戶在同一或不同時期內(nèi)的產(chǎn)品評價給予激勵或衰減。

本算法是基于KNN(k-NearestNeighbor)算法模型預(yù)測用戶對未評價過的產(chǎn)品的喜好，結(jié)果越大表明越喜歡。其算法通常需要以下三個步驟：

(1) 通過相似性算法計算出當(dāng)前用戶與其他用戶之間的相似度；

(2) 從全部用戶中選擇K個與當(dāng)前用戶相似度最高的用戶并作為當(dāng)前用戶的鄰近相似集合[8]；

(3) 根據(jù)這K個最鄰近相似用戶對某產(chǎn)品的評分的均值預(yù)測當(dāng)前用戶對其產(chǎn)品的評分。

本文把興趣強(qiáng)度強(qiáng)弱變化設(shè)定在(0,5)之間。0表示極其討厭，5極其喜歡。圖1表示在用戶對某事物隨著時間變化其興趣強(qiáng)度的變化。

圖1 興趣強(qiáng)度維持曲線

從圖1興趣強(qiáng)度曲線可以看出在比較短的時間內(nèi)用戶A、用戶B、用戶C對同一件事都抱有很強(qiáng)的興趣，而本文可以認(rèn)為短期(0～3)內(nèi)這三個用戶是相似的用戶。但隨著時間的推移用戶對此事物的興趣發(fā)生了不同的變化，用戶A對此事物失去了興趣，用戶B依然保持很強(qiáng)的興趣，用戶C的興趣強(qiáng)度時而高時而低，用戶D的興趣強(qiáng)度是不斷的增加的。這時(在8～10時間段內(nèi))用戶BCD是相似用戶?，F(xiàn)在問題來了，假設(shè)用戶ABCD都對此事物給出了好的評價，但評價的時間點不一樣(如圖點狀標(biāo)注)。不考慮時間因素的話顯然ABCD都為相似用戶，但這是不準(zhǔn)確的。根據(jù)用戶興趣在一個短期的時間間隔內(nèi)保持穩(wěn)定但長期內(nèi)不同的用戶興趣會產(chǎn)生不同是波動的情況，本文提出了時間向量算子TVO(TimeVectorOperator)的概念。TVO對于用戶對產(chǎn)品的評價在時間上的不同給予其不同的權(quán)重，加大近期權(quán)重，減小久遠(yuǎn)的評價權(quán)重，從而讓推薦算法具有了在時間上的認(rèn)知。

為此本文給出了時間向量算子表達(dá)式：

(10)

之后用時間向量算子對用戶評價的產(chǎn)品加權(quán)，如式(11)和式(12)：

(11)

(12)

在給產(chǎn)品的評價加時間權(quán)重時，為了提高準(zhǔn)確度和減少不必要的計算時間，本文給產(chǎn)品的評價設(shè)立一個閾值L，如式(13)，只有大于L才給產(chǎn)品評價加上時間權(quán)重。

(13)

加入時間權(quán)重后使用改進(jìn)的皮爾遜相關(guān)系數(shù)相似性算法為用戶找出用戶鄰居：

(14)

最后產(chǎn)品的推薦分?jǐn)?shù)可以通過下式得出：

(15)

式中Score(i) 為目標(biāo)用戶度產(chǎn)品i的預(yù)測評價，Sim(Uw,Uv) 為用戶Uw、Uv之間的相似度，K表示相似鄰近用戶的個數(shù)，Svi為用戶Uv對產(chǎn)品i的評價。

最后把這些評分從高到低進(jìn)行排序，把TopN即前N個產(chǎn)品推薦給用戶。

3 實驗仿真

本節(jié)通過k-折交叉驗證來檢驗杰卡德時間向量皮爾遜相似度算法的推薦質(zhì)量，并驗證以下兩個問題：

(1) 數(shù)據(jù)集的不同對推薦的影響；

(2) 不同時間的梯度會對推薦效果造成何種影響。

驗證的具體過程如下：隨機(jī)地將數(shù)據(jù)分成k個大小相等且不相交的子集。其中k-1個集合作為訓(xùn)練集，剩下一個集合作為測試集。訓(xùn)練集用來預(yù)測測試集中用戶的評分并與測試集的數(shù)據(jù)相比較來判斷測試的準(zhǔn)確性。然后重復(fù)k次，目的是讓每個子集都作為測試集預(yù)測一遍，從而減小實驗的誤差，保證實驗的準(zhǔn)確性。最后，通過計算準(zhǔn)確率與召回率驗證方法的有效性。本實驗把數(shù)據(jù)分成了十份也可以說成十折交叉驗證。這種實驗的優(yōu)點是所有的集合都能輪流作為測試集驗證，仿真的可信度更高。

實驗使用的數(shù)據(jù)集是MovieLens(一種電影評分?jǐn)?shù)據(jù)集)。該推薦系統(tǒng)的評分是從0.5到5分，按0.5遞增。5分表明該用戶非常喜歡這部電影，而0.5表明該用戶對這部電影評價很差。

實驗環(huán)境：本課題的實驗是在Windows7系統(tǒng)下，IntelCorei7-4700HQ2.40GHz處理器，內(nèi)存4.0GB的PC機(jī)上進(jìn)行，采用MySQL數(shù)據(jù)庫存儲數(shù)據(jù)集，Java語言編程實現(xiàn)。

實驗用兩個MovieLens數(shù)據(jù)集(MovieLensl、MovieLens2)進(jìn)行驗證，其時間戳的跨度為10年，如表2所示。

表2 數(shù)據(jù)集

評價標(biāo)準(zhǔn)：實驗通過準(zhǔn)確率Precision、召回率Recall來對推薦質(zhì)量進(jìn)行評價。Precision指在所有的推薦中用戶喜歡的產(chǎn)品數(shù)占總的推薦產(chǎn)品數(shù)的比；Recall指在所有的推薦中用戶喜歡的產(chǎn)品數(shù)與推薦系統(tǒng)中用戶喜歡的所有產(chǎn)品數(shù)的比。其的形式化定義如式(16)、式(17)所示，符號的含義見表3所示。

表3 變量含義表

(16)

(17)

實驗中，使用MovieLens-l數(shù)據(jù)集時，時間梯度是以2009年開始以每次向后退2年的方式一直到2000年。即2009-2008(2009和2008兩年)，2009-2006，…，2009-2000，時間跨度T的取值則分別為2、4、6、8、10；使用MovieLens-2數(shù)據(jù)集時，同上以2015年開始以每次向后退2年，一直到2006年，時間跨度T的取值則為2、4、6、8、10。實驗結(jié)果，如圖2-圖5所示。

圖2 MovieLens-1中不同方法的準(zhǔn)確率對比

圖3 MovieLens-1中不同方法的召回率對比

圖4 MovieLens-1中不同方法的準(zhǔn)確率對比

圖5 MovieLens-2中不同方法的召回率對比

圖2和圖3表示使用MovieLens-1數(shù)據(jù)集時，在不同的時間梯度上四種相似度算法在準(zhǔn)確率和召回率上的對比結(jié)果。由圖可以看出隨著時間梯度的增加JPCC、PCC、COS推薦算法在準(zhǔn)確率和召回率上都出現(xiàn)了下滑趨勢。而JTVP推薦算法依然能保持較高的準(zhǔn)確率和召回率。

圖4和圖5表示使用MovieLens-2數(shù)據(jù)集時，在不同的時間梯度上四種相似度算法在準(zhǔn)確率和召回率上的對比結(jié)果。由于數(shù)據(jù)集的不同其準(zhǔn)確率和召回率在大體程度上存在些差異，但可以由圖看出JTVP推薦算法依然能保持較高的準(zhǔn)確率和召回率。而其他三種推薦算法在準(zhǔn)確率和召回率上依然出現(xiàn)了下滑的趨勢。

實驗結(jié)果表明加入時間向量算子的JTVP推薦算法能有效的解決隨著時間推移用戶興趣發(fā)生變化而帶來的推薦質(zhì)量的下滑問題。

4 結(jié) 語

針對用戶的興趣一般在短期的時間間隔內(nèi)保持穩(wěn)定但在長期時間跨度內(nèi)不同用戶的興趣變化是不確定的情況。本文提出了杰卡德時間向量皮爾遜相似度算法JTVP，采用時間向量算子tvo把用戶的評價加入時間認(rèn)知。同時，引入杰卡德系數(shù)對皮爾遜相關(guān)系數(shù)相似度模型對相似度算法加以完善提升，從而確定用戶相似度的最佳模型；然后對相似鄰近的用戶評價的產(chǎn)品進(jìn)行預(yù)測，選出最有可能被用戶接受的產(chǎn)品，并推薦給用戶。最后在時間梯度上把不同推薦算法的準(zhǔn)確度和召回率進(jìn)行比較、分析。實驗結(jié)果表明融入時間向量算子的JTVP推薦算法能有效地解決因用戶興趣變化而帶來的推薦質(zhì)量的下滑。從而說明本文提出的杰卡德時間向量皮爾遜相似度算法JTVP在應(yīng)對用戶興趣變化方面是有效并可行的。

隨著大數(shù)據(jù)時代的到來，網(wǎng)絡(luò)的規(guī)則將變得越來越完善，各大網(wǎng)絡(luò)公司的合作及數(shù)據(jù)共享會變得越來越頻繁。越來越多用戶將只需一個賬號就可以登錄各大網(wǎng)站，從而讓網(wǎng)站為自己提供自己的專屬服務(wù)。這時用戶-產(chǎn)品矩陣會更加密集，用戶的數(shù)據(jù)會更加豐富精確，融合時間向量算子的協(xié)同過濾推薦算法的準(zhǔn)確率將會得到進(jìn)一步的提升。

[1]LiWJ,XuYY,DongQ,etal.TaDb:Atime-awarediffusion-basedrecommenderalgorithm[J].InternationalJournalofModernPhysicsC,2015,26(9):5-9.

[2]CandillierL,MeyerF,FessantF.Designingspecificweightedsimilaritymeasurestoimprovecollaborativefilteringsystems[C]//IndustrialConferenceonAdvancesinDataMining:MedicalApplications,E-Commerce,Marketing,andTheoreticalAspects.Springer-Verlag,2008:242-255.

[3]AhnHJ.Anewsimilaritymeasureforcollaborativefilteringtoalleviatethenewusercold-startingproblem[J].InformationSciences,2008,178(1):37-51.

[4]WeiS,YeN,ZhangQ.Time-AwareCollaborativeFilteringforRecommenderSystems[M]//PatternRecognition,2012:663-670.

[5]ResnickP,IacovouN,SuchakM,etal.GroupLens:anopenarchitectureforcollaborativefilteringofnetnews[C]//Proceedingsofthe1994ACMConferenceonComputerSupportedCooperativeWork.ACM,1994:175-186.

[6]BreeseJS,HeckermanD,KadieC.Empiricalanalysisofpredictivealgorithmsforcollaborativefiltering[C]//FourteenthConferenceonUncertaintyinArtificialIntelligence,2013:43-52.

[7] 孫慧峰.基于協(xié)同過濾的個性化Web推薦[D].北京:北京郵電大學(xué),2012.

[8] 項亮.推薦系實踐[M].北京:人民郵電出版社,2012:36-73.

[9] 成軍.面向電子商務(wù)的協(xié)同過濾推薦算法與推薦系統(tǒng)研究[D].南京:南京理工大學(xué),2013.

RESEARCH ON DYNAMIC MULTI SOURCE TIME COGNITIVE RECOMMENDATION ALGORITHM

Li Jingzhao1,2Zhu Dongjun2Tan Dayu2

1(FacultyofElectricalandInformationEngineering,AnhuiUniversityofScienceandTechnology,Huainan232001,Anhui,China)2(FacultyofComputerScienceandEngineering,AnhuiUniversityofScienceandTechnology,Huainan232001,Anhui,China)

A good recommendation algorithm is becoming very important in today’s intelligent web applications. In this paper, we propose a time cognitive recommendation algorithm. Traditional recommendation algorithms often use early and recent evaluations indiscriminately, ignoring user interest changes over time. And user interests remain stable over short periods of time but change over a long period of time. Based on the existing cooperative filtering recommendation algorithm, the time vector factor is used to motivate the recent records or weaken the early records in order to achieve the purpose of more effective classification of similar interests. The results show that the proposed method can effectively improve the accuracy and efficiency in the intelligent web.

Intelligent web Time vector factor Collaborative filtering recommendation User interest changes

2016-07-21。國家自然科學(xué)基金項目(61170060)；安徽省學(xué)術(shù)與技術(shù)帶頭人學(xué)術(shù)科研活動資助項目(2015D046)；安徽省高等學(xué)校優(yōu)秀拔尖人才項目(gxbjZD2016044)。李敬兆，教授，主研領(lǐng)域：機(jī)器學(xué)習(xí)。朱東郡，碩士生。譚大禹，碩士生。

TP39

A

10.3969/j.issn.1000-386x.2017.02.010