龍超奇，蔣 瑜，謝 雨

（成都信息工程大學(xué)軟件工程學(xué)院，成都 610225）

0 引言

小波聚類（WaveCluster）算法［1］是一種基于網(wǎng)格的聚類算法。該算法從多維信號(hào)處理的角度出發(fā)，能夠有效地處理大數(shù)據(jù)集，發(fā)現(xiàn)任意形狀的簇，不容易受到噪聲的影響。這些優(yōu)點(diǎn)使得小波聚類算法被廣泛地應(yīng)用于數(shù)據(jù)處理。

目前，國(guó)內(nèi)外在小波聚類算法的應(yīng)用上取得了較大的進(jìn)展。文獻(xiàn)［2］將小波聚類應(yīng)用于數(shù)據(jù)約簡(jiǎn)，根據(jù)小波聚類結(jié)果抽選出不等數(shù)量的數(shù)據(jù)作為數(shù)據(jù)約簡(jiǎn)后的結(jié)果，能夠很好地描述大致的數(shù)據(jù)分布情況；文獻(xiàn)［3］將小波聚類應(yīng)用于本科招生生源分析，分析結(jié)果對(duì)高校管理招生工作起到了科學(xué)指導(dǎo)和輔助決策作用；文獻(xiàn)［4］將小波聚類應(yīng)用于入侵檢測(cè)系統(tǒng)，提高了入侵檢測(cè)的檢測(cè)率并降低了誤報(bào)率；文獻(xiàn)［5］從時(shí)空角度出發(fā)，將小波聚類算法應(yīng)用于交通事故分析中，具體地分析了造成交通事故的主要原因，對(duì)預(yù)防交通事故有參考價(jià)值；文獻(xiàn)［6］使用一維卷積神經(jīng)網(wǎng)絡(luò)和小波聚類分析方法檢測(cè)和診斷傳感器控制回路中的故障，提高了故障檢測(cè)的準(zhǔn)確性，并且在噪聲下也具有良好的診斷效果。

同其他基于網(wǎng)格聚類的算法相同，小波聚類也同樣會(huì)面臨可塑性面積單元問(wèn)題（Modifiable Area Unit Problem，MAUP），即依據(jù)不同網(wǎng)格劃分尺度會(huì)有不同的聚類分析結(jié)果。過(guò)于細(xì)密的網(wǎng)格會(huì)使得簇內(nèi)元素距離太遠(yuǎn)，造成同一簇元素被分割為多個(gè)簇的情況；而較為粗疏的網(wǎng)格會(huì)使簇間距離縮短，無(wú)法清晰地分割不同的簇。針對(duì)這個(gè)問(wèn)題，文獻(xiàn)［7］提出利用廣度優(yōu)先搜索（Breadth-First-Search，BFS）的方法判斷連通區(qū)域，以廣度優(yōu)先搜索鄰居聚類算法中控制類形狀的類門限參數(shù)λ去彌補(bǔ)相連定義類劃分不精確的問(wèn)題，改善小波聚類的聚類精度及速度；文獻(xiàn)［8］提出一種基于雙網(wǎng)格校正小波聚類算法，通過(guò)校正算法利用校正網(wǎng)格的聚類結(jié)果對(duì)原始網(wǎng)格的結(jié)果進(jìn)行校正，降低了網(wǎng)格劃分和網(wǎng)格密度閾值對(duì)聚類質(zhì)量的影響，為MAUP 提供了一種解決思路；文獻(xiàn)［9］使用并行小波算法，通過(guò)使用不同尺度級(jí)別的小波變換，在并行處理的條件下擴(kuò)展了聚類速度和規(guī)模，同時(shí)還克服了小波聚類中過(guò)大的空間復(fù)雜度的約束條件；文獻(xiàn)［10］聚焦于網(wǎng)格邊緣，運(yùn)用partition and judge the gridCij算法［11］尋找簇與簇的邊界，利用K-Means 算法劃分邊界，進(jìn)一步細(xì)化了邊界網(wǎng)格，在區(qū)分了簇與簇的邊緣的問(wèn)題上取得了較好的成果。

