基于圖的情境離群點(diǎn)檢測方法

李濤，張蕓，黃志宏

(華南農(nóng)業(yè)大學(xué) 現(xiàn)代教育技術(shù)中心，廣東 ，廣州 510640)

?

基于圖的情境離群點(diǎn)檢測方法

李濤，張蕓，黃志宏

(華南農(nóng)業(yè)大學(xué) 現(xiàn)代教育技術(shù)中心，廣東 ，廣州 510640)

針對異常模式挖掘中的情境離群點(diǎn)檢測問題，提出一種基于圖的檢測方法.首先對數(shù)據(jù)實(shí)例構(gòu)建一個(gè)實(shí)例圖，然后采用一個(gè)滑動窗口穿越數(shù)據(jù)實(shí)例，對處于滑動窗口內(nèi)的數(shù)據(jù)實(shí)例，計(jì)算結(jié)點(diǎn)之間的閔可夫斯基距離作為邊權(quán)值，然后采用最小生成樹聚類算法對實(shí)例圖進(jìn)行聚類，再采用第二個(gè)滑動窗口穿越數(shù)據(jù)實(shí)例，根據(jù)窗口內(nèi)的數(shù)據(jù)實(shí)例是否屬于主趨勢聚類賦予不同的離群值評分，不屬于主趨勢聚類的數(shù)據(jù)實(shí)例被認(rèn)為是潛在的離群點(diǎn).仿真實(shí)驗(yàn)和實(shí)際數(shù)據(jù)分析表明該方法在一元序列數(shù)據(jù)檢測中是切實(shí)可行的，該方法具有較好的適用性和擴(kuò)展性.

數(shù)據(jù)挖掘；離群點(diǎn)檢測；圖；聚類

近年來，異常模式挖掘又稱離群點(diǎn)檢測得到數(shù)據(jù)挖掘研究社區(qū)的重視.情境離群點(diǎn)是一類特殊的異常模式，又稱條件離群點(diǎn)，因?yàn)樗鼈儣l件的依賴于選定的情境.情境離群點(diǎn)檢測中，數(shù)據(jù)對象的屬性劃分為兩組：情境屬性和行為屬性.情境離群點(diǎn)是局部離群點(diǎn)的推廣.全局離群點(diǎn)檢測可以看做情境離群點(diǎn)檢測的特例，其中情境屬性集為空.與全局離群點(diǎn)檢測不同，在情境離群點(diǎn)檢測中，一個(gè)對象是否是離群點(diǎn)不僅僅依賴于行為屬性，而且還依賴情境屬性.情境通過情境屬性來定義，通常由用戶提供.情境屬性可以包括空間屬性、時(shí)間、網(wǎng)絡(luò)位置和復(fù)雜結(jié)構(gòu)的屬性.與一般的離群點(diǎn)檢測不同，識別情境離群點(diǎn)需要分析對應(yīng)的情境信息.

盡管目前開發(fā)了很多技術(shù)探測離群點(diǎn)，但其中支持情境離群點(diǎn)的方法并不多.目前有兩種一般方法被用來解決情境離群點(diǎn)檢測問題.第一種是把情境離群點(diǎn)檢測轉(zhuǎn)換成傳統(tǒng)的點(diǎn)離群點(diǎn)檢測.第二種方法是利用利用情境對正常行為建模，數(shù)據(jù)的結(jié)構(gòu)信息抽取情境離群點(diǎn).以往挖掘情境離群點(diǎn)的時(shí)間序列模型方法通常依賴數(shù)據(jù)中必須存在周期性規(guī)律，這二種方法在面對不存在周期性模式的數(shù)據(jù)時(shí)，一般很難處理.通常情況下，需要一定數(shù)量的訓(xùn)練數(shù)據(jù)實(shí)例來構(gòu)建分類模型.近年來代表性的情境離群點(diǎn)檢測方法包括：文獻(xiàn)[1]提出利用空間拓?fù)潢P(guān)系進(jìn)行條件離群點(diǎn)檢測，對空間數(shù)據(jù)的實(shí)驗(yàn)證明效果較好.文獻(xiàn)[2]提出了一種條件離群點(diǎn)檢測算法，作者改進(jìn)了基于近鄰的情境離群點(diǎn)檢測算法，通過去掉比較難設(shè)置的參數(shù)變量，提高了之前近鄰情境離群點(diǎn)檢測算法的適用性.文獻(xiàn)[3]基于隨機(jī)游走，提出利用概率方法進(jìn)行情境離群點(diǎn)檢測，通過穩(wěn)態(tài)期望的方式進(jìn)行離群值評分.

