聚類(lèi)算法綜述(共9頁(yè))

1、精選優(yōu)質(zhì)文檔-傾情為你奉上學(xué)術(shù)型碩士課程論文（或讀書(shū)報(bào)告）課程名稱(chēng)： 科技論文寫(xiě)作 題 目： 數(shù)據(jù)挖掘中聚類(lèi)算法的綜述 題目類(lèi)型（課程論文或讀書(shū)報(bào)告）： 課程論文 學(xué) 院： 計(jì)算機(jī)科學(xué)與工程學(xué)院 專(zhuān)業(yè)名稱(chēng)： 計(jì)算機(jī)科學(xué)與技術(shù) 姓 名： 王銀 學(xué) 號(hào)： 任課教師： 潘地林 授課時(shí)間：2015年9月6日2015年11月7日提交時(shí)間： 2015年12月10日 專(zhuān)心-專(zhuān)注-專(zhuān)業(yè)數(shù)據(jù)挖掘中聚類(lèi)算法的綜述王銀（安徽理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，安徽） 摘要：聚類(lèi)是數(shù)據(jù)挖掘中用來(lái)發(fā)現(xiàn)數(shù)據(jù)分布和隱含模式的一項(xiàng)重要技術(shù)。本綜述按照聚類(lèi)算法的分類(lèi)，對(duì)每一類(lèi)中具有代表性的算法進(jìn)行介紹，分析和評(píng)價(jià)。最后從發(fā)

2、現(xiàn)聚類(lèi)形狀、所適用的數(shù)據(jù)庫(kù)和輸入數(shù)據(jù)順序的敏感性等方面進(jìn)行了算法推薦，以便對(duì)聚類(lèi)算法作進(jìn)一步的研究。關(guān)鍵詞：數(shù)據(jù)挖掘；聚類(lèi)分析；聚類(lèi)算法 Review of Clustering Algorithm in Data MiningAbstract:Clustering is an important technology in Data Mining to discovery data distribution and implicit model. the classification of clustering algorithms was proposed in this pap

3、er.Each class has a representative algorithm is introduced,analysis and evaluation.In the end,it is suggested that the algorithm can be used to further study the clustering algorithm,which is based on the shape of the discovery,the database and the order of input data.Keywords:Data Mining;Clustering

4、 analysis;Clustering Algorithm1 引言隨著信息技術(shù)和計(jì)算機(jī)技術(shù)的迅猛發(fā)展，人們面臨著越來(lái)越多的文本、圖像、視頻以及音頻數(shù)據(jù)，為幫助用戶(hù)從這些大量數(shù)據(jù)中分析出其間所蘊(yùn)涵的有價(jià)值的知識(shí)，數(shù)據(jù)挖掘（Data Mining，DM）技術(shù)應(yīng)運(yùn)而生。所謂數(shù)據(jù)挖掘，就是從大量無(wú)序的數(shù)據(jù)中發(fā)現(xiàn)隱含的、有效的、有價(jià)值的、可理解的模式，進(jìn)而發(fā)現(xiàn)有用的知識(shí)，并得出時(shí)間的趨向和關(guān)聯(lián)，為用戶(hù)提供問(wèn)題求解層次的決策支持能力。與此同時(shí)，聚類(lèi)作為數(shù)據(jù)挖掘的主要方法之一，也越來(lái)越引起人們的關(guān)注。典型的聚類(lèi)過(guò)程主要包括數(shù)據(jù)準(zhǔn)備、特征選擇和特征提取、接近度計(jì)算、聚類(lèi)(或分組)、對(duì)聚類(lèi)結(jié)果進(jìn)行有效性評(píng)估等

