結(jié)合評(píng)分時(shí)間和用戶空間的協(xié)同過濾推薦算法

李 炎 艾 均 蘇 湛

(上海理工大學(xué)光電信息與計(jì)算機(jī)工程學(xué)院 上海 200093)

0 引 言

隨著科學(xué)技術(shù)和計(jì)算機(jī)應(yīng)用的高速發(fā)展，人類進(jìn)入了信息爆炸的時(shí)代。面對(duì)海量的信息，用戶需要根據(jù)其信息需求投入大量的時(shí)間進(jìn)行信息過濾和信息選擇，產(chǎn)生了信息過載問題[1]。推薦系統(tǒng)是解決這個(gè)問題行之有效的方法，并且在這些年發(fā)展迅速。推薦系統(tǒng)根據(jù)用戶的信息需求，為其提供個(gè)性化的推薦，在海量的信息空間中，為用戶推薦有用的信息[2]。目前推薦系統(tǒng)主要包括基于協(xié)同過濾的推薦[3-4]，基于內(nèi)容的推薦技術(shù)[5]，基于網(wǎng)絡(luò)的推薦技術(shù)[6]和混合推薦技術(shù)[7-9]四類。目前應(yīng)用廣泛且頗受歡迎的是協(xié)同過濾推薦算法，在物品推薦的過程中只依賴推薦的社交性而不需要關(guān)注物品的信息就可以實(shí)現(xiàn)推薦。

協(xié)同過濾推薦算法通常根據(jù)用戶行為計(jì)算每一對(duì)對(duì)象的相似度度量，并向相似的用戶推薦一個(gè)類似的項(xiàng)目。例如，如果用戶A與用戶B相似，那么兩個(gè)用戶在項(xiàng)目上做了相同的評(píng)價(jià)，而用戶B喜歡項(xiàng)目C，但是用戶A還沒有對(duì)項(xiàng)目C進(jìn)行評(píng)價(jià)，那么此算法可以假定用戶A喜歡項(xiàng)目C，并將其推薦給用戶A。該過程的核心步驟包括計(jì)算對(duì)象相似度，根據(jù)相似度選擇對(duì)象的鄰居，并根據(jù)鄰居的評(píng)級(jí)來(lái)預(yù)測(cè)評(píng)級(jí)。

傳統(tǒng)上，網(wǎng)絡(luò)科學(xué)一直專注于靜態(tài)網(wǎng)絡(luò)來(lái)探索鏈接預(yù)測(cè)。也就是說，在計(jì)算過程中，類似的方法會(huì)將節(jié)點(diǎn)之間的連接持久化。然而，越來(lái)越多的人認(rèn)識(shí)到，大多數(shù)推薦系統(tǒng)最好被描述為時(shí)間網(wǎng)絡(luò)，其中的鏈接只是間歇性的或有一定的重量衰減。另外，在推薦系統(tǒng)中節(jié)點(diǎn)的空間分布很少是科學(xué)家考慮的因素，因?yàn)橥負(fù)浣Y(jié)構(gòu)不保持任何空間信息或位置約束，并影響相似計(jì)算的結(jié)果。很多學(xué)者針對(duì)時(shí)序方面提出了一系列的方案。文獻(xiàn)[10]結(jié)合物品信息和情境上下文信息，發(fā)現(xiàn)情境上下文在提高推薦質(zhì)量上有明顯作用。文獻(xiàn)[11]提出結(jié)合上下文信息得到的結(jié)果更容易獲得用戶信任。文獻(xiàn)[12]提出時(shí)間物品提前過濾的方法，也就是說選擇與目標(biāo)時(shí)間相同的評(píng)分信息當(dāng)作訓(xùn)練集去訓(xùn)練推薦模型的算法。文獻(xiàn)[13]提出結(jié)合用戶行為的時(shí)間信息對(duì)于提高推薦質(zhì)量有明顯作用。文獻(xiàn)[14]提出的即時(shí)推薦系統(tǒng)能夠提供量身定制的推薦列表，充分滿足用戶的需求，幫助他們獲得有用的信息以及大數(shù)據(jù)空間里感興趣的資源。但以上算法主要研究了用戶行為時(shí)間特性，而忽略了用戶所處的空間對(duì)于推薦的影響，所以本文利用用戶行為的時(shí)間特性和用戶空間因素，采用結(jié)合評(píng)分時(shí)間和用戶空間的方法對(duì)推薦算法進(jìn)行研究。

