經(jīng)典聚類算法研究綜述

鄧林培

摘 要 文章通過(guò)介紹4種經(jīng)典的聚類算法以加強(qiáng)人們對(duì)聚類算法的了解，同時(shí)對(duì)每一種算法的適用情況和優(yōu)勢(shì)劣勢(shì)進(jìn)行闡述。聚焦于聚類算法發(fā)展所呈現(xiàn)的趨勢(shì)和應(yīng)用情景中涉及的領(lǐng)域，感知聚類算法在機(jī)器學(xué)習(xí)甚至人工智能領(lǐng)域的強(qiáng)大生命力。

關(guān)鍵詞 人工智能；機(jī)器學(xué)習(xí)；聚類；K-means

中圖分類號(hào) TP2 文獻(xiàn)標(biāo)識(shí)碼 A 文章編號(hào) 1674-6708（2019）230-0108-03

從1956年的達(dá)特茅斯會(huì)議到如今，不過(guò)短短60多年的時(shí)間，人工智能發(fā)展之迅速令人驚嘆。人工智能領(lǐng)域十分廣泛，神經(jīng)網(wǎng)絡(luò)、自然語(yǔ)言處理、遺傳算法、深度學(xué)習(xí)，甚至哲學(xué)問(wèn)題和未來(lái)趨勢(shì)等都是這一大學(xué)科中的一部分。對(duì)機(jī)器來(lái)說(shuō)，所謂智能，實(shí)質(zhì)是由人對(duì)它輸入算法和數(shù)據(jù)，機(jī)器本身運(yùn)用算法從數(shù)據(jù)中進(jìn)行學(xué)習(xí)，并由此處理新的實(shí)際問(wèn)題。不光算法，像自然語(yǔ)言處理，哲學(xué)問(wèn)題都可以與機(jī)器學(xué)習(xí)結(jié)合。

機(jī)器學(xué)習(xí)中有許多算法。其中聚類算法是一個(gè)大的分支。針對(duì)不同數(shù)據(jù)類型，聚類算法中有各種不用運(yùn)行理念、不同基準(zhǔn)的算法可將不同類型的樣本數(shù)據(jù)收聚到較好的結(jié)果。聚類算法中經(jīng)典的算法如K-means算法、均值漂移算法、DBSCAN算法和層次聚類算法在當(dāng)下仍經(jīng)久不衰。同時(shí)，聚類算法在信息技術(shù)和人工智能浪潮的推涌之下，呈現(xiàn)出融合的新態(tài)勢(shì)。

1 經(jīng)典聚類算法研究

1.1 K-means

K-means算法是一種應(yīng)用極為廣泛的聚類算法[ 1 ]。它的核心思想是用戶指定k個(gè)初始的質(zhì)心（隨機(jī)數(shù)）作為聚類的類別，并重復(fù)迭代直至算法收斂。

首先，計(jì)算所有數(shù)據(jù)點(diǎn)到這k個(gè)初始質(zhì)心的距離，并以這個(gè)計(jì)算出的距離作為下一步分類標(biāo)準(zhǔn)，也就是說(shuō)，各數(shù)據(jù)點(diǎn)到哪個(gè)質(zhì)心距離最近，便決定它在此次類別的分取中屬于哪一類別。那么，初始定義的k個(gè)質(zhì)心就會(huì)在迭代中將所有數(shù)據(jù)分為k個(gè)類別也就是k個(gè)簇。待對(duì)每個(gè)樣本點(diǎn)進(jìn)行了距離計(jì)算并類別歸屬之后，再重新計(jì)算k個(gè)簇中每一個(gè)簇對(duì)應(yīng)的質(zhì)心，即更新質(zhì)心。每個(gè)簇?cái)?shù)據(jù)明朗，質(zhì)心實(shí)際可求，于是，對(duì)所得的每一個(gè)簇的所有數(shù)據(jù)點(diǎn)求新質(zhì)心，再以此質(zhì)心替換隨機(jī)數(shù)質(zhì)心做為新的距離計(jì)算標(biāo)準(zhǔn)，重復(fù)距離近便成一簇的過(guò)程。之后繼續(xù)重復(fù)質(zhì)心更新和數(shù)據(jù)分簇過(guò)程，直至質(zhì)心更新時(shí)，每簇的質(zhì)心不再變化或僅有微小變化時(shí)，算法停止。最后所得的k個(gè)最終質(zhì)心及它們所在簇包含的樣本點(diǎn)，即所期望的聚類結(jié)果。

