聚類分析算法概述及其適用性比較

印曉天 湛高峰

摘 要：聚類算法作為大數(shù)據(jù)與人工智能領(lǐng)域重要的分析工具，受到了學(xué)術(shù)界的高度關(guān)注與廣泛研究。本文從算法設(shè)計(jì)思想的角度對(duì)現(xiàn)今主要的聚類算法進(jìn)行了歸納總結(jié)。具體來(lái)講，針對(duì)中心聚類法、層次聚類法、密度聚類法、譜聚類法以及一些其他聚類算法分析了各自算法及其思想的優(yōu)缺點(diǎn)與適用性，對(duì)算法的實(shí)際應(yīng)用建立指導(dǎo)性作用。

關(guān)鍵詞：聚類分析 算法 適用性

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1672-3791（2018）11（c）-0230-03

聚類分析作為機(jī)器學(xué)習(xí)的重要分析手段，是當(dāng)前大數(shù)據(jù)時(shí)代下的熱點(diǎn)研究領(lǐng)域之一。在過(guò)去數(shù)十年間，產(chǎn)生了大量的聚類分析算法。本文對(duì)目前主流的聚類算法進(jìn)行歸納總結(jié)，并對(duì)各自的優(yōu)缺點(diǎn)和適用性進(jìn)行比較分析。

通俗來(lái)講，聚類算法的目標(biāo)是將具有共性的樣本歸為同一類型，而將沒(méi)有或者少有共性的樣本歸為不同類型。數(shù)學(xué)上對(duì)于共性的度量常用樣本之間的距離來(lái)衡量，而如何定義距離則需要根據(jù)實(shí)際情況具體分析。因此，聚類算法的目標(biāo)是得到一系列內(nèi)部聯(lián)系相對(duì)緊密、外部聯(lián)系相對(duì)稀疏的樣本集合（又稱為類簇）。聚類算法按實(shí)現(xiàn)方式，主要可以分為中心聚類、層次聚類、密度聚類、譜聚類等。下面就以上各類型聚類算法逐一介紹。由于本文著重分類介紹算法的思想，旨在分析各類算法的優(yōu)缺點(diǎn)及其適用性，所以在介紹的時(shí)候不會(huì)拘泥于參數(shù)細(xì)節(jié)，而強(qiáng)調(diào)執(zhí)行過(guò)程是如何體現(xiàn)算法思想的。具體的算法實(shí)現(xiàn)過(guò)程可參考相應(yīng)文獻(xiàn)。

1 中心聚類法

中心聚類法是一類極為常見聚類算法。它以找各類簇的中心為基本任務(wù)，將離某中心最近那些點(diǎn)歸為該中心所代表的類簇。中心聚類的代表性算法是K-means[1-2]。K-means算法的執(zhí)行是一個(gè)迭代的過(guò)程，以正整數(shù)K作為超參數(shù)，在每輪次更新K個(gè)類簇的中心。具體來(lái)說(shuō)，給定空間中樣本點(diǎn)集合作為輸入，初始時(shí)算法以某種方式選定K個(gè)空間中的點(diǎn)作為K個(gè)類簇的初始中心點(diǎn)，這種選取方式可以是隨機(jī)的，也可以是根據(jù)輸入樣本的特征先驗(yàn)選取。在每輪迭代的過(guò)程中，對(duì)每一個(gè)輸入樣本，計(jì)算他們到各個(gè)中心的距離，將其歸入距離最近的中心所代表的類簇中，這將得到一個(gè)樣本的類別劃分。然后對(duì)每一個(gè)聚類計(jì)算其新的中心，計(jì)算方式通常是取類簇中各自樣本集合的平均值，作為下一次迭代的中心。迭代直到每個(gè)類簇的中心相較于上一輪迭代的中心都僅產(chǎn)生足夠小的位移為止。