在現(xiàn)實(shí)生活中，用戶的興趣會(huì)隨著時(shí)間的變化而改變，用戶最近的評(píng)分相比用戶以前的評(píng)分更能體現(xiàn)用戶的興趣點(diǎn)。所以在進(jìn)行用戶相似性計(jì)算時(shí)，對(duì)用戶評(píng)分進(jìn)行時(shí)間衰減，將原來(lái)單一評(píng)分改為相對(duì)時(shí)間的評(píng)分來(lái)降低歷史評(píng)分對(duì)推薦的影響力，相應(yīng)地增加最近評(píng)分對(duì)推薦的影響力。這樣用戶評(píng)分的時(shí)間特性對(duì)推薦的作用得以體現(xiàn)。

對(duì)于空間，假設(shè)用戶在這樣的推薦系統(tǒng)中構(gòu)建一個(gè)隱藏的社交網(wǎng)絡(luò)，每?jī)蓚€(gè)用戶之間的連接就會(huì)推斷出他們的品味或者友誼，以及用戶在一個(gè)空間中的分布情況。在每個(gè)用戶的空間約束下，可以通過使用用戶之間的距離來(lái)選擇鄰居，而不是通過相似性。本文把用戶抽象成網(wǎng)絡(luò)節(jié)點(diǎn)，用戶之間的相似度作為用戶之間連接的邊權(quán)重，利用復(fù)雜網(wǎng)絡(luò)拓?fù)洳季炙惴╗15]建立用戶空間網(wǎng)絡(luò)布局。通過用戶空間布局計(jì)算所有用戶之間的空間距離，根據(jù)用戶空間距離選取一定數(shù)量的鄰居用戶，最終計(jì)算用戶對(duì)未評(píng)分物品的預(yù)測(cè)評(píng)分值。

1 研究方法

1.1 協(xié)同過濾推薦算法

協(xié)同過濾推薦算法一般分為兩種類型：一種是基于用戶的協(xié)同推薦(UBCF)，另一種是基于項(xiàng)目的協(xié)同推薦(IBCF)[3-4]。

UBCF算法從用戶角度出發(fā)，計(jì)算用戶相似度，從而確定目標(biāo)用戶的鄰居用戶，為目標(biāo)用戶進(jìn)行項(xiàng)目推薦。

IBCF算法從項(xiàng)目角度出發(fā)，計(jì)算項(xiàng)目相似度，從而確定該項(xiàng)目的相似項(xiàng)目，為用戶進(jìn)行項(xiàng)目推薦。

UBCF算法主要通過以下5個(gè)步驟實(shí)現(xiàn)物品的推薦：

(1) 初始化用戶行為信息，建立用戶評(píng)分矩陣；

(2) 通過相似度公式計(jì)算用戶相似度；

(3) 根據(jù)用戶相似度結(jié)果，選取目標(biāo)用戶的鄰居用戶；

(4) 求出用戶對(duì)物品的預(yù)測(cè)評(píng)分，生成評(píng)分預(yù)測(cè)矩陣；

(5) 根據(jù)評(píng)分預(yù)測(cè)矩陣，選擇前N個(gè)項(xiàng)目組成推薦物品集合進(jìn)行Top-N推薦。

推薦系統(tǒng)中用戶集合為U={ui|1≤i≤m}，表示有m個(gè)用戶，物品集合為O={oj|1≤j≤n}，表示有n個(gè)物品。用戶的評(píng)分矩陣集合為R={ria}∈Rm,n，其中ria表示用戶i對(duì)物品α的評(píng)分值，評(píng)分值的差異反映了用戶對(duì)物品興趣度。另外設(shè)置一個(gè)與評(píng)分矩陣集合對(duì)應(yīng)的集合A={aiα}∈Rm,n，若用戶i對(duì)物品α評(píng)過分，則aiα為1，否則為0。表1即為UBCF算法的用戶-物品評(píng)分矩陣模型。雖然表1顯示了用戶對(duì)物品的行為信息，但用戶行為的時(shí)間特性并沒有表現(xiàn)出來(lái)。

