李曉明

本專(zhuān)欄上一期介紹的是分類(lèi)問(wèn)題中的算法，這一期討論聚類(lèi)。

“分類(lèi)”指的是要將一個(gè)未知類(lèi)別的對(duì)象歸到某個(gè)已知類(lèi)別中?！熬垲?lèi)”則是要將若干對(duì)象劃分成幾組，稱(chēng)每一組為一個(gè)類(lèi)別。

在實(shí)際應(yīng)用中，分類(lèi)的類(lèi)別是事先給定的，往往對(duì)應(yīng)某種現(xiàn)實(shí)含義，如網(wǎng)購(gòu)者可能分為“隨性”和“理性”兩個(gè)類(lèi)別，人們大致也知道是什么意思。聚類(lèi)則是本無(wú)類(lèi)，只是根據(jù)對(duì)象之間的某種相似性（也稱(chēng)鄰近程度或距離），將它們分組。例如，有兩個(gè)任務(wù)要完成，于是需要將一群人分成兩組，分別去完成一個(gè)任務(wù)，為了有較高的效率，希望組內(nèi)成員之間關(guān)系較好，配合默契。聚類(lèi)形成的類(lèi)不一定有明顯的外在特征，往往只是根據(jù)事先給定的目標(biāo)類(lèi)數(shù)（如有三個(gè)任務(wù)，就要分成三組），將對(duì)象集合進(jìn)行合理劃分。

所謂“合理”，在這里的原則就是盡量讓同組的成員之間比較相似（距離較近），組間的成員之間距離較遠(yuǎn)（不相似）。一旦分類(lèi)完成后，就可能會(huì)按照不同類(lèi)的某些特征給它們分別命名。

與分類(lèi)一樣，為了聚類(lèi)，對(duì)象之間的相似性（或距離）含義和定義是基礎(chǔ)。在有些應(yīng)用中，對(duì)象兩兩之間的相似性是直接給出的;在更多的應(yīng)用中，相似性則要根據(jù)對(duì)象的特征屬性按照一定的規(guī)則進(jìn)行計(jì)算。下面我們討論兩個(gè)算法。

● 自底向上的分層聚類(lèi)法

想象我們要搞城市群建設(shè)，需要規(guī)劃將一些城市分成幾個(gè)群，群內(nèi)統(tǒng)籌協(xié)調(diào)發(fā)展。一共要分成幾個(gè)群？哪些城市該放在同一個(gè)群里？這是很現(xiàn)實(shí)的問(wèn)題。當(dāng)然，做出這樣的決定取決于許多因素，但其中一個(gè)重要因素就是城市間的空間距離。很難想象同一個(gè)群內(nèi)的城市之間相距很遠(yuǎn)，而相距很近的兩個(gè)城市卻分到了不同群。

表1是六座城市之間的距離矩陣（在搜索引擎中查出來(lái)的數(shù)據(jù)，不一定很準(zhǔn)，這里只是作為例子），如果我們想分成兩個(gè)群，該如何分？分成三個(gè)呢？這就是聚類(lèi)問(wèn)題。我們注意到，在這種背景下，兩個(gè)對(duì)象（城市）之間的相似性或鄰近程度自然地以距離的方式給了出來(lái)。

1967年，Stephen Johnson發(fā)表了一個(gè)針對(duì)這種場(chǎng)景的算法，稱(chēng)為“分層聚類(lèi)法”（hierarchical clustering）。基本思想如下（假設(shè)有n個(gè)對(duì)象，要聚成k類(lèi)）：

（1）初始，每一個(gè)對(duì)象看成是一個(gè)類(lèi)，于是有n個(gè)類(lèi)，類(lèi)和類(lèi)之間的距離由表1那樣的矩陣數(shù)據(jù)給出。

