聚類(lèi)的目標是使同一類(lèi)對象的相似度盡可能地??；不同類(lèi)對象之間的相似度盡可能地大。目前聚類(lèi)的方法很多，根據基本思想的不同，大致可以將聚類(lèi)算法分為五大類(lèi)：層次聚類(lèi)算法、分割聚類(lèi)算法、基于約束的聚類(lèi)算法、機器學(xué)習中的聚類(lèi)算法和用于高維度的聚類(lèi)算法。摘自 數據挖掘中的聚類(lèi)分析研究綜述 這篇論文。

1、層次聚類(lèi)算法

1.1聚合聚類(lèi)

1.1.1相似度依據距離不同：Single-Link:最近距離、Complete-Link：最遠距離、Average-Link：平均距離

1.1.2最具代表性算法

1）CURE算法

特點(diǎn)：固定數目有代表性的點(diǎn)共同代表類(lèi)

優(yōu)點(diǎn)：識別形狀復雜，大小不一的聚類(lèi)，過(guò)濾孤立點(diǎn)

2）ROCK算法

特點(diǎn)：對CURE算法的改進(jìn)

優(yōu)點(diǎn)：同上，并適用于類(lèi)別屬性的數據

3）CHAMELEON算法

特點(diǎn)：利用了動(dòng)態(tài)建模技術(shù)

1.2分解聚類(lèi)

1.3優(yōu)缺點(diǎn)

優(yōu)點(diǎn)：適用于任意形狀和任意屬性的數據集；靈活控制不同層次的聚類(lèi)粒度，強聚類(lèi)能力

缺點(diǎn)：大大延長(cháng)了算法的執行時(shí)間，不能回溯處理

2、分割聚類(lèi)算法

2.1基于密度的聚類(lèi)

2.1.1特點(diǎn)

將密度足夠大的相鄰區域連接，能有效處理異常數據，主要用于對空間數據的聚類(lèi)

2.1.2典型算法

1）DBSCAN：不斷生長(cháng)足夠高密度的區域

2）DENCLUE：根據數據點(diǎn)在屬性空間中的密度進(jìn)行聚類(lèi)，密度和網(wǎng)格與處理的結合

3）OPTICS、DBCLASD、CURD：均針對數據在空間中呈現的不同密度分不對DBSCAN作了改進(jìn)

2.2基于網(wǎng)格的聚類(lèi)

2.2.1特點(diǎn)

利用屬性空間的多維網(wǎng)格數據結構，將空間劃分為有限數目的單元以構成網(wǎng)格結構；

1）優(yōu)點(diǎn)：處理時(shí)間與數據對象的數目無(wú)關(guān)，與數據的輸入順序無(wú)關(guān)，可以處理任意類(lèi)型的數據

2）缺點(diǎn)：處理時(shí)間與每維空間所劃分的單元數相關(guān)，一定程度上降低了聚類(lèi)的質(zhì)量和準確性

2.2.2典型算法

1）STING：基于網(wǎng)格多分辨率，將空間劃分為方形單元，對應不同分辨率

2）STING+：改進(jìn)STING，用于處理動(dòng)態(tài)進(jìn)化的空間數據

3）ＣＬＩＱＵＥ：結合網(wǎng)格和密度聚類(lèi)的思想，能處理大規模高維度數據

4）WaveCluster：以信號處理思想為基礎

2.3基于圖論的聚類(lèi)

2.3.1特點(diǎn)

轉換為組合優(yōu)化問(wèn)題，并利用圖論和相關(guān)啟發(fā)式算法來(lái)解決，構造數據集的最小生成數，再逐步刪除最長(cháng)邊

1）優(yōu)點(diǎn)：不需要進(jìn)行相似度的計算

2.3.2兩個(gè)主要的應用形式

1）基于超圖的劃分

2）基于光譜的圖劃分

2.4基于平方誤差的迭代重分配聚類(lèi)

2.4.1思想

逐步對聚類(lèi)結果進(jìn)行優(yōu)化、不斷將目標數據集向各個(gè)聚類(lèi)中心進(jìn)行重新分配以獲最優(yōu)解

2.4.2具體算法

1）概率聚類(lèi)算法

