基于關聯(lián)規(guī)則的標簽推薦

陳雙雙，王曉軍

(南京郵電大學 計算機學院，江蘇 南京 210003)

0 引 言

標簽系統(tǒng)在實際生活中應用廣泛，用戶通過標簽可以標注或者搜索自己感興趣的資源，反映該用戶的偏好，表達對事物的看法，因此標簽是連接用戶和事物的紐帶。目前常見的標簽推薦方法大都基于FolkRank算法[1]，這種方法主要是基于用戶、標簽、資源三者之間的關系，并且以這種關系為基礎構建一個無向圖進行標簽推薦，但是現(xiàn)有的方法沒有考慮到標簽與標簽之間的關系，并且也不能有效地緩解數(shù)據(jù)稀疏問題。針對這些問題，引入了標簽與標簽的關系，并且利用標簽之間的關系進行推薦。

1 相關研究

Kim等[2]強調(diào)標簽數(shù)據(jù)可以描述用戶潛在的興趣和特征，并認為結合不同的算法(協(xié)同過濾、隨機游走模型等等)可以得到顯著的優(yōu)勢，提高個性化推薦的質(zhì)量。Mahboob等[3]在推薦過程中應用熱擴散算法，在提取數(shù)據(jù)，如用戶、標簽、資源以及它們之間的關系之后，從系統(tǒng)日志文件創(chuàng)建基于圖的模式；根據(jù)用戶的活動路徑并觀察所創(chuàng)建的模式的熱傳導，將預期進一步的目標推薦給該用戶。Mao等[4]通過記錄各個用戶使用共同標簽的情況，建立一個帶有權重節(jié)點的網(wǎng)絡，然后在標簽-資源兩偶圖上執(zhí)行一個擴散過程，將標簽的權值轉(zhuǎn)換成推薦項的分數(shù)，進行個性化推薦。Ma等[5]為了提高推薦的精確度，改進了基于用戶的協(xié)同過濾方法，提出融合用戶標簽與用戶關系網(wǎng)的方法。Li等[6]針對在線用戶構建了一種新的LDA(latent Dirichlet allocation)模型，以學習用戶的動態(tài)興趣，并且結合LDA模型和增長Biterm主題模型(incremental biterm topic model，IBTM)設計了一種新的自動標簽推薦方法。Rawashdeh等[7]為了提高標簽推薦的準確度，提出了基于用戶-標簽-項目關系的鄰接矩陣，并結合卡茨模型(Katz model)構建出一個關于用戶、標簽、項目的卡茨矩陣。Mashal等[8]利用近鄰法(K-nearest neighbors，KNN)進行標簽推薦，KNN方法從文檔集合中選擇出與新文檔最相關的K個文檔，將這K個文檔標簽推薦給新文檔，相似度越大的文檔，其標簽推薦的位置越靠前。Belem等[9]提出了一種有監(jiān)督的主題模型，是針對主題模型LDA的一種改進，它增加了一個連續(xù)變量代表標簽，并利用標簽訓練出最優(yōu)的參數(shù)。Si等[10]也是在LDA模型的基礎上，提出了主題模型Tag-LDA，此方法基于文檔內(nèi)容和標簽聯(lián)合建模。

以上研究雖然在一定程度上提高了精確度，卻忽略了標簽與標簽之間的關系，并且沒能考慮到標簽數(shù)據(jù)稀疏問題。在實際應用中，用戶的標簽數(shù)據(jù)往往會一直處于稀疏的狀態(tài)，系統(tǒng)無法準確捕捉其興趣偏好，從而影響了推薦的質(zhì)量。針對標簽數(shù)據(jù)稀疏問題，提出一種基于重疊的時間窗口模型(based on overlapping time window model，OTWM)標簽數(shù)據(jù)采集方法；此方法按照時間窗口順序去采集標簽數(shù)據(jù)，每兩個相鄰的時間窗口有重疊的時間區(qū)間，這使得重疊時間區(qū)間內(nèi)的標簽重復利用，緩解了數(shù)據(jù)稀疏問題。為了提高標簽推薦的精確度，提出了一種基于關聯(lián)規(guī)則的標簽推薦方法(based on association rules tag recommendation，ATRecom)。首先，構建一種基于重疊的時間窗口模型用來采集用戶的標簽數(shù)據(jù)；然后，對這些標簽數(shù)據(jù)進行挖掘分析，找到標簽與標簽之間的關系；最后，利用挖掘出來的關聯(lián)規(guī)則為用戶進行標簽推薦。

