基于殘差和密度網(wǎng)格的簇心自確認(rèn)聚類算法

陳勝發(fā)，賈瑞玉

安徽大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，合肥230601

1 引言

聚類算法是數(shù)據(jù)挖掘中最經(jīng)典的算法之一，已經(jīng)得到了許多學(xué)者的研究。聚類技術(shù)在許多領(lǐng)域得到了廣泛的應(yīng)用。在商業(yè)領(lǐng)域，它可以用來分析顧客的行為，為商業(yè)營銷策略的制定提供重要的依據(jù)[1-2]。此外，在互聯(lián)網(wǎng)電子商務(wù)領(lǐng)域，它可以用來分析符合用戶瀏覽日志的相似客戶的特征，從而幫助互聯(lián)網(wǎng)商家提供更好的客戶服務(wù)[3]。

聚類是將樣本元素分為不同的簇，在同一簇中的元素都是具有較高的相似度，不同簇中的元素相似度低[4]。數(shù)十年來國內(nèi)外專家學(xué)者對(duì)聚類算法進(jìn)行了深入研究，已獲得了相當(dāng)好的成果。如基于劃分的聚類算法[5]有K-means[6]、K-medoids[7]等；基于密度的聚類算法有DBSCAN[8]等；基于層次的聚類算法有CURE[9]等；基于網(wǎng)格的聚類算法有STING[10]等。

文獻(xiàn)[11]結(jié)合密度峰值，提出了一種基于密度的Canopy算法，將改進(jìn)的Canopy算法作為K-means算法的預(yù)處理過程，從而提高了K-means的聚類質(zhì)量。文獻(xiàn)[12]利用網(wǎng)格對(duì)數(shù)據(jù)空間劃分并使用KL散度進(jìn)行相似性度量，解決了不確定數(shù)據(jù)聚類問題（存在于障礙空間），并很好提升了算法的聚類效果。CCDDG算法[13]以網(wǎng)格化數(shù)據(jù)集空間，用網(wǎng)格對(duì)象代替數(shù)據(jù)對(duì)象，大大地降低了計(jì)算復(fù)雜度，但是最終的初始聚類中心和聚類數(shù)目還需要人工來選取。SNIC_K-means算法[14]利用樣本點(diǎn)在數(shù)據(jù)集空間中的分布信息來確定數(shù)據(jù)集的聚類數(shù)目和初始聚類中心，但算法需要計(jì)算每個(gè)數(shù)據(jù)對(duì)象的密度值、距離值和殘差，計(jì)算復(fù)雜度非常大。

2014年6月，Laio等人在Science發(fā)表了快速搜索和發(fā)現(xiàn)密度峰值的聚類算法（Clustering by fast search and find of Density Peaks，DPC）[15]，該算法的思路是將具有局部較大密度且與其他密度更高的有較遠(yuǎn)距離的數(shù)據(jù)點(diǎn)視為聚類中心，通過快速搜索聚類中心，將每一個(gè)非聚類中心的數(shù)據(jù)點(diǎn)沿著密度遞增的最近鄰方向劃分到對(duì)應(yīng)的聚類中心中，實(shí)現(xiàn)數(shù)據(jù)劃分。該算法與傳統(tǒng)的聚類算法相比，具有較好的聚類效果，但存在以下的幾個(gè)問題：（1）樣本的密度取值依托于截?cái)嚅g隔dc；（2）需要計(jì)算所有樣本間的距離，計(jì)算復(fù)雜度大；（3）需要通過人工監(jiān)督的方式從決策圖中選取出簇心對(duì)象。

為了解決文獻(xiàn)[15]的三個(gè)問題，本文結(jié)合文獻(xiàn)[13]和文獻(xiàn)[14]的優(yōu)點(diǎn)，提出了基于殘差和密度網(wǎng)格的簇心自確認(rèn)聚類算法（Self-confirming Clustering algorithm based on Residual Error and Density Grid，REDGSC）。該算法首先將數(shù)據(jù)集空間網(wǎng)格化，刪除沒有任何信息的網(wǎng)格對(duì)象；然后計(jì)算每個(gè)網(wǎng)格對(duì)象的密度值ρ和距離值δ；接著通過殘差分析從計(jì)算得到的ρ和δ中決策出簇心網(wǎng)格對(duì)象；最后，根據(jù)一種密度距離的劃分方式來對(duì)劃分網(wǎng)格對(duì)象，再用與非邊緣點(diǎn)的距離和自變動(dòng)的閾值來處理網(wǎng)格邊緣點(diǎn)和噪聲點(diǎn)，完成數(shù)據(jù)集的聚類。

