丁曉陽(yáng) 羅 陽(yáng) 王建新

(北京林業(yè)大學(xué)信息學(xué)院 北京 100083)

層次化聚類在分布式計(jì)算環(huán)境中的剪枝策略

丁曉陽(yáng) 羅 陽(yáng) 王建新

(北京林業(yè)大學(xué)信息學(xué)院 北京 100083)

基于樹(shù)結(jié)構(gòu)中結(jié)點(diǎn)覆蓋關(guān)系的一類層次化聚類算法可以對(duì)海量數(shù)據(jù)生成有意義的摘要。然而，該算法已被證明是NP-完全問(wèn)題，求解其精確解需要龐大的計(jì)算量。雖然它在單機(jī)計(jì)算環(huán)境中存在有效的剪枝方法，但在分布式計(jì)算環(huán)境中這種剪枝算法并不可行。相應(yīng)地提出了該層次聚類算法在分布式環(huán)境中的剪枝新策略，通過(guò)綁定結(jié)點(diǎn)與其覆蓋的基本事件構(gòu)成的有序數(shù)組，使窮舉查詢轉(zhuǎn)換為有序數(shù)組的求交集運(yùn)算，并能夠在合并過(guò)程中執(zhí)行大量剪枝，從而在有限的額外空間消耗的基礎(chǔ)上顯著減少計(jì)算時(shí)間。在2組公開(kāi)基準(zhǔn)數(shù)據(jù)集上進(jìn)行了測(cè)試，結(jié)果表明，相比樸素的分布式計(jì)算策略，新的層次化聚類算法在時(shí)間效率上平均有30～40倍左右的提升。

層次化聚類算法 分布式計(jì)算環(huán)境 剪枝操作

0 引 言

聚類分析指在大型數(shù)據(jù)集中發(fā)現(xiàn)積聚現(xiàn)象并加以定量化描述[1]，也就是將一個(gè)由大量抽象對(duì)象組成的集合分組，并得到由類似的對(duì)象組成的多個(gè)子集。在近幾十年中，隨著數(shù)據(jù)規(guī)模的迅猛增長(zhǎng)，單純靠人工很難在海量數(shù)據(jù)中發(fā)現(xiàn)規(guī)律與有用的信息，因此，聚類的重要性及其與其他方向研究的交叉特性也越來(lái)越受到人們的關(guān)注[2]。

傳統(tǒng)聚類算法大致可分為層次聚類算法、劃分聚類算法、基于密度的聚類算法和基于網(wǎng)格聚類算法等[1-3]。其中，層次聚類算法也可稱作樹(shù)聚類算法[4]，其將數(shù)據(jù)對(duì)象視作若干棵事件樹(shù)。

層次聚類的方式一般分為凝聚的層次聚類與分裂的層次聚類[1, 3,5]。而本文中的層次聚類—基于樹(shù)結(jié)構(gòu)中結(jié)點(diǎn)覆蓋關(guān)系的一類層次化聚類算法，既非凝聚也非分裂，而是找出能夠覆蓋一定數(shù)目以上的基本事件且最“緊致”的(也就是最具體的)抽象事件，稱之為最小覆蓋事件[6-7]。這種層次聚類可以對(duì)海量數(shù)據(jù)生成有意義的摘要[6]。

接下來(lái)用實(shí)際的問(wèn)題描述基于樹(shù)結(jié)構(gòu)中結(jié)點(diǎn)覆蓋關(guān)系的層次聚類，在大量女性化妝品單次消費(fèi)數(shù)據(jù)中尋找最常見(jiàn)的某些年齡段的女性單次消費(fèi)某些金額的頻率，便可構(gòu)建如圖1所示的兩棵事件樹(shù)。聚類所處理的數(shù)據(jù)集是由事件樹(shù)的葉子結(jié)點(diǎn)所構(gòu)成的大量基本事件。某個(gè)女性的年齡與她某次消費(fèi)的金額所構(gòu)成的事件，如(“34”,“200”)，即一個(gè)基本事件。

圖1 女性年齡(歲)與化妝品消費(fèi)(元)事件樹(shù)結(jié)構(gòu)示例

