張艷梅,王 璐

(中央財(cái)經(jīng)大學(xué)信息學(xué)院,北京100081)

適應(yīng)用戶興趣變化的社會(huì)化標(biāo)簽推薦算法研究

張艷梅,王 璐

(中央財(cái)經(jīng)大學(xué)信息學(xué)院,北京100081)

目前許多基于社會(huì)化標(biāo)簽的推薦均忽視用戶的興趣變化及反復(fù)性,影響了推薦質(zhì)量。針對(duì)該問題,提出一種將指數(shù)遺忘權(quán)重和時(shí)間窗口相結(jié)合的算法,既突出了近期興趣的重要性,又強(qiáng)調(diào)了反復(fù)出現(xiàn)的早期數(shù)據(jù)。建立基準(zhǔn)標(biāo)簽集,根據(jù)指數(shù)偏移后的標(biāo)簽向量選出目標(biāo)用戶的最近鄰居,通過目標(biāo)用戶時(shí)間窗內(nèi)標(biāo)記的資源計(jì)算其所有資源的推薦權(quán)重向量,結(jié)合推薦權(quán)重和資源相似度給出最近鄰居標(biāo)記資源的推薦分?jǐn)?shù),取分?jǐn)?shù)最高的前K個(gè)資源做出推薦。仿真實(shí)驗(yàn)結(jié)果表明,改進(jìn)后的算法能動(dòng)態(tài)地跟蹤、學(xué)習(xí)用戶的興趣變化,提高推薦精度。

協(xié)同過濾;標(biāo)簽;興趣變化;指數(shù)遺忘;時(shí)間窗;推薦

1 概述

近年來(lái),互聯(lián)網(wǎng)規(guī)模及Web2.0迅速發(fā)展,大量有用信息和垃圾數(shù)據(jù)充斥著網(wǎng)絡(luò),面對(duì)信息過載問題,信息檢索領(lǐng)域迫切需要個(gè)性化推薦服務(wù)為用戶提供有價(jià)值信息,完善用戶體驗(yàn),使用戶由被動(dòng)的信息瀏覽者轉(zhuǎn)變?yōu)橹鲃?dòng)的參與者。當(dāng)前主流的推薦方法包括協(xié)同過濾推薦［1］、基于內(nèi)容推薦［2］、基于圖結(jié)構(gòu)的推薦［3］、混合推薦［4］等。其中,協(xié)同過濾技術(shù)是實(shí)際應(yīng)用中使用最廣泛的推薦技術(shù)［5］。聯(lián)系用戶和資源,標(biāo)簽就是其中一種,它既能表現(xiàn)用戶的興趣取向,同時(shí)還能體現(xiàn)資源的屬性特征。文獻(xiàn)［6-7］的研究顯示標(biāo)簽可以準(zhǔn)確顯示用戶對(duì)網(wǎng)頁(yè)內(nèi)容的判斷,同時(shí)標(biāo)簽也是描述資源的一種好方法。目前,社會(huì)化標(biāo)簽系統(tǒng)越來(lái)越流行,比如 MovieLens,Flickr, del.icio.us,Citeulike,國(guó)內(nèi)的豆瓣網(wǎng)站等。

標(biāo)簽反映了用戶對(duì)物品的看法,是一種重要的用戶行為,也是反映用戶興趣的數(shù)據(jù)來(lái)源。處理用戶興趣變化的方法主要有2種:時(shí)間窗口法和遺忘函數(shù)法［8］,其中時(shí)間窗口法利用滑動(dòng)時(shí)間窗反映用戶近期興趣及反復(fù)興趣;遺忘函數(shù)法則利用遺忘函數(shù)對(duì)用戶的興趣權(quán)重進(jìn)行衰減,從而得到真正的興趣趨勢(shì)。

文獻(xiàn)［9］首先使用線性遺忘函數(shù)并引入了漸進(jìn)遺忘的思想。文獻(xiàn)［10］用冪函數(shù)曲線跟蹤模擬用戶興趣,將基于時(shí)間窗與基于資源相似度的數(shù)據(jù)權(quán)重結(jié)合起來(lái)反映用戶的興趣度,但沒有考慮標(biāo)簽這一聯(lián)系用戶和資源的主要因素。文獻(xiàn)［11］通過指數(shù)遺忘函數(shù)衰減用戶興趣模型,以捕獲用戶興趣的變化,擬合記憶遺忘機(jī)制,但忽視了興趣的反復(fù)性與穩(wěn)定性,未能準(zhǔn)確跟蹤用戶興趣變化。針對(duì)現(xiàn)有的基于標(biāo)簽協(xié)同過濾算法不能快速、準(zhǔn)確地反映用戶興趣變化趨勢(shì)的問題［12］,本文在社會(huì)化標(biāo)簽推薦的基礎(chǔ)上,綜合處理用戶興趣變化的2種方法,提出一種適應(yīng)用戶興趣變化的標(biāo)簽推薦算法(User Interest Change-tagging Collaborative Filtering,UIC-TCF)。