K-means算法的優(yōu)點(diǎn)是計(jì)算簡(jiǎn)單，迭代收斂速度快，尤其適合歐式空間中按向量和歐式距離定義的樣本聚類。但是其缺點(diǎn)也很明顯，最大的缺點(diǎn)是需要事先選定一個(gè)超參數(shù)K。一般在樣本數(shù)目很大的應(yīng)用中，對(duì)于類別數(shù)目沒(méi)有先驗(yàn)知識(shí)時(shí)，這個(gè)參數(shù)不好估計(jì)，通常需要對(duì)各種給定的值進(jìn)行試探。其次，K-means算法找到的類簇中心由于類簇中樣本分布不定的原因，可能落在樣本分布稀疏的地方，導(dǎo)致與直觀上的聚類中心不符。為了克服這個(gè)問(wèn)題，

人們提出在每次更新各類簇中心點(diǎn)的時(shí)候限制其在樣本點(diǎn)上選取，這就是K-medoids算法[3]。此外，還有高斯混合模型聚類，可以視為K-means算法的擴(kuò)展，它假設(shè)類簇的各維度服從高斯分布，從而保證類簇中心的稠密性與類簇的凸性。另一個(gè)問(wèn)題是K-means算法得到的類簇之間是剛性劃分，沒(méi)有重疊或軟性隸屬關(guān)系，這在某些應(yīng)用場(chǎng)景中是與事實(shí)不合的（之后我們會(huì)看到，這也是大部分聚類算法的通?。?。為此，人們提出模糊（Fuzzy）c-means聚類算法[4-5]，即設(shè)定在各類簇邊緣的樣本點(diǎn)可以依一定概率屬于多個(gè)類簇，概率值大小反映樣本對(duì)于該類別的隸屬程度。

2 層次聚類法

層次聚類法是另一類極為常見聚類算法。它的思想是通過(guò)逐層次的劃分方式將樣本點(diǎn)分成若干類簇的集合。層次聚類法一般把樣本及其之間的距離建模成帶權(quán)圖，其中包含頂點(diǎn)、邊以及邊的權(quán)重等參數(shù)。通常啟發(fā)式地有兩種層次劃分方式，即自頂向下的分裂法和自底向上的凝聚法。分裂法從初始將所有樣本視為同一類開始，通過(guò)某種規(guī)則將當(dāng)前的每一個(gè)類簇拆分成兩個(gè)，直到每個(gè)類簇達(dá)到終止條件為止。而凝聚法則相反，它從初始將每一個(gè)樣本都視為不同類別，也是通過(guò)某種規(guī)則將當(dāng)前的類簇兩兩合并成，直到每個(gè)類簇達(dá)到終止條件為止。

層次聚類法的拆分或者合并規(guī)則通常是基于某種特定的指標(biāo)。分裂法中類型拆分的依據(jù)常用的是平衡割（Balanced Cut）。平衡割指的是移除之后能將圖分割成大小或體積相差不多的兩個(gè)子圖的邊的集合，分裂法中找的是權(quán)重之和最小的平衡割。之所以要求兩個(gè)子圖大小或體積相對(duì)平衡，是為了防止計(jì)算過(guò)程中出現(xiàn)僅僅為了達(dá)到數(shù)學(xué)上的極小值，而在圖中的一個(gè)小局部進(jìn)行切分的情況，而這樣零散的小局部聚類通常不能很好地反映樣本的共性，且過(guò)于細(xì)小的切分通常也不是我們需要的聚類方式。當(dāng)然，解決這一問(wèn)題還有其他的指標(biāo)，如稀疏割（Sparsest Cut）等。