但上述算法均并沒(méi)有從聚類精度與網(wǎng)格劃分尺度的大小方向討論MAUP，本文通過(guò)研究劃分網(wǎng)格的粒度粗細(xì)對(duì)聚類精度影響，并提出了一種基于峰值網(wǎng)格的連通區(qū)域檢測(cè)算法。實(shí)驗(yàn)結(jié)果表明改進(jìn)后的算法能夠在較低的網(wǎng)格粒度下得到較好的聚類結(jié)果。

1 基礎(chǔ)概念

由于小波聚類算法是基于網(wǎng)格進(jìn)行的聚類算法，需要將原始數(shù)據(jù)映射到網(wǎng)格空間中。

定義1對(duì)d維特征空間P=A1×A2× …×Ad，將特征空間中每一維Ai(i={1，2，…，d})分割為數(shù)量為m的網(wǎng)格。即把原數(shù)據(jù)中的每一個(gè)維度以固定步長(zhǎng)分割為共計(jì)md個(gè)網(wǎng)格構(gòu)成新的網(wǎng)格空間Pgrid，m為網(wǎng)格劃分的尺度。

對(duì)于特征空間P中的任一元素{α1，α2，…，αn}，其在網(wǎng)格空間中的描述為{β1，β2，…，βn}，β的值為：

小波聚類算法采用離散小波變換，變換流程如圖1 所示。圖1 中：a[n]代表原始數(shù)據(jù)；g[n]和h[n]分別為小波基的低通濾波器和高通濾波器；↓2 表示對(duì)經(jīng)濾波器變換后的數(shù)據(jù)進(jìn)行下二元采樣［12］。網(wǎng)格空間Pgrid經(jīng)小波變換后取其低頻區(qū)域a1，g[n]構(gòu)成新的網(wǎng)格空間Pwave。a[n]到a1，g[n]的變換［1］如下：

由式（2）可知，網(wǎng)格空間進(jìn)行小波變換后的網(wǎng)格空間Pwave中總網(wǎng)格數(shù)為：

其中：L為小波基的濾波器長(zhǎng)度，即式（2）中g(shù)[n]的長(zhǎng)度。濾波器長(zhǎng)度L根據(jù)不同的小波基有不同的取值，本文選取的小波基為Daubechies 小波，其濾波器長(zhǎng)度為2N，N為小波基的系數(shù)。

圖1 一階離散小波變換流程Fig.1 First-order discrete wavelet transform process

小波聚類中，對(duì)于低密度網(wǎng)格的判別主要依靠密度閾值作為主要判別依據(jù)，并根據(jù)高密度網(wǎng)格建立連通區(qū)域。

定義2設(shè)網(wǎng)格密度閾值為t。對(duì)于任意的變換后網(wǎng)格，若網(wǎng)格的值大于t，則視為稠密網(wǎng)格；否則為稀疏網(wǎng)格。

定義3在空間Pwave中，若網(wǎng)格a可以通過(guò)若干個(gè)稠密網(wǎng)格到達(dá)網(wǎng)格b，則稱a與b互為可達(dá)網(wǎng)格。對(duì)于網(wǎng)格空間中某一區(qū)域的所有網(wǎng)格，若其中的網(wǎng)格均互為可達(dá)網(wǎng)格，則視該區(qū)域?yàn)檫B通區(qū)域。

算法1給出了傳統(tǒng)小波聚類算法的算法步驟［13］。

算法1 小波聚類算法。

輸入dt數(shù)據(jù)，m網(wǎng)格數(shù)目，t密度閾值，wavelet小波基。

輸出cluster_result聚類結(jié)果。

1）構(gòu)造大小為md的網(wǎng)格空間，將數(shù)據(jù)映射到網(wǎng)格空間中。

2）以wavelet作為小波基進(jìn)行小波變換，得到變換后的網(wǎng)格空間Pwave。

