一種在圖連接項(xiàng)集上發(fā)掘精簡(jiǎn)模式的方法

張迪，張?jiān)迫?，張廣治

(1.中國(guó)傳媒大學(xué) 計(jì)算機(jī)學(xué)院，北京 100024；2.中國(guó)科學(xué)院 計(jì)算技術(shù)研究所，北京 100190)

一種在圖連接項(xiàng)集上發(fā)掘精簡(jiǎn)模式的方法

張迪1，張?jiān)迫?，張廣治1

(1.中國(guó)傳媒大學(xué) 計(jì)算機(jī)學(xué)院，北京 100024；2.中國(guó)科學(xué)院 計(jì)算技術(shù)研究所，北京 100190)

項(xiàng)集通常具備兩個(gè)特點(diǎn)：(1)觀測(cè)樣本來(lái)自于不同的實(shí)體，這些實(shí)體間存在著相似關(guān)系；(2)樣本量稀少，導(dǎo)致模式發(fā)掘不完整。本文考慮如何在這類數(shù)據(jù)上有效地發(fā)掘精簡(jiǎn)的模式集合。首先，通過(guò)定義一個(gè)擴(kuò)散核函數(shù)，可將每個(gè)節(jié)點(diǎn)下的小樣本擴(kuò)展至圖中的所有節(jié)點(diǎn)，并通過(guò)權(quán)重來(lái)標(biāo)識(shí)他們與當(dāng)前節(jié)點(diǎn)的相似度：繼而這一權(quán)重值，又可以自然地引入到精簡(jiǎn)模式的搜索與評(píng)估過(guò)程中。這樣我們不僅從理論上給出了圖結(jié)構(gòu)對(duì)MDL評(píng)估的影響，并且在實(shí)現(xiàn)上也相對(duì)簡(jiǎn)單，只需對(duì)現(xiàn)有算法添加一個(gè)預(yù)處理過(guò)程，并進(jìn)行少量修改即可。實(shí)驗(yàn)表明，這一方案的挖掘效果，比通常的獨(dú)立挖掘、全局挖掘方式均具備明顯的優(yōu)勢(shì)。而且，由于只有一個(gè)額外的預(yù)處理過(guò)程，計(jì)算代價(jià)也較低。

模式發(fā)掘；最小描述長(zhǎng)度；圖；擴(kuò)散核

1 引言

模式挖掘技術(shù)，研究如何在數(shù)據(jù)表的項(xiàng)集中發(fā)現(xiàn)潛在的共現(xiàn)關(guān)系。經(jīng)典的頻繁模式發(fā)掘，如Apriori[1]，通過(guò)對(duì)所有數(shù)據(jù)項(xiàng)的出現(xiàn)次數(shù)進(jìn)行排序，并濾去其中的低頻模式，并將剩下的高頻模式作為結(jié)果輸出。這些模式既可以作為最終結(jié)果直接輸出，也可以作為特征供后續(xù)的數(shù)據(jù)挖掘任務(wù)作為輸入。該方式由于原理直觀，計(jì)算簡(jiǎn)便，獲得了較為廣泛的應(yīng)用。

隨著應(yīng)用的深入，該方法的一些缺陷也被暴露出來(lái)，最主要的問(wèn)題就是模式爆炸[2]。對(duì)于高頻模式而言，它的一部分子模式同樣有可能是高頻的。這樣，很可能會(huì)得到大量冗余的模式：這對(duì)于人工使用而言，非常難以檢視和分析；而對(duì)于數(shù)據(jù)挖掘任務(wù)而言，如果使用大量冗余的特征作為輸入，將容易導(dǎo)致過(guò)擬合現(xiàn)象，降低模式準(zhǔn)確度。對(duì)于該問(wèn)題，一種實(shí)際的做法是，將頻率的篩選閾值(即支持度)盡量設(shè)置得高一些，以便將模式總數(shù)控制在合理范圍。不過(guò)，該做法也會(huì)容易導(dǎo)致得到的模式都是顯而易見的，沒(méi)有特別的價(jià)值。