（2）兩兩檢查現(xiàn)有類(lèi)之間的距離，挑出最小的，也就是表1數(shù)據(jù)中最小的（不算對(duì)角線元素，因?yàn)樗鼈兪恰白约旱阶约骸钡木嚯x）。將對(duì)應(yīng)的兩個(gè)類(lèi)合并，具體就是將它們的數(shù)據(jù)“合并到”一行（列）上，刪去另一行（列）。數(shù)據(jù)合并的策略有多種考量，其中一種是取對(duì)應(yīng)兩個(gè)數(shù)的較大值。（注意，現(xiàn)在類(lèi)數(shù)少了一個(gè)，對(duì)應(yīng)表1那種矩陣少了一行一列）

（3）如果已經(jīng)是k類(lèi)了，就結(jié)束;否則返回（2）。

我們以表1為例，初始6個(gè)類(lèi)，考慮k=3，也就是要聚為3類(lèi)，來(lái)模擬算法的運(yùn)行。核心是算法的第（2）步。由于數(shù)據(jù)矩陣的對(duì)稱(chēng)性，觀察的時(shí)候只需考慮上三角。為簡(jiǎn)單清楚起見(jiàn)，更新的時(shí)候則統(tǒng)一處理。

首先，看到表1上三角中最小的數(shù)是160，即南京和合肥之間的距離。它位于第1行第6列。按照算法，應(yīng)該將南京與合肥聚成一類(lèi)，同時(shí)合并它們的數(shù)據(jù)，對(duì)應(yīng)矩陣數(shù)據(jù)的更新。我們?nèi)≥^大值方案，并讓第6行（列）向第1行（列）合并，就得到表2所示的結(jié)果。發(fā)生了更新的數(shù)據(jù)由下畫(huà)線標(biāo)示?，F(xiàn)在是5個(gè)類(lèi)，比初始減少了一個(gè)。其中加下畫(huà)線顯示的數(shù)就是取較大值更新的結(jié)果。

繼續(xù)，看到最小的數(shù)是202，上海與杭州之間的距離，位于第2行第3列。將它們合并為一類(lèi)，并讓第3行（列）向第2行（列）合并，就得到表3所示的結(jié)果。這一次，除了對(duì)角線上的數(shù)據(jù)外，第2行的其他數(shù)據(jù)恰好沒(méi)有變化?，F(xiàn)在就是4類(lèi)了。

再來(lái)一輪，看到第3行第4列的358最小，讓第4行（列）向第3行（列）合并，就得到下頁(yè)表4（a）所示的結(jié)果。這就是聚成3類(lèi)了，達(dá)到了預(yù)定目標(biāo)。

若需要，還可以在這個(gè)基礎(chǔ)上繼續(xù)，得到聚為2類(lèi)的結(jié)果如下頁(yè)表4（b）所示。

如果能把這個(gè)例子跟蹤下來(lái)，相信讀者一定就掌握了這個(gè)算法的要領(lǐng)。

這個(gè)算法的聚類(lèi)效果如何？看這個(gè)例子，似乎還不錯(cuò)。但要意識(shí)到，像許多機(jī)器學(xué)習(xí)算法一樣，效果沒(méi)有一個(gè)“金標(biāo)準(zhǔn)”度量，而是與數(shù)據(jù)集和應(yīng)用目的有關(guān)。因而，這類(lèi)算法常常包含一些啟發(fā)式，用以根據(jù)具體情況斟酌采用。對(duì)S.C. Johnson算法而言，啟發(fā)式的體現(xiàn)就在于算法第（2）步中的數(shù)據(jù)合并策略。我們例子中用的是“較大值”，其他策略還有“較小值”“平均值”等。建議讀者思考體會(huì)這幾種策略的“物理意義”，從而在應(yīng)用中可以有針對(duì)性地選用。

這個(gè)算法的時(shí)間效率如何？如果任務(wù)是要把n個(gè)對(duì)象聚成k類(lèi)，每一輪找到最小的數(shù)是主要操作，總起來(lái)就是O（（n-k）*n2）。

● K-means

下面討論另一個(gè)聚類(lèi)算法——K-means（K均值）算法，也是現(xiàn)在大數(shù)據(jù)聚類(lèi)中比較流行的算法，其中的K是預(yù)先給定的要形成的類(lèi)數(shù)。作為一個(gè)例子，考慮有若干數(shù)據(jù)點(diǎn)（不妨認(rèn)為它們代表一些人的年齡），并將其放到數(shù)軸上，如下頁(yè)圖1所示。