表1 用戶-物品評(píng)分矩陣

UBCF算法通過用戶相似度確定用戶的鄰居用戶。本文采用基于用戶的皮爾遜相似度計(jì)算公式計(jì)算用戶相似度[16],公式如下：

(1)

UBCF算法選擇相似度最高的前m個(gè)用戶作為其鄰居用戶，構(gòu)成鄰居用戶集合Ti。由于已知用戶相似度以及鄰居用戶的評(píng)分信息，利用式(2)對(duì)目標(biāo)用戶ui的所有未評(píng)分物品oj進(jìn)行評(píng)分預(yù)測(cè)。

(2)

1.2 基于時(shí)間和空間的用戶相似算法

考慮到一個(gè)包含n個(gè)節(jié)點(diǎn)和m條邊的復(fù)雜網(wǎng)絡(luò)G，我們認(rèn)為網(wǎng)絡(luò)G分布在一個(gè)空間區(qū)域內(nèi)。其中t表示G的時(shí)間屬性，而且節(jié)點(diǎn)代表推薦系統(tǒng)中的用戶，邊代表用戶之間的連接，比如用戶之間的相似性。

基于時(shí)空的推薦算法由以下規(guī)則組成：

規(guī)則1初始化用戶之間的連接。

規(guī)則2初始化用戶之間的位置。

規(guī)則3用戶對(duì)物品的評(píng)分改變了它們的連接和位置。

規(guī)則4用戶對(duì)物品的評(píng)分隨著時(shí)間的變化而有一定程度的衰減。

規(guī)則5對(duì)于用戶的評(píng)分預(yù)測(cè)，其對(duì)項(xiàng)目的評(píng)分取決于項(xiàng)目的平均評(píng)分和用戶最近鄰居的評(píng)分。

把用戶集合U中所有用戶抽象成網(wǎng)絡(luò)節(jié)點(diǎn),記用戶節(jié)點(diǎn)數(shù)n，通過式(1)計(jì)算用戶之間的相似度S(i,j)，把用戶之間的相似度作為用戶節(jié)點(diǎn)之間連接的邊權(quán)重，記用戶之間的連接邊為m。利用復(fù)雜網(wǎng)絡(luò)拓?fù)洳季炙惴ń⒂脩糁g的網(wǎng)絡(luò)布局。由于數(shù)據(jù)量龐大，本文對(duì)用戶網(wǎng)絡(luò)布局中的邊進(jìn)行篩選，公式如下：

(3)

以k=1為例，用戶空間網(wǎng)絡(luò)布局如圖1所示。

圖1 k=1時(shí)用戶網(wǎng)絡(luò)布局

在用戶空間網(wǎng)絡(luò)布局中，對(duì)于每一個(gè)用戶ui都會(huì)生成一個(gè)坐標(biāo)(xui，yui，zui)，因此，利用歐幾里得距離公式可以計(jì)算出相關(guān)聯(lián)用戶之間的空間距離，公式如下：

(4)

對(duì)用戶空間距離升序排列，用戶之間距離越小，說明用戶之間相關(guān)聯(lián)程度越高。取出與目標(biāo)用戶距離最近的前m個(gè)用戶作為其鄰居用戶集合TDi。

例如，有10個(gè)用戶，用戶編號(hào)為1到10，其中用戶1為目標(biāo)用戶，其余9個(gè)用戶為用戶1的相似用戶，取用戶1的5個(gè)鄰居用戶。用戶相似度如表2所示。

表2 用戶1與其余用戶相似度

本文對(duì)于鄰居用戶的選擇是基于用戶空間距離，有別于傳統(tǒng)的基于用戶相似度選取鄰居用戶的規(guī)則。用戶1的空間布局如圖2所示。

圖2 用戶1的空間布局

