各種聚類(lèi)算法的比較.doc

《各種聚類(lèi)算法的比較.doc》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、各種聚類(lèi)算法的比較??????????聚類(lèi)的目標(biāo)是使同一類(lèi)對(duì)象的相似度盡可能地小；不同類(lèi)對(duì)象之間的相似度盡可能地大。目前聚類(lèi)的方法很多，根據(jù)基本思想的不同，大致可以將聚類(lèi)算法分為五大類(lèi)：層次聚類(lèi)算法、分割聚類(lèi)算法、基于約束的聚類(lèi)算法、機(jī)器學(xué)習(xí)中的聚類(lèi)算法和用于高維度的聚類(lèi)算法。摘自數(shù)據(jù)挖掘中的聚類(lèi)分析研究綜述這篇論文。1、層次聚類(lèi)算法1.1聚合聚類(lèi)1.1.1相似度依據(jù)距離不同：Single-Link:最近距離、Complete-Link：最遠(yuǎn)距離、Average-Link：平均距離1.1.2最具代表性算法1）CURE算法特點(diǎn)：固定數(shù)目有代表性的點(diǎn)共同代表類(lèi)優(yōu)點(diǎn)：識(shí)別形狀復(fù)雜，大小不一的

2、聚類(lèi)，過(guò)濾孤立點(diǎn)2）ROCK算法特點(diǎn)：對(duì)CURE算法的改進(jìn)優(yōu)點(diǎn)：同上，并適用于類(lèi)別屬性的數(shù)據(jù)3）CHAMELEON算法特點(diǎn)：利用了動(dòng)態(tài)建模技術(shù)1.2分解聚類(lèi)1.3優(yōu)缺點(diǎn)優(yōu)點(diǎn)：適用于任意形狀和任意屬性的數(shù)據(jù)集；靈活控制不同層次的聚類(lèi)粒度，強(qiáng)聚類(lèi)能力缺點(diǎn)：大大延長(zhǎng)了算法的執(zhí)行時(shí)間，不能回溯處理?2、分割聚類(lèi)算法2.1基于密度的聚類(lèi)2.1.1特點(diǎn)將密度足夠大的相鄰區(qū)域連接，能有效處理異常數(shù)據(jù)，主要用于對(duì)空間數(shù)據(jù)的聚類(lèi)2.1.2典型算法1）DBSCAN：不斷生長(zhǎng)足夠高密度的區(qū)域2）DENCLUE：根據(jù)數(shù)據(jù)點(diǎn)在屬性空間中的密度進(jìn)行聚類(lèi)，密度和網(wǎng)格與處理的結(jié)合3）OPTICS、DBCLASD、CU

3、RD：均針對(duì)數(shù)據(jù)在空間中呈現(xiàn)的不同密度分不對(duì)DBSCAN作了改進(jìn)2.2基于網(wǎng)格的聚類(lèi)2.2.1特點(diǎn)利用屬性空間的多維網(wǎng)格數(shù)據(jù)結(jié)構(gòu)，將空間劃分為有限數(shù)目的單元以構(gòu)成網(wǎng)格結(jié)構(gòu)；1）優(yōu)點(diǎn)：處理時(shí)間與數(shù)據(jù)對(duì)象的數(shù)目無(wú)關(guān)，與數(shù)據(jù)的輸入順序無(wú)關(guān)，可以處理任意類(lèi)型的數(shù)據(jù)2）缺點(diǎn)：處理時(shí)間與每維空間所劃分的單元數(shù)相關(guān)，一定程度上降低了聚類(lèi)的質(zhì)量和準(zhǔn)確性2.2.2典型算法1）STING：基于網(wǎng)格多分辨率，將空間劃分為方形單元，對(duì)應(yīng)不同分辨率2）STING+：改進(jìn)STING，用于處理動(dòng)態(tài)進(jìn)化的空間數(shù)據(jù)3）ＣＬＩＱＵＥ：結(jié)合網(wǎng)格和密度聚類(lèi)的思想，能處理大規(guī)模高維度數(shù)據(jù)4）WaveCluster：以信號(hào)處理思