有鑒于此，人們將挖掘的目標(biāo)從高頻模式轉(zhuǎn)向了感興趣的模式。其中一種流行方法是，基于MDL準(zhǔn)則過(guò)濾掉冗余的模式，即Krimp算法[3]。該算法假設(shè)待求的模式集合為一個(gè)字典，而我們用這個(gè)字典對(duì)數(shù)據(jù)進(jìn)行編碼，對(duì)應(yīng)編碼長(zhǎng)度可基于經(jīng)驗(yàn)概率值，以信息論的方式求得。為了找到一個(gè)(近似)最優(yōu)的字典，Krimp采用啟發(fā)式方法對(duì)可能的模式組合進(jìn)行搜索。經(jīng)試驗(yàn)表明，該方法通過(guò)能將冗余模式刪減至原有的5%-20%，并且能發(fā)現(xiàn)一些少見的模式[3]。

本文主要考慮如何將Krimp應(yīng)用到內(nèi)部蘊(yùn)含有結(jié)構(gòu)性關(guān)系的數(shù)據(jù)項(xiàng)上。通常，在數(shù)據(jù)表記錄中，我們會(huì)發(fā)現(xiàn)一類實(shí)體標(biāo)記字段，如用戶名、設(shè)備名等。它們本身不包含當(dāng)前對(duì)象的狀態(tài)信息，但標(biāo)記了數(shù)據(jù)發(fā)生的來(lái)源。另外，我們也會(huì)得到一些實(shí)體的屬性信息，如用戶的基本信息、設(shè)備之間的連接關(guān)系等等。當(dāng)樣本量不足時(shí)，通過(guò)分析實(shí)體間的相似性，就可以在相似節(jié)點(diǎn)間對(duì)數(shù)據(jù)進(jìn)行某種“復(fù)用”，從而提高模式挖掘的完整性和穩(wěn)健性。

這一問(wèn)題，或與本問(wèn)題相似的一類場(chǎng)景，已經(jīng)在一些研究中得到了關(guān)注，在論文[4]中，討論了如何在節(jié)點(diǎn)帶有屬性值的圖上，發(fā)掘相似的拓?fù)淠Ｊ健Ｔ谡撐腫5]中，討論如何在動(dòng)態(tài)并且?guī)傩灾档膱D上，挖掘拓?fù)浣Y(jié)構(gòu)演變與屬性值改變之間的關(guān)系。在論文[6]中，介紹了一種在社交網(wǎng)絡(luò)中，基于采樣方式進(jìn)行模式發(fā)掘，研究用戶之間如何相互影響。本工作的區(qū)別在于：在場(chǎng)景上，我們關(guān)注如何將圖的結(jié)構(gòu)信息導(dǎo)入到精簡(jiǎn)模式發(fā)掘過(guò)程中，并不討論如何挖掘圖本身結(jié)構(gòu)、或圖結(jié)構(gòu)與節(jié)點(diǎn)屬性之間的重現(xiàn)關(guān)系；在方案上，我們使用了核函數(shù)來(lái)表達(dá)節(jié)點(diǎn)之間的相似關(guān)系，并實(shí)現(xiàn)了對(duì)小樣本模式的挖掘。

在接下來(lái)的篇幅中，本文將首先介紹Krimp和核方法的基礎(chǔ)知識(shí)，繼而介紹本方案的理念推導(dǎo)和算法過(guò)程，最后給出相關(guān)的實(shí)驗(yàn)結(jié)果。

2 背景

2.1 基于MDL的模式挖掘

引理1 數(shù)據(jù)庫(kù)D的總壓縮長(zhǎng)度為(即優(yōu)化目標(biāo))

L(D，CT)=L(CT)+L(D|CT)

(1)

后一項(xiàng)代表數(shù)據(jù)編碼后的長(zhǎng)度，具體為

(2)

(3)

其中，Cover函數(shù)基于CT，給出事務(wù)t匹配的編碼codeCT。另外，編碼表的長(zhǎng)度為

(4)

其中，前一項(xiàng)代表編碼表中的條目，后一項(xiàng)代表對(duì)應(yīng)的碼長(zhǎng)，而Usage給出每個(gè)模式X的出現(xiàn)次數(shù)。