2 REDGSC算法介紹

2.1 密度網(wǎng)格思想介紹

將數(shù)據(jù)的每一維進(jìn)行等距離劃分，均勻劃分成相同的段數(shù)，記為fG；將數(shù)據(jù)集空間分割成若干個(gè)超矩形網(wǎng)格對(duì)象，刪除不含任何信息的網(wǎng)格對(duì)象，剩余的網(wǎng)格對(duì)象就是所需要的，記為G；網(wǎng)格對(duì)象的個(gè)數(shù)記為NG。經(jīng)過多次實(shí)驗(yàn)表明，當(dāng)網(wǎng)格對(duì)象數(shù)量NG大于或等于數(shù)據(jù)集中的數(shù)據(jù)對(duì)象個(gè)數(shù)n的1/8時(shí)，算法的聚類效果最佳。圖1為二維數(shù)據(jù)集的網(wǎng)格化結(jié)果。網(wǎng)格化具體步驟如下：

步驟1將含有n個(gè)數(shù)據(jù)對(duì)象的數(shù)據(jù)集空間中每一維劃分成相同段數(shù)，記為f（初值為2），形成網(wǎng)格。

步驟2刪除不含任何信息的網(wǎng)格對(duì)象，剩余的記為N。

步驟3如果N＜n/8，則讓f=f+1，然后返回步驟1。

步驟4最后確定網(wǎng)格對(duì)象集G，劃分段數(shù)為fG，網(wǎng)格對(duì)象數(shù)NG。

圖1 二維數(shù)據(jù)集的網(wǎng)格化

確定網(wǎng)格對(duì)象集后，接下來就是如何計(jì)算網(wǎng)格對(duì)象的密度值ρ和距離值δ，相關(guān)定義如下：

定義1（密度值）將網(wǎng)格對(duì)象i中的數(shù)據(jù)元素個(gè)數(shù)作為密度值，記為ρi。

定義2（網(wǎng)格對(duì)象距離）網(wǎng)格對(duì)象i和網(wǎng)格對(duì)象j之間距離為：

其中，xi和xj為網(wǎng)格對(duì)象i和網(wǎng)格對(duì)象j中的數(shù)據(jù)對(duì)象的平均值；xip(i=1,2,…,n;p=1,2,…,d)代表網(wǎng)格對(duì)象i的第p維屬性；d為數(shù)據(jù)的維數(shù)。

定義3（距離值）δi表示網(wǎng)格對(duì)象i到具有更高密度值的網(wǎng)格對(duì)象j的最近距離。如果網(wǎng)格對(duì)象i的密度值為最大值，δi定義為max(dij)；如果網(wǎng)格對(duì)象i的密度值不是最大值，δi被定義為min(dij)，具體定義如下：

2.2 決策圖介紹

在Rodriguez和Laio在Science期刊上提出的聚類中心在與具有更高密度值的數(shù)據(jù)對(duì)象之間具有較大的距離δ且具有較高的密度值ρ的假設(shè)下，REDGSC算法網(wǎng)格化數(shù)據(jù)集空間后，含有簇心的網(wǎng)格對(duì)象也是具有較高的密度值ρ和較大的距離值δ。通過定義1和定義3，計(jì)算出每個(gè)網(wǎng)格對(duì)象的密度值和距離值，構(gòu)造出網(wǎng)格對(duì)象的δ和ρ的決策圖，如圖2所示。

通過圖2，人工很容易認(rèn)為最偏離的兩個(gè)點(diǎn)就是含有簇心的網(wǎng)格對(duì)象。但是這樣人工選取的方式非常不智能化而且還比較繁瑣，所以本文引入了殘差分析的方法來自動(dòng)決策出含有簇心的網(wǎng)格對(duì)象。

2.3 殘差分析確認(rèn)簇心

圖2 ρ和δ的決策圖

從2.2節(jié)的決策圖中可以很容易地看出簇心所在的網(wǎng)格對(duì)象，但是這屬于人工選取，并且這也是文獻(xiàn)[15]的思想中的一個(gè)缺陷。為了能自動(dòng)從網(wǎng)格對(duì)象集中獲取較大的ρi和δi的網(wǎng)格對(duì)象，進(jìn)而引用統(tǒng)計(jì)學(xué)中的殘差分析和線性回歸，利用規(guī)范化殘差來自動(dòng)獲取含有簇心的網(wǎng)格對(duì)象。相關(guān)概念如下：

