一種基于網格的等密度線聚類算法

徐明釗，楊 春，范 健，張 健，張耐民

(北京宇航系統工程研究所，北京 100076)

【信息科學與控制工程】

一種基于網格的等密度線聚類算法

徐明釗，楊 春，范 健，張 健，張耐民

(北京宇航系統工程研究所，北京 100076)

提出了一種基于網格的等密度線聚類算法，通過對樣本所在空間進行網格劃分，從樣本分布等密度線圖的思想出發，可自動發現任何形狀的類，時間復雜度和空間復雜度較好，實現了對不同類樣本空間容積的計算，具有很好的聚類效果和容積計算能力。

聚類；網格；等密度線；容積

聚類[1]作為數據挖掘中常用的手段，把一個沒有類別標記的樣本集在無先驗知識的情況下按某種準則分成若干個子集，使相似的樣本歸為一類，而不相似的樣本盡量劃分到不同的類中。聚類分析的方法可以分為以下幾類：基于劃分的方法、基于層次的方法、基于密度的方法、基于網格的方法和基于模型的方法[2]。在實際應用中，常常需要針對不同算法的特點，結合上述多種聚類方法，才能針對具體問題收到理想的效果。本文提出了一種基于網格的等密度線聚類算法，實現了樣本的聚類分析。

1 等密度線聚類算法

1.1 等密度線聚類算法概述

等密度線聚類算法是一種基于密度的聚類方法，密度是衡量點的疏密程度的概念。通常把每一樣本作為中心，在一定體積內包含樣本的數目作為該樣本的密度。現有一些聚類算法(如DBSCAN算法等)只關注高密度樣本的部分[3]，卻忽視了高密度周圍低密度數據集的聚類。另外，聚類過程中無法對孤立樣本進行處理，所以不能對多密度數據集進行聚類。Chamelenon等一些算法盡管可以對多密度數據集進行聚類，但是聚類精度不高，無法對不同的密度區間進行準確劃分。

趙艷廠等[4]從聚類點的樣本分布等密度線圖的思想出發，找出樣本分布比較集中的區域，從而發現隱含在樣本集中的類。在此基礎上，本文提出了一種等密度線聚類方法，統計出每個樣本鄰域內包含樣本的數目作為該樣本的密度值，根據密度值實現對樣本的聚類，其中每個子類可以是不連通的集合。

1.2 算法步驟

等密度線聚類算法的步驟如下：

1) 對于樣本集中所有n個樣本點X，統計出任意兩點之間的距離，得到距離矩陣dist，dist(i,j)=D(X(i),X(j)),i,j=1,…,n。

2) 根據距離矩陣dist得到鄰域大小RT，RT=mean(dist)/ncoefRT。其中mean(dist)是任意兩點間的平均距離，coefRT是鄰域調節系數，取值在0到1之間。實驗發現coefRT取0.3時往往會有比較好的聚類結果。

3) 統計密度矩陣den即每個樣本點在鄰域RT內包含的樣本點數目。密度矩陣den的統計示意圖見圖1，對于其中位于圓心處的點，在其RT鄰域內的點的個數為4，那么該點的密度為4。

圖1 密度矩陣den的統計示意圖

4) 根據密度矩陣確定密度閾值向量DT，即密度線向量。DT的選擇與樣本的密度分布直接相關，例如當密度低到密度高的樣本的個數呈現快速增長趨勢，可將DT設定為一個等比增加的序列。具體使用過程中常常需要根據聚類的結果調整DT的取值，以便最后達到最滿意的聚類效果。

5) 根據密度閾值向量DT完成子類的劃分。把密度值在兩條等密度線之間的樣本歸為一類。如果聚類效果不好，則調整DT的取值，重新聚類。

2 基于網格的等密度線聚類算法

2.1 基于網格的等密度線聚類算法概述

針對某些特定問題的聚類分析，除了完成已有數據樣本的聚類外，還需要對聚類樣本在空間內占據的空間大小或分布(容積)進行計算。等密度線聚類算法可以實現基于密度的聚類，但無法計算聚類樣本的“容積”。為了解決這一問題，本文對該算法做了適當改進，提出了一種基于網格劃分的等密度線聚類算法。