本文方法比起以上文獻(xiàn)，原理比較容易理解，具有可擴(kuò)展性可以擴(kuò)展到更復(fù)雜的數(shù)據(jù)集.采用基于圖的有關(guān)算法，包括基于圖的最小生成樹的聚類算法和滑動窗口技術(shù).該方法可以在不同類型的序列數(shù)據(jù)中檢測離群點(diǎn)，在不存在周期性規(guī)律的數(shù)據(jù)中也同樣適用.

1 檢測原理與方法

定義1 序列數(shù)據(jù)：設(shè)I={I1，I2，…，Ip}是所有項(xiàng)的集合.項(xiàng)集是項(xiàng)的非空集合.序列是事件的有序列表.序列s記作〈e1e2e3…el〉，其中事件e1出現(xiàn)在e2之間，e2出現(xiàn)在e3之間，事件ej也稱為s的元素.

定義2 滑動窗口：給定一個(gè)長度m的序列數(shù)據(jù)集D，和一個(gè)用戶預(yù)先定義的子序列長度α，通過使用一個(gè)長度α的滑動窗口穿越D，能夠抽取所有長度α的子序列.

本文有關(guān)情境離群點(diǎn)檢測問題的有關(guān)正式定義如下：

輸入：一個(gè)序列數(shù)據(jù)實(shí)例的集合D，其中包含n個(gè)數(shù)據(jù)實(shí)例{d1，d2，…，dn}.其中每個(gè)數(shù)據(jù)實(shí)例是情境屬性和行為屬性的組合，可以定義為一個(gè)二元組di=〈xi，yi〉，其中xi為情境屬性，yi為行為屬性.

輸出：離群點(diǎn)實(shí)例的集合O；它們的行為屬性與它們在數(shù)據(jù)集中的鄰居數(shù)據(jù)實(shí)例存在明顯不同.

為簡化問題的研究，預(yù)先設(shè)定：① 所有實(shí)例{d1，d2，…，dn}都僅有一個(gè)情境屬性xi；這對于序列數(shù)據(jù)和時(shí)間序列數(shù)據(jù)都成立.這類數(shù)據(jù)集僅有一個(gè)情境屬性就是時(shí)間或者數(shù)據(jù)實(shí)例在數(shù)據(jù)集中的索引值.但是在空間和時(shí)空數(shù)據(jù)中，情境屬性的數(shù)量超過一個(gè)，通過使用更復(fù)雜的滑動窗口技術(shù)，本文的算法可以推廣到存在多個(gè)情境屬性的數(shù)據(jù)集中.② 只有一個(gè)行為屬性yi;所有實(shí)例都有同樣數(shù)量的行為屬性；對于一般同質(zhì)的數(shù)據(jù)集這個(gè)設(shè)定都是成立的，對于異構(gòu)混雜的數(shù)據(jù)，每個(gè)被檢測的數(shù)據(jù)實(shí)例并不是包含同樣數(shù)量的行為屬性，這種情況稱為包含分類屬性，通過采用其他更復(fù)雜的距離測量標(biāo)準(zhǔn)，本文的方法也可以推廣到異構(gòu)混合分類數(shù)據(jù)集中.③ 所有行為屬性都是連續(xù)的；這個(gè)設(shè)定對于日常生活中的序列數(shù)據(jù)集都是成立的.圖1給出了算法流程圖.

1.1 構(gòu)建實(shí)例圖