K-means算法中k值也就是聚類的類別數(shù)是需要用戶自己定義的，當(dāng)遇到一個(gè)復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，可能需要多次嘗試才能選取到一個(gè)較好的k值，使這個(gè)樣本數(shù)據(jù)聚成如此多個(gè)類才是最優(yōu)的。

我們可以發(fā)現(xiàn)，因在最初的算法迭代中選取的初始質(zhì)心為隨機(jī)定義而來(lái)，會(huì)致使聚類效果不好，迭代次數(shù)增多，可能僅得到局部最優(yōu)結(jié)果。局部最優(yōu)是K-means算法乃至機(jī)器學(xué)習(xí)算法存在的普遍問(wèn)題。同時(shí)，K-means算法僅適用于數(shù)據(jù)聚類，并且在噪音數(shù)據(jù)出現(xiàn)時(shí)，由于其算法的原理，以距離平方和為準(zhǔn)則，會(huì)使一些不合理的極端數(shù)據(jù)影響聚類結(jié)果。

針對(duì)它的這些缺陷，K-means算法衍生出的變種k-modes算法和K-prototype算法在一定程度上彌補(bǔ)了K-means算法的不足。

K-modes算法適用于離散型非數(shù)值型的集合，如時(shí)間、文本、顏色、大小等。它是以屬性來(lái)度量?jī)蓸颖镜南嚓P(guān)性D。比較兩樣本所有屬性，若屬性不同就給D加1，相同就加0。也就是說(shuō)，D值越大，兩樣本就越不相關(guān)。這不相關(guān)程度越大就相當(dāng)于k-means中的距離越遠(yuǎn)。接著以每一簇中出現(xiàn)頻率最大的屬性值來(lái)代表那一簇的屬性，不斷更新簇，更新代表屬性，重復(fù)迭代。

K-prototype算法是對(duì)K-means算法和K-modes算法的結(jié)合，它適用于樣本記錄里面既有離散型數(shù)據(jù)又有數(shù)值型數(shù)據(jù)的集合。它結(jié)合K-means得到數(shù)值屬性和結(jié)合K-modes得到分類屬性，最終通過(guò)權(quán)重來(lái)得出樣本混合屬性。其更新也是兩者結(jié)合，并重復(fù)迭代得出結(jié)果。

當(dāng)然，K-means算法以其運(yùn)算迅速，操作簡(jiǎn)單易行等優(yōu)勢(shì)仍在各領(lǐng)域有著廣泛的應(yīng)用。

1.2 均值漂移聚類

與K-means相似，都是基于質(zhì)心的聚類算法。均值漂移算法[ 2 ]依賴于自定義半徑的圓形滑動(dòng)窗口的移動(dòng)。窗口會(huì)一直向著能使圓內(nèi)數(shù)據(jù)點(diǎn)密度增大最快的方向靠近，直至窗口無(wú)論再向哪個(gè)方向移動(dòng)，都無(wú)法再使更多點(diǎn)被包括進(jìn)窗口內(nèi)，即窗口內(nèi)數(shù)據(jù)密度不再增加時(shí)，窗口才不再滑動(dòng)。它與K-means的相似之處是它也需要先隨機(jī)選取窗口中心值和窗口半徑，待窗口滑到新的數(shù)據(jù)區(qū)時(shí)，中心值便隨之更新，即把窗口內(nèi)所有數(shù)據(jù)點(diǎn)的平均值作為新的中心點(diǎn)而繼續(xù)滑動(dòng)。

