聚類分析又稱群分析，它是研究（樣品或指標(biāo)）分類問題的一種統(tǒng)計(jì)分析方法，同時(shí)也是數(shù)據(jù)挖掘的一個(gè)重要算法。

聚類（Cluster）分析是由若干模式（Pattern）組成的，通常，模式是一個(gè)度量（Measurement）的向量，或者是多維空間中的一個(gè)點(diǎn)。

聚類分析以相似性為基礎(chǔ)，在一個(gè)聚類中的模式之間比不在同一聚類中的模式之間具有更多的相似性。

在商業(yè)上，聚類可以幫助市場(chǎng)分析人員從消費(fèi)者數(shù)據(jù)庫中區(qū)分出不同的消費(fèi)群體來，并且概括出每一類消費(fèi)者的消費(fèi)模式或者說習(xí)慣。它作為數(shù)據(jù)挖掘中的一個(gè)模塊，可以作為一個(gè)單獨(dú)的工具以發(fā)現(xiàn)數(shù)據(jù)庫中分布的一些深層的信息，并且概括出每一類的特點(diǎn)，或者把注意力放在某一個(gè)特定的類上以作進(jìn)一步的分析；并且，聚類分析也可以作為數(shù)據(jù)挖掘算法中其他分析算法的一個(gè)預(yù)處理步驟。

聚類分析的算法可以分為劃分法（Partitioning Methods）、層次法（Hierarchical Methods）、基于密度的方法（density－based methods）、基于網(wǎng)格的方法（grid－based methods）、基于模型的方法（Model－Based Methods）。

聚類要求

1、可伸縮性

許多聚類算法在小于 200 個(gè)數(shù)據(jù)對(duì)象的小數(shù)據(jù)集合上工作得很好；但是，一個(gè)大規(guī)模數(shù)據(jù)庫可能包含幾百萬個(gè)對(duì)象，在這樣的大數(shù)據(jù)集合樣本上進(jìn)行聚類可能會(huì)導(dǎo)致有偏的結(jié)果。

2、不同屬性

許多算法被設(shè)計(jì)用來聚類數(shù)值類型的數(shù)據(jù)。但是，應(yīng)用可能要求聚類其他類型的數(shù)據(jù)，如二元類型（binary），分類／標(biāo)稱類型（categorical／nominal），序數(shù)型（ordinal）數(shù)據(jù)，或者這些數(shù)據(jù)類型的混合。

3、任意形狀

許多聚類算法基于歐幾里得或者曼哈頓距離度量來決定聚類。基于這樣的距離度量的算法趨向于發(fā)現(xiàn)具有相近尺度和密度的球狀簇。但是，一個(gè)簇可能是任意形狀的。提出能發(fā)現(xiàn)任意形狀簇的算法是很重要的。

4、領(lǐng)域最小化

許多聚類算法在聚類分析中要求用戶輸入一定的參數(shù)，例如希望產(chǎn)生的簇的數(shù)目。聚類結(jié)果對(duì)于輸入?yún)��?shù)十分敏感。參數(shù)通常很難確定，特別是對(duì)于包含高維對(duì)象的數(shù)據(jù)集來說。這樣不僅加重了用戶的負(fù)擔(dān)，也使得聚類的質(zhì)量難以控制。

5、處理“噪聲”

絕大多數(shù)現(xiàn)實(shí)中的數(shù)據(jù)庫都包含了孤立點(diǎn)，缺失，或者錯(cuò)誤的數(shù)據(jù)。一些聚類算法對(duì)于這樣的數(shù)據(jù)敏感，可能導(dǎo)致低質(zhì)量的聚類結(jié)果。

6、記錄順序

一些聚類算法對(duì)于輸入數(shù)據(jù)的順序是敏感的。例如，同一個(gè)數(shù)據(jù)集合，當(dāng)以不同的順序交給同一個(gè)算法時(shí)，可能生成差別很大的聚類結(jié)果。開發(fā)對(duì)數(shù)據(jù)輸入順序不敏感的算法具有重要的意義。

7、高維度

（high dimensionality）

一個(gè)數(shù)據(jù)庫或者數(shù)據(jù)倉庫可能包含若干維或者屬性。許多聚類算法擅長處理低維的數(shù)據(jù)，可能只涉及兩到三維。人類的眼睛在最多三維的情況下能夠很好地判斷聚類的質(zhì)量。在高維空間中聚類數(shù)據(jù)對(duì)象是非常有挑戰(zhàn)性的，特別是考慮到這樣的數(shù)據(jù)可能分布非常稀疏，而且高度偏斜。