2 UIC-TCF算法描述

UIC-TCF算法大致分為2個(gè)階段:首先根據(jù)偏移后的用戶標(biāo)簽矩陣選出相似度最高的N個(gè)鄰居用戶,然后將這N個(gè)用戶標(biāo)記過的資源與目標(biāo)用戶最近一段時(shí)間內(nèi)標(biāo)記的資源一一計(jì)算相似度,取相似度最高的K個(gè)資源推薦給目標(biāo)用戶,兩階段中相似度均通過基準(zhǔn)標(biāo)簽集來(lái)計(jì)算。

2.1 最近鄰居選取

給定目標(biāo)用戶u0后,u0使用過的標(biāo)簽集合構(gòu)成基準(zhǔn)標(biāo)簽集T=(t1,t2,…,tn)。使用過基準(zhǔn)標(biāo)簽集中至少一個(gè)標(biāo)簽ti的用戶集合稱為候選用戶集。用戶的標(biāo)簽權(quán)重向量中每個(gè)標(biāo)簽ti的權(quán)重由TF-IDF加權(quán)方案得出。一般來(lái)說(shuō),用戶近期標(biāo)記資源對(duì)生成未來(lái)可能感興趣的資源起相對(duì)重要的作用,而早期的標(biāo)記記錄對(duì)推薦影響相對(duì)較小。因此,為擬合人腦的遺忘規(guī)律,本文采用指數(shù)遺忘曲線以提高近期標(biāo)記資源的重要性。

定義1(用戶標(biāo)簽向量) 設(shè)基準(zhǔn)標(biāo)簽集T中有n個(gè)標(biāo)簽。用戶uj的標(biāo)簽權(quán)重向量:

定義2(指數(shù)偏移權(quán)重) 用戶uj在標(biāo)簽ti上的偏移權(quán)重為:

其中,?為衰減系數(shù),0＜?＜1;Datebegin為用戶uj開始使用標(biāo)簽系統(tǒng)的時(shí)間;Datelast為用戶uj最后一次使用標(biāo)記系統(tǒng)的時(shí)間;Datei為用戶uj最后一次使用標(biāo)簽ti的時(shí)間。

定義3(偏移后的用戶標(biāo)簽向量) 偏移后用戶uj的標(biāo)簽向量為:

定義4(用戶相似度) 目標(biāo)用戶u0與比對(duì)用戶uj之間的余弦相似度公式為:

2.2 資源推薦

使用指數(shù)衰減后,用戶近期標(biāo)記資源的權(quán)重總是大于早期標(biāo)記記錄的權(quán)重,從而突出了近期數(shù)據(jù)的重要性。但一般情況下,不同用戶興趣變化速度和趨勢(shì)不同。此外,用戶興趣還會(huì)經(jīng)常表現(xiàn)出反復(fù)性,所以用戶早期的標(biāo)記數(shù)據(jù)往往對(duì)于生成推薦也很重要,單純使用指數(shù)函數(shù)衰減權(quán)重,削弱所有早期資源在推薦生成中的作用,可能會(huì)降低推薦效果。

設(shè)用戶u0標(biāo)記過的資源集合為Iu。設(shè)定一個(gè)時(shí)間窗win,得到目標(biāo)用戶最近一段時(shí)間win內(nèi)標(biāo)記資源集合Iwin,該集合內(nèi)的資源一定程度上反映了用戶近期的興趣偏好。無(wú)論資源標(biāo)記時(shí)間早晚,只要和Iwin的相似度較高,說(shuō)明該資源和用戶當(dāng)前的興趣很相關(guān),即有較高的推薦權(quán)重,依次算出Iu中每一資源對(duì)u0的推薦權(quán)重。在上一步最近鄰居用戶選定后,獲取鄰居用戶訪問資源,構(gòu)成候選推薦資源集合,結(jié)合推薦權(quán)重和資源相似度算出推薦分?jǐn)?shù),給出TOP-K推薦。