3）遍歷Pwave中的網(wǎng)格，檢查其中的連通區(qū)域，Pwave中網(wǎng)格密度低于t的記為稀疏網(wǎng)格。

4）標(biāo)記不同的連通區(qū)域?yàn)椴煌拇仡悺?/p>

5）建立數(shù)據(jù)與小波變換后網(wǎng)格空間的查找表，將Pwave中的簇類記錄到cluster_result中。

6）輸出cluster_result。

2 算法改進(jìn)

2.1 網(wǎng)格尺度分析

網(wǎng)格空間Pgrid經(jīng)離散小波變換產(chǎn)生的網(wǎng)格空間Pwave中以數(shù)值形式反映網(wǎng)格間關(guān)系。由式（2）可知，離散小波變換過(guò)程中，能量會(huì)向具有更高密度的網(wǎng)格匯聚，變換后網(wǎng)格的數(shù)值是由其身周共計(jì)x個(gè)網(wǎng)格共同決定的。其中x的值為：

由式（3）和式（4）可知，選擇的小波基的濾波器長(zhǎng)度L決定了網(wǎng)格空間中劃分尺度的最低大小。若濾波器長(zhǎng)度大于網(wǎng)格劃分尺度，則采樣頻率太低，小波變換的意義不明顯。在變換后的網(wǎng)格空間Pwave中，聚類中心總是屬于數(shù)值較大的網(wǎng)格。

圖2 展示了兩個(gè)簇間距離較小的簇類在小波變換之前的分布情況。

圖2 兩個(gè)不同的簇類Fig.2 Two different clusters

圖2 為兩個(gè)不同的簇在網(wǎng)格空間中的劃分情況（網(wǎng)格劃分為6×6 的網(wǎng)格），它們的邊緣區(qū)域位于x∈(0.125，0.25)，y∈(0.25，0.375) 中。圖3 展示了此網(wǎng)格空間經(jīng)由算法1（t=0，稀疏網(wǎng)格記為X）在網(wǎng)格劃分尺度分別為6 和10 時(shí)的聚類過(guò)程。

圖3 中：圖3（a）和（b）展示了不同網(wǎng)格密度下經(jīng)算法1 中的步驟2）和步驟4）處理的結(jié)果，圖3（c）和（d）分別為經(jīng)圖3（a）和（b）中描述的過(guò)程再經(jīng)由步驟5）映射之后的聚類結(jié)果，圖中簇2包含的數(shù)據(jù)點(diǎn)為小波聚類中所判定的離群點(diǎn)。

從圖3 中可以發(fā)現(xiàn)，較低網(wǎng)格密度下，雖然產(chǎn)生的小波變換矩陣較小且算法的消耗較低，但密集的變換矩陣導(dǎo)致只劃分出了一個(gè)有效的聚類；雖然圖3（d）中通過(guò)提高網(wǎng)格尺度產(chǎn)生了兩個(gè)有效聚類，但由于高網(wǎng)格尺度下的元素相對(duì)分散稀疏網(wǎng)格增多，從而產(chǎn)生了較多的離群點(diǎn)，導(dǎo)致算法只能大致地劃分?jǐn)?shù)據(jù)中不同的簇類，并且較大的網(wǎng)格劃分尺度也會(huì)增加算法的時(shí)間及空間消耗。

對(duì)比圖2及圖3（a）和（b）可知，小波變換后的網(wǎng)格數(shù)值反映了原數(shù)據(jù)中高密度的區(qū)域和低密度區(qū)域的分布。在高密度的區(qū)域內(nèi)其網(wǎng)格數(shù)值較大，而低密度區(qū)域和邊緣區(qū)域的網(wǎng)格數(shù)值往往遠(yuǎn)小于高密度區(qū)域。然而從圖3 中可以發(fā)現(xiàn)，小波聚類算法對(duì)經(jīng)小波變換后的網(wǎng)格數(shù)值并沒(méi)有很好地運(yùn)用起來(lái)，僅通過(guò)密度閾值對(duì)其進(jìn)行了分割處理。

