基于層次的Ｋ均值聚類

摘 要：介紹一種基于層次的K均值聚類算法(HKMA)。在統計力學的基礎上，對傳統K均值聚類劃分矩陣里的元素(“隸屬”概率)做了形式上的改變，并引入一個調控實際聚類數目的因子。這樣，在對同一組數據集進行聚類時，調控因子值不同，結果得到的類數目就不同。用一組二維正態分布的數據集和一組用來測試聚類算法的標準數據集(Iris數)進行測試，結果表明該算法具有層次聚類的性質和較滿意的聚類精度。

關鍵詞：聚類；代價函數；層次；K均值聚類

中圖分類號：TP391 文獻標識碼：B 文章編號：1004373X(2008)1616303

KMeans Clustering Based on Hiberarchy

ZHANG Shuaiqin，ZHANG Botao

(Institute of Sciences，Information Engineering University，Zhengzhou，450001，China)

Abstract：A Kmeans clustering arithmetic based on hiberarchy is presented.On basis of statistical mechanics，partition matrix element (membership probability) in traditional Kmeans clustering is changed and a lagrange multiplier controlling the clusters number is introduced.Thus，for a given dataset，the result gives different clusters number when the lagrange multiplier is not the same.The method is tested on one synthetic and one real datasets.The result demonstrates hiberarchy feature and precision of arithmetic as expected.

Keywords：clustering;cost function;hiberarchy;Kmeans clustering

1 引 言

聚類是數據分析中的一項重要技術，是眾多科學領域和工程技術中的一項基礎性工作。這種技術被廣泛應用于生物學、天體物理學、模式識別、數據挖掘、計算機圖像處理、最優化問題等。聚類是把d維特征空間中的n個數據點分成k個不同的類，使類內數據點的相似度高、不同類間的數據點的相似度低^［14］。這里的相似在特征空間中表現為距離近，所以距離可以用來對2個數據點進行相似性測度。

K均值聚類是在各個領域用得最多的聚類算法之一。它的主要特點是：對給定的數據集可能存在的類數目需要作出假設；對用來代表某類的類中心需要在迭代計算前做初始化；迭代計算出的類中心容易陷入某些滿足局部最優的值中。可以看出，設定恰當的類數目和初始化合適的類中心是K均值聚類算法中的關鍵。文獻［5］中用基于模糊K均值的分裂算法(FBSA)來確定類數目，文獻［6］中用聚類中心初始化算法(CCIA)來確定初始的類中心，它們都不同程度地提高了聚類精度。這里介紹一種基于層次的K均值聚類(HKMA)。在該算法中，對傳統K均值聚類中劃分矩陣里的元素(“隸屬”概率)做了形式上的改變，同時引入一個調控因子。這里希望通過調控因子來決定聚類結果中的類中心和實際類數目。

2 傳統K均值聚類

2.1 K均值聚類

K均值聚類的首要目標是迭代計算出類中心^［7］。這些類中心是通過最小化下面的代價函數得到的。cost f(P，U)=∑ni=1∑cj=1pijxi-uj.2(1) 這里n是給定數據集的數據點的總個數；c是潛在的類數目；X={x1，x2，…，xn}是特征數據集；U= {u1，u2，…，uc}是類中心集；P=(pij)n×c是一個劃分矩陣(“隸屬”概率集)，其中元素pij是數據點xi屬于由類中心uj代表的類j的成員的概率，對任意的i=1，2，…，n滿足∑cj=1pij=1，對任意的i=1，2，…，n和j=1，2，…，c滿足pij≥0。

最小化代價函數cost f(P，U)可以得到劃分矩陣和代表各個類的類中心的迭代表達式： pij=1 ‖xi-uj‖.2≤‖xi-uk‖.2

0else(2)

uj=∑ni=1pijxi/∑ni=1pij(3) K均值聚類在迭代過程中，c個類中心會不斷移動，以使得代價函數cost f達到最小值。其中迭代的每一步，一個數據點都是確定性地屬于某一類，這由式(2)可以看出。這只是判定一個點屬于某一類的一種方式。事實上，在以距離度量兩點相似性的聚類算法中，一個點屬于某一類是一個隨該點與該類中心距離衰減的函數。基于此，完全可以用模糊劃分矩陣來代替一般劃分矩陣，使一個點以一定概率屬于某一類。這就是模糊K均值聚類。