概念1研究變量間函數(shù)關(guān)系是回歸分析中的一種方法。設(shè)響應(yīng)變量為Y，以X1,X2,…,Xp表示預(yù)測變量，其中p是預(yù)測變量的個(gè)數(shù)，Y與X1,X2,…,Xp的關(guān)系可以用以下回歸模型來描述：

其中，ε為隨機(jī)誤差，是模型不能高精度擬合數(shù)據(jù)的緣由。函數(shù)f(X1,X2,…,Xp)描述了Y與X1,X2,…,Xp之間的關(guān)系。

概念2響應(yīng)變量Y的擬合值Y*是使用擬合函數(shù)獲得的值，其表述如下：

例如，假設(shè)用以下線性模型：

來擬合某二維數(shù)據(jù)集中變量xi和yi的關(guān)系，則響應(yīng)變量yi的擬合值如下所示：

概念3殘差是擬合值減去觀測值的相反數(shù)，殘差ei的定義如下：

其中，yi和分別是xi對(duì)應(yīng)的觀測值和擬合值。

在回歸分析中，測定值減去由回歸方程預(yù)測出來的值所得到的值，以δ0表示。殘差δ0遵從正態(tài)分布N(0,σ2)；(δ0)/標(biāo)準(zhǔn)化殘差，稱為規(guī)范化殘差，以δ*表示；δ*服從標(biāo)準(zhǔn)正態(tài)分布N(0,1)。若某一網(wǎng)格對(duì)象的規(guī)范化殘差的值在(-1,1)區(qū)間之外，則該網(wǎng)格對(duì)象一定是異常的，這個(gè)定論在統(tǒng)計(jì)學(xué)的書籍[16]中有介紹過。

從決策圖中獲取具有較大的ρi和δi的網(wǎng)格對(duì)象，就是在決策圖中找到異常點(diǎn)，因此找到合適的回歸模型是非常重要的，從而求出決策圖中每個(gè)網(wǎng)格對(duì)象的殘差，并將殘差進(jìn)行規(guī)范化，則規(guī)范化殘差的絕對(duì)值大于1的網(wǎng)格對(duì)象就是含有簇心的網(wǎng)格對(duì)象。

圖3是圖2中數(shù)據(jù)的走勢圖，從圖2中可以看出，幾乎所有網(wǎng)格對(duì)象對(duì)應(yīng)的點(diǎn)都靠近ρ軸和δ軸，并且這些點(diǎn)分布在一條反比例曲線周圍，因此本文使用函數(shù)δ=a0+a1×(1/ρ)來擬合ρ和δ的關(guān)系。通過圖3可以看出除了可以被確認(rèn)為含有簇心的網(wǎng)格對(duì)象外，大部分?jǐn)?shù)據(jù)點(diǎn)都集中在反比例曲線上。運(yùn)用殘差分析從決策圖中得到具有較大的ρi和δi的數(shù)據(jù)對(duì)象的步驟流程如下：

步驟1用函數(shù)δ=a0+a1×(1/ρ)來擬合決策圖中δ和ρ的函數(shù)關(guān)系。

步驟2令ρ*=1/ρ，可將步驟1中的擬合函數(shù)線性化為δ=a0+a1×ρ*。

步驟3根據(jù)步驟2中的擬合函數(shù)來擬合數(shù)據(jù)點(diǎn)，然后計(jì)算每個(gè)網(wǎng)格對(duì)象對(duì)應(yīng)的數(shù)據(jù)點(diǎn)的殘差ei。

步驟4將步驟3獲得的殘差進(jìn)行規(guī)范化。

步驟5通過比較計(jì)算得到規(guī)范化殘差的絕對(duì)值大于1的網(wǎng)格對(duì)象對(duì)應(yīng)的數(shù)據(jù)點(diǎn)，這些網(wǎng)格對(duì)象對(duì)應(yīng)的數(shù)據(jù)點(diǎn)就是含有簇心的網(wǎng)格對(duì)象。

圖3 決策圖的數(shù)據(jù)走勢圖

圖4 是圖2中數(shù)據(jù)點(diǎn)的規(guī)范化殘差圖，以ρ*為橫軸，標(biāo)準(zhǔn)殘差δ*為縱軸。在圖4中，在兩條虛線外有兩個(gè)數(shù)據(jù)點(diǎn)，也就是說這兩個(gè)網(wǎng)格對(duì)象就是含有簇心的網(wǎng)格對(duì)象。

