一種基于自適應(yīng)網(wǎng)格劃分和決策圖的聚類算法研究

蔡 莉，江 芳，許衛(wèi)霞，梁 宇

1(復(fù)旦大學(xué) 計(jì)算機(jī)科學(xué)技術(shù)學(xué)院，上海 200433) 2(云南大學(xué) 軟件學(xué)院，昆明 650091)E-mail：lcai@fudan.edu.cn

1 引 言

作為數(shù)據(jù)挖掘中的一類重要算法，聚類廣泛應(yīng)用于數(shù)據(jù)分析、圖像處理、市場(chǎng)研究、用戶劃分、Web文檔分類等.目前，聚類算法大致可以劃分為四種類型.第一種是以K-means、K-medoids等算法為代表的基于劃分的聚類算法[1，2].第二種是以CURE和BIRCH[3]等算法為代表的基于層次的聚類算法，它們通過(guò)計(jì)算不同類別數(shù)據(jù)點(diǎn)間的相似度來(lái)創(chuàng)建一棵有層次的嵌套聚類樹(shù).第三種則是以DBSCAN、OPTICS等算法為代表的基于密度的聚類算法[4，5].這類算法核心思想是將簇定義為密度相連的點(diǎn)的最大集合，能夠把在一定范圍內(nèi)，具有足夠高密度的區(qū)域劃分為簇.第四種是以Clique算法[6]為代表的基于網(wǎng)格的聚類算法.這類算法對(duì)數(shù)據(jù)輸入順序不敏感，無(wú)需假設(shè)任何規(guī)范的數(shù)據(jù)分布，當(dāng)數(shù)據(jù)維數(shù)增加時(shí)具有良好的可伸縮性[7，8].

每一類算法都有各自的適用場(chǎng)合和優(yōu)缺點(diǎn).基于劃分的聚類算法實(shí)現(xiàn)簡(jiǎn)單，應(yīng)用非常廣泛，但是，其最大缺陷是需要提前確定簇的數(shù)量.基于層次的聚類算法的缺陷在于當(dāng)數(shù)據(jù)集較大時(shí)，樹(shù)形圖的規(guī)模會(huì)變得非常巨大，效率較為低下.基于密度的聚類算法不僅可以發(fā)現(xiàn)任意形狀的類，而且可以對(duì)噪聲數(shù)據(jù)和孤立數(shù)據(jù)進(jìn)行過(guò)濾.但是，此類算法的最大問(wèn)題是如何選擇有效的參數(shù).像大多數(shù)基于密度的聚類算法一樣，基于網(wǎng)格的聚類非常依賴于密度閾值的選擇.閾值太高會(huì)導(dǎo)致簇丟失，閾值太低又會(huì)使本應(yīng)該分開(kāi)的簇被合并在一起.2014年Alex Rodriguez和Alessandro Laio在Science上發(fā)表了一篇基于密度峰值的聚類算法(Clustering by fast search and find of density peaks，簡(jiǎn)稱為DPC算法)[9]，其思想是尋找被低密度區(qū)域分離的高密度區(qū)域.DPC算法通過(guò)決策圖尋找具有較高的密度ρ且與更高密度點(diǎn)具有較大的距離δ的聚類中心.計(jì)算局部密度ρ需要用到截?cái)嗑嚯x(Cut-off distance，簡(jiǎn)稱為dC).參數(shù)dC是指一個(gè)距離值，它從一個(gè)有序距離序列中選出.例如，對(duì)數(shù)據(jù)集中任意兩點(diǎn)計(jì)算距離值并得到一個(gè)距離矩陣，然后升序排序.由用戶自己設(shè)置一個(gè)參數(shù)百分比，dC為該排列的參數(shù)百分比.針對(duì)距離閾值人工選取問(wèn)題，Wang等人[10]提出了一種利用原始數(shù)據(jù)集中數(shù)據(jù)場(chǎng)的潛在熵自動(dòng)提取閾值最優(yōu)值的新方法，其對(duì)比實(shí)驗(yàn)結(jié)果表明，與經(jīng)驗(yàn)閾值相比，具有數(shù)據(jù)場(chǎng)閾值的算法可以獲得更好的聚類結(jié)果，但該方法在大數(shù)據(jù)集上尚未驗(yàn)證.在處理海量數(shù)據(jù)集時(shí)，DPC算法的計(jì)算工作量非常龐大.Xie等人[11]提出了FKNN-DPC(簡(jiǎn)稱為FDPC)算法.對(duì)于任何獨(dú)立于dC的數(shù)據(jù)集，計(jì)算點(diǎn)i相對(duì)于其K近鄰的局部密度ρi，并使用兩種新的點(diǎn)分配策略將剩余的點(diǎn)分配給最可能的簇.FDPC算法比DPC算法的性能要好，但是，算法中的K值需要預(yù)先確定，這對(duì)于無(wú)監(jiān)督的聚類來(lái)說(shuō)比較困難.何熊熊等人提出了一種基于密度和網(wǎng)格的簇心可確定聚類算法，簡(jiǎn)稱為DGCCD算法[12].DGCCD算法采用網(wǎng)格化數(shù)據(jù)集來(lái)減少聚類過(guò)程中的計(jì)算復(fù)雜度，其劃分網(wǎng)格的依據(jù)是：網(wǎng)格對(duì)象集中網(wǎng)格對(duì)象數(shù)量NG在大于或等于數(shù)據(jù)集中數(shù)據(jù)量N的1/6的情況下最好.

