1、聚類(lèi)算法綜述姓名： 謝天嬌 學(xué)校： 北京郵電大學(xué) 學(xué)院: 計(jì)算機(jī)學(xué)院 2014 年 5 月 30 日摘要聚類(lèi)算法又稱(chēng)群集分析，常用于將大量數(shù)據(jù)按照一定規(guī)則分為不同類(lèi)別，其與分類(lèi)算法的差異在于，聚類(lèi)算法可在非監(jiān)督模式下處理數(shù)據(jù)，不需要人為輸入數(shù)據(jù)標(biāo)簽。聚類(lèi)算法發(fā)展至今約有六十余年，其非監(jiān)督的特性在如今的大數(shù)據(jù)時(shí)代顯示出更大的優(yōu)勢(shì)，而與之相應(yīng)很多學(xué)者也致力于研究針對(duì)海量數(shù)據(jù)且精確度更高，語(yǔ)義更明確的聚類(lèi)算法。筆者在文中從算法分類(lèi)的角度簡(jiǎn)述不同種類(lèi)聚類(lèi)算法的基礎(chǔ)和發(fā)展現(xiàn)狀。然后就當(dāng)前使用范圍較廣的層次法，劃分法，密度法，譜聚類(lèi)各選出一個(gè)較為代表性的算法簡(jiǎn)要分析其算法結(jié)構(gòu)和性能。最后，筆者給出一種譜聚

2、類(lèi)的matlab實(shí)現(xiàn)實(shí)例及實(shí)驗(yàn)結(jié)果。正文一、引言聚類(lèi)分析最早起源于分類(lèi)學(xué)，初時(shí)人們依靠經(jīng)驗(yàn)一類(lèi)事件的集合分為若干子集。隨著科技的發(fā)展，人們將數(shù)學(xué)工具引入分類(lèi)學(xué)，聚類(lèi)算法便被細(xì)化歸入數(shù)值分類(lèi)學(xué)領(lǐng)域。后來(lái)，信息技術(shù)快速發(fā)展，新數(shù)據(jù)的出現(xiàn)呈井噴趨勢(shì)，其結(jié)構(gòu)的復(fù)雜性和內(nèi)容的多元化尤為聚類(lèi)提出了新的要求，于是多元分析技術(shù)被引入數(shù)值分析學(xué)，形成了聚類(lèi)分析學(xué)。聚類(lèi)分析，在英文中是Cluster analysis，又譯為群集分析。其作用，簡(jiǎn)單而言即是非監(jiān)督式的將大量數(shù)據(jù)以相似度為基礎(chǔ)形成集合。非監(jiān)督式，即是聚類(lèi)分析與分類(lèi)和回歸分析的區(qū)別所在，聚類(lèi)不需要人為的輸入標(biāo)簽，盡管某些聚類(lèi)算法需要設(shè)定初始劃分方法或者根

3、據(jù)輸入?yún)?shù)確定聚類(lèi)集合個(gè)數(shù)，但在分析過(guò)程中，算法無(wú)須人為輸入分類(lèi)標(biāo)準(zhǔn)。因此，聚類(lèi)分析在很多時(shí)候用于大型數(shù)據(jù)庫(kù)的分類(lèi)預(yù)處理，當(dāng)然聚類(lèi)分析也常作為獨(dú)立分析數(shù)據(jù)的工具。而不同的關(guān)于相似度的判斷，就形成了不同的聚類(lèi)算法。聚類(lèi)算法的分類(lèi)有很多，從時(shí)間上可以分為傳統(tǒng)聚類(lèi)算法和現(xiàn)代聚類(lèi)算法；從子集元素可以分為軟聚類(lèi)和硬聚類(lèi)；從對(duì)初始狀態(tài)的處理可以分為結(jié)構(gòu)性聚類(lèi)和分散性聚類(lèi)，基于其他標(biāo)準(zhǔn)亦有其他的分類(lèi)方法，在本文第二節(jié)將會(huì)給出詳細(xì)介紹和分析。聚類(lèi)分析具有廣泛的應(yīng)用領(lǐng)域。對(duì)于網(wǎng)絡(luò)流量的監(jiān)控和數(shù)據(jù)挖掘，可以實(shí)現(xiàn)輿情分析，獲知前所未有的又出現(xiàn)的熱點(diǎn)事件。在商業(yè)上，市場(chǎng)消費(fèi)數(shù)據(jù)的聚類(lèi)，可以使企業(yè)相關(guān)人員獲知新的消費(fèi)趨

4、勢(shì)和市場(chǎng)需求。而在城市規(guī)劃領(lǐng)域，對(duì)于地形地貌或者人口分布的聚類(lèi)，可以幫助市政規(guī)劃人員更好的進(jìn)行城市分區(qū)和建設(shè)。不同的應(yīng)用領(lǐng)域，需要聚類(lèi)的數(shù)據(jù)差異很大，對(duì)于聚類(lèi)結(jié)果也有不同的要求，選擇合適的聚類(lèi)算法才能得到最滿(mǎn)意的聚類(lèi)結(jié)果。二、聚類(lèi)算法分類(lèi)及國(guó)內(nèi)外發(fā)展現(xiàn)狀根據(jù)中國(guó)知網(wǎng)的搜索結(jié)果顯示，可搜到的最早關(guān)于聚類(lèi)的外國(guó)文獻(xiàn)出版于1957年，中文文獻(xiàn)則是1975年方開(kāi)泰教授發(fā)表于期刊數(shù)學(xué)的實(shí)踐與認(rèn)識(shí)上的聚類(lèi)分析系列文章 方開(kāi)泰. 聚類(lèi)分析J. 數(shù)學(xué)的實(shí)踐與認(rèn)識(shí), 1975, （一）(01期):66-78.。聚類(lèi)分析的實(shí)現(xiàn)步驟大致為特征選擇，計(jì)算相似度，選擇聚類(lèi)算法，驗(yàn)證判定結(jié)果。每一步中選擇不同的方法，便是