求解一個(gè)最佳編碼表，是一個(gè)NP問(wèn)題[3]。通常，采用啟發(fā)式搜索，可得到一個(gè)可行解。在搜索過(guò)程中，需要定義兩個(gè)次序：i)由引理1中的Cover函數(shù)所定義的編碼次序，即表項(xiàng)對(duì)于數(shù)據(jù)的匹配優(yōu)先級(jí)，這唯一確定了某條事務(wù)的編碼方式；ii)候選模式排序，添加那哪條模式到編碼表中，以評(píng)估中否可以進(jìn)一步提升壓縮效果[7]。這里主要依據(jù)Usage的結(jié)果進(jìn)行倒排序，高頻模式優(yōu)先。后面我們將嘗試改變ii)步驟中的Usage。對(duì)于搜索過(guò)程，也有兩種方式：a)先用頻繁準(zhǔn)則生成候選模式，繼而使用啟發(fā)式搜索對(duì)這些候選模式進(jìn)行揀選：b)按從短到長(zhǎng)的次序，一邊生成候選模式，一邊進(jìn)行選擇。它們的原理是相似的，出于性能考慮，我們?cè)趯?shí)驗(yàn)中將采用b)。

2.2 分布的核嵌入

核函數(shù)可以用來(lái)衡量數(shù)據(jù)樣本之間的相似性。

定義1令Ω為一個(gè)非空集合，對(duì)稱函數(shù)κ：Ω×Ω→R是一個(gè)半正定的核函數(shù)，當(dāng)

(5)

對(duì)于任意n∈N，x1，…xn∈Ω，c1，…cn∈R均成立。

對(duì)于核函數(shù)κ，我們也可以用特征函數(shù)φ(x)來(lái)表達(dá)：

定理1(Mercer定理)

(6)

以這些特征函數(shù)為基，可生成一個(gè)函數(shù)空間：

定義2

(7)

定理2(再生核希爾伯特空間定理)

<κ(x1，·)，κ(x2，·)>H=κ(x1，x2)

(8)

當(dāng)我們定義內(nèi)積為

(9)

現(xiàn)在，我們可以將一個(gè)概率分布函數(shù)P(x)嵌入到上述空間[9]：

定義3

(10)

給定n個(gè)樣本{x1，…，xn}，則式(10)在經(jīng)驗(yàn)意義下寫為：

(11)

相應(yīng)地，還可定義聯(lián)合概率和條件概率對(duì)應(yīng)的算子：

(12)

(13)

2.3 圖的核函數(shù)

通過(guò)矩陣的指數(shù)運(yùn)算，可以產(chǎn)生合法的核函數(shù)：

定義4 指數(shù)核定義為

(14)

其中H為產(chǎn)生器，β為帶寬參數(shù)。通過(guò)在H中體現(xiàn)圖的結(jié)構(gòu)，可定義圖上的擴(kuò)散核：

3 方案

顯然，與通常的模式發(fā)掘不同，這里既不適合對(duì)每個(gè)節(jié)點(diǎn)分別挖掘模式，忽略了各節(jié)點(diǎn)間的關(guān)聯(lián)性；也不能簡(jiǎn)單地直接合并所有樣本，抹煞了各節(jié)點(diǎn)之間的差異性。這里的關(guān)鍵是，要先結(jié)合圖的結(jié)構(gòu)，重新估計(jì)項(xiàng)集的分布函數(shù)。于是，我們基于圖上的核函數(shù)，先得到一個(gè)再生核希爾伯特空間。繼而，將各節(jié)點(diǎn)下的經(jīng)驗(yàn)分布都映射到該空間中，推斷各節(jié)點(diǎn)下的新分布函數(shù)，并將其重新表示為權(quán)重和原有樣本值的集合。最后，在MDL準(zhǔn)則下，結(jié)合各節(jié)點(diǎn)不同的權(quán)重值，對(duì)樣本集合進(jìn)行模式發(fā)掘，即為所求。

3.1 模型