圖2清晰地展示了用戶1與其余用戶的拓?fù)浣Y(jié)構(gòu)圖。用戶之間的空間距離也能直觀地顯示在圖中，并且距離越近的鄰居，與用戶1的連邊越清晰。

本文使用拓?fù)洳季炙惴?，為空間中每個(gè)用戶生成空間坐標(biāo)。利用式(4)，計(jì)算用戶1與其他用戶的空間距離。需要說明的是，對(duì)于沒有連邊的用戶，即使也有相應(yīng)的空間坐標(biāo)，但是默認(rèn)與用戶1的空間距離無(wú)限大。用戶1與其他用戶空間距離如表3所示。對(duì)表中與用戶1的空間距離進(jìn)行升序排序，由于取用戶1的前5個(gè)鄰居，故取與用戶1距離最小的前5個(gè)用戶，分別為7，5，8，6，4。

表3 用戶1與其余用戶的空間距離

對(duì)于用戶評(píng)分的時(shí)間效應(yīng)，本文引入時(shí)間衰減函數(shù)，公式如下：

(5)

式中：t為推薦時(shí)間；t(riα)為用戶i對(duì)物品α的評(píng)分的時(shí)間信息；γ為時(shí)間衰減因子，取值為[0,1)之間的小數(shù)。當(dāng)衰減因子γ遞增時(shí)，衰減函數(shù)w(t,t(riα))呈遞減趨勢(shì)，當(dāng)γ越大時(shí)，說明時(shí)間的影響越大，可以動(dòng)態(tài)的調(diào)整γ值來(lái)優(yōu)化推薦結(jié)果。當(dāng)衰減因子γ=0時(shí)，公式?jīng)]有衰減，即不考慮時(shí)間因素，僅考慮用戶空間因素對(duì)推薦結(jié)果的影響，這種情況需要與衰減后的情況進(jìn)行對(duì)比。

式(5)按照歷史評(píng)分產(chǎn)生的時(shí)間對(duì)評(píng)分的重要性進(jìn)行了衰減，生成用戶-物品的衰減評(píng)分值RT(ui,oj)。

1.3 算法基本思想

根據(jù)以上描述，本文的算法思想如下：

輸入：<用戶(user)，物品(item)，用戶行為(rating)，時(shí)間戳(TimeStamp)>。

輸出：預(yù)測(cè)評(píng)分值矩陣

步驟1根據(jù)用戶對(duì)物品的評(píng)分信息建立“用戶-物品-評(píng)分-時(shí)間”模型。

步驟2利用式(1)計(jì)算用戶相似度S(i,j)，利用復(fù)雜網(wǎng)絡(luò)拓?fù)洳季炙惴ń⒂脩艨臻g網(wǎng)絡(luò)布局，并且為每一個(gè)用戶生成空間坐標(biāo)(xui,yui,zui)。

步驟3利用式(4)計(jì)算所有用戶之間的空間距離D(ui,vi)，然后選取前m個(gè)用戶作為其鄰居用戶集合TDi。

步驟4在用戶-物品-評(píng)分-時(shí)間模型中，利用式(5)，計(jì)算用戶-物品的衰減評(píng)分值RT(ui,oj)，再利用式(1)計(jì)算評(píng)分衰減之后的用戶相似度ST(i,j)。

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

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

在數(shù)據(jù)集選取方面，MovieLens數(shù)據(jù)集不僅記錄了943個(gè)用戶對(duì)1 682部電影的100 000條評(píng)分[17]，而且記錄了用戶行為的時(shí)間戳信息，所以可以作為實(shí)驗(yàn)的數(shù)據(jù)集。

實(shí)驗(yàn)將數(shù)據(jù)集劃分為訓(xùn)練數(shù)據(jù)集和測(cè)試數(shù)據(jù)集，其中訓(xùn)練數(shù)據(jù)集占80%，測(cè)試數(shù)據(jù)集占20%。這樣有利于減少偶然因素帶來(lái)的不利影響，保證實(shí)驗(yàn)的準(zhǔn)確性。為了檢驗(yàn)結(jié)合評(píng)分時(shí)間和用戶空間的協(xié)同過濾推薦算法(TS)的有效性，本文用基于皮爾遜用戶協(xié)同過濾算法(UCF-Pearson-Opt)和基于皮爾遜物品協(xié)同過濾算法(ICF-Pearson-Opt)作為對(duì)比[18]。

