論各種聚類算法及改進(jìn)算法的探究

《論各種聚類算法及改進(jìn)算法的探究》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。

1、論各種聚類算法及改進(jìn)算法的探究　　論文：數(shù)據(jù)挖掘；聚類算法；聚類分析　　論文：該文具體闡述了數(shù)據(jù)挖掘領(lǐng)域的常用聚類算法及改進(jìn)算法，并比較分析了其優(yōu)缺點，提出了數(shù)據(jù)挖掘?qū)垲惖牡湫鸵螅赋龈髯缘奶卣?，以便于人們更快、更輕易地選擇一種聚類算法解決特定新題目和對聚類算法作進(jìn)一步的探究。并給出了相應(yīng)的算法評價標(biāo)準(zhǔn)、改進(jìn)建議和聚類分析探究的熱門、難點。上述工作將為聚類分析和數(shù)據(jù)挖掘等探究提供有益的參考?！　?引言　　隨著經(jīng)濟(jì)社會和科學(xué)技術(shù)的高速發(fā)展，各行各業(yè)積累的數(shù)據(jù)量急劇增長，如何從海量的數(shù)據(jù)中提取有用的信息成為當(dāng)務(wù)之急。聚類是將數(shù)據(jù)劃分成群組的

2、過程，即把數(shù)據(jù)對象分成多個類或簇，在同一個簇中的對象之間具有較高的相似度，而不同簇中的對象差別較大。它對未知數(shù)據(jù)的劃分和分析起著非常有效的功能。通過聚類，能夠識別密集和稀疏的區(qū)域，發(fā)現(xiàn)全局的分布模式，以及數(shù)據(jù)屬性之間的相互關(guān)系等。為了找到效率高、通用性強(qiáng)的聚類方法人們從不同角度提出了很多種聚類算法，一般可分為基于層次的，基于劃分的，基于密度的，基于X格的和基于模型的五大類?！　?數(shù)據(jù)挖掘?qū)垲愃惴ǖ囊蟆　?1)可兼容性：要求聚類算法能夠適應(yīng)并處理屬性不同類型的數(shù)據(jù)。(2)可伸縮性：要求聚類算法對大型數(shù)據(jù)集和小數(shù)據(jù)集都適用。(3)對用戶專業(yè)

3、知識要求最小化。(4)對數(shù)據(jù)種別簇的包容性：即聚類算法不僅能在用基本幾何形式表達(dá)的數(shù)據(jù)上運行得很好，還要在以其他更高維度形式表現(xiàn)的數(shù)據(jù)上同樣也能實現(xiàn)。(5)能有效識別并處理數(shù)據(jù)庫的大量數(shù)據(jù)中普遍包含的異常值，空缺值或錯誤的不符合現(xiàn)實的數(shù)據(jù)。(6)聚類結(jié)果既要滿足特定約束條件，又要具有良好聚類特性，且不丟失數(shù)據(jù)的真實信息。(7)可讀性和可視性：能利用各種屬性如顏色等以直觀形式向用戶顯示數(shù)據(jù)挖掘的結(jié)果。(8)處理噪聲數(shù)據(jù)的能力。(9)算法能否和輸進(jìn)順序無關(guān)?！　?各種聚類算法先容　　隨著人們對數(shù)據(jù)挖掘的深進(jìn)探究和了解，各種聚類算法的改進(jìn)算法也相

4、繼提出，很多新算法在前人提出的算法中做了某些方面的進(jìn)步和改進(jìn)，且很多算法是有針對性地為特定的領(lǐng)域而設(shè)計。某些算法可能對某類數(shù)據(jù)在可行性、效率、精度或簡單性上具有一定的優(yōu)越性，但對其它類型的數(shù)據(jù)或在其他領(lǐng)域應(yīng)用中則不一定還有上風(fēng)。所以，我們必須清楚地了解各種算法的優(yōu)缺點和應(yīng)用范圍，根據(jù)實際新題目選擇合適的算法?！　?.1基于層次的聚類算法　　基于層次的聚類算法對給定數(shù)據(jù)對象進(jìn)行層次上的分解，可分為凝聚算法和***算法?！　?1)自底向上的凝聚聚類方法。這種策略是以數(shù)據(jù)對象作為原子類，然后將這些原子類進(jìn)行聚合。逐步聚合成越來越大的類，直到滿足終

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

6、一步一步細(xì)化。它的優(yōu)點在于探究者可以把注重力集中在數(shù)據(jù)的結(jié)構(gòu)上面。一般情況下不使用***型方法，由于在較高的層很難進(jìn)行正確的拆分?！　?.2基于密度的聚類算法　　很多算法都使用間隔來描述數(shù)據(jù)之間的相似性，但對于非凸數(shù)據(jù)集，只用間隔來描述是不夠的。此時可用密度來取代間隔描述相似性，即基于密度的聚類算法。它不是基于各種各樣的間隔，所以能克服基于間隔的算法只能發(fā)現(xiàn)“類圓形”的聚類的缺點。其指導(dǎo)思想是：只要一個區(qū)域中的點的密度（對象或數(shù)據(jù)點的數(shù)目）大過某個閾值，就把它加到和之相近的聚類中往。該法從數(shù)據(jù)對象的分布密度出發(fā)，把密度足夠大的區(qū)域連接起來，

7、從而可發(fā)現(xiàn)任意外形的簇，并可用來過濾“噪聲”數(shù)據(jù)。常見算法有DBSCAN，DENCLUE等。　　3.3基于劃分的聚類算法　　給定一個N個對象的元組或數(shù)據(jù)庫，根據(jù)給定要創(chuàng)建的劃分的數(shù)目k，將數(shù)據(jù)劃分為k個組，每個組表示一個簇類（%26lt;=N）時滿足如下兩點：(1)每個組至少包含一個對象；(2)每個對象必須屬于且只屬于一個組。算法先隨機(jī)創(chuàng)建一個初始劃分，然后采用一種迭代的重定位技術(shù)，通過將對象根據(jù)簇類之間的差異從一個劃分移到另一個劃分來進(jìn)步簇類內(nèi)數(shù)據(jù)之間的相似程度。一種好的劃分的一般準(zhǔn)則是：在同一個類中的對象盡可能“接近”或相似，而不同類中

8、的對象盡可能“闊別”或不同。為了達(dá)到全局最優(yōu)，基于劃分的聚類會要求窮舉所有可能的劃分。典型的劃包括：K-means，PAM，EM等。劃分法收斂速度快，在對中小規(guī)模的數(shù)據(jù)庫中發(fā)現(xiàn)球