設(shè)想要把它們分成4組，每一組內(nèi)的人的年齡比較相近，以便談話(huà)更有共同語(yǔ)言。怎么分合適呢？就這個(gè)例子而言，乍一看這個(gè)圖，可能還真有點(diǎn)為難。頭3個(gè)為一組，接著7個(gè)為一組，再接著6個(gè)為一組，后面4個(gè)為一組？還真不見(jiàn)得。

這個(gè)例子數(shù)據(jù)，每個(gè)數(shù)據(jù)點(diǎn)就一個(gè)值，稱(chēng)之為1維數(shù)據(jù)。而在實(shí)際中常見(jiàn)的是多維數(shù)據(jù)。例如，圖2是一個(gè)二維數(shù)據(jù)點(diǎn)集的情形。如果要把它們聚成2類(lèi)，似乎有很直觀的結(jié)果，3類(lèi)也行，4類(lèi)就不太好說(shuō)了。讀者還可以想到，如果數(shù)據(jù)的維數(shù)>2，情況會(huì)變得更加復(fù)雜①，而且不太可能有視覺(jué)直觀。

無(wú)論數(shù)據(jù)的維度如何，如前所述，數(shù)據(jù)之間的距離都是聚類(lèi)算法的基礎(chǔ)。在前面討論分層聚類(lèi)法的例子中，我們直接用城市間的空間距離作為距離。在本專(zhuān)欄上一期討論分類(lèi)的時(shí)候，我們談到了不同的應(yīng)用背景有不同的距離、如歐式距離、曼哈頓距離，余弦距離等，此處不再贅述。

下面以二維為例進(jìn)行算法討論，其思想也可以用于多維。后面的運(yùn)行例為簡(jiǎn)單起見(jiàn)，則采用上面的年齡數(shù)據(jù)（一維）。

1.問(wèn)題

給定一個(gè)二維數(shù)據(jù)集合D={x，y，…}和希望聚成的類(lèi)別數(shù)K，要將那些數(shù)據(jù)分成K組，使得每一組內(nèi)的數(shù)據(jù)點(diǎn)較近，而組間數(shù)據(jù)點(diǎn)的距離較遠(yuǎn)。假設(shè)采用歐式距離。

稍為仔細(xì)一點(diǎn)讀這個(gè)問(wèn)題描述，會(huì)感到它只是表達(dá)了一個(gè)宏觀的愿望，細(xì)節(jié)要求并沒(méi)有說(shuō)清楚?！拜^近”和“較遠(yuǎn)”的具體比較對(duì)象是什么呢？以圖2為例，若聚成3類(lèi)，無(wú)論怎么聚，不同類(lèi)邊界上兩個(gè)點(diǎn)的距離都有可能比類(lèi)中兩個(gè)點(diǎn)的距離更近。那豈不是說(shuō)這個(gè)問(wèn)題沒(méi)法解決？

為此，我們需要讓那種宏觀的愿望具有可操作性，明確“類(lèi)中數(shù)據(jù)點(diǎn)較近”和“類(lèi)間數(shù)據(jù)點(diǎn)較遠(yuǎn)”的具體含義。注意到由于有了距離的概念，我們就可以談?wù)撘唤M數(shù)據(jù)的“中心”，如一維空間中兩個(gè)數(shù)的中心就是它們的均值，二維空間中兩個(gè)數(shù)據(jù)點(diǎn)的中心就是它們連線的中點(diǎn)，等等。而如果有多個(gè)中心，就可以談?wù)撘粋€(gè)數(shù)據(jù)點(diǎn)離哪一個(gè)更近。K-means就是從初始給定的數(shù)據(jù)點(diǎn)集合出發(fā)，對(duì)K個(gè)不同中心的確定和數(shù)據(jù)點(diǎn)歸屬關(guān)系進(jìn)行迭代，最終形成K個(gè)數(shù)據(jù)類(lèi)別的算法。

2.算法思路