設(shè)集合D={d1，d2，…，dn}，di=〈xi，yi〉是數(shù)據(jù)實(shí)例對象的集合.首先按照數(shù)據(jù)集的情境屬性對D中數(shù)據(jù)實(shí)例進(jìn)行排序.再為每個(gè)數(shù)據(jù)實(shí)例構(gòu)建一個(gè)結(jié)點(diǎn)，生成一個(gè)帶權(quán)圖G=(V，E，L，λ，ω)，其中V是圖的結(jié)點(diǎn)集合，E是邊的集合，L是標(biāo)號集合，λ:V→L，λ是一個(gè)標(biāo)號函數(shù)用來給結(jié)點(diǎn)分配標(biāo)號，ω:E→R+是一個(gè)權(quán)值函數(shù)用來對每條邊(u，v)∈E分派一個(gè)實(shí)數(shù)w>0作為權(quán)值.λ是一個(gè)單射函數(shù)，G中不存在重復(fù)標(biāo)號.

1.2 生成實(shí)例圖的邊

采用第一個(gè)滑動窗口WIN1從左到右掃描穿越數(shù)據(jù)集.對于數(shù)據(jù)對象di，dj，如果存在|xi-xj|≤α1，就計(jì)算di，dj之間的閔可夫斯基距離：

(1)

閔可夫斯基距離又稱為Lp范數(shù)，文中取p=3.

然后在實(shí)例圖G中，與di，dj對應(yīng)的結(jié)點(diǎn)vi，vj之間連通一條邊e(vi，vj)∈E，邊的權(quán)值：

ω(vi，vj)=Dist(di，dj)；

在這一步，滑動窗口的大小參數(shù)α1對算法的精確度和效率起到關(guān)鍵作用.對于每個(gè)數(shù)據(jù)實(shí)例，要比較的數(shù)據(jù)實(shí)例的個(gè)數(shù)是2(α1-1).因此這步的運(yùn)行時(shí)間是O(|D|α1)，其中|D|是數(shù)據(jù)實(shí)例的個(gè)數(shù).如果α1的值太低，會導(dǎo)致實(shí)例圖G中連接鄰居結(jié)點(diǎn)的邊太少，圖會變的很稀疏，也會導(dǎo)致極差的聚類質(zhì)量.如果α1的值太大，也會導(dǎo)致圖中太多邊，嚴(yán)重影響算法的運(yùn)行時(shí)間.α1的最優(yōu)值取決于被挖掘數(shù)據(jù)的種類和用戶的操作經(jīng)驗(yàn)，通常α1被設(shè)置為輕微大過離群點(diǎn)邊界的尺寸.方法如下：如果離群點(diǎn)的集合是O={d1，d2，…，dn}，計(jì)算任意兩個(gè)離群點(diǎn)的情境屬性之間的索引距離：dinx(i，j)=|xi-xj|，i，j∈[1，n]，α1的值可以設(shè)置為所有索引距離的最大值，這個(gè)最大值就是離群點(diǎn)邊界的尺寸：

(2)

這樣設(shè)置α1的值，算法可以在最短的計(jì)算時(shí)間內(nèi)取得最大精確度.在運(yùn)算結(jié)束之前通常并不知道這個(gè)值的大小，也可以先抽取少量數(shù)據(jù)作為訓(xùn)練集，來計(jì)算出大概的α1的大小，不過這會增加算法的運(yùn)行時(shí)間.

1.3 裁剪實(shí)例圖G中的邊

因?yàn)闃?gòu)建實(shí)例圖G的目的是在下一步中發(fā)現(xiàn)一個(gè)最小生成樹聚類，如果圖G中邊太多，會導(dǎo)致算法運(yùn)行時(shí)間太長，所以可以在這一步中裁剪某些不必要的邊，這對于快速創(chuàng)建最小生成樹聚類有好處.因?yàn)閷τ趩巫兞繑?shù)據(jù)每個(gè)數(shù)據(jù)實(shí)例都僅有一個(gè)行為屬性，可以發(fā)現(xiàn)一個(gè)最小生成樹，其中有|D|條邊的權(quán)值是一樣的.盡管下面提出這個(gè)裁剪方法并不能幫助改進(jìn)第一步的運(yùn)行時(shí)間，但是在輸入數(shù)據(jù)是單變量時(shí)，它可以減少下一步發(fā)現(xiàn)最小生成樹算法的運(yùn)行時(shí)間.本文采取的裁剪方法就是選擇性地創(chuàng)建連通邊，就是在第二步移動第一個(gè)滑動窗口WIN1時(shí)，并不是把所有處于窗口內(nèi)的結(jié)點(diǎn)都創(chuàng)建邊連通，而是選擇性的只選擇一些有代表性的結(jié)點(diǎn)創(chuàng)建邊連通.創(chuàng)建的規(guī)則如下：