2 標簽的關聯(lián)規(guī)則挖掘

2.1 關聯(lián)規(guī)則概念

關聯(lián)規(guī)則可反映一個事務與其他事務之間的關聯(lián)性[11]。若兩個或者多個事務之間存在關聯(lián)關系，那么就能通過已經(jīng)發(fā)生的事務預測與其關聯(lián)的事務，例如廣為人知的啤酒與尿布案例。

關聯(lián)規(guī)則定義為形如X→Y的蘊涵式，描述了頻繁共現(xiàn)的事務X，Y同時出現(xiàn)的規(guī)律和模式，表示規(guī)則前件事務X和后件事務Y中的項目頻繁地同時出現(xiàn)。例如{tag1,tag2}→{tag3}的蘊涵式，描述了標簽集{tag1,tag2}出現(xiàn)時，標簽集{tag3}也很有可能出現(xiàn)。

關聯(lián)規(guī)則挖掘過程主要包含3個階段[12]：

第一階段是采集數(shù)據(jù)事務庫。

第二階段從數(shù)據(jù)事務庫發(fā)現(xiàn)頻繁項集集合。

第三階段利用挖掘獲得的頻繁項集集合，產(chǎn)生關聯(lián)規(guī)則(association rules)。

2.2 相關定義

定義1：時間窗口TW。

假設S={tag1, tag2, …, tagn}是一個在時間區(qū)域[TS,TE]內(nèi)出現(xiàn)的標簽序列；Sw={tagw+1, tagw+2,… ,tagw+m}是一個在時間區(qū)域[ts,te]內(nèi)的標簽序列，即Sw?S，其中ts>TS，te

定義2：滑動步長ST。

假設在兩個相鄰時間窗TWi= [ti,tj]和TWi+1= [ti+1,tj+1]中，ti

定義3：標簽事務和標簽事務庫。

L(uid,TW) = {tag1,tag2,…, tagh}是用戶uid在時間窗口TW內(nèi)使用過的標簽序列，它定義為一條標簽事務(tag transaction)。多條標簽事務組成的集合就是標簽事務庫T。

定義4：頻繁共現(xiàn)標簽集。

設P為一個由多個標簽組成的集合，P={tag1，tag2,…，tagk}，P中所有標簽在標簽事務集合T中同時出現(xiàn)的次數(shù)為sup(P)，稱為P的支持度。給定一個最支持度minSup，當sup(P)> minSup時，稱P為頻繁共現(xiàn)標簽集，且頻繁共現(xiàn)標簽集有一個特征，如果P是頻繁共現(xiàn)的，那么P的子集也是頻繁共現(xiàn)的。

2.3 基于OTWM的數(shù)據(jù)采集

圖1是基于關聯(lián)規(guī)則的標簽推薦(ATRecom)過程。

圖1 基于關聯(lián)規(guī)則的標簽推薦過程

系統(tǒng)在采集用戶的標簽數(shù)據(jù)時，首先在第一個時間窗口TW1內(nèi)采集每個用戶所使的標簽序列L(uid,TW1)，即用戶標識為uid的標簽事務，并且將這條標簽事務添加到標簽事務庫T中；當采集完該窗口內(nèi)所有用戶的標簽數(shù)據(jù)后，時間窗口向前滑動ST步長，到達第二時間窗口TW2，同樣采集第二時間窗口TW2內(nèi)所有用戶的標簽數(shù)據(jù)，針對每個用戶都會生成一條關于該用戶的標簽事務，添加到標簽數(shù)據(jù)庫T中。依次類推，OTWM模型會把所有時間窗口內(nèi)的用戶標簽數(shù)據(jù)采集完成，得到標簽事務庫T，標簽數(shù)據(jù)采集完成。其過程如下：

步驟1：定義時間窗口TW的大小t，滑動步長ST。

步驟2：采集當前時間窗口TWi(代表第i個時間窗口)內(nèi)的每個用戶對應的標簽事務，直到所有用戶在該窗口內(nèi)的標簽數(shù)據(jù)采集完畢，得到該窗口內(nèi)所有用戶的標簽事務，加入標簽事務庫T中。

