摘 要：介紹一種基于層次的K均值聚類(lèi)算法(HKMA)。在統(tǒng)計(jì)力學(xué)的基礎(chǔ)上，對(duì)傳統(tǒng)K均值聚類(lèi)劃分矩陣?yán)锏脑?“隸屬”概率)做了形式上的改變，并引入一個(gè)調(diào)控實(shí)際聚類(lèi)數(shù)目的因子。這樣，在對(duì)同一組數(shù)據(jù)集進(jìn)行聚類(lèi)時(shí)，調(diào)控因子值不同，結(jié)果得到的類(lèi)數(shù)目就不同。用一組二維正態(tài)分布的數(shù)據(jù)集和一組用來(lái)測(cè)試聚類(lèi)算法的標(biāo)準(zhǔn)數(shù)據(jù)集(Iris數(shù))進(jìn)行測(cè)試，結(jié)果表明該算法具有層次聚類(lèi)的性質(zhì)和較滿(mǎn)意的聚類(lèi)精度。

關(guān)鍵詞：聚類(lèi)；代價(jià)函數(shù)；層次；K均值聚類(lèi)

中圖分類(lèi)號(hào)：TP391 文獻(xiàn)標(biāo)識(shí)碼：B 文章編號(hào)：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 引 言

聚類(lèi)是數(shù)據(jù)分析中的一項(xiàng)重要技術(shù)，是眾多科學(xué)領(lǐng)域和工程技術(shù)中的一項(xiàng)基礎(chǔ)性工作。這種技術(shù)被廣泛應(yīng)用于生物學(xué)、天體物理學(xué)、模式識(shí)別、數(shù)據(jù)挖掘、計(jì)算機(jī)圖像處理、最優(yōu)化問(wèn)題等。聚類(lèi)是把d維特征空間中的n個(gè)數(shù)據(jù)點(diǎn)分成k個(gè)不同的類(lèi)，使類(lèi)內(nèi)數(shù)據(jù)點(diǎn)的相似度高、不同類(lèi)間的數(shù)據(jù)點(diǎn)的相似度低^［14］。這里的相似在特征空間中表現(xiàn)為距離近，所以距離可以用來(lái)對(duì)2個(gè)數(shù)據(jù)點(diǎn)進(jìn)行相似性測(cè)度。

K均值聚類(lèi)是在各個(gè)領(lǐng)域用得最多的聚類(lèi)算法之一。它的主要特點(diǎn)是：對(duì)給定的數(shù)據(jù)集可能存在的類(lèi)數(shù)目需要作出假設(shè)；對(duì)用來(lái)代表某類(lèi)的類(lèi)中心需要在迭代計(jì)算前做初始化；迭代計(jì)算出的類(lèi)中心容易陷入某些滿(mǎn)足局部最優(yōu)的值中?？梢钥闯觯O(shè)定恰當(dāng)?shù)念?lèi)數(shù)目和初始化合適的類(lèi)中心是K均值聚類(lèi)算法中的關(guān)鍵。文獻(xiàn)［5］中用基于模糊K均值的分裂算法(FBSA)來(lái)確定類(lèi)數(shù)目，文獻(xiàn)［6］中用聚類(lèi)中心初始化算法(CCIA)來(lái)確定初始的類(lèi)中心，它們都不同程度地提高了聚類(lèi)精度。這里介紹一種基于層次的K均值聚類(lèi)(HKMA)。在該算法中，對(duì)傳統(tǒng)K均值聚類(lèi)中劃分矩陣?yán)锏脑?“隸屬”概率)做了形式上的改變，同時(shí)引入一個(gè)調(diào)控因子。這里希望通過(guò)調(diào)控因子來(lái)決定聚類(lèi)結(jié)果中的類(lèi)中心和實(shí)際類(lèi)數(shù)目。

2 傳統(tǒng)K均值聚類(lèi)

2.1 K均值聚類(lèi)

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

最小化代價(jià)函數(shù)cost f(P，U)可以得到劃分矩陣和代表各個(gè)類(lèi)的類(lèi)中心的迭代表達(dá)式： 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均值聚類(lèi)在迭代過(guò)程中，c個(gè)類(lèi)中心會(huì)不斷移動(dòng)，以使得代價(jià)函數(shù)cost f達(dá)到最小值。其中迭代的每一步，一個(gè)數(shù)據(jù)點(diǎn)都是確定性地屬于某一類(lèi)，這由式(2)可以看出。這只是判定一個(gè)點(diǎn)屬于某一類(lèi)的一種方式。事實(shí)上，在以距離度量?jī)牲c(diǎn)相似性的聚類(lèi)算法中，一個(gè)點(diǎn)屬于某一類(lèi)是一個(gè)隨該點(diǎn)與該類(lèi)中心距離衰減的函數(shù)?；诖耍耆梢杂媚：齽澐志仃噥?lái)代替一般劃分矩陣，使一個(gè)點(diǎn)以一定概率屬于某一類(lèi)。這就是模糊K均值聚類(lèi)。

2.2 模糊K均值聚類(lèi)

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