對于數(shù)據(jù)集D中的某個(gè)數(shù)據(jù)對象di，在圖G中對應(yīng)的結(jié)點(diǎn)是vi，在所有與vi處于同一個(gè)滑動窗口的所有結(jié)點(diǎn)集合Dwin中，根據(jù)有關(guān)圖理論，設(shè)定vi只與下面6種結(jié)點(diǎn)連通(分別是左邊3個(gè)和右邊3個(gè))：

①vl-:vl-∈Dwin，vj∈Dwin，λ(vj)<λ(vi)，存在λ(vl-)≤λ(vj)&&dl-(y)>di(y)；

②vl：vl∈Dwin，vj∈Dwin，λ(vj)<λ(vi)，存在dl(y)>di(y);

③vl+:vl+∈Dwin，vj∈Dwin，λ(vj)<λ(vi)，存在λ(vl+)≥λ(vj)&&dl+(y)

④vr-:vr-∈Dwin，vj∈Dwin，λ(vj)>λ(vi)，存在λ(vr-)≤λ(vj)&&dr-(y)>di(y);

⑤vr:vr∈Dwin，vj∈Dwin，λ(vj)>λ(vi)，存在dr(y)=di(y);

⑥vr+:vr+∈Dwin，vj∈Dwin，λ(vj)>λ(vi)，存在λ(vr+)≥λ(vj)&&dr+(y)>di(y).

如果圖中還存在其他邊和這6條邊一樣的權(quán)值，就一起刪除.圖2解釋了實(shí)際效果，點(diǎn)劃線框代表滑動窗口WIN1，跟當(dāng)前結(jié)點(diǎn)vi落入同一個(gè)滑動窗口的結(jié)點(diǎn)都列入被考慮連通的范圍，按照上面的規(guī)則，只連通左邊的3個(gè)結(jié)點(diǎn)和右邊的3個(gè)結(jié)點(diǎn)，如圖中粗實(shí)線所示，而同一個(gè)滑動窗口中其他虛線連通結(jié)點(diǎn)都實(shí)際上不與vi連通.對于單變量數(shù)據(jù)集，如果每個(gè)實(shí)例vi都被鏈接到這樣的左邊3個(gè)和右邊3個(gè)的實(shí)例，而不是鏈接到和vi處在同一個(gè)窗口中的所有右邊和左邊的實(shí)例，實(shí)例圖G的最小生成樹的權(quán)值和不會增長[4].

1.4 聚類實(shí)例圖G的結(jié)點(diǎn)

在這一步，采用基于最小生成樹的聚類算法[5]來對輸入數(shù)據(jù)產(chǎn)生的示例圖G的結(jié)點(diǎn)進(jìn)行聚類.算法步驟如下：

步驟1 在無環(huán)帶權(quán)圖G=(V，E，L，λ，ω)上構(gòu)建最小生成樹：

m(MST)=min{m(tree)|tree=(V，E)};

步驟2 按照MST的邊的權(quán)值重新對邊進(jìn)行排序；

步驟3 從MST刪除權(quán)值最大的邊，形成D上的森林，則

步驟4 在第三步刪除邊后尋找連通子圖；獲得森林F中的所有樹

則

(3)

步驟5 把其中每棵樹(Vi，Ei)作為一個(gè)單獨(dú)的聚類Ci=Vi.根據(jù)聚類質(zhì)量的評估標(biāo)準(zhǔn)，來決定聚類效果是否可以接受；

步驟6 如果聚類達(dá)到效果，返回連通子圖作為聚類組份，否則返回步驟3繼續(xù)執(zhí)行.