如前所述，圖G反映了各節(jié)點(diǎn)之間的相似關(guān)系。我們考慮擴(kuò)展圖G，在每個(gè)節(jié)點(diǎn)下連接一個(gè)額外節(jié)點(diǎn)，以便表示各節(jié)點(diǎn)對(duì)應(yīng)的觀測(cè)樣本。一個(gè)樣例如圖1所示。

圖1 各節(jié)點(diǎn)觀測(cè)樣本之間的連接關(guān)系(示例)

其中，其中白色圓圈代表G中的節(jié)點(diǎn)，灰色的代表擴(kuò)展節(jié)點(diǎn)E，我們記它們的集合為G′。形式地，我們有：

引理 2 一個(gè)擴(kuò)展圖G′的鄰接矩陣定義為：

(15)

容量矩陣D′為

(16)

對(duì)應(yīng)的產(chǎn)生器為H′=W′-D′。

由于目前把觀測(cè)樣本都放置到了擴(kuò)展節(jié)點(diǎn)上，那么就可以得到這些節(jié)點(diǎn)上的經(jīng)驗(yàn)分布。接下來(lái)，原有圖G中各節(jié)點(diǎn)上的分布，或者說(shuō)經(jīng)驗(yàn)分布，就可以視為條件概率分布P(G|E)。我們利用式(12)，即可得到下面的定理。

定理3 給定n個(gè)樣本{(g1，e1)，…，(gn，en)}，圖G中各節(jié)點(diǎn)上的經(jīng)驗(yàn)分布為

其中，w(e)=Κ-1Κe，并且Κe=ΨTκ(x，·)=(k(x1，x)，...，k(x1，x))T

(17)

證明：記特征向量Φ：=[φ(g1)，...，φ(gn)]T和Ψ：=[ψ(e1)，...，ψ(en)]T，并且K=ΨTΨ和L=ΦTΦ。在經(jīng)驗(yàn)意義下，我們可以將式(13)寫為[9]

在觀測(cè)樣本已經(jīng)得到的情況下，

整理為式(17)中的形式，即證畢。

定理3說(shuō)明，原圖G節(jié)點(diǎn)上的經(jīng)驗(yàn)分布，都可以由擴(kuò)展節(jié)點(diǎn)E中樣本進(jìn)行加權(quán)和得到。下面，將定理3得到的權(quán)重導(dǎo)入到Krimp中，即更新如下兩個(gè)函數(shù)：

定義6 考慮數(shù)據(jù)庫(kù)D的每個(gè)事務(wù)t上有權(quán)重wt，則模式x出現(xiàn)頻次的計(jì)算方式調(diào)整為

(18)

與決策樹中參考權(quán)重對(duì)節(jié)點(diǎn)劃分的方式[10]類似，將式(3)調(diào)整為

(19)

3.2 算法

本方案的算法實(shí)現(xiàn)如下：

(1)輸入：一個(gè)數(shù)據(jù)庫(kù)集合{Dv|v∈V}，一個(gè)結(jié)構(gòu)G={V，E}

(2)輸出：一個(gè)模式集合X

(3)將G的擴(kuò)展為G′；

(4)生成G′的擴(kuò)散核矩陣；

(6)forallv∈Vdo

(7)計(jì)算所有節(jié)點(diǎn)在本節(jié)點(diǎn)v對(duì)應(yīng)的權(quán)重W

(8)依據(jù)usage′，L′(t|CT)運(yùn)行Krimp，生成對(duì)應(yīng)的模式集CTv

(9)endfor

考慮到Krimp的復(fù)雜度為O(|CT|log|CT|+|D|×|CT|×|I|)[8]，則本算法的復(fù)雜度為O(|V|*[|CT|log|CT|+|D|×|CT|×|I|]+|V|3)。考慮到|V|<<|D|，實(shí)際上|V|3的影響不大，即計(jì)算權(quán)重的運(yùn)算實(shí)際并不費(fèi)時(shí)。

4 實(shí)驗(yàn)

4.1 設(shè)計(jì)

