各種聚類(lèi)算法及改進(jìn)算法研究

1、各種聚類(lèi)算法及改進(jìn)算法的研究各種聚類(lèi)算法及改進(jìn)算法的研究作者：王安志李明東李超時(shí)間：20093310:59:00來(lái)源：論文天下論文網(wǎng)論文關(guān)鍵詞：數(shù)據(jù)挖掘；聚類(lèi)算法；聚類(lèi)分析論文關(guān)鍵詞：數(shù)據(jù)挖掘；聚類(lèi)算法；聚類(lèi)分析論文摘要：論文摘要：該文詳細(xì)闡述了數(shù)據(jù)挖掘領(lǐng)域的常用聚類(lèi)算法及改進(jìn)算法，并比較分析了其優(yōu)缺點(diǎn)，提出了數(shù)據(jù)挖掘?qū)垲?lèi)的典型要求，指出各自的特點(diǎn)，以便于人們更快、更容易地選擇一種聚類(lèi)算法解決特定問(wèn)題和對(duì)聚類(lèi)算法作進(jìn)一步的研究。并給出

2、了相應(yīng)的算法評(píng)價(jià)標(biāo)準(zhǔn)、改進(jìn)建議和聚類(lèi)分析研究的熱點(diǎn)、難點(diǎn)。上述工作將為聚類(lèi)分析和數(shù)據(jù)挖掘等研究提供有益的參考。1引言引言隨著經(jīng)濟(jì)社會(huì)和科學(xué)技術(shù)的高速發(fā)展，各行各業(yè)積累的數(shù)據(jù)量急劇增長(zhǎng)，如何從海量的數(shù)據(jù)中提取有用的信息成為當(dāng)務(wù)之急。聚類(lèi)是將數(shù)據(jù)劃分成群組的過(guò)程，即把數(shù)據(jù)對(duì)象分成多個(gè)類(lèi)或簇，在同一個(gè)簇中的對(duì)象之間具有較高的相似度，而不同簇中的對(duì)象差別較大。它對(duì)未知數(shù)據(jù)的劃分和分析起著非常有效的作用。通過(guò)聚類(lèi)，能夠識(shí)別密集和稀疏的區(qū)域，發(fā)現(xiàn)全

3、局的分布模式，以及數(shù)據(jù)屬性之間的相互關(guān)系等。為了找到效率高、通用性強(qiáng)的聚類(lèi)方法人們從不同角度提出了許多種聚類(lèi)算法，一般可分為基于層次的，基于劃分的，基于密度的，基于網(wǎng)格的和基于模型的五大類(lèi)。2數(shù)據(jù)挖掘?qū)垲?lèi)算法的要求數(shù)據(jù)挖掘?qū)垲?lèi)算法的要求(1)可兼容性：要求聚類(lèi)算法能夠適應(yīng)并處理屬性不同類(lèi)型的數(shù)據(jù)。(2)可伸縮性：要求聚類(lèi)算法對(duì)大型數(shù)據(jù)集和小數(shù)據(jù)集都適用。(3)對(duì)用戶(hù)專(zhuān)業(yè)知識(shí)要求最小化。(4)對(duì)數(shù)據(jù)類(lèi)別簇的包容性：即聚類(lèi)算法不僅能在用

4、基本幾何形式表達(dá)的數(shù)據(jù)上運(yùn)行得很好，還要在以其他更高維度形式表現(xiàn)的數(shù)據(jù)上同樣也能實(shí)現(xiàn)。(5)能有效識(shí)別并處理數(shù)據(jù)庫(kù)的大量數(shù)據(jù)中普遍包含的異常值，空缺值或錯(cuò)誤的不符合現(xiàn)實(shí)的數(shù)據(jù)。(6)聚類(lèi)結(jié)果既要滿(mǎn)足特定約束條件，又要具有良好聚類(lèi)特性，且不丟失數(shù)據(jù)的真實(shí)信息。(7)可讀性和可視性：能利用各種屬性如顏色等以直觀形式向用戶(hù)顯示數(shù)據(jù)挖掘的結(jié)果。(8)處理噪聲數(shù)據(jù)的能力。(9)算法能否與輸入順序無(wú)關(guān)。3各種聚類(lèi)算法介紹各種聚類(lèi)算法介紹隨著人們對(duì)數(shù)

5、據(jù)挖掘的深入研究和了解，各種聚類(lèi)算法的改進(jìn)算法也相繼提出，很多新算法在前人提出的算法中做了某些方面的提高和改進(jìn)，且很多算法是有針對(duì)性地為特定的領(lǐng)域而設(shè)計(jì)。某些算法可能對(duì)某類(lèi)數(shù)據(jù)在可行性、效率、精度或簡(jiǎn)單性上具有一定的優(yōu)越性，但對(duì)其它類(lèi)型的數(shù)據(jù)或在其他領(lǐng)域應(yīng)用中則不一定還有優(yōu)勢(shì)。所以，我們必須清楚地了解各種算法的優(yōu)缺點(diǎn)和應(yīng)用范圍，根據(jù)實(shí)際問(wèn)題選擇合適的算法。3.1基于層次的聚類(lèi)算法基于層次的聚類(lèi)算法基于層次的聚類(lèi)算法對(duì)給定數(shù)據(jù)對(duì)象進(jìn)行層次

