聚類方法及原理介紹(文檔)

將物理或抽象對象的集合分組成為有類似的對象組成的多個簇的過程被稱為聚類。由聚類所生成的簇是一組數(shù)據(jù)對象的集合，這些對象與同一個簇中的對象彼此相似，與其它簇中的對象相異。在許多應用中，可以將一個簇中的數(shù)據(jù)對象作為一個整體來對待。目前在文獻中存在大量的聚類算法。算法的選擇取決于數(shù)據(jù)的類型、聚類的目的和應用。如果聚類分析備用作描述或探查的工具，可以對同樣的數(shù)據(jù)嘗試多種算法，以發(fā)現(xiàn)數(shù)據(jù)可能揭示的結(jié)果。大體上，主要的聚類技術(shù)可以劃分為如下幾類：劃分方法給定一個個對象或元組的數(shù)據(jù)庫，一個劃分方法構(gòu)建數(shù)據(jù)的k個劃分，每個劃分表示一個聚簇，并且k每個組至少包含一個對象；每個對象必須屬于且只屬于一個組。給定要構(gòu)建的劃分數(shù)目k,劃分方法首先創(chuàng)建一個初始劃分。然后采用一種迭代的重定位技術(shù)，嘗試通過對象在劃分間移動來改進劃分。一個好的劃分的一般準則是：在同一類中的對象之間盡可能“接近”或相關(guān),而不同類中的對象之間盡可能“遠離”或不同。還有許多其它劃分質(zhì)量評判準則。為了達到全局最優(yōu),基于劃分的聚類會要求窮舉三所有可能的劃分。實際上,絕大多數(shù)應用采用了以下兩個比較流行的啟發(fā)式方法：(1)聚于質(zhì)心的技術(shù)：k-平均方法k-平均算法以k為參數(shù)，把n個對象分為k個簇，以使簇內(nèi)具有較高的相似度，而簇間的相似度較低。相似度的計算根據(jù)一個簇中對象的平均值（被看作簇的重心）來進行。k-平均算法的處理流程如下。首先，隨機地選擇個對象，每個對象初始地代表一個簇的平均值或中心。對剩余的每個對象，根據(jù)其與各個簇中心的距離，將它賦給最近的簇。然后重新計算每個簇的平均值。這個過程不斷重復，直到準則函數(shù)收斂。通常采用平方誤差準、、 e=EE\p~m^則，其定義如下：（2T）這里的E是數(shù)據(jù)庫中所有對象的平方誤差的總和，是空間的點，表示給定的數(shù)據(jù)對象，mi是簇Ci的平均值（p和mi都是多維的）。這個準則是使圖生成的結(jié)果簇盡可能的緊湊和獨立。例1假設(shè)有一個分布在空間中的對象集合，如圖2－1所示。給定k=3，即要求將這些對象聚類為三個簇。根據(jù)^平均算法，我們?nèi)我膺x擇三個對象作為初始簇的中心，簇中心在圖中用“＋”來標示。根據(jù)與簇中心的距離，每個對象分配給離其最近的一個簇。這樣分布形成如圖a中所繪的圖形。這樣的分組會改變聚類的中心，也就是說，每個聚類的平均值會根據(jù)類中的對象重新計算。依據(jù)這些新的聚類中心，對象被重新分配到各個類中。這樣重新分配形成了圖b中描繪的輪廓。以上的過程重復產(chǎn)生了圖c的情況。最后，當沒有對象重新分配發(fā)生時，處理過程結(jié)束，聚類的結(jié)果被返回。圖2-1基于K-means方法的一組對象的聚類這個算法嘗試找出是平方誤差函數(shù)值最小的K個劃分，當結(jié)果簇是密集的，而簇與簇之間區(qū)別明顯時，它的效果較好。對處理大數(shù)據(jù)集，該算法是相對可仲縮的和高效率的，因為它的復雜程度是0（nkt）。其中，n是所有對象的數(shù)目，k是簇的數(shù)目，t是迭代的數(shù)目。通常的，k但是，k-平均方法只有在簇的平均值被定義的情況下使用。這可能不適應某些應用。例如涉及有分類屬性的數(shù)據(jù)。要求用戶必須事先給出k（要生成的簇的數(shù)目）可能算是該方法的一個缺點。K-平均方法不適合于發(fā)現(xiàn)非凸面形狀的簇，或者大小差別很大的簇，并且，它對于“噪聲”和孤立點數(shù)據(jù)很敏感，少量的該類數(shù)據(jù)能夠?qū)ζ骄诞a(chǎn)生很大影響。（2）基于有代表性的對象的技術(shù)k-中心點方法采用簇中位置最中心的對象，作為參照點即中心點，這樣劃分依然是基于最小化所有對象與參照點之間的相異度之和的原則來執(zhí)行的。這是k-中心點的基礎(chǔ)。它的基本策略是：首先為每個簇隨意選擇一個代表對象；剩余對象根據(jù)與代表對象的距離分配給最近的一個簇。然后反復用非代表對象代替代表對象，以改進聚類的質(zhì)量。聚類結(jié)果的質(zhì)量用一個代價函數(shù)來估算，該函數(shù)度量對象與參照對象之間的平均相異度。為了判定一個非代表對象是否是當前一個代表對象的好的替代，對于每一個非中心點對象p,下面的四種情況被考慮：第一種情況：p當前隸屬于中心點Oj。如果Oj被Orandom所代替作為中心點，且p離一個Oi最近，iHj,那么p被重新分配給Oi.第二種情況:p當前隸屬于中心點Oj.如果Oj被Orandom代替作為中心點，且p離Orandom最近，那么p被重新分配給Orandom。第三種情況：p當前隸屬于中心點Oi,i#jo如果Oj被Orandom代替作為一個中心點，而p依然離Oi最近，那么對象的隸屬不發(fā)生變化。第四種情況：p當前隸屬于中心點Oi,iHj。如果Oj被Orandom代替作為一個中心點，且p離Orandom最近，那么p被重新分配給Orandom。圖2－2描述了上述四種情況。每當重新分配發(fā)生時,平方誤差E所產(chǎn)生的差別對代價函數(shù)有影響。因此一個當前的中心點對象被非中心點所代替,代價函數(shù)計算平方－誤差值所產(chǎn)生的差別。替代的總代價使所有非中心點對象所產(chǎn)生的代價之和。如果總代價是負的,那么實際的平方一誤差將會減小，Oj可以被Orandom代替。如果總代價是正的，則當前中心點Oj被認為是可以接受的，在本次迭代中沒有變化發(fā)生。一個典型的k-中心點算法描述在圖2-2中給出。圖2-2K-中心點聚類代價函數(shù)的四種情況“那個方法更健壯：k-平均或者k-中心點？”當存在“噪聲”和孤立點數(shù)據(jù)時，k-中心點比k-平均更健壯，這是因為中心點不像平均值那樣容易受到極端數(shù)據(jù)影響。但是，k-中心點的執(zhí)行代價比k-平均方法高.這些啟發(fā)式方法對中小規(guī)模的數(shù)據(jù)庫中發(fā)現(xiàn)球狀簇很實用。為了對大規(guī)模的數(shù)據(jù)集進行聚類，以及處理復雜形狀的聚類，基于劃分的方法需要進一步的擴展。層次的方法一個層次的聚類方法將數(shù)據(jù)對象組成一棵聚類的樹。根據(jù)層次分解是自底向上的還是自頂向下形成的，層次的聚類方法可以進一步分為凝聚的（agglomerative）和分裂的（divisive）層次聚類。（1）凝聚的層次聚類：這種自底向上的策略首先將每個對象作為單獨的一個簇，然后和并這些原子簇為越來越大的簇，直到所有的對像都在一個簇中，或者達到某個終止條件。（2）分裂的層次聚類：這種自頂向下的策略與凝聚的層次聚類相反，它首先將所有的對象置于一個簇中。然后逐漸細分為越來越小的簇，直到每個對象在單獨的一個簇中，或者達到一個終止條件，例如打到了某個希望的簇數(shù)目后者兩個簇之間的距離超過了某個閥值。例2圖2—3描述了一個凝聚的層次聚類方法AGNES(AgglomerativeNESting)和一個分裂的層次聚類方法DIANA(DivisiveAnalysis)在一個包含五個對象的數(shù)據(jù)集合{a,b,c,d,e}上的處理過程。最初AGNES將每個對象作為一個簇，然后這些簇根據(jù)某些準則一步步合并。例如，如果簇C1中的一個對象和簇C2中的一個對象之間的距離使所有屬于不同簇的對象間歐式距離最小的，C1和C2可能被合并。其每個簇可以被簇中所有對象代表，兩個簇間的相似度由兩個不同簇中距離最近的數(shù)據(jù)點對的相似度來確定。聚類的合并過程反復進行直到所有對象最終合并為一個簇。步0步1abbabcdecdeddee分換的劌步1步步0步1abbabcdecdeddee分換的劌步1步o耀星的(ANGNES5<DIA1^A>圖2-3在對象集合(a,b,c,d)上的凝聚與分裂層次聚類在DIANA方法處理過程中，所有的對象都放在一個簇中。根據(jù)些原則(如簇中最鄰近的對象的最大歐氏距離)，將該簇分裂。簇的分裂過程反復進行，直到最終每個新的簇只包含一個對象。層次聚類方法盡管簡單，但經(jīng)常會遇到合并或分裂點選擇的困難。這樣的選擇是非常關(guān)鍵的，因為一旦一組對象(合并或分裂)完成，它就不能被撤銷，下一步的處理將在新完成的簇上進行。這個嚴格規(guī)定是有用的，由于不用擔心組合數(shù)目的不同選擇，計算代價會比較小。但是，已做的處理不能被撤消，聚類之間也不能交換對象。如果在某一步?jīng)]有很好的選擇合并或分裂的決定，可能會導致低質(zhì)量的聚類結(jié)果。而且，這種聚類不具有很好的可伸縮性。因為合并或分裂的決定需要檢查和估算大量的對象或結(jié)果。改進層次方法的聚類質(zhì)量的一個有希望的方向是將層次聚類和其他聚類技術(shù)集成。有兩種方法可以改進層次聚類的結(jié)果：在每層劃分中，仔細分析對象間的“聯(lián)接”，例如CURE和Chameleon中的做法。綜合層次凝聚和迭代的重定位方法。首先用自底向上的層次算法，然后用迭代的重定位來改進結(jié)果。例如BIRCH中的方法?；诿芏鹊姆椒ń^大多數(shù)劃分方法給予對象之間的距離進行聚類。這樣的方法只能發(fā)現(xiàn)球狀的簇，而在發(fā)現(xiàn)任意形狀的簇上遇到了困難。隨之提出了基于密度的聚類方法，它是將簇看作是數(shù)據(jù)空間中被低密度區(qū)域分割開的高密度區(qū)域。其主要思想是：只要鄰近區(qū)域的密度(對象或數(shù)據(jù)點的數(shù)目)超出了某個閥值，就繼續(xù)聚類。也就是說，對給定類中的每個數(shù)據(jù)點，在一個給定范圍的區(qū)域中必須至少某個數(shù)目的點。這樣的方法可以用來過濾“噪聲”孤立點數(shù)據(jù)，發(fā)現(xiàn)任意形狀的簇。DBSCAN是一個有代表性的基于密度的方法，它根據(jù)一個密度閥值來控制簇的增長。OPTICS是另一個基于密度的方法，它為自動的和交互的聚類分析計算一個聚類順序。基于網(wǎng)格的方法基于網(wǎng)格的方法把對象空間量化為有限數(shù)目的單元，形成一個網(wǎng)格結(jié)構(gòu)。所有的聚類操作都在這個網(wǎng)格結(jié)構(gòu)（即量化的空間）上進行。這種方法的主要優(yōu)點是處理速度快，其處理時間獨立與數(shù)據(jù)對象的數(shù)目，只與量化空間中的每一維的單元數(shù)目有關(guān)?；诰W(wǎng)格方法的有代表性的例子：STING,它利用存儲在網(wǎng)格單元中的統(tǒng)計信息；WaveC