基于密度的最佳聚類數確定方法

[摘要]確定數據集的正確聚類數目是聚類分析中的一個基礎性難題。常用的聚類數確定方法通常依賴特定的聚類算法，且在數據集存在子簇群的情況下效果欠佳。本文提出一種新的最佳聚類數確定的指標，該指標著重于分析簇的幾何結構，從數據對象分布密度的角度來度量類內緊密度與類間分離度。該指標對噪聲不敏感并且可以識別數據集中的子簇群，在實際數據和合成數據上的實驗結果表明，新指標的性能優于廣泛使用的其他指標。

[關鍵字]聚類評估，聚類數，聚類有效性指標

0 引言

聚類是數據挖掘研究中重要的分析手段，其目的是將數據集中對象聚集成類，使得同一類中的對象是相似的，而不同類中的對象是不同的。迄今研究者已經提出了為數眾多的聚類算法，并已經在商務智能、圖形分析、生物信息等領域得到了廣泛應用。作為一種非監督學習的方法，對學習得到的聚類結果進行評估是非常有必要的。因為許多聚類算法需要用戶給定數據集的聚類數量，而在實際應用中這通常是事先不知道的。確定數據集的聚類數問題目前仍是聚類分析研究中的基礎性難題之一 [1][2]。

聚類評估用于評價聚類結果的質量，這被認為是影響聚類分析成功與否的重要因素之一[3]。它在聚類分析過程中的位置如圖1所示。聚類評估的一些重要問題包括確定數據集的聚類趨勢、確定正確的類個數、將聚類分析結果與已知的客觀結果比較等，本文主要研究其中的最佳聚類數的確定。

通常最佳聚類數的確定是通過以下計算過程來確定的。在給定的數據集上，通過使用不同的輸入參數（如聚類數 ）運行特定的聚類算法，對數據集進行不同的劃分，計算每種劃分的聚類有效性指標，最后比較各個指標值的大小或變化情況，符合預定條件的指標值所對應的算法參數 被認為是最佳的聚類數 [4]。

迄今為止，已有各種類型的度量指標從不同角度來評估數據集劃分的有效性，這些指標稱為聚類有效性指標（Clustering Validation Indices）。一般地，用于評估聚類的各方面的評估度量指標可分成以下兩類[5]。

1）外部指標（External index）：指聚類分析的評價函數是針對基準問題的，其簇的個數及每個數據對象的正確分類均為已知。代表性外部指標有熵、純度、F-measure等。

2）內部指標（Internal index）：指數據集結構未知的情況下，聚類結果的評價只依靠數據集自身的特征和量值。在這種情況下，聚類分析的度量追求兩個目標：類內緊密度和類間分離度。這也是本文的主要研究領域，代表性內部指標有DB，CH，XB，SD等。

從其他不同角度，聚類有效性指標又可分為分割指標與層次指標，模糊指標與非模糊指標，統計指標與幾何指標。

用內部指標來評估聚類有效性，獲取數據集最佳劃分或最佳聚類數的過程一般分為以下4步[6]：

第一步：給出一系列用來對數據集進行聚類的聚類算法；

第二步：對于每一種聚類算法，分別使用不同的輸入參數以獲得不同的聚類結果；

第三步：對于第二步中得到的不同聚類結果，計算其內部指標并得到相應的取值；

第四步：根據內部指標所要求的規則選擇最佳分割或最佳聚類數。

1 常用聚類有效性指標

1.1Davies-Bouldin 指標（DB）[7]

DB指標首先計算每個類中各點與類中心的平均距離，然后以此計算每個類與其他各類的相似度，并取最大值作為該類的相似度，最后，DB指標由所有類的相似度平均得到。容易得出，DB越小表示類與類之間的相似度越低，從而對應越佳的聚類結果。

1.2Calinski-Harabasz指標（CH）[8]

CH指標通過計算類中各點與類中心的距離平方和來度量類內的緊密度，通過計算各類中心點與數據集中心點距離平方和來度量數據集的分離度，CH指標由分離度與緊密度的比值得到。從而，CH越大代表著類自身越緊密，類與類之間越分散，即更優的聚類結果。

1.3Xie-Beni指標（XB）[9]

XB指標使用最小的類與類中心距離平方來衡量類間分離度，使用類中各點與類中心的距離平方和來衡量類內緊密度。XB指標也是類內緊密度與類間分離度的比值。和CH指標一樣，XB就是在類內緊密度與類間分離度之間尋找一個平衡點，使其達到最小，從而得到最優的聚類結果。

1.4SD指標[10]

SD有效性指標定義為

SD指標通過計算類中對象的標準差來衡量類內緊密度，通過計算類與類之間的距離來衡量類間分離度。其中 是加權項，可以平衡類內緊密度和類間分離度之間的相對重要性，在本文中， 取值為 。 、 分別是類 與數據集的標準偏差。

2 基于密度的聚類有效性指標（Density Based Index）

由于對于一個特定的聚類算法，不同的輸入參數會導致不同的聚類劃分。而對某一個特定的數據集而言，只有一個劃分結果是最優的。此處的最優劃分是指，相比其他劃分，它和數據集原本的真實劃分是最接近的。

因此，本課題研究的目標是定義一個新的聚類有效性指標，用來評估不同聚類劃分的質量。這個聚類有效性指標可以從數據集使用某一聚類算法得到的劃分結果中，找出最符合真實情況的那一個劃分，從而得到這一劃分所需的輸入參數，如聚類個數。

現有的聚類有效性指標大都是基于對象與中心之間的距離度量，使得其不能很好地捕捉類內部的對象分布情況，同時也忽略了類間的對象分布緊密程度。