使用網(wǎng)格劃分來(lái)減少聚類過(guò)程的計(jì)算量是一種較好的方法[13]，但是，傳統(tǒng)基于網(wǎng)格的聚類算法是采用固定網(wǎng)格的方法區(qū)分稠密區(qū)域和稀疏區(qū)域，一些稀疏區(qū)域會(huì)被刪減掉，導(dǎo)致原本屬于某個(gè)聚類簇的數(shù)據(jù)點(diǎn)被刪除，或者被分割到了相鄰的區(qū)間，破壞了聚類簇的完整性.為了解決相關(guān)算法存在的問(wèn)題，本文提出了一種基于自適應(yīng)網(wǎng)格劃分的聚類算法，稱之為AGPCA(Adaptive Grid Partition Clustering Algorithm)算法.該算法結(jié)合網(wǎng)格劃分和距離判斷的優(yōu)點(diǎn)，適用于大規(guī)模數(shù)據(jù)的聚類計(jì)算.

2 AGPCA聚類算法原理

2.1 相對(duì)熵

1948年Shannon將熵的概念引入信息論，它是用來(lái)度量信息價(jià)值高低的一種方法[14].熵可以表示為：

(1)

其中，x為隨機(jī)變量，S(x)為x可以取值的集合，p(x)為x的概率函數(shù).

相對(duì)熵[15]是從熵衍生出來(lái)的概念，可以反映數(shù)據(jù)點(diǎn)分布趨近于均勻分布的程度.當(dāng)數(shù)據(jù)分布越趨于均勻，相對(duì)熵值越大；當(dāng)數(shù)據(jù)分布越趨于集中，相對(duì)熵值越小.本文利用相對(duì)熵來(lái)區(qū)分子空間中的密集數(shù)據(jù)區(qū)域和稀疏數(shù)據(jù)區(qū)域，做到自適應(yīng)網(wǎng)格劃分[16].

定義1.第i維上直方圖中的單個(gè)直方格(bin)的相對(duì)熵可以用如下公式表示：

(2)

其中，xij為第i維上第j個(gè)直方圖格，d(xij)為直方圖格里的數(shù)據(jù)數(shù)量占整個(gè)數(shù)據(jù)空間數(shù)據(jù)集的比例，Ti為第i維上的直方圖格的數(shù)量.

定義2.第i維上直方圖的相對(duì)熵可以用如下公式表示：

(3)

其中，Xi為第i維上直方圖格的集合.

本文利用相對(duì)熵自適應(yīng)劃分網(wǎng)格的過(guò)程如下：