2.2 模糊K均值聚類

模糊K均值聚類的首要目標也是迭代計算出類中心^［7］。這些類中心通過最小化下面的代價函數得到。cost fb(P，U)=∑ni=1∑cj=1p.bij‖xi-uj‖.2(4) 這里概率上的指數b叫模糊度，是一個用來控制不同類別的混合程度的自由參數。

最小化代價函數Costfb(P，U)可以得到模糊劃分矩陣和各個類中心的迭代表達式：pij=∑ck=1‖xi-uj‖‖xi-uk‖.2b-1.-1if‖xi-uk‖>0

1if‖xi-uj‖=0

0if‖xi-uk‖=0(5)

uj=∑ni=1p.bijxi/∑Ni=1p.bij(6) 模糊K均值聚類與K均值聚類相比有2點不同：一是引入了模糊“隸屬”關系，使一個樣本點以一定概率屬于某一類別，這樣更接近一個事實，即K均值聚類是一種基于距離的聚類方法；二是引入了隸屬度這個自由參數，可以控制不同類別的混合程度，使聚類達到更好的結果。當取b=1，且使P中每一個樣本點屬于某類別的n個概率值中，最大者置為１，其他置為0時，模糊K均值聚類就過渡到了K均值聚類。K均值聚類是模糊K均值聚類的一種近似，一個特例，這也正是模糊K均值比K均值的聚類精度更高的原因。

3 基于層次的K均值聚類(HKMA)

對一個給定類構型的數據集，該類構型的平均總代價(平均總能量)可表示為：\\=∑ni=1∑cj=1pijEij其中: Eij=‖xi-uj‖.2(7)

數據集類構型的信息熵可表示為：H=-∑ni=1∑cj=1pijlog2 pij 這里n是給定數據集的數據點的總個數，c是潛在的類數目；X={x1，x2，…，xn}是特征數據集，U= {u1，u2，…，uc}是類中心集，P=(pij)n×c 是一個模糊劃分矩陣(模糊“隸屬”概率集)，其中元素pij是數據點xi屬于由類中心uj代表的類j的成員概率，對任意的i=1，2，…，n滿足∑cj=1pij=1，對任意的i=1，2，…，n和j=1，2，…，c滿足pij≥0，E=(Eij)n×c是對應于P的代價(能量)矩陣，Eij是數據點xi以概率pij屬于類j的成員時的代價(能量)。

在平均總代價(平均總能量)不變的約束下，為得到信息熵的最大值，對熵函數求導可得吉布斯概率分布：pij=exp(-βEij)Zi(8)其中Zi是數據點xi的配分函數，表達式為：Zi=∑ck=1exp(-βEik)(9) 這里的β是拉格朗日乘子，其值由約束公式(平均總代價不變)來確定。

對一個給定類構型的數據集，可以認為不同的數據點“隸屬”于自己的類的概率是獨立的。這樣總的配分函數可表示為：Z=∏ni=1Zi 由總配分函數可以得到該方法所需要的代價函數(自由能)：

F=-1βln Z

=-1β∑ni=1ln∑cj=1exp-β‖xi-uj‖.2(10)

由式(7)~(8)知模糊劃分矩陣：pij=exp(-β‖xi-uj‖.2)∑ck=1exp(-β‖xi-uk‖.2)(11) 為了使代價函數(自由能)最小，對代價函數求導，得到類中心表達式：uj=∑ni=1xipij/∑ni=1pij(12) 基于層次的K均值聚類算法(HKMA)與傳統的K均值聚類算法相比較，有兩點不同。一是劃分矩陣中元素(“隸屬”概率)的形式發生了變化。數據點間的相似性從原來直接由點到類中心的距離倒數1/dij(或者能量倒數1/Eij)來度量，變為現在的以指數形式exp(-β dij)(或者exp(-βEij))來度量。這樣，“隸屬”概率成為距離的緩變(光滑)函數，使得聚類結果對初始化類中心不再像原來那么敏感，有利于提高聚類精度。二是增加了一項用來調節“隸屬”概率模糊度的調控因子β。當β增大時，“隸屬”概率模糊度降低。事實上，β=0時，各個“隸屬”概率值相同，每個點都等概率地屬于每一類；而當β→∞時，一個點以概率1屬于離自己最近的類中心所代表的那個類，基于層次的K均值聚類退化為傳統的K均值聚類。