由于聚類分析的目的是將數據集中對象聚集成類，使得同一類中的對象是相似的，而不同類中的對象是不同的。從數據幾何分布的角度來看，聚類將使得同一類空間里的對象分布較為密集，而類與類之間的空間對象分布較為稀疏，即可理解為同一類中對象密度比類間對象密度更大。使用基于密度的方法來評估聚類結果的有效性，是和聚類分析的本質相符合的。

給定一個 維數據集 ， 為一個數據對象， 為數據集 中數據對象的個數。一個硬劃分聚類算法將 劃分為 個子集的集合 ，子集 稱為 的類。本文中用 表示數據集 中心點，用 表示類 中心點， 表示 中對象個數， 表示對象間距離。

定義1：類中心密度（cluster center density）

類中心密度是以類 中心點 為中心，給定半徑范圍 ，此類中所有到類中心點距離小于等于 的對象個數。 。

定義2：類半徑（cluster radius）

類半徑是類中所有對象到類中心的距離的平均值。

定義3：類間中位點（medium point between clusters）

類間中位點是在以兩類中心的連線上的一個點，使得中位點到兩類中心的距離的比值等于兩類半徑的比值。如圖2所示，數據集中存在類 、 、 三個類，其中類 的半徑是類 、 的一半，則類 與類 的中位點 到類 中心 距離為到類 中心 距離的一半，而類 與類 的中位點 到類 中心 距離與到類 中心 距離相等。

定義4：類邊緣密度（cluster boundary density）

類邊緣密度是以類 中心點 與數據集中某一類 中心點 的中位點（medium point）為中心，給定半徑范圍 ， 與 中所有到中位點距離小于等于 的對象個數的均值。

在本文中， 取值為 。

定義5：基于密度有效性指標（Density Based Index， DBI）

3 實驗結果

為了說明新指標DBI的效果，我們測試了DBI在各種各樣的數據下的表現，現僅以較具代表性的5組來做一個說明，其中包括了3組生成數據和2組實際數據。3組生成數據由混合高斯分布生成，而另外2組實際數據來源于UCI數據庫。這5組數據的特征如表1所示。

由于數據集Iris和Satimage的維數都大于3維，在文中無法展示其結構。而人工數據集DS1、DS2、DS3的分布如圖3所示。從圖中可以看出，DS1中存在5個分布較好的類和一些噪音，DS2中3個類之間存在著不均衡的分布，而DS3的5個類中存在著子簇群。

實驗中， 使用CLUTO工具對數據集進行聚類，其中數據集DS2使用了Chameleon算法，其余數據集使用了Kmeans算法。因為DS2中存在著不均衡分布，Kmeans算法無法得到合適的聚類結果。實驗中設置最小聚類數為2，最大聚類數為9，包括了5個數據集的最佳聚類數。各指標對5個數據集所選擇的最佳聚類數如表2所示。

從實驗結果可以看出，CH指標對數據集DS2選擇了錯誤的聚類數，DB和SD在數據集DS3下沒能選擇正確的聚類數。對實際數據Iris，只有新指標DBI選擇了正確聚類數3，而對實際數據Satimage，所有的指標都沒有選擇正確的聚類數。在這組實驗中，DBI的正確率最高，為80%，而其他4個指標中，最高為XB正確率60%，其他均只有40%。

4 結論與展望

現有的聚類算法通常都需要用戶根據經驗知識提供輸入參數，如聚類數，但通常情況下這事先無法確定。使得在實際應用中，用戶對于聚類分析的結果無法進行正確的選擇。本文提出了一種新的確定最佳聚類數的有效性指標，該指標著重于分析簇的幾何結構，從數據對象分布密度的角度來度量類內緊密度與類間分離度。該指標對噪聲不敏感并且可以識別數據集中的子簇群，在實際數據和合成數據上的實驗結果表明，新指標的性能優于廣泛使用的其他指標，對于聚類分析的實際應用提供了一定的參考。

參考文獻

[1] 陳黎飛，姜青山，王聲瑞，基于層次劃分的最佳聚類數確定方法，軟件學報，(19):1， 2008， pp.62-72.

[2] 楊燕，靳蕃，K. Mohamed，聚類有效性評價綜述，計算機應用研究，(25):6， 2008， pp.1630-1632.

[3]A. K. Jain and R. C. Dubes， Algorithms for clustering data. Upper Saddle River， NJ， USA: Prentice-Hall， Inc.， 1988.

[4] 楊善林，李永森，胡笑旋，等，K-means算法中的k值優化問題研究，系統工程理論與實踐，2006(2):97-101.

[5] P.N. Tan， M. Steinbach， and V. Kumar， Introduction to Data Mining. USA: Addison-Wesley Longman， Inc.， 2005.

[6] 周世兵，徐振源，唐旭清，新的K-均值算法最佳聚類數確定方法，計算機工程與應用，46(16)， 2010， pp.27-31.

[7] D. Davies and D. Bouldin， “A cluster separation measure，” IEEE PAMI， vol. 1， no. 2， pp. 224–227， 1979.

[8] T. Calinski and J. Harabasz， “A dendrite method for cluster analysis，” Comm. in Statistics， vol. 3， no. 1， pp. 1–27， 1974.

[9] X. L. Xie and G. Beni， “A validity measure for fuzzy clustering，” IEEE PAMI， vol. 13， no. 8， pp. 841–847， 1991.

[10] M. Halkidi， M. Vazirgiannis， and Y. Batistakis， “Quality scheme assessment in the clustering process，” in PKDD， London， UK， 2000， pp. 265–276

作者簡介

劉燕馳，男，江西吉安人，博士研究生，主要研究方向：數據挖掘，智能數據分析。.