8、基于約束

現(xiàn)實(shí)世界的應(yīng)用可能需要在各種約束條件下進(jìn)行聚類。假設(shè)你的工作是在一個(gè)城市中為給定數(shù)目的自動(dòng)提款機(jī)選擇安放位置，為了作出決定，你可以對(duì)住宅區(qū)進(jìn)行聚類，同時(shí)考慮如城市的河流和公路網(wǎng)，每個(gè)地區(qū)的客戶要求等情況。要找到既滿足特定的約束，又具有良好聚類特性的數(shù)據(jù)分組是一項(xiàng)具有挑戰(zhàn)性的任務(wù)。

9、解釋性－可用性

用戶希望聚類結(jié)果是可解釋的，可理解的，和可用的。也就是說，聚類可能需要和特定的語義解釋和應(yīng)用相聯(lián)系。應(yīng)用目標(biāo)如何影響聚類方法的選擇也是一個(gè)重要的研究課題。

記住這些約束，我們對(duì)聚類分析的學(xué)習(xí)將按如下的步驟進(jìn)行。首先，學(xué)習(xí)不同類型的數(shù)據(jù)，以及它們對(duì)聚類方法的影響。接著，給出了一個(gè)聚類方法的一般分類。然后我們?cè)敿?xì)地討論了各種聚類方法，包括劃分方法，層次方法，基于密度的方法，基于網(wǎng)格的方法，以及基于模型的方法。最后我們探討在高維空間中的聚類和孤立點(diǎn)分析（outlier analysis）。

算法分類

很難對(duì)聚類方法提出一個(gè)簡潔的分類，因?yàn)檫@些類別可能重疊，從而使得一種方法具有幾類的特征，盡管如此，對(duì)于各種不同的聚類方法提供一個(gè)相對(duì)有組織的描述依然是有用的，為聚類分析計(jì)算方法主要有如下幾種：

1、劃分法

劃分法（partitioning methods），給定一個(gè)有N個(gè)元組或者紀(jì)錄的數(shù)據(jù)集，分裂法將構(gòu)造K個(gè)分組，每一個(gè)分組就代表一個(gè)聚類，K＜N。而且這K個(gè)分組滿足下列條件：

（1） 每一個(gè)分組至少包含一個(gè)數(shù)據(jù)紀(jì)錄；

（2）每一個(gè)數(shù)據(jù)紀(jì)錄屬于且僅屬于一個(gè)分組（注意：這個(gè)要求在某些模糊聚類算法中可以放寬）；

對(duì)于給定的K，算法首先給出一個(gè)初始的分組方法，以后通過反復(fù)迭代的方法改變分組，使得每一次改進(jìn)之后的分組方案都較前一次好，而所謂好的標(biāo)準(zhǔn)就是：同一分組中的記錄越近越好，而不同分組中的紀(jì)錄越遠(yuǎn)越好。

大部分劃分方法是基于距離的。給定要構(gòu)建的分區(qū)數(shù)k，劃分方法首先創(chuàng)建一個(gè)初始化劃分。然后，它采用一種迭代的重定位技術(shù)，通過把對(duì)象從一個(gè)組移動(dòng)到另一個(gè)組來進(jìn)行劃分。一個(gè)好的劃分的一般準(zhǔn)備是：同一個(gè)簇中的對(duì)象盡可能相互接近或相關(guān)，而不同的簇中的對(duì)象盡可能遠(yuǎn)離或不同。還有許多評(píng)判劃分質(zhì)量的其他準(zhǔn)則。傳統(tǒng)的劃分方法可以擴(kuò)展到子空間聚類，而不是搜索整個(gè)數(shù)據(jù)空間。當(dāng)存在很多屬性并且數(shù)據(jù)稀疏時(shí)，這是有用的。為了達(dá)到全局最優(yōu)，基于劃分的聚類可能需要窮舉所有可能的劃分，計(jì)算量極大。實(shí)際上，大多數(shù)應(yīng)用都采用了流行的啟發(fā)式方法，如k－均值和k－中心算法，漸近的提高聚類質(zhì)量，逼近局部最優(yōu)解。這些啟發(fā)式聚類方法很適合發(fā)現(xiàn)中小規(guī)模的數(shù)據(jù)庫中小規(guī)模的數(shù)據(jù)庫中的球狀簇。為了發(fā)現(xiàn)具有復(fù)雜形狀的簇和對(duì)超大型數(shù)據(jù)集進(jìn)行聚類，需要進(jìn)一步擴(kuò)展基于劃分的方法。