在實(shí)驗(yàn)結(jié)果對(duì)比中，鄰居個(gè)數(shù)選擇從10開始，直到150，每次增加10。需要說明的是，鄰居個(gè)數(shù)為5的對(duì)比結(jié)果也一并列出。

2.2 評(píng)價(jià)指標(biāo)與結(jié)果及分析

(6)

(7)

實(shí)驗(yàn)使用MAE值和RMSE值度量推薦算法的準(zhǔn)確度，MAE值和RMSE值越小，說明準(zhǔn)確度越高。

本文提出的算法中，衰減系數(shù)γ是至關(guān)重要的參數(shù)。因此，首先通過實(shí)驗(yàn)研究了衰減系數(shù)γ對(duì)推薦結(jié)果的影響，選取最優(yōu)的衰減系數(shù)。評(píng)價(jià)指標(biāo)結(jié)果如圖3和圖4所示。

圖3 算法的MAE值隨著的變化

圖4 算法的RMSE值隨著的變化

在圖3和圖4中，橫坐標(biāo)均代表衰減因子γ，縱坐標(biāo)分別代表MAE值和RMSE值?？梢钥闯?，當(dāng)衰減因子從0增加到0.9時(shí)，MAE值和RMSE值波動(dòng)比較大。當(dāng)衰減系數(shù)γ=0.1時(shí)，MAE值和RMSE值均取最小值。

為了比較不同算法的預(yù)測(cè)效果，計(jì)算UCF-Pearson-Opt和ICF-Pearson-Opt與本文提出的TS在不同鄰居數(shù)目的平均絕對(duì)誤差和均方根誤差。需要說明的是，當(dāng)衰減系數(shù)γ=0時(shí)，即沒有考慮時(shí)間因素，僅考慮在用戶網(wǎng)絡(luò)布局中，空間距離因素對(duì)于推薦算法結(jié)果的影響。結(jié)果分別如圖5和圖6所示。

圖5 三種算法的MAE值，TS為本文算法

圖6 三種算法的RMSE值，TS為本文算法

在圖5和圖6中，橫坐標(biāo)均代表目標(biāo)用戶的鄰居用戶數(shù)目，縱坐標(biāo)分別代表MAE值和RMSE值?？梢钥闯?，本文所使用的TS算法在衰減因子γ=0.1時(shí)效果最好，在目標(biāo)用戶鄰居數(shù)目為5時(shí)MAE值最低，為0.340 102 736；當(dāng)鄰居數(shù)目為80時(shí)RMSE最低，為0.508 920 893，并且隨著用戶相似鄰居數(shù)目的增長(zhǎng)，曲線呈水平增長(zhǎng)，說明TS算法的穩(wěn)定性較好。

TS算法在衰減系數(shù)γ=0.1時(shí)的誤差比ICF-Pearson-Opt算法更低，MAE值提高了38%，RMSE值提高了41%，說明了本文算法的有效性。當(dāng)衰減因子γ時(shí)，隨著鄰居數(shù)目的增加，MAE值和RMSE值由遠(yuǎn)遠(yuǎn)高于UCF-Pearson-Opt和ICF-Pearson-Opt算法逐漸歸為持平狀態(tài)，說明在僅考慮用戶空間因素方面還有待改進(jìn)和優(yōu)化。

3 結(jié) 語(yǔ)

結(jié)合三種算法的結(jié)果可知，TS算法在衰減系數(shù)γ=0時(shí)，推薦效果并不顯著。當(dāng)衰減系數(shù)γ=0.1時(shí)效果最好，相比ICF-Pearson-Opt算法，MAE值提高了38%，RMSE值提高了41%。綜上所述，在MovieLens數(shù)據(jù)集上，通過實(shí)驗(yàn)證明，與傳統(tǒng)的協(xié)同過濾算法比較，本文所用算法的準(zhǔn)確率有顯著提高，并且算法的時(shí)間復(fù)雜度較低。