基于網格的聚類方法采用網格這一數據結構對聚類空間進行了劃分，把空間量化為有限的數據單元，并以此為基本單位進行聚類[5]。經過網格劃分后的空間聚類樣本變成了網格，不再是孤立的樣本點，因此方便了統計樣本空間，實現了容積計算。

目前常見的基于網格的聚類算法有以下幾種：STING算法是一種基于網格的多分辨率聚類方法，網格結構利于并行處理和數據的更新，效率高，但是聚類的精度較低；WaveCluster算法[6]在數據空間中加入了一個多維網格結構，并用小波變換變換原來的特征空間，算法較為復雜；CLIQUE算法[6]綜合了基于密度和基于網格兩種聚類算法，適合用于大型數據庫和高位數據的聚類，但是聚類的精度較差。以上3種算法無法進行多密度聚類，也無法實現對聚類后容積的計算。

2.2 算法步驟

基于網格的等密度線聚類算法借鑒了基于網格的聚類算法以及等密度線聚類算法的思想，具體步驟為：

1) 對于樣本集中所有n個樣本點X，計算任意兩點之間的平均距離mean(dist)，然后計算出鄰域大小RT，RT=mean(dist)/ncoefRT，其中coefRT是鄰域調節系數，計算過程同1.2節。

2) 網格的劃分。把聚類空間每個維度劃分為p個區間

表示上取整)

網格劃分的大小將直接影響聚類的效果，網格太大或太小會導致網格中包含的樣本數量不合理，導致最終的聚類結果不精確。此外如果網格太小，空間中網格數太多會導致時間復雜度大大增加。文獻[7]給出了網格劃分大小的依據，其中的區間劃分系數coefM是一個正數的調節系數，其取值范圍在一般情況下為1～2。

3) 鄰域網格的確定。計算統計密度時，每一維的鄰域網格數ri=ceil(RT/Leni×p)，其中，Leni是聚類空間在每一維上的長度投影。

步驟2)對聚類空間劃分網格，但是統計密度的時候不宜直接統計每個網格中樣本的個數，算法吸取了圖像處理中的相關處理方法[8]，統計每個網格及其鄰域中樣本的數目，作為此網格的密度，相當于對網格密度做了一次高斯平滑，達到減少噪聲的目的[9]。

5) 根據網格密度矩陣確定密度閾值向量DT。算法密度閾值矩陣DT的確定仍然沿用等密度線聚類算法的公式。具體使用過程中常常需要根據聚類的結果調整DT的取值，以便達到最滿意的聚類效果。

6)根據密度閾值向量DT完成子類的劃分。把密度值在兩條等密度線之間的樣本點歸為一類。如果聚類效果不好，則調整DT的取值，重新聚類。

圖2 密度矩陣den的統計

3 算法的性能分析

3.1 聚類結果比較

選取二維正態分布進行隨機采樣的點進行聚類，以對比基于網格的等密度線聚類算法與等密度線聚類算法的效果和性能。

二維正態分布的聯合概率密度函數為

其中：μ1、μ2是兩個變量的期望；σ1、σ2是兩個變量的方差；ρ是協方差系數。

實驗中二維正態分布的參數選取為

實驗中設定聚類的子類數目為5。對于2 000點、6 000點的樣本集，兩種聚類方法得到的聚類結果如圖3。

由圖3所示的實驗結果可以看出，基于網格的等密度線聚類方法與等密度線聚類方法具有相當的聚類效果。兩種聚類方法都能夠有效地將以二維正態分布采樣的點聚類成5個近似同心圓環的子類，在樣本點較多的情況下聚類效果更好。當樣本點較少的情況下，兩種聚類算法對子類邊緣的樣本不能很好的處理，聚類性能有所下降。

圖3 兩種聚類方法對不同樣本點數的聚類效果比較

3.2 復雜度分析

