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

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

1、各種聚類(lèi)算法及改進(jìn)算法的研究作者：王安志　李明東　李　超　　時(shí)間：2009-3-310:59:00　　來(lái)源：論文天下論文網(wǎng)論文關(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)一步的研究。并給出了相應(yīng)的算法評(píng)價(jià)標(biāo)準(zhǔn)、改進(jìn)建議和聚類(lèi)分析研究的熱點(diǎn)、難點(diǎn)。上述工作將為聚類(lèi)分析和數(shù)據(jù)挖掘等研究提供有益的參考?！　?引言　　隨著經(jīng)濟(jì)社會(huì)和科學(xué)技術(shù)的高速發(fā)展，各行各業(yè)積累的數(shù)據(jù)量急劇增長(zhǎng)，

2、如何從海量的數(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)全局的分布模式，以及數(shù)據(jù)屬性之間的相互關(guān)系等。為了找到效率高、通用性強(qiáng)的聚類(lèi)方法人們從不同角度提出了許多種聚類(lèi)算法，一般可分為基于層次的，基于劃分的，基于密度的，基于網(wǎng)格的和基于模型的五大類(lèi)。　　2數(shù)據(jù)挖掘?qū)垲?lèi)算法的要求　　(1)可兼容性：要求聚類(lèi)算法能夠適應(yīng)并處理屬性不同類(lèi)型的數(shù)據(jù)。(2)可伸縮性：要求聚類(lèi)算法對(duì)

3、大型數(shù)據(jù)集和小數(shù)據(jù)集都適用。(3)對(duì)用戶(hù)專(zhuān)業(yè)知識(shí)要求最小化。(4)對(duì)數(shù)據(jù)類(lèi)別簇的包容性：即聚類(lèi)算法不僅能在用基本幾何形式表達(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)可讀性和可視性：能利用各種屬性如顏色等以直觀(guān)形式向用戶(hù)顯示數(shù)據(jù)挖掘的結(jié)果。(8)處理噪聲數(shù)據(jù)的能力。(9)算法能否與輸入順序無(wú)關(guān)?！　?各種聚類(lèi)算法介紹　　隨著人們對(duì)數(shù)據(jù)挖掘的深入研究和了解，各種聚類(lèi)

4、算法的改進(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)題選擇合適的算法?！　?.1基于層次的聚類(lèi)算法　　基于層次的聚類(lèi)算法對(duì)給定數(shù)據(jù)對(duì)象進(jìn)行層次上的分解，可分為凝聚算法和分裂算法。　　(1)自底向上的凝聚聚類(lèi)方法。這種策略是以數(shù)據(jù)對(duì)象作為原子類(lèi)，然后將這些原子類(lèi)進(jìn)行聚合。逐步聚合成越來(lái)越大的類(lèi)，直到滿(mǎn)足終止條件。凝聚

5、算法的過(guò)程為：在初始時(shí)，每一個(gè)成員都組成一個(gè)單獨(dú)的簇，在以后的迭代過(guò)程中，再把那些相互鄰近的簇合并成一個(gè)簇，直到所有的成員組成一個(gè)簇為止。其時(shí)間和空間復(fù)雜性均為O(n2)。通過(guò)凝聚式的方法將兩簇合并后，無(wú)法再將其分離到之前的狀態(tài)。在凝聚聚類(lèi)時(shí)，選擇合適的類(lèi)的個(gè)數(shù)和畫(huà)出原始數(shù)據(jù)的圖像很重要?！　?2)自頂向下分裂聚類(lèi)方法。與凝聚法相反，該法先將所有對(duì)象置于一個(gè)簇中，然后逐漸細(xì)分為越來(lái)越小的簇，直到每個(gè)對(duì)象自成一簇，或者達(dá)到了某個(gè)終結(jié)條件。其主要思想是將那些成員之間不是非常緊密的簇進(jìn)行分裂。跟凝聚式方法的方向相反，從一個(gè)簇出發(fā)，一步一步細(xì)化。它的優(yōu)點(diǎn)在于研究者可以把注意

6、力集中在數(shù)據(jù)的結(jié)構(gòu)上面。一般情況下不使用分裂型方法，因?yàn)樵谳^高的層很難進(jìn)行正確的拆分?！　?.2基于密度的聚類(lèi)算法　　很多算法都使用距離來(lái)描述數(shù)據(jù)之間的相似性，但對(duì)于非凸數(shù)據(jù)集，只用距離來(lái)描述是不夠的。此時(shí)可用密度來(lái)取代距離描述相似性，即基于密度的聚類(lèi)算法。它不是基于各種各樣的距離，所以能克服基于距離的算法只能發(fā)現(xiàn)“類(lèi)圓形”的聚類(lèi)的缺點(diǎn)。其指導(dǎo)思想是：只要一個(gè)區(qū)域中的點(diǎn)的密度（對(duì)象或數(shù)據(jù)點(diǎn)的數(shù)目）大過(guò)某個(gè)閾值，就把它加到與之相近的聚類(lèi)中去。該法從數(shù)據(jù)對(duì)象的分布密度出發(fā)，把密度足夠大的區(qū)域連接起來(lái)，從而可發(fā)現(xiàn)任意形狀的簇，并可用來(lái)過(guò)濾“噪聲”數(shù)據(jù)。常見(jiàn)算法有DBSCA

7、N，DENCLUE等。[　　3.3基于劃分的聚類(lèi)算法　　給定一個(gè)N個(gè)對(duì)象的元組或數(shù)據(jù)庫(kù)，根據(jù)給定要?jiǎng)?chuàng)建的劃分的數(shù)目k，將數(shù)據(jù)劃分為k個(gè)組，每個(gè)組表示一個(gè)簇類(lèi)（<=N）時(shí)滿(mǎn)足如下兩點(diǎn)：(1)每個(gè)組至少包含一個(gè)對(duì)象；(2)每個(gè)對(duì)象必須屬于且只屬于一個(gè)組。算法先隨機(jī)創(chuàng)建一個(gè)初始劃分，然后采用一種迭代的重定位技術(shù)，通過(guò)將對(duì)象根據(jù)簇類(lèi)之間的差異從一個(gè)劃分移到另一個(gè)劃分來(lái)提高簇類(lèi)內(nèi)數(shù)據(jù)之間的相似程度。一種好的劃分的一般準(zhǔn)則是：在同一個(gè)類(lèi)中的對(duì)象盡可能“接近”或相似，而不同類(lèi)中的對(duì)象盡可能“遠(yuǎn)離”或不同。為了達(dá)到全局最優(yōu)，基于劃分的聚類(lèi)會(huì)要求窮舉所有可能的劃分。典型的劃包括：