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

丁曉陽 羅 陽 王建新

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

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

丁曉陽 羅 陽 王建新

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

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

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

0 引 言

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

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

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

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

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

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

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

(1)

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

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

(0+1)/2 = 0.5

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

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

(2)

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

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

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

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

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

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

輸入：一組基本事件；閾值T；一組事件樹

輸出： 一個抽象事件

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

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

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

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

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

}

返回抽象事件A

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

圖3 簡化事件樹示例

(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)樹的所有結(jié)點集和(b)樹的所有結(jié)點集的笛卡爾乘積，因此有5×8=40個抽象事件。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖4 前序遍歷樹示意圖

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

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

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

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

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

2 DHCSA算法原理概述

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

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

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

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

2.2 事件樹預(yù)處理

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

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

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

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

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

續(xù)表4

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

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

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

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

2.3 找出最小覆蓋事件

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

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

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

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

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

2.4 算法特點

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

表7 新舊兩種剪枝策略特點對比

3 實驗方法與結(jié)果分析

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

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

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

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

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

3.2 算法效率比較試驗

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

表9 兩種算法找出最小覆蓋事件所需時間對比

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

圖6 兩種分布式聚類算法耗時對比圖

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

4 結(jié) 語

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

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

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

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

[4] Marquesdesa J P. 模式識別——原理, 方法及應(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] 隋新, 劉瑩. 入侵檢測技術(shù)的研究[J]. 科技通報, 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-完全問題淺談[J]. 天津理工大學(xué)學(xué)報, 1984(1): 27-34.

[13] 杜立智, 符海東, 張鴻, 等. P 與 NP 問題研究[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ù)庫快速關(guān)聯(lián)規(guī)則挖掘算法[J]. 計算機(jī)科學(xué), 2011, 38(4): 216-220.

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

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

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

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

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

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

[22] 陸嘉恒. Hadoop實戰(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。丁曉陽，碩士生，主研領(lǐng)域：數(shù)據(jù)挖掘。羅陽， 碩士生。王建新，教授。

TP3

A

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