基于關聯規則的標簽推薦

陳雙雙，王曉軍

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

0 引 言

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

1 相關研究

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

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

2 標簽的關聯規則挖掘

2.1 關聯規則概念

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

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

關聯規則挖掘過程主要包含3個階段[12]：

第一階段是采集數據事務庫。

第二階段從數據事務庫發現頻繁項集集合。

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

2.2 相關定義

定義1：時間窗口TW。

假設S={tag1, tag2, …, tagn}是一個在時間區域[TS,TE]內出現的標簽序列；Sw={tagw+1, tagw+2,… ,tagw+m}是一個在時間區域[ts,te]內的標簽序列，即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內使用過的標簽序列，它定義為一條標簽事務(tag transaction)。多條標簽事務組成的集合就是標簽事務庫T。

定義4：頻繁共現標簽集。

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

2.3 基于OTWM的數據采集

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

圖1 基于關聯規則的標簽推薦過程

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

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

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

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

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

2.4 標簽關聯規則挖掘

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

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

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

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

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

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

2.5 標簽推薦

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

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

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

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

3 實驗與結果分析

3.1 數據集與評估標準

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

表1 數據特征

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

3.2 實驗結果

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

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

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

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

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

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

(a)Last.fm

數據集稀疏度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高，并且當數據的稀疏程度發生變化時，ATRecom的精確度變化幅度低于KatzBM25。這表明ATRecom推薦方法在一定程度上緩解了數據稀疏造成的推薦不準確的問題，其主要原因是在數據采集過程中，ATRecom采用了有重疊的時間窗口，這使稀疏的標簽數據可以二次利用。

(a)Last.fm

(b)CiteULike

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

4 結束語

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