抽象事件是由事件森林(多棵事件樹(shù))中的任意結(jié)點(diǎn)向量所構(gòu)成的事件，因此，也可以認(rèn)為基本事件是一類特殊的抽象事件。兩個(gè)抽象事件之間距離的判斷依據(jù)是兩個(gè)事件對(duì)應(yīng)的分量(結(jié)點(diǎn))間的距離，而同一棵樹(shù)中兩個(gè)結(jié)點(diǎn)間的距離為結(jié)點(diǎn)間有向弧的條數(shù)。圖1的上圖中結(jié)點(diǎn)“13”到結(jié)點(diǎn)“全部年齡”間的距離為3。但由于結(jié)點(diǎn)“未成年人”與結(jié)點(diǎn)“34”之間沒(méi)有祖先-后代關(guān)系，因此這兩個(gè)結(jié)點(diǎn)間的距離無(wú)定義[6]。

定義1 抽象事件之間的距離定義為其對(duì)應(yīng)分量距離的平均值[4]。若事件森林中共有n棵事件樹(shù)，di為事件a的第i個(gè)分量與事件b的第i個(gè)分量之間的距離，則事件a與事件b之間的距離為：

(1)

在圖1中，抽象事件(“18”,“中等”)到抽象事件(“18”, “201”)的距離[7]為：

(d(“18”,“18”) +d(“中等”,“201”) )/2=

(0+1)/2 = 0.5

且由于抽象事件(“18”,“201”)中每一個(gè)分量均為事件(“18”,“中等”)相應(yīng)分量本身或其子孫，因此(“18”,“中等”)覆蓋(“18”,“201”)。

定義2 若某個(gè)抽象事件a覆蓋了m個(gè)基本事件，d(a,bi)為抽象事件a到其覆蓋的第i個(gè)基本事件bi之間的距離，則該抽象事件距離其覆蓋的所有基本事件的平均距離為：

(2)

所以最小覆蓋事件本身也是一個(gè)抽象事件，它不僅能覆蓋不少于指定閾值數(shù)的基本事件，且距其覆蓋的所有基本事件的平均距離均值最小(也就是這個(gè)抽象事件需要最具體化)。

根據(jù)圖1描述的情形，若有3個(gè)基本事件(“13”,“202”)、(“16”, “215”)與(“60”,“501”)，閾值設(shè)置為2，則最小覆蓋事件應(yīng)為(“未成年人”,“中等”)。因?yàn)樵撌录軌蚋采w(“13”,“202”)與(“16”,“215”)，且距這2個(gè)基本事件的平均距離為1；而其他符合閾值條件的抽象事件距其覆蓋的基本事件的平均距離均大于1。例如，(“全部年齡”,“全部金額”)能夠覆蓋全部基本事件，但其距離所有能覆蓋的基本事件的平均距離為2.33，大于1。換句話說(shuō)，抽象事件(“全部年齡”,“全部金額”)不如(“未成年人”,“中等”)能夠更加具體地代表給出的3個(gè)基本事件[8]。也就是說(shuō)，抽象事件(“未成年人”,“中等”)是基本事件的、滿足閾值條件的、最有意義的摘要。

可以看出，基于樹(shù)結(jié)構(gòu)中結(jié)點(diǎn)覆蓋關(guān)系的層次聚類算法的主要思想是在全部抽象事件中找出一個(gè)符合要求的抽象事件。在閾值確定的情況下，聚類的結(jié)果不僅是唯一的，也是精確的。

基于樹(shù)結(jié)構(gòu)中結(jié)點(diǎn)覆蓋關(guān)系的層次聚類算法所應(yīng)用的領(lǐng)域相當(dāng)廣泛。例如，用于應(yīng)對(duì)網(wǎng)絡(luò)攻擊的入侵檢測(cè)系統(tǒng)(IDS)[9]每天會(huì)接收到大量的警報(bào)[8]，其中高達(dá)99%為由良性事件所觸發(fā)的誤報(bào)，導(dǎo)致真陽(yáng)性事件難以被發(fā)現(xiàn)[10]。如此大量的誤報(bào)會(huì)給操作者和決策者帶來(lái)很大負(fù)擔(dān)，為此,可采用如圖2所示的樹(shù)形結(jié)構(gòu)進(jìn)行層次聚類，幫助操作者理解和判斷[7]。

圖2 入侵檢測(cè)系統(tǒng)ip地址與端口分類樹(shù)結(jié)構(gòu)示例

基于樹(shù)結(jié)構(gòu)中結(jié)點(diǎn)覆蓋關(guān)系的層次聚類已被證明為一種NP-完全問(wèn)題[6, 11]，即隨著樹(shù)結(jié)構(gòu)數(shù)量的增加無(wú)法在多項(xiàng)式時(shí)間內(nèi)求得解的問(wèn)題[12]。這類問(wèn)題無(wú)法通過(guò)計(jì)算求得正確解，但可驗(yàn)證某個(gè)解是否正確[13]。換句話說(shuō)，每個(gè)抽象事件均可能是最小覆蓋事件，但不存在直接找出最小覆蓋事件的多項(xiàng)式時(shí)間算法，在理論上每個(gè)抽象事件都要進(jìn)行判斷。Julisch[10]給出了如下的近似算法[14]。

