◆劉康明 艾鴿 張宇 傅毓

基于層次聚類和劃分聚類算法的BTS聚類算法研究

◆劉康明 艾鴿 張宇 傅毓

（深圳市國家保密科技測評中心 廣東 518000）

BTS（Best Two Step）聚類算法是結(jié)合層次聚類和劃分聚類算法的兩步聚類算法。層次聚類算法類與類之間不可以對象交換，很容易造成聚類質(zhì)量不高的結(jié)果。而劃分聚類對于初始值的設(shè)定以及異常噪聲數(shù)據(jù)都很敏感，所以我們研究提出了BTS算法，實驗證明BTS算法可達(dá)到高質(zhì)量的聚類效果。

BTS算法；層次聚類；劃分聚類

1 引言

數(shù)據(jù)挖掘是很大的研究領(lǐng)域，本文主要針對離群數(shù)據(jù)挖掘[1]。離群數(shù)據(jù)挖掘工作一般分為兩個部分：離群數(shù)據(jù)的檢測[2]和離群數(shù)據(jù)的分析[3]。本文主要研究離群數(shù)據(jù)挖掘的關(guān)鍵部分：離群數(shù)據(jù)的檢測。離群數(shù)據(jù)的檢測近年來受到了很大的關(guān)注，出現(xiàn)了非常多的算法。層次聚類算法操作簡單，能夠細(xì)致地看出由小類聚成大類的過程，數(shù)據(jù)集之間的親疏程度可以由合并過程中的水平距離看出，層次聚類也可以有效地找出異常值。但是層次聚類比較明顯的不足是：無法回溯撤銷，一旦一組數(shù)據(jù)對象合并，下一步的操作是在新合并成的類中進行，只要完成了一個步驟，它就無法撤銷，類與類之間不可以對象交換，很容易造成聚類質(zhì)量不高的結(jié)果。而劃分聚類一般都是線性復(fù)雜度，很適合用于挖掘大規(guī)模數(shù)據(jù)，具有伸縮性好、高效性、簡單易行的優(yōu)點，但是對于初始值的設(shè)定以及異常噪聲數(shù)據(jù)都很敏感，所以我們研究提出了BTS算法，結(jié)合NChameleon聚類算法和NK-means算法，兩個算法互相彌補不足，達(dá)到高質(zhì)量的聚類效果。

2 相關(guān)理論

2.1 NChameleon聚類算法思想

NChameleon算法主要思想是：第一階段是形成小簇集的過程，第二個階段是合并這些小聚簇形成最終的結(jié)果聚簇。為了保證結(jié)果的真實性，只有聚合之后的結(jié)果簇與組成這個結(jié)果簇的兩個子簇之間相似時，這兩個子簇才會被合并在一起，也是確保被合并的子簇是具有最相似性的。

NChameleon算法主要有三步：構(gòu)造k-最近鄰圖、劃分Gk圖形成最初子簇、合并最初子簇形成結(jié)果簇。如圖1所示

NChameleon算法為了確定最具有相似性的子簇對，不僅考慮了簇對之間的互連性，而且也加入了近似性特征的考量。該算法不受用戶提供的靜態(tài)模型的影響，它能夠自適應(yīng)內(nèi)部特征屬性，這些內(nèi)部特征屬性是合并簇之間的內(nèi)部特征屬性。為此，我們給出以下幾個定義：

定義2.1：Gk-k最近鄰圖，對于數(shù)據(jù)對象p，如果數(shù)據(jù)對象o是p的k個最相似對象之前，則p與o之間有一條邊，這樣最后形成Gk.

定義2.2：簇P和簇O的相對互連性用RI{P，O}表示，表示簇P和簇O之間的內(nèi)部互連性與每個簇的絕對互連性的相互聯(lián)系，即：

其中，EC{P，O}表示內(nèi)部互連性，簇P和簇O連接所用到的所有邊的權(quán)值之和，EC{P}表示絕對互連性，簇P劃分為兩個近似大小的子簇時，連接簇內(nèi)的各個數(shù)據(jù)對象的邊的權(quán)值之和。

定義2.3：簇P和簇O的相對近似性用RC{P，O}表示，表示該簇對之間的內(nèi)部近似度與每個簇的絕對近似度的相互聯(lián)系，即：

其中，TC{P，O}表示內(nèi)部近似度，簇P和簇O連接用到的所有邊平均權(quán)值，TC{P}表示絕對近似度，簇P劃分為兩個近似大小的簇時，連接簇內(nèi)的各個數(shù)據(jù)對象的邊的平均權(quán)值。|P|與|O|分別代表簇P和簇O中包含的所有數(shù)據(jù)對象的數(shù)目。