5、7步驟。聚類(lèi)過(guò)程：(1)數(shù)據(jù)準(zhǔn)備：包括特征標(biāo)準(zhǔn)化和降維。(2)特征選擇：從最初的特征中選擇最有效的特征，并將其存儲(chǔ)于向量中。(3)特征提?。和ㄟ^(guò)對(duì)所選擇的特征進(jìn)行轉(zhuǎn)換形成新的突出特征。(4)聚類(lèi)(或分組)：首先選擇合適特征類(lèi)型的某種距離函數(shù)或構(gòu)造新的距離函數(shù)進(jìn)行接近程度的度量，然后執(zhí)行聚類(lèi)或分組。(5)聚類(lèi)結(jié)果評(píng)估：是指對(duì)聚類(lèi)結(jié)果進(jìn)行評(píng)估。評(píng)估主要有3種：外部有效性評(píng)估、內(nèi)部有效性評(píng)估和相關(guān)性測(cè)試評(píng)估。2 聚類(lèi)算法的分類(lèi)聚類(lèi)屬于無(wú)監(jiān)督學(xué)習(xí)，它是一種常見(jiàn)的數(shù)據(jù)分析工具，其目的是把大量數(shù)據(jù)點(diǎn)的集合分成若干類(lèi)，使得每個(gè)類(lèi)中的數(shù)據(jù)之間最大程度地相似，而不同類(lèi)中的數(shù)據(jù)最大程度地不同。在多媒體信息檢索及數(shù)

6、據(jù)挖掘的過(guò)程中，聚類(lèi)處理對(duì)于建立高效的數(shù)據(jù)庫(kù)索引、實(shí)現(xiàn)快速準(zhǔn)確的信息檢索具有重要的理論和現(xiàn)實(shí)意義。本文將聚類(lèi)算法分為劃分聚類(lèi)算法、層次聚類(lèi)算法、基于密度的聚類(lèi)算法、基于網(wǎng)格的聚類(lèi)算法以及基于模型的聚類(lèi)算法。2.1 劃分聚類(lèi)算法給定一個(gè)包含n個(gè)樣本的數(shù)據(jù)對(duì)象的數(shù)據(jù)集，構(gòu)建數(shù)據(jù)的k個(gè)劃分(kn)，每個(gè)劃分表示一個(gè)聚類(lèi)。要滿(mǎn)足每個(gè)類(lèi)至少包含一個(gè)對(duì)象、每個(gè)對(duì)象屬于且僅屬于一個(gè)類(lèi)這兩個(gè)條件。創(chuàng)建一個(gè)劃分的數(shù)目為k的初始劃分，然后采用一種迭代的重定位技術(shù)，通過(guò)反復(fù)迭代來(lái)改進(jìn)劃分，直到滿(mǎn)足一個(gè)最優(yōu)的劃分。一個(gè)好的劃分的一般準(zhǔn)則是：在同一類(lèi)中的對(duì)象之間盡可能“相似”，不同類(lèi)中的對(duì)象之間盡可能“相異”4。其代表

7、算法有K-means、K-medoids5、大型數(shù)據(jù)庫(kù)劃分方法(CLARANS)等。很多算法都是由這三個(gè)算法改進(jìn)而來(lái)的，為了對(duì)大規(guī)模的數(shù)據(jù)集進(jìn)行聚類(lèi)，以及處理復(fù)雜形狀的聚類(lèi)，基于劃分的方法需要進(jìn)一步的擴(kuò)展。2.2 層次的聚類(lèi)算法層次法對(duì)給定的數(shù)據(jù)對(duì)象集合像樹(shù)一樣進(jìn)行層次似的分解,形成一棵聚類(lèi)樹(shù)。按層次分解的形成方式自底向上還是自頂向下，層次法可分為凝聚和分裂兩大類(lèi)。凝聚的方法，也稱(chēng)為自底向上的方法，首先將每個(gè)對(duì)象作為單獨(dú)的一個(gè)聚類(lèi)，然后根據(jù)性質(zhì)和規(guī)則相繼地合并相近的類(lèi)。直到所有的對(duì)象都合并為一個(gè)聚類(lèi)中(層次的最上層)，或者滿(mǎn)足一定的終止條件為止。而分裂的方法，也稱(chēng)為自頂向下的方法，正好與凝聚法