輸入：一組基本事件；閾值T；一組事件樹(shù)

輸出： 一個(gè)抽象事件

選擇任意由葉子結(jié)點(diǎn)組合構(gòu)成的抽象事件A

當(dāng) (A覆蓋的基本事件數(shù)小于T) {

選擇抽象事件A的任意一個(gè)結(jié)點(diǎn)a；

用a的父結(jié)點(diǎn)b替換a；

把A更新為包含b的更加抽象的事件。

}

返回抽象事件A

全部抽象事件的數(shù)量為每個(gè)事件樹(shù)結(jié)點(diǎn)數(shù)的笛卡爾積。表1為由圖3中事件樹(shù)所組成的所有抽象事件。

圖3 簡(jiǎn)化事件樹(shù)示例

(a b)(a1 b2)(a11 b12)(a12 b14)(a b1)(a1 b11)(a11 b13)(a12 b15)(a b2)(a1 b12)(a11 b14)(a13 b)(a b11)(a1 b13)(a11 b15)(a13 b1)(a b12(a1 b14)(a12 b)(a13 b2)

續(xù)表1

表1中所有抽象事件是圖3中(a)樹(shù)的所有結(jié)點(diǎn)集和(b)樹(shù)的所有結(jié)點(diǎn)集的笛卡爾乘積，因此有5×8=40個(gè)抽象事件。

隨著事件樹(shù)個(gè)數(shù)的增多，抽象事件數(shù)將以指數(shù)形式增長(zhǎng)，計(jì)算量也將愈加龐大。算法的時(shí)間復(fù)雜度高也是層次聚類普遍具有的缺點(diǎn)[1]。為應(yīng)對(duì)該問(wèn)題，需要分布式計(jì)算的手段，使聚類任務(wù)在多個(gè)計(jì)算節(jié)點(diǎn)上并行處理。目前流行的聚類分析的策略是將聚類算法與常用于處理大數(shù)據(jù)的分布式計(jì)算平臺(tái)相結(jié)合，設(shè)計(jì)出高效的算法[15-16]。對(duì)于一個(gè)需要十分巨大的計(jì)算能力才能解決的問(wèn)題，分布式計(jì)算能將該問(wèn)題分成許多小的部分，再將這些部分分配給多臺(tái)計(jì)算機(jī)進(jìn)行并行運(yùn)算[17]。

集群是分布式計(jì)算環(huán)境中的常用結(jié)構(gòu)之一。在該結(jié)構(gòu)中，各個(gè)計(jì)算機(jī)之間通信較少，運(yùn)算基本上獨(dú)立進(jìn)行。為了統(tǒng)計(jì)某個(gè)抽象事件覆蓋的基本事件數(shù)，并不是將基本事件數(shù)據(jù)存儲(chǔ)到集群，而需將所有抽象事件分布到集群中，通過(guò)并行計(jì)算找出最小覆蓋事件，這樣可以顯著減少計(jì)算時(shí)間，一定程度上解決這種NP-完全問(wèn)題中的適中的輸入規(guī)模問(wèn)題。事實(shí)上，基于結(jié)點(diǎn)覆蓋關(guān)系的層次化聚類分析中所用的樹(shù)結(jié)構(gòu)的數(shù)量一般在3至10棵，是可以通過(guò)分布式計(jì)算獲得其精確最優(yōu)解的。分布式計(jì)算方法MapReduce模型[18-19]是比較適合的處理方式之一，其核心思想為將執(zhí)行的問(wèn)題拆解成映射(Map)和規(guī)約(Reduce)操作，即先通過(guò)Map程序?qū)?shù)據(jù)分割，分配給大量計(jì)算機(jī)處理，再通過(guò)Reduce程序?qū)⒔Y(jié)果匯總，輸出結(jié)果[18-19]。