圖4 決策圖的規(guī)范化殘差圖

至此，已經(jīng)較好地解決了自動(dòng)選取網(wǎng)格對(duì)象集中含有簇心的網(wǎng)格對(duì)象的問題。

2.4 聚類過程

在自動(dòng)選好簇心網(wǎng)格對(duì)象后，首先為每個(gè)簇心網(wǎng)格對(duì)象標(biāo)上不同編號(hào)，然后根據(jù)已經(jīng)計(jì)算出來的每個(gè)網(wǎng)格對(duì)象的密度值ρ，將剩余的網(wǎng)格對(duì)象的標(biāo)號(hào)跟隨距離最近且密度值更高的已經(jīng)標(biāo)號(hào)的網(wǎng)格對(duì)象，這樣就可以很快地完成網(wǎng)格對(duì)象集的聚類，網(wǎng)格對(duì)象集的聚類完成也就是整個(gè)數(shù)據(jù)集的聚類完成。

2.5 邊緣點(diǎn)和噪聲

2.5.1 邊緣點(diǎn)處理

對(duì)于邊緣點(diǎn)的處理，首先就是選取出邊緣處的網(wǎng)格對(duì)象；然后計(jì)算所有非邊緣數(shù)據(jù)對(duì)象到選取出來的邊緣網(wǎng)格對(duì)象中每個(gè)數(shù)據(jù)對(duì)象之間的距離；接著就是將這些邊緣網(wǎng)格對(duì)象中的數(shù)據(jù)對(duì)象標(biāo)上和它們距離最近的非邊緣數(shù)據(jù)對(duì)象一樣的編號(hào)，這樣就完成了邊緣點(diǎn)的處理。

2.5.2 噪聲處理

由于噪聲點(diǎn)一般都是離群點(diǎn)，網(wǎng)格化數(shù)據(jù)集后，噪聲點(diǎn)都是處于邊界網(wǎng)格對(duì)象內(nèi)，所以對(duì)于噪聲點(diǎn)的處理，這里是用自動(dòng)變換的閾值來代替人工設(shè)定的噪聲點(diǎn)閾值。首先就是找到簇與簇之間的邊界網(wǎng)格對(duì)象，然后將邊界網(wǎng)格對(duì)象中密度最大值作為閾值，記為ρb，只要是密度值低于ρb的網(wǎng)格對(duì)象，就視為噪聲點(diǎn)，將其刪除。將邊界網(wǎng)格對(duì)象中密度最大值作為閾值，這樣就能很好地去除大部分噪聲點(diǎn)，并省去人工設(shè)定閾值的麻煩，雖然這樣的設(shè)定有可能將一些有用的信息刪除，但是通過實(shí)驗(yàn)證明，聚類準(zhǔn)確度得到了很大的提高，這是因?yàn)樵肼朁c(diǎn)會(huì)對(duì)聚類精度產(chǎn)生很大的影響，在犧牲一些有用的信息的同時(shí)可以刪除大量的噪聲點(diǎn)，所以聚類準(zhǔn)確度得到很大的提高。

3 算法流程和仿真實(shí)驗(yàn)

3.1 算法流程

本文提出了一種基于殘差和密度網(wǎng)格的簇心自確認(rèn)聚類算法。首先網(wǎng)格化數(shù)據(jù)集空間，刪除沒有任何信息的網(wǎng)格對(duì)象；然后就是通過殘差分析自動(dòng)獲取含有簇心的網(wǎng)格對(duì)象；最后通過密度距離的劃分方式進(jìn)行聚類操作。

REDGSC算法的處理流程如下：

步驟1輸入數(shù)據(jù)集D={x1,x2,…,xn}。

步驟2根據(jù)2.1節(jié)中的網(wǎng)格化步驟來網(wǎng)格化數(shù)據(jù)集空間，得到網(wǎng)格對(duì)象集G={X1,X2,…,Xn}。

步驟3根據(jù)定義1和定義3求出G中每個(gè)網(wǎng)格對(duì)象的ρi和δi。

步驟4運(yùn)用線性函數(shù)δ=a0+a1×ρ*（其中ρ*=1/ρ去擬合ρi和δi的關(guān)系。

步驟5計(jì)算每個(gè)網(wǎng)格對(duì)象的殘差，并規(guī)范化所有殘差。