5、區(qū)分聚類(lèi)算法的原則之一。目前的聚類(lèi)算法有很多種，考慮到數(shù)據(jù)類(lèi)型，相似度計(jì)算公式以計(jì)算法結(jié)構(gòu)，各種算法已有很多交集。本文中，筆者參考網(wǎng)絡(luò)文獻(xiàn)聚類(lèi)算法綜述 binma85. 聚類(lèi)算法綜述D/OL. 2009-3-212014-5-24. /s/blog_4c2cb83f0100ct0l.html.中該作者的分類(lèi)方法，將聚類(lèi)算法按其發(fā)展進(jìn)程大致分為傳統(tǒng)聚類(lèi)算法和現(xiàn)代聚類(lèi)算法，在此基礎(chǔ)上在按其技術(shù)細(xì)節(jié)細(xì)分。1. 傳統(tǒng)聚類(lèi)算法傳統(tǒng)聚類(lèi)算法多數(shù)屬于硬聚類(lèi)，每個(gè)元素只能屬于一個(gè)集合，在元素特征模糊時(shí)聚類(lèi)結(jié)果將受到影響。此外，一些傳統(tǒng)聚類(lèi)算法需要輸入子集數(shù)量的初始值

6、，這使得在處理大數(shù)據(jù)時(shí)聚類(lèi)效果不佳。但傳統(tǒng)聚類(lèi)是現(xiàn)代聚類(lèi)發(fā)展的理論基礎(chǔ)和實(shí)踐先驅(qū)，因此對(duì)于傳統(tǒng)聚類(lèi)的介紹和理解具有重要意義。(1) 層次法 層次法的指導(dǎo)思想是對(duì)給定待聚類(lèi)數(shù)據(jù)集合進(jìn)行層次化分解。此算法又稱(chēng)為數(shù)據(jù)類(lèi)算法，此算法根據(jù)一定的鏈接規(guī)則將數(shù)據(jù)以層次架構(gòu)分裂或聚合，最終形成聚類(lèi)結(jié)果。從算法的選擇上看，層次聚類(lèi)分為自頂而下的分裂聚類(lèi)和自下而上的聚合聚類(lèi)。分裂聚類(lèi)初始將所有待聚類(lèi)項(xiàng)看成同一類(lèi)，然后找出其中與該類(lèi)中其他項(xiàng)最不相似的類(lèi)分裂出去形成兩類(lèi)。如此反復(fù)執(zhí)行直到所有項(xiàng)自成一類(lèi)。聚合聚類(lèi)初始將所有待聚類(lèi)項(xiàng)都視為獨(dú)立的一類(lèi)，通過(guò)聯(lián)接規(guī)則，包括單鏈接、全連接、類(lèi)間平均連接，以及采用歐氏距離作為相似

7、度計(jì)算的算法，將相似度最高的兩個(gè)類(lèi)合并成一個(gè)類(lèi)。如此反復(fù)執(zhí)行直到所有項(xiàng)并入同一個(gè)類(lèi)。BIRCH算法 Zhang, Tian, Raghu Ramakrishnan, and Miron Livny. BIRCH: an efficient data clustering method for very large databases.JACM SIGMOD Record. Vol. 25. No. 2. ACM, 1996.是層次算法中的典型代表算法，其核心是CF（Cluster Feature）和CF樹(shù)。CF是一個(gè)存儲(chǔ)了聚類(lèi)信息的三元組，其中包含了N（待聚類(lèi)項(xiàng)個(gè)數(shù)），LS（N個(gè)數(shù)據(jù)點(diǎn)的線(xiàn)性和

8、），SS（N個(gè)數(shù)據(jù)點(diǎn)的平方和）。LS和SS分別反映了聚類(lèi)的質(zhì)心和聚類(lèi)的直徑大小。CF樹(shù)有兩個(gè)參數(shù)：分支因子和閾值T。分支因子包括非葉節(jié)點(diǎn)CF條目的最大個(gè)數(shù)和葉節(jié)點(diǎn)CF條目的最大個(gè)數(shù)。這里葉節(jié)點(diǎn)看作聚合而成的一個(gè)簇。閾值T限定了所有條目的最大半徑或直徑。BIRCH算法主要有四個(gè)階段。第一階段掃描待聚類(lèi)的所有數(shù)據(jù)項(xiàng)，根據(jù)初始閾值T初始化一顆CF樹(shù)。第二階段采用聚合思路，通過(guò)增加閾值T重建CF樹(shù)，使其聚合度上升。第三、四階段，對(duì)已有的CF樹(shù)實(shí)行全局聚類(lèi)以得到更好的聚類(lèi)效果。然而B(niǎo)IRCH算法并未給出詳細(xì)的設(shè)定初始閾值T的方法，只是簡(jiǎn)單地賦值T=0，在第二階段中，BIRCH算法也并未給出增加T值的規(guī)則

9、。這也正是近年來(lái)學(xué)者對(duì)于改進(jìn)BIRCH算法的一個(gè)方向。蔣盛益教授在他的一種改進(jìn)的BIRCH聚類(lèi)算法 蔣盛益, 李霞. 一種改進(jìn)的BIRCH聚類(lèi)算法 J. 計(jì)算機(jī)應(yīng)用, 2009, 29(1):293-296.中說(shuō)明，基于T的定義可知，其值與組內(nèi)平均距離和組件平均距離，及數(shù)據(jù)的分布有關(guān)。因此，初始閾值T，可以采用如下公式計(jì)算得出。在數(shù)據(jù)集中隨機(jī)選取N對(duì)數(shù)據(jù)，計(jì)算每對(duì)數(shù)據(jù)間的距離di，計(jì)算N對(duì)數(shù)據(jù)間距離的數(shù)學(xué)期望Ex和方差Dx。初始化CF樹(shù)的T值為，T=P*（Ex+0.25*Dx）。P為事先設(shè)定的百分比。在算法第二階段，T的提升規(guī)則這是增大公式中的P值。這一算法的改進(jìn)提升了原本算法的平均聚類(lèi)精度和

