龍章勇

（南京鐵道職業(yè)技術(shù)學(xué)院，江蘇　南京　210031）

基于局部密度估計的聚類個數(shù)確定研究

龍章勇

（南京鐵道職業(yè)技術(shù)學(xué)院，江蘇南京210031）

隨著人工智能和數(shù)據(jù)挖掘技術(shù)的興起，聚類分析已被廣泛應(yīng)用于通信、文本數(shù)據(jù)統(tǒng)計、生物信息學(xué)和圖像處理中。對于非監(jiān)督聚類分析，聚類的分類數(shù)目是決定聚類質(zhì)量的關(guān)鍵因素。通常聚類個數(shù)事先無法確定，隨即選擇的初始聚類中心容易使聚類結(jié)果不穩(wěn)定。針對此，基于聚類中心具有高局部密度且距高局部密度聚類中心距離較遠(yuǎn)的特點(diǎn)，提出一種基于局部密度估計的聚類個數(shù)的估計方法。經(jīng)過仿真實(shí)驗(yàn)，驗(yàn)證了該算法具有良好的有效性和魯棒性。

聚類個數(shù)；密度峰值估計；聚類有效性；聚類分析

隨著計算機(jī)和互聯(lián)網(wǎng)應(yīng)用的普及，信息和數(shù)據(jù)爆炸似的增長，復(fù)雜的多種信息數(shù)據(jù)也可以作為很重要的研究內(nèi)容。從海量數(shù)據(jù)的研究和挖掘中提取出互有關(guān)系的信息變得非常重要，甚至決定了社會科技的發(fā)展。聚類算法作為數(shù)據(jù)分析的主要工具，已在多方面被廣泛地研究和應(yīng)用。

1　聚類有效性分析與聚類個數(shù)估計

1.1聚類有效性分析

現(xiàn)在常用的估計聚類個數(shù)的有效性評價方法大概有3種：有效性指標(biāo)、檢測穩(wěn)定聚類結(jié)構(gòu)的穩(wěn)定性方法和系統(tǒng)演化方法。其中，有效性指標(biāo)在實(shí)際中應(yīng)用廣泛，包括Silhouette指標(biāo)、Davies-Bouldin指標(biāo)、Calinski-Harabasz指標(biāo)、加權(quán)的類間類內(nèi)相似度比率和Homogeneity-Separation指標(biāo)等。

1.1.1平均Silhouette（Sil）指標(biāo)。設(shè)a（t）為聚類Cj中的樣本t與類內(nèi)所有其他樣本的平均不相似度或距離，d（t，Ci）為樣本t到另一個類Ci的所有樣本的平均不相似度或距離，則b（t）=min｛d（t，Ci）｝，i=1，2，……，k；i≠j［1］。Sil指標(biāo)計算每個樣本與同一聚類中樣本的不相似度以及與其他聚類中樣本的不相似度，其每個樣本t的計算公式如下：

一般以一個數(shù)據(jù)集的所有樣本的平均Sil值來評價聚類結(jié)果的質(zhì)量，Sil指標(biāo)越大，表示聚類質(zhì)量越好，其最大值對應(yīng)的類數(shù)作為最優(yōu)的聚類個數(shù)。

1.1.2Davies-Bouldin（DBI）指數(shù)。DBI指數(shù)是基于樣本的類內(nèi)散度與各聚類中心間距的測度，進(jìn)行類數(shù)估計時其最小值對應(yīng)的類數(shù)作為最優(yōu)的聚類個數(shù)。設(shè)DWi表示聚類Ci的所有樣本到其聚類中心的平均距離，DCij表示聚類Ci和聚類Cj中心之間的距離，則DB指標(biāo)如下：

1.1.3Calinski-Harabasz（CH）指標(biāo)。CH指標(biāo)（偽F統(tǒng)計量）是基于全部樣本的類內(nèi)離差矩陣與類間離差矩陣的測度，其最大值對應(yīng)的類數(shù)作為最優(yōu)的聚類個數(shù)，則CH指標(biāo)如下：

其中，SSB和SSw分別表示類間離差矩陣和類內(nèi)離差矩陣，k為聚類數(shù)目。類間離差矩陣SSB定義如下：

其中，mi，m分別表示第i個類的中心和類內(nèi)平均，||mi-m||定義了向量之間的歐式距離。類內(nèi)離差矩陣SSw的定義如下（也稱為Hartigan指標(biāo)）：

其中，x，Ci分別表示數(shù)據(jù)點(diǎn)和第i個類。

從定義可以看出：好的聚類結(jié)果，是希望SSB越大越好和SSw越小越好。因此，CH（k）的值越大，選擇的k值越接近最優(yōu)。

1.2聚類數(shù)目對有效性的影響

對于盲聚類分析，聚類數(shù)目和聚類初始中心對于結(jié)果的影響很明顯，因?yàn)槟壳安捎玫木垲愃惴?，類似于K-均值聚類，都對類數(shù)和初始聚類中心敏感。

不失一般性，對同一組數(shù)據(jù)集合，分別采用目標(biāo)類數(shù)為3～5進(jìn)行K-均值聚類，仿真的對比結(jié)果如圖1所示。

（a）采用k=3聚類的結(jié)果

圖1　不同類數(shù)下的K均值聚類結(jié)果