步驟6從規(guī)范化殘差中，通過計(jì)算選出殘差絕對(duì)值大于1的網(wǎng)格對(duì)象，這些被選出來的網(wǎng)格對(duì)象就是含有簇心的網(wǎng)格對(duì)象。

步驟7根據(jù)2.4節(jié)和2.5節(jié)，并以步驟6中獲得含有簇心的網(wǎng)格對(duì)象，對(duì)G中的網(wǎng)格對(duì)象進(jìn)行聚類。

步驟8輸出聚類結(jié)果。

詳細(xì)算法流程圖如圖5所示。

3.2 仿真實(shí)驗(yàn)與分析

3.2.1 性能對(duì)比

為了測試本文算法的聚類性能，實(shí)驗(yàn)采用7個(gè)不同分布的人工數(shù)據(jù)集AD1、AD2、AD3、AD4、AD5、AD6和一個(gè)UCI數(shù)據(jù)集Iris，7個(gè)數(shù)據(jù)集的參數(shù)描述如表1所示。本文算法使用的聚類準(zhǔn)確率R為正確分類的數(shù)據(jù)對(duì)象個(gè)數(shù)占總數(shù)據(jù)對(duì)象個(gè)數(shù)的百分比。實(shí)驗(yàn)中每個(gè)算法在每個(gè)數(shù)據(jù)集上都運(yùn)行10次，在這10次運(yùn)算中，獲取平均算法執(zhí)行時(shí)間Ta、平均聚類準(zhǔn)確度Ra、最高聚類準(zhǔn)確度Rmax和最低聚類準(zhǔn)確度Rmin，在這里對(duì)于算法執(zhí)行時(shí)間的計(jì)算，并沒有考慮CCDDG和DPC兩個(gè)算法的人工決策出聚類簇心的時(shí)間。

表1 7個(gè)數(shù)據(jù)集的具體描述

圖5 算法流程圖

AD1～AD6數(shù)據(jù)集的二維分布如圖6所示。AD1～AD6數(shù)據(jù)集網(wǎng)格化后網(wǎng)格對(duì)象對(duì)應(yīng)的規(guī)范化殘差的ρ*和δ*分布如圖7所示，Iris對(duì)應(yīng)的ρ*和δ*分布如圖8所示。

本文以CCDDG算法、DPC算法、SNIC_K-means算法和REDGSC算法，在給出的7個(gè)數(shù)據(jù)集上進(jìn)行對(duì)比實(shí)驗(yàn)，以測試本文算法的聚類性能，實(shí)驗(yàn)結(jié)果如表2所示。

3.2.2 算法執(zhí)行時(shí)間分析

由表2的實(shí)驗(yàn)結(jié)果可知，使用網(wǎng)格化數(shù)據(jù)集空間的REDGSC算法和CCDDG算法在7個(gè)數(shù)據(jù)集上的平均執(zhí)行時(shí)間都小于DPC算法和SNIC_K-means算法，其中當(dāng)數(shù)據(jù)量相對(duì)較大（達(dá)到2 000以上）的時(shí)候，執(zhí)行時(shí)間下降了30倍以上。對(duì)于REDGSC算法在執(zhí)行時(shí)間上大于CCDDG算法，這是因?yàn)楸疚乃惴ㄌ砑恿藲埐罘治鰜碜詣?dòng)確認(rèn)簇心和對(duì)于邊緣點(diǎn)和噪聲的處理，這兩個(gè)操作增加了本文算法的執(zhí)行時(shí)間。

圖6 6個(gè)數(shù)據(jù)集的二維分布圖

圖7 6個(gè)數(shù)據(jù)集的網(wǎng)格對(duì)象對(duì)應(yīng)的規(guī)范化殘差ρ*和δ*分布圖

圖8 Iris對(duì)應(yīng)的ρ*和δ*分布圖

表2 4種算法在7個(gè)數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果

3.2.3 算法復(fù)雜度分析