10、聚類(lèi)效率，改進(jìn)了BIRCH算法的性能。(2) 劃分法劃分法屬于硬聚類(lèi)，指導(dǎo)思想是將給定的數(shù)據(jù)集初始分裂為K個(gè)簇，每個(gè)簇至少包含一條數(shù)據(jù)記錄，然后通過(guò)反復(fù)迭代至每個(gè)簇不再改變即得出聚類(lèi)結(jié)果。劃分聚類(lèi)在初始的一步中即將數(shù)據(jù)分成給定個(gè)數(shù)個(gè)簇。在算法過(guò)程中還需使用準(zhǔn)則函數(shù)對(duì)劃分結(jié)果進(jìn)行判斷，易產(chǎn)生最有聚類(lèi)結(jié)果。K-Means算法 Hamerly G, Elkan C. Alternatives to the k-means algorithm that find better clusteringsJ. ACM, 2002(11):600-607，中文譯為K均值算法。這種算法通過(guò)迭代不斷移動(dòng)個(gè)聚簇中心

11、和簇類(lèi)成員，直到得到理想的結(jié)果。通過(guò)K均值算法得到的聚簇結(jié)果，簇內(nèi)項(xiàng)相似度很高，簇間項(xiàng)相似度很低，具有較好的局部最優(yōu)特性，但并非是全局最優(yōu)解。此外，K均值只能定義在數(shù)值類(lèi)屬性值上，無(wú)法處理其他類(lèi)型的數(shù)據(jù)。針對(duì)于無(wú)法產(chǎn)生全局最優(yōu)解問(wèn)題，算法的研究者們一部分傾向于通過(guò)優(yōu)化初始簇的選擇算法和均值計(jì)算改善算法性能，另一部分則允許簇分裂與合并，來(lái)調(diào)整簇間關(guān)系。K-Harmonic Means（K調(diào)和均值）算法 Zhang, B., “Generalized K-Harmonic Means Dynamic Weighting of Data in Unsupervised Learning,”, the

12、 First SIAM International Conference on Data Mining (SDM2001), Chicago, USA, April 57, (2001)是建立在中心基礎(chǔ)上的迭代算法。其評(píng)價(jià)函數(shù)為所有點(diǎn)到所有中心的均方距離的調(diào)和平均值函數(shù)。P個(gè)數(shù)，a1,a2,ap的調(diào)和平均值定義為HA=P/(i=1P1ai)。這樣的評(píng)價(jià)函數(shù)，通過(guò)對(duì)于項(xiàng)的分布給不同項(xiàng)賦值不同權(quán)重，可以將過(guò)于集中的中心點(diǎn)移到數(shù)據(jù)附近沒(méi)有中心點(diǎn)的區(qū)域上。這種算法降低了對(duì)初始點(diǎn)選取的依賴(lài)，提高了算法的魯棒性。在數(shù)據(jù)挖掘中集中劃分聚類(lèi)算法的比較及改進(jìn) 彭麗. 數(shù)據(jù)挖掘中集中劃分聚類(lèi)算法的比較及改進(jìn)D.

13、大連理工大學(xué), 2008年.中，該文章作者通過(guò)使用一種新的距離度量應(yīng)用于K調(diào)和均值算法中，進(jìn)一步改進(jìn)了該算法的聚類(lèi)效果。通常而言，算法中關(guān)于距離的度量都采用歐氏距離。這篇文章中，作者介紹了新的度量函數(shù)d(x,y)=1-exp(-x-y2)，其中是一個(gè)正的常數(shù)，其值的大小決定了聚簇疏密。新的度量方式改變了K調(diào)和均值的目標(biāo)函數(shù)公式和中心更新公式。通過(guò)Wine等三個(gè)聚類(lèi)數(shù)據(jù)集的驗(yàn)證，采用新距離度量方法的K調(diào)和均值算法，從運(yùn)行時(shí)間、迭代次數(shù)和結(jié)果精度方面都有所提高。(3) 基于密度的方法上文中提到的兩類(lèi)算法，其聚類(lèi)的劃分都以距離為基礎(chǔ)，容易產(chǎn)生類(lèi)圓形的凸聚類(lèi)。而密度算法很好的克服了這一缺點(diǎn)。密度算法的

14、指導(dǎo)思想是將空間中密度大于某一閾值的點(diǎn)加入到一個(gè)聚類(lèi)中。DBSCAN算法 榮秋生, 顏君彪, 郭國(guó)強(qiáng). 基于DBSCAN聚類(lèi)算法的研究與實(shí)現(xiàn)J. 計(jì)算機(jī)應(yīng)用, 2004, 24(4):45-46.是基于密度聚類(lèi)的經(jīng)典算法。它將簇定義為密度相連的點(diǎn)的最大集合，將足夠高密度的區(qū)域劃分為簇。這樣的算法對(duì)噪聲具有健壯性，并且可以發(fā)現(xiàn)任意形狀的聚簇。DBSCAN的基本算法流程為，從任意對(duì)象P開(kāi)始根據(jù)閾值和參數(shù)通過(guò)廣度優(yōu)先搜索提取從P密度可達(dá)的所有對(duì)象，得到一個(gè)聚類(lèi)。若P是核心對(duì)象，則可以一次標(biāo)記相應(yīng)對(duì)象為當(dāng)前類(lèi)并以此為基礎(chǔ)進(jìn)行擴(kuò)展。得到一個(gè)完整的聚類(lèi)后，在選擇一個(gè)新的對(duì)象重復(fù)上述過(guò)程。若P是邊界對(duì)象，則

15、將其標(biāo)記為噪聲并舍棄。盡管DBSCAN算法改進(jìn)完善了上述兩種算法的一些缺陷，但此算法也存在不足。如聚類(lèi)的結(jié)果與參數(shù)關(guān)系較大，閾值過(guò)大容易將同一聚類(lèi)分割，閾值過(guò)小容易將不同聚類(lèi)合并。此外固定的閾值參數(shù)對(duì)于稀疏程度不同的數(shù)據(jù)不具適應(yīng)性，密度小的區(qū)域同一聚類(lèi)易被分割，密度大的區(qū)域不同聚類(lèi)易被合并。針對(duì)DBSCAN算法在聚類(lèi)時(shí)未考慮非空間屬性，以及處理大量數(shù)據(jù)的內(nèi)存消耗。文獻(xiàn) 胡彩平, 秦小麟. 一種改進(jìn)的基于密度的抽樣聚類(lèi)算法J. 中國(guó)圖像圖形學(xué)報(bào), 2007, 12(11):2031-2036.中提出了基于密度的抽樣聚類(lèi)IDBSCAS算法，此算法通過(guò)核心對(duì)象和邊界對(duì)象選取適當(dāng)位置和數(shù)量的種子對(duì)象，