凝聚法中通常有一個(gè)目標(biāo)函數(shù)，算法在每輪次凝聚的過(guò)程中貪心地選取使得目標(biāo)函數(shù)值優(yōu)化最多的兩個(gè)類型的樣本集合進(jìn)行合并，直到目標(biāo)函數(shù)無(wú)法繼續(xù)優(yōu)化或者達(dá)到其他終止條件為止。這個(gè)目標(biāo)函數(shù)是定義在全樣本及其聚類劃分上的，它的大小從某種直觀上反映了該樣本劃分定義的聚類的質(zhì)量。目前使用最為廣泛、最有代表性的目標(biāo)函數(shù)是模塊性（Modularity），它反映的是在該劃分下的聚類程度與保持頂點(diǎn)度數(shù)不變的隨機(jī)連邊的聚類程度之間的差距。這一正向差距越大，表明該劃分的聚類效果越好。近年來(lái)有學(xué)者提出了圖的結(jié)構(gòu)熵（Structural Entropy）的概念，從圖中隨機(jī)游走編碼極小化的角度定義了圖的K-維結(jié)構(gòu)熵，并設(shè)計(jì)了基于二維結(jié)構(gòu)熵極小化的凝聚聚類算法。

分裂法聚類的優(yōu)點(diǎn)在于其算法過(guò)程完全是基于人們對(duì)聚類方式的直觀理解，思路清晰明確，因此效果一般較好，并且算法的遞歸過(guò)程天然地給出了樣本的層次聚類劃分，將樣本類型之間的距離以及樣本類型的更高層次聚類關(guān)系都展示了出來(lái)。但是缺點(diǎn)是計(jì)算過(guò)程緩慢，因?yàn)槊枯喌诋?dāng)前子問(wèn)題中求全局的劃分方式，且不論找最小平衡割的計(jì)算困難性，單是子問(wèn)題的遞歸次數(shù)就已經(jīng)與樣本規(guī)模成正比。而找最小平衡割的問(wèn)題本身是困難的，有效時(shí)間內(nèi)只能找到近似解。另一個(gè)問(wèn)題是，分裂法的算法終止條件需要人為設(shè)定，即到底劃分到多細(xì)就（才）能滿足需要。這樣的條件需要對(duì)樣本有一定的先驗(yàn)，或者取不同的參數(shù)進(jìn)行多次嘗試。

凝聚法聚類的優(yōu)點(diǎn)在于執(zhí)行速度快，貪心凝聚的迭代過(guò)程中，目標(biāo)函數(shù)的增量無(wú)論模塊性還是二維結(jié)構(gòu)熵均能局部計(jì)算，因此以堆作為輔助的數(shù)據(jù)結(jié)構(gòu)，這兩種算法均能在幾乎線性時(shí)間內(nèi)完成。與分裂法相比，凝聚法的另一個(gè)優(yōu)勢(shì)是它的目標(biāo)函數(shù)清晰，所以終止條件明確且具有可解釋性。它的缺點(diǎn)是由于樣本的局部微觀結(jié)構(gòu)導(dǎo)致初始時(shí)樣本的聚類方式比較任意，并且之后的算法執(zhí)行過(guò)程中聚在同一類簇中的樣本無(wú)法再分開，從而就有可能造成最終的結(jié)果雖然使得目標(biāo)函數(shù)值較優(yōu)，但是與真實(shí)的聚類方式差距較大。當(dāng)然，為了克服這一缺點(diǎn)，可以增加一些在貪心迭代過(guò)程中的樣本遷移策略來(lái)糾正初始時(shí)的錯(cuò)誤。

3 密度聚類法

密度聚類法將內(nèi)部連續(xù)稠密的樣本子集視為同一類型，代表性算法是DBSCAN（Density-Based Spatial Clustering of Applications with Noise）。DBSCAN算法首先將所有樣本點(diǎn)區(qū)分為核心點(diǎn)和非核心點(diǎn)，其中核心點(diǎn)指半徑r以內(nèi)樣本點(diǎn)數(shù)目大于k的那些點(diǎn)，這里r，k均為參數(shù)。如果兩個(gè)核心點(diǎn)的距離不超過(guò)r，則稱之為直接密度可達(dá)。經(jīng)過(guò)多次直接密度可達(dá)的核心點(diǎn)稱為密度可達(dá)。一個(gè)極大的密度可達(dá)的核心點(diǎn)子集并上其中各核心點(diǎn)半徑r以內(nèi)的非核心點(diǎn)，即構(gòu)成一個(gè)類簇?？梢钥吹剑珼BSCAN算法得到的各類簇之間的核心點(diǎn)集不交，但非核心點(diǎn)集可能相交，并且還可能存在某些非核心點(diǎn)其r半徑內(nèi)不包含任何核心點(diǎn)，這被視為噪聲。因此，DBSCAN算法允許類簇有重疊，也允許某些點(diǎn)不從屬于任何類簇，是其他大多數(shù)聚類算法所不具備的優(yōu)勢(shì)。而DBSCAN算法的缺點(diǎn)是它用一個(gè)統(tǒng)一的尺度r和k來(lái)衡量所有類簇，很多時(shí)候這樣是不合適的。因此，人們提出了改進(jìn)版本OPTICS（Ordering Points To Identify the Clustering Structure）算法，將半徑r設(shè)為靈活的參數(shù)，由算法自身來(lái)調(diào)節(jié)，但思想上與DBSCAN是統(tǒng)一的。