8、相反，首先將所有的對(duì)象都看做是一個(gè)聚類(lèi)，然后在每一步中，上層類(lèi)被分裂為下層更小的類(lèi)，直到每個(gè)類(lèi)只包含一個(gè)單獨(dú)的對(duì)象，或者也滿(mǎn)足一個(gè)終止條件為止。分裂算法將生成與凝聚方法完全相同的類(lèi)集，只是生成過(guò)程的次序完全相反 。層次的方法的缺陷在于，一旦一個(gè)步驟（合并或分裂）完成，它就不能被撤消。這個(gè)嚴(yán)格規(guī)定是有用的，由于不用擔(dān)心組合數(shù)目的不同選擇，計(jì)算代價(jià)會(huì)較小。代表算法有BIRCH,CURE等算法。2.3基于密度的聚類(lèi)算法絕大多數(shù)劃分方法基于對(duì)象之間的距離進(jìn)行聚類(lèi)。這樣的方法只能發(fā)現(xiàn)球狀的簇，而在發(fā)現(xiàn)任意形狀的簇上遇到了困難隨之提出了基于密度的另一類(lèi)聚類(lèi)方法，其主要思想是：只要臨近區(qū)域的密度（對(duì)象或數(shù)據(jù)

9、點(diǎn)的數(shù)目）超過(guò)某個(gè)閾值，就繼續(xù)聚類(lèi)。也就是說(shuō)，對(duì)給定類(lèi)中的每個(gè)數(shù)據(jù)點(diǎn)，在一個(gè)給定范圍的區(qū)域中必須包含至少某個(gè)數(shù)目的點(diǎn)。這樣的方法可以用來(lái)過(guò)濾“噪音”數(shù)據(jù)，發(fā)現(xiàn)任意形狀的簇。DBSCAN是一個(gè)有代表性的基于密度的方法，它根據(jù)一個(gè)密度閾值來(lái)控制簇的增長(zhǎng)。OPTICS 是另一個(gè)基于密度的方法，它為自動(dòng)的，交互的聚類(lèi)分析計(jì)算一個(gè)聚類(lèi)順序。2.4 基于網(wǎng)格的聚類(lèi)算法基于網(wǎng)格的方法把對(duì)象空間量化為有限數(shù)目的單元，形成一個(gè)網(wǎng)格結(jié)構(gòu)。所有的聚類(lèi)操作都基于這個(gè)網(wǎng)格結(jié)構(gòu)(即量化空間)上進(jìn)行。這種算法的優(yōu)點(diǎn)就是處理速度很快，并且其處理速度獨(dú)立于數(shù)據(jù)對(duì)象的數(shù)目，只與量化空間中每一維的單元數(shù)目有關(guān)。缺點(diǎn)是只能發(fā)現(xiàn)邊界是

10、水平或垂直的聚類(lèi)，而不能檢測(cè)到斜邊界。此類(lèi)算法也不適合維數(shù)較多的情況，因?yàn)榫S數(shù)的增加，網(wǎng)格單元會(huì)隨之呈指數(shù)增加。常見(jiàn)的基于網(wǎng)格的代表算法有STING、CLIQUE、WAVE-CLUSTER等8。2.5 基于模型的聚類(lèi)算法基于模型的聚類(lèi)方法就是設(shè)法優(yōu)化給定的數(shù)據(jù)和某些數(shù)學(xué)模型之間的適應(yīng)性，找出數(shù)據(jù)對(duì)給定模型的最佳擬合。該算法通過(guò)構(gòu)建反映數(shù)據(jù)點(diǎn)空間分布的密度函數(shù)來(lái)實(shí)現(xiàn)聚類(lèi)。它也基于標(biāo)準(zhǔn)的統(tǒng)計(jì)數(shù)字自動(dòng)決定聚類(lèi)的數(shù)目。通過(guò)統(tǒng)計(jì)數(shù)字來(lái)分析噪聲數(shù)據(jù)或孤立點(diǎn)，從而產(chǎn)生優(yōu)化的聚類(lèi)方法?；谀Ｐ偷姆椒ㄖ饕袃深?lèi)：統(tǒng)計(jì)學(xué)方法和網(wǎng)絡(luò)神經(jīng)方法8。其中，統(tǒng)計(jì)學(xué)方法有COBWEB算法，網(wǎng)絡(luò)神經(jīng)方法有SOM算法。3 典型的