Step1.根據(jù)輸入的網(wǎng)格步長(zhǎng)ε參數(shù)等長(zhǎng)劃分Di，構(gòu)造第i維的直方圖；

Step2.計(jì)算第i維的每一個(gè)直方圖格Hb的相對(duì)熵；

Step3.計(jì)算第i維直方圖的相對(duì)熵以及相對(duì)熵閾值θh；

Step4.順序掃描第i維的所有Hb，若Hb的相對(duì)熵≥θh，則繼續(xù)掃描后一個(gè)Hb，直至遇到Hb<θh，則將之前掃描的Hb進(jìn)行合并，并繼續(xù)掃描至結(jié)束；

Step5.重復(fù)Step 1-Step 4，直到多維網(wǎng)格掃描完成.

2.2 決策圖與簇心網(wǎng)格

為了加快查找速度，本文在這一處理階段使用了Kd-Tree[17]來(lái)創(chuàng)建索引.Kd-Tree是K-dimension Tree的縮寫(xiě)，是一種平衡二叉樹(shù)的具體實(shí)現(xiàn).它可以根據(jù)數(shù)據(jù)點(diǎn)的維度，在k維數(shù)據(jù)空間(如三維(x，y，z))中劃分出對(duì)應(yīng)的索引結(jié)構(gòu).Kd-Tree主要應(yīng)用于多維空間關(guān)鍵數(shù)據(jù)的搜索，如最近鄰搜索等[18].確定簇心網(wǎng)格的過(guò)程為：

Step1.根據(jù)相對(duì)熵自適應(yīng)地將數(shù)據(jù)集空間中的每一維k劃分為互不重疊的n個(gè)網(wǎng)格；

Step2.掃描所有網(wǎng)格，刪除數(shù)據(jù)點(diǎn)為0的網(wǎng)格，形成新的非空網(wǎng)格并記為Np；

Step3.確定網(wǎng)格的對(duì)象集Np和網(wǎng)格對(duì)象數(shù)NG；

Step4.確定每一個(gè)網(wǎng)格對(duì)象的密度參數(shù)ρi和距離值δi.

參數(shù)ρi和δi的定義分別如下：

定義3.每一個(gè)網(wǎng)格celli中的密度為ρi.ρi=Count(Celli).

定義4.以網(wǎng)格對(duì)象celli到更高密度網(wǎng)格對(duì)象cellj的最近距離作為網(wǎng)格對(duì)象的距離值，記為δi，公式如下：

(4)

其中，dij為網(wǎng)格對(duì)象celli中心位置到網(wǎng)格對(duì)象cellj中心位置之間的歐氏距離.

假設(shè)網(wǎng)格集合中密度最高的網(wǎng)格對(duì)象為ex，其距離值δex=max(δi)，j為除ex以外的所有網(wǎng)格對(duì)象.位于簇心位置的網(wǎng)格對(duì)象會(huì)同時(shí)具有較高的密度ρ和較大距離值δ，如圖1所示.可以看出：編號(hào)為5和9的網(wǎng)格對(duì)象具有較高的密度ρ和較大的距離δ，將它們作為簇心網(wǎng)格對(duì)象.

圖1 決策圖(密度與距離的分布圖)Fig.1 Decision diagrams(den-sity and distance distribution)

2.3 聚類過(guò)程

在簇心網(wǎng)格對(duì)象確定之后，采用基于密度的劃分方式來(lái)完成聚類，具體步驟為：

Step1.給每個(gè)簇心網(wǎng)格celli分配不同類別Ci；

Step2.遍歷簇心網(wǎng)格的相鄰網(wǎng)格，若相鄰網(wǎng)格密度值大于2，則給相鄰網(wǎng)格分配簇心類標(biāo)；

Step3.將剩下未分配的網(wǎng)格進(jìn)行鄰接網(wǎng)格遍歷，若鄰接網(wǎng)格有類標(biāo)，則將該類標(biāo)分配給該網(wǎng)格；