期望最大化、能夠處理異構數據、能夠處理具有復雜結構的記錄、能夠連續處理成批的數據、具有在線(xiàn)處理能力、產(chǎn)生的聚類(lèi)結果易于解釋

2）最近鄰聚類(lèi)算法——共享最近鄰算法SNN

特點(diǎn)：結合基于密度方法和ROCK思想，保留K最近鄰簡(jiǎn)化相似矩陣和個(gè)數

不足：時(shí)間復雜度提高到了O(N^2)

3）K-Medioids算法

特點(diǎn)：用類(lèi)中的某個(gè)點(diǎn)來(lái)代表該聚類(lèi)

優(yōu)點(diǎn)：能處理任意類(lèi)型的屬性；對異常數據不敏感

4）K-Means算法

1》特點(diǎn)：聚類(lèi)中心用各類(lèi)別中所有數據的平均值表示

2》原始K-Means算法的缺陷：結果好壞依賴(lài)于對初始聚類(lèi)中心的選擇、容易陷入局部最優(yōu)解、對K值的選擇沒(méi)有準則可依循、對異常數據較為敏感、只能處理數值屬性的數據、聚類(lèi)結構可能不平衡

3》K-Means的變體

Bradley和Fayyad等：降低對中心的依賴(lài)，能適用于大規模數據集

Dhillon等：調整迭代過(guò)程中重新計算中心方法，提高性能

Zhang等：權值軟分配調整迭代優(yōu)化過(guò)程

Sarafis：將遺傳算法應用于目標函數構建中

Berkh in等：應用擴展到了分布式聚類(lèi)

還有：采用圖論的劃分思想，平衡聚類(lèi)結果，將原始算法中的目標函數對應于一個(gè)各向同性的高斯混合模型

5）優(yōu)缺點(diǎn)

優(yōu)點(diǎn)：應用最為廣泛；收斂速度快；能擴展以用于大規模的數據集

缺點(diǎn)：傾向于識別凸形分布、大小相近、密度相近的聚類(lèi)；中心選擇和噪聲聚類(lèi)對結果影響大

3、基于約束的聚類(lèi)算法

3.1約束

對個(gè)體對象的約束、對聚類(lèi)參數的約束；均來(lái)自相關(guān)領(lǐng)域的經(jīng)驗知識

3.2重要應用

對存在障礙數據的二維空間按數據進(jìn)行聚類(lèi),如COD(Clustering with Obstructed Distance)：用兩點(diǎn)之間的障礙距離取代了一般的歐式距離

3.3不足

通常只能處理特定應用領(lǐng)域中的特定需求

4、用于高維數據的聚類(lèi)算法

4.1困難來(lái)源因素

1）無(wú)關(guān)屬性的出現使數據失去了聚類(lèi)的趨勢

2)區分界限變得模糊

4.2解決方法

1)對原始數據降維

2)子空間聚類(lèi)

CACTUS：對原始空間在二維平面上的投影

CLIQUE：結合基于密度和網(wǎng)格的聚類(lèi)思想，借鑒Apriori算法

3)聯(lián)合聚類(lèi)技術(shù)

特點(diǎn)：對數據點(diǎn)和屬性同時(shí)進(jìn)行聚類(lèi)

文本：基于雙向劃分圖及其最小分割的代數學(xué)方法

4.3不足：不可避免地帶來(lái)了原始數據信息的損失和聚類(lèi)準確性的降低

5、機器學(xué)習中的聚類(lèi)算法

5.1兩個(gè)方法

1)人工神經(jīng)網(wǎng)絡(luò )方法

自組織映射：向量化方法，遞增逐一處理；映射至二維平面，實(shí)現可視化

基于投影自適應諧振理論的人工神經(jīng)網(wǎng)絡(luò )聚類(lèi)

2)基于進(jìn)化理論的方法

缺陷：依賴(lài)于一些經(jīng)驗參數的選取，并具有較高的計算復雜度 

模擬退火：微擾因子；遺傳算法（選擇、交叉、變異）

5.2優(yōu)缺點(diǎn)

優(yōu)點(diǎn)：利用相應的啟發(fā)式算法獲得較高質(zhì)量的聚類(lèi)結果

缺點(diǎn)：計算復雜度較高，結果依賴(lài)于對某些經(jīng)驗參數的選擇