16、使算法能夠有效的處理大規(guī)?？臻g數(shù)據(jù)庫(kù)并且同時(shí)考慮了數(shù)據(jù)的非空間因素。針對(duì)DBSCAN理大量數(shù)據(jù)的內(nèi)存消耗和對(duì)分布不均數(shù)據(jù)處理的不適應(yīng)，文獻(xiàn) 周水庚, 周傲英, 曹晶. 基于數(shù)據(jù)區(qū)分的DBSCAN算法J. 計(jì)算機(jī)研究與發(fā)展, 2000, 37(10):1153-1159.給出了一種解決方案。將數(shù)據(jù)在主要但分布稀疏程度不均的維度上將數(shù)據(jù)空間劃分為若干區(qū)域，分別計(jì)算各個(gè)區(qū)域的聚類(lèi)密度閾值，以此進(jìn)行聚類(lèi)合并，最后再進(jìn)行全局聚類(lèi)合并。(4) 基于網(wǎng)格的方法基于網(wǎng)格的方法，通過(guò)采用一個(gè)多分辨率的網(wǎng)格數(shù)據(jù)結(jié)構(gòu)，近數(shù)據(jù)空間劃分為有限個(gè)單元，之后所有的處理都是以單個(gè)單元為對(duì)象的。這樣的處理使得算法處理速度很快，

17、處理工作量與數(shù)據(jù)項(xiàng)個(gè)數(shù)無(wú)關(guān)，而與劃分的網(wǎng)格個(gè)數(shù)有關(guān)。STING算法 Wang W,Yang J,Muntz R.STING:A Statistical Information Grid Approach to Spatial Data MiningC In:Proceedings of the 23rd VLDB Conference.Athens,Greece:s.n.,1997:186-195.是傳統(tǒng)的基于網(wǎng)格的算法，它將空間區(qū)域劃分為矩形單元后處理。WaveCluster算法 Sheikholeslami G,Chatterjee S,Zhang A.WaveCluster:A Mult

18、i-Resolution ClusteringApproach forVery Large Spatial DatabasesC In:Proceedings of the 24th VLDB Conference.New York,USA:s.n.,1998:428-439.先在空間上加一多維網(wǎng)格結(jié)構(gòu)匯總數(shù)據(jù)，然后采用小波變換變換元特征空間，在再變換后的空間中尋找密集區(qū)域。2. 現(xiàn)代聚類(lèi)算法隨著科學(xué)技術(shù)的發(fā)展以及待處理數(shù)據(jù)的多元化和數(shù)據(jù)洪流的出現(xiàn)。傳統(tǒng)聚類(lèi)算法盡管不斷自我完善和改進(jìn)，但一些基于新的思想或利潤(rùn)的聚類(lèi)算法亦不斷出現(xiàn)。 (1) 模糊聚類(lèi)1969年，數(shù)據(jù)集模糊劃分 Ruspini H

19、E. A new approach to clustering. Inf Cont., 1969, 15: 2228.的概念被Ruspini首先提出，并首次系統(tǒng)探究了關(guān)于模糊聚類(lèi)的算法，其后的一些學(xué)者也相繼提出了基于模糊關(guān)系的聚類(lèi)算法。但由于當(dāng)數(shù)據(jù)集較大時(shí)，基于模糊關(guān)系的聚類(lèi)算法需要先建立模糊等價(jià)矩陣，計(jì)算量非常大，這類(lèi)方法也就逐漸減少研究了。與此同時(shí)，借助于圖論、動(dòng)態(tài)規(guī)劃、進(jìn)化算法、馬爾科夫隨機(jī)場(chǎng)等技術(shù)，學(xué)者們提出了許多其他的模糊聚類(lèi)算法，其中應(yīng)用最為廣泛的是基于目標(biāo)函數(shù)的聚類(lèi)方法。該方法設(shè)計(jì)簡(jiǎn)單，應(yīng)用范圍廣，本質(zhì)來(lái)說(shuō)可歸結(jié)為較為簡(jiǎn)單的優(yōu)化問(wèn)題。模糊C均值（FCM）算法是基于木變函數(shù)的模糊聚

20、類(lèi)算法的典型代表。自Dumn于1974年發(fā)表后，便被人們不斷完善發(fā)展。FCM算法最早是從硬聚類(lèi)目標(biāo)函數(shù)的優(yōu)化中導(dǎo)出的，通過(guò)將項(xiàng)與對(duì)應(yīng)簇的中心點(diǎn)距離用隸屬平方加權(quán)，將類(lèi)內(nèi)誤差平方和目標(biāo)函數(shù)改寫(xiě)為類(lèi)內(nèi)加權(quán)誤差平方和目標(biāo)函數(shù)，得到了關(guān)于給予目標(biāo)函數(shù)模糊聚類(lèi)的一種大致描述。由于FCM算法的實(shí)用性和數(shù)據(jù)處理效果，對(duì)于此算法的研究有著蓬勃的發(fā)展，目前已經(jīng)形成了龐大的體系。對(duì)于FCM的算法研究和改進(jìn)大致有如下方面：基于目標(biāo)函數(shù)的研究，不同數(shù)據(jù)類(lèi)型的聚類(lèi)，隸屬度約束條件的研究、算法實(shí)現(xiàn)等?；谀繕?biāo)函數(shù)的研究中，2011年，Tsai在文獻(xiàn) Tsai Du-Ming, Lin Chung-Chan. Fuzzy

21、C-means based clustering for linearly and nonlinearly separable data. Pattern Recognition, 2011, 44: 17501760.提出了一種包含距離變量的新居里準(zhǔn)則，在FCM算法和KFCM算法中嘗試應(yīng)用并得到了較好的效果。當(dāng)數(shù)據(jù)并非球體分布式，通過(guò)核函數(shù)改造目標(biāo)函數(shù)中的距離測(cè)度成為了一種解決方案。2010年，Gravest和Pedrycz提出了一種綜合比較分析的模糊核聚類(lèi)算法，在一定程度上解決了非球體分布數(shù)據(jù)的聚類(lèi)問(wèn)題。但核函數(shù)的選擇構(gòu)造及參數(shù)設(shè)定又是一個(gè)新的難題。(2) 量子聚類(lèi)隨著量子力學(xué)理論在實(shí)踐方