另一個(gè)基于密度的聚類算法是團(tuán)滲透（Clique Percolation）算法。團(tuán)是圖論中的經(jīng)典概念，一個(gè)大小為k的團(tuán)就是指k個(gè)點(diǎn)的完全圖。團(tuán)滲透算法主要針對(duì)的是無(wú)向圖中的聚類問(wèn)題。它以一個(gè)正整數(shù)k作為參數(shù)，首先找到圖中所有的極大團(tuán)（即不存在更大的團(tuán)以該團(tuán)作為子集），然后當(dāng)兩個(gè)極大團(tuán)的交集大小為至少k-1時(shí)將兩個(gè)極大團(tuán)合并，視為同一類簇。算法執(zhí)行過(guò)程中是從一個(gè)極大團(tuán)出發(fā)找與其交集大于等于k-1的“鄰居”團(tuán)，如同液體的滲透蔓延，故而得名。以團(tuán)作為類簇組成的基本元素在某些應(yīng)用中是十分合理的，比如社交網(wǎng)絡(luò)，但k的取值不宜過(guò)大，通常取3或4即可，否則對(duì)類簇稠密度要求太高，不易找到合理的類簇。不難發(fā)現(xiàn)，團(tuán)滲透算法也能找到重疊類簇。但是其缺點(diǎn)是對(duì)于類簇內(nèi)部密度要求較高，且只能適用于圖的聚類，應(yīng)用場(chǎng)景有很大的局限性。

4 譜聚類法

譜聚類（Spectral Clustering）是一種針對(duì)圖聚類的基于譜圖理論的聚類算法。它將圖中的每個(gè)頂點(diǎn)先用代數(shù)方法向量化，然后調(diào)用其他經(jīng)典的聚類算法對(duì)向量樣本聚類。雖然算法執(zhí)行步驟是代數(shù)的，但其直觀基于最小化各類簇的擴(kuò)張性（expansion）。一個(gè)點(diǎn)集擴(kuò)張性是指該點(diǎn)集向外聯(lián)系的邊的數(shù)目比上自身的大小，因此這是一個(gè)既考慮向外聯(lián)系的緊密程度又同時(shí)考慮類簇自身大小的數(shù)學(xué)量。算法執(zhí)行過(guò)程首先計(jì)算圖的拉普拉斯矩陣的最小的k個(gè)特征值，這個(gè)k的設(shè)定需要根據(jù)特征值的分布，使得拉普拉斯矩陣的主要特征向量被指使出來(lái)。之后將這k個(gè)特征值對(duì)應(yīng)的長(zhǎng)度為n（n為頂點(diǎn)數(shù)目）的特征向量按各頂點(diǎn)分量構(gòu)成k維向量并歸一化，再用其他聚類算法對(duì)這n個(gè)向量樣本進(jìn)行聚類。譜聚類算法的優(yōu)點(diǎn)是它可以處理聯(lián)系非常稀疏的樣本，并且它給出了一個(gè)對(duì)高維數(shù)據(jù)進(jìn)行降維的方法。但缺點(diǎn)是由于涉及矩陣運(yùn)算求特征值和特征向量，計(jì)算復(fù)雜度較高，且需要一個(gè)處理向量聚類的算法做輔助。