我們使用兩類數(shù)據(jù)進(jìn)行實(shí)驗(yàn)，一為模擬數(shù)據(jù)，二為某連鎖超市的購(gòu)物數(shù)據(jù)集。數(shù)據(jù)集需要分為兩步處理：1)準(zhǔn)備數(shù)據(jù)；2)進(jìn)行采樣以測(cè)試算法的準(zhǔn)確性。對(duì)于真實(shí)數(shù)據(jù)，我們直接使用即可；對(duì)于模擬數(shù)據(jù)，我們使用NetworkX[11]生成隨機(jī)圖(節(jié)點(diǎn)數(shù)=100，連接半徑=0.125)，并且使用IBMQuestSyntheticDataGenerator[12]為每個(gè)節(jié)點(diǎn)獨(dú)立生成一個(gè)不同的模式集。接下來(lái)，基于定理3，按比例w(e)進(jìn)行摻混。其次，我們僅取現(xiàn)有數(shù)據(jù)的1/10進(jìn)行模式發(fā)掘，并與全量數(shù)據(jù)下獨(dú)立挖掘的結(jié)果進(jìn)行比較。

本方案中可調(diào)整的主要參數(shù)為擴(kuò)散核的β，我們需要考查其取值對(duì)結(jié)果的影響。另外我們使用兩個(gè)指標(biāo)來(lái)評(píng)估結(jié)果：用F1-Score衡量模式發(fā)掘的準(zhǔn)確率；用壓縮比L(D，CT)/L(D，ST)評(píng)估精簡(jiǎn)模式挖掘是否確實(shí)有效。

4.2 結(jié)果

通過(guò)在兩個(gè)數(shù)據(jù)集上運(yùn)行本方案，我們得到實(shí)驗(yàn)結(jié)果，如圖2所示。

在圖2中，(a)展現(xiàn)了一個(gè)隨機(jī)圖的例子?？梢钥吹?，圖是無(wú)向和連通的，這與本文的假設(shè)保持一致。(b)為盒圖，代表了F1-score在圖上節(jié)點(diǎn)的分布，左側(cè)為模擬數(shù)據(jù)，右側(cè)為真實(shí)數(shù)據(jù)。在計(jì)算F1-score時(shí)，我們以抽樣前的全量數(shù)據(jù)挖掘結(jié)果作為真實(shí)值，而以本方案的結(jié)果作為預(yù)測(cè)值。F1-score均值都大于0.6，說(shuō)明本方案是合理的。(c)對(duì)比了三種方式得到的模式集合的有效性，即壓縮比L(D，CT)/L(D，ST)，分為左右兩組，同樣是左模擬、右真實(shí)。在每一組中，最左側(cè)的列代表了將所有節(jié)點(diǎn)下的樣本合并，并進(jìn)行編碼，得到的壓縮比例；中間的列代表各節(jié)點(diǎn)獨(dú)立挖掘的壓縮比，顯然這是最差的；右側(cè)的列，代表本方案的效果，比其他兩種均明顯為優(yōu)。

(a)

(b)

(c)圖2 隨機(jī)圖樣例、以及模式發(fā)掘的準(zhǔn)確性、有效性

各節(jié)點(diǎn)之間聯(lián)系的緊密程度，可以通過(guò)擴(kuò)散核中的帶寬β進(jìn)行控制。我們測(cè)試了其不同取值下，壓縮比的變化情況，如圖3所示。

圖3 擴(kuò)散核參數(shù)對(duì)壓縮比的影響

從中可以發(fā)現(xiàn)，對(duì)于不同的數(shù)據(jù)集，最優(yōu)的β取值并不一致。模擬數(shù)據(jù)的最優(yōu)β要大于真實(shí)數(shù)據(jù)集的β，這說(shuō)明它的各節(jié)點(diǎn)聯(lián)系要更強(qiáng)。通過(guò)實(shí)驗(yàn)選取最優(yōu)的β，實(shí)際上我們也可以對(duì)圖中各節(jié)點(diǎn)模式的相似性，獲得一定的知識(shí)。

5 結(jié)論

本文討論了如何在圖結(jié)構(gòu)上對(duì)精簡(jiǎn)項(xiàng)集進(jìn)行挖掘的問(wèn)題。通過(guò)定義圖上的擴(kuò)散核，并在其誘導(dǎo)的希爾伯特空間上進(jìn)行概率推理，我們?yōu)槊總€(gè)樣本生成了一個(gè)權(quán)重，并將其自然地導(dǎo)入了MDL的計(jì)算過(guò)程中。實(shí)驗(yàn)證明，該方法不僅易于實(shí)現(xiàn)，而且獲得了比較顯著的效果。