為了識別在步驟5當(dāng)前聚類是否達(dá)到可以接受的效果，本文采用兩個(gè)判斷標(biāo)準(zhǔn)：

① 第一個(gè)是邊的權(quán)值閾值min_w.如果下一步要刪除的邊的權(quán)值小于一個(gè)預(yù)定義的邊權(quán)閾值min_w，算法就退出循環(huán)，否則回到步驟3繼續(xù)執(zhí)行，重新從MST中刪除邊.在某些情況下，在MST中不一致邊和正常邊的權(quán)值之間存在明顯的邊界.此時(shí)可以發(fā)現(xiàn)這個(gè)邊界并且設(shè)置好邊權(quán)閾值min_w.如果并沒有檢測到不一致邊和正常邊的權(quán)值之間的邊界，也可以繼續(xù)刪除邊直到接近圖中的平均邊權(quán)值.

② 第2個(gè)停止刪除邊的判斷準(zhǔn)則是對刪除邊前后引發(fā)的聚類變化進(jìn)行測量，稱為聚類變化度量系數(shù)μ，計(jì)算方式如下：

(4)

式中:X1，X2，…，Xn為n個(gè)數(shù)據(jù)實(shí)例；Xnd表示實(shí)例Xn的第d個(gè)行為屬性的值；Fkd為在聚類k中的所有實(shí)例的第d個(gè)行為屬性的值總和；Zk為聚類k中數(shù)據(jù)實(shí)例的數(shù)量.

然后采用一個(gè)標(biāo)準(zhǔn)化因子μN(yùn)來除上述公式進(jìn)行標(biāo)準(zhǔn)化從而獲得一個(gè)標(biāo)準(zhǔn)化的μ測量值.對于一個(gè)給定數(shù)據(jù)集，標(biāo)準(zhǔn)化因子μN(yùn)就是μ的最大可能值，就是當(dāng)所有實(shí)例都存在于同一個(gè)聚類內(nèi)部時(shí)可以達(dá)到的μ值，此時(shí)聚類變化度量μ定義為

(5)

式中分母就是μN(yùn)，其中Fd是聚類中所有實(shí)例的第d個(gè)行為屬性值的總和.

為了評價(jià)采用標(biāo)準(zhǔn)化μ評價(jià)聚類效果的可接受性，定義一個(gè)μ的閾值μT，凡是計(jì)算聚類變化系數(shù)μ低于閾值μT的聚類都認(rèn)為是可以接受的.在本文的方法中，不斷刪除邊，從而生成新的聚類，直到μ達(dá)到穩(wěn)定狀態(tài)，也就是刪除一條邊前計(jì)算得到的μ值和刪除一條邊后計(jì)算獲得的μ值并沒有發(fā)生什么改變.正確的算法停止準(zhǔn)則對于算法的性能很關(guān)鍵，最優(yōu)的停止準(zhǔn)則還取決于輸入數(shù)據(jù)的統(tǒng)計(jì)屬性.本文中同時(shí)考慮兩個(gè)準(zhǔn)則，如果兩個(gè)標(biāo)準(zhǔn)中的一個(gè)得到滿足，算法就可以結(jié)束循環(huán).

1.5 檢測離群點(diǎn)

在這一步，上一步的聚類結(jié)果被用來識別情境離群點(diǎn).采用第二個(gè)滑動窗口WIN2對聚類后的數(shù)據(jù)進(jìn)行第二次掃描，這一步的滑動窗口的長度通過投票窗尺寸α2決定.算法步驟描述如下：

步驟1 從擁有最小情境屬性值的數(shù)據(jù)實(shí)例開始進(jìn)行掃描，用數(shù)據(jù)實(shí)例填滿滑動窗口WIN2；

步驟2 計(jì)算當(dāng)前滑動窗口WIN2中屬于每個(gè)聚類的實(shí)例的數(shù)量；

步驟3 在當(dāng)前滑動窗口中，擁有最多數(shù)據(jù)實(shí)例數(shù)量的聚類被認(rèn)為是當(dāng)前滑動窗口中的數(shù)據(jù)主趨勢；

