畢業(yè)設(shè)計（論文）文獻綜述：基于聚類分析的圖像分割算法

畢業(yè)設(shè)計（論文）--文獻綜述綜述題目基于聚類分析的圖像分割算法專業(yè)信息與計算科學(xué)姓名學(xué)號指導(dǎo)教師基于聚類分析的圖像分割算法摘要：聚類是數(shù)據(jù)挖掘的重要工具，根據(jù)數(shù)據(jù)間的相似性將數(shù)據(jù)庫分成多個類，每類中數(shù)據(jù)應(yīng)盡可能相似。從機器學(xué)習(xí)的觀點來看，類相當(dāng)于隱藏模式，尋找類是無監(jiān)督學(xué)習(xí)過程。目前己有應(yīng)用于統(tǒng)計、模式識別、機器學(xué)習(xí)等不同領(lǐng)域的幾十種聚類算法。本文對數(shù)據(jù)挖掘中的聚類算法進行了歸納和分類，總結(jié)了幾類算法并分析了其性能特點。關(guān)鍵詞：聚類分析；數(shù)據(jù)挖掘ImageSegmentationAlgorithmBasedonClusterAnalysisShenHuanxia（SchoolofMathematicsandPhysics,AnhuiUniversityofArchitecture,Hefei230601）Abstract:Clusteringisanimportanttoolfordatamining.Thedatabaseisdividedintomultipleclassesaccordingtothesimilaritybetweendata.Thedataineachcategoryshouldbeassimilaraspossible.Fromthepointofviewofmachinelearning,theclassisequivalenttothehiddenpattern,lookingforclassesisunsupervisedlearningprocess.Therearedozensofclusteringalgorithmsthathavebeenusedinstatistics,patternrecognition,andmachinelearning.Inthispaper,theclusteringalgorithmsindataminingaresummarizedandclassified,andseveralalgorithmsaresummarizedandtheirperformancecharacteristicsareanalyzed.Keywords:Clusteringanalysis;datamining1引言聚類是指將數(shù)據(jù)分類到不同的類或者簇這樣的一個過程所以同一個簇中的對象有很大的相似性，而不同簇間的對象有很大的相異性。聚類分析[7]是指將物理或抽象對象的集合分組為由類似的對象組成的多個類的分析過程，它是一種探索性的群組統(tǒng)計分析技術(shù)。在分析的過程中，人們不必事先給出一個分類的標準，聚類分析能夠從樣本數(shù)據(jù)出發(fā)，自動進行分類，所使用的方法不同，常常會得到不同的結(jié)論，不同研究者對于同一組數(shù)據(jù)進行聚類分析，所得到的聚類數(shù)未必一致。聚類分析的目標就是在相似的基礎(chǔ)上收集數(shù)據(jù)來分類。聚類源于很多領(lǐng)域，包括數(shù)學(xué)、計算機科學(xué)、統(tǒng)計學(xué)、生物學(xué)和經(jīng)濟學(xué)，在不同的應(yīng)用領(lǐng)域，很多聚類技術(shù)都得到了發(fā)展，這些技術(shù)方法被用作描述數(shù)據(jù)，衡量不同數(shù)據(jù)源間的相似性，以及把數(shù)據(jù)源分類到不同的簇中[1][2]。聚類方法的特征如下：1.聚類分析簡單直觀；2.聚類分析主要應(yīng)用于探索性的研究，其分析的結(jié)果可以提供多個可能的解，選擇最終的解需要研究者的主觀判斷和后續(xù)分析；3.不管實際數(shù)據(jù)中是否真正存在不同的，利用聚類分析都能得到分成若干類別的解；4.聚類分析的解完全依賴于研究者所選擇的聚類變量，增加或刪除一些變量對最終的解都可能產(chǎn)生實質(zhì)性的影響；5.研究者在使用聚類分析時應(yīng)特別注意可能影響結(jié)果的各個因素；6.異常值和特殊的變量對聚類有較大影響，當(dāng)分類變量的測量尺度不一致時，需要事先做標準化處理。2聚類分析方法1）劃分聚類算法假設(shè)數(shù)據(jù)集有N個像素或者記錄，劃分方法將這N個像素分為K個組，代表K個聚類，這K個分組必須滿足每個分組都不為空，同時每個記錄必須只存在于其中一個分組。通過反復(fù)的迭代計算改變分組中的數(shù)據(jù)，最終使相似的記錄屬于同一個分組，不相似的記錄在不同的分組。經(jīng)典的劃分聚類算法有：K-means：一種典型的劃分聚類算法，它用一個聚類的中心來代表一個簇，即在迭代過程中選擇的聚點不一定是聚類中的一個點，該算法只能處理數(shù)值型數(shù)據(jù)[3]。K-modes：K-Means算法的擴展，采用簡單匹配方法來度量分類型數(shù)據(jù)的相似度。K-medoids：在迭代過程中選擇簇中的某點作為聚點，PAM是典型的k-medoids算法。PCM：模糊集合理論引入聚類分析中并提出了PCM模糊聚類算法。2）層次聚類算法層次聚類算法是將數(shù)據(jù)對象想象成一棵聚類的樹，根據(jù)樹的方向通過自上而下或自下而上的方式完成聚類過程。自上而下的方式叫做分列式的層次聚類，從整個對象開始，不斷將屬于不同聚類的元素分裂出去，直到達到某個終止條件。自下而上的方式叫做聚合式的層次聚類，將集合中的每個對象都作為一個初始簇，通過一定方法判斷相似的簇合并成一個簇，不斷反復(fù)，直到不再有合并過程發(fā)生[4]。3）密度聚類算法利用數(shù)據(jù)樣本分布的密度作為相似性測度，把密度相似的樣本聚為一個類，該方法進行聚類時不需要知道樣本的分布情況，所以優(yōu)點是能發(fā)現(xiàn)數(shù)據(jù)樣本中各種形狀的聚類。經(jīng)典的密度聚類方法大致分為基于高密度鏈接區(qū)域的密度聚類和基于密度分布函數(shù)的聚類，主要有：DBSCAN：該算法采用空間索引技術(shù)來搜索對象的鄰域，引入了“核心對象”和“密度可達”等概念，從核心對象出發(fā)，把所有密度可達的對象組成一個簇。GDBSCAN：通過泛化DBSCAN算法中鄰域的概念，以適應(yīng)空間對象的特點。4）模型聚類算法將數(shù)據(jù)和模型很好地結(jié)合在一起，在對數(shù)據(jù)的處理中有效地利用了某些數(shù)學(xué)模型。該方法主要分為兩類：統(tǒng)計學(xué)方法和神經(jīng)網(wǎng)絡(luò)方法?；诮y(tǒng)計學(xué)的聚類算法：COBWeb：是一個通用的概念聚類方法，是基于機器學(xué)習(xí)的聚類方法，對于需要處理的數(shù)據(jù)對象，概念聚類能通過機器學(xué)習(xí)的方式形成對象的分類模式，利用分類模式將待處理的數(shù)據(jù)對象進行分類，同時描述了每組對象的特征，使每組對象能夠代表一個類或者概念。AutoClass：是以概率混合模型為基礎(chǔ)，利用屬性的概率分布來描述聚類，該方法能夠處理混合型的數(shù)據(jù)，但要求各屬性相互獨立?；谏窠?jīng)網(wǎng)絡(luò)的聚類算法[5]：自組織神經(jīng)網(wǎng)絡(luò)SOM：該方法的基本思想是--由外界輸入不同的樣本到人工的自組織映射網(wǎng)絡(luò)中，一開始時，輸入樣本引起輸出興奮細胞的位置各不相同，但自組織后會形成一些細胞群，它們分別代表了輸入樣本，反映了輸入樣本的特征。3總結(jié)聚類算法總結(jié)：對聚類進行研究是數(shù)據(jù)挖掘中的一個熱門方向，由于以上所介紹的聚類方法都存在著某些缺點，因此近些年對于聚類分析的研究很多都專注于改進現(xiàn)有的聚類方法或者是提出一種新的聚類方法。以下將對傳統(tǒng)聚類方法中存在的問題以及人們在這些問題上所做的努力做一個簡單的總結(jié)：