步驟3：判斷當前窗口TWi是否為最后一個時間窗口。

步驟4：如果當前窗口不是最后一個時間窗口，滑動時間窗口ST步長，到達下一個時間窗口TWi+1，重復步驟2，采集此窗口內(nèi)每個用戶的標簽數(shù)據(jù)，生成關于該用戶的標簽事務，將其加入標簽事務庫T中；如果當前窗口是最后一個時間窗口，那么用戶標簽數(shù)據(jù)采集完畢。得到最終的標簽事務庫T。

2.4 標簽關聯(lián)規(guī)則挖掘

頻繁項集合挖掘的方法有許多，但是實際應用中常見的有兩種：(1)Apriori及其改進算法，其基本思想是[13]由k項頻繁項集產(chǎn)生k+1項頻繁項集，直到滿足條件的頻繁項集發(fā)現(xiàn)為止。Apriori算法通過不斷地構造候選集、篩選候選集挖掘出頻繁項集，需要多次掃描原始數(shù)據(jù)，當原始數(shù)據(jù)較大時，磁盤I/O次數(shù)太多，效率比較低下。(2)FP-Growth算法處理數(shù)據(jù)的效率比較高，其基本思想是將原始數(shù)據(jù)壓縮到一個FP-Tree，在該樹上進行頻繁項集的挖掘，只需要掃描兩邊數(shù)據(jù)庫[14]。

ATRecom采用FP-Growth算法。利用FP-Growth算法對標簽事務庫T[15]進行頻繁項[16]挖掘，得到頻繁共現(xiàn)的標簽集集合，記F={P1,P2,…,Pm}，其中Pi是頻繁共現(xiàn)的標簽組成的集合，即頻繁共現(xiàn)標簽集。

對上述得到的頻繁共現(xiàn)的標簽集集合F進行挖掘，找出標簽之間的關聯(lián)規(guī)則庫R。其過程主要分為以下幾步：

步驟1：讀取頻繁共現(xiàn)標簽集集合F，其中F={F1,F2,…,Fi,…,Fn}。

步驟2：對頻繁共現(xiàn)標簽集集合F中每個頻繁共現(xiàn)標簽集Fi，產(chǎn)生其所有非空子集，并存放在集合Sub中，其中Sub={sub1,sub2,sub3…}。

步驟3：對于非空子集集合Sub中的每個元素Subi都計算其在F中的支持度；如果為最小支持度minSup，則認為關聯(lián)規(guī)則“subi→(Fi-subi)”是可靠的，并且保存到關聯(lián)規(guī)則庫R中。

2.5 標簽推薦

針對要進行推薦的目標用戶uid收集其標簽事務，得到關于該用戶的標簽事務庫Tu，然后利用上一小節(jié)中挖掘獲得的標簽之間的關聯(lián)規(guī)則庫R尋找用戶uid潛在感興趣的標簽列表。其過程主要分為以下幾步：

(1)收集待推薦用戶uid使用過的所有標簽，得到關于該用戶標簽集合tuid= {tag(uid,1)， tag(uid,2),…， tag(uid,k)}；

(2)依次讀取上述標簽關聯(lián)規(guī)則庫R中形如X→Y的關聯(lián)規(guī)則，并且判斷該規(guī)則中的先導標簽集X是否存在于關于該用戶的標簽集合tuid中；

(3)當判斷為存在時，即X?tuid，并且該條規(guī)則X→Y中先導標簽集X關聯(lián)的后繼標簽集Y?tuid，將標簽集Y推薦給對應用戶。

3 實驗與結果分析

3.1 數(shù)據(jù)集與評估標準

實驗選取了在標簽推薦系統(tǒng)中常用的兩個數(shù)據(jù)集，分別是Last.fm[17]和CiteULike[18]，它們的數(shù)據(jù)特征如表1所示。Last.fm是一家著名的音樂網(wǎng)站，它通過分析用戶的聽歌行為來預測用戶對音樂的興趣，數(shù)據(jù)集包含用戶2 100個，標簽12 648個，項目(歌手)18 745個，用戶給項目貼標簽的信息186 479條。CiteULike是一個著名的論文書簽網(wǎng)站，它允許研究人員提交或者收藏他們感興趣的論文，給論文打標簽，從而幫助用戶更好地發(fā)現(xiàn)和自己研究領域相關的優(yōu)秀論文，數(shù)據(jù)集包含用戶2 614個，項目4 096個，標簽2 310個，用戶給資源打標簽信息161 395條。