定義5(資源的標(biāo)簽向量) 資源Rx的標(biāo)簽權(quán)重向量為:

定義6(資源相似度) 資源q與資源k間的余弦相似度為:

2.3 推薦算法

推薦算法描述如下:

定義8(資源推薦分?jǐn)?shù)) 鄰居用戶標(biāo)記過的資源X對(duì)目標(biāo)用戶u0的推薦分?jǐn)?shù)為:

輸入 用戶標(biāo)記項(xiàng)的矩陣;m:候選用戶數(shù);n:社區(qū)用戶數(shù);win:時(shí)間窗;u0:用戶

輸出 推薦給u0的分?jǐn)?shù)最高的K個(gè)資源列表

Step1 標(biāo)準(zhǔn)標(biāo)簽集初始化T=(t1,t2,…,tn);

Step2 為u0創(chuàng)建標(biāo)簽矢量ut0,乘以指數(shù)抵消標(biāo)簽矢量,then得到ut′0;

Step3 For j=1 to m-1

Step4 對(duì)sim(u0,uj)降序排列,then得到分?jǐn)?shù)最高的N個(gè)鄰居;

Step5 Iwin=GetLatestItemSet(u0,win); Step6 For q=1 to Length(Itemu0)

Step8 降序排列rec(u0,x),產(chǎn)生推薦給u0的分?jǐn)?shù)最好的K個(gè)資源列表。

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

3.1 實(shí)驗(yàn)環(huán)境

本文用Citeulike提供的公開數(shù)據(jù)集作為實(shí)驗(yàn)數(shù)據(jù)對(duì)UIC-TCF算法與傳統(tǒng)的基于用戶的協(xié)同過濾算法(記為CF)作比較。Citeulike是一個(gè)專門為學(xué)術(shù)研究人員提供分享、存儲(chǔ)、組織學(xué)術(shù)文章的社會(huì)化書簽網(wǎng)站,每條記錄包括＜用戶,論文,標(biāo)簽,時(shí)間＞4個(gè)字段。對(duì)獲取的數(shù)據(jù)進(jìn)行預(yù)處理,刪除使用用戶數(shù)量小于20的標(biāo)簽以及使用標(biāo)簽種類小于20的用戶,同時(shí)由于用戶的興趣在較短的時(shí)間內(nèi)是相對(duì)穩(wěn)定的,興趣變化只能在一段時(shí)間內(nèi)體現(xiàn),因此刪除那些只在短期內(nèi)(Datelast-Datebegin＜30天)使用過標(biāo)簽系統(tǒng)的用戶數(shù)據(jù)。最終從以上數(shù)據(jù)集中選取847個(gè)用戶對(duì)3 597個(gè)項(xiàng)目的評(píng)分記錄,以及相應(yīng)的133個(gè)頻繁標(biāo)簽。其中,把每個(gè)用戶最近30%的數(shù)據(jù)作為測(cè)試集,剩下的70%作為訓(xùn)練集。實(shí)驗(yàn)運(yùn)行環(huán)境為:Windows XP操作系統(tǒng),CPU主頻2.26 GHz,2 GB內(nèi)存,Eclipse開發(fā)平臺(tái),SQL Server 2000數(shù)據(jù)庫(kù)。

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

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

為了檢驗(yàn)UIC-TCF算法效果,將UIC-TCF算法與傳統(tǒng)基于用戶的協(xié)同過濾算法作比較,對(duì)比在推薦不同數(shù)目時(shí),2種方法準(zhǔn)確率的變化情況。設(shè)置了3組實(shí)驗(yàn),實(shí)驗(yàn)過程中推薦個(gè)數(shù)由5逐步增長(zhǎng)到20,間隔為5。以下所有實(shí)驗(yàn)中,最近鄰居數(shù)目均取為10。

圖1顯示了衰減系數(shù)?不同取值時(shí)UIC-TCF算法與傳統(tǒng)協(xié)同過濾算法推薦準(zhǔn)確率的對(duì)比。其中,時(shí)間窗win=10,?分別為0.3,0.5,0.7。

圖1 不同?取值下算法準(zhǔn)確率的對(duì)比