原則上，改變設定的類數目，就會改變類中心的個數。然而，當β一定時，卻存在某個類數目臨界值c0，使得c>c0時，結果只能得到c0個不同的類中心，而剩下的c-c0個類中心都重疊在c0個類中心上。這說明β決定著聚類結果中的類中心和實際類數目。在下面的仿真試驗中將會看到這一點。

4 試 驗

4.1 二維正態分布隨機數據集

用正態隨機數產生器產生一個數據集。該數據集由4個子數據集組成，子數據集分別是以(1，1.5)，(1，2.5)，(5，2)和(7，2)為中心的正態分布數。每一個子數據集有160個數據樣本構成。下圖是該數據集在c=6，β分別等于0，0.25，0.95，2.90情況下的聚類結果。其中每一個方框標示一個類中心，代表聚類結果中的一個類。當β=0時，每個數據點都以相同的概率隸屬于每一個類，由公式(8)知道所有類中心相互重疊，都處在數據集的質心上，結果只有一個類(見圖1(a))。當β=0.25時，“隸屬”概率模糊度降低，對距離的依賴加強，原來的一個大類分裂成兩個小類(見圖1(b))。β繼續增加，“隸屬”概率模糊度進一步降低，新的小類分裂成更小的類(見圖1(c)，圖1(d))。這種過程一直進行下去，直到β足夠大(如β →∞)時分裂成設定的類數目c。

4.2 Iris數

Iris數據集共有3類，分別代表鳶尾屬植物(Iris flowers)的3個不同種類：Iris setosa，Iris versicolor和Iris virginica。每一類有50個樣本，總共有150個樣本。每一個樣本通過萼片長度(sepal length)、萼片寬度(sepal width)、花瓣長度(petal length)和花瓣寬度(petal width)四個屬性描述。

用HKMA對Iris數進行聚類，β值不同時結果類數目不同，顯示層次聚類的性質。圖2中上半圖是Iris數的3個種類在第一維和第四維上的投影，在此作為參照圖；下半圖是在β=0.75的情況下對Iris數聚類所得結果在第一維和第四維上的投影。兩圖對照可以看出，150個樣本中只有15個樣本分類錯誤。

圖1 聚類結果圖示 圖2 Iris數在β=0.75時的聚類結果5 結 語

基于層次的K均值聚類(HKMA)，是在統計力學基礎上，借鑒傳統K均值聚類算法改進而來的。該算法配分矩陣元素(“隸屬”概率)的形式提高了聚類的精度，它所特有的調控因子使其具有層次聚類的特性。結果不再像以前那樣由設定的類數目確定類中心，而是由得到的類中心確定實際的類數目。

參 考 文 獻

［1］Domany E.Superparamagnetic Clustering of DataThe Definitive Solution of an IllPosed Problem.Physica A，1999，263:158169.

［2］Blatt M，Wiseman S，Domany E.Superparamagnetic Clustering of Data.Physical Review Letters，1996，76:3 2513 255.

［3］Blatt M，Wiseman S，Domany E.Clustering Data through an Analogy to the Potts Model.Advances in Neural Information Processing System，MIT Press，1996.

［4］Blatt M，Wiseman S，Domany E.Data Clustering Using a Model Granular Magnet\\.Neural Computation，1997(9):1 8051 842.

［5］Haojun Sun，Shengrui Wang，Qingshan Jiang.FCMbased Model Selection Algorithms for Determining the Number of Clusters.Pattern Recognition，2004，37:2 0272 037.

［6］Shehroz S Khan，Amir Ahmad.Cluster Center Initialization Algorithm for Kmeans Clustering.Pattern Recognition Letters，2004，25:1 2931 302.

［7］\\ 迪達.模式分類\\.Duda R O，李宏東，等譯.2版.北京:機械工業出版社，2003.

作者簡介 張帥欽 男，1983年出生，信息工程大學碩士研究生。研究方向為統計識別與聚類分析。

張波濤 教授。

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文