基于上述情況，在原小波聚類連通檢測(cè)方法的基礎(chǔ)上，本文提出了使用高密度網(wǎng)格建立連通區(qū)域的方法，以改善較低網(wǎng)格密度下小波聚類算法的聚類效果。

圖3 不同網(wǎng)格劃分尺度的聚類過(guò)程Fig.3 Clustering processes of different grid division scales

2.2 基于峰值網(wǎng)格的連通區(qū)域檢測(cè)

定義4對(duì)小波變換后的網(wǎng)格空間Pwave中任意網(wǎng)格Cw，若Cw中值大于周圍x個(gè)數(shù)據(jù)點(diǎn)，則視Cw為峰值網(wǎng)格，Cw及其周圍x個(gè)網(wǎng)格相連所構(gòu)成的區(qū)域稱為峰值連通區(qū)域。

如果有若干個(gè)峰值連通區(qū)域重合，則視整個(gè)連通區(qū)域?yàn)槠渲凶畲蟮姆逯稻W(wǎng)格形成的極大峰值連通區(qū)域。

經(jīng)小波變換的網(wǎng)格空間Pwave中可以獲得若干個(gè)峰值網(wǎng)格，在判斷峰值連通區(qū)域時(shí)可以使用廣度優(yōu)先搜索算法檢測(cè)連通區(qū)域并處理連通區(qū)域的邊緣網(wǎng)格。

若某網(wǎng)格Ca處于Cw所屬極大峰值連通區(qū)域的邊緣并且其鄰近非該連通區(qū)域網(wǎng)格Cb滿足如下關(guān)系，則將Cb加入該極大峰值連通區(qū)域中。

其中：θ為極大峰值連通區(qū)域波動(dòng)系數(shù)，θ∈(0，1)，它決定了該連通區(qū)域的最大擴(kuò)散程度。

因此，利用峰值網(wǎng)格建立連通區(qū)域的算法如算法2所示。

算法2 峰值網(wǎng)格連通檢測(cè)算法。

輸入dt數(shù)據(jù)，m網(wǎng)格數(shù)目，wavelet小波基，θ波動(dòng)系數(shù)。

輸出cluster_result聚類結(jié)果。

1）同算法1 中1）、2）兩步，得到經(jīng)小波變換后的網(wǎng)格空間Pwave。

2）對(duì)小波變換后的網(wǎng)格數(shù)據(jù)快速排序。

3）從下標(biāo)0開始選取Pwave中未被標(biāo)記的網(wǎng)格并入隊(duì)。

4）隊(duì)列隊(duì)頭元素出隊(duì)并標(biāo)記其為新的簇類。

5）通過(guò)廣度優(yōu)先搜索遍歷與該出隊(duì)元素相鄰的所有網(wǎng)格，若其中某一網(wǎng)格的值滿足式（5），將該網(wǎng)格入隊(duì)并標(biāo)記該網(wǎng)格屬于當(dāng)前極大峰值區(qū)域?qū)?yīng)的簇。

6）重復(fù)步驟4）直到隊(duì)列為空。

7）重復(fù)步驟3）直到Pwave中所有網(wǎng)格均被標(biāo)記。

8）建立原數(shù)據(jù)與小波變換后數(shù)據(jù)之間的查找表，將Pwave中的簇類記錄到cluster_result中。

9）輸出cluster_result。

對(duì)圖2 中的數(shù)據(jù)使用算法2，可以在較低網(wǎng)格劃分尺度（m=6）下得到較好的聚類結(jié)果，如圖4所示。

圖4 算法2聚類結(jié)果Fig.4 Clustering results by algorithm 2

相對(duì)于算法1，在同樣低網(wǎng)格尺度下，算法2 利用高密度區(qū)域的網(wǎng)格，能夠更快地根據(jù)聚類中心尋找連通區(qū)域，同時(shí)還能分割處理較低網(wǎng)格劃分尺度下不同的簇類，所取得的聚類結(jié)果更好。

