陳雙雙，王曉軍

(南京郵電大學(xué) 計(jì)算機(jī)學(xué)院，江蘇 南京 210003)

0 引 言

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

1 相關(guān)研究

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

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

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

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

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

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

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

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

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

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

2.2 相關(guān)定義

定義1：時(shí)間窗口TW。

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

定義2：滑動(dòng)步長(zhǎng)ST。

假設(shè)在兩個(gè)相鄰時(shí)間窗TWi= [ti,tj]和TWi+1= [ti+1,tj+1]中，ti

定義3：標(biāo)簽事務(wù)和標(biāo)簽事務(wù)庫(kù)。

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

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

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

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

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

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

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

步驟1：定義時(shí)間窗口TW的大小t，滑動(dòng)步長(zhǎng)ST。

步驟2：采集當(dāng)前時(shí)間窗口TWi(代表第i個(gè)時(shí)間窗口)內(nèi)的每個(gè)用戶(hù)對(duì)應(yīng)的標(biāo)簽事務(wù)，直到所有用戶(hù)在該窗口內(nèi)的標(biāo)簽數(shù)據(jù)采集完畢，得到該窗口內(nèi)所有用戶(hù)的標(biāo)簽事務(wù)，加入標(biāo)簽事務(wù)庫(kù)T中。

步驟3：判斷當(dāng)前窗口TWi是否為最后一個(gè)時(shí)間窗口。

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

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

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

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

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

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

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

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

2.5 標(biāo)簽推薦

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

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

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

(3)當(dāng)判斷為存在時(shí)，即X?tuid，并且該條規(guī)則X→Y中先導(dǎo)標(biāo)簽集X關(guān)聯(lián)的后繼標(biāo)簽集Y?tuid，將標(biāo)簽集Y推薦給對(duì)應(yīng)用戶(hù)。

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

3.1 數(shù)據(jù)集與評(píng)估標(biāo)準(zhǔn)

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

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

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

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

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

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

圖2 時(shí)間窗口對(duì)精確度的影響

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

其中，sparsity是數(shù)據(jù)的稀疏度；users是用戶(hù)個(gè)數(shù)；items是項(xiàng)目個(gè)數(shù)；tagassinments是用戶(hù)給項(xiàng)目打標(biāo)簽的記錄條數(shù)。

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

(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

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

(a)Last.fm

(b)CiteULike

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

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

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