基于峰值網格改進的小波聚類算法

龍超奇，蔣 瑜，謝 雨

（成都信息工程大學軟件工程學院，成都 610225）

0 引言

小波聚類（WaveCluster）算法［1］是一種基于網格的聚類算法。該算法從多維信號處理的角度出發，能夠有效地處理大數據集，發現任意形狀的簇，不容易受到噪聲的影響。這些優點使得小波聚類算法被廣泛地應用于數據處理。

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

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

但上述算法均并沒有從聚類精度與網格劃分尺度的大小方向討論MAUP，本文通過研究劃分網格的粒度粗細對聚類精度影響，并提出了一種基于峰值網格的連通區域檢測算法。實驗結果表明改進后的算法能夠在較低的網格粒度下得到較好的聚類結果。

1 基礎概念

由于小波聚類算法是基于網格進行的聚類算法，需要將原始數據映射到網格空間中。

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

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

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

由式（2）可知，網格空間進行小波變換后的網格空間Pwave中總網格數為：

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

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

小波聚類中，對于低密度網格的判別主要依靠密度閾值作為主要判別依據，并根據高密度網格建立連通區域。

定義2設網格密度閾值為t。對于任意的變換后網格，若網格的值大于t，則視為稠密網格；否則為稀疏網格。

定義3在空間Pwave中，若網格a可以通過若干個稠密網格到達網格b，則稱a與b互為可達網格。對于網格空間中某一區域的所有網格，若其中的網格均互為可達網格，則視該區域為連通區域。

算法1給出了傳統小波聚類算法的算法步驟［13］。

算法1 小波聚類算法。

輸入dt數據，m網格數目，t密度閾值，wavelet小波基。

輸出cluster_result聚類結果。

1）構造大小為md的網格空間，將數據映射到網格空間中。

2）以wavelet作為小波基進行小波變換，得到變換后的網格空間Pwave。

3）遍歷Pwave中的網格，檢查其中的連通區域，Pwave中網格密度低于t的記為稀疏網格。

4）標記不同的連通區域為不同的簇類。

5）建立數據與小波變換后網格空間的查找表，將Pwave中的簇類記錄到cluster_result中。

6）輸出cluster_result。

2 算法改進

2.1 網格尺度分析

網格空間Pgrid經離散小波變換產生的網格空間Pwave中以數值形式反映網格間關系。由式（2）可知，離散小波變換過程中，能量會向具有更高密度的網格匯聚，變換后網格的數值是由其身周共計x個網格共同決定的。其中x的值為：

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

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

圖2 兩個不同的簇類Fig.2 Two different clusters

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

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

從圖3 中可以發現，較低網格密度下，雖然產生的小波變換矩陣較小且算法的消耗較低，但密集的變換矩陣導致只劃分出了一個有效的聚類；雖然圖3（d）中通過提高網格尺度產生了兩個有效聚類，但由于高網格尺度下的元素相對分散稀疏網格增多，從而產生了較多的離群點，導致算法只能大致地劃分數據中不同的簇類，并且較大的網格劃分尺度也會增加算法的時間及空間消耗。

對比圖2及圖3（a）和（b）可知，小波變換后的網格數值反映了原數據中高密度的區域和低密度區域的分布。在高密度的區域內其網格數值較大，而低密度區域和邊緣區域的網格數值往往遠小于高密度區域。然而從圖3 中可以發現，小波聚類算法對經小波變換后的網格數值并沒有很好地運用起來，僅通過密度閾值對其進行了分割處理。

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

圖3 不同網格劃分尺度的聚類過程Fig.3 Clustering processes of different grid division scales

2.2 基于峰值網格的連通區域檢測

定義4對小波變換后的網格空間Pwave中任意網格Cw，若Cw中值大于周圍x個數據點，則視Cw為峰值網格，Cw及其周圍x個網格相連所構成的區域稱為峰值連通區域。

如果有若干個峰值連通區域重合，則視整個連通區域為其中最大的峰值網格形成的極大峰值連通區域。

經小波變換的網格空間Pwave中可以獲得若干個峰值網格，在判斷峰值連通區域時可以使用廣度優先搜索算法檢測連通區域并處理連通區域的邊緣網格。

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

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

因此，利用峰值網格建立連通區域的算法如算法2所示。

算法2 峰值網格連通檢測算法。

輸入dt數據，m網格數目，wavelet小波基，θ波動系數。

輸出cluster_result聚類結果。

1）同算法1 中1）、2）兩步，得到經小波變換后的網格空間Pwave。

2）對小波變換后的網格數據快速排序。

3）從下標0開始選取Pwave中未被標記的網格并入隊。

4）隊列隊頭元素出隊并標記其為新的簇類。

5）通過廣度優先搜索遍歷與該出隊元素相鄰的所有網格，若其中某一網格的值滿足式（5），將該網格入隊并標記該網格屬于當前極大峰值區域對應的簇。

6）重復步驟4）直到隊列為空。

7）重復步驟3）直到Pwave中所有網格均被標記。

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

9）輸出cluster_result。

對圖2 中的數據使用算法2，可以在較低網格劃分尺度（m=6）下得到較好的聚類結果，如圖4所示。

圖4 算法2聚類結果Fig.4 Clustering results by algorithm 2

相對于算法1，在同樣低網格尺度下，算法2 利用高密度區域的網格，能夠更快地根據聚類中心尋找連通區域，同時還能分割處理較低網格劃分尺度下不同的簇類，所取得的聚類結果更好。

2.3 時間復雜度分析

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