22、面的發(fā)展，量子計(jì)算在物理方面的實(shí)現(xiàn)極大地推動(dòng)了量子計(jì)算理論與量子算法的創(chuàng)新。2002年，David Home將量子機(jī)制與聚類(lèi)算法結(jié)合，通過(guò)將數(shù)據(jù)映射到量子空間，構(gòu)建波函數(shù)，測(cè)量勢(shì)能方程來(lái)獲取最終的聚類(lèi)中心，提出了一種量子聚類(lèi)算法 David Horn; Assaf Gottlieb. The Method of Quantum ClusteringJ, Advances in Neural Information Processing Systems,2001:769-776.。2010年曾成、徐紅等人在文獻(xiàn) 曾成,趙錫均,徐紅.基于量子遺傳算法的聚類(lèi)方法C.Proceedings of th

23、e 29th Chinese Control Conference July 29-31,201O Beijing,China.采用量子遺傳算法，將聚類(lèi)問(wèn)題轉(zhuǎn)化為聚類(lèi)中心學(xué)有問(wèn)題，提出了一種基于量子遺傳算法的聚類(lèi)方法。(3) 譜聚類(lèi)譜聚類(lèi) Jain A,Murty M,Flynn P.Data clustering:A ReviewJ. ACM Computing Surveys,1999,31(3):264-323是聚類(lèi)分析中一個(gè)新興且具有生命力的分支，是近年來(lái)國(guó)際上機(jī)器學(xué)習(xí)數(shù)據(jù)挖掘領(lǐng)域的一個(gè)新的研究熱點(diǎn)。譜聚類(lèi)建立在譜圖理論基礎(chǔ)上，克服了傳統(tǒng)聚類(lèi)中對(duì)于樣本空間形狀的局限，以及可能陷入局部最

24、優(yōu)而非全局最優(yōu)的問(wèn)題。譜聚類(lèi)算法本質(zhì)上是將聚類(lèi)問(wèn)題轉(zhuǎn)化為圖的最優(yōu)劃分問(wèn)題，屬于對(duì)點(diǎn)聚類(lèi)算法。但由于以譜圖理論為基礎(chǔ)，要實(shí)現(xiàn)譜聚類(lèi)需要一定的圖論方面的理論知識(shí)基礎(chǔ)。其中主要包括三個(gè)方面：一、圖劃分準(zhǔn)則：包括最小割集準(zhǔn)則、規(guī)范割集準(zhǔn)則、比例割集準(zhǔn)則、平均割集準(zhǔn)則、最小最大割集準(zhǔn)則、多路規(guī)范割集準(zhǔn)則。二、相似矩陣、度矩陣及Laplacian矩陣。 三、勢(shì)函數(shù)、Fiedler向量及譜。譜聚類(lèi)算法大致分為三個(gè)階段。階段一，構(gòu)建矩陣W表示樣本集。階段二，計(jì)算W的前k個(gè)特征值和特征向量，構(gòu)建特征向量空間。階段三，利用K-means或其他經(jīng)典聚類(lèi)算法對(duì)向量空間中的特征向量進(jìn)行聚類(lèi)。不同的譜映射方法和準(zhǔn)則函數(shù)的

25、選擇形成了不同的譜聚類(lèi)算法。在文獻(xiàn) 蔡曉妍, 戴冠中, 楊黎斌. 譜聚類(lèi)算法綜述J. 計(jì)算機(jī)科學(xué), 2008, 35(7):14-18.中，作者將譜聚類(lèi)按使用的劃分準(zhǔn)則分為迭代譜和多路譜兩類(lèi)，并給出了各類(lèi)中典型算法的介紹。迭代譜聚類(lèi)算法中，PF算法 Perona P,Freeman W T.A factorization approach to grouping. H.Burkardt and B.Neumann,eds.Proc.ECCV.1998:655-670于1998年由Perona和Freeman提出，算法通過(guò)用相似矩陣W的第一個(gè)特征向量x1（最大特征值對(duì)應(yīng)的特征向量）進(jìn)行聚類(lèi)。該算

26、法以其簡(jiǎn)單易于實(shí)現(xiàn)的特征引起了學(xué)術(shù)界的廣泛關(guān)注。2000年，美國(guó)學(xué)者Shi和Malik提出了SM算法 Shi J,Malik J.Normalized cuts and image segmentation.IEEE Transactions on Pattern Analysis and Machine Intelligence, 2000,22(8):888-905，該算法中構(gòu)造正規(guī)相似矩陣W代入分割準(zhǔn)則計(jì)算，并且用到了前兩個(gè)特征值對(duì)應(yīng)的特征向量，這樣的改進(jìn)使得SM算法DE聚類(lèi)效果明顯優(yōu)于PF算法。此外，迭代譜聚類(lèi)算法中的典型算法還包括Scott G L.提出的SLH算法 Scott G

27、L,Longuet-Higgins H C.Feature grouping by relocalization of eigenvectors of the proximity matrix. Proc.British Machine Vision Conference.1990:103-108，2000年Kan nan提出的KVV算法 Kannan R,Vempala S,Vetta A.On clusterings-good,bad and spectral.In FOCS,2000:367-377等。早期關(guān)于譜聚類(lèi)的研究者傾向于利用二路劃分準(zhǔn)則通過(guò)迭代方式聚類(lèi)樣本數(shù)據(jù)。但近期研究發(fā)現(xiàn)，

28、選擇多個(gè)特征直接進(jìn)行k路分割會(huì)得到更好的聚類(lèi)效果。2000年，Meila提出了MS算法 Meila M,Shi J.Learning segmentation by random walks.In NIPS,2000:873-879.，此算法以將相似性解釋為馬爾科夫鏈中的隨機(jī)游動(dòng)為基礎(chǔ)，對(duì)MNcut進(jìn)行了概率解釋?zhuān)诖私忉尩目蚣芟逻x擇隨機(jī)游動(dòng)矩陣P的前k個(gè)特征向量構(gòu)造矩陣X，在實(shí)際應(yīng)用中取得了一定的效果。2002年，Ng. Jordan等人提出了NJW算法 Ng A Y,Jordan M I,Weiss Y.On spectral clustering:Analysis and an algo