2.3 時(shí)間復(fù)雜度分析

設(shè)小波聚類的網(wǎng)格空間為k=md，在算法中，讀取數(shù)據(jù)集并映射到特征空間其時(shí)間復(fù)雜度為O（n），小波變換的時(shí)間復(fù)雜度最多為在劃分合理的情況下，小波變換的網(wǎng)格空間k?n，則小波變換的時(shí)間復(fù)雜度應(yīng)小于O（n）。與傳統(tǒng)小波聚類算法對(duì)比，本文算法對(duì)網(wǎng)格進(jìn)行排序并使用廣度優(yōu)先搜索區(qū)分簇類的時(shí)間復(fù)雜度為O（k2），大于傳統(tǒng)小波聚類算法O（k），建立查找表的時(shí)間復(fù)雜度為O（k）。則總計(jì)時(shí)間復(fù)雜度為：

在n?k的情況下，本文算法的時(shí)間復(fù)雜度量級(jí)為O（n），與傳統(tǒng)小波聚類算法的時(shí)間復(fù)雜度量級(jí)相同。雖然本文算法在計(jì)算連通區(qū)域時(shí)的時(shí)間復(fù)雜度大于原小波聚類算法，但本文算法能以更低的網(wǎng)格劃分尺度進(jìn)行聚類，所以時(shí)間性能上略優(yōu)于傳統(tǒng)小波聚類算法。

相較于算法1 中以連通區(qū)域劃分簇的方式，以網(wǎng)格峰值為序的連通檢測(cè)機(jī)制能夠在低精度網(wǎng)格下有效地區(qū)分網(wǎng)格空間Pwave中的聚類邊緣。

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

3.1 實(shí)驗(yàn)使用的數(shù)據(jù)集及參數(shù)

本文使用了人工數(shù)據(jù)集和UCI數(shù)據(jù)集分析本文算法相對(duì)于傳統(tǒng)小波聚類算法以及現(xiàn)有的聚類算法的改進(jìn)程度。其中，人工數(shù)據(jù)集主要用于測(cè)試本文算法在不同形狀的數(shù)據(jù)集以及網(wǎng)格尺度方面的優(yōu)化程度，UCI 數(shù)據(jù)集用于考察本文算法相對(duì)于其他聚類算法的優(yōu)勢(shì)和劣勢(shì)。本文實(shí)驗(yàn)基于Windows10操作系統(tǒng)，使用的編譯語(yǔ)言為Python 3.6.5。

使用的數(shù)據(jù)集如表1～2 所示，DS 系列數(shù)據(jù)集是由scikitlearn 庫(kù)生成的凸數(shù)據(jù)集，對(duì)于數(shù)據(jù)集中的每個(gè)簇類，設(shè)定其簇間距離總是大于簇內(nèi)距離，該數(shù)據(jù)集用于測(cè)試本文算法對(duì)于傳統(tǒng)小波聚類算法在網(wǎng)格劃分尺度的優(yōu)化程度；sym、Aggregation、Zigzag和Ring數(shù)據(jù)集為具有特定形狀的人工數(shù)據(jù)集：Zigzag 和Ring 是使用Matlab 生成的之字形及環(huán)形數(shù)據(jù)集，sym 和Aggregation 數(shù)據(jù)集為包含不同形狀的具有不等的簇間距離的綜合數(shù)據(jù)集，這四種數(shù)據(jù)集主要用于測(cè)試算法對(duì)簇間距離不等的特定形狀數(shù)據(jù)聚類的效果。為方便對(duì)比，所有小波聚類算法均使用Daubechies小波（系數(shù)為2）。

表1 人工數(shù)據(jù)集Tab.1 Synthetic datasets

表2 UCI數(shù)據(jù)集Tab.2 UCI datasets

本文實(shí)驗(yàn)采用外部指標(biāo)歸一化互信息（Normalized Mutual Information，NMI）和內(nèi)部指標(biāo)CH（Calinski-Harabaz score）作為聚類效果評(píng)估參數(shù)。