然而在以往的研究中，前文所述層次聚類并不適合在分布式集群中解決。由于所有的抽象事件均由事件樹(shù)結(jié)點(diǎn)構(gòu)成，因此抽象事件間有一定的耦合關(guān)系，即一個(gè)抽象事件需要根據(jù)與其關(guān)聯(lián)的其他抽象事件判斷其是否覆蓋某個(gè)或某些基本事件。若在單機(jī)環(huán)境中進(jìn)行層次聚類，程序可以跳過(guò)這些被推斷為不符合條件的抽象事件，從而大大減少運(yùn)算時(shí)間。這種操作稱為“剪枝”。但要處理更大規(guī)模的樹(shù)結(jié)構(gòu)集合，則單機(jī)處理方案因計(jì)算能力有限而不可行。若在集群上進(jìn)行該層次聚類操作，則抽象事件會(huì)作為相互獨(dú)立的個(gè)體分布到集群中，導(dǎo)致上述剪枝操作無(wú)法實(shí)施。而對(duì)所有的抽象事件進(jìn)行所有基本事件的覆蓋判斷會(huì)大大增加計(jì)算時(shí)間耗費(fèi)。

針對(duì)上述問(wèn)題，本文提出了一種新的層次聚類機(jī)制—基于有序數(shù)組的分布式層次聚類算法，稱為DHCSA (Distributed Hierarchical Clustering based on Sorted Arrays)，其中使用了一種剪枝新策略，既滿足分布式計(jì)算條件，也就是將抽象事件視作獨(dú)立個(gè)體，又可以進(jìn)行剪枝，從而大大減少聚類消耗的時(shí)間。該算法能借助集群對(duì)大數(shù)據(jù)和密集計(jì)算的處理能力，解決這種NP-完全問(wèn)題中常見(jiàn)的輸入規(guī)模情形。

1 單機(jī)層次聚類剪枝和樸素分布式方案概述

聚類算法在單機(jī)上運(yùn)行時(shí)，會(huì)有諸如單位時(shí)間內(nèi)處理量小、對(duì)大量數(shù)據(jù)處理的時(shí)間會(huì)很長(zhǎng)等問(wèn)題。但較小規(guī)模的層次聚類算法能在單機(jī)環(huán)境下高效運(yùn)行，得益于其剪枝策略，即部分抽象事件可以直接略過(guò)不進(jìn)行處理。

1.1 輸入數(shù)據(jù)預(yù)處理

如表2所示，在聚類前對(duì)基本事件進(jìn)行分類統(tǒng)計(jì)，得到每個(gè)基本事件的統(tǒng)計(jì)信息(即個(gè)數(shù))。

表2 輸入數(shù)據(jù)預(yù)處理示例

在表2中，每種基本事件在預(yù)處理之前都是結(jié)點(diǎn)向量的形式；在預(yù)處理之后，相同的基本事件被合并，重復(fù)出現(xiàn)的次數(shù)增添為向量的最后一個(gè)分量。

1.2 單機(jī)層次聚類剪枝原理概述

在事件森林中，按照如圖4所示的路徑順序遍歷每棵事件樹(shù)的結(jié)點(diǎn)，從而遍歷所有抽象事件，統(tǒng)計(jì)每個(gè)抽象事件覆蓋的基本事件數(shù)。統(tǒng)計(jì)的方法如下[20]：

遍歷過(guò)程中的一個(gè)基本的操作是判斷抽象事件與每個(gè)基本事件的覆蓋關(guān)系。為此，首先判斷抽象事件的第一個(gè)分量是否覆蓋基本事件的第一個(gè)分量，若是，則依次判斷之后的分量；否則不能覆蓋，直接跳到下一個(gè)基本事件。若該抽象事件的所有分量均覆蓋該基本事件的相應(yīng)分量，則該抽象事件覆蓋該基本事件，將該基本事件的重復(fù)次數(shù)加到該抽象事件的覆蓋事件數(shù)中。

若該抽象事件的覆蓋事件數(shù)超過(guò)指定閾值，則計(jì)算它到其覆蓋的所有基本事件的平均距離。若小于之前找出的最小覆蓋事件的平均距離，則將該抽象事件取代已知的最小覆蓋事件，成為當(dāng)前的最小覆蓋事件。

在前序遍歷抽象事件中，當(dāng)某個(gè)抽象事件覆蓋的基本事件數(shù)小于閾值時(shí)，便可以進(jìn)行剪枝，即跳過(guò)由該抽象事件所覆蓋的所有其他抽象事件。以圖3為例，若抽象事件(a1, b1)覆蓋的基本事件數(shù)小于閾值，則可跳過(guò)由 (a1, b1)所覆蓋的其他抽象事件，如(a1, b11)和(a11, b1)等，并繼續(xù)由抽象事件(a1, b2)開(kāi)始判斷。

圖4 前序遍歷樹(shù)示意圖

1.3 樸素分布式層次聚類算法原理概述