通過圖1可以看出,本文算法明顯優(yōu)于傳統(tǒng)協(xié)同過濾算法。在準(zhǔn)確率指標(biāo)下,推薦數(shù)目越少,本文算法的優(yōu)勢(shì)越明顯。同時(shí),衰減系數(shù)?的取值對(duì)實(shí)驗(yàn)結(jié)果也有較大影響。由于存在不同種類的標(biāo)簽、資源,同時(shí)用戶興趣的變化速度和變化規(guī)律也不同,權(quán)重增長(zhǎng)過快或過慢都會(huì)降低推薦精度。在?=0.5時(shí),算法性能達(dá)到最優(yōu)。如在推薦數(shù)目為5,?=0.5時(shí),推薦準(zhǔn)確度提升了約54.8%。同時(shí),隨著推薦數(shù)量的增加,UIC-TCF算法的性能并沒有迅速下降,而是與傳統(tǒng)協(xié)同過濾算法保持穩(wěn)定的推薦精度差值。

圖2顯示了時(shí)間窗win的取值對(duì)推薦效果的影響。實(shí)驗(yàn)依次取win=5天,10天,15天,其中,?=0.5。

圖2 不同w i n值下算法準(zhǔn)確率對(duì)比

從圖2可以看出，w i n的取值會(huì)對(duì)推薦結(jié)果產(chǎn)生一定影響。因?yàn)橥ㄟ^設(shè)置時(shí)間窗w i n來(lái)截取目標(biāo)用戶最近使用過的標(biāo)簽，通過這些標(biāo)簽找到用戶反復(fù)出現(xiàn)的興趣偏好（即用戶重復(fù)使用過的標(biāo)簽），并給予這部分標(biāo)簽較高的推薦權(quán)重，進(jìn)而影響用戶間的相似度。當(dāng)w i n值為5～1 0之間時(shí)達(dá)到了較好的推薦效果，過大則無(wú)法反映用戶的當(dāng)前興趣，失去了設(shè)置時(shí)間窗的意義。同時(shí)，通過上述時(shí)間窗的作用原理可知，時(shí)間窗 w i n取值越小，算法的運(yùn)行時(shí)間越短，推薦效率越高。

最后，在最近鄰個(gè)數(shù)為1 0，推薦數(shù)量等于5的條件下，測(cè)試衰減系數(shù)?和時(shí)間窗w i n同時(shí)變化時(shí)，對(duì)推薦精度產(chǎn)生的影響，如圖3所示。

圖3 ?與w i n綜合影響下的算法準(zhǔn)確率對(duì)比

由圖3可以看出，?和w i n的不同取值組合會(huì)顯著影響推薦效果。在前2組實(shí)驗(yàn)中，已得到?和w i n的部分最優(yōu)值。從圖中可以看到，在?介于0.5～0.7之間時(shí)，算法可以達(dá)到較好的推薦精度；無(wú)論?取何值，隨著w i n的增大，推薦效果均有所降低，仍然在w i n為5～1 0之間時(shí)，取得較高的準(zhǔn)確度。但無(wú)論?和w i n如何組合，U I C-T C F算法均在一定程度上優(yōu)于傳統(tǒng)協(xié)同過濾算法。

因此，如果推薦算法只考慮用指數(shù)衰減或是時(shí)間窗來(lái)反映用戶興趣變化，必然會(huì)損失部分精度。指數(shù)漸進(jìn)衰減衡量的是用戶長(zhǎng)期的興趣趨勢(shì)，而時(shí)間窗可以捕捉用戶穩(wěn)定的興趣偏好，只有綜合兩者的優(yōu)勢(shì)，才能達(dá)到更好的推薦效果。

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

針對(duì)現(xiàn)有基于標(biāo)簽協(xié)同過濾算法不能快速發(fā)現(xiàn)用戶興趣變化問題，本文提出了一種綜合標(biāo)簽和時(shí)間信息的推薦算法。用戶興趣以標(biāo)簽權(quán)重的形式表現(xiàn)，使用時(shí)間窗口提高反復(fù)出現(xiàn)的用戶早期興趣權(quán)重，采用指數(shù)漸進(jìn)遺忘對(duì)用戶長(zhǎng)期興趣偏好進(jìn)行更新。從實(shí)驗(yàn)結(jié)果可以看出，相比一般推薦系統(tǒng)以靜態(tài)方式進(jìn)行推薦，本文方法可以更為準(zhǔn)確地?cái)M合用戶興趣偏好，推薦精度更高。下一步的研究工作將在多個(gè)社會(huì)化標(biāo)簽網(wǎng)站上收集有一定時(shí)間趨勢(shì)的活躍用戶的大數(shù)據(jù)集，檢驗(yàn)算法的時(shí)間效率。

