基于圖論的EMST聚類算法的適用性研究

魏 亮，陳曉耀，崔亞濤1，

(1.安徽中醫(yī)藥科學(xué)院 亳州中醫(yī)藥研究所，安徽 亳州 236800；2.亳州職業(yè)技術(shù)學(xué)院，安徽 亳州 236800；3.合肥工業(yè)大學(xué)，安徽 合肥 230009)

隨著傳統(tǒng)聚類分析方法在空間數(shù)據(jù)庫中的應(yīng)用，當(dāng)前可用于空間聚類的算法非常豐富。然而，現(xiàn)有的空間聚類算法往往都具有其局限性，如何對當(dāng)前的空間聚類算法進行歸納、整理，同時對其適用情況進行總結(jié)對于空間聚類分析的應(yīng)用具有重要的意義[1]。

本文將通過對比實驗，對EMST算法在空間數(shù)據(jù)庫中的性能及適用性進行分析和總結(jié)。

1 EMST算法的理論基礎(chǔ)

1.1 EMST算法的思想

EMST算法是基于圖論的一種算法，能夠探測不規(guī)則簇的界限。與傳統(tǒng)的聚類算法不同，最小生成樹聚類算法不假設(shè)球面形狀基本數(shù)據(jù)。

圖的最小生成樹是所有生成樹中邊的權(quán)值之和最小的生成樹。本文采用Prim算法構(gòu)造最小生成樹。如果從MST中刪除一些邊，就會產(chǎn)生一個連通分支的集合，則連通分支定義為簇。當(dāng)一個簇中點的數(shù)量小于某個值的時候，作為噪聲點處理。

1.2 EMST算法的描述

由于本文中的最小生成樹方法建立在完全圖的鄰接矩陣基礎(chǔ)上，因此，首先需構(gòu)建一個包含所有聚類的賦權(quán)完全圖G(V，E)，其中V為圖的原始輸入數(shù)據(jù)點集，E為圖中各頂點間的邊集，權(quán)值就是原始數(shù)據(jù)集各點間的距離，在得到各點間距離的鄰接矩陣后，便可利用Prim算法查找最小生成樹[2]。

基本思想是從源點S 開始構(gòu)造樹,然后每次在兩個點的集合間(已在生成樹上的點的集合Utree 與尚不在樹上的點的集合Vtree) 選擇一條最小代價邊，隨后將該邊加入樹中，并將相應(yīng)端點加入集合Tree 中，最終當(dāng)V中所有點均在集合Tree 中時，最小生成樹算法結(jié)束[3]。

下一步是刪除不一致邊，當(dāng)滿足 |m-l|〉qσ(m 代筆所有邊的平均值，l代表每條邊的值，q是固定值，σ是標(biāo)準(zhǔn)差)條件時，刪掉此邊。每刪掉一條邊，就標(biāo)記一個簇，如果簇的數(shù)量小于2，就作為噪聲點。

1.3 EMST算法的流程

EMST算法的流程：

(1) 加載數(shù)據(jù)圖層

(2) 求鄰接矩陣

(3) prim法求最小生成樹

(4) 刪掉最小生成樹中不一致邊

(5) 標(biāo)記簇

(6) 用不同的幾何符號和顏色顯示結(jié)果

2 EMST算法對比實驗

為了進一步說明EMST算法的性能及適用性，本實驗共設(shè)計了九個模擬實驗數(shù)據(jù)進行對比分析。本節(jié)設(shè)計的九個模擬實驗從以下四方面：(1)簇的空間形態(tài)(類球形和任意形狀)；(2)簇的空間密度差異；(3)簇的空間鄰近；(4)噪聲點(孤立點)的影響來比較EMST算法的優(yōu)缺點，同時對EMST算法參數(shù)的不同取值分別計算聚類結(jié)果，探討參數(shù)對其聚類結(jié)果的影響[4-10]。

對于EMST算法，刪除不一致邊的條件是|m-l|〉qσ，本實驗中對參數(shù)q取三次不同的值進行對比實驗。

2.1 模擬實驗一

第一個模擬實驗共有254個點，是密度分布比較均勻的類球形簇，圖1是EMST算法針對密度分布比較均勻的類球形簇的運行結(jié)果：

圖1 EMST算法的運行結(jié)果

從算法的聚類結(jié)果可以看出，參數(shù)取不同值時，三副圖聚類效果一樣，說明了對于此數(shù)據(jù)，參數(shù)對EMST算法影響很小，同時也驗證了此算法適用于密度分布均勻的類球形簇。

2.2 模擬實驗二

第二個模擬實驗共有263個點，在第一個模擬實驗數(shù)據(jù)的基礎(chǔ)上增加了若干噪聲點，圖2是EMST算法針對帶有噪聲點且密度分布比較均勻的類球形簇的運行結(jié)果：

圖2 EMST算法的運行結(jié)果

從算法的聚類結(jié)果可以看出，隨著參數(shù)的增大，每個類的成員有增加的趨勢。對于此數(shù)據(jù)，當(dāng)參數(shù)q =1.645時，聚類效果最好，q=2的時候比較好。說明EMST算法對于帶有噪聲點且密度分布比較均勻的類球形簇，EMST算法處理效果非常好。