NMI 常用在聚類中度量?jī)蓚€(gè)聚類結(jié)果的相近程度，是重要的外部衡量指標(biāo)，可以比較客觀地評(píng)價(jià)出當(dāng)前簇類劃分與標(biāo)準(zhǔn)劃分之間相比的準(zhǔn)確度。NMI的值域是0 到1，越高代表劃分得越準(zhǔn)。

CH 指標(biāo)通過(guò)計(jì)算類中各點(diǎn)與類中心的距離平方和來(lái)度量類內(nèi)的緊密程度，通過(guò)計(jì)算各類中心點(diǎn)距離平方和來(lái)度量數(shù)據(jù)集的分離度，CH 指標(biāo)由分離度與緊密度的比值得到。CH 指標(biāo)越大代表著類中元素越緊密，類與類之間越分散，且CH指標(biāo)只受到數(shù)據(jù)自身分布的影響，有利于分析不同聚類簇?cái)?shù)下的聚類效果。

不同的網(wǎng)格密度會(huì)產(chǎn)生不同的聚類結(jié)果，由第2 章可知，網(wǎng)格劃分越緊密，網(wǎng)格空間中存有數(shù)據(jù)的網(wǎng)格越少。為了評(píng)價(jià)數(shù)據(jù)進(jìn)網(wǎng)格劃分后的密集程度，本文使用空間密度q表示了經(jīng)過(guò)網(wǎng)格排列后數(shù)據(jù)的緊密程度，公式如下：

其中：Ngrid為數(shù)據(jù)映射到網(wǎng)格空間Pgrid中的非空網(wǎng)格個(gè)數(shù)；N為原始數(shù)據(jù)樣本個(gè)數(shù)。

由網(wǎng)格劃分的概念可知，對(duì)于任意的聚類數(shù)據(jù)集，其網(wǎng)格劃分尺度m及密度q之間的大致關(guān)系如圖5所示。

在網(wǎng)格空間中，空間密度q與網(wǎng)格劃分尺度m呈正相關(guān)。隨著網(wǎng)格劃分尺度m的增長(zhǎng)，空間密度q的遞增速度會(huì)隨著聚類分布逐步改變。當(dāng)q的增長(zhǎng)速度放緩時(shí)，則說(shuō)明數(shù)據(jù)中的聚類程度通過(guò)網(wǎng)格空間已經(jīng)難以劃分，此時(shí)再增大網(wǎng)格劃分尺度對(duì)于改善聚類的效果甚微。

基于以上分析，由于小波聚類算法時(shí)間密度與網(wǎng)格劃分尺度關(guān)聯(lián)緊密，為了避免網(wǎng)格劃分尺度過(guò)大從而使得聚類效率低下，設(shè)定空間密度q＜0.9 為網(wǎng)格劃分尺度的取值范圍，同時(shí)根據(jù)式（4）給出的分析調(diào)整其最低劃分尺度。即

式（7）限定了網(wǎng)格劃分尺度m的取值范圍，以下實(shí)驗(yàn)也將基于此范圍展開。

圖5 m-q曲線圖Fig.5 m-q curve

3.2 網(wǎng)格優(yōu)化分析

使用表1中的數(shù)據(jù)集，將本文提出的改進(jìn)算法與算法1中的小波聚類算法比較，考察最優(yōu)聚類效果下網(wǎng)格劃分尺度的差異。

圖6 為兩種算法在式（7）給定的網(wǎng)格劃分范圍內(nèi)對(duì)前四個(gè)數(shù)據(jù)集的聚類情況對(duì)比，采用NMI指標(biāo)作為衡量標(biāo)準(zhǔn)，以散點(diǎn)圖的形式記錄其分布情況。由圖6 可以看出，本文算法能夠在較低的網(wǎng)格密度下形成效果較好的聚類，且總體的NMI指數(shù)仍大于原傳統(tǒng)小波聚類算法。但由于算法本身聚類數(shù)目并不固定，可能會(huì)由聚類簇?cái)?shù)的不同從而使結(jié)果偏差。因此，在圖6 的實(shí)驗(yàn)基礎(chǔ)上輔以CH 指標(biāo)對(duì)比分析小波聚類算法和本文算法在數(shù)據(jù)及上的最優(yōu)聚類效果。