在K-means算法中，K表示類(lèi)別數(shù)，means表示均值。意指聚類(lèi)過(guò)程將數(shù)據(jù)集分成了K類(lèi)，每一類(lèi)中的數(shù)據(jù)點(diǎn)都離它們的中心（亦稱(chēng)質(zhì)心）更近，離其他的中心較遠(yuǎn)。

“中心”，在本文的討論中就是一個(gè)虛擬的數(shù)據(jù)點(diǎn)，其坐標(biāo)為它所代表的數(shù)據(jù)集中數(shù)據(jù)點(diǎn)坐標(biāo)的平均值。如果是兩個(gè)點(diǎn)，如x=（1，2），y=（4，6），其中心就是（（1+4）/2，（2+6）/2）=（2.5，4）;如果是三個(gè)點(diǎn)，如x=（1，2），y=（4，6），z=（4，4），其中心就是（（1+4+4）/3，（2+6+4）/3） =（3，4）;等等。一般地，n個(gè)點(diǎn)，d1=（x1，y1），…，dn=（xn，yn），中心就是：

K-means算法，就是基于待聚類(lèi)的數(shù)據(jù)，迭代尋找中心的過(guò)程。它根據(jù)預(yù)設(shè)的類(lèi)別數(shù)K，為每個(gè)類(lèi)別設(shè)定一個(gè)初始中心（可以隨機(jī)產(chǎn)生），然后按照離它們距離的遠(yuǎn)近，將數(shù)據(jù)做歸屬劃分。一旦有了數(shù)據(jù)劃分，反過(guò)來(lái)就可以計(jì)算它們的中心，然后再按數(shù)據(jù)離新中心的遠(yuǎn)近對(duì)數(shù)據(jù)做重新劃分。如此反復(fù)，直到中心不再改變。屆時(shí)，就達(dá)到了每個(gè)數(shù)據(jù)點(diǎn)都離所在類(lèi)的中心最近的目標(biāo)。

3.算法描述（如圖3）

4.算法運(yùn)行例

二維數(shù)據(jù)作為手工呈現(xiàn)的例子會(huì)比較煩瑣。我們不妨利用前面的一維年齡數(shù)據(jù)例子，體會(huì)一下過(guò)程。

5，10，13，21，23，24，25，39，41，42，52，55，58，59，61，62，72，79，82，92

根據(jù)題意，K=4，隨機(jī)設(shè)初始中心為10，30，50，70。注意，它們不需要屬于初始數(shù)據(jù)點(diǎn)集。

以距離最近為原則，將20個(gè)數(shù)據(jù)點(diǎn)做第一次劃分，如表5（a）所示，而根據(jù)劃分得到的新中心如表5（b）所示。

然后以這些中心為參照，將所有數(shù)據(jù)按離新中心的距離重新劃分（看到先前第4類(lèi)中有些數(shù)據(jù)跑到第3類(lèi)了），得到新的4個(gè)類(lèi)別：{5，10，13}，{21，23，24，25，39}，{41，42，52，55，58，59，61，62}，{72，79，82，92}。

再計(jì)算中心，前兩個(gè)不變，第3個(gè)成為（41+42+52+55+58+59+61+62）/8=53.75，第4個(gè)變成（72+79+82+92）/4=81.25。按它們?cè)賱澐謹(jǐn)?shù)據(jù)，發(fā)現(xiàn)沒(méi)有引起變化，K-means聚類(lèi)過(guò)程完成！我們清楚地看到了中心的確定和類(lèi)別劃分之間的相互“迭代”。上述過(guò)程也可以用下頁(yè)表6來(lái)表示。

5.算法分析

K-means算法是經(jīng)典的聚類(lèi)算法，上一輪的結(jié)果作為新一輪計(jì)算的開(kāi)始值，直至前后兩輪計(jì)算的結(jié)果落在一個(gè)誤差范圍中，即趨于穩(wěn)定。這里要關(guān)心的基本問(wèn)題就是它是否能趨于穩(wěn)定，也就是其中|new_centers-centers|是否能變得小于一個(gè)任意設(shè)定的門(mén)檻值threshold，即“收斂”。否則，這算法就會(huì)無(wú)窮無(wú)盡地執(zhí)行下去。數(shù)學(xué)理論告訴我們，收斂會(huì)發(fā)生。盡管我們不需要懂得證明，但懂得這是需要關(guān)心的事情是算法素養(yǎng)的要求。