定義2.4：F（V）是度量合并的相似度函數(shù)，動態(tài)建模確定簇與簇之間的相似度，同時考慮相對緊密度和相對互連度來合并最相似的簇對，選擇合并是該函數(shù)值達(dá)到最大的簇對，即：

F（V）=RI（P，O）*RC（P，O）α（2.3）

其中，α是用戶指定的參數(shù)，若α>1，則Chameleon算法更重視相對緊密度；若α<1，則相對互連性更重要。所以α=1時，相對互連性和相對緊密度同樣重要。

2.2 NK_Means算法思想

定義2.5：噪聲衡量指標(biāo)V{S，H}，噪聲或者孤立點數(shù)據(jù)容易干擾聚類效果，因此加入噪聲衡量指標(biāo)來改進原始K_Means算法，即：

其中，n為樣本數(shù)據(jù)集，d為數(shù)據(jù)維數(shù)。

NK_Means算法具體流程如下：

（1）針對聚類后的數(shù)據(jù)集，計算每一個數(shù)據(jù)對象的噪聲衡量指標(biāo)。

（2）對每一個數(shù)據(jù)對象P，如果Sp>H，將P作為數(shù)據(jù)集的孤立點。

（3）刪除孤立點或者將孤立點導(dǎo)出到異常值列表中，獲得新的數(shù)據(jù)集X。

（4）從數(shù)據(jù)集X中隨機選取K個初始聚類中心C1，C2，…，Ck。

（5）依據(jù)初始聚類中心C1，C2，…，Ck對數(shù)據(jù)集進行劃分，劃分根據(jù)以下原則：若dij（xi，cj）

（7）如果對? i∈{i=1，2，…，k}，都有ci*=ci，那么算法結(jié)束，其中c1*，c2*，…，ck*表示最終形成的聚類，否則，另ci=ci*，返回到步驟（2）。設(shè)置一個迭代次數(shù)閥值，用來防止達(dá)不到終止條件時會出現(xiàn)無線循環(huán)。

（8）把聚類的結(jié)果輸出。

3 實驗驗證

BTS聚類是一種很高質(zhì)量的有效的聚類算法，接下來將通過以下幾個方面的對比進行驗證：一個是分別和一趟聚類NChameleon、一趟聚類NK_Means作對比，一個是改進前的兩階段聚類作對比。全面分析驗證BTS聚類算法的高質(zhì)量性以及有效性。所采用的測試數(shù)據(jù)集是UCI數(shù)據(jù)集中的Pen-Based Recognition of Handwritten Digits數(shù)據(jù)集，該數(shù)據(jù)集總共有10992條記錄，每條記錄有16個數(shù)字屬性。實驗將從簇個數(shù)的變化實現(xiàn)精度的比較，是由于需要進行實驗的聚類算法都需要手動指定K 值，BTS可以自動指定K值，BTS的實驗將會從動態(tài)指定K值和自動生成K值兩方面實驗來發(fā)現(xiàn)自動指定K值的聚類穩(wěn)定性以及高效性，對比實驗數(shù)據(jù)如圖2所示：

圖2 聚類算法效果對比

從圖2中可以發(fā)現(xiàn)，改進前的兩階段聚類比一趟聚類NChameleon與一趟聚類NK_Means有更好的聚類質(zhì)量，說明兩階段聚類可以在一定程度改進一趟聚類的聚類質(zhì)量，而BTS聚類的聚類質(zhì)量比兩階段聚類更好，說明結(jié)合NChameleon算法和NK_Means算法能夠彌補它們各自的不足以達(dá)到聚類質(zhì)量的提高。

4 結(jié)束語

本文分析了傳統(tǒng)的層次和劃分聚類算法的不足，并針對一些不足進行了改進，得出了基于NChameleon和NK_Means算法的BTS聚類算法，大大提高了聚類質(zhì)量。但聚類結(jié)果還是會存在異常數(shù)據(jù)點，如何對聚類數(shù)據(jù)集進行全面異常分析是我們下一步的研究目標(biāo)。

[1]王茜，劉書志. 基于密度的局部離群數(shù)據(jù)挖掘方法的改進[J]. 計算機應(yīng)用研究，2014（06）： 1693-1696+1701.

[2]湯俊，熊前興. 基于時間序列相似度的離群模式檢測模型[J]. 武漢大學(xué)學(xué)報（工學(xué)版），2006（03）：111-114.

[3]盧正鼎，王瓊. 基于相似度的離群模式發(fā)現(xiàn)模型[J]. 華中科技大學(xué)學(xué)報（自然科學(xué)版），2005（01）：22-24+27.