樸素分布式層次聚類算法與單機(jī)層次聚類算法的基本事件數(shù)據(jù)預(yù)處理的方式相同，也是對(duì)基本事件進(jìn)行分類統(tǒng)計(jì)。

而對(duì)于抽象事件的遍歷并非基于事件樹(shù)的遍歷，而是將所有的抽象事件生成一個(gè)新的數(shù)據(jù)集，并分布到集群的各個(gè)計(jì)算節(jié)點(diǎn)中去。新的數(shù)據(jù)集如表1所示，它是由圖3所示樹(shù)結(jié)構(gòu)形成的所有抽象事件集。

與單機(jī)層次聚類算法相似，樸素分布式層次聚類算法需要遍歷抽象事件集，判斷每個(gè)抽象事件覆蓋的基本事件數(shù)。若覆蓋數(shù)超過(guò)閾值，則計(jì)算平均距離，最終找出最小覆蓋事件。但是，集群環(huán)境中的每個(gè)計(jì)算單元只考慮本單元所分配的抽象事件是滿足閾值條件，而且給管理單元匯報(bào)其中距離最小的抽象事件；管理單元在所有計(jì)算單元匯報(bào)的抽象事件中再選取距離最小者，作為最終結(jié)果。

可以看出，與單機(jī)環(huán)境中的層次聚類算法相比，樸素的分布式層次聚類算法中各個(gè)抽象事件之間是獨(dú)立判斷的，沒(méi)有依賴關(guān)系，沒(méi)有信息共享，因此不能進(jìn)行剪枝，從而致使效率低下。而在單機(jī)環(huán)境下，一個(gè)抽象事件不滿足閾值條件，可以推理出若干個(gè)抽象事件也不滿足閾值條件，從而形成有效的剪枝。因此，需要進(jìn)一步挖掘在分布式環(huán)境中的可行的剪枝方式。

2 DHCSA算法原理概述

為了在分布式環(huán)境下運(yùn)行，DHCSA算法也需要對(duì)所有抽象事件進(jìn)行判斷，而判斷過(guò)程中使用了一種新的剪枝方式。

2.1 輸入數(shù)據(jù)預(yù)處理

DHCSA算法的數(shù)據(jù)預(yù)處理是在單機(jī)版本算法的數(shù)據(jù)預(yù)處理的基礎(chǔ)上，為每種基本事件添加一個(gè)編號(hào)，如表3所示。

表3 DHCSA算法輸入數(shù)據(jù)預(yù)處理示例

2.2 事件樹(shù)預(yù)處理

分別遍歷每棵事件樹(shù)，并給每個(gè)結(jié)點(diǎn)綁定一個(gè)有序數(shù)組，其內(nèi)容為所有包含其覆蓋結(jié)點(diǎn)的基本事件編號(hào)，如圖5所示。例如，a1綁定的數(shù)組為所有包含a11與a12的基本事件編號(hào)。由于根結(jié)點(diǎn)必包含所有基本事件編號(hào)，因此可不進(jìn)行處理。

圖5 樹(shù)結(jié)點(diǎn)掛接的有序數(shù)組

以下為綁定數(shù)組的方法和步驟：

(1) 在找出某結(jié)點(diǎn)所要綁定的所有基本事件編號(hào)時(shí)，可將所有基本事件按照該結(jié)點(diǎn)所在樹(shù)的葉子結(jié)點(diǎn)的順序進(jìn)行排列，借助該序列可提高綁定數(shù)組的效率，如表4所示為分別根據(jù)a樹(shù)與b樹(shù)的葉子結(jié)點(diǎn)順序排列的基本事件。

表4 事件樹(shù)預(yù)處理示例(根據(jù)樹(shù)結(jié)構(gòu)(a與b)排列事件)

續(xù)表4

(2) 為每個(gè)結(jié)點(diǎn)綁定數(shù)組。如表5所示，若處理的是葉子結(jié)點(diǎn)，以b13為例，直接將包含b13的事件編號(hào)組成數(shù)組賦予b13，共3種基本事件。

表5 葉子結(jié)點(diǎn)的數(shù)組示例(結(jié)點(diǎn)b13的數(shù)組)

(3) 若處理的是非葉子結(jié)點(diǎn)，則如表6所示，在根據(jù)該樹(shù)排序的基本事件集中找出該結(jié)點(diǎn)的左葉子結(jié)點(diǎn)與右葉子結(jié)點(diǎn)。以b2為例，找出b13與b15；將包含b13的事件、包含b15的事件及兩者之間的事件編號(hào)共同組成有序數(shù)組賦予b2，共3+1+1=5種基本事件。