步驟4 對于不屬于當(dāng)前滑動窗口主趨勢的數(shù)據(jù)實(shí)例，增加它們的離群值評分，而對于屬于主趨勢的數(shù)據(jù)實(shí)例，減少它們的離群值評分；

步驟5 如果滑動窗口WIN2還沒有到達(dá)數(shù)據(jù)的末端，就向右邊移動一個(gè)數(shù)據(jù)實(shí)例的位置，然后轉(zhuǎn)向步驟2繼續(xù)執(zhí)行，如果已經(jīng)到了數(shù)據(jù)末端，就轉(zhuǎn)到步驟6；

步驟6 對擁有最高可能離群值評分的實(shí)例進(jìn)行標(biāo)注，標(biāo)記為情境離群點(diǎn).

按照這種方式每次移動滑動窗口，就可以識別在滑動窗口中占優(yōu)勢的聚類，屬于少數(shù)派聚類的數(shù)據(jù)實(shí)例就增加它們的離群值評分.因此在這一步的運(yùn)行時(shí)間在最壞情況下是O(|D|α2).

因?yàn)榛瑒哟翱诿看问窍蛴乙苿右粋€(gè)位置，可能會出現(xiàn)當(dāng)前主趨勢聚類的結(jié)點(diǎn)移動到窗口邊緣時(shí)，變成不占主趨勢的結(jié)點(diǎn)，該結(jié)點(diǎn)的離群值評分也會增加，可能會被誤判為離群點(diǎn).所以在步驟4分配離群值評分的時(shí)候，本文采取雙向評分的方式：

在當(dāng)前滑動窗口WIN2內(nèi)，假設(shè)有若干個(gè)聚類C1，C2，…，Cn，按照如下機(jī)制計(jì)算離群值評分：

主趨勢聚類

對于主趨勢聚類的數(shù)據(jù)結(jié)點(diǎn)di：

Score(di)=-|CM|，di∈CM.

對于其他結(jié)點(diǎn)dj：

Score(dj)=|Cj|，dj?CM.

α1和α2這兩個(gè)參數(shù)的重要功能是可以控制情境屬性覆蓋的規(guī)模，從而控制在每一步算法覆蓋到的數(shù)據(jù)實(shí)例的數(shù)量.如果這兩個(gè)參數(shù)設(shè)置值太低，就變成檢測局部離群點(diǎn)，如果值太高，就變成檢測全局離群點(diǎn).在極端的情況下，如果這兩個(gè)參數(shù)設(shè)置成整個(gè)數(shù)據(jù)集的規(guī)模|D|，算法就會返回針對整個(gè)數(shù)據(jù)集的離群點(diǎn).此時(shí)情境屬性就對離群點(diǎn)檢測過程沒有任何影響力，輸出的離群點(diǎn)是純粹的全局離群點(diǎn).

2 實(shí)驗(yàn)分析

實(shí)驗(yàn)環(huán)境酷睿i3-2100 3.10 GHz雙核CPU，12 G內(nèi)存，Win7系統(tǒng)，Java開發(fā)環(huán)境.在真實(shí)數(shù)據(jù)集上進(jìn)行測試，采用的數(shù)據(jù)集是海洋溫度數(shù)據(jù)SST，來自于NCDC網(wǎng)站[6].采集的數(shù)據(jù)是南太平洋區(qū)域，從東經(jīng)150°，到西經(jīng)70°，緯度是南緯20°，溫度計(jì)數(shù)是每隔0.25°一個(gè)計(jì)數(shù)，時(shí)間是2011年10月1日，整個(gè)下載的數(shù)據(jù)集包含559個(gè)數(shù)據(jù)實(shí)例.每個(gè)數(shù)據(jù)實(shí)例擁有一個(gè)經(jīng)度索引坐標(biāo)和一個(gè)溫度值，在本文中，經(jīng)度坐標(biāo)是情境屬性，而溫度值是行為屬性.