1、從以上對傳統(tǒng)的聚類分析方法所做的總結(jié)來看，不管是k-means方法，還是CURE方法，在進行聚類之前都需要用戶事先確定要得到的聚類的數(shù)目。然而在現(xiàn)實數(shù)據(jù)中，聚類的數(shù)目是未知的，通常要經(jīng)過不斷的實驗來獲得合適的聚類數(shù)目[6]，得到較好的聚類結(jié)果。

2、傳統(tǒng)的聚類方法一般都是適合于某種情況的聚類，沒有一種方法能夠滿足各種情況下的聚類，比如BIRCH方法[7]對于球狀簇有很好的聚類性能，但是對于不規(guī)則的聚類，則不能很好的工作；K-medoids方法不太受孤立點的影響，但是其計算代價又很大。因此如何解決這個問題成為當(dāng)前的一個研究熱點，有學(xué)者提出將不同的聚類思想進行融合以形成新的聚類算法，從而綜合利用不同聚類算法的優(yōu)點，在一次聚類過程中綜合利用多種聚類方法，能夠有效的緩解這個問題。

3、隨著信息時代的到來，對大量的數(shù)據(jù)進行分析處理是一個很龐大的工作，這就關(guān)系到一個計算效率的問題。有文獻提出了一種基于最小生成樹的聚類算法[8]，該算法通過逐漸丟棄最長的邊來實現(xiàn)聚類結(jié)果，當(dāng)某條邊的長度超過了某個閾值，那么更長邊就不需要計算而直接丟棄，這樣就極大地提高了計算效率，降低了計算成本。