Step4.將剩下仍未分配的網(wǎng)格，利用Kd-Tree索引，找到離它最近的K個(gè)網(wǎng)格(K為數(shù)據(jù)集大小的3‰)，將最近有類標(biāo)的點(diǎn)且距離小于K近鄰點(diǎn)的平均距離的點(diǎn)的類標(biāo)賦予該網(wǎng)格，反之，該網(wǎng)格標(biāo)記為噪聲點(diǎn)網(wǎng)格，類標(biāo)賦值0.

Step5.重復(fù)Step 4，直到所有網(wǎng)格已經(jīng)分配類標(biāo)，則整個(gè)聚類工作結(jié)束.

3 AGPCA算法描述

本小節(jié)介紹AGPCA算法的實(shí)現(xiàn)過(guò)程，為了更好地描述本算法，對(duì)算法中涉及到的變量進(jìn)行說(shuō)明，如表1所示.

表1 AGPCA算法中使用的變量Table 1 Notations for AGPCA algorithm

AGPCA算法的偽代碼描述如下：

Input：有k維的數(shù)據(jù)集D，ε

Output：聚類結(jié)果C

/* Step 1：劃分網(wǎng)格*/

1.for eachi，i=(1，…，k)

2.Hbi= SplitGrid(Di，ε) /*根據(jù)輸入的參數(shù)等長(zhǎng)劃分Di，構(gòu)造第i維的直方圖*/

3.hr(xij) = Compute_entropy(xi) /* 計(jì)算第i維的每一個(gè)直方圖格的相對(duì)熵hr(xij) */

4.θh=CalThreshold()/*計(jì)算第i維相對(duì)熵閾值θh*/

5. MergeGrid()/*將熵值大于閾值的網(wǎng)格進(jìn)行合并 */

6.end for

7.GridQueue=Get_grid()/*得到多維自適應(yīng)劃分網(wǎng)格*/

/*Step 2：確定簇心網(wǎng)格*/

8.for eachCelliinGridQueue

9.Np=DelEmptyGrid[Celli] /*刪除空網(wǎng)格Celli*/

10.end for

11.KD=CreateKd(GridQueue) /*非空網(wǎng)格建立kd樹(shù)*/

12.gc=Determine_center(Np) /* 確定簇心網(wǎng)格gc，并遍歷簇心網(wǎng)格的鄰接網(wǎng)格*/

13.addgcinC

/* Step 3：確定聚類結(jié)果*/

14.Nearest_neighbor(gc)/*遍歷簇心網(wǎng)格的鄰接網(wǎng)格*/

15.NearestCluster(Np) /*遍歷未分配網(wǎng)格的鄰接網(wǎng)格*/

16.KNearestGrid(Np) /*遍歷未分配網(wǎng)格的K近鄰網(wǎng)格，返回滿足條件的K近鄰網(wǎng)格的類標(biāo)，反之返回0*/

17.returnC

4 實(shí)驗(yàn)及分析

本小節(jié)通過(guò)實(shí)驗(yàn)來(lái)驗(yàn)證AGPCA算法的有效性.

4.1 實(shí)驗(yàn)數(shù)據(jù)集

實(shí)驗(yàn)數(shù)據(jù)集包括5個(gè)基準(zhǔn)數(shù)據(jù)集和1個(gè)真實(shí)數(shù)據(jù)集.數(shù)據(jù)集Aggregation和Compound具有明顯的聚類簇大小不均衡的特征；數(shù)據(jù)集R15具有聚類簇?cái)?shù)量繁多并且高度重合的特征.數(shù)據(jù)集Flame和Spiral是經(jīng)典的流型數(shù)據(jù)集.出租車GPS數(shù)據(jù)集則是真實(shí)、無(wú)監(jiān)督的數(shù)據(jù)集.表2表示相關(guān)數(shù)據(jù)集的具體特征，圖2表示6個(gè)數(shù)據(jù)集的初始效果.

表2 實(shí)驗(yàn)數(shù)據(jù)集Table 2 Experimental data sets

圖2 數(shù)據(jù)集分布圖Fig.2 Distribution of six data sets

4.2 實(shí)驗(yàn)結(jié)果與評(píng)估