4、想為基礎(chǔ)2.3基于圖論的聚類(lèi)2.3.1特點(diǎn)轉(zhuǎn)換為組合優(yōu)化問(wèn)題，并利用圖論和相關(guān)啟發(fā)式算法來(lái)解決，構(gòu)造數(shù)據(jù)集的最小生成數(shù)，再逐步刪除最長(zhǎng)邊1）優(yōu)點(diǎn)：不需要進(jìn)行相似度的計(jì)算2.3.2兩個(gè)主要的應(yīng)用形式1）基于超圖的劃分2）基于光譜的圖劃分2.4基于平方誤差的迭代重分配聚類(lèi)2.4.1思想逐步對(duì)聚類(lèi)結(jié)果進(jìn)行優(yōu)化、不斷將目標(biāo)數(shù)據(jù)集向各個(gè)聚類(lèi)中心進(jìn)行重新分配以獲最優(yōu)解2.4.2具體算法1）概率聚類(lèi)算法期望最大化、能夠處理異構(gòu)數(shù)據(jù)、能夠處理具有復(fù)雜結(jié)構(gòu)的記錄、能夠連續(xù)處理成批的數(shù)據(jù)、具有在線處理能力、產(chǎn)生的聚類(lèi)結(jié)果易于解釋2）最近鄰聚類(lèi)算法——共享最近鄰算法SNN特點(diǎn)：結(jié)合基于密度方法和ROCK思想

5、，保留K最近鄰簡(jiǎn)化相似矩陣和個(gè)數(shù)不足：時(shí)間復(fù)雜度提高到了O(N^2)3）K-Medioids算法特點(diǎn)：用類(lèi)中的某個(gè)點(diǎn)來(lái)代表該聚類(lèi)優(yōu)點(diǎn)：能處理任意類(lèi)型的屬性；對(duì)異常數(shù)據(jù)不敏感4）K-Means算法1》特點(diǎn)：聚類(lèi)中心用各類(lèi)別中所有數(shù)據(jù)的平均值表示2》原始K-Means算法的缺陷：結(jié)果好壞依賴于對(duì)初始聚類(lèi)中心的選擇、容易陷入局部最優(yōu)解、對(duì)K值的選擇沒(méi)有準(zhǔn)則可依循、對(duì)異常數(shù)據(jù)較為敏感、只能處理數(shù)值屬性的數(shù)據(jù)、聚類(lèi)結(jié)構(gòu)可能不平衡3》K-Means的變體Bradley和Fayyad等：降低對(duì)中心的依賴，能適用于大規(guī)模數(shù)據(jù)集Dhillon等：調(diào)整迭代過(guò)程中重新計(jì)算中心方法，提高性能Zhang等：權(quán)值

6、軟分配調(diào)整迭代優(yōu)化過(guò)程Sarafis：將遺傳算法應(yīng)用于目標(biāo)函數(shù)構(gòu)建中Berkhin等：應(yīng)用擴(kuò)展到了分布式聚類(lèi)還有：采用圖論的劃分思想，平衡聚類(lèi)結(jié)果，將原始算法中的目標(biāo)函數(shù)對(duì)應(yīng)于一個(gè)各向同性的高斯混合模型5）優(yōu)缺點(diǎn)優(yōu)點(diǎn)：應(yīng)用最為廣泛；收斂速度快；能擴(kuò)展以用于大規(guī)模的數(shù)據(jù)集缺點(diǎn)：傾向于識(shí)別凸形分布、大小相近、密度相近的聚類(lèi)；中心選擇和噪聲聚類(lèi)對(duì)結(jié)果影響大3、基于約束的聚類(lèi)算法3.1約束對(duì)個(gè)體對(duì)象的約束、對(duì)聚類(lèi)參數(shù)的約束；均來(lái)自相關(guān)領(lǐng)域的經(jīng)驗(yàn)知識(shí)3.2重要應(yīng)用對(duì)存在障礙數(shù)據(jù)的二維空間按數(shù)據(jù)進(jìn)行聚類(lèi),如COD(ClusteringwithObstructedDistance)：用兩點(diǎn)之間的障礙

7、距離取代了一般的歐式距離3.3不足通常只能處理特定應(yīng)用領(lǐng)域中的特定需求4、用于高維數(shù)據(jù)的聚類(lèi)算法4.1困難來(lái)源因素1）無(wú)關(guān)屬性的出現(xiàn)使數(shù)據(jù)失去了聚類(lèi)的趨勢(shì)2)區(qū)分界限變得模糊4.2解決方法1)對(duì)原始數(shù)據(jù)降維2)子空間聚類(lèi)CACTUS：對(duì)原始空間在二維平面上的投影CLIQUE：結(jié)合基于密度和網(wǎng)格的聚類(lèi)思想，借鑒Apriori算法3)聯(lián)合聚類(lèi)技術(shù)特點(diǎn)：對(duì)數(shù)據(jù)點(diǎn)和屬性同時(shí)進(jìn)行聚類(lèi)文本：基于雙向劃分圖及其最小分割的代數(shù)學(xué)方法4.3不足：不可避免地帶來(lái)了