適應用戶興趣變化的社會化標簽推薦算法研究

張艷梅,王 璐

(中央財經大學信息學院,北京100081)

適應用戶興趣變化的社會化標簽推薦算法研究

張艷梅,王 璐

(中央財經大學信息學院,北京100081)

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

協同過濾;標簽;興趣變化;指數遺忘;時間窗;推薦

1 概述

近年來,互聯網規模及Web2.0迅速發展,大量有用信息和垃圾數據充斥著網絡,面對信息過載問題,信息檢索領域迫切需要個性化推薦服務為用戶提供有價值信息,完善用戶體驗,使用戶由被動的信息瀏覽者轉變為主動的參與者。當前主流的推薦方法包括協同過濾推薦［1］、基于內容推薦［2］、基于圖結構的推薦［3］、混合推薦［4］等。其中,協同過濾技術是實際應用中使用最廣泛的推薦技術［5］。聯系用戶和資源,標簽就是其中一種,它既能表現用戶的興趣取向,同時還能體現資源的屬性特征。文獻［6-7］的研究顯示標簽可以準確顯示用戶對網頁內容的判斷,同時標簽也是描述資源的一種好方法。目前,社會化標簽系統越來越流行,比如 MovieLens,Flickr, del.icio.us,Citeulike,國內的豆瓣網站等。

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

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

2 UIC-TCF算法描述

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

2.1 最近鄰居選取

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

定義1(用戶標簽向量) 設基準標簽集T中有n個標簽。用戶uj的標簽權重向量:

定義2(指數偏移權重) 用戶uj在標簽ti上的偏移權重為:

其中,?為衰減系數,0＜?＜1;Datebegin為用戶uj開始使用標簽系統的時間;Datelast為用戶uj最后一次使用標記系統的時間;Datei為用戶uj最后一次使用標簽ti的時間。

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

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

2.2 資源推薦

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

設用戶u0標記過的資源集合為Iu。設定一個時間窗win,得到目標用戶最近一段時間win內標記資源集合Iwin,該集合內的資源一定程度上反映了用戶近期的興趣偏好。無論資源標記時間早晚,只要和Iwin的相似度較高,說明該資源和用戶當前的興趣很相關,即有較高的推薦權重,依次算出Iu中每一資源對u0的推薦權重。在上一步最近鄰居用戶選定后,獲取鄰居用戶訪問資源,構成候選推薦資源集合,結合推薦權重和資源相似度算出推薦分數,給出TOP-K推薦。

定義5(資源的標簽向量) 資源Rx的標簽權重向量為:

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

2.3 推薦算法

推薦算法描述如下:

定義8(資源推薦分數) 鄰居用戶標記過的資源X對目標用戶u0的推薦分數為:

輸入 用戶標記項的矩陣;m:候選用戶數;n:社區用戶數;win:時間窗;u0:用戶

輸出 推薦給u0的分數最高的K個資源列表

Step1 標準標簽集初始化T=(t1,t2,…,tn);

Step2 為u0創建標簽矢量ut0,乘以指數抵消標簽矢量,then得到ut′0;

Step3 For j=1 to m-1

Step4 對sim(u0,uj)降序排列,then得到分數最高的N個鄰居;

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

Step8 降序排列rec(u0,x),產生推薦給u0的分數最好的K個資源列表。

3 實驗結果與分析

3.1 實驗環境

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

3.2 評價指標

3.3 實驗結果

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

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

圖1 不同?取值下算法準確率的對比

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

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

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

從圖2可以看出，w i n的取值會對推薦結果產生一定影響。因為通過設置時間窗w i n來截取目標用戶最近使用過的標簽，通過這些標簽找到用戶反復出現的興趣偏好（即用戶重復使用過的標簽），并給予這部分標簽較高的推薦權重，進而影響用戶間的相似度。當w i n值為5～1 0之間時達到了較好的推薦效果，過大則無法反映用戶的當前興趣，失去了設置時間窗的意義。同時，通過上述時間窗的作用原理可知，時間窗 w i n取值越小，算法的運行時間越短，推薦效率越高。

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

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

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

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

4 結束語

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

［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］秦光潔，張 穎.基于綜合興趣度的協同過濾推薦算法［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］.智能系統學報，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］于 洪，李轉運.基于遺忘曲線的協同過濾推薦算法［J］.南京大學學報：自然科學版，2010，46（5）：520-527.

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

［12］ 邢春曉，高鳳榮，戰思南，等.適應用戶興趣變化的協同過濾推薦算法［J］.計算機研究與發展，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

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

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

2013-09-24

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

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