在算例中，采用Matlab編程并利用Intel i7處理器的計算機計算，其中2 000點聚類計算中等密度線聚類算法耗時2.548 s，基于網格的等密度線聚類算法耗時1.782 s。

在基于網格的等密度線聚類算法步驟4)中提到，該算法密度矩陣可以由樣本點更新的方式進行計算，這使得該算法具有良好的可更新性，適合在工程實踐中使用。

3.3 容積的計算

基于網格的等密度線聚類算法由于對空間進行了網格的劃分，在將樣本聚類的同時也把整個空間分成了幾個子類。因此，可以通過統計每個子類中網格的數目計算出每個子類的“容積”。圖4給出了2 000個樣本點時最終統計出的容積，不同深淺色表示了不同區域中子類的容積。如圖4所示，對應于5個不同的子類，每個網格也被劃分到相應的子類中，統計網格的面積就可以計算出每個子類容積的大小。經統計，按照密度從高到低的子類容積分別為15.87、51.21、43.46、38.73、250.73。

圖4 基于網格的等密度線聚類方法容積的計算

4 結束語

基于網格的等密度線聚類算法步驟清楚，設計方法易于編程實現，時間復雜度和空間復雜度較好，可以完成對數據樣本的有效聚類，同時實現了對樣本空間容積的計算。該算法的提出可為數據挖掘的分析提供參考，具有較大的發展潛力。

[1] 廖芹,郝志峰,陳志宏.數據挖掘與數學建模[M].北京:國防工業出版社,2010.

[2] 呂曉玲,謝邦昌.數據挖掘方法與應用[M].北京:中國人民大學出版社,2009.

[3] 邱保志,沈鈞毅.基于擴展和網格的多密度聚類算法[J].控制與決策,2006,21(9):1011-1014.

[4] 趙艷廠,謝帆,宋俊德.一種新的聚類算法:等密度線算法[J].北京郵電大學學報,2002,25(2):8-13.

[5] 張西芝.網格聚類算法的研究[D].鄭州:鄭州大學,2006.

[6] 趙慧,劉希玉,崔海青.網格聚類算法[J].計算機技術與發展,2010,20(9):83-89.

[7] GAO S,XIA Y.GDCIC:a grid-based density-confidence-interval clustering algorithm for multi-density dataset in large spatial database[C]//Proc of the 6 th International Conference on Intelligent Systems Design and Applications.Washington DC:IEEE Computer Society,2006:713-717.

[8] 田宇,羅辛.一種基于圖像去噪的多密度網格聚類算法[J].智能計算機與研究,2014,6(1):45-47.

[9] 夏英,李克非,豐江帆.基于網格梯度的多密度聚類算法[J].計算機應用研究,2008,25(11):3278-3280.

[10]黃紅偉,黃天民.基于網格相對密度差的擴展聚類算法[J].計算機應用研究,2014,31(6):1702-1705.

(責任編輯 楊繼森)

A Grid-Based Density-Isoline Clustering Algorithm

XU Ming-zhao，YANG Chun，FAN Jian,ZHANG Jian,ZHANG Nai-min

(Beijing Institute of Aerospace System Engineering, Beijing 100076, China)

We proposed a grid-based density-isoline clustering algorithm. The algorithm meshes the space where the samples in, with the thought of density distribution, and it can automatically discover any kind of shape, and has great time complexity and space complexity. In addition, we achieved the calculation of the sample space of different types of volume. It has good clustering effect and volume grid-based computing capabilities.

clustering; grid-based; density-isoline; volume

2016-09-28；

2016-10-20

徐明釗(1986—)，男，碩士，工程師，主要從事導彈總體設計和智能算法研究。

10.11809/scbgxb2017.02.020

徐明釗，楊春，范健，等.一種基于網格的等密度線聚類算法[J].兵器裝備工程學報，2017(2):88-91.

format:XU Ming-zhao，YANG Chun，FAN Jian, et al.A Grid-Based Density-Isoline Clustering Algorithm[J].Journal of Ordnance Equipment Engineering,2017(2):88-91.

TP181

A

2096-2304(2017)02-0088-04