2.3 模擬實驗三

第三個模擬實驗共有280個點，是密度分布比較均勻的任意形狀簇，圖3是EMST算法針對密度分布比較均勻的任意形狀簇的運行結(jié)果：

圖3 EMST算法的運行結(jié)果

從算法的聚類結(jié)果可以看出，對于密度分布比較均勻的任意形狀簇，EMST算法聚類效果很好，并且EMST算法受參數(shù)影響不大，三幅圖聚類結(jié)果都正確。

2.4 模擬實驗四

第四個模擬實驗共有293個點，在第三個模擬實驗數(shù)據(jù)基礎(chǔ)上增加了若干噪聲點，圖4是EMST算法針對帶有噪聲點且密度分布比較均勻的任意形狀簇的運行結(jié)果：

圖4 EMST算法的運行結(jié)果

從算法的聚類結(jié)果可以看出，當(dāng)參數(shù)q=1.645時聚類效果最佳，q=2時效果較好。說明對于帶有噪聲點且密度分布比較均勻的任意形狀簇，EMST算法處理效果非常好。

2.5 模擬實驗五

第五個模擬實驗共有245個點，是密度分布差異較大的任意形狀簇，圖5是EMST算法針對密度分布差異較大的任意形狀簇的運行結(jié)果：

圖5 EMST算法的運行結(jié)果

從算法的聚類結(jié)果可以看出，只有圖(2)的聚類效果最好，說明EMST算法中當(dāng)參數(shù)取值為2的時候能夠發(fā)現(xiàn)正確的簇，此法適用于密度分布差異較大的任意形狀簇。

2.6 模擬實驗六

第六個模擬實驗共有254個點，在第五個模擬實驗數(shù)據(jù)的基礎(chǔ)上增加了若干個噪聲點，圖6是EMST算法針對帶有噪聲點且密度分布差異較大的任意形狀簇的運行結(jié)果：

圖6 EMST算法的運行結(jié)果

從算法的聚類結(jié)果可以看出，只有圖(2)的聚類效果相對較好，說明EMST算法中當(dāng)參數(shù)取值為2的時候，能夠發(fā)現(xiàn)噪聲點，此法比較適用于帶有噪聲點且密度分布差異較大的任意形狀簇。

2.7 模擬實驗七

第七個模擬實驗共有241個點，是分布密度差異較大并有相鄰情況的任意形狀簇，圖7是EMST算法針對密度分布差異較大并有相鄰情況的任意形狀簇的運行結(jié)果：

圖7 EMST算法的運行結(jié)果

從算法的聚類結(jié)果可以看出，當(dāng)參數(shù)取的小時，一些分布有規(guī)律的點被當(dāng)做了噪聲點來處理，而參數(shù)稍大一點，一些分布規(guī)律明顯不同的簇被聚為一類。說明EMST算法對密度分布差異較大并有相鄰情況的任意形狀簇的處理效果差。

2.8 模擬實驗八

第八個模擬實驗共有258個點，在第七個模擬實驗數(shù)據(jù)的基礎(chǔ)上增加了若干個噪聲點，圖8是EMST算法針對帶有噪聲點且密度分布差異較大并有相鄰情況的任意形狀簇的運行結(jié)果：

圖8 EMST算法的運行結(jié)果

從算法的聚類結(jié)果可以看出，對帶有噪聲點且密度分布差異較大并有相鄰情況的任意形狀簇，EMST算法并不適用。

2.9 模擬實驗九

EMST算法適合于類球形簇，所以第九組模擬實驗是類球形兼有空間鄰近和密度分布不均勻的簇，繼續(xù)驗證其算法的適用性。圖9是EMST算法針密度分布差異較大并有相鄰情況的類球形簇的運行結(jié)果：

圖9 EMST算法的運行結(jié)果

從算法的聚類結(jié)果可以看出，對密度分布差異較大并有相鄰情況的類球形簇,EMST算法并不適用。

3 結(jié)論

對EMST算法進行了對比實驗測試，將參數(shù)q在不同取值時所對應(yīng)的聚類結(jié)果進行比較，并且進一步比較了四種干擾因素(簇的空間形態(tài)、簇的空間密度差異、簇的空間鄰近、噪聲點的影響)對聚類結(jié)果的影響，從而確定EMST算法在空間數(shù)據(jù)庫中的性能。

通過對EMST算法進行的實驗對比，總結(jié)出該算法的適用性：(1)空間簇的鄰接對其影響較大，對發(fā)現(xiàn)相鄰簇的效果不好，空間密度的差異對其結(jié)果具有一定的影響。(2)能發(fā)現(xiàn)任意形狀的簇，可以發(fā)現(xiàn)比較明顯的噪聲點。q比較小時，密度比較稀疏的簇被當(dāng)做噪聲點，q比較大時，不同的簇被歸為一類，q的取值為2左右的效果比較好。

EMST算法的該種特性，可以成為是否選用該算法進行空間聚類的決定指標(biāo)，也進一步增強了該算法的實際應(yīng)用價值。