圖6 兩種算法在DS數(shù)據(jù)集上的聚類情況Fig.6 Clustering situations of two algorithms on DS datasets

表3 分別選取了兩種聚類算法中CH 指標(biāo)較高且聚類數(shù)接近原始數(shù)據(jù)聚類數(shù)的聚類結(jié)果進(jìn)行對(duì)比，考察兩種算法在最優(yōu)聚類效果下網(wǎng)格劃分尺度的差異。

表3 不同算法在DS數(shù)據(jù)集上的聚類結(jié)果Tab.3 Clustering results of different algorithms on DS datasets

結(jié)合表3 與圖6 可知，本文算法在精度變化不大的情況下，相較于傳統(tǒng)小波聚類算法減小了50%～60%的網(wǎng)格劃分尺度；但由于本文算法在處理連通區(qū)域時(shí)消耗的時(shí)間要遠(yuǎn)大于傳統(tǒng)小波聚類算法，所以時(shí)間性能上只提升了25%左右。

但本文算法在非密集型簇類時(shí)聚類性能與傳統(tǒng)小波聚類算法差別不太明顯。圖7 展示了在均勻分布數(shù)據(jù)下本文算法與傳統(tǒng)小波聚類算法的聚類對(duì)比。由于兩種算法在ring 和Zigzag 數(shù)據(jù)集上聚類效果相同，所以這兩個(gè)數(shù)據(jù)集中僅展示了本文算法的聚類結(jié)果。表4 給出了兩種算法在這四種數(shù)據(jù)集上的網(wǎng)格劃分尺度及聚類數(shù)。

圖7 均勻分布數(shù)據(jù)上的聚類結(jié)果Fig.7 Clustering results on uniformly distributed data

表4 非凸數(shù)據(jù)集上的網(wǎng)格劃分尺度Tab.4 Grid division scales on non-convex datasets

結(jié)合表4 與圖7 可知，對(duì)于ring 和Zigzag 數(shù)據(jù)集，本文算法與傳統(tǒng)小波聚類算法聚類性能差別不大，并且它們使用的網(wǎng)格劃分尺度也基本相同；但在處理形如sym 與Aggregation這種簇間距離較小的數(shù)據(jù)集聚類時(shí)，本文算法相比傳統(tǒng)小波聚類算法的網(wǎng)格劃分尺度平均減小了25%，且能夠分離出較為緊密的簇類。

綜合上述實(shí)驗(yàn)結(jié)果，本文算法相對(duì)于傳統(tǒng)小波聚類算法，對(duì)于聚類緊密的數(shù)據(jù)集效果提升十分明顯，尤其是在凸數(shù)據(jù)集上的提升尤為顯著。產(chǎn)生上述結(jié)果的原因主要是傳統(tǒng)小波聚類算法在檢測(cè)連通區(qū)域時(shí)，以連通為條件判定該區(qū)域元素所屬簇類。這種檢測(cè)方式能夠快速地尋找到數(shù)據(jù)集中相互連通的網(wǎng)格，但在對(duì)簇間距離較小的數(shù)據(jù)集聚類時(shí)，較小的網(wǎng)格劃分尺度不足以分隔不同的簇類，而較大的網(wǎng)格劃分尺度又會(huì)使得原本同一簇類的元素被分為多個(gè)簇類。

相對(duì)于傳統(tǒng)小波聚類算法，本文算法在連通區(qū)域的基礎(chǔ)上，使用峰值網(wǎng)格作為連通區(qū)域的中心，并以峰值連通區(qū)域邊緣的低密度網(wǎng)格為邊界分隔密度差距較大的網(wǎng)格，從一定程度上改善了原算法對(duì)于緊密簇類的聚類效果，能夠在低網(wǎng)格尺度下形成較為穩(wěn)定的聚類。這也是本文算法對(duì)高密度區(qū)域集中的凸數(shù)據(jù)集的聚類效果更好的原因。

