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

張艷梅,王 璐

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

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

張艷梅,王 璐

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

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

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

1 概述

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

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

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

2 UIC-TCF算法描述

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

2.1 最近鄰居選取

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

定義1(用戶標(biāo)簽向量) 設(shè)基準(zhǔn)標(biāo)簽集T中有n個標(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)的時間;Datelast為用戶uj最后一次使用標(biāo)記系統(tǒng)的時間;Datei為用戶uj最后一次使用標(biāo)簽ti的時間。

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

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

2.2 資源推薦

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

設(shè)用戶u0標(biāo)記過的資源集合為Iu。設(shè)定一個時間窗win,得到目標(biāo)用戶最近一段時間win內(nèi)標(biāo)記資源集合Iwin,該集合內(nèi)的資源一定程度上反映了用戶近期的興趣偏好。無論資源標(biāo)記時間早晚,只要和Iwin的相似度較高,說明該資源和用戶當(dāng)前的興趣很相關(guān),即有較高的推薦權(quán)重,依次算出Iu中每一資源對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對目標(biāo)用戶u0的推薦分?jǐn)?shù)為:

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

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

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 對sim(u0,uj)降序排列,then得到分?jǐn)?shù)最高的N個鄰居;

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

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

3 實驗結(jié)果與分析

3.1 實驗環(huán)境

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

3.2 評價指標(biāo)

3.3 實驗結(jié)果

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

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

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

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

圖2顯示了時間窗win的取值對推薦效果的影響。實驗依次取win=5天,10天,15天,其中,?=0.5。

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

從圖2可以看出，w i n的取值會對推薦結(jié)果產(chǎn)生一定影響。因為通過設(shè)置時間窗w i n來截取目標(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之間時達(dá)到了較好的推薦效果，過大則無法反映用戶的當(dāng)前興趣，失去了設(shè)置時間窗的意義。同時，通過上述時間窗的作用原理可知，時間窗 w i n取值越小，算法的運行時間越短，推薦效率越高。

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

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

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

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

4 結(jié)束語

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

［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］.計算機工程，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é)報，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)運.基于遺忘曲線的協(xié)同過濾推薦算法［J］.南京大學(xué)學(xué)報：自然科學(xué)版，2010，46（5）：520-527.

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

［12］ 邢春曉，高鳳榮，戰(zhàn)思南，等.適應(yīng)用戶興趣變化的協(xié)同過濾推薦算法［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

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

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

2013-09-24

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

中文引用格式:張艷梅,王 璐.適應(yīng)用戶興趣變化的社會化標(biāo)簽推薦算法研究［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.