［1］Middleton S E，Shadbolt N R，Roure D C.Ontological User Profiling in Recommender Systems［J］.ACM Transactions on Information Systems，2004，22（1）：54-88.

［2］Adomavicius G，Tuzhilin A.Toward the Next Generation of Recommender System：A Survey of the Start-of-the-Artand Possible Extensions［J］.IEEE Transactions on Knowledge and Data Engineering，2005，17（6）：734-749.

［3］Zhou Tao，Jiang Luohuo，Su Riqi，etal.Effect of Initial Configuration on Network-based Recommendation［EB／OL］.（2007-11-15）.http：／／www.doc88.com／p-2691099654385.html.

［4］Pazzani M，Billsus D.Learning and Revising User Profiles：The Identification of Interesting Web Sites［J］.Machine Learning，1997，27（3）：313-331.

［5］秦光潔，張 穎.基于綜合興趣度的協(xié)同過濾推薦算法［J］.計(jì)算機(jī)工程，2009，35（17）：81-83.

［6］Heymann P，Koutrila G，Molina H G.Can Social Bookmarking Improve Web Search［C］／／Proceedings of the 1st ACM International Conference on Web Search and Web Data Mining.［S.l.］：ACM Press，2008：195-206.

［7］Sen S，Lam S K，Rashid A M，etal.Tagging Communities，Vocabulary，EvolutionC］／／Proceedings of ACM Conference on Computer Supp or ted Cooperative Work.［S.l.］：ACM Press，2006：181-190.

［8］ 郭新明，弋改珍.混合模型的用戶興趣漂移算法［J］.智能系統(tǒng)學(xué)報(bào)，2010，5（2）：181-184.

［9］Koychev I，Schwab I.Adaptation to Drifting User's Interests［C］／／Proceedings of Workshopon Machine Learningin New Information Age.Barcelona，Spain：［s.n.］，2000：39-46.

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

［11］ 李克潮，梁正友.適應(yīng)用戶興趣變化的指數(shù)遺忘協(xié)同過濾算法［J］.計(jì)算機(jī)工程與應(yīng)用，2011，47（13）：154-156.

［12］ 邢春曉，高鳳榮，戰(zhàn)思南，等.適應(yīng)用戶興趣變化的協(xié)同過濾推薦算法［J］.計(jì)算機(jī)研究與發(fā)展，2007，44（2）：296-301.

編輯 顧逸斐

Research on Social Tagging Recommendation Algorithm Incorporated with User Interest Change

ZHANG Yanmei,WANG Lu
(School of Information,Central University of Finance and Economics,Beijing 100081,China)

Many recommendation methods based on social tagging ignore the change and repeatability of user interests,which may lead to unsatisfactory results.In order to solve these problems,a new method which efficiently combines exponential forgetting-based data weight and time windows is proposed.The method not only highlights the importance of recent interest, but also stresses the recurring early data.Based on standard tag set of the target user,the nearest neighbour set can be gained according to exponential offset tag vectors,and then calculates weight vectors via items within time windows.Recommendation values of the nearest neighbour set are computed by weight vectors and similarity.Finally,it makes recommendation of items within the top K predicted values.Simulation experimental results show that the proposed algorithm for recommendation can dynamically track the changes in user`s interest and has high quality of precision to some extent.

collaborative filtering;tag;interest change;exponential forgetting;time window;recommendation

1000-3428(2014)11-0318-04

A

F724.6

10.3969/j.issn.1000-3428.2014.11.062

教育部人文社會(huì)科學(xué)研究基金資助項(xiàng)目(11YJC880163);北京市哲學(xué)社會(huì)科學(xué)規(guī)劃基金資助項(xiàng)目(11JGC136)。

張艷梅(1976-),女,副教授、博士,主研方向:電子商務(wù),服務(wù)計(jì)算;王 璐,碩士研究生。

2013-09-24

2013-12-27E-mail:jlzym0309@sina.com

中文引用格式:張艷梅,王 璐.適應(yīng)用戶興趣變化的社會(huì)化標(biāo)簽推薦算法研究［J］.計(jì)算機(jī)工程,2014,40(11):318-321.

英文引用格式:Zhang Yanmei,Wang Lu.Research on Social Tagging Recommendation Algorithm Incorporated with User Interest Change［J］.Computer Engineering,2014,40(11):318-321.