在n?k的情況下，本文算法的時間復雜度量級為O（n），與傳統小波聚類算法的時間復雜度量級相同。雖然本文算法在計算連通區域時的時間復雜度大于原小波聚類算法，但本文算法能以更低的網格劃分尺度進行聚類，所以時間性能上略優于傳統小波聚類算法。

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

3 實驗與結果分析

3.1 實驗使用的數據集及參數

本文使用了人工數據集和UCI數據集分析本文算法相對于傳統小波聚類算法以及現有的聚類算法的改進程度。其中，人工數據集主要用于測試本文算法在不同形狀的數據集以及網格尺度方面的優化程度，UCI 數據集用于考察本文算法相對于其他聚類算法的優勢和劣勢。本文實驗基于Windows10操作系統，使用的編譯語言為Python 3.6.5。

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

表1 人工數據集Tab.1 Synthetic datasets

表2 UCI數據集Tab.2 UCI datasets

本文實驗采用外部指標歸一化互信息（Normalized Mutual Information，NMI）和內部指標CH（Calinski-Harabaz score）作為聚類效果評估參數。

NMI 常用在聚類中度量兩個聚類結果的相近程度，是重要的外部衡量指標，可以比較客觀地評價出當前簇類劃分與標準劃分之間相比的準確度。NMI的值域是0 到1，越高代表劃分得越準。

CH 指標通過計算類中各點與類中心的距離平方和來度量類內的緊密程度，通過計算各類中心點距離平方和來度量數據集的分離度，CH 指標由分離度與緊密度的比值得到。CH 指標越大代表著類中元素越緊密，類與類之間越分散，且CH指標只受到數據自身分布的影響，有利于分析不同聚類簇數下的聚類效果。

不同的網格密度會產生不同的聚類結果，由第2 章可知，網格劃分越緊密，網格空間中存有數據的網格越少。為了評價數據進網格劃分后的密集程度，本文使用空間密度q表示了經過網格排列后數據的緊密程度，公式如下：

其中：Ngrid為數據映射到網格空間Pgrid中的非空網格個數；N為原始數據樣本個數。

由網格劃分的概念可知，對于任意的聚類數據集，其網格劃分尺度m及密度q之間的大致關系如圖5所示。

在網格空間中，空間密度q與網格劃分尺度m呈正相關。隨著網格劃分尺度m的增長，空間密度q的遞增速度會隨著聚類分布逐步改變。當q的增長速度放緩時，則說明數據中的聚類程度通過網格空間已經難以劃分，此時再增大網格劃分尺度對于改善聚類的效果甚微。

基于以上分析，由于小波聚類算法時間密度與網格劃分尺度關聯緊密，為了避免網格劃分尺度過大從而使得聚類效率低下，設定空間密度q＜0.9 為網格劃分尺度的取值范圍，同時根據式（4）給出的分析調整其最低劃分尺度。即

式（7）限定了網格劃分尺度m的取值范圍，以下實驗也將基于此范圍展開。

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

3.2 網格優化分析

使用表1中的數據集，將本文提出的改進算法與算法1中的小波聚類算法比較，考察最優聚類效果下網格劃分尺度的差異。

圖6 為兩種算法在式（7）給定的網格劃分范圍內對前四個數據集的聚類情況對比，采用NMI指標作為衡量標準，以散點圖的形式記錄其分布情況。由圖6 可以看出，本文算法能夠在較低的網格密度下形成效果較好的聚類，且總體的NMI指數仍大于原傳統小波聚類算法。但由于算法本身聚類數目并不固定，可能會由聚類簇數的不同從而使結果偏差。因此，在圖6 的實驗基礎上輔以CH 指標對比分析小波聚類算法和本文算法在數據及上的最優聚類效果。

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

表3 分別選取了兩種聚類算法中CH 指標較高且聚類數接近原始數據聚類數的聚類結果進行對比，考察兩種算法在最優聚類效果下網格劃分尺度的差異。

表3 不同算法在DS數據集上的聚類結果Tab.3 Clustering results of different algorithms on DS datasets

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

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

圖7 均勻分布數據上的聚類結果Fig.7 Clustering results on uniformly distributed data

表4 非凸數據集上的網格劃分尺度Tab.4 Grid division scales on non-convex datasets

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

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

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

3.3 與其他算法在UCI數據集的聚類對比

將本文算法運用到分布更為復雜的真實數據集中，分析其聚類的效果并驗證相對于傳統小波聚類算法的提升。本次實驗使用多種聚類算法［7，10，15-17］進行對比。

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

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

4 結語

本文通過研究小波聚類算法中網格劃分精度和檢測連通區域的相關算法，提出了一種基于峰值網格的連通檢測算法用以改進低密度網格劃分尺度下的小波聚類算法的聚類效果。算法將峰值網格依序排列，通過廣度優先搜索算法檢測連通區域并按照不同的峰值區域分割聚類邊緣。在網格優化測試中能夠以低于原傳統小波聚類算法的網格劃分尺度區分不同的簇類，同時在UCI 數據集的聚類問題上取得了較好的聚類結果。

但在針對聚類邊緣不清晰的數據聚類時，本文算法與傳統小波聚類算法聚類性能差別不大。對于小波聚類算法這種基于網格的聚類算法而言，如果不從網格內部解決聚類邊緣問題，那么只能通過改變網格劃分尺度來分離不同的簇類。本文算法對小波聚類算法的改進并沒有深入到網格內部，在連通區域檢測方式上的改進雖然從一定程度上改善了對聚類邊緣緊密的數據的聚類效果，但對簇類區域互有交叉的聚類應用效果不好。如何通過調整網格內部的關系從而改善對邊緣不清晰的聚類效果將是以后改進研究的重點方向。