聚類問題中的算法

聚類問題中的算法“分類”指的是要將一個(gè)未知類別的對(duì)象歸到某個(gè)已知類別中。“聚類”則是要將若干對(duì)象劃分成幾組，稱每一組為一個(gè)類別。在實(shí)際應(yīng)用中，分類的類別是事先給定的，往往對(duì)應(yīng)某種現(xiàn)實(shí)含義，如網(wǎng)購者可能分為“隨性”和“理性”兩個(gè)類別，人們大致也知道是什么意思。聚類則是本無類，只是根據(jù)對(duì)象之間的某種相似性（也稱鄰近程度或距離），將它們分組。例如，有兩個(gè)任務(wù)要完成，于是需要將一群人分成兩組，分別去完成一個(gè)任務(wù)，為了有較高的效率，希望組內(nèi)成員之間關(guān)系較好，配合默契。聚類形成的類不一定有明顯的外在特征，往往只是根據(jù)事先給定的目標(biāo)類數(shù)（如有三個(gè)任務(wù)，就要分成三組），將對(duì)象集合進(jìn)行合理劃分。所謂“合理”，在這里的原則就是盡量讓同組的成員之間比較相似（距離較近），組間的成員之間距離較遠(yuǎn)（不相似）。一旦分類完成后，就可能會(huì)按照不同類的某些特征給它們分別命名。與分類一樣，為了聚類，對(duì)象之間的相似性（或距離）含義和定義是基礎(chǔ)。在有些應(yīng)用中，對(duì)象兩兩之間的相似性是直接給出的;在更多的應(yīng)用中，相似性則要根據(jù)對(duì)象的特征屬性按照一定的規(guī)則進(jìn)行計(jì)算。下面我們討論兩個(gè)算法?！褡缘紫蛏系姆謱泳垲惙ㄏ胂笪覀円愠鞘腥航ㄔO(shè)，需要規(guī)劃將一些城市分成幾個(gè)群，群內(nèi)統(tǒng)籌協(xié)調(diào)發(fā)展。一共要分成幾個(gè)群？哪些城市該放在同一個(gè)群里？這是很現(xiàn)實(shí)的問題。當(dāng)然，做出這樣的決定取決于許多因素，但其中一個(gè)重要因素就是城市間的空間距離。很難想象同一個(gè)群內(nèi)的城市之間相距很遠(yuǎn)，而相距很近的兩個(gè)城市卻分到了不同群。表1是六座城市之間的距離矩陣（在搜索引擎中查出來的數(shù)據(jù)，不一定很準(zhǔn)，這里只是作為例子），如果我們想分成兩個(gè)群，該如何分？分成三個(gè)呢？這就是聚類問題。我們注意到，在這種背景下，兩個(gè)對(duì)象（城市）之間的相似性或鄰近程度自然地以距離的方式給了出來。（1）初始，每一個(gè)對(duì)象看成是一個(gè)類，于是有n個(gè)類，類和類之間的距離由表1那樣的矩陣數(shù)據(jù)給出。（2）兩兩檢查現(xiàn)有類之間的距離，挑出最小的，也就是表1數(shù)據(jù)中最小的（不算對(duì)角線元素，因?yàn)樗鼈兪恰白约旱阶约骸钡木嚯x）。將對(duì)應(yīng)的兩個(gè)類合并，具體就是將它們的數(shù)據(jù)“合并到”一行（列）上，刪去另一行（列）。數(shù)據(jù)合并的策略有多種考量，其中一種是取對(duì)應(yīng)兩個(gè)數(shù)的較大值。（注意，現(xiàn)在類數(shù)少了一個(gè)，對(duì)應(yīng)表1那種矩陣少了一行一列）（3）如果已經(jīng)是k類了，就結(jié)束;否則返回（2）。我們以表1為例，初始6個(gè)類，考慮k=3，也就是要聚為3類，來模擬算法的運(yùn)行。核心是算法的第（2）步。由于數(shù)據(jù)矩陣的對(duì)稱性，觀察的時(shí)候只需考慮上三角。為簡單清楚起見，更新的時(shí)候則統(tǒng)一處理。首先，看到表1上三角中最小的數(shù)是160，即南京和合肥之間的距離。它位于第1行第6列。按照算法，應(yīng)該將南京與合肥聚成一類，同時(shí)合并它們的數(shù)據(jù)，對(duì)應(yīng)矩陣數(shù)據(jù)的更新。我們?nèi)≥^大值方案，并讓第6行（列）向第1行（列）合并，就得到表2所示的結(jié)果。發(fā)生了更新的數(shù)據(jù)由下畫線標(biāo)示?，F(xiàn)在是5個(gè)類，比初始減少了一個(gè)。其中加下畫線顯示的數(shù)就是取較大值更新的結(jié)果。繼續(xù)，看到最小的數(shù)是202，上海與杭州之間的距離，位于第2行第3列。將它們合并為一類，并讓第3行（列）向第2行（列）合并，就得到表3所示的結(jié)果。這一次，除了對(duì)角線上的數(shù)據(jù)外，第2行的其他數(shù)據(jù)恰好沒有變化?，F(xiàn)在就是4類了。再來一輪，看到第3行第4列的358最小，讓第4行（列）向第3行（列）合并，就得到下頁表4（a）所示的結(jié)果。這就是聚成3類了，達(dá)到了預(yù)定目標(biāo)。若需要，還可以在這個(gè)基礎(chǔ)上繼續(xù)，得到聚為2類的結(jié)果如下頁表4（b）所示。如果能把這個(gè)例子跟蹤下來，相信讀者一定就掌握了這個(gè)算法的要領(lǐng)。這個(gè)算法的聚類效果如何？看這個(gè)例子，似乎還不錯(cuò)。但要意識(shí)到，像許多機(jī)器學(xué)習(xí)算法一樣，效果沒有一個(gè)“金標(biāo)準(zhǔn)”度量，而是與數(shù)據(jù)集和應(yīng)用目的有關(guān)。因而，這類算法常常包含一些啟發(fā)式，用以根據(jù)具體情況斟酌采用。對(duì)S.C.Johnson算法而言，啟發(fā)式的體現(xiàn)就在于算法第（2）步中的數(shù)據(jù)合并策略。我們例子中用的是“較大值”，其他策略還有“較小值”“平均值”等。建議讀者思考體會(huì)這幾種策略的“物理意義”，從而在應(yīng)用中可以有針對(duì)性地選用。這個(gè)算法的時(shí)間效率如何？如果任務(wù)是要把n個(gè)對(duì)象聚成k類，每一輪找到最小的數(shù)是主要操作，總起來就是O（（n-k）*n2）?！馣-means這個(gè)例子數(shù)據(jù)，每個(gè)數(shù)據(jù)點(diǎn)就一個(gè)值，稱之為1維數(shù)據(jù)。而在實(shí)際中常見的是多維數(shù)據(jù)。例如，圖2是一個(gè)二維數(shù)據(jù)點(diǎn)集的情形。如果要把它們聚成2類，似乎有很直觀的結(jié)果，3類也行，4類就不太好說了。讀者還可以想到，如果數(shù)據(jù)的維數(shù)>2，情況會(huì)變得更加復(fù)雜①，而且不太可能有視覺直觀。給定一個(gè)二維數(shù)據(jù)集合D={x，y，…}和希望聚成的類別數(shù)K，要將那些數(shù)據(jù)分成K組，使得每一組內(nèi)的數(shù)據(jù)點(diǎn)較近，而組間數(shù)據(jù)點(diǎn)的距離較遠(yuǎn)。假設(shè)采用歐式距離。稍為仔細(xì)一點(diǎn)讀這個(gè)問題描述，會(huì)感到它只是表達(dá)了一個(gè)宏觀的愿望，細(xì)節(jié)要求并沒有說清楚?！拜^近”和“較遠(yuǎn)”的具體比較對(duì)象是什么呢？以圖2為例，若聚成3類，無論怎么聚，不同類邊界上兩個(gè)點(diǎn)的距離都有可能比類中兩個(gè)點(diǎn)的距離更近。那豈不是說這個(gè)問題沒法解決？為此，我們需要讓那種宏觀的愿望具有可操作性，明確“類中數(shù)據(jù)點(diǎn)較近”和“類間數(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ù)類別的算法。2.算法思路在K-means算法中，K表示類別數(shù)，means表示均值。意指聚類過程將數(shù)據(jù)集分成了K類，每一類中的數(shù)據(jù)點(diǎn)都離它們的中心（亦稱質(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算法，就是基于待聚類的數(shù)據(jù)，迭代尋找中心的過程。它根據(jù)預(yù)設(shè)的類別數(shù)K，為每個(gè)類別設(shè)定一個(gè)初始中心（可以隨機(jī)產(chǎn)生），然后按照離它們距離的遠(yuǎn)近，將數(shù)據(jù)做歸屬劃分。一旦有了數(shù)據(jù)劃分，反過來就可以計(jì)算它們的中心，然后再按數(shù)據(jù)離新中心的遠(yuǎn)近對(duì)數(shù)據(jù)做重新劃分。如此反復(fù)，直到中心不再改變。屆時(shí)，就達(dá)到了每個(gè)數(shù)據(jù)點(diǎn)都離所在類的中心最近的目標(biāo)。3.算法描述（如圖3）4.算法運(yùn)行例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類中有些數(shù)據(jù)跑到第3類了），得到新的4個(gè)類別：{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)沒有引起變化，K-means聚類過程完成！我們清楚地看到了中心的確定和類別劃分之間的相互“迭代”。上述過程也可以用下頁表6來表示。5.算法分析K-means算法是經(jīng)典的聚類算法，上一輪的結(jié)果作為新一輪計(jì)算的開始值，直至前后兩輪計(jì)算的結(jié)果落在一個(gè)誤差范圍中，即趨于穩(wěn)定。這里要關(guān)心的基本問題就是它是否能趨于穩(wěn)定，也就是其中|new_centers-centers|是否能變得小于一個(gè)任意設(shè)定的門檻值threshold，即“收斂”。否則，這算法就會(huì)無窮無盡地執(zhí)行下去。數(shù)學(xué)理論告訴我們，收斂會(huì)發(fā)生。盡管我們不需要懂得證明，但懂得這是需要關(guān)心的事情是算法素養(yǎng)的要求。從執(zhí)行效率看，算法是一個(gè)兩重循環(huán)。內(nèi)層循環(huán)就是對(duì)數(shù)據(jù)集的兩次遍歷，一次做劃分（在K個(gè)類中心中選取最近的），一次計(jì)算新的中心。外層循環(huán)執(zhí)行的次數(shù)與類中心初值的選取有關(guān)。假設(shè)N為樣本數(shù)據(jù)量，K為類別數(shù)，M為外層循環(huán)的迭代次數(shù)，算法復(fù)雜性就是O（M*N*K）。由上述討論可見，K-means算法的時(shí)間開銷除了與數(shù)據(jù)樣本數(shù)、聚類的類別數(shù)有關(guān)外，初始聚類中心的選擇對(duì)聚類結(jié)果也有較大的影響，一旦初始值選擇得不好，不僅會(huì)影響收斂速度，而且可能無法得到有意義的聚類結(jié)果。由此可見，聚類算法的效率和質(zhì)量不僅僅是計(jì)算機(jī)算法的問題，對(duì)要解決的問題本身的了解和經(jīng)驗(yàn)也是重要的因素。當(dāng)然，當(dāng)我們對(duì)要處理的問題不夠了解時(shí)，可以用隨機(jī)數(shù)作為初始中心，還可以用不同的類別數(shù)對(duì)同一數(shù)據(jù)集合做多次嘗試，與熟悉應(yīng)用背景的專業(yè)人士合作，解讀、解釋有關(guān)數(shù)據(jù)，最終確定合適的類別數(shù)，預(yù)設(shè)中心的初始值。釋：①所謂“維數(shù)”，指的是數(shù)據(jù)對(duì)象特征的個(gè)數(shù)。在人工智能應(yīng)用中，