29、rithm. T.G.Dietterich,S.Becker,and Ghahramani,eds.Advances in Neural Information Processing Systems,Cambridge,MA,MIT Press,2002,14:849-856，選取Laplacican矩陣的前k個(gè)特征向量，在k維空間中生成與原數(shù)據(jù)一一對(duì)應(yīng)的映像，并在此空間中進(jìn)行聚類(lèi)。三、四種主要聚類(lèi)算法的總結(jié)比較上文介紹了很多種聚類(lèi)算法，各個(gè)算法基于不同的理論基礎(chǔ)，算法流程也各不相近，但對(duì)于聚類(lèi)算法的性能評(píng)價(jià)有著比較通用的標(biāo)準(zhǔn)和測(cè)試數(shù)據(jù)集。本節(jié)中筆者首先簡(jiǎn)單介紹聚類(lèi)要求，然后對(duì)目前四種常見(jiàn)的聚

30、類(lèi)算法進(jìn)行總結(jié)和性能比較。1. 評(píng)價(jià)標(biāo)準(zhǔn) 百度百科. 聚類(lèi)算法EB/OL. 2014-5-26. /view/69222.htm#3.(1) 可伸縮性：聚類(lèi)算法在處理小數(shù)據(jù)集合和大規(guī)模數(shù)據(jù)庫(kù)對(duì)象時(shí)，是否具有同樣良好的性能，而不因?yàn)閿?shù)據(jù)量增大導(dǎo)致結(jié)果偏差。(2) 多類(lèi)型數(shù)據(jù)：算法在處理非數(shù)值型數(shù)據(jù)，如二元類(lèi)型，分類(lèi)/標(biāo)稱(chēng)類(lèi)型，序數(shù)類(lèi)型等數(shù)據(jù)時(shí)的性能。(3) 任意形狀性：算法度量是否適用于任意形狀（而非只是球狀）的數(shù)據(jù)集，能夠形成任意形狀的正確聚簇。(4) 參數(shù)依賴(lài)性：聚簇結(jié)果對(duì)參數(shù)的依賴(lài)程度，以及適當(dāng)參數(shù)確定的難度。(5) 抗噪聲性：算法對(duì)于待處理數(shù)據(jù)中

31、孤立點(diǎn)，缺失或者錯(cuò)誤數(shù)據(jù)的敏感程度以及其對(duì)聚簇結(jié)果的影響程度。(6) 順序依賴(lài)性：聚簇結(jié)果對(duì)輸入數(shù)據(jù)的順序是否具有依賴(lài)性。(7) 高維度性：算法對(duì)于待處理數(shù)據(jù)的高維度處理能力。(8) 基于約束：算法是否能處理遇到現(xiàn)實(shí)問(wèn)題時(shí)的額外約束，并給出合理的聚簇結(jié)果。(9)解釋/可用性：算法給出的聚簇結(jié)果應(yīng)該具有在現(xiàn)實(shí)中可以理解使用的特性。2. 四種主要算法的總結(jié)比較本小節(jié)中，筆者將給出當(dāng)前比較主流的四種算法Kmeans、BIRCH、DBSCAN、譜聚類(lèi)中較有代表性的具體算法的總結(jié)性描述，以及基于查閱資料基礎(chǔ)上的性能分析比較，未能通過(guò)編碼及統(tǒng)一的數(shù)據(jù)集進(jìn)行測(cè)試，得出更為客觀有參考性的比較結(jié)果筆者表示很遺憾