3.3 與其他算法在UCI數(shù)據(jù)集的聚類對(duì)比

將本文算法運(yùn)用到分布更為復(fù)雜的真實(shí)數(shù)據(jù)集中，分析其聚類的效果并驗(yàn)證相對(duì)于傳統(tǒng)小波聚類算法的提升。本次實(shí)驗(yàn)使用多種聚類算法［7，10，15-17］進(jìn)行對(duì)比。

表5 為本次對(duì)比實(shí)驗(yàn)采取的真實(shí)數(shù)據(jù)集，數(shù)據(jù)均來(lái)自UCI。從表5可以看出，本文算法在時(shí)間性能上較傳統(tǒng)小波聚類算法平均提升了14%，與文獻(xiàn)［7］算法和文獻(xiàn)［10］算法相比在聚類性能上有所提高。本文算法與文獻(xiàn)［7］算法相比，在其廣度優(yōu)先搜索的基礎(chǔ)上更進(jìn)一步地使用峰值網(wǎng)格區(qū)域劃分簇類邊緣，對(duì)于使用DBSCAN（Density-Based Spatial Clustering of Applications with Noise）和CLIQUE（CLustering In QUEst）算法難以分割的簇類同樣能得到較好的結(jié)果。與文獻(xiàn)［10］算法相比，本文算法在時(shí)間性能上也有所提高，其原因在于本文算法在簇邊界劃分上僅使用峰值網(wǎng)格作為參考，相較于使用K-Means 算法劃分網(wǎng)格邊界的方法所需求的計(jì)算量更??；但本文算法總體時(shí)間性能仍要弱于K-Means算法。

表5 多種聚類算法在UCI數(shù)據(jù)集上的性能對(duì)比Tab.5 Performance comparison of multiple clustering algorithms on UCI datasets

4 結(jié)語(yǔ)

本文通過(guò)研究小波聚類算法中網(wǎng)格劃分精度和檢測(cè)連通區(qū)域的相關(guān)算法，提出了一種基于峰值網(wǎng)格的連通檢測(cè)算法用以改進(jìn)低密度網(wǎng)格劃分尺度下的小波聚類算法的聚類效果。算法將峰值網(wǎng)格依序排列，通過(guò)廣度優(yōu)先搜索算法檢測(cè)連通區(qū)域并按照不同的峰值區(qū)域分割聚類邊緣。在網(wǎng)格優(yōu)化測(cè)試中能夠以低于原傳統(tǒng)小波聚類算法的網(wǎng)格劃分尺度區(qū)分不同的簇類，同時(shí)在UCI 數(shù)據(jù)集的聚類問(wèn)題上取得了較好的聚類結(jié)果。

但在針對(duì)聚類邊緣不清晰的數(shù)據(jù)聚類時(shí)，本文算法與傳統(tǒng)小波聚類算法聚類性能差別不大。對(duì)于小波聚類算法這種基于網(wǎng)格的聚類算法而言，如果不從網(wǎng)格內(nèi)部解決聚類邊緣問(wèn)題，那么只能通過(guò)改變網(wǎng)格劃分尺度來(lái)分離不同的簇類。本文算法對(duì)小波聚類算法的改進(jìn)并沒(méi)有深入到網(wǎng)格內(nèi)部，在連通區(qū)域檢測(cè)方式上的改進(jìn)雖然從一定程度上改善了對(duì)聚類邊緣緊密的數(shù)據(jù)的聚類效果，但對(duì)簇類區(qū)域互有交叉的聚類應(yīng)用效果不好。如何通過(guò)調(diào)整網(wǎng)格內(nèi)部的關(guān)系從而改善對(duì)邊緣不清晰的聚類效果將是以后改進(jìn)研究的重點(diǎn)方向。