基于聚類分析的圖像分割研究畢業(yè)論文.doc

南京郵電大學(xué)通達(dá)學(xué)院畢 業(yè) 設(shè) 計(jì)（論 文）題 目： 基于聚類分析的圖像分割研究 專 業(yè)： 信息工程 學(xué)生姓名： 朱丹青 班級(jí)學(xué)號(hào)： 100002 10000215 指導(dǎo)教師： 李雷 指導(dǎo)單位： 理學(xué)院 日期： 2014 年 1月 16 日 至 2014 年 6 月 13 日畢業(yè)設(shè)計(jì)（論文）原創(chuàng)性聲明本人鄭重聲明：所提交的畢業(yè)設(shè)計(jì)（論文），是本人在導(dǎo)師指導(dǎo)下，獨(dú)立進(jìn)行研究工作所取得的成果。除文中已注明引用的內(nèi)容外，本畢業(yè)設(shè)計(jì)（論文）不包含任何其他個(gè)人或集體已經(jīng)發(fā)表或撰寫(xiě)過(guò)的作品成果。對(duì)本研究做出過(guò)重要貢獻(xiàn)的個(gè)人和集體，均已在文中以明確方式標(biāo)明并表示了謝意。 論文作者簽名： 日期： 年 6月 2日 目錄第一章 緒論11.1圖像分割的背景及意義11.2圖像分割的研究現(xiàn)狀31.3本文的主要工作5第二章 聚類分析理論72.1 聚類分析概述72.2 常見(jiàn)的聚類算法122.3 模糊聚類算法142.4圖像分割方法162.5本章總結(jié)18第三章 基于k-means算法的圖像分割方法193.1顏色空間193.2定義和概述193.3 簡(jiǎn)單的例子介紹213.4 k-means圖像分割233.5改進(jìn)的k-均值聚類圖像分割算法273.6本章總結(jié)31第四章 基于fcm算法的圖像分割324.1模糊聚類的概念324.2fcm算法的概述344.3本章總結(jié)43總結(jié)與展望445.1總結(jié)445.2研究展望45結(jié)束語(yǔ)46致謝47參考文獻(xiàn)48附錄a52基于k-means算法的matlab源程序52附錄b54基于k-均值聚類改進(jìn)前的matlab源程序54附錄c57基于fcm聚類算法的matlab源程序57摘 要在飛速發(fā)展的信息時(shí)代，圖像是人類獲取信息的重要手段之一，因而圖像的處理就變得極其重要。而圖像分割通常是為了進(jìn)一步對(duì)圖像進(jìn)行分析、識(shí)別、跟蹤、理解、壓縮編碼等，分割的好壞直接影響后期的圖像識(shí)別和理解。圖像分割是指將一幅圖像分解成若干互不相交區(qū)域的集合，其實(shí)質(zhì)是一個(gè)像素的聚類過(guò)程。本文以圖像分割的聚類實(shí)質(zhì)為線索，對(duì)近幾年國(guó)內(nèi)外最新的圖像分割算法進(jìn)行了分析比較，指出了聚類在這個(gè)領(lǐng)域的重要性。本論文針對(duì)聚類算法在圖像分割中的應(yīng)用，主要涉及了以下幾個(gè)內(nèi)容：（1）詳細(xì)介紹當(dāng)前圖像分割以及聚類分析的研究背景，現(xiàn)狀。（2）對(duì)基于模糊k均值的圖像分割算法進(jìn)行探討，并對(duì)k均值算法進(jìn)行改進(jìn)，通過(guò)粗糙集理論提供 k-均值聚類所需要的初始類的個(gè)數(shù)和均值，提高了聚類的效率和分類的精度。（3）對(duì)基于標(biāo)準(zhǔn)模糊 c 均值聚類的圖像分割算法進(jìn)行了探討，研究了基于模糊聚類的圖像分割方法中初始類別數(shù)的選取、初始類中心和初始隸屬度矩陣的確定等問(wèn)題。（4）將基于模糊k均值的圖像分割算法與基于標(biāo)準(zhǔn)模糊 c 均值聚類的圖像分割算法進(jìn)行對(duì)比分析。關(guān)鍵詞： 聚類分析， 模糊聚類，圖像分割，k均值算法，c均值算法abstract the rapid development in the information age , the image is an important means of human access to information , and thus the image processing becomes extremely important. and the image segmentation of the image is usually performed to further analysis, identification , tracking , understanding , compression , etc., directly affects the post- split image recognition and understanding.image segmentation refers to the collection of an image is decomposed into several disjoint regions , and its essence is a pixel clustering process . in this paper, image segmentation clustering substantive clue , at home and abroad in recent years, image segmentation algorithms are analyzed and compared , pointed out the importance of clustering in this field . this thesis clustering algorithm for image segmentation , mainly related to the following elements :( 1 ) a detailed description of current research background image segmentation and clustering analysis of the status .( 2 ) image segmentation algorithm based on fuzzy k-means were discussed , and the k-means algorithm is improved , providing the initial class and the mean number of k- means clustering required by rough set theory , improve the efficiency of clustering and classification accuracy.( 3 ) the standard image segmentation algorithm based on fuzzy c -means clustering were discussed , studied to select the initial number of categories based on fuzzy clustering method of image segmentation , determining the initial cluster centers and the initial membership matrix of other issues.( 4 ) the segmentation algorithm for image segmentation algorithm based on fuzzy c-means clustering standard comparative analysis based on k-means fuzzy image .keywords: cluster analysis , fuzzy clustering , image segmentation , k -means algorithm , c -means algorithm南京郵電大學(xué)通達(dá)學(xué)院2014屆本科生畢業(yè)設(shè)計(jì)(論文)第一章 緒論 在當(dāng)前快速發(fā)展信息化時(shí)代，通過(guò)圖像來(lái)獲取信息是人類認(rèn)識(shí)世界改造世界的重要方式之一，由此看來(lái)圖像的處理就變得十分重要1。圖像處理(image processing)，用計(jì)算機(jī)對(duì)圖像進(jìn)行分析，以達(dá)到所需結(jié)果的技術(shù)。又稱影像處理。基本內(nèi)容 圖像處理一般指數(shù)字圖像處理。數(shù)字圖像是指用數(shù)字?jǐn)z像機(jī)、掃描儀等設(shè)備經(jīng)過(guò)采樣和數(shù)字化得到的一個(gè)大的二維數(shù)組，該數(shù)組的元素稱為像素，其值為一整數(shù)，稱為灰度值。圖像處理技術(shù)的主要內(nèi)容包括圖像壓縮，增強(qiáng)和復(fù)原，匹配、描述和識(shí)別3個(gè)部分2。 常見(jiàn)的處理有圖像數(shù)字化、圖像編碼、圖像增強(qiáng)、圖像復(fù)原、圖像分割和圖像分析等。其中圖像分割的目的是為了后續(xù)對(duì)圖像進(jìn)行分析、識(shí)別、跟蹤、理解、壓縮編碼等，分割的準(zhǔn)確性直接影響后續(xù)任務(wù)的效果，具有極其重要的意義。所以本課題將研究方向確定在利用圖像分割技術(shù)來(lái)進(jìn)行圖像的識(shí)別3。1.1圖像分割的背景及意義 聚類分析研究有很長(zhǎng)的歷史，幾十年來(lái)，其重要性及其研究方向的交叉特性得到人們的肯定。聚類分析是數(shù)據(jù)挖掘研究方向的重要研究?jī)?nèi)容之一，在識(shí)別數(shù)據(jù)的內(nèi)在結(jié)構(gòu)方面有極其重要的作用。數(shù)據(jù)挖掘技術(shù)是從上世紀(jì)80年代開(kāi)始發(fā)展起來(lái)的一門交叉學(xué)科，涉及到數(shù)據(jù)庫(kù)、統(tǒng)計(jì)學(xué)、人工智能和機(jī)器學(xué)習(xí)多個(gè)領(lǐng)域。計(jì)算機(jī)的應(yīng)用普及產(chǎn)生了大量數(shù)據(jù)，數(shù)據(jù)挖掘就是利用上述學(xué)科的技術(shù)進(jìn)行大量的數(shù)據(jù)處理。數(shù)據(jù)挖掘的應(yīng)用范圍非常的廣泛，從農(nóng)業(yè)生產(chǎn)的預(yù)測(cè)到基因分類，從信用卡欺詐到稅務(wù)稽查，數(shù)據(jù)挖掘技術(shù)對(duì)未來(lái)社會(huì)的各個(gè)領(lǐng)域?qū)⑵鸬皆絹?lái)越大的作用4。 在一副圖像中，我們?cè)谕ǔＧ闆r下只是對(duì)其中的某些目標(biāo)感興趣，它們通常在要分割的圖像中占據(jù)一定的區(qū)域，而且在某些特性上與周圍的圖像存在一定的差別。這些差別有時(shí)候可能是特別明顯的，也有可能是非常微小的，以至于人的肉眼無(wú)法察覺(jué)的到的。圖像分割是按照一定的制約規(guī)則把圖像劃分為若干個(gè)互不相交，具有特定性質(zhì)的區(qū)域,是把我們關(guān)注的區(qū)域從需要分割的圖像中提取出來(lái)，從此進(jìn)行進(jìn)一步研究和處理的技術(shù)。它使得其中的圖像分析和識(shí)別等處理過(guò)程中所要處理的數(shù)據(jù)量大大減少了，同時(shí)有保留了有關(guān)圖像結(jié)構(gòu)特征的信息。圖像分割的結(jié)果是圖像特征提取和識(shí)別等圖像理解的基礎(chǔ)，對(duì)圖像分割的研究一直是數(shù)字圖像處理技術(shù)的焦點(diǎn)和熱點(diǎn)。關(guān)于圖像分割的概念有很多，但最終都?xì)w于一個(gè)基本思想，即圖像分割時(shí)根據(jù)實(shí)際需求與應(yīng)用，按照指定特征信息，對(duì)圖像中有意義的邊界、興趣區(qū)域或者對(duì)相一致的區(qū)域（灰度、顏色、紋理等）進(jìn)行分解和提取的技術(shù)和過(guò)程5。 圖像分割的數(shù)學(xué)解釋：假定一幅圖像中所有像素的集合為，有關(guān)均勻性的假設(shè)為。分割定義把劃分為若干子集，其中每個(gè)子集都構(gòu)成一個(gè)空間連通區(qū)域。用四個(gè)條件進(jìn)行數(shù)學(xué)描述，即6：；。式中，為空集。 圖像分割的重要性，可以從圖像工程的三個(gè)層次來(lái)理解，如圖1.1所示。圖像工程是指對(duì)圖像進(jìn)行采樣、量化、編碼、傳輸、增強(qiáng)、邊緣檢測(cè)、分割、形態(tài)分析、目標(biāo)識(shí)別、目標(biāo)表達(dá)等一系列的加工處理、分析和理解的綜合工程技術(shù)。 圖像工程根據(jù)抽象程度和研究方法的不同分為三個(gè)層次：圖像處理、圖像分析和圖像理解。而圖像分割是圖像識(shí)別和圖像理解的基礎(chǔ)，分割的好壞結(jié)果直接影響到后期的識(shí)別和理解7。 圖1.1圖像分割在圖像工程中的位置 圖像分割在實(shí)際中也已得到廣泛的應(yīng)用，例如在工業(yè)自動(dòng)化，在線產(chǎn)品檢驗(yàn)，以及軍事、體育、農(nóng)業(yè)工程等方面8。概括來(lái)說(shuō)，在各種圖像應(yīng)用中，只要需對(duì)圖像目標(biāo)進(jìn)行提取，測(cè)量等都離不開(kāi)圖像分割。 圖像分割技術(shù)的發(fā)展與許多其它學(xué)科和領(lǐng)域，例如數(shù)學(xué)、物理、心理學(xué)、電子學(xué)、計(jì)算機(jī)科學(xué)等學(xué)科密切相關(guān)。近年來(lái)，隨著各學(xué)科許多新理論和方法的提出，人們也提出了許多結(jié)合一些特定理論、方法和工具的分割技術(shù)9。每當(dāng)有新的數(shù)學(xué)工具或方法提出來(lái)，人們就試著將其用于圖像分割，因而提出了不少特殊的算法。例如利用馬爾可夫隨機(jī)場(chǎng)、數(shù)學(xué)形態(tài)學(xué)、模擬退火、遺傳算法、聚類分析。新的分割算法還在不斷涌現(xiàn)。其中，基于聚類分析的圖像分割方法是圖像分割領(lǐng)域中一類極其重要和應(yīng)用相當(dāng)廣泛的算法，其在應(yīng)用領(lǐng)域取得的巨大成功引起了廣大關(guān)注10。 1.2圖像分割的研究現(xiàn)狀 基于聚類分析的圖像分割方法是圖像領(lǐng)域中一類極其重要和應(yīng)用相當(dāng)廣泛的算法，無(wú)論是灰度圖像分割、彩色圖像分割還是紋理圖像或者其他類型的圖像分割，都可運(yùn)用聚類分析方法11。 聚類是把具有相似性質(zhì)的事物區(qū)分開(kāi)并加以分類，它是運(yùn)用數(shù)學(xué)方法對(duì)處理給定對(duì)象的進(jìn)行分類。聚類問(wèn)題是一個(gè)古老的問(wèn)題，是伴隨人類的產(chǎn)生和發(fā)展而不斷深化的一個(gè)問(wèn)題，有關(guān)聚類分析的理論和應(yīng)用的研究己有大量的文獻(xiàn)。經(jīng)典分類學(xué)是從單個(gè)因素或有限幾個(gè)因素出發(fā)，憑經(jīng)驗(yàn)和專業(yè)知識(shí)對(duì)事物分類，這種分類具有非此即彼的特性，分出的類別界限很清晰。隨著認(rèn)識(shí)的深入，發(fā)現(xiàn)這種分類不適用于具有模糊性的分類問(wèn)題，如圖像中的區(qū)域之間的邊界就往往是模糊不清的。模糊數(shù)學(xué)的產(chǎn)生為上述軟分類提供了數(shù)學(xué)基礎(chǔ)，由此產(chǎn)生了模糊聚類分析12。 用普通數(shù)學(xué)方法進(jìn)行分類的聚類法稱為普通聚類分析，而把應(yīng)用模糊數(shù)學(xué)方法進(jìn)行分析的聚類分析稱為模糊聚類分析。由于圖像技術(shù)本身的復(fù)雜性和相關(guān)性，在圖像處理過(guò)程中出現(xiàn)了不確定性和不精確性。這種不確定性和不精確性主要體現(xiàn)在圖像灰度的不確定性、幾何形狀的不確定性和不確定性知識(shí)等。這種不確定性是經(jīng)典的數(shù)學(xué)理論無(wú)法解決的，并且這種不確定性不是隨機(jī)的，因而不適于用概率論來(lái)解決13。 因?yàn)槟：碚搶?duì)于圖像的這種不確定性有很好的描述能力，所以可以引入模糊理論作為有效描述圖像特點(diǎn)和人的視覺(jué)特性的模型和方法。近年來(lái)一些學(xué)者致力于將模糊理論引入到圖像處理中，取得很好的效果，經(jīng)過(guò)專家學(xué)者幾十年的研究，圖像的模糊處理技術(shù)獲得極大的發(fā)展。基于模糊理論的圖像分割方法主要可分為模糊閾值分割和模糊聚類分割。圖像分割的實(shí)質(zhì)簡(jiǎn)單地說(shuō)是一個(gè)按照像素屬性（灰度，紋理，顏色等）聚類的過(guò)程14。 因此，聚類分析就廣泛應(yīng)用于圖像分割之中。其中模糊聚類分割方法是最先提出、也是最經(jīng)典的一種圖像模糊分割方法。本文中基于聚類分析的圖像分割算法主要是針對(duì)模糊聚類算法應(yīng)用于圖像分割中的介紹和研究。實(shí)際中應(yīng)用最為廣泛的模糊聚類方法是模糊c-均值算法(fuzzy c-means)，簡(jiǎn)稱fcm，本文中的模糊聚類算法也特指模糊c均值算法15。fcm算法首先是由ruspini提出的，但真正有效的方法是由dunn給出的。1974 年dunn將硬c-均值聚類算法推廣到模糊情形，同年，bezdek將dunn的方法一般化，建立了模糊c-均值聚類理論。1980 年bezdek又證明了模糊c-均值聚類算法的收斂性，并討論了模糊c-均值聚類算法與硬c-均值聚類算法的關(guān)系16。從此，基于目標(biāo)函數(shù)的模糊聚類方法蓬勃發(fā)展起來(lái)，目前從不同的角度對(duì)基于目標(biāo)函數(shù)的模糊聚類方法進(jìn)行研究，歸納起來(lái)主要集中在以下四個(gè)方面：模糊聚類新方法的研究、實(shí)現(xiàn)途徑的研究、聚類有效性的研究和模糊聚類的應(yīng)用研究。 fcm 算法采用迭代法優(yōu)化目標(biāo)函數(shù)來(lái)獲得對(duì)數(shù)據(jù)集的模糊分類，算法具有很好的收斂性。采用模糊 c-均值聚類的方法進(jìn)行圖像分割的優(yōu)點(diǎn)是避免了設(shè)定閾值的問(wèn)題，并且能解決閾值化分割難以解決的多個(gè)分支的分割問(wèn)題。fcm 適合于圖像中存在不確定性和模糊性的特點(diǎn)，同時(shí) fcm 算法是屬于無(wú)監(jiān)督的分類方法，聚類過(guò)程中不需要任何人工的干預(yù)，很適合于自動(dòng)分割的應(yīng)用領(lǐng)域17。 利用fcm算法進(jìn)行圖像分割主要有以下難點(diǎn)和問(wèn)題：聚類類別數(shù)c的確定 在聚類進(jìn)行之前必需給定類的數(shù)目，否則聚類無(wú)法進(jìn)行。在實(shí)際應(yīng)用中，尤其是自動(dòng)化的系統(tǒng)中這是不太現(xiàn)實(shí)的。均值聚類方法中最困難的是圖像分割的類別數(shù)的確定。初始類中心初始隸屬度矩陣的確定 模糊聚類分割方法必須給出初始聚類中心和確定初始隸屬度矩陣。根據(jù)數(shù)學(xué)分析理論任何一個(gè)迭代并且最后收斂的序列，如果迭代的初始值比較接近于最后的收斂結(jié)果的話，收斂的速度會(huì)明顯提高，迭代次數(shù)也會(huì)較大幅度地減小。同時(shí)，也因?yàn)榻咏詈蠼Y(jié)果陷入其它局部最優(yōu)的可能性減小。另外，如果聚類迭代的初始值接近于某個(gè)局部極值的話，就很有可能最終陷入局部極值，從而得不到全局最優(yōu)值，所以fcm算法對(duì)初始值相當(dāng)敏感。在沒(méi)有任何先驗(yàn)知識(shí)也沒(méi)有任何輔助手段的情況下，系統(tǒng)可以采用隨機(jī)選取類中心的辦法。但那樣就過(guò)于盲目，而且很容易陷入局部最優(yōu)迭代，收斂速度可能很低，迭代的次數(shù)也可能會(huì)增加很多，這樣也就會(huì)增加計(jì)算時(shí)間。所以初始參數(shù)的確定，對(duì)于計(jì)算量的降低顯得尤其重要。然而目前尚無(wú)有效的理論指導(dǎo)，如何選擇合適的聚類初始值仍然是一個(gè)難題。迭代過(guò)程中的大計(jì)算量問(wèn)題 由于聚類是一個(gè)非線性優(yōu)化過(guò)程，聚類迭代算法在一般情況下收斂速度較慢。圖像分割是一個(gè)樣本量很大的分類問(wèn)題，尤其當(dāng)特征空間是多維空間時(shí)（如彩色圖像分割時(shí)的三維顏色空間聚類時(shí)）迭代算法中計(jì)算量過(guò)大而且只能串行，耗時(shí)很多，基于模糊聚類的計(jì)算量就更大了，使得fcm算法的實(shí)際應(yīng)用具有一定的局限性，更不用說(shuō)實(shí)時(shí)應(yīng)用了。為了解決模糊聚類中大計(jì)算量的問(wèn)題，降低計(jì)算時(shí)間，人們一般從三個(gè)方面來(lái)考慮：選擇接近最后結(jié)果的初始值，盡可能地減少迭代的次數(shù)；改進(jìn)算法，減少每一輪迭代的計(jì)算量；設(shè)計(jì)快速的實(shí)現(xiàn)算法。丁震等人提出了一種針對(duì)模糊聚類的快速二值化方法，該方法將圖像映射到灰度特征空間，然后在特征空間中進(jìn)行聚類，顯然特征空間中灰度級(jí)是很少的，而圖像的像素則是大樣本集，這樣一來(lái)計(jì)算量大幅度降低，分割質(zhì)量也還可以。但是該算法只適用于將圖像分割成目標(biāo)和背景兩類的灰度圖像應(yīng)用?？臻g信息的使用 模糊均值聚類方法分割的另一個(gè)問(wèn)題是它只考慮到了灰度特征或彩色圖像的色特征，忽略了圖像中固有的豐富的空間信息，從而導(dǎo)致它對(duì)噪聲比較敏感，而且使得分割出的區(qū)域往往不連續(xù)，導(dǎo)致本屬于同類的像素沒(méi)有連在一起，不能形成有意義的子圖。如何有效地利用空間信息，提高分割質(zhì)量，同時(shí)又不至于大幅增加計(jì)算量是一個(gè)很有意義的研究課題。聚類的后處理的問(wèn)題 由于模糊聚類法分割是一般都沒(méi)有有效地利用圖像像素之間的空間關(guān)系信息，容易導(dǎo)致分割出來(lái)的區(qū)域可能不連續(xù)；另一個(gè)分割時(shí)類別數(shù)未必是正確的，往往有過(guò)分割的可能。于是一般在聚類完成后對(duì)分割出的結(jié)果需要進(jìn)行一些合并類的后處理，使得最后分割出的區(qū)域都是有意義的。針對(duì)模糊聚類fcm存在的這個(gè)問(wèn)題，ray等人提出了一種基于解微分方程的曲線進(jìn)化的方法，該方法利用截集理論來(lái)演變分割圖中的幾何曲線，進(jìn)而描述圖像的區(qū)域。該方法不失為一種較好的后處理方法，它排除了分割圖中的不連續(xù)性，使得各區(qū)域之間的邊界是封閉和連續(xù)的。但該方法的邊界曲線演變過(guò)程的計(jì)算復(fù)雜度很高，非常耗時(shí)；它存在的另一個(gè)問(wèn)題是后處理過(guò)程可能會(huì)產(chǎn)生新的分割錯(cuò)誤。然而，好的后處理方法應(yīng)該分析聚類后存在的各種不同的問(wèn)題，然后采用不同的方法進(jìn)行處理，既要降低計(jì)算復(fù)雜度，又要避免引入新的噪聲。二十幾年來(lái)，研究工作者們對(duì)傳統(tǒng)fcm算法進(jìn)行不斷的研究，提出許多不同的改進(jìn)，但上述問(wèn)題仍然沒(méi)有完全解決。 1.3本文的主要工作 本文在介紹圖像分割的定義、方法、應(yīng)用及研究意義和研究現(xiàn)狀以及支持向量機(jī)的基礎(chǔ)理論之后做了如下任務(wù)：（1）詳細(xì)介紹當(dāng)前圖像分割以及聚類分析的研究背景，現(xiàn)狀。（2）介紹了基于聚類算法的圖像分割的算法步驟，以及本文所使用matlab軟件工具；（3）對(duì)基于模糊k均值的圖像分割算法進(jìn)行探討，并對(duì)k均值算法進(jìn)行改進(jìn)，通過(guò)粗糙集理論提供 k-均值聚類所需要的初始類的個(gè)數(shù)和均值，提高了聚類的效率和分類的精度。（4）對(duì)基于標(biāo)準(zhǔn)模糊 c 均值聚類的圖像分割算法進(jìn)行了探討，研究了基于模糊聚類的圖像分割方法中初始類別數(shù)的選取、初始類中心和初始隸屬度矩陣的確定等問(wèn)題（5）總結(jié)了本文的主要研究?jī)?nèi)容，并就本文尚存在的不足進(jìn)行了展望。第二章 聚類分析理論聚類分析是一種新興的多元統(tǒng)計(jì)方法，是當(dāng)代分類學(xué)與多元分析的結(jié)合。聚類分析是將分類對(duì)象置于一個(gè)多維空間中，依據(jù)樣本間關(guān)聯(lián)的度量標(biāo)準(zhǔn)將其自動(dòng)分成幾個(gè)群組，且使同一群組內(nèi)的樣本相似，而屬于不同群組的樣本相異的一組方法。聚類的樣本是用度量指針的一個(gè)向量表示，即用多維空間的一個(gè)點(diǎn)來(lái)表示。同類中的樣本比屬于不同類的樣本彼此具有更高的相似性。聚類分析通常是基于距離的，通過(guò)構(gòu)造一個(gè) m 維空間的距離函數(shù)，利用這個(gè)距離函數(shù)來(lái)進(jìn)行聚類。 2.1 聚類分析概述 迄今為止，聚類還沒(méi)有一個(gè)學(xué)術(shù)界公認(rèn)的定義，這里給出everittis在1974年關(guān)于聚類所下的定義：一個(gè)類簇內(nèi)的實(shí)體是相似的，不同類簇的實(shí)體是不相似的；一個(gè)類簇是測(cè)試空間中點(diǎn)的會(huì)聚，同一類簇的任意兩個(gè)點(diǎn)間的距離小于不同類簇的任意兩個(gè)點(diǎn)間的距離；類簇可以描述為一個(gè)包含密度相對(duì)較高的點(diǎn)集的多維空間中的連通區(qū)域，它們借助包含密度相對(duì)較低的點(diǎn)集的區(qū)域與其他區(qū)域（類簇）相分離。 定義 2.1簇(cluster)：一個(gè)數(shù)據(jù)對(duì)象的集合。在同一簇中，對(duì)象具有相似性，不同簇中，對(duì)象之間是相異的。 定義 2.2聚類分析(clustering analysis)：把一個(gè)給定的數(shù)據(jù)對(duì)象集合分成不同的簇,即在空間 x 中給定一個(gè)有限的取樣點(diǎn)集或從數(shù)據(jù)庫(kù)中取得有限個(gè)例子的集合，xini=1。聚類的目標(biāo)是將數(shù)據(jù)聚集成類，使得類間的相似性最小，而類內(nèi)的相似性盡可能得大。 沒(méi)有任何一種聚類技術(shù)（聚類算法）可以普遍適用于揭示各種多維數(shù)據(jù)集中所呈現(xiàn)出來(lái)的多種多樣的結(jié)構(gòu)，根據(jù)數(shù)據(jù)在聚類中積聚規(guī)則以及應(yīng)用這些規(guī)則的方法，有多種聚類算法。聚類算法有多種分類方法：1劃分方法給定一個(gè)包含n 個(gè)對(duì)象的數(shù)據(jù)集，劃分方法將數(shù)據(jù)集劃分為k 個(gè)子集。其中每個(gè)子集均代表一個(gè)聚類（k=n）。給定需要?jiǎng)澐值膫€(gè)數(shù)k，一個(gè)劃分方法創(chuàng)建一個(gè)初始劃分，然后利用循環(huán)再定位技術(shù)，即通過(guò)移動(dòng)不同劃分中的對(duì)象來(lái)改變劃分內(nèi)容。一個(gè)好的劃分衡量標(biāo)準(zhǔn)通常就是同一個(gè)組中的對(duì)象彼此相近或相關(guān)，而不同組中的對(duì)象較遠(yuǎn)或差距較大。主要的劃分方法有：k-means 聚類法和k-medoid 聚類法。k-means 聚類法在處理海量數(shù)據(jù)庫(kù)方面較有效，特別是對(duì)數(shù)值屬性處理，它對(duì)異常數(shù)據(jù)很敏感。pam（圍繞中心對(duì)象進(jìn)行劃分）方法是最初提出的k-medoid 聚類算法之一。k-medoid 聚類算法比k-means 聚類算法在處理異常數(shù)據(jù)和噪聲數(shù)據(jù)方面更為魯棒，但是前者的處理時(shí)間要比后者更大。2層次方法層次方法就是通過(guò)分解所給定的數(shù)據(jù)對(duì)象集來(lái)創(chuàng)建一個(gè)層次。根據(jù)層次分解形成的方式，可以將層次方法分為自下而上（也稱凝聚方式）和自上而下（也稱分割方式）兩種類型。自下而上的層次方法從每個(gè)對(duì)象均為一個(gè)單獨(dú)的組開(kāi)始,逐步將這些組進(jìn)行合并，直到組合并到了層次頂端或滿足終止條件為止。自上而下層次方法從所有對(duì)象均屬于一個(gè)組開(kāi)始，每一次循環(huán)將其分解為更小的組，直到每個(gè)對(duì)象構(gòu)成一組或滿足終止條件為止。birch 和cure 算法就是層次方法的實(shí)例。3基于密度方法基于密度的聚類方法就是不斷增長(zhǎng)所獲得的聚類直到鄰近密度小于一定閾值為止。這種方法可以用于消除數(shù)據(jù)中的噪聲（異常數(shù)據(jù)）。dbscan 就是一個(gè)典型的基于密度的方法，該方法根據(jù)密度閾值不斷增長(zhǎng)聚類。4基于網(wǎng)格方法基于網(wǎng)格方法將對(duì)象空間劃分為有限數(shù)目的單元以形成網(wǎng)格結(jié)構(gòu)。所有聚類操作均是在這一網(wǎng)格結(jié)構(gòu)上進(jìn)行的。這種方法主要優(yōu)點(diǎn)就是處理事件由于與數(shù)據(jù)對(duì)象個(gè)數(shù)無(wú)關(guān)而僅與劃分對(duì)象空間的網(wǎng)格數(shù)相關(guān)，從而顯得相對(duì)較快。sting 就是一個(gè)典型的基于網(wǎng)格的方法。5基于模型方法基于模型的方法就是為每個(gè)聚類假設(shè)一個(gè)模型，再去發(fā)現(xiàn)符合相應(yīng)模型的數(shù)據(jù)對(duì)象。一個(gè)基于模型的算法可以通過(guò)構(gòu)造一個(gè)描述數(shù)據(jù)點(diǎn)空間分布的密度函數(shù)來(lái)確定具體聚類。它根據(jù)標(biāo)準(zhǔn)統(tǒng)計(jì)方法并考慮到“噪聲”或異常數(shù)據(jù)，可以自動(dòng)確定聚類個(gè)數(shù)，因此它可以產(chǎn)生很魯棒的聚類方法。如神經(jīng)網(wǎng)絡(luò)方法。 2.1.1聚類分析中的數(shù)據(jù)類型數(shù)據(jù)挖掘的一個(gè)重要步驟是數(shù)據(jù)準(zhǔn)備，這包括對(duì)選定的數(shù)據(jù)進(jìn)行規(guī)范化、整合和預(yù)處理等等，這是進(jìn)行數(shù)據(jù)挖掘的前提，也同樣是聚類算法能正常實(shí)施的必要前提。要對(duì)數(shù)據(jù)對(duì)象進(jìn)行聚類，基于統(tǒng)計(jì)方法，其最重要的前提是要計(jì)算各個(gè)數(shù)據(jù)對(duì)象之間的距離即相異度，針對(duì)不同的數(shù)據(jù)類型有不同的相異度計(jì)算方法。許多基于內(nèi)存的聚類算法常使用以下兩種有代表性的數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)矩陣和相異度矩陣。 數(shù)據(jù)矩陣與相異度矩陣 設(shè)聚類問(wèn)題中有n個(gè)對(duì)象:(i=1,2,.,n)，對(duì)每個(gè)對(duì)象選擇了p個(gè)變量，用間隔尺度測(cè)定后，第i個(gè)對(duì)象的第j個(gè)變量的觀測(cè)值用表示，則這n個(gè)對(duì)象所有p個(gè)變量的觀測(cè)值可以看成是如下的 np 矩陣: （2.1）矩 陣 (2.1)常被稱為數(shù)據(jù)矩陣，它是對(duì)象變量結(jié)構(gòu)的數(shù)據(jù)表達(dá)方式，其中 第i個(gè)對(duì)象的p個(gè)變量的觀測(cè)值可以記為向量:=t (2.2)聚類中常用的另外一種數(shù)據(jù)結(jié)構(gòu)是相異度矩陣，它存儲(chǔ)的是n個(gè)對(duì)象兩兩之間的近似性，表現(xiàn)形式為一個(gè) nn 矩陣: (2.3)其中 d(i,j) , 是對(duì)象 i 與對(duì)象 1 之間相異性的量化表示，通常它是一個(gè)非負(fù)的數(shù)值，當(dāng)對(duì)象 i 和對(duì)象 j 越相似和越“接近”， d(i,j) , 的值就越接近。反之，如果兩個(gè)對(duì)象越不同或相距“越遠(yuǎn)”， d(i,j) , 的值就越大。顯然d(i,j) ,d(i,j) ，且d(i,j) , =0，因此可以得到形如(2.3)的矩陣。相異度矩陣是對(duì)象對(duì)象結(jié)構(gòu)的一種數(shù)據(jù)表達(dá)方式。2.1.2聚類分析的典型要求 聚類是一個(gè)富有挑戰(zhàn)性的研究領(lǐng)域，它的潛在應(yīng)用提出了各自特殊的要求。數(shù)據(jù)挖掘?qū)垲惖牡湫鸵笕缦隆?) 可伸縮性許多聚類算法在小于200 個(gè)數(shù)據(jù)對(duì)象的小數(shù)據(jù)集合上工作得很好；但是，一個(gè)大規(guī)模數(shù)據(jù)庫(kù)可能包含幾百萬(wàn)個(gè)對(duì)象，在這樣的大數(shù)據(jù)集合樣本上進(jìn)行聚類又可能會(huì)導(dǎo)致偏差的結(jié)果。我們需要具有高度可伸縮性的算法。2）處理不同類型屬性的能力許多算法被設(shè)計(jì)用來(lái)聚類數(shù)值類型的數(shù)據(jù)。但是，應(yīng)用可能要求聚類其他類型的數(shù)據(jù)，如二元類型（binary），分類/標(biāo)稱類型（categorical/nominal），序數(shù)型（ordinal）數(shù)據(jù)，或者這些數(shù)據(jù)類型的混合。3）發(fā)現(xiàn)任意形狀的聚類許多聚類算法基于歐幾里的距離或者曼哈坦距離度量來(lái)決定聚類?；谶@樣的距離度量的算法趨向于發(fā)現(xiàn)具有相近尺度合密度的球狀簇。但是，一個(gè)簇可能是任意形狀的。提出能發(fā)現(xiàn)任意形狀簇的算法是很重要的。4）處理噪聲數(shù)據(jù)的能力絕大多數(shù)現(xiàn)實(shí)世界中的數(shù)據(jù)庫(kù)都包含了孤立點(diǎn)，空缺，未知數(shù)據(jù)或者錯(cuò)誤的數(shù)據(jù)。一些聚類算法對(duì)于這樣的數(shù)據(jù)敏感，可能導(dǎo)致低質(zhì)量的聚類結(jié)果。5）對(duì)于輸入記錄的順序不敏感一些聚類算法對(duì)于輸入數(shù)據(jù)的順序是敏感的。例如，同一個(gè)數(shù)據(jù)集合，當(dāng)以不同的順序提交同一個(gè)算法時(shí)，可能生成差別很大的聚類結(jié)果。開(kāi)發(fā)對(duì)數(shù)據(jù)輸入順序布敏感的算法具有重要的意義。6）高維性（high dimensionality）一個(gè)數(shù)據(jù)庫(kù)或者數(shù)據(jù)倉(cāng)庫(kù)可能包含若干維或者屬性。許多聚類三算法擅長(zhǎng)處理低維數(shù)據(jù)，可能只涉及兩到三維。人類最多在三維的情況下能夠很好地判斷聚類的質(zhì)量。在高維空間中聚類數(shù)據(jù)對(duì)象時(shí)非常有挑戰(zhàn)性的，特別是考慮到這樣的數(shù)據(jù)可能非常稀疏，而且高度偏斜。 2.1.3聚類分析的一般步驟 在實(shí)際應(yīng)用聚類分析中，根據(jù)有無(wú)領(lǐng)域知識(shí)參與可將整個(gè)過(guò)程分解為三個(gè)環(huán)節(jié)，每個(gè)環(huán)節(jié)都有其明確的任務(wù)，這樣對(duì)于整個(gè)聚類分析的過(guò)程就會(huì)有更清晰的認(rèn)識(shí)，如圖 1.1 所示。 圖1.1聚類的一般步驟第一步是特征抽取。 它的輸入是原始樣本，由領(lǐng)域?qū)＜覜Q定使用哪些特征來(lái)深刻地刻畫(huà)樣本的本質(zhì)性質(zhì)和結(jié)構(gòu)。它的結(jié)果輸出是一個(gè)矩陣，矩陣的每一行是一個(gè)樣本，每一列是一個(gè)特征指標(biāo)變量。選取特征的優(yōu)劣將直接影響以后的分析和決策。如果第一步就選擇了和聚類意圖根本無(wú)關(guān)的特征變量，那企圖得到良好的聚類結(jié)果則無(wú)異于緣木求魚(yú)。合理的特征選取方案應(yīng)當(dāng)使得同類樣本在特征空間中相距較近，異類樣本則相距較遠(yuǎn)。在有些應(yīng)用場(chǎng)合還需要將得到的樣本矩陣進(jìn)行一些后處理工作。比如為了統(tǒng)一量綱就對(duì)變量進(jìn)行標(biāo)準(zhǔn)化處理，這樣采用不同量綱的變量才具有可比性；有些場(chǎng)合可能選擇的特征變量太多，不利于以后的分析和決策，這時(shí)可以先進(jìn)行降維處理；僅憑經(jīng)驗(yàn)和領(lǐng)域知識(shí)選擇的特征變量有可能是相關(guān)的，進(jìn)行主成分分析就可以消除變量間的相關(guān)性，從而得到一些相互獨(dú)立的特征變量。第二步是執(zhí)行聚類算法，獲得聚類譜系圖。 它的輸入是一個(gè)樣本矩陣，它把一個(gè)樣本想象成特征變量空間中的一個(gè)點(diǎn)。聚類算法的目的就是獲得能夠反映 x 維空間中這些樣本點(diǎn)之間的最本質(zhì)的“簇成一團(tuán)”性質(zhì)。這一步?jīng)]有領(lǐng)域?qū)＜业膮⑴c，它除了幾何知識(shí)外不考慮任何的領(lǐng)域知識(shí)，不考慮特征變量在其領(lǐng)域中的特定含義，僅僅認(rèn)為它是特征空間中一維而己。聚類算法的輸出一般是一個(gè)聚類譜系圖，由粗到細(xì)地反映了所有的分類情況；或者直接給出具體的分類方案，包括總共分成幾類，每類具體包含那些樣本點(diǎn)等等。第三步是選取合適的分類閾值。 在得到了聚類譜系圖之后，領(lǐng)域?qū)＜覒{借經(jīng)驗(yàn)和領(lǐng)域知識(shí)，根據(jù)具體的應(yīng)用場(chǎng)合，決定閾值的選取。選定閾值之后，就能夠從聚類譜系圖上直接看出分類方案。領(lǐng)域?qū)＜疫€可以對(duì)聚類結(jié)果結(jié)合領(lǐng)域知識(shí)進(jìn)行進(jìn)一步的分析，從而加深樣本點(diǎn)和特征變量的認(rèn)識(shí)。 總之，實(shí)際應(yīng)用聚類分析是一個(gè)需要多方參與的過(guò)程，它無(wú)法脫離開(kāi)領(lǐng)域?qū)＜业膮⑴c，聚類算法僅僅是整個(gè)聚類流程中的一環(huán)而己，光依靠聚類算法一般不會(huì)得到令人滿意的效果。2.2 常見(jiàn)的聚類算法2.2.1 k-means 算法k-means 聚類算法是給定類的個(gè)數(shù) k，利用距離最近的原則，將 n 個(gè)對(duì)象分到 k 個(gè)類中去，聚類的結(jié)果由 k 個(gè)聚類中心來(lái)表達(dá)，基于給定的聚類目標(biāo)函數(shù)（或稱聚類效果判別函數(shù)），算法采用迭代更新的方法，每一次迭代過(guò)程都是向目標(biāo)函數(shù)值減少的方向進(jìn)行；在每一輪中，依據(jù) k 個(gè)參照點(diǎn)將其周圍的點(diǎn)分別組成 k 個(gè)簇，而每個(gè)簇的幾何中心將被作為下一輪迭代的參照點(diǎn)，迭代使得選取的參照點(diǎn)越來(lái)越接近真實(shí)的簇幾何中心，使得類內(nèi)對(duì)象之間的相似性最大，類之間的相似性最小。聚類效果的好壞用目標(biāo)函數(shù) j表示:， (2.4) 其中是與之間的距離函數(shù)，如歐氏距離。目標(biāo)函數(shù)j 其實(shí)就是每個(gè)數(shù)據(jù)點(diǎn)與所在簇的質(zhì)心的距離之和，所以，j值越小，簇就越緊湊，相對(duì)越獨(dú)立。因此，算法通過(guò)不斷優(yōu)化j的取值來(lái)尋求好的聚類方案，當(dāng)j取極小值時(shí)，對(duì)應(yīng)的聚類方案即是最優(yōu)方案。根據(jù)聚類結(jié)果的表達(dá)方式可以將聚類算法劃分為：硬k-means（hcm）算法、模糊k-means（fcm）算法和概率k-means 算法（pcm）。k-means 算法描述如下：步驟 1) 隨機(jī)選取k個(gè)對(duì)象作為初始的簇的質(zhì)心; 步驟 2) 計(jì)算對(duì)象與各個(gè)族的質(zhì)心的距離，將對(duì)象劃分到距離其最近的簇 ; 步驟 3) 重新計(jì)算每個(gè)新簇的均值，即質(zhì)心;步驟 4) 若簇的質(zhì)心不再變化，則返回劃分結(jié)果，否則轉(zhuǎn)步驟2）.k-means 算法嘗試找出使平方誤差函數(shù)值最小的k個(gè)劃分。當(dāng)結(jié)果簇是密集的，而簇與簇之間區(qū)別明顯時(shí)，它的效果較好。面對(duì)大規(guī)模數(shù)據(jù)集，該算法是相對(duì)可擴(kuò)展的，并且具有較高的效率。算法的復(fù)雜度為o(nkt),其中，n為數(shù)據(jù)集中對(duì)象的數(shù)目，k為期望得到的簇的數(shù)目，t為迭代的次數(shù)。通常情況下，算法可以終止于局部最優(yōu)解。 但是，kmeans算法只有在簇的平均值被定義的情況下才能使用。這可能不適用于某些應(yīng)用，例如涉及有分類屬性的數(shù)據(jù)。其次，這種算法要求事先給出要生成的簇的數(shù)目k，顯然，這在某些應(yīng)用中是不實(shí)際的。另外，k-means算法不適用于發(fā)現(xiàn)非凸面形狀的簇，或者大小差別很大的簇。還有，它對(duì)于噪音和孤立點(diǎn)數(shù)據(jù)是敏感的。 kmeans算法有很多變種，例如，k-模算法用模代替簇的平均值，用新的相異性度量方法來(lái)處理分類對(duì)象，用基于頻率的方法來(lái)修改聚類的模。而k平均算法和k模算法相結(jié)合，用來(lái)處理有數(shù)值類型和分類類型屬性的數(shù)據(jù)，就產(chǎn)生了k-原型算法。2 .2. 2 d bscan 算法dbscan 算法可以將足夠高密度的區(qū)域劃分為簇, 并可以在帶有 “噪聲” 的空間數(shù)據(jù)庫(kù)中發(fā)現(xiàn)任意形狀的聚類 。 dbscan 通過(guò)檢查數(shù)據(jù)庫(kù)中每個(gè)點(diǎn)的e 2鄰域來(lái)尋找聚類 。 如果一個(gè)點(diǎn) p 的 e 2 鄰域包含多于m inp ts 個(gè)點(diǎn), 則創(chuàng)建一個(gè)以 p 作為核心對(duì)象的新簇 。然后反復(fù)地尋找從這些核心對(duì)象直接密度可達(dá)的對(duì)象, 當(dāng)沒(méi)有新的點(diǎn)可以被添加到任何簇時(shí), 該過(guò)程結(jié)束 。 如果采用空間索引, dbscan 的計(jì)算復(fù)雜度是o(n log n ) 。 2.2.3 sting算法sting（statistical information grid)算法是一種基于網(wǎng)格的多分辨率聚類方法，它將空間區(qū)域劃分為若干矩形網(wǎng)格單元。針對(duì)不同級(jí)別的分辨率，通常存在多個(gè)級(jí)別的矩形單元，這些單元形成了一個(gè)層次結(jié)構(gòu)，高層的每個(gè)單元被劃分為多個(gè)低一層的單元。關(guān)于每個(gè)網(wǎng)格單元屬性的統(tǒng)計(jì)信息，如平均值、最大值、最小值等，被預(yù)先計(jì)算和存儲(chǔ)。 高層單元的統(tǒng)計(jì)參數(shù)可以很容易地從低層單元的計(jì)算得到。這些統(tǒng)計(jì)參數(shù)包括:屬性無(wú)關(guān)的參數(shù)count；屬性相關(guān)的參數(shù)m(平均值)，s(標(biāo)準(zhǔn)方差)，min(最小值)，max(最大值)，以及該單元中屬性值遵循的分布(distribution)類型，例如正態(tài)分布、平均分布、指數(shù)分布或無(wú)(如果分布未知)。當(dāng)數(shù)據(jù)被裝載進(jìn)數(shù)據(jù)庫(kù)時(shí)，底層單元的參數(shù)count、m、s, min和max直接進(jìn)行計(jì)算。如果分布的類型事先知道，distribution的值可以由用戶指定，也可以通過(guò)假設(shè)檢驗(yàn)來(lái)獲得。 統(tǒng)計(jì)參數(shù)的使用可以按照以下自頂向下的基于網(wǎng)格的方法:首先，在層次結(jié)構(gòu)中選定一層作為查詢處理的開(kāi)始點(diǎn)。通常該層包含少量的單元。對(duì)當(dāng)前層次的每個(gè)單元，我們計(jì)算置信度區(qū)間或者估算其概率范圍，用以反映該單元與給定查詢的關(guān)聯(lián)程度，不相關(guān)的單元就不再考慮。低一層的處理就只檢查剩余的相關(guān)單元。這個(gè)過(guò)程反復(fù)進(jìn)行，直到達(dá)到底層。此時(shí)，如果滿足查詢條件，那么返回相關(guān)單元的區(qū)域。否則，檢索和進(jìn)一步處理相關(guān)單元中的數(shù)據(jù)，直到它們滿足查詢條件。 與其他聚類方法相比，sting算法的優(yōu)點(diǎn)在于: (1) 由于存儲(chǔ)在每個(gè)單元中的統(tǒng)計(jì)信息提供了單元中的數(shù)據(jù)不依賴于查詢的匯總信息，所有基于網(wǎng)格的計(jì)算是獨(dú)立于查詢的； (2) 網(wǎng)格結(jié)構(gòu)有利于并行處理和增量更新； (3) 算法效率很高。sting算法通過(guò)掃描一次數(shù)據(jù)庫(kù)來(lái)計(jì)算單元的統(tǒng)計(jì)信息，產(chǎn)生聚類的時(shí)間復(fù)雜度是on)，其中n為對(duì)象的數(shù)目。在層次結(jié)構(gòu)建好后，查詢處理的時(shí)間復(fù)雜度是o(g)，其中g(shù)是最低網(wǎng)格單元的數(shù)目，通常遠(yuǎn)遠(yuǎn)小于n 。 sting 算法的性能取決于最底層單元的粒度，該粒度也決定著聚類結(jié)果的質(zhì)量。sting算法在粒度較大時(shí)，速度非?？欤@時(shí)聚類的質(zhì)量不夠好。當(dāng)粒度較小時(shí)，聚類結(jié)果的質(zhì)量好，但處理的代價(jià)會(huì)增加。2.3 模糊聚類算法2.3.1 模糊聚類算法概述模糊聚類算法是一種基于函數(shù)最優(yōu)方法的聚類算法，使用微積分計(jì)算技術(shù)求最優(yōu)代價(jià)函數(shù)。在基于概率算法的聚類方法中將使用概率密度函數(shù)，為此要假定合適的模型，模糊聚類算法的向量可以同時(shí)屬于多個(gè)聚類，從而擺脫上述問(wèn)題。在模糊聚類算法中，定義了向量與聚類之間的近鄰函數(shù)，并且聚類中向量的隸屬度由隸屬函數(shù)集合提供。對(duì)模糊方法而言，在不同聚類中的向量隸屬函數(shù)值是相互關(guān)聯(lián)的。硬聚類可以看成是模糊聚類方法的一個(gè)特例。2.3.2 模糊聚類算法的分類模糊聚類分析算法大致可分為三類4： 1）分類數(shù)不定，根據(jù)不同要求對(duì)事物進(jìn)行動(dòng)態(tài)聚類，此類方法是基于模糊等價(jià)矩陣聚類的，稱為模糊等價(jià)矩陣動(dòng)態(tài)聚類分析法。 2）分類數(shù)給定，尋找出對(duì)事物的最佳分析方案，此類方法是基于目標(biāo)函數(shù)聚類的，稱為模c均值聚類。3）在攝動(dòng)有意義的情況下，根據(jù)模糊相似矩陣聚類，此類方法稱為基于攝動(dòng)的模糊聚類分析法。2.3.3 fcm算法fcm算法是一種基于劃分的聚類算法，它的思想就是使得被劃分到同一簇的對(duì)象之間相似度最大，而不同簇之間的相似度最小。 模糊c均值算法是普通c均值算法的改進(jìn)，普通c均值算法對(duì)于數(shù)據(jù)的劃分是硬性的，而fcm則是一種柔性的模糊劃分。在介紹fcm具體算法之前我們先介紹一些模糊集合的基本知識(shí)。隸屬度函數(shù)是表示一個(gè)對(duì)象x隸屬于集合a的程度的函數(shù)，通常記做a(x)，其自變量范圍是所有可能屬于集合a的對(duì)象（即集合a所在空間中的所有點(diǎn)），取值范圍是0,1，即0=1，a(x)1是一個(gè)加權(quán)指數(shù) 構(gòu)造如下新的目標(biāo)函數(shù)，可求得使（1.2）式達(dá)到最小值的必要條件：(2.6)這里lj，j=1到n，是（6.9）式的n個(gè)約束式的拉格朗日乘子。對(duì)所有輸入?yún)⒘壳髮?dǎo)，使式（6.10）達(dá)到最小的必要條件為：(2.7) 和(2.8)2.4圖像分割方法2.4.1. 基于閾值的分割方法包括全局閾值、自適應(yīng)閾值、最佳閾值等等。閾值分割算法的關(guān)鍵是確定閾值，如果能確定一個(gè)合適的閾值就可準(zhǔn)確地將圖像分割開(kāi)來(lái)。閾值確定后，將閾值與像素點(diǎn)的灰度值比較和像素分割可對(duì)各像素并行地進(jìn)行，分割的結(jié)果直接給出圖像區(qū)域。全局閾值是指整幅圖像使用同一個(gè)閾值做分割處理，適用于背景和前景有明顯對(duì)比的圖像。它是根據(jù)整幅圖像確定的：t=t(f)。但是這種方法只考慮像素本身的灰度值，一般不考慮空間特征，因而對(duì)噪聲很敏感。常用的全局閾值選取方法有利用圖像灰度直方圖的峰谷法、最小誤差法、最大類間方差法、最大熵自動(dòng)閾值法以及其它一些方法。 在許多情況下，物體和背景的對(duì)比度在圖像中的各處不是一樣的，這時(shí)很難用一個(gè)統(tǒng)一的閾值將物體與背景分開(kāi)。這時(shí)可以根據(jù)圖像的局部特征分別采用不同的闞值進(jìn)行分割。實(shí)際處理時(shí)，需要按照具體問(wèn)題將圖像分成若干子區(qū)域分別選擇閾值，或者動(dòng)態(tài)地根據(jù)一定的鄰域范圍選擇每點(diǎn)處的閾值，進(jìn)行圖像分割。這時(shí)的閾值為自適應(yīng)閾值。 閾值的選擇需要根據(jù)具體問(wèn)題來(lái)確定，一般通過(guò)實(shí)驗(yàn)來(lái)確定。對(duì)于給定的圖像，可以通過(guò)分析直方圖的方法確定最佳的閾值，例如當(dāng)直方圖明顯呈現(xiàn)雙峰情況時(shí)，可以選擇兩個(gè)峰值的中點(diǎn)作為最佳閾值。2.4.2基于邊緣的分割方法檢測(cè)灰度級(jí)或者結(jié)構(gòu)具有突變的地方，表明一個(gè)區(qū)域的終結(jié)，也是另一個(gè)區(qū)域開(kāi)始的地方。這種不連續(xù)性稱為邊緣。不同的圖像灰度不同，邊界處一般有明顯的邊緣，利用此特征可以分割圖像。圖像中邊緣處像素的灰度值不連續(xù)，這種不連續(xù)性可通過(guò)求導(dǎo)數(shù)來(lái)檢測(cè)到。對(duì)于階躍狀邊緣，其位置對(duì)應(yīng)一階導(dǎo)數(shù)的極值點(diǎn)，對(duì)應(yīng)二階導(dǎo)數(shù)的過(guò)零點(diǎn)(零交叉點(diǎn))。因此常用微分算子進(jìn)行邊緣檢測(cè)。常用的一階微分算子有roberts算子、prewitt算子和sobel算子，二階微分算子有l(wèi)aplace算子和kirsh算子等。在實(shí)際中各種微分算子常用小區(qū)域模板來(lái)表示，微分運(yùn)算是利用模板和圖像卷積來(lái)實(shí)現(xiàn)。這些算子對(duì)噪聲敏感，只適合于噪聲較小不太復(fù)雜的圖像。 由于邊緣和噪聲都是灰度不連續(xù)點(diǎn)，在頻域均為高頻分量，直接采用微分運(yùn)算難以克服噪聲的影響。因此用微分算子檢測(cè)邊緣前要對(duì)圖像進(jìn)行平滑濾波。log算子和canny算子是具有平滑功能的二階和一階微分算子，邊緣檢測(cè)效果較好，如圖4所示。其中l(wèi)og算子是采用laplacian算子求高斯函數(shù)的二階導(dǎo)數(shù)，canny算子是高斯函數(shù)的一階導(dǎo)數(shù)，它在噪聲抑制和邊緣檢測(cè)之間取得了較好的平衡。2.4.3基于聚類分析的圖像分割方法 特征空間聚類法進(jìn)行圖像分割是將圖像空間中的像素用對(duì)應(yīng)的特征空間點(diǎn)表示，根據(jù)它們?cè)谔卣骺臻g的聚集對(duì)特征空間進(jìn)行分割，然后將它們映射回原圖像空間，得到分割結(jié)果。其中，k均值、模糊c均值聚類(fcm)算法是最常用的聚類算法。k均值算法先選k個(gè)初始類均值，然后將每個(gè)像素歸入均值離它最近的類并計(jì)算新的類均值。迭代執(zhí)行前面的步驟直到新舊類均值之差小于某一閾值。模糊c均值算法是在模糊數(shù)學(xué)基礎(chǔ)上對(duì)k均值算法的推廣，是通過(guò)最優(yōu)化一個(gè)模糊目標(biāo)函數(shù)實(shí)現(xiàn)聚類，它不像k均值聚類那樣認(rèn)為每個(gè)點(diǎn)只能屬于某一類，而是賦予每個(gè)點(diǎn)一個(gè)對(duì)各類的隸屬度，用隸屬度更好地描述邊緣像素亦此亦彼的特點(diǎn)，適合處理事物內(nèi)在的不確定性。利用模糊c均值(fcm)非監(jiān)督模糊聚類標(biāo)定的特點(diǎn)進(jìn)行圖像分割，可以減少人為的干預(yù)，且較適合圖像中存在不確定性和模糊性的特點(diǎn)。2.5本章總結(jié) 本章主要介紹了聚類分析的概述以及定義，聚類分析的一般步驟，常見(jiàn)的聚類算法k-means 算法，d bscan 算法，sting算法，fcm算法，和常見(jiàn)的圖像分割方法，本章是該研究所需要的預(yù)備基礎(chǔ)知識(shí)。第三章 基于k-means算法的圖像分割方法對(duì)于彩色圖像的研究都是在特定的顏色空間進(jìn)行的，常用的顏色空間有、等。顏色空間的選擇應(yīng)盡可能與人類的視覺(jué)系統(tǒng)和心理感知一致。本章就是在空間研究k-means算法應(yīng)用于圖像分割的效果。 3.1顏色空間彩色空間非常簡(jiǎn)單，如圖4.1所示，彩色空間是一個(gè)立方體三維坐標(biāo)空間結(jié)構(gòu)，分別用紅、綠、藍(lán)表示三個(gè)坐標(biāo)軸。任何顏色都落入彩色立方體內(nèi)。圖3.1彩色空間但是，存在如下一些不足：（1）空間用紅、綠、藍(lán)三基色的混合比例定義不同的色彩，從而不同的顏色難以用準(zhǔn)確的數(shù)值來(lái)表示，定量分析比較困難。（2）系統(tǒng)中，彩色通道之間的相關(guān)性很好，從而合成圖像的飽和度偏低，色調(diào)變化較小，圖像視覺(jué)效果較差。（3）人眼只能夠通過(guò)感知顏色的亮度、色調(diào)以及飽和度來(lái)區(qū)分