表1 數(shù)據(jù)特征

評估標簽推薦系統(tǒng)的性能度量主要采用精確度(precision)和召回率(recall)[19]。

3.2 實驗結果

實驗采用了基于關聯(lián)規(guī)則的標簽推薦和基于卡茨(Katz)模型的標簽推薦[7]兩種方法。其中，基于Katz模型的標簽推薦方法主要根據(jù)用戶-標簽-項目的關系構建出一個關于用戶、項目、標簽的三元鄰接矩陣，通過最佳匹配文本相似度公式(Best Match25，BM25)計算出這個鄰接矩陣上的各個權值，然后結合Katz模型，對該矩陣進行矩陣處理，得到Katz矩陣。最后根據(jù)Katz矩陣計算用戶、項目、標簽的Katz評分，從而進行推薦。ATRecom是利用標簽與標簽之間的關系進行推薦，而KatzBM25則是根據(jù)用戶、標簽、項目之間的關系。

利用ATRecom方法的標簽推薦涉及到時間窗口TW這個不確定參數(shù)。為了找出最為合適的時間窗口值TW，驗證了TW取值在20到90之間的均勻分布的實驗結果。圖2顯示了時間窗口TW的變化對標簽推薦結果精確度的影響，當時間窗口TW的取值為50時，推薦的精確度是最高的。

圖2 時間窗口對精確度的影響

數(shù)據(jù)稀疏度是影響推薦精確度重要因素。數(shù)據(jù)集Last.fm和CiteULike的數(shù)據(jù)稀疏度計算如下：

其中，sparsity是數(shù)據(jù)的稀疏度；users是用戶個數(shù)；items是項目個數(shù)；tagassinments是用戶給項目打標簽的記錄條數(shù)。

為了觀察數(shù)據(jù)稀疏度對ATRecom、KatzBM25方法推薦精確度的影響，驗證了這兩種方法在Last.fm、CiteULike數(shù)據(jù)集，3種不同稀疏度下的實驗結果。圖3、表2顯示了各數(shù)據(jù)集在時間窗口TW為50時，在不同的稀疏度下獲得的實驗結果。

(a)Last.fm

數(shù)據(jù)集稀疏度ATRecomSwallowMATKatzBM25Last.fm0.0030.450.410.370.340.003 70.520.480.430.400.004 70.590.570.540.50CiteULike0.013 10.510.480.450.430.014 10.580.550.530.510.015 10.660.630.610.60

結果表明，ATRecom獲得的精確度比KatzBM25高，并且當數(shù)據(jù)的稀疏程度發(fā)生變化時，ATRecom的精確度變化幅度低于KatzBM25。這表明ATRecom推薦方法在一定程度上緩解了數(shù)據(jù)稀疏造成的推薦不準確的問題，其主要原因是在數(shù)據(jù)采集過程中，ATRecom采用了有重疊的時間窗口，這使稀疏的標簽數(shù)據(jù)可以二次利用。

(a)Last.fm

(b)CiteULike

圖4顯示了ATRecom和KatzBM25在Last.fm和CiteULike兩種數(shù)據(jù)集推薦的準確度和召回率的關系，在此，Last.fm數(shù)據(jù)集的稀疏度為0.004 7，CiteULike數(shù)據(jù)集的稀疏度為0.015 1，ATRecom中的時間窗口TW為50?？芍扑]的精確度越高召回率就會越低。但是ATRecom推薦結果精確度、召回率都明顯高于KatzBM25。

4 結束語

基于關聯(lián)規(guī)則的標簽推薦方法不同于傳統(tǒng)的標簽推薦，該方法中采用基于重疊的時間窗口模型的標簽數(shù)據(jù)采集方法能夠使重疊時間區(qū)間內(nèi)的標簽數(shù)據(jù)多次合理利用，緩解了數(shù)據(jù)稀疏問題；同時避免了當標簽信息的時間跨度過大時，本來無關的標簽之間的相互影響造成的規(guī)則挖掘的不準確性。此外，這種標簽推薦方法也考慮到了標簽-標簽的關系，而不在拘泥于傳統(tǒng)的用戶-標簽，資源-標簽這種關系。