本文設(shè)置第一個(gè)滑動窗口尺寸α1=20，這樣設(shè)置的效果是每個(gè)數(shù)據(jù)實(shí)例可以和它左邊東經(jīng)5°和右邊的西經(jīng)5°的數(shù)據(jù)進(jìn)行比較，按照每0.25°一個(gè)數(shù)據(jù)實(shí)例，剛好20個(gè)數(shù)據(jù)實(shí)例處于一個(gè)滑動窗口內(nèi).因?yàn)樵趯?shí)際溫度中10個(gè)經(jīng)度區(qū)域范圍內(nèi)溫差一般存在明顯變化，所以不大可能存在某個(gè)離群點(diǎn)組成的聚類區(qū)域跨越10個(gè)經(jīng)度，α1=20剛好足夠達(dá)到離群點(diǎn)區(qū)域的最大邊界.根據(jù)數(shù)據(jù)D創(chuàng)建對應(yīng)的實(shí)例圖G后，因?yàn)閳D中邊較多，生成最小生成樹常用的克魯斯卡爾算法不實(shí)用，本文運(yùn)行普里姆算法生成MST.

為了生成聚類，必須從MST中刪除不一致的邊.首先對邊進(jìn)行排序，圖3表示了對邊排序的效果.較大的權(quán)值的邊都是不一致邊，可以看出這些不一致邊的權(quán)值幾乎都大于0.1，因此設(shè)置邊權(quán)閾值min_w為0.1.

從原始數(shù)據(jù)集中選出包含20個(gè)實(shí)例的一部分?jǐn)?shù)據(jù)作為訓(xùn)練集得出評價(jià)聚類質(zhì)量的閾值μT，對訓(xùn)練集運(yùn)用基于MST的聚類生成算法，圖4顯示了μ與聚類數(shù)量的比較關(guān)系，從圖中可以看出，當(dāng)聚類數(shù)量達(dá)到4時(shí)，μ的值基本穩(wěn)定下來，因此對于這個(gè)訓(xùn)練集最合適的就是4個(gè)聚類，此時(shí)對應(yīng)的μ值大概是0.1，因此本文設(shè)置聚類系數(shù)閾值μT為0.1.

在創(chuàng)建完成聚類后，就可以進(jìn)行離群點(diǎn)檢測步驟.在這里設(shè)置第2個(gè)滑動窗口WIN2尺寸α2=80，這樣可以確保規(guī)模最大的離群點(diǎn)聚類區(qū)域在滑動窗口內(nèi)仍然可能屬于少數(shù)派，從而可以把規(guī)模最大的離群點(diǎn)區(qū)域識別為離群點(diǎn).圖5展示了實(shí)際的實(shí)驗(yàn)效果，一共識別出15個(gè)數(shù)據(jù)實(shí)例或者區(qū)域?qū)儆陔x群點(diǎn).

其中B，C，D，G，I，J區(qū)域的溫度與鄰居的溫度值明顯不同，被正確識別為離群點(diǎn).區(qū)域M和N也被識別為離群點(diǎn)，是因?yàn)檫@兩個(gè)區(qū)域的數(shù)據(jù)呈現(xiàn)局部劇烈的變化.在圖中可以看出在這些區(qū)域中，實(shí)例的行為屬性值呈現(xiàn)過于陡峭的下降趨勢，在這些區(qū)域中每個(gè)實(shí)例與它的鄰居實(shí)例比較都有完全不同的行為屬性值，所以在這些區(qū)域中存在很多情境離群點(diǎn).J和O可以看做是全局離群點(diǎn)，因?yàn)橐驗(yàn)樗鼈兊闹迪鄬τ谌侄际潜容^極端.另外可以看出，在最后的3個(gè)區(qū)域M，N，O中，都是小規(guī)模的離群點(diǎn)聚類區(qū)域，每個(gè)區(qū)域都是由單獨(dú)的小規(guī)模聚類組成.該數(shù)據(jù)集如果采用前面文獻(xiàn)提到的兩種普通情境離群點(diǎn)檢測算法，檢測到的離群點(diǎn)數(shù)量會少一些，M和N區(qū)域都識別不到.

3 結(jié) 論