表6 非葉子結(jié)點(diǎn)的數(shù)組示例(結(jié)點(diǎn)b2的數(shù)組)

2.3 找出最小覆蓋事件

遍歷所有的抽象事件，根據(jù)每個(gè)結(jié)點(diǎn)所綁定的數(shù)組判斷其是否為覆蓋某個(gè)或某些基本事件。某個(gè)結(jié)點(diǎn)所覆蓋的基本事件的數(shù)量可以通過(guò)它所綁定的數(shù)組計(jì)算取得：即把數(shù)組的每個(gè)元素(即某種基本事件的序號(hào))對(duì)應(yīng)的基本事件重復(fù)次數(shù)相加。例如在表6中，結(jié)點(diǎn)b2對(duì)應(yīng)的數(shù)組是[0, 1, 2, 4, 5]，那么b2對(duì)應(yīng)的基本事件的數(shù)量是2+3+2+1+3=11。

顯然，將抽象事件中所有結(jié)點(diǎn)對(duì)應(yīng)的數(shù)組取交集的結(jié)果即為該抽象事件所覆蓋的所有基本事件。如果所覆蓋基本事件數(shù)小于指定的閾值，則該抽象事件可跳過(guò)。因此，在這里可以進(jìn)行另一種剪枝。

(1) 將當(dāng)前抽象事件結(jié)點(diǎn)向量(結(jié)點(diǎn)個(gè)數(shù)為n)對(duì)應(yīng)的n個(gè)數(shù)組按照數(shù)組長(zhǎng)度由小到大進(jìn)行排序：如抽象事件(a1, b11)對(duì)應(yīng)的兩個(gè)數(shù)組分別為[0, 1, 2, 3, 4]和[1]，則排列后為[1]和[0, 1, 2, 3, 4]，也就是優(yōu)先對(duì)b11對(duì)應(yīng)的數(shù)組[1]進(jìn)行處理。

(2) 判斷第一個(gè)數(shù)組中基本事件的個(gè)數(shù)和是否小于閾值。若是，則說(shuō)明該抽象事件所覆蓋的基本事件數(shù)必定小于閾值，因此直接跳過(guò)并處理下一個(gè)抽象事件，這一步即新的剪枝；否則(第一個(gè)數(shù)組中事件的個(gè)數(shù)符合閾值條件)，則將其與之后的數(shù)組依次取交集，且每次均判斷其結(jié)果所包含的基本事件數(shù)與閾值的大小關(guān)系；一旦小于閾值，則判斷終止，并跳轉(zhuǎn)到下一個(gè)抽象事件。

(3) 若最終所有數(shù)組的交集所包含的基本事件數(shù)仍大于閾值，則計(jì)算該抽象事件到所有其覆蓋的基本事件的平均距離。整個(gè)過(guò)程中出現(xiàn)的平均距離最小的抽象事件即為最小覆蓋事件。

2.4 算法特點(diǎn)

DHCSA算法中所有抽象事件之間均為獨(dú)立的，因此可以運(yùn)行在分布式集群上；并且在計(jì)算過(guò)程中執(zhí)行大量的剪枝操作，能夠顯著減少計(jì)算時(shí)間。這一過(guò)程中的一個(gè)常用操作是求兩個(gè)有序數(shù)組的交集。眾所周知，如果兩個(gè)或多個(gè)數(shù)組是無(wú)序的，則求交集運(yùn)算的時(shí)間復(fù)雜度是平方級(jí)別的；但如果數(shù)組是有序的，則這個(gè)操作的時(shí)間復(fù)雜度是線性的，因此運(yùn)算效率很高。這也是DHCSA算法高效性的主要因素之一。如表7所示為新舊兩種剪枝方法的特點(diǎn)比較。

表7 新舊兩種剪枝策略特點(diǎn)對(duì)比

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

由于并不存在其他能夠在分布式環(huán)境下實(shí)現(xiàn)的剪枝策略，因此在本節(jié)中，將在分布式環(huán)境下用基準(zhǔn)數(shù)據(jù)集對(duì)樸素分布式層次聚類算法與DHCSA算法的效率進(jìn)行比較，驗(yàn)證DHCSA算法的有高效性。

3.1 實(shí)驗(yàn)環(huán)境和數(shù)據(jù)集