5 其他聚類方法

還有其他一些聚類方法沒(méi)有被歸入以上4種，如標(biāo)簽傳播聚類法、神經(jīng)網(wǎng)絡(luò)聚類法等。標(biāo)簽傳播（Label Propagation）算法運(yùn)用了隨機(jī)游走的思想，用當(dāng)前頂點(diǎn)的標(biāo)簽去預(yù)測(cè)下一步其鄰居的標(biāo)簽。算法初始時(shí)可以有一些標(biāo)注好的頂點(diǎn)，其標(biāo)簽代表其所屬的真實(shí)類型，而其他頂點(diǎn)可隨機(jī)賦予標(biāo)簽。算法迭代執(zhí)行的每一步都視為每個(gè)頂點(diǎn)以隨機(jī)游走的方式將標(biāo)簽傳給其鄰居，因此需計(jì)算每個(gè)頂點(diǎn)獲得其鄰居標(biāo)簽的概率，但實(shí)現(xiàn)的時(shí)候只需計(jì)算矩陣與向量的乘法即可。然后除已標(biāo)注頂點(diǎn)外，其他頂點(diǎn)獲得概率最大的那個(gè)標(biāo)簽，多個(gè)概率最大標(biāo)簽之間任意選取即可。算法執(zhí)行至所有頂點(diǎn)標(biāo)簽不再發(fā)生改變?yōu)橹??？梢钥闯?，距離越近的兩個(gè)頂點(diǎn)之間越容易獲得共同的標(biāo)簽。標(biāo)簽傳播算法的優(yōu)點(diǎn)是簡(jiǎn)潔直觀，計(jì)算速度快，雖然在某些極端情況下算法不收斂，但實(shí)際問(wèn)題中很難遇到這種情況。由于算法允許一些標(biāo)注樣本的存在，所以標(biāo)簽傳播也是一種簡(jiǎn)單高效的半監(jiān)督算法。其缺點(diǎn)也很明顯，由于初始對(duì)于非標(biāo)注頂點(diǎn)的標(biāo)簽是隨機(jī)賦予的，這使得算法結(jié)果差異很大，影響準(zhǔn)確性。另外還有一類基于特定神經(jīng)網(wǎng)絡(luò)模型的聚類算法，自組織映射（Self Organizing Maps）神經(jīng)網(wǎng)絡(luò)算法。由于神經(jīng)網(wǎng)絡(luò)的原理解釋仍是目前學(xué)術(shù)界的一大難題，所以這里所用的思想還并不明確，需要進(jìn)一步探究，我們?cè)诖艘膊辉斒觥?/p>

6 結(jié)語(yǔ)

本文總結(jié)了目前常用的聚類算法，并按算法思想分類，闡述了基于其思想的算法實(shí)現(xiàn)過(guò)程，分析了優(yōu)缺點(diǎn)與適用性。總體來(lái)說(shuō)，沒(méi)有任何一個(gè)算法可以適用于所有的需求，需要根據(jù)實(shí)際應(yīng)用場(chǎng)景選擇最適合的聚類算法。

參考文獻(xiàn)

[1] S. P. Lloyd. Least square quantization in PCM[A].Bell Telephone Laboratories Paper，Published much later in IEEE Transactions on Information Theory[C].1982：129-137.

[2] E. W. Forgy. Cluster analysis of multivariate data： efficiency versus interpretability of classifications[J]. Biometrics，1965（2）：768-769.

[3] L. Kaufman and P.J. Rousseeuw. Clustering by means of medoids[A].In Statistical Data Analysis Based on the L1-Norm and Related Methods[C].North-Holland，1987：405-416.

[4] J. C. Dunn. A Fuzzy Relative of the ISODATA Process and Its Use in Detecting Compact Well-Separated Clusters[J].Journal of Cybernetics，1973（3）：32-57.

[5] J. C. Bezdek. Pattern Recognition with Fuzzy Objective Function Algorithms[Z]. ISBN 0-306-40671-3，1981.