使用這個(gè)基本思想的算法有：K－MEANS算法、K－MEDOIDS算法、CLARANS算法；

2、層次法

層次法（hierarchical methods），這種方法對(duì)給定的數(shù)據(jù)集進(jìn)行層次似的分解，直到某種條件滿足為止。具體又可分為“自底向上”和“自頂向下”兩種方案。

例如，在“自底向上”方案中，初始時(shí)每一個(gè)數(shù)據(jù)紀(jì)錄都組成一個(gè)單獨(dú)的組，在接下來的迭代中，它把那些相互鄰近的組合并成一個(gè)組，直到所有的記錄組成一個(gè)分組或者某個(gè)條件滿足為止。

層次聚類方法可以是基于距離的或基于密度或連通性的。層次聚類方法的一些擴(kuò)展也考慮了子空間聚類。層次方法的缺陷在于，一旦一個(gè)步驟（合并或分裂）完成，它就不能被撤銷。這個(gè)嚴(yán)格規(guī)定是有用的，因?yàn)椴挥脫?dān)心不同選擇的組合數(shù)目，它將產(chǎn)生較小的計(jì)算開銷。然而這種技術(shù)不能更正錯(cuò)誤的決定。已經(jīng)提出了一些提高層次聚類質(zhì)量的方法。

代表算法有：BIRCH算法、CURE算法、CHAMELEON算法等；

3、密度算法

基于密度的方法（density－based methods），基于密度的方法與其它方法的一個(gè)根本區(qū)別是：它不是基于各種各樣的距離的，而是基于密度的。這樣就能克服基于距離的算法只能發(fā)現(xiàn)“類圓形”的聚類的缺點(diǎn)。

這個(gè)方法的指導(dǎo)思想就是，只要一個(gè)區(qū)域中的點(diǎn)的密度大過某個(gè)閾值，就把它加到與之相近的聚類中去。

代表算法有：DBSCAN算法、OPTICS算法、DENCLUE算法等；

4、圖論聚類法

圖論聚類方法解決的第一步是建立與問題相適應(yīng)的圖，圖的節(jié)點(diǎn)對(duì)應(yīng)于被分析數(shù)據(jù)的最小單元，圖的邊（或�。�對(duì)應(yīng)于最小處理單元數(shù)據(jù)之間的相似性度量。因此，每一個(gè)最小處理單元數(shù)據(jù)之間都會(huì)有一個(gè)度量表達(dá)，這就確保了數(shù)據(jù)的局部特性比較易于處理。圖論聚類法是以樣本數(shù)據(jù)的局域連接特征作為聚類的主要信息源，因而其主要優(yōu)點(diǎn)是易于處理局部數(shù)據(jù)的特性。

5、網(wǎng)格算法

基于網(wǎng)格的方法（grid－based methods），這種方法首先將數(shù)據(jù)空間劃分成為有限個(gè)單元（cell）的網(wǎng)格結(jié)構(gòu)，所有的處理都是以單個(gè)的單元為對(duì)象的。這么處理的一個(gè)突出的優(yōu)點(diǎn)就是處理速度很快，通常這是與目標(biāo)數(shù)據(jù)庫中記錄的個(gè)數(shù)無關(guān)的，它只與把數(shù)據(jù)空間分為多少個(gè)單元有關(guān)。

代表算法有：STING算法、CLIQUE算法、WAVE－CLUSTER算法；

6、模型算法

基于模型的方法（model－based methods），基于模型的方法給每一個(gè)聚類假定一個(gè)模型，然后去尋找能夠很好的滿足這個(gè)模型的數(shù)據(jù)集。這樣一個(gè)模型可能是數(shù)據(jù)點(diǎn)在空間中的密度分布函數(shù)或者其它。它的一個(gè)潛在的假定就是：目標(biāo)數(shù)據(jù)集是由一系列的概率分布所決定的。

通常有兩種嘗試方向：統(tǒng)計(jì)的方案和神經(jīng)網(wǎng)絡(luò)的方案。