集群由2臺(tái)普通PC組成，其中一臺(tái)作為主節(jié)點(diǎn)(master)，另一臺(tái)作為從節(jié)點(diǎn)(slave)；在Linux操作系統(tǒng)Ubuntu中全部采用Java環(huán)境，JDK版本是：JDK1.6.0-39；實(shí)驗(yàn)與編譯環(huán)境：Eclipse SDK 3.5.2；Hadoop[21,22]平臺(tái)：Hadoop 0.20.2。

本文選取了UCI數(shù)據(jù)集[23]中的2個(gè)數(shù)據(jù)集對(duì)DHCSA算法與樸素分布式層次聚類算法的效率進(jìn)行比較，所列信息包括數(shù)據(jù)集名稱、基本事件數(shù)、事件樹(shù)數(shù)量和抽象事件數(shù)等內(nèi)容。數(shù)據(jù)集的具體信息如表8所示。

表8 實(shí)驗(yàn)所使用的UCI數(shù)據(jù)集

3.2 算法效率比較試驗(yàn)

實(shí)驗(yàn)內(nèi)容是在相同的環(huán)境和平臺(tái)上分別運(yùn)行DHCSA算法和與樸素分布式層次聚類算法的效率，兩種算法所得出的結(jié)果都是完全一致的。實(shí)驗(yàn)結(jié)果如表9所示(其中，T1為樸素分布式層次聚類算法所消耗時(shí)間；T2為DHCSA算法所消耗時(shí)間)：

表9 兩種算法找出最小覆蓋事件所需時(shí)間對(duì)比

圖6是樸素的分布式聚類算法和新提出的聚類算法DHCSA處理相同的數(shù)據(jù)集所需時(shí)間的對(duì)比圖。圖中橫軸是經(jīng)過(guò)樹(shù)結(jié)構(gòu)分割處理后，數(shù)據(jù)集所產(chǎn)生的基本事件數(shù)量；縱軸是聚類所需時(shí)間。

圖6 兩種分布式聚類算法耗時(shí)對(duì)比圖

由圖6可看出，相比樸素的分布式計(jì)算策略，DHCSA算法在時(shí)間效率上至少有30倍的提升，有些甚至超過(guò)40倍；且隨著基本事件數(shù)的增多，DHCSA算法的效率提升更明顯。

4 結(jié) 語(yǔ)

本文提出一種新型層次聚類算法DHCSA，針對(duì)單機(jī)版剪枝操作無(wú)法在集群上實(shí)現(xiàn)、樸素分布式層次聚類算法效率低等問(wèn)題，采用了一種不涉及抽象事件之間耦合關(guān)系的新剪枝策略，使層次化聚類算法能夠高效地在分布式集群上運(yùn)行。實(shí)驗(yàn)結(jié)果表明，對(duì)于數(shù)據(jù)量的不同大小和事件的不同復(fù)雜程度，DHCSA算法的運(yùn)算效率均遠(yuǎn)高于樸素分布式層次聚類算法，并且數(shù)據(jù)量越大，DHCSA算法的高效率特性便越顯著。

[1] 周濤, 陸惠玲. 數(shù)據(jù)挖掘中聚類算法研究進(jìn)展[J]. 計(jì)算機(jī)工程與應(yīng)用, 2012,48(12):100-111.

[2] 孫吉貴, 劉杰, 趙連宇. 聚類算法研究[J]. 軟件學(xué)報(bào), 2008,19(1): 48-61.

[3] 覃艷, 王洪, 周全華. 數(shù)據(jù)挖掘中聚類算法的研究[J]. 網(wǎng)絡(luò)安全技術(shù)與應(yīng)用, 2014 (1): 65-66.

[4] Marquesdesa J P. 模式識(shí)別——原理, 方法及應(yīng)用[M]. 吳逸飛，譯. 清華大學(xué)出版社，2002: 51-74.

[5] 韓家煒, Kamber M. 數(shù)據(jù)挖掘: 概念與技術(shù)[M]. 3版. 機(jī)械工業(yè)出版社，2012:298-300.

[6] Julisch K. Mining alarm clusters to improve alarm handling efficiency [C] //Computer Security Applications Conference. IEEE, 2001: 12-21.

[7] Wang Jianxin, Zhao Geng, Zhang Weidong. A subjective distance for clustering security events [C] //Communications, Circuits and Systems. IEEE, 2005, 1: 74-78.

[8] Julisch K. Dealing with false positives in intrusion detection [C]. In: Recent Advances in Intrusion Detection(RAID 2000), Toulouse, 2000: 113-119.

[9] 隋新, 劉瑩. 入侵檢測(cè)技術(shù)的研究[J]. 科技通報(bào), 2014, 30(11): 89-94.