也許我們覺(jué)得還應(yīng)該從收斂時(shí)聚類(lèi)結(jié)果是否合理來(lái)討論正確性，也就是“到底聚對(duì)沒(méi)有”？但這通常會(huì)比較主觀，與應(yīng)用背景有關(guān)。以上述一維數(shù)據(jù)為例，如果將它們看成是年齡，我們腦子里事先已經(jīng)有了少年、青年、中年、老年這樣幾個(gè)背景概念，也許你會(huì)覺(jué)得若41和42在第2類(lèi)會(huì)更加合理。但如果那些數(shù)據(jù)有不同的含義，就不一定了。由于算法是不理解數(shù)據(jù)的含義的，它只負(fù)責(zé)類(lèi)中心的收斂（數(shù)學(xué)上嚴(yán)格的，也符合實(shí)際中關(guān)于聚類(lèi)的一些直覺(jué)）。在這個(gè)意義上，它就是正確的。至于它在某個(gè)具體問(wèn)題上是否合適，則需要在特定應(yīng)用背景下的實(shí)踐來(lái)檢驗(yàn)了。不過(guò)，取決于初值的選取，盡管都會(huì)收斂，但結(jié)果類(lèi)中心不是唯一的，可能造成數(shù)據(jù)集劃分的不同。這也需要在實(shí)際應(yīng)用中注意。

從執(zhí)行效率看，算法是一個(gè)兩重循環(huán)。內(nèi)層循環(huán)就是對(duì)數(shù)據(jù)集的兩次遍歷，一次做劃分（在K個(gè)類(lèi)中心中選取最近的），一次計(jì)算新的中心。外層循環(huán)執(zhí)行的次數(shù)與類(lèi)中心初值的選取有關(guān)。假設(shè)N為樣本數(shù)據(jù)量，K為類(lèi)別數(shù)，M為外層循環(huán)的迭代次數(shù)，算法復(fù)雜性就是O（M*N*K）。

由上述討論可見(jiàn)，K-means算法的時(shí)間開(kāi)銷(xiāo)除了與數(shù)據(jù)樣本數(shù)、聚類(lèi)的類(lèi)別數(shù)有關(guān)外，初始聚類(lèi)中心的選擇對(duì)聚類(lèi)結(jié)果也有較大的影響，一旦初始值選擇得不好，不僅會(huì)影響收斂速度，而且可能無(wú)法得到有意義的聚類(lèi)結(jié)果。由此可見(jiàn)，聚類(lèi)算法的效率和質(zhì)量不僅僅是計(jì)算機(jī)算法的問(wèn)題，對(duì)要解決的問(wèn)題本身的了解和經(jīng)驗(yàn)也是重要的因素。

當(dāng)然，當(dāng)我們對(duì)要處理的問(wèn)題不夠了解時(shí)，可以用隨機(jī)數(shù)作為初始中心，還可以用不同的類(lèi)別數(shù)對(duì)同一數(shù)據(jù)集合做多次嘗試，與熟悉應(yīng)用背景的專(zhuān)業(yè)人士合作，解讀、解釋有關(guān)數(shù)據(jù)，最終確定合適的類(lèi)別數(shù)，預(yù)設(shè)中心的初始值。

釋?zhuān)?①所謂“維數(shù)”，指的是數(shù)據(jù)對(duì)象特征的個(gè)數(shù)。在人工智能應(yīng)用中，維數(shù)可能達(dá)到成千上萬(wàn)。

參考文獻(xiàn)：

[1]S.C.Johnson.Hierarchical Clustering Schemes[J].Psychometrika，1967（02）：241-254.

[2]Anil K. Jain.Data clustering：50 years beyond K-means[J].Pattern Recognition Letters，2009.

注：作者系北京大學(xué)計(jì)算機(jī)系原系主任。