11、聚類(lèi)算法分析3.1 K-means算法k-means 算法以k 為參數(shù)，把n 個(gè)對(duì)象分為k 個(gè)簇，以使類(lèi)內(nèi)具有較高的相似度，而類(lèi)間的相似度最低。相似度的計(jì)算根據(jù)一個(gè)簇中對(duì)象的平均值（被看作簇的重心）來(lái)進(jìn)行。首先，隨機(jī)地選擇k 個(gè)對(duì)象，每個(gè)對(duì)象初始地代表了一個(gè)簇中心。對(duì)剩余的每個(gè)對(duì)象，根據(jù)其與各個(gè)簇中心的距離，將它賦給最近的簇,然后重新計(jì)算每個(gè)簇的平均值。這個(gè)過(guò)程不斷重復(fù)，直到準(zhǔn)則函數(shù)收斂。但是k-means 方法只有在簇的平均值被定義的情況下才能使用。K-means 方法不適合于發(fā)現(xiàn)非凸面形狀的簇，或者大小差別很大的簇。而且，它對(duì)于“噪音”和孤立點(diǎn)數(shù)據(jù)是敏感的，少量的該類(lèi)數(shù)據(jù)能夠?qū)ζ骄诞a(chǎn)生極

12、大的影響。3.2 BIRCH算法BIRCH是個(gè)一次掃描就可以進(jìn)行較好的聚類(lèi)，它利用層次方法的平衡迭代進(jìn)行聚類(lèi)。其核心是用一個(gè)聚類(lèi)特征三元組表示一個(gè)簇的有關(guān)信息，從而使一簇點(diǎn)的表示可用對(duì)應(yīng)的聚類(lèi)特征。它通過(guò)構(gòu)造滿(mǎn)足分支因子和簇直徑（閾值）限制的聚類(lèi)特征樹(shù)來(lái)求聚類(lèi)。該算法通過(guò)聚類(lèi)特征可以方便地進(jìn)行中心、半徑、直徑及類(lèi)內(nèi)、類(lèi)間距離的運(yùn)算。算法具有對(duì)象數(shù)目的線(xiàn)性易伸縮性，及良好的聚類(lèi)質(zhì)量。如果簇不是球形，則該算法不能很好地工作。3.3 DBSCAN算法DBSCAN是基于密度的聚類(lèi)算法，可以將足夠高密度的區(qū)域分為簇，并可以在帶有“噪聲”的空間數(shù)據(jù)庫(kù)中發(fā)現(xiàn)任意形狀的類(lèi)。該算法利用類(lèi)的密度連通性可以快速發(fā)現(xiàn)