6、上的分解，可分為凝聚算法和分裂算法。(1)自底向上的凝聚聚類(lèi)方法。這種策略是以數(shù)據(jù)對(duì)象作為原子類(lèi)，然后將這些原子類(lèi)進(jìn)行聚合。逐步聚合成越來(lái)越大的類(lèi)，直到滿(mǎn)足終止條件。凝聚算法的過(guò)程為：在初始的輸入對(duì)象用分類(lèi)屬性值對(duì)來(lái)描述。COBWEB的優(yōu)點(diǎn)為：可以自動(dòng)修正劃分中類(lèi)的數(shù)目；不需要用戶(hù)提供輸入?yún)?shù)。缺點(diǎn)為：COBWEB基于這樣一個(gè)假設(shè)：在每個(gè)屬性上的概率分布是彼此獨(dú)立的。但這個(gè)假設(shè)并不總是成立。且對(duì)于偏斜的輸入數(shù)據(jù)不是高度平衡的，它可能導(dǎo)致

7、時(shí)間和空間復(fù)雜性的劇烈變化，不適用于聚類(lèi)大型數(shù)據(jù)庫(kù)的數(shù)據(jù)。3.6模糊聚類(lèi)算法模糊聚類(lèi)算法現(xiàn)實(shí)中很多對(duì)象沒(méi)有嚴(yán)格的屬性，其類(lèi)屬和形態(tài)存在著中介性，適合軟劃分。恰好模糊聚類(lèi)具有描述樣本類(lèi)屬中間性的優(yōu)點(diǎn)，因此成為當(dāng)今聚類(lèi)分析研究的主流。常用的模糊聚類(lèi)有動(dòng)態(tài)直接聚類(lèi)法、最大樹(shù)法、FCM等?；驹頌椋杭僭O(shè)有N個(gè)要分析的樣本，每個(gè)樣本有M個(gè)可量化的指標(biāo)，一般步驟為：(1)標(biāo)準(zhǔn)化數(shù)據(jù)：常用的數(shù)據(jù)標(biāo)準(zhǔn)化方法有：小數(shù)定標(biāo)規(guī)范化，最大最小值規(guī)范化，標(biāo)準(zhǔn)差

8、規(guī)范化等。(2)建立模糊相似矩陣，標(biāo)定相似系數(shù)。(3)計(jì)算多極相似矩陣，計(jì)算整體相似關(guān)系矩陣，有傳遞閉包法，動(dòng)態(tài)直接聚類(lèi)法，最大樹(shù)法等。(4)給定一個(gè)聚類(lèi)水平，計(jì)算絕對(duì)相似矩陣。按行列調(diào)整絕對(duì)相似矩陣，每個(gè)分塊即為一個(gè)分類(lèi)。3.6.1模糊C均值聚類(lèi)算法FCM算法用隸屬度確定每個(gè)樣本屬于某個(gè)聚類(lèi)的程度。它與K平均算法和中心點(diǎn)算法等相比，計(jì)算量可大大減少，因?yàn)樗∪チ硕嘀氐姆磸?fù)計(jì)算過(guò)程，效率將大大提高。同時(shí)，模糊聚類(lèi)分析可根據(jù)數(shù)據(jù)庫(kù)中的

9、相關(guān)數(shù)據(jù)計(jì)算形成模糊相似矩陣，形成相似矩陣之后，直接對(duì)相似矩陣進(jìn)行處理即可，無(wú)須多次反復(fù)掃描數(shù)據(jù)庫(kù)。根據(jù)實(shí)驗(yàn)要求動(dòng)態(tài)設(shè)定m值，以滿(mǎn)足不同類(lèi)型數(shù)據(jù)挖掘任務(wù)的需要，適于高維度的數(shù)據(jù)的處理，具有較好的伸縮性，便于找出異常點(diǎn)。但m值根據(jù)經(jīng)驗(yàn)或者實(shí)驗(yàn)得來(lái)，具有不確定性，可能影響實(shí)驗(yàn)結(jié)果。并且，由于梯度法的搜索方向總是沿著能量減小的方向，使得算法存在易陷入局部極小值和對(duì)初始化敏感的缺點(diǎn)。為克服上述缺點(diǎn)，可在FCM算法中引入全局尋優(yōu)法來(lái)擺脫FCM聚類(lèi)

10、運(yùn)算時(shí)可能陷入的局部極小點(diǎn)，優(yōu)化聚類(lèi)效果。3.6.2免疫進(jìn)化算法該算法借鑒生命科學(xué)中的免疫概念和理論在保留原算法優(yōu)良特性的前提下，力圖有選擇、有目的地利用待求問(wèn)題中的一些特征或知識(shí)來(lái)抑制其優(yōu)化過(guò)程中出現(xiàn)的退化現(xiàn)象。免疫算法的核心在于免疫算子的構(gòu)造，通過(guò)接種疫苗或免疫選擇兩個(gè)步驟來(lái)完成。免疫進(jìn)化算法能提高個(gè)體的適應(yīng)度和防止群體的退化，從而達(dá)到減輕原有進(jìn)化算法后期的波動(dòng)現(xiàn)象和提高收斂速度。例如IFCM、IFCL算法。它們既較大地提高了獲取全

11、局最優(yōu)的概率，又減輕了基于遺傳聚類(lèi)算法在遺傳后期的波動(dòng)現(xiàn)象。進(jìn)一步的工作是參數(shù)的適當(dāng)選取和減小運(yùn)行時(shí)間等。人對(duì)于客觀事物的識(shí)別往往只通過(guò)一些模糊信息的綜合，便可以獲得足夠精確的定論。[3.7其它聚類(lèi)算法其它聚類(lèi)算法3.7.1基于群的聚類(lèi)方法該法是進(jìn)化計(jì)算的一個(gè)分支，模擬了生物界中蟻群、魚(yú)群等在覓食或避敵時(shí)的行為?？煞譃橄伻核惴ˋCO和PSO。蟻群聚類(lèi)算法的許多特性，如靈活性、健壯性、分布性和自組織性等，使其非常適合本質(zhì)上是分布、動(dòng)態(tài)及又