32、。(1) K-meansAKHM算法7AKHM算法即改進(jìn)的K-調(diào)和均值算法。關(guān)于K-means的基本特征上文已經(jīng)給出，此處不再贅述。KHM的算法流程為根據(jù)簇均值將數(shù)據(jù)初始分為K個(gè)簇，通過(guò)目標(biāo)函數(shù)和中心移動(dòng)公式對(duì)簇成員和中心點(diǎn)進(jìn)行移動(dòng)，算法迭代執(zhí)行至不再有點(diǎn)移動(dòng)即停止。AKHM對(duì)于傳統(tǒng)KHM（K調(diào)和均值算法）的改進(jìn)，在于使用了新的度量函數(shù)d(x,y)=1-exp(-x-y2)。得到KHM的新的目標(biāo)函數(shù)如下：AKHMX,C=i=1NKj=1K11-exp(-xi-xj2)以及由此計(jì)算出的新的中心更新公式：wj=i=1Nexp(-xi-xj2)(1-exp(-xi-xj2)2(i=1K11-exp(

33、-xi-xj2)2xii=1Nexp(-xi-xj2)(1-exp(-xi-xj2)2(i=1K11-exp(-xi-xj2)2可見(jiàn)式中除了參數(shù)其他都以固定，故的選擇影響了算法性能。文獻(xiàn)7的作者通過(guò)對(duì)三個(gè)數(shù)據(jù)集IRIS、Wine以及Pendisttes進(jìn)行試驗(yàn)，通過(guò)試驗(yàn)結(jié)果得出了針對(duì)不同數(shù)據(jù)的最優(yōu)值。對(duì)于IRIS數(shù)據(jù)集，最優(yōu)=0.1。Wine最優(yōu)=0.00001。Pendisttes最優(yōu)=0.0001。取三種最優(yōu)值是，聚類(lèi)結(jié)果的的誤差平均和均小于KHM，聚類(lèi)精確度不同程度上的優(yōu)于KHM，運(yùn)行時(shí)間和平迭代次數(shù)平均也優(yōu)于KHM。由此，綜合KHM的基本特性，可以得出AKHM對(duì)應(yīng)于評(píng)價(jià)標(biāo)準(zhǔn)的一些特性分

34、析。1 可伸縮性：原文作者在文中指出，用于測(cè)試的數(shù)據(jù)集選擇了離散的較小的數(shù)據(jù)量，盡管驗(yàn)證表明K-means伸縮性較好，但此算法的精確度優(yōu)勢(shì)在應(yīng)用于處理大數(shù)據(jù)的效果并不可得知。2 數(shù)據(jù)結(jié)構(gòu)適應(yīng)性：AKHM由于繼承自K-means，且并未對(duì)樣本數(shù)據(jù)結(jié)構(gòu)的處理能力進(jìn)行優(yōu)化，故仍然主要處理數(shù)值類(lèi)型數(shù)據(jù)。3 參數(shù)依賴(lài)性：AKHM繼承了K-means算法對(duì)參數(shù)K的依賴(lài)，以及本身對(duì)參數(shù)的依賴(lài)。此二者在一定程度上限制了AKHM的通用性和普及性。使得算法的性能依賴(lài)于算法使用者的經(jīng)驗(yàn)而非算法本身。4 抗噪聲性：AKHM具備調(diào)和均值的特性，可以根據(jù)數(shù)據(jù)點(diǎn)特征賦予其不同權(quán)重，抗噪聲性明顯優(yōu)于K-meas算法。5 順序

35、依賴(lài)性：類(lèi)屬于劃分法的AKHM算法對(duì)于數(shù)據(jù)的輸入順序并不敏感。6 高維度性：從實(shí)驗(yàn)數(shù)據(jù)結(jié)果可知對(duì)于13維的數(shù)據(jù)集Wine和16維的數(shù)據(jù)集Pendisttes，AKHM算法均能得到比較理想的聚類(lèi)效果。7 可解釋/可用性：同樣基于實(shí)驗(yàn)結(jié)果精度可知此算法具有較強(qiáng)的可解釋和可用性。(2)BIRCH一種改進(jìn)的BIRCH聚類(lèi)算法26BIRCH算法屬于層次聚類(lèi)法的代表算法。BIRCH算法以及文獻(xiàn)26中的改進(jìn)策略在上文中已有詳述，此處再做回顧以便于說(shuō)明算法性能。BIRCH算法主要有四個(gè)階段。第一階段掃描待聚類(lèi)的所有數(shù)據(jù)項(xiàng)，根據(jù)初始閾值T初始化一顆CF樹(shù)。第二階段采用聚合思路，通過(guò)增加閾值T重建CF樹(shù)，使其聚合

36、度上升。第三、四階段，對(duì)已有的CF樹(shù)實(shí)行全局聚類(lèi)以得到更好的聚類(lèi)效果。文獻(xiàn)26中對(duì)于BIRCH算法有兩方面改進(jìn)。一是分類(lèi)屬性的處理，而是閾值T的設(shè)定規(guī)則。關(guān)于分類(lèi)屬性的處理，文中將CF結(jié)構(gòu)改為SCF。SCF=（N，Summary），N是聚類(lèi)中數(shù)據(jù)點(diǎn)的個(gè)數(shù)，Summary包含數(shù)據(jù)點(diǎn)的數(shù)字屬性和分類(lèi)屬性。由此改進(jìn)了BIRCH算法只能處理數(shù)值型數(shù)據(jù)的局限。結(jié)構(gòu)基于T的定義可知，其值與組內(nèi)平均距離和組件平均距離，及數(shù)據(jù)的分布有關(guān)。因此，初始閾值T，可以采用如下公式計(jì)算得出。在數(shù)據(jù)集中隨機(jī)選取N對(duì)數(shù)據(jù)，計(jì)算每對(duì)數(shù)據(jù)間的距離di，計(jì)算N對(duì)數(shù)據(jù)間距離的數(shù)學(xué)期望Ex和方差Dx。初始化CF樹(shù)的T值為，T=P*（

37、Ex+0.25*Dx）。P為事先設(shè)定的百分比。在算法第二階段，T的提升規(guī)則這是增大公式中的P值。這一算法的改進(jìn)提升了原本算法的平均聚類(lèi)精度和聚類(lèi)效率，改進(jìn)了BIRCH算法的性能。文獻(xiàn)26的作者通過(guò)將改進(jìn)后的BIRCH算法與K-means和K-modes算法的綜合算法K-prototypes進(jìn)行對(duì)比，使用三個(gè)數(shù)據(jù)集Mushroom，Congressional Votes和KDDCUP99的10%數(shù)據(jù)子集（包含條記錄）進(jìn)行測(cè)試對(duì)比了聚類(lèi)精度，在測(cè)試時(shí)調(diào)整了調(diào)整了BIRCH的參數(shù)P和B、L（葉/非葉節(jié)點(diǎn)的條目個(gè)數(shù)），達(dá)到的最優(yōu)聚類(lèi)效果的平均算法進(jìn)度分別高出K-prototypes算法4%，22%，3

38、%。下邊同樣給出改進(jìn)了的BIRCH算法對(duì)應(yīng)于評(píng)價(jià)標(biāo)準(zhǔn)的一些特性分析。1 可伸縮性：從實(shí)驗(yàn)數(shù)據(jù)以計(jì)算法特征可知，BIRCH算法具有良好的處理大量數(shù)據(jù)的能力。2 數(shù)據(jù)結(jié)構(gòu)適應(yīng)性：文獻(xiàn)26中對(duì)于CF結(jié)構(gòu)的調(diào)整即使BIRCH算法的數(shù)據(jù)結(jié)構(gòu)適應(yīng)性增強(qiáng)，對(duì)于車(chē)司機(jī)中非數(shù)值型的數(shù)據(jù)也能有較好地處理。3 參數(shù)依賴(lài)性：改進(jìn)的BIRCH算法依賴(lài)于因子P的設(shè)定，同時(shí)還與B、L有關(guān)，這些參數(shù)均只能通過(guò)反復(fù)測(cè)試即經(jīng)驗(yàn)的得出，降低了算法的非監(jiān)督特性。4 抗噪聲性： BIRCH算法本身的第三、四階段全局優(yōu)化時(shí)，會(huì)舍棄包含過(guò)少數(shù)據(jù)點(diǎn)的聚簇，對(duì)噪聲有一定的抵抗能力。5 順序依賴(lài)性：由于BIRCH算法在一次掃面數(shù)據(jù)既建成初始CF

39、樹(shù)，故數(shù)據(jù)的在CF的不同狀態(tài)時(shí)輸入可能會(huì)被插入不同的位置，此算法的順序依賴(lài)性較嚴(yán)重。6 高維度性：有實(shí)驗(yàn)數(shù)據(jù)得知BIRCH算法對(duì)于維度高的數(shù)據(jù)聚類(lèi)結(jié)果較差。7 解釋/可用性：通過(guò)對(duì)三個(gè)測(cè)試集的得到平均聚類(lèi)精度均高于90%的結(jié)果可知，此算法的解釋/可用性很好。(3) DBSCANIDBSCAN9DBSCAN是基于密度的空間聚類(lèi)算法，算法的基本流程為從任意對(duì)象P開(kāi)始根據(jù)閾值和參數(shù)通過(guò)廣度優(yōu)先搜索提取從P密度可達(dá)的所有對(duì)象，得到一個(gè)聚類(lèi)。若P是核心對(duì)象，則可以一次標(biāo)記相應(yīng)對(duì)象為當(dāng)前類(lèi)并對(duì)此類(lèi)內(nèi)的項(xiàng)進(jìn)行密度可達(dá)擴(kuò)展，所有密度可達(dá)的項(xiàng)均被標(biāo)記為p所在類(lèi)，重復(fù)此過(guò)程直到不再有新的項(xiàng)被納入此類(lèi)。然后再選擇一

40、個(gè)新的對(duì)象重復(fù)上述過(guò)程。若P是邊界對(duì)象，則將其標(biāo)記為噪聲。重復(fù)上述過(guò)程直到所有項(xiàng)被標(biāo)記如某一類(lèi)或者噪聲，即得到聚類(lèi)結(jié)果。文獻(xiàn)9中，作者提出了DBSCAN的幾點(diǎn)不足，如密集數(shù)據(jù)時(shí)選取的無(wú)意義的種子對(duì)象過(guò)多導(dǎo)致算法效率低內(nèi)存占用率大，以及對(duì)于非空間因素考慮不全面。針對(duì)這兩個(gè)問(wèn)題作者提出了IDBSCAN算法。對(duì)于前者問(wèn)題，作者給出的解決方案是以初始點(diǎn)P為圓心，密度可達(dá)距離為半徑原，以P為原點(diǎn)做坐直角坐標(biāo)系，并畫(huà)出I, III和II, IV象限的角平分線(xiàn)與圓的交點(diǎn)，每個(gè)象限內(nèi)選取離該象限三個(gè)邊界對(duì)象最近的至多8個(gè)點(diǎn)作為種子對(duì)象進(jìn)行擴(kuò)展，這樣很好地解決了冗余查詢(xún)問(wèn)題。對(duì)于非空間因素的問(wèn)題則提出了純度（領(lǐng)

41、域內(nèi)相同非空間屬性的對(duì)象個(gè)數(shù)與領(lǐng)域內(nèi)所有對(duì)象的比值），以此為基礎(chǔ)提出了純核心對(duì)象，純直接密度可達(dá)等概念，同時(shí)給出了直接密度可達(dá)構(gòu)造的聚簇與純密度可達(dá)構(gòu)造聚簇的關(guān)系，已解決非空間因素考慮不足的問(wèn)題。在算法性能驗(yàn)證方面，文章作者將DBSCAN算法與IDBSCAN算法用為測(cè)試密度聚類(lèi)而構(gòu)造的數(shù)據(jù)集進(jìn)行聚類(lèi)測(cè)試。測(cè)試結(jié)果現(xiàn)實(shí)，在空間屬性接近而非空間屬性不同的區(qū)域中，IDESCAN算法準(zhǔn)確的將其聚類(lèi)為兩類(lèi)，而DBSCAN算法則并未識(shí)別直接將其聚為一類(lèi)。在執(zhí)行效率方面，作者將模擬數(shù)據(jù)集的對(duì)象個(gè)數(shù)從20000漸增到，IDBSCAN算法的效率性能明顯優(yōu)于DBSCAN算法。從算法評(píng)價(jià)標(biāo)準(zhǔn)來(lái)看：1 可伸縮性： I

42、DBSCAN對(duì)于大量數(shù)據(jù)的處理能力優(yōu)于DBSCAN，但由于基于密度的算法的自身特性，考慮到內(nèi)存占用和算法效率，這類(lèi)算法并不適于過(guò)大規(guī)模的數(shù)據(jù)處理。2 任意形狀性：IDBSCAN對(duì)于空間屬性的處理方式使其有著較好的對(duì)數(shù)據(jù)形狀的適應(yīng)性。但主要應(yīng)用于處理球面數(shù)據(jù)。3 參數(shù)依賴(lài)性：聚簇效果依賴(lài)于參數(shù)：半徑。4 抗噪聲性：基于密度算法會(huì)舍棄獨(dú)立點(diǎn)，具有良好的抗噪聲性。5 順序依賴(lài)性：根據(jù)密度聚類(lèi)，對(duì)于數(shù)據(jù)的輸入順序不敏感。6 高維度性：根據(jù)實(shí)驗(yàn)數(shù)據(jù)得出結(jié)論，算法在處理數(shù)據(jù)方面性能略差。7 解釋/可用性：改進(jìn)后的IDBSCAN算法考慮了數(shù)據(jù)的非空間特征，使得聚類(lèi)結(jié)果更為合理。(4) 譜聚類(lèi)NJW算法24NJW算法是譜聚類(lèi)算法中多路譜聚類(lèi)方法的一個(gè)代表算法。它的基本算法流程為：首先將待分類(lèi)數(shù)據(jù)構(gòu)成一個(gè)有權(quán)無(wú)向圖，圖的定點(diǎn)為數(shù)據(jù)點(diǎn)，邊的權(quán)重為數(shù)據(jù)點(diǎn)間的相似度。然后將此圖轉(zhuǎn)化為L(zhǎng)aplacian矩陣。計(jì)算矩陣的前k個(gè)特征向量，構(gòu)建向量空間并將其行向量變換為單位向量。此時(shí)向量空間中的特征向量與原數(shù)據(jù)存在一一對(duì)應(yīng)關(guān)系。在特征向量空間中利用K-means等聚類(lèi)算法進(jìn)行聚類(lèi)。當(dāng)向量空間中第i行被劃分到某一聚類(lèi)中，其對(duì)應(yīng)的原數(shù)據(jù)點(diǎn)便被標(biāo)記為該類(lèi)。在算法性能方面NJW算法選擇了更多特征向量，并直接計(jì)