【谷速軟件】matlab源碼-各種聚類算法的比較

《【谷速軟件】matlab源碼-各種聚類算法的比較》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

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

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

3、區(qū)域2）DENCLUE：根據(jù)數(shù)據(jù)點(diǎn)在屬性空間中的密度進(jìn)行聚類，密度和網(wǎng)格與處理的結(jié)合3）OPTICS、DBCLASD、CURD：均針對數(shù)據(jù)在空間中呈現(xiàn)的不同密度分不對DBSCAN作了改進(jìn)2.2基于網(wǎng)格的聚類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ù)對象的數(shù)目無關(guān)，與數(shù)據(jù)的輸入順序無關(guān)，可以處理任意類型的數(shù)據(jù)2）缺點(diǎn)：處理時(shí)間與每維空間所劃分的單元數(shù)相關(guān)，一定程度上降低了聚類的質(zhì)量和準(zhǔn)確性2.2.2典型算法1）STING：基于網(wǎng)格多分辨率，

4、將空間劃分為方形單元，對應(yīng)不同分辨率2）STING+：改進(jìn)STING，用于處理動(dòng)態(tài)進(jìn)化的空間數(shù)據(jù)3）ＣＬＩＱＵＥ：結(jié)合網(wǎng)格和密度聚類的思想，能處理大規(guī)模高維度數(shù)據(jù)4）WaveCluster：以信號處理思想為基礎(chǔ)2.3基于圖論的聚類2.3.1特點(diǎn)轉(zhuǎn)換為組合優(yōu)化問題，并利用圖論和相關(guān)啟發(fā)式算法來解決，構(gòu)造數(shù)據(jù)集的最小生成數(shù)，再逐步刪除最長邊1）優(yōu)點(diǎn)：不需要進(jìn)行相似度的計(jì)算2.3.2兩個(gè)主要的應(yīng)用形式1）基于超圖的劃分2）基于光譜的圖劃分2.4基于平方誤差的迭代重分配聚類2.4.1思想逐步對聚類結(jié)果進(jìn)行優(yōu)化、不斷

5、將目標(biāo)數(shù)據(jù)集向各個(gè)聚類中心進(jìn)行重新分配以獲最優(yōu)解2.4.2具體算法1）概率聚類算法期望最大化、能夠處理異構(gòu)數(shù)據(jù)、能夠處理具有復(fù)雜結(jié)構(gòu)的記錄、能夠連續(xù)處理成批的數(shù)據(jù)、具有在線處理能力、產(chǎn)生的聚類結(jié)果易于解釋2）最近鄰聚類算法——共享最近鄰算法SNN特點(diǎn)：結(jié)合基于密度方法和ROCK思想，保留K最近鄰簡化相似矩陣和個(gè)數(shù)不足：時(shí)間復(fù)雜度提高到了O(N^2)3）K-Medioids算法特點(diǎn)：用類中的某個(gè)點(diǎn)來代表該聚類優(yōu)點(diǎn)：能處理任意類型的屬性；對異常數(shù)據(jù)不敏感4）K-Means算法1》特點(diǎn)：聚類中心用各類別中所有數(shù)據(jù)

6、的平均值表示2》原始K-Means算法的缺陷：結(jié)果好壞依賴于對初始聚類中心的選擇、容易陷入局部最優(yōu)解、對K值的選擇沒有準(zhǔn)則可依循、對異常數(shù)據(jù)較為敏感、只能處理數(shù)值屬性的數(shù)據(jù)、聚類結(jié)構(gòu)可能不平衡3》K-Means的變體Bradley和Fayyad等：降低對中心的依賴，能適用于大規(guī)模數(shù)據(jù)集Dhillon等：調(diào)整迭代過程中重新計(jì)算中心方法，提高性能Zhang等：權(quán)值軟分配調(diào)整迭代優(yōu)化過程Sarafis：將遺傳算法應(yīng)用于目標(biāo)函數(shù)構(gòu)建中Berkhin等：應(yīng)用擴(kuò)展到了分布式聚類還有：采用圖論的劃分思想，平衡聚類結(jié)果，將

7、原始算法中的目標(biāo)函數(shù)對應(yīng)于一個(gè)各向同性的高斯混合模型5）優(yōu)缺點(diǎn)優(yōu)點(diǎn)：應(yīng)用最為廣泛；收斂速度快；能擴(kuò)展以用于大規(guī)模的數(shù)據(jù)集缺點(diǎn)：傾向于識別凸形分布、大小相近、密度相近的聚類；中心選擇和噪聲聚類對結(jié)果影響大3、基于約束的聚類算法3.1約束對個(gè)體對象的約束、對聚類參數(shù)的約束；均來自相關(guān)領(lǐng)域的經(jīng)驗(yàn)知識3.2重要應(yīng)用對存在障礙數(shù)據(jù)的二維空間按數(shù)據(jù)進(jìn)行聚類,如COD(ClusteringwithObstructedDistance)：用兩點(diǎn)之間的障礙距離取代了一般的歐式距離3.3不足通常只能處理特定應(yīng)用領(lǐng)域中的特定需求

8、4、用于高維數(shù)據(jù)的聚類算法4.1困難來源因素1）無關(guān)屬性的出現(xiàn)使數(shù)據(jù)失去了聚類的趨勢2)區(qū)分界限變得模糊4.2解決方法1)對原始數(shù)據(jù)降維2)子空間聚類CACTUS：對原始空間在二維平面上的投影CLIQUE：結(jié)合基于密度和網(wǎng)格的聚類思想，借鑒Apriori算法3)聯(lián)合聚類技術(shù)特點(diǎn)：對數(shù)據(jù)點(diǎn)和屬性同時(shí)進(jìn)行聚類文本：基于雙向劃分圖及其最小分割的代數(shù)學(xué)方法4.3不足：不可避免地帶來了原始數(shù)據(jù)信息的損失和聚類準(zhǔn)確性的降低5