本文中提出一種針對單變量數(shù)據(jù)的情境離群點(diǎn)檢測方法.采用了挖掘序列數(shù)據(jù)的滑動窗口計(jì)數(shù)，有效利用了閔可夫斯基距離作為測量標(biāo)準(zhǔn)，采用了基于圖理論的最小生成樹聚類算法，并且提出了聚類評價(jià)標(biāo)準(zhǔn)函數(shù).對天氣數(shù)據(jù)的實(shí)驗(yàn)結(jié)果表明該方法可以識別其他局部離群點(diǎn)檢測算法識別不了的周邊數(shù)據(jù)實(shí)例差異較大的某些實(shí)例和區(qū)域作為情境離群點(diǎn).該方法比較簡單容易實(shí)現(xiàn)，具有較好的適用性.下一步的工作包括采用更復(fù)雜的滑動窗口技術(shù)把本文的方法推廣到存在多個(gè)情境屬性的數(shù)據(jù)集中，還要嘗試采用其他距離測量標(biāo)準(zhǔn)推廣到包含多個(gè)行為屬性的分類數(shù)據(jù)集中[7].

[1] 顧珊,吉根林.一種基于包含關(guān)系的空間面對象條件離群檢測算法[J].山東大學(xué)學(xué)報(bào)：工學(xué)版,2011,41(2):91-95.

Gu Shan, Ji Genlin.An algorithm for detecting conditional outlier polygons based on inclusion relations[J].Journal of Shandong University: Engineering Science, 2011,41(2):91-95.(in Chinese)

[2] 楊茂林.離群檢測算法研究[D].武漢：華中科技大學(xué),2012.

Yang Maolin.Research on algorithms for outlier detection[D].Wuhan: Huazhong University of Science &Technology, 2012.(in Chinese)

[3] Wang X, Davidson I.Discovering contexts and contextual outliers using random walks in graphs;proceedings of the data mining[C]∥Proceedings of 2009 ICDM’09 Ninth IEEE International Conference on.[S.l.]: IEEE, 2009.

[4] Bollob S B, Kun G, Leader I.Cops and robbers in a random graph [J].Journal of Combinatorial Theory, Series B, 2013, 103(2): 226-236.

[5] 王小樂,劉青寶,陸昌輝,等.一種最小生成樹聚類算法[J].小型微型計(jì)算機(jī)系統(tǒng),2009,30(5):876-881.

Wang Xiaole, Liu Qingbao, Lu Changhui, et al.Minimum spanning tree clustering algorithm[J].Journal of Chinese Computer Systems, 2009,30(5):876-881.(in Chinese)

[6] Tang G, Bailey J, Pei J, et al.Mining multidimensional contextual outliers from categorical relational data[C]∥Proceedings of the 25th International Conference on Scientific and Statistical Database Management.[S.l.]: ACM, 2013.

(責(zé)任編輯：劉芳)

An Approach for Contextual Outlier Detection Based on Graph

LI Tao，ZHANG Yun，HUANG Zhi-hong

(Modern Education Technology Center，South China Agricultural University，Guangzhou 510640，Guangdong，China)

Aiming at the contextual outlier detection problem in abnormal pattern mining, a graph-based detection method was presented, first a graph was built to represent the data instances, then a sliding window was used across the data instance, the Minkowski distance was calculated between nodes for the data instances in the sliding window, the Minkowski distance was adopted as the edges weight.Then the minimum spanning tree clustering algorithm was adopted to cluster the instances graph, finally the second sliding window was adopted cross the data instance, different outlier score was given to the data instance according to the data instance belonged to the main trends clustering or not.The data instances which did not belong to the main trends within the window clustering were considered potential outliers.Simulation experiments and real data analysis show that this algorithm is feasible in binary sequence data； and this method has good applicability and scalability.

data mining;outlier detection;graph;clustering

2014-11-15

國家教育部人文社會科學(xué)研究青年基金項(xiàng)目(15YJC880037)

李濤(1978—)，男，博士生，E-mail:verrazano@126.com.

TP 391

A

1001-0645(2016)03-0302-06

10.15918/j.tbit1001-0645.2016.03.015