為了對比不同聚類數(shù)目下的聚類結(jié)果的性能指標(biāo)，對上述實(shí)驗(yàn)數(shù)據(jù)，分別采用2.1節(jié)中的指標(biāo)進(jìn)行評估，結(jié)果如圖2所示。從圖2可以看出，前3種指標(biāo)顯示，選擇類數(shù)為4最接近最優(yōu)的聚類目標(biāo)。但是采用Hartigan指標(biāo)，其結(jié)果不然。

圖2　4種有效性指標(biāo)估計結(jié)果

上述實(shí)驗(yàn)中，不同的指標(biāo)所側(cè)重的測度是不一致的，從而適用的應(yīng)用場景也是有區(qū)別的。另外，從相鄰類數(shù)下指標(biāo)的走勢可以看出，K-均值算法對于類數(shù)敏感性顯而易見。因此，在聚類之前，能夠確定有效的聚類數(shù)目是非常必要和重要的。

2　基于局部密度估計的聚類個數(shù)確定

給定點(diǎn)集S，對于每一個樣本點(diǎn)i，為其定義2個屬性參量：局部密度ρi和距離高密度點(diǎn)集的距離δi。樣本點(diǎn)i的局部目的ρ定義如下：

其中，dij為樣本點(diǎn)i和樣本點(diǎn)j之間的“距離”度量，并且滿足三角不等式；dc是常數(shù)參數(shù)，定義為截止距離，其物理意義是控制樣本點(diǎn)的影響最遠(yuǎn)距離。式（6）中函數(shù)R（x）的定義如式（7）：

其中，ρi表示距離i的距離小于dc的樣本點(diǎn)數(shù)量。i的參數(shù)δi計算如下：

其中，max（ρ）為點(diǎn)集S的最大局部密度。從式（8）可以看出，對于非最大局部密度樣本點(diǎn)，δi定義為樣本點(diǎn)i距離其他任意更高局部密度樣本點(diǎn)的最小距離；而對于最大局部密度樣本點(diǎn)，δi定義為其他點(diǎn)到此點(diǎn)的最大距離。

通過對點(diǎn)集S中的樣本經(jīng)行二維空間的處理，以 ρi和δi兩個指標(biāo)對點(diǎn)集降維處理。其中，ρi用來限制點(diǎn)集在多維測度空間內(nèi)的局部密度，而δi用來度量局部密度較大的多維點(diǎn)集在測度空間內(nèi)的相對聚類。距離其他高局部密度較“遠(yuǎn)”的點(diǎn)，稱為在決策圖上的“孤點(diǎn)”?！肮曼c(diǎn)”的個數(shù)即是聚類的估計類數(shù)。在局部密度的估計中，截止距離dc的選擇非常重要，其影響了局部密度測度空間的邊界。對于dc的選擇準(zhǔn)則，還需要進(jìn)一步的理論分析，但是多次實(shí)驗(yàn)證明，dc的選擇需要保證局部密度的最小取值不小于點(diǎn)集總數(shù)的1%～2%。

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

對于2.2中所采樣的同樣的數(shù)據(jù)數(shù)據(jù)集合，使用2中介紹的基于局部密度估計的方法，計算點(diǎn)集中每個樣本的ρi和δi兩個指標(biāo)，繪出決策圖如圖3所示。

從圖3可以看出，在ρi和δi兩個指標(biāo)都很“突出”的區(qū)域有4個明顯的“孤”點(diǎn)。所以，估計算法確定出的聚類數(shù)目為k=4。對于2.2節(jié)的結(jié)論，兩者的結(jié)論是一致的。通過對多組數(shù)據(jù)的實(shí)驗(yàn)，該文所提出的算法估計出的聚類類數(shù)和Sil指標(biāo)、DBI指標(biāo)和CH指標(biāo)的一致率分別是99.4%、99.1%和98.8%。

圖3　基于局部密度估計的決策圖

4　結(jié)論

從K-均值算法對于聚類個數(shù)和初始中心敏感的缺陷出發(fā)，基于聚類中心具有高密度且距高局部密度聚類中心具有較遠(yuǎn)距離的特點(diǎn)，提出一種基于局部密度估計的聚類個數(shù)的估計方法。經(jīng)過仿真實(shí)驗(yàn)，驗(yàn)證了該算法具有良好的有效性和魯棒性。

Cluster Number Estimation Based on Local Density Estimator

Long Zhangyong
（Nanjing Institute of Railway Technology，Nanjing Jiangsu 210031）

With the development of artificial intelligence and data mining technology，cluster analysis has been widely used in many fields，which range from communication to bioinformatics，bibliometrics，and image processing.For unsupervised clustering analysis，the number of clusters is the key factor to determine the quality of clustering.Usually the number of clusters can not be determined in advance，then the initial cluster center is easy to make that the clustering result is not stable.For this，based on the characteristic that the cluster centers have a high local density and a relatively large distance from the high local density clustering center，a new method for estimating the number of clusters based on local density estimation was proposed.The simulation showed that the proposed algorithm performance was effective and robust.

cluster number；density peaks estimator；cluster validation；cluster analysis

TP18

A

1003-5168（2016）05-0026-03

2016-04-18

中國職教學(xué)會軌道交通專業(yè)委員會科研基金（201419）；全國教育信息技術(shù)研究十二五規(guī)劃課題（136231366）。

龍章勇（1979-），男，碩士，講師，研究方向：無線通信技術(shù)。

［1］Kaufman L，P J Rousseeuw.Finding Groups in Data：An Introduction to Cluster Analysis［M］.Hoboken，NJ：John Wiley&Sons，Inc.，1990.