13、任意形狀的類(lèi)?；舅枷胧牵簩?duì)于一個(gè)類(lèi)中的每個(gè)對(duì)象，在其給定半徑的領(lǐng)域中包含的對(duì)象不能少于某一給定的最小數(shù)目。DBSCAN算法不進(jìn)行任何的預(yù)處理而直接對(duì)整個(gè)數(shù)據(jù)集進(jìn)行聚類(lèi)操作。當(dāng)數(shù)據(jù)量非常大時(shí)，就必須有大量?jī)?nèi)存支持，IO消耗也非常大。聚類(lèi)過(guò)程的大部分時(shí)間用在區(qū)域查詢(xún)操作上。DBSCAN算法的優(yōu)點(diǎn)是能夠發(fā)現(xiàn)空間數(shù)據(jù)庫(kù)中任意形狀的密度連通集；在給定合適的參數(shù)條件下，能很好地處理噪聲點(diǎn)；對(duì)用戶(hù)領(lǐng)域知識(shí)要求較少。缺點(diǎn)是對(duì)數(shù)據(jù)的輸入順序不太敏感；適用于大型數(shù)據(jù)庫(kù)，但DBSCAN算法要求事先指定領(lǐng)域和閾值，具體使用的參數(shù)依賴(lài)于應(yīng)用的目的。3.4 STING算法STING是一種網(wǎng)格的多分辨率聚類(lèi)技術(shù)。它將空間

14、區(qū)域劃分為矩形單元，針對(duì)不同級(jí)別的分辨率，通常存在多個(gè)級(jí)別的矩形單元，這些單元形成一個(gè)層次結(jié)構(gòu)：高層的每個(gè)單元被劃分為多個(gè)低一層的單元。高層單元的統(tǒng)計(jì)參數(shù)可以很容易地從底層單元計(jì)算得到。STING 是獨(dú)立于查詢(xún)的，有利于并行處理和增量更新。但由于STING 采用了一個(gè)多分辨率的方法來(lái)進(jìn)行聚類(lèi)分析，聚類(lèi)的質(zhì)量取決于網(wǎng)格結(jié)構(gòu)的最低層粒度。如果數(shù)據(jù)粒度比較細(xì)，處理的代價(jià)明顯增加。并且STING在構(gòu)建一個(gè)父單元時(shí)沒(méi)有考慮子單元和其相鄰單元之間的關(guān)系。因此，盡管該技術(shù)處理速度快，但可能降低簇的質(zhì)量和精確性。3.5 COBWEB算法COBWEB算法以一個(gè)分類(lèi)樹(shù)的形式創(chuàng)建層次聚類(lèi)，它的輸入對(duì)象用“分類(lèi)屬性”

15、-“值”來(lái)描述。其工作流程是：在給定一個(gè)新的對(duì)象后，COBWEB沿一條適當(dāng)?shù)穆窂较蛳?，修改?jì)數(shù)，以尋找可以分類(lèi)該對(duì)象的最好節(jié)點(diǎn)。該判定基于將對(duì)象臨時(shí)置于每個(gè)節(jié)點(diǎn)，并計(jì)算結(jié)果劃分的分類(lèi)效用。產(chǎn)生最高分類(lèi)效用的位置應(yīng)當(dāng)是對(duì)象節(jié)點(diǎn)的一個(gè)好的選擇。COBWEB算法的優(yōu)點(diǎn)是可以自動(dòng)修正劃分中類(lèi)的數(shù)目；不需要用戶(hù)提供輸入?yún)?shù)。其缺點(diǎn)是COBWEB算法是基于這樣一個(gè)假設(shè)：在每個(gè)屬性上的概率分布是彼此獨(dú)立的，但這個(gè)假設(shè)并不總是成立。因此，分類(lèi)樹(shù)對(duì)于偏斜的輸入數(shù)據(jù)不是高度平衡的，它可能導(dǎo)致時(shí)間和空間復(fù)雜性的劇烈變化。COBWEB不適用于聚類(lèi)大型數(shù)據(jù)庫(kù)的數(shù)據(jù)。4 總結(jié)與展望通過(guò)以上的分析得知，沒(méi)有一種算法是十全十