最小化代價(jià)函數(shù)Costfb(P，U)可以得到模糊劃分矩陣和各個(gè)類(lèi)中心的迭代表達(dá)式：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均值聚類(lèi)與K均值聚類(lèi)相比有2點(diǎn)不同：一是引入了模糊“隸屬”關(guān)系，使一個(gè)樣本點(diǎn)以一定概率屬于某一類(lèi)別，這樣更接近一個(gè)事實(shí)，即K均值聚類(lèi)是一種基于距離的聚類(lèi)方法；二是引入了隸屬度這個(gè)自由參數(shù)，可以控制不同類(lèi)別的混合程度，使聚類(lèi)達(dá)到更好的結(jié)果。當(dāng)取b=1，且使P中每一個(gè)樣本點(diǎn)屬于某類(lèi)別的n個(gè)概率值中，最大者置為１，其他置為0時(shí)，模糊K均值聚類(lèi)就過(guò)渡到了K均值聚類(lèi)。K均值聚類(lèi)是模糊K均值聚類(lèi)的一種近似，一個(gè)特例，這也正是模糊K均值比K均值的聚類(lèi)精度更高的原因。

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

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

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

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

對(duì)一個(gè)給定類(lèi)構(gòu)型的數(shù)據(jù)集，可以認(rèn)為不同的數(shù)據(jù)點(diǎn)“隸屬”于自己的類(lèi)的概率是獨(dú)立的。這樣總的配分函數(shù)可表示為：Z=∏ni=1Zi 由總配分函數(shù)可以得到該方法所需要的代價(jià)函數(shù)(自由能)：

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) 為了使代價(jià)函數(shù)(自由能)最小，對(duì)代價(jià)函數(shù)求導(dǎo)，得到類(lèi)中心表達(dá)式：uj=∑ni=1xipij/∑ni=1pij(12) 基于層次的K均值聚類(lèi)算法(HKMA)與傳統(tǒng)的K均值聚類(lèi)算法相比較，有兩點(diǎn)不同。一是劃分矩陣中元素(“隸屬”概率)的形式發(fā)生了變化。數(shù)據(jù)點(diǎn)間的相似性從原來(lái)直接由點(diǎn)到類(lèi)中心的距離倒數(shù)1/dij(或者能量倒數(shù)1/Eij)來(lái)度量，變?yōu)楝F(xiàn)在的以指數(shù)形式exp(-β dij)(或者exp(-βEij))來(lái)度量。這樣，“隸屬”概率成為距離的緩變(光滑)函數(shù)，使得聚類(lèi)結(jié)果對(duì)初始化類(lèi)中心不再像原來(lái)那么敏感，有利于提高聚類(lèi)精度。二是增加了一項(xiàng)用來(lái)調(diào)節(jié)“隸屬”概率模糊度的調(diào)控因子β。當(dāng)β增大時(shí)，“隸屬”概率模糊度降低。事實(shí)上，β=0時(shí)，各個(gè)“隸屬”概率值相同，每個(gè)點(diǎn)都等概率地屬于每一類(lèi)；而當(dāng)β→∞時(shí)，一個(gè)點(diǎn)以概率1屬于離自己最近的類(lèi)中心所代表的那個(gè)類(lèi)，基于層次的K均值聚類(lèi)退化為傳統(tǒng)的K均值聚類(lèi)。

原則上，改變?cè)O(shè)定的類(lèi)數(shù)目，就會(huì)改變類(lèi)中心的個(gè)數(shù)。然而，當(dāng)β一定時(shí)，卻存在某個(gè)類(lèi)數(shù)目臨界值c0，使得c>c0時(shí)，結(jié)果只能得到c0個(gè)不同的類(lèi)中心，而剩下的c-c0個(gè)類(lèi)中心都重疊在c0個(gè)類(lèi)中心上。這說(shuō)明β決定著聚類(lèi)結(jié)果中的類(lèi)中心和實(shí)際類(lèi)數(shù)目。在下面的仿真試驗(yàn)中將會(huì)看到這一點(diǎn)。

4 試 驗(yàn)

4.1 二維正態(tài)分布隨機(jī)數(shù)據(jù)集

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

4.2 Iris數(shù)

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

用HKMA對(duì)Iris數(shù)進(jìn)行聚類(lèi)，β值不同時(shí)結(jié)果類(lèi)數(shù)目不同，顯示層次聚類(lèi)的性質(zhì)。圖2中上半圖是Iris數(shù)的3個(gè)種類(lèi)在第一維和第四維上的投影，在此作為參照?qǐng)D；下半圖是在β=0.75的情況下對(duì)Iris數(shù)聚類(lèi)所得結(jié)果在第一維和第四維上的投影。兩圖對(duì)照可以看出，150個(gè)樣本中只有15個(gè)樣本分類(lèi)錯(cuò)誤。

圖1 聚類(lèi)結(jié)果圖示 圖2 Iris數(shù)在β=0.75時(shí)的聚類(lèi)結(jié)果5 結(jié) 語(yǔ)

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

參 考 文 獻(xiàn)

［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］\\ 迪達(dá).模式分類(lèi)\\.Duda R O，李宏?yáng)|，等譯.2版.北京:機(jī)械工業(yè)出版社，2003.

作者簡(jiǎn)介 張帥欽 男，1983年出生，信息工程大學(xué)碩士研究生。研究方向?yàn)榻y(tǒng)計(jì)識(shí)別與聚類(lèi)分析。

張波濤 教授。

注：本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文