4、處理大規(guī)模數(shù)據(jù)和高維數(shù)據(jù)的能力有待于提高。目前許多聚類方法處理小規(guī)模數(shù)據(jù)和低維數(shù)據(jù)時性能比較好，但是當(dāng)數(shù)據(jù)規(guī)模增大，維度升高時，性能就會急劇下降，比如k-medoids方法處理小規(guī)模數(shù)據(jù)時性能很好，但是隨著數(shù)據(jù)量增多，效率就逐漸下降，而現(xiàn)實生活中的數(shù)據(jù)大部分又都屬于規(guī)模比較大、維度比較高的數(shù)據(jù)集。有文獻提出了一種在高維空間挖掘映射聚類的方法PCKA[9]，它從多個維度中選擇屬性相關(guān)的維度，去除不相關(guān)的維度，沿著相關(guān)維度進行聚類，以此對高維數(shù)據(jù)進行聚類。

5、目前的許多算法都只是理論上的，經(jīng)常處于某種假設(shè)之下，比如聚類能很好的被分離，沒有突出的孤立點等，但是現(xiàn)實數(shù)據(jù)通常是很復(fù)雜的，噪聲很大，因此如何有效的消除噪聲的影響，提高處理現(xiàn)實數(shù)據(jù)的能力還有待進一步的提高。參考文獻[1]OwsińskiJ.Machine-partgroupingandclusteranalysis:similarities,distancesandgroupingcriteria[J].BulletinofthePolishAcademyofSciencesTechnicalSciences,2010,57(3):217-228.[2]王駿,王士同,鄧趙紅.聚類分析研究中的若干問題[J].控制與決策,2012,27(3):321-328.[3]BhartiK,JainS,ShuklaS.FuzzyK-meanClusteringViaRandomForestForIntrusiionDetectionSystem[J].InternationalJournalonComputerScience&Engineering,2010,2(6):315-318.[4]段明秀.層次聚類算法的研究及應(yīng)用[D].中南大學(xué),2009.[5]馮曉毅,周鳳岐.圖象分割的一種神經(jīng)網(wǎng)絡(luò)實現(xiàn)方法[J].計算機工程與科學(xué),2000,22(2):70-72.[6]周世兵.聚類分析中的最佳聚類數(shù)確定方法研究及應(yīng)用[D].江南大學(xué),2011.[7]周迎春,駱嘉偉.一種改進的BIRCH聚類分析算法及其應(yīng)用研究[J].嶺南師范學(xué)院學(xué)報,2009,30(3):83-87.[8]ChenJA,ShihCC,LinPF,etal.Collaborativeevaluationa