16、美的。在選擇算法時(shí)，要根據(jù)具體情況而定，也可以結(jié)合多個(gè)算法使用。例如發(fā)現(xiàn)聚類(lèi)的形狀、數(shù)據(jù)輸入順序是否敏感、適用數(shù)據(jù)庫(kù)的大小或者算法效率，來(lái)選擇聚類(lèi)算法。一般情況下有以下結(jié)論6：(1)目標(biāo)數(shù)據(jù)庫(kù)如果比較大，建議使用綜合性的聚類(lèi)算法，如：BIRCH、CURE、DBSCAN和STING等。以提高算法效率。(2)如果聚類(lèi)的形狀是球形或者凸形，BIRCH和CLARANS比較適合。(3)一般而言，聚類(lèi)算法對(duì)數(shù)據(jù)輸入的順序都比較敏感。如果希望不敏感，可以選用基于網(wǎng)格的STING算法。(4)將不同類(lèi)型的聚類(lèi)算法相互結(jié)合(例如BIRCH算法和CURE算法)，綜合各自的優(yōu)點(diǎn)。以滿(mǎn)足不同的聚類(lèi)要求，是今后聚類(lèi)算法的

17、一個(gè)重要發(fā)展方向。聚類(lèi)分析是數(shù)據(jù)挖掘中一種非常有用的技術(shù)，它可作為特征和分類(lèi)算法的預(yù)處理步驟，也可將聚類(lèi)結(jié)果用于進(jìn)一步關(guān)聯(lián)分析，還可以作為一個(gè)獨(dú)立的工具來(lái)獲得數(shù)據(jù)分布的情況。聚類(lèi)算法的研究具有廣泛的應(yīng)用前景，其今后的發(fā)展也面臨著越來(lái)越多的挑戰(zhàn)。首先是聚類(lèi)算法的選擇，建議使用者根據(jù)實(shí)際情況(例如發(fā)現(xiàn)聚類(lèi)的形狀、數(shù)據(jù)輸人顧序是否敏感、適用數(shù)據(jù)庫(kù)的大小或者算法效率)來(lái)選擇合適的聚類(lèi)算法。其次，對(duì)于特征數(shù)據(jù)本身所具備的高維性、復(fù)雜性、動(dòng)態(tài)性以及容易達(dá)到大規(guī)模的特性，聚類(lèi)算法的設(shè)計(jì)還應(yīng)該更多地考慮融合不同的聚類(lèi)思想形成新的聚類(lèi)算法，從而綜合利用不同聚類(lèi)算法的優(yōu)點(diǎn)。參考文獻(xiàn)1 張銀奎，廖麗，宋俊等譯.數(shù)據(jù)

18、挖掘原理.機(jī)械工業(yè)出版社，20032 楊杰，姚莉秀.數(shù)據(jù)挖掘技術(shù)及其應(yīng)用.上海交通大學(xué)出版社，20113 閃四清，陳茵，程雁等譯.數(shù)據(jù)挖掘概念、模型、方法和算法.清華大學(xué)出版社.20034 洪松林，莊映輝，李堃.數(shù)據(jù)挖掘技術(shù)與工程實(shí)踐.機(jī)械工業(yè)出版社.20145 呂紀(jì)榮，王士虎.數(shù)據(jù)中聚類(lèi)算法研究綜述.理論廣角.2014.1(下)6 胡慶林，葉念渝，朱明富.數(shù)據(jù)挖掘中聚類(lèi)算法的綜述.計(jì)算機(jī)與數(shù)字工程.2007第2期7 應(yīng)劭霖.數(shù)據(jù)挖掘中的聚類(lèi)算綜述.2014.68 方媛，車(chē)啟鳳.數(shù)據(jù)挖掘之聚類(lèi)算法綜述.河西學(xué)院學(xué)報(bào).2012第5期9 蔡偉杰，張曉輝，朱建秋，朱揚(yáng)勇關(guān)聯(lián)規(guī)則挖掘綜述，200410 薛惠鋒，張文字，寇曉東智能數(shù)握挖掘技術(shù)西安：西北工業(yè)大學(xué)出版社.200511 王光宏，蔣平數(shù)據(jù)挖掘綜述同濟(jì)大學(xué)學(xué)報(bào)2004年2月12 Hart J W，Micheline K數(shù)據(jù)