龍章勇

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

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

龍章勇

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

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

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

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

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

1.1聚類有效性分析

現(xiàn)在常用的估計(jì)聚類個(gè)數(shù)的有效性評(píng)價(jià)方法大概有3種：有效性指標(biāo)、檢測(cè)穩(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到另一個(gè)類Ci的所有樣本的平均不相似度或距離，則b（t）=min｛d（t，Ci）｝，i=1，2，……，k；i≠j［1］。Sil指標(biāo)計(jì)算每個(gè)樣本與同一聚類中樣本的不相似度以及與其他聚類中樣本的不相似度，其每個(gè)樣本t的計(jì)算公式如下：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

給定點(diǎn)集S，對(duì)于每一個(gè)樣本點(diǎn)i，為其定義2個(gè)屬性參量：局部密度ρ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計(jì)算如下：

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

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

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

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

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

圖3　基于局部密度估計(jì)的決策圖

4　結(jié)論

從K-均值算法對(duì)于聚類個(gè)數(shù)和初始中心敏感的缺陷出發(fā)，基于聚類中心具有高密度且距高局部密度聚類中心具有較遠(yuǎn)距離的特點(diǎn)，提出一種基于局部密度估計(jì)的聚類個(gè)數(shù)的估計(jì)方法。經(jīng)過(guò)仿真實(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

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

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

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