4.2.1 標(biāo)準(zhǔn)數(shù)據(jù)集對(duì)比實(shí)驗(yàn)

本小節(jié)先使用AGPCA算法對(duì)5個(gè)基準(zhǔn)數(shù)據(jù)集進(jìn)行聚類，并將AGPCA算法與DBSCAN算法、DPC算法、DGCCD和FKNN-DPC等四種算法進(jìn)行對(duì)比.聚類結(jié)果的有效性可以通過(guò)一些評(píng)價(jià)方法進(jìn)行測(cè)量，這些評(píng)價(jià)方法可以分為：外部評(píng)價(jià)、內(nèi)部評(píng)價(jià)和相對(duì)評(píng)價(jià)三種類型[19].常用的外部評(píng)價(jià)法指標(biāo)有F-measure、Rand指數(shù)、Purity和NMI(Normalized Mutual Information，標(biāo)準(zhǔn)互信息)等.內(nèi)部評(píng)價(jià)法對(duì)應(yīng)的評(píng)價(jià)指標(biāo)有CP(Compactness，緊密性)，SP(Separation，間隔性)[20].相對(duì)評(píng)價(jià)法的評(píng)價(jià)指標(biāo)包括DBI(Davies-Bouldin Index，戴維森堡丁指數(shù))和DVI(Dunn Validity Index，鄧恩指數(shù))等[21].

由于5個(gè)基準(zhǔn)數(shù)據(jù)集的分類已知，本文采用F-measure、Rand指數(shù)和Purity三種指標(biāo)來(lái)評(píng)價(jià)五種算法的聚類結(jié)果.

圖3 五種算法在標(biāo)準(zhǔn)數(shù)據(jù)集上的聚類評(píng)估結(jié)果Fig.3 Clustering assessment results of five algorithms on standard data sets

圖3(a)-圖3(c)顯示了5種算法在不同數(shù)據(jù)集上的RI、Purity、F-measure值對(duì)比結(jié)果.如圖3(a)-圖3(c)所示，在Aggregation、R15和Spiral這3個(gè)數(shù)據(jù)集上，F(xiàn)KNN-DPC算法的結(jié)果優(yōu)于其他算法.DPC算法的聚類效果易受截?cái)嗑嚯x的影響，因此在不同數(shù)據(jù)集上的聚類評(píng)估指標(biāo)會(huì)有一定差異.AGPCA算法在5個(gè)數(shù)據(jù)集上的平均RI、平均Purity、平均F-measure值都為最優(yōu)且達(dá)到96%以上.

4.2.2 真實(shí)數(shù)據(jù)集對(duì)比實(shí)驗(yàn)

本文也采用真實(shí)數(shù)據(jù)集對(duì)五種算法進(jìn)行實(shí)驗(yàn)對(duì)比，表3和表4分別統(tǒng)計(jì)了兩個(gè)不同日期(工作日和休息日)在四個(gè)不同時(shí)段下的聚類結(jié)果.

表3 GPS數(shù)據(jù)聚類結(jié)果統(tǒng)計(jì)Table 3 Number of clusters for GPS trajectory data on Monday and Sunday