[10] Julisch K. Clustering intrusion detection alarms to support root cause analysis [J]. ACM Transactions on Information and System Security (TISSEC), 2003, 6(4): 443-471.

[11] Julisch K, Dacier M. Mining intrusion detection alarms for actionable knowledge [C] // Proceedings of the 8th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2002: 366-375.

[12] 李昭智. NP-完全問(wèn)題淺談[J]. 天津理工大學(xué)學(xué)報(bào), 1984(1): 27-34.

[13] 杜立智, 符海東, 張鴻, 等. P 與 NP 問(wèn)題研究[J]. 計(jì)算機(jī)技術(shù)與發(fā)展, 2013, 23(1): 37-42.

[14] Wang Jianxin, Wang Hongzhou, Zhao Geng. A GA-based solution to an NP-hard problem of clustering security events [C] //Communications, Circuits and Systems Proceedings. IEEE, 2006, 3: 2093-2097.

[15] 崔建, 李強(qiáng), 楊龍坡. 基于垂直數(shù)據(jù)分布的大型稠密數(shù)據(jù)庫(kù)快速關(guān)聯(lián)規(guī)則挖掘算法[J]. 計(jì)算機(jī)科學(xué), 2011, 38(4): 216-220.

[16] 鄭湃, 崔立真, 王海洋, 等. 云計(jì)算環(huán)境下面向數(shù)據(jù)密集型應(yīng)用的數(shù)據(jù)布局策略與方法[J]. 計(jì)算機(jī)學(xué)報(bào), 2010, 33(8): 1472-1480.

[17] 葛澎. 分布式計(jì)算技術(shù)概述[J]. 微電子學(xué)與計(jì)算機(jī), 2012, 29(5): 201-204.

[18] 李成華, 張新訪, 金海, 等. MapReduce: 新型的分布式并行計(jì)算編程模型[J]. 計(jì)算機(jī)工程與科學(xué), 2011, 33(3):129-135.

[19] 劉向東, 劉奎, 胡飛翔, 等. 基于MapReduce的并行聚類算法設(shè)計(jì)與實(shí)現(xiàn)[J]. 計(jì)算機(jī)應(yīng)用與軟件, 2014,31(11):251-256.

[20] 肖政, 王建新, 侯紫峰, 等. 基于搜索樹(shù)的告警高效聚類算法和 Bayes 分類器的設(shè)計(jì)和研究[J]. 計(jì)算機(jī)科學(xué), 2006, 33(8): 190-194.

[21] 沈利香, 曹國(guó). 分布式計(jì)算環(huán)境下的入侵檢測(cè)數(shù)據(jù)分類研究[J]. 計(jì)算機(jī)與現(xiàn)代化, 2015 (12): 43-47.

[22] 陸嘉恒. Hadoop實(shí)戰(zhàn)[M]. 機(jī)械工業(yè)出版社, 2011:2-10.

[23] Merz C J, Murphy P M. UCI Repository of machine learning datasets [EB/OL]. (1998). http//www.ics.uci. edu/～mlearn/MLRepository.html.

PRUNING STRATEGY OF HIERARCHICAL CLUSTERING IN DISTRIBUTED COMPUTING ENVIRONMENT

Ding Xiaoyang Luo Yang Wang Jianxin

(SchoolofInformation,BeijingForestryUniversity,Beijing100083，China)

A hierarchical clustering algorithm based on the node coverage relation in the tree structure can generate meaningful abstracts for the massive data. However, this algorithm has been proved to be an NP-complete problem, and its exact solution requires a large amount of computation. Although it has an effective pruning method in stand-alone computing environment, this pruning algorithm is not feasible in a distributed computing environment. A new pruning strategy of hierarchical clustering algorithm in distributed environment is proposed. By binding an ordered array of nodes and basic events that they cover, an exhaustive query is converted to an intersection set of ordered arrays, and a large number of pruning can be performed during the merge process. Thereby significantly reducing the computational time on the basis of limited additional space consumption. Tests were performed on two sets of open reference datasets. The results show that the new hierarchical clustering algorithm has 30～40 times improvement in time efficiency compared with the simple distributed computing strategy.

Hierarchical clustering algorithm Distributed computing environment Pruning operation

2016-05-04。丁曉陽(yáng)，碩士生，主研領(lǐng)域：數(shù)據(jù)挖掘。羅陽(yáng)， 碩士生。王建新，教授。

TP3

A

10.3969/j.issn.1000-386x.2017.05.045