[1]Aggarwal，CharuC，JiaweiHan(eds).Frequentpatternmining[M].Switzerland：SpringerInternationalPublishing，2014：12-15.

[2]MengerVJ.AnExperimentalAnalysisofthePatternExplosion[D].Utrecht，theNetherlands：UtrechtUniversity，2015：6-9.

[3]VreekenJ，VanLeeuwenM，SiebesA.Krimp：miningitemsetsthatcompress[J].DataMiningandKnowledgeDiscovery，2011，23(1)：169-214.

[4]BoulicautJF，PlantevitM，RobardetC.LocalPatternDetectioninAttributedGraphs[A].SolvingLargeScaleLearningTasks：ChallengesandAlgorithms，LectureNotesinComputerScience，SpringerInternationalPublishing，2016：168-183.

[5]SinghR，GravesJA，TalbertDA.ComplexPatternsinDynamicAttributedGraphs[C].Proceedingsofthe25thInternationalConferenceCompan-

iononWorldWideWeb，InternationalWorldWideWebConferencesSteeringCommittee，2016：105-106.

[6]ZhangJ，TangJ，ZhongY，etal.StructInf：MiningStructuralInfluencefromSocialStreams[C].ProceedingsoftheNationalConferenceonArtificialIntelligence(AAAI’2016)，MITPress，Cambridge，MAArtificialIntelligence，2016，128(1-2)：203-235.

[7]SmetsK，VreekenJ.Slim：Directlyminingdescriptivepatterns[C].Proceedingsofthe2012SIAMInternationalConferenceonDataMining，SocietyforIndustrialandAppliedMathematics，2012：236-247.

[8]MurphyKP.MachineLearning：aProbabilisticPerspective[M].Cambridge，Massachusetts，USA：MITPress，2012：534-536.

[9]SongL，F(xiàn)ukumizeK，GrettonA.Kernelembeddingsofconditionaldistributions：Aunifiedkernelframeworkfornonparametricinferenceingraphicalmodels[J].IEEESignalProcessingMagazine，2013，30(4)：98-111.

[10]NowozinS.ImprovedInformationGainEstimatesforDecisionTreeInduction[C].Proceedingsofthe29thinternationalconferenceonmachinelearning，InternationalMachineLearningSociety，2012：297-304.

[11]http：//networkx.github.io/[DB/OL].

[12]https：//sourceforge.net/projects/ibmquestdatagen/[DB/OL].

(責(zé)任編輯：王謙)

Mining Concise Patterns on Graph-Connected Itemsets

ZHANG Di1，ZHANG Yun-quan2，ZHANG Guang-zhi1

(1.Computer Science School，Communication University of China，Beijing 100024，China;2. Institute of Computing Technology，Chinese Academy of Sciences，Beijing 100190，China)

Itemset(or binary data tables)has the following two characteristics：(1)observation samples come from different entities，and there are similarities between these entities；(2)the sample size is scarce，resulting in pattern excavation is incomplete.This article further discusses how to discover patterns on structural itemsets.First，by defining a diffusion kernel function，we can extend a small sample under each node to all nodes in the graph and identify their similarity with the current node by weight；and this weight value can be naturally introduced into the pipeline of the search and evaluation process.In this way，we not only give theoretically the influence of the graph structure on the MDL evaluation，but also the relatively simple implementation，where only a small amount of modifications are needed based on the original MDL evaluation logic.Experiments show that the effect of this scheme has obvious advantages over the usual independent mining and global mining methods.Moreover，since there is only one additional pre-processing phase，the computational cost is also low.

2017-03-28

張迪(1982-)，男(漢族)，湖北洪湖人，中國(guó)傳媒大學(xué)計(jì)算機(jī)學(xué)院博士研究生.E-mail：andy.zhang.cn.12@qq.com

TP391.4

A

1673-4793(2017)03-0025-06