本文以周一的09：00-11：00時(shí)段為例，對(duì)5種不同算法的聚類結(jié)果進(jìn)行分析，其中圖3(a)-圖3(e)分別展示5種不同算法在該時(shí)段的聚類結(jié)果.圖2(f)顯示了GPS的原始數(shù)據(jù)分布圖，可知所有軌跡點(diǎn)分布緊密，無(wú)法直接識(shí)別出聚類的個(gè)數(shù).圖4(a)-圖4(b)分別顯示了AGPCA、DBSCAN的聚類結(jié)果，可以發(fā)現(xiàn)這兩種算法的聚類簇特征相似，但在聚類簇分布位置不盡相同.AGPCA算法的聚類結(jié)果是以相對(duì)熵劃分網(wǎng)格，且先以聚類中心的鄰接網(wǎng)格進(jìn)行聚類，分配剩余點(diǎn)的策略是以K近鄰網(wǎng)格進(jìn)行聚類，所以聚類簇的分布較廣.DB-SCAN是以給定的半徑及最小點(diǎn)參數(shù)進(jìn)行聚類.圖4(c)顯示的是DPC算法的聚類結(jié)果，可知該聚類結(jié)果從左至右呈長(zhǎng)條矩形分布且聚類簇點(diǎn)數(shù)多，簇與簇之間的間距小.產(chǎn)生這種結(jié)果的原因在于DPC算法是人工選取截?cái)嗑嚯x參數(shù)，取不到最優(yōu)參數(shù)；同理在做噪聲點(diǎn)刪除時(shí)，也涉及到人工選取參數(shù)進(jìn)行處理，導(dǎo)致每一個(gè)聚類簇點(diǎn)數(shù)多.圖4(d)顯示的是DGCCD算法的聚類結(jié)果，由圖可知，該聚類結(jié)果呈網(wǎng)格狀分布，且連接緊密.產(chǎn)生這種結(jié)果的原因在于DGCCD算法通過(guò)迭代網(wǎng)格數(shù)至滿足某個(gè)條件最終確定網(wǎng)格總數(shù).DGCCD算法對(duì)聚類簇的區(qū)分度不好，會(huì)將原本不屬于同一個(gè)聚類簇的多個(gè)聚類結(jié)果合并在一起，無(wú)法得到準(zhǔn)確的結(jié)果.圖4(e)顯示的是FDPC算法的聚類結(jié)果，該聚類結(jié)果中存在一個(gè)特別大的聚類簇和若干個(gè)分散的小聚類簇.大聚類簇已經(jīng)涵蓋了二環(huán)區(qū)域內(nèi)所有GPS點(diǎn)，結(jié)果完全錯(cuò)誤.產(chǎn)生這一錯(cuò)誤的原因是該算法在算局部密度時(shí)，是根據(jù)某一點(diǎn)到其K近鄰點(diǎn)的距離計(jì)算所得，導(dǎo)致將多個(gè)相鄰近的聚類簇合并為一個(gè)超大聚類簇.

圖4 5種算法在真實(shí)數(shù)據(jù)集上的聚類對(duì)比結(jié)果Fig.4 Comparison of clustering results for five algorithms on GPS data sets

對(duì)于非監(jiān)督數(shù)據(jù)，本文使用DBI指數(shù)來(lái)評(píng)估聚類結(jié)果，表4顯示了7號(hào)和13號(hào)下各數(shù)據(jù)集聚類結(jié)果的戴維森堡丁指數(shù).從表4可以看出，在7號(hào)各時(shí)段下AGPCA獲得最小的DB指數(shù)，DPC算法、DGCCD算法的DB指數(shù)較高，原因在于在大數(shù)據(jù)集上人為選取參數(shù)較不準(zhǔn)確，剔除噪聲點(diǎn)較困難導(dǎo)致其聚類結(jié)果間距太小，且包含點(diǎn)數(shù)眾多.在13號(hào)各時(shí)段下DGCCD算法的平均DB指數(shù)最高，原因在于處理13：00-15：00/15：00-17：00時(shí)段下的文件時(shí)，分別聚出了40、31個(gè)類，遠(yuǎn)高于其他算法的聚類結(jié)果，且每個(gè)類間距離緊密.AGPCA算法在獲得數(shù)量更多的聚類簇的同時(shí)又能得到最小DB指數(shù)，具有很好的聚類效果.

4.2.3 運(yùn)行時(shí)間對(duì)比結(jié)果

表4 周一和周日聚類結(jié)果的DBI指數(shù)Table 4 DBI indices of clustering results on monday and sunday

最后，本文對(duì)比五種不同算法在不同數(shù)據(jù)量下的執(zhí)行時(shí)間，如圖5和圖6所示.9月7號(hào)在7：00-9：00、9：00-11：00、13：00-15：00和15：00-17：00四個(gè)時(shí)段的數(shù)據(jù)量分別為10561、17728、17219和16760.9月13號(hào)在對(duì)應(yīng)時(shí)段的數(shù)據(jù)量分別為11077、15501、18152和18113.各時(shí)段下數(shù)據(jù)量均超過(guò)1w條以上，其中19：00-21：00時(shí)段下的數(shù)據(jù)量最大，接近2萬(wàn)條.

