【文章內(nèi)容簡(jiǎn)介】 地反映了所有的分類情況；或者直接給出具體的分類方案，包括總共分成幾類，每類具體包含那些樣本點(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ì)得到令人滿意的效果。 常見(jiàn)的聚類算法 Kmeans 算法Kmeans 聚類算法是給定類的個(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表示:， () 其中是與之間的距離函數(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á)方式可以將聚類算法劃分為：硬Kmeans（HCM）算法、模糊Kmeans（FCM）算法和概率Kmeans 算法（PCM）。Kmeans 算法描述如下：步驟 1) 隨機(jī)選取k個(gè)對(duì)象作為初始的簇的質(zhì)心。 步驟 2) 計(jì)算對(duì)象與各個(gè)族的質(zhì)心的距離，將對(duì)象劃分到距離其最近的簇 。 步驟 3) 重新計(jì)算每個(gè)新簇的均值，即質(zhì)心。步驟 4) 若簇的質(zhì)心不再變化，則返回劃分結(jié)果，否則轉(zhuǎn)步驟2）.kmeans 算法嘗試找出使平方誤差函數(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)解。 但是，k－means算法只有在簇的平均值被定義的情況下才能使用。這可能不適用于某些應(yīng)用，例如涉及有分類屬性的數(shù)據(jù)。其次，這種算法要求事先給出要生成的簇的數(shù)目k，顯然，這在某些應(yīng)用中是不實(shí)際的。另外，kmeans算法不適用于發(fā)現(xiàn)非凸面形狀的簇，或者大小差別很大的簇。還有，它對(duì)于噪音和孤立點(diǎn)數(shù)據(jù)是敏感的。 k－means算法有很多變種，例如，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 ) 。 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ì)增加。 模糊聚類算法 　模糊聚類算法概述模糊聚類算法是一種基于函數(shù)最優(yōu)方法的聚類算法，使用微積分計(jì)算技術(shù)求最優(yōu)代價(jià)函數(shù)。在基于概率算法的聚類方法中將使用概率密度函數(shù)，為此要假定合適的模型，模糊聚類算法的向量可以同時(shí)屬于多個(gè)聚類，從而擺脫上述問(wèn)題。在模糊聚類算法中，定義了向量與聚類之間的近鄰函數(shù)，并且聚類中向量的隸屬度由隸屬函數(shù)集合提供。對(duì)模糊方法而言，在不同聚類中的向量隸屬函數(shù)值是相互關(guān)聯(lián)的。硬聚類可以看成是模糊聚類方法的一個(gè)特例。 模糊聚類算法的分類模糊聚類分析算法大致可分為三類[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)的模糊聚類分析法。 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。μA(x)=1表示x完全隸屬于集合A，相當(dāng)于傳統(tǒng)集合概念上的x∈A。一個(gè)定義在空間X={x}上的隸屬度函數(shù)就定義了一個(gè)模糊集合A，或者叫定義在論域X={x}上的模糊子集 。對(duì)于有限個(gè)對(duì)象x1，x2，……，xn模糊集合 可以表示為：FCM的目標(biāo)函數(shù)一般化形式： ()這里uij介于0，1間；ci為模糊組I的聚類中心，dij=||cixj||為第I個(gè)聚類中心與第j個(gè)數(shù)據(jù)點(diǎn)間的歐幾里德距離；且m1是一個(gè)加權(quán)指數(shù) 構(gòu)造如下新的目標(biāo)函數(shù)，可求得使（）式達(dá)到最小值的必要條件： ()這里lj，j=1到n，是（）式的n個(gè)約束式的拉格朗日乘子。對(duì)所有輸入?yún)⒘壳髮?dǎo)，使式（）達(dá)到最小的必要條件為： () 和 (). 基于閾值的分割方法包括全局閾值、自適應(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)作為最佳閾值。．基于邊緣的分割方法檢測(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算子，二階微分算子有Laplace算子和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è)之間取得了較好的平衡。．基于聚類分析的圖像分割方法　　 特征空間聚類法進(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)。 本章主要介紹了聚類分析的概述以及定義，聚類分析的一般步驟，常見(jiàn)的聚類算法Kmeans 算法，D BSCAN 算法，STING算法，F(xiàn)CM算法，和常見(jiàn)的圖像分割方法，本章是該研究所需要的預(yù)備基礎(chǔ)知識(shí)。第三章 基于Kmeans算法的圖像分割方法對(duì)于彩色圖像的研究都是在特定的顏色空間進(jìn)行的，常用的顏色空間有、等。顏色空間的選擇應(yīng)盡可能與人類的視覺(jué)系統(tǒng)和心理感知一致。本章就是在空間研究Kmeans算法應(yīng)用于圖像分割的效果。 彩色空間非常簡(jiǎn)單，彩色空間是一個(gè)立方體三維坐標(biāo)空間結(jié)構(gòu)，分別用紅、綠、藍(lán)表示三個(gè)坐標(biāo)軸。任何顏色都落入彩色立方體內(nèi)。但是，存在如下一些不足：（1）空間用紅、綠、藍(lán)三基色的混合比例定義不同的色彩，從而不同的顏色難以用準(zhǔn)確的數(shù)值來(lái)表示，定量分析比較困難。（2）系統(tǒng)中，彩色通道之間的相關(guān)性很好，從而合成圖像的飽和度偏低，色調(diào)變化較小，圖像視覺(jué)效果較差。（3）人眼只能夠通過(guò)感知顏色的亮度、色調(diào)以及飽和度來(lái)區(qū)分物體，不能夠直接感覺(jué)紅、綠、藍(lán)三色的比例，此外，色調(diào)和飽和度與紅、綠、藍(lán)的關(guān)系是非線性的，因此，空間中對(duì)圖像進(jìn)行分析與處理難以控制其結(jié)果。kmeans算法是一種得到最廣泛使用的基于劃分的聚類算法，把n個(gè)對(duì)象分為k個(gè)簇，以使簇內(nèi)具有較高的相似度。相似度的計(jì)算根據(jù)一個(gè)簇中對(duì)象的平均值來(lái)進(jìn)行。它與處理混合正態(tài)分布的最大期望算法很相似，因?yàn)樗麄兌荚噲D找到數(shù)據(jù)中自然聚類的中心。算法首先隨機(jī)地選擇k個(gè)對(duì)象，每個(gè)對(duì)象初始地代表了一個(gè)簇的平均值或中心。對(duì)剩余的每個(gè)對(duì)象根據(jù)其與各個(gè)簇中心的距離，將它賦給最近的簇，然后重新計(jì)算每個(gè)簇的平均值。這個(gè)過(guò)程不斷重復(fù)，直到準(zhǔn)則函數(shù)收斂。 ()它假設(shè)對(duì)象屬性來(lái)自于空間向量，并且目標(biāo)是使各個(gè)群組內(nèi)部的均方誤差總和最小。假設(shè)有k個(gè)群組Si, i=1,2,...,k。μi是群組Si內(nèi)所有元素xj的重心，或叫中心點(diǎn)。kmeans 算法基本步驟：（1） 從 n個(gè)數(shù)據(jù)對(duì)象任意選擇 k 個(gè)對(duì)象作為初始聚類中心；（2） 根據(jù)每個(gè)聚類對(duì)象的均值（中心對(duì)象），計(jì)算每個(gè)對(duì)象與這些中心對(duì)象的距離；并根據(jù)最小距離重新對(duì)相應(yīng)對(duì)象進(jìn)行劃分；（3） 重新計(jì)算每