設(shè)聚類數(shù)據(jù)集是一個(gè)含有n個(gè)m維的數(shù)據(jù)集，首先算法對(duì)數(shù)據(jù)集進(jìn)行網(wǎng)格化并得到網(wǎng)格對(duì)象的密度值，這個(gè)過程的計(jì)算復(fù)雜度為O()；然后計(jì)算每個(gè)網(wǎng)格對(duì)象的距離需要的計(jì)算代價(jià)為O((N2-N)/2)，算法進(jìn)行一次距離密度的劃分完成聚類，其計(jì)算代價(jià)為O(N lg N+N/2)；接著就是邊緣點(diǎn)和噪聲處理的過程的計(jì)算代價(jià)為O(bn+aN)，其中b表示邊緣點(diǎn)的個(gè)數(shù)，a表示簇與簇之間的邊界網(wǎng)格對(duì)象個(gè)數(shù)；最后就是線性回歸和殘差分析的計(jì)算代價(jià)O(N2+N)。因此REDGSC算法的算法時(shí)間復(fù)雜度為O(+N lg N+3N2/2+N+bn)。

由表3可以分析得到：相比SNIC_K-means和DPC，REDGSC算法有著較低的時(shí)間復(fù)雜度，所以在執(zhí)行速度方面，REDGSC算法相比前兩個(gè)算法，有著較快的表現(xiàn)；而相比CCDDG算法，REDGSC算法有著較高的時(shí)間復(fù)雜度，這是因?yàn)榫€性回歸和殘差分析的過程中消耗了部分時(shí)間。但REDGSC算法的優(yōu)勢：（1）能夠自動(dòng)確定簇心而不是人工選?。唬?）確定含有簇心的網(wǎng)格對(duì)象后，利用一種密度距離的劃分方式進(jìn)行類簇的劃分，這就使得REDGSC算法對(duì)于任意形狀分布的數(shù)據(jù)集都有著較好的聚類效果。

表3 算法時(shí)間復(fù)雜度對(duì)比表

3.2.4 實(shí)驗(yàn)結(jié)果分析

綜上7個(gè)數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果，可以看出REDGSC算法在聚類準(zhǔn)確度和時(shí)間復(fù)雜度上都優(yōu)于SNIC_K-means算法，這是因?yàn)镽EDGSC算法網(wǎng)格化數(shù)據(jù)集，將網(wǎng)格對(duì)象作為聚類對(duì)象，大大地降低計(jì)算復(fù)雜度，而且還進(jìn)行了邊緣點(diǎn)和噪聲的處理，從而提高了聚類準(zhǔn)確度。相比于CCDDG算法，REDGSC算法解決了CCDDG算法需要人工選取聚類中心的弊端，并在聚類準(zhǔn)確度上高于CCDDG算法，這是因?yàn)镽EDGSC算法在網(wǎng)格化數(shù)據(jù)集后，在聚類的過程中進(jìn)行了邊緣點(diǎn)和噪聲的處理。

對(duì)于REDGSC算法在聚類準(zhǔn)確度上稍微低于DPC算法，是因?yàn)榫W(wǎng)格化數(shù)據(jù)集空間時(shí)，會(huì)有可能將不同簇的數(shù)據(jù)對(duì)象分到一個(gè)網(wǎng)格對(duì)象中，雖然REDGSC算法在后續(xù)操作中進(jìn)行了邊緣點(diǎn)和噪聲的處理，但是這樣的處理并不能處理所有的情況，所以在聚類準(zhǔn)確度上會(huì)有所降低，但是REDGSC算法很好地解決了DPC算法的三個(gè)缺陷（依賴截?cái)嗑嚯xdc、計(jì)算復(fù)雜度高和需要人工選取聚類中心）。

4 結(jié)語

本文提出了一種基于殘差和密度網(wǎng)格的簇心自確認(rèn)聚類算法。該算法將數(shù)據(jù)對(duì)象映射到網(wǎng)格上，用網(wǎng)格對(duì)象替換數(shù)據(jù)對(duì)象進(jìn)行聚類計(jì)算，這樣大大減少了聚類過程中的計(jì)算量，加快了算法的執(zhí)行速度。在算法聚類的過程中，采用一種密度距離的方式來劃分網(wǎng)格對(duì)象，這樣使得本文算法對(duì)于任意形狀分布的數(shù)據(jù)集都有著較好的聚類效果。而且在網(wǎng)格化數(shù)據(jù)集空間后的聚類過程中，對(duì)邊緣點(diǎn)和噪聲進(jìn)行了處理，很好地提高了聚類準(zhǔn)確性。通過實(shí)驗(yàn)表明本文算法在保持著聚類準(zhǔn)確度的前提下，很好地解決了DPC算法的三個(gè)缺陷。

由于本文算法在聚類準(zhǔn)確性上低于DPC算法，因此，未來的研究就是提高算法的聚類準(zhǔn)確性。