圖5 周一各時(shí)段數(shù)據(jù)集運(yùn)行時(shí)間對(duì)比結(jié)果Fig.5 ComparisonofRunningtimeonmonday圖6 周日各時(shí)段數(shù)據(jù)集運(yùn)行時(shí)間對(duì)比結(jié)果Fig.6 ComparisonofRunningtimeonsunday

從圖5和圖6可以看出：AGPCA與DBSCAN的運(yùn)行時(shí)間比較接近，但AGPCA的運(yùn)行時(shí)間最短.DBSCAN算法耗時(shí)較短，原因在于其運(yùn)行參數(shù)是預(yù)先給定的.一旦待處理數(shù)據(jù)集的分布和規(guī)模發(fā)生改變，DBSCAN算法的兩個(gè)運(yùn)行參數(shù)Eps和Minpts要重新選取，這一過(guò)程非常耗費(fèi)時(shí)間.DGCCD算法耗費(fèi)時(shí)間長(zhǎng)，原因在于選定網(wǎng)格個(gè)數(shù)時(shí)，需計(jì)算當(dāng)前非空網(wǎng)格數(shù)是否滿足條件，若不滿足，則增加網(wǎng)格個(gè)數(shù)迭代計(jì)算，處理大數(shù)據(jù)集則運(yùn)行時(shí)間長(zhǎng).DPC算法耗時(shí)最長(zhǎng)的原因是該算法首先需要計(jì)算海量數(shù)據(jù)點(diǎn)之間的兩兩距離并形成距離矩陣，然后從中選取2%作為截?cái)嗑嚯x，該過(guò)程的時(shí)間復(fù)雜度為O(n2).FDPC算法的運(yùn)行時(shí)間稍低于DPC算法，其耗時(shí)原因是需要計(jì)算每個(gè)未分配點(diǎn)的K近鄰相似距離點(diǎn)以確定點(diǎn)的類標(biāo)，并依次遍歷下去.AGPCA算法在劃分網(wǎng)格時(shí)利用相對(duì)熵將一些網(wǎng)格進(jìn)行合并，從而減少了網(wǎng)格數(shù)；而且，在做網(wǎng)格聚類時(shí)利用KD樹(shù)以及鄰接網(wǎng)格思想分配網(wǎng)格，從而提高了查詢效率和運(yùn)算速度.

5 結(jié) 論

本文提出了一種基于自適應(yīng)網(wǎng)格劃分和決策圖的聚類算法.該算法首先對(duì)數(shù)據(jù)集進(jìn)行自適應(yīng)網(wǎng)格劃分，得到稠密和稀疏的網(wǎng)格，將無(wú)效網(wǎng)格進(jìn)行刪減；在聚類過(guò)程中，使用Kd-tree進(jìn)行索引查找，提高了查詢效率.該算法在處理大數(shù)據(jù)集時(shí)，可以很好地減少計(jì)算量以及降低運(yùn)行時(shí)長(zhǎng).通過(guò)對(duì)DBSCAN算法、DPC算法、DGCCD算法、FDPC算法以及AGPCA算法在標(biāo)準(zhǔn)數(shù)據(jù)集以及昆明市出租車GPS軌跡數(shù)據(jù)進(jìn)行實(shí)驗(yàn)對(duì)比，從結(jié)果分析可知AGPCA算法能夠挖掘出準(zhǔn)確的聚類結(jié)果，并且在處理大數(shù)據(jù)集時(shí)也具有較好的時(shí)間性能.相對(duì)熵閾值的選取在一定程度上影響著網(wǎng)格劃分結(jié)果，目前還是通過(guò)多次實(shí)驗(yàn)獲得最好的結(jié)果；此外，在處理不平衡數(shù)據(jù)集時(shí)，簇心選取時(shí)會(huì)丟失小簇聚類.因此，這兩個(gè)問(wèn)題將是下一步工作的研究重點(diǎn).