均值漂移算法的優(yōu)點(diǎn)在于不需要我們事先確定類別數(shù)目，當(dāng)初始的中心點(diǎn)數(shù)目足夠，它會(huì)自發(fā)收斂到密度最高的幾個(gè)區(qū)域。

此算法對(duì)密度分布差異較大的數(shù)據(jù)聚類效果好且受均值影響較小。但對(duì)分布均勻的數(shù)據(jù)來(lái)說(shuō)，均值漂移算法收斂效果較差。

1.3 DBSCAN算法

DBSCAN是一種基于密度的聚類算法[ 3 ]，它的聚類思想是以密度可達(dá)關(guān)系導(dǎo)出可得的最大密度相連樣本集合，此即為聚類出的一個(gè)簇。

6）另取核心對(duì)象重復(fù)上兩步步驟。DBSCAN適用于任意稠密數(shù)據(jù)，對(duì)數(shù)據(jù)里的噪聲數(shù)據(jù)不敏感，聚類結(jié)果相對(duì)受其他因素干擾較少，可避免出現(xiàn)K-means受初始值影響大的情況。但正是由于其基于密度的算法特性，如果樣本密度不均，會(huì)導(dǎo)致出現(xiàn)聚類質(zhì)量低的情況。且如果樣本數(shù)據(jù)多，DBSCAN聚類收斂耗時(shí)會(huì)較長(zhǎng)，并不理想。

1.4 層次聚類算法

層次聚類包括自下而上的凝聚聚類和自上而下的分裂聚類方法[ 4 ]。

其中凝聚聚類要求我們首先得把每個(gè)數(shù)據(jù)點(diǎn)視為一個(gè)單一的簇，再將距離最近的兩個(gè)簇合并。這里就需要我們選定一個(gè)距離度量標(biāo)準(zhǔn)。例如我們可以使用簇間距離，即第一個(gè)簇中的數(shù)據(jù)點(diǎn)與第二個(gè)簇中的數(shù)據(jù)點(diǎn)之間的平均距離作為標(biāo)準(zhǔn)來(lái)進(jìn)行合并。合并后重新計(jì)算各簇間距離，重復(fù)合并步驟，直到聚類成一簇或達(dá)到預(yù)設(shè)條件方可結(jié)束算法。

而分裂聚類與凝聚聚類恰好相反，它意在將一個(gè)大的數(shù)據(jù)集分裂成許多小簇。先將所有對(duì)象置于一個(gè)類中，然后逐漸分出小簇，使總數(shù)據(jù)集變?yōu)樵絹?lái)越小但個(gè)數(shù)越來(lái)越多的簇，直到每個(gè)對(duì)象獨(dú)自成簇或滿足了一定的終止條件。例如達(dá)到了我們希望的聚類簇?cái)?shù)目，結(jié)束算法。

層次聚類不需要我們提前知道需要合成或分割所得的簇的數(shù)目，同時(shí)它可以使用多種距離計(jì)算方法來(lái)計(jì)算簇間距離，但也正是距離計(jì)算量大，層次聚類并不迅速，效率低。

2 聚類算法的發(fā)展趨勢(shì)與應(yīng)用前景

2.1 發(fā)展趨勢(shì)

正如人類認(rèn)識(shí)社會(huì)，需要區(qū)別不同事物，聯(lián)系相同相似事物一樣，數(shù)據(jù)的挖掘、處理也離不開(kāi)聚類分析。在這個(gè)數(shù)據(jù)爆炸的時(shí)代，聚類算法大有用武之地。公司對(duì)目標(biāo)顧客的分析，市場(chǎng)銷售的調(diào)研等等都與聚類算法有著密切聯(lián)系。不難發(fā)現(xiàn)，聚類算法中不同類型的算法有著不同適用領(lǐng)域，但每個(gè)算法都并不完美。各個(gè)算法之間存在一種相互彌補(bǔ)相互結(jié)合的關(guān)系，正與現(xiàn)代社會(huì)發(fā)展，領(lǐng)域不斷更新，各領(lǐng)域數(shù)據(jù)變得更龐大更多元更復(fù)雜的趨勢(shì)相適應(yīng)。這無(wú)疑對(duì)算法提出了更高的要求，孤立的算法已經(jīng)并不完全適用于這個(gè)時(shí)代。

2.2 應(yīng)用前景

聚類算法可應(yīng)用于圖像分割、機(jī)器視覺(jué)、數(shù)據(jù)壓縮和信息檢索，它功能強(qiáng)大，譬如檢索時(shí)可以使檢索時(shí)間縮短并且擁有更高的精確度。它還應(yīng)用于一些生活中常用的軟件，如知識(shí)管理系統(tǒng)里的知識(shí)共享、知識(shí)推薦功能，學(xué)生成績(jī)統(tǒng)計(jì)分析軟件對(duì)成績(jī)的深度挖掘功能。

聚類算法可應(yīng)用于建立數(shù)據(jù)庫(kù)，其中的文本聚類算法還被用來(lái)建立詞義網(wǎng)（Word Net）。隨著時(shí)代的發(fā)展，聚類算法的應(yīng)用領(lǐng)域已從商業(yè)金融拓展到了教育互聯(lián)網(wǎng)等行業(yè)，同時(shí)對(duì)生物學(xué)、心理學(xué)、考古學(xué)、地質(zhì)學(xué)的研究也都有重要作用。

3 結(jié)論與展望

聚類算法的發(fā)展已經(jīng)到了一個(gè)融合互補(bǔ)的時(shí)期，它所包含的孤立的經(jīng)典算法雖仍然能得到較為廣泛的應(yīng)用但終會(huì)逐漸追逐不上時(shí)代日新月異的復(fù)雜變化。時(shí)代發(fā)展要求數(shù)據(jù)結(jié)構(gòu)向著更復(fù)雜更靈活的方向發(fā)展。聚類算法要想繼續(xù)能將機(jī)器學(xué)習(xí)進(jìn)行得正確而高速，勢(shì)必要在原本的經(jīng)典算法的基礎(chǔ)之上，做出符合時(shí)代數(shù)據(jù)特征的創(chuàng)新。

在筆者看來(lái)，完美倒不是一件幸事，只有在對(duì)不完美的修正與創(chuàng)新中，才能擦出新的思維火花，在成果不斷更新被淘汰更新再換代的過(guò)程中，人類的智慧才得以更大可能的激發(fā)，社會(huì)才得以不斷進(jìn)步。正因如此，聚類算法的未來(lái)，是互相融合互相補(bǔ)充的未來(lái)，是不斷改進(jìn)與簡(jiǎn)化的未來(lái)，至少以后的一段時(shí)期內(nèi)，它的未來(lái)前景不可小覷。

參考文獻(xiàn)

[1]楊善林，李永森，胡笑旋，等.K-means算法中的K值優(yōu)化問(wèn)題研究[J].系統(tǒng)工程理論與實(shí)踐，2006，26（2）：97-101.

[2]周芳芳，樊曉平，葉榛.均值漂移算法的研究與應(yīng)用[J].控制與決策，2007，22（8）：841-847.

[3]榮秋生，顏君彪，郭國(guó)強(qiáng).基于DBSCAN聚類算法的研究與實(shí)現(xiàn)[J].計(jì)算機(jī)應(yīng)用，2004，24（4）：45-46.

[4]史變霞，張明新.一種改進(jìn)的層次聚類算法[J].微電子學(xué)與計(jì)算機(jī)，2010，27（12）：55-56.