【文章內(nèi)容簡介】 地反映了所有的分類情況；或者直接給出具體的分類方案，包括總共分成幾類，每類具體包含那些樣本點等等。第三步是選取合適的分類閾值。 在得到了聚類譜系圖之后，領(lǐng)域?qū)＜覒{借經(jīng)驗和領(lǐng)域知識，根據(jù)具體的應用場合，決定閾值的選取。選定閾值之后，就能夠從聚類譜系圖上直接看出分類方案。領(lǐng)域?qū)＜疫€可以對聚類結(jié)果結(jié)合領(lǐng)域知識進行進一步的分析，從而加深樣本點和特征變量的認識。 總之，實際應用聚類分析是一個需要多方參與的過程，它無法脫離開領(lǐng)域?qū)＜业膮⑴c，聚類算法僅僅是整個聚類流程中的一環(huán)而己，光依靠聚類算法一般不會得到令人滿意的效果。 常見的聚類算法 Kmeans 算法Kmeans 聚類算法是給定類的個數(shù) K，利用距離最近的原則，將 N 個對象分到 K 個類中去，聚類的結(jié)果由 K 個聚類中心來表達，基于給定的聚類目標函數(shù)（或稱聚類效果判別函數(shù)），算法采用迭代更新的方法，每一次迭代過程都是向目標函數(shù)值減少的方向進行；在每一輪中，依據(jù) k 個參照點將其周圍的點分別組成 k 個簇，而每個簇的幾何中心將被作為下一輪迭代的參照點，迭代使得選取的參照點越來越接近真實的簇幾何中心，使得類內(nèi)對象之間的相似性最大，類之間的相似性最小。聚類效果的好壞用目標函數(shù) J表示:， () 其中是與之間的距離函數(shù)，如歐氏距離。目標函數(shù)J 其實就是每個數(shù)據(jù)點與所在簇的質(zhì)心的距離之和，所以，J值越小，簇就越緊湊，相對越獨立。因此，算法通過不斷優(yōu)化J的取值來尋求好的聚類方案，當J取極小值時，對應的聚類方案即是最優(yōu)方案。根據(jù)聚類結(jié)果的表達方式可以將聚類算法劃分為：硬Kmeans（HCM）算法、模糊Kmeans（FCM）算法和概率Kmeans 算法（PCM）。Kmeans 算法描述如下：步驟 1) 隨機選取k個對象作為初始的簇的質(zhì)心。 步驟 2) 計算對象與各個族的質(zhì)心的距離，將對象劃分到距離其最近的簇 。 步驟 3) 重新計算每個新簇的均值，即質(zhì)心。步驟 4) 若簇的質(zhì)心不再變化，則返回劃分結(jié)果，否則轉(zhuǎn)步驟2）.kmeans 算法嘗試找出使平方誤差函數(shù)值最小的k個劃分。當結(jié)果簇是密集的，而簇與簇之間區(qū)別明顯時，它的效果較好。面對大規(guī)模數(shù)據(jù)集，該算法是相對可擴展的，并且具有較高的效率。算法的復雜度為O(nkt),其中，n為數(shù)據(jù)集中對象的數(shù)目，k為期望得到的簇的數(shù)目，t為迭代的次數(shù)。通常情況下，算法可以終止于局部最優(yōu)解。 但是，k－means算法只有在簇的平均值被定義的情況下才能使用。這可能不適用于某些應用，例如涉及有分類屬性的數(shù)據(jù)。其次，這種算法要求事先給出要生成的簇的數(shù)目k，顯然，這在某些應用中是不實際的。另外，kmeans算法不適用于發(fā)現(xiàn)非凸面形狀的簇，或者大小差別很大的簇。還有，它對于噪音和孤立點數(shù)據(jù)是敏感的。 k－means算法有很多變種，例如，k模算法用模代替簇的平均值，用新的相異性度量方法來處理分類對象，用基于頻率的方法來修改聚類的模。而k－平均算法和k－模算法相結(jié)合，用來處理有數(shù)值類型和分類類型屬性的數(shù)據(jù)，就產(chǎn)生了k原型算法。2 .2. 2　 D BSCAN 算法DBSCAN 算法可以將足夠高密度的區(qū)域劃分為簇, 并可以在帶有 “噪聲” 的空間數(shù)據(jù)庫中發(fā)現(xiàn)任意形狀的聚類 。 DBSCAN 通過檢查數(shù)據(jù)庫中每個點的E 2鄰域來尋找聚類 。 如果一個點 P 的 E 2 鄰域包含多于M inP ts 個點, 則創(chuàng)建一個以 P 作為核心對象的新簇 。然后反復地尋找從這些核心對象直接密度可達的對象, 當沒有新的點可以被添加到任何簇時, 該過程結(jié)束 。 如果采用空間索引, DBSCAN 的計算復雜度是O(n log n ) 。 STING算法STING（Statistical Information Grid)算法是一種基于網(wǎng)格的多分辨率聚類方法，它將空間區(qū)域劃分為若干矩形網(wǎng)格單元。針對不同級別的分辨率，通常存在多個級別的矩形單元，這些單元形成了一個層次結(jié)構(gòu)，高層的每個單元被劃分為多個低一層的單元。關(guān)于每個網(wǎng)格單元屬性的統(tǒng)計信息，如平均值、最大值、最小值等，被預先計算和存儲。 高層單元的統(tǒng)計參數(shù)可以很容易地從低層單元的計算得到。這些統(tǒng)計參數(shù)包括:屬性無關(guān)的參數(shù)count；屬性相關(guān)的參數(shù)m(平均值)，s(標準方差)，min(最小值)，max(最大值)，以及該單元中屬性值遵循的分布(distribution)類型，例如正態(tài)分布、平均分布、指數(shù)分布或無(如果分布未知)。當數(shù)據(jù)被裝載進數(shù)據(jù)庫時，底層單元的參數(shù)count、m、s, min和max直接進行計算。如果分布的類型事先知道，distribution的值可以由用戶指定，也可以通過假設(shè)檢驗來獲得。 統(tǒng)計參數(shù)的使用可以按照以下自頂向下的基于網(wǎng)格的方法:首先，在層次結(jié)構(gòu)中選定一層作為查詢處理的開始點。通常該層包含少量的單元。對當前層次的每個單元，我們計算置信度區(qū)間或者估算其概率范圍，用以反映該單元與給定查詢的關(guān)聯(lián)程度，不相關(guān)的單元就不再考慮。低一層的處理就只檢查剩余的相關(guān)單元。這個過程反復進行，直到達到底層。此時，如果滿足查詢條件，那么返回相關(guān)單元的區(qū)域。否則，檢索和進一步處理相關(guān)單元中的數(shù)據(jù)，直到它們滿足查詢條件。 與其他聚類方法相比，STING算法的優(yōu)點在于: (1) 由于存儲在每個單元中的統(tǒng)計信息提供了單元中的數(shù)據(jù)不依賴于查詢的匯總信息，所有基于網(wǎng)格的計算是獨立于查詢的； (2) 網(wǎng)格結(jié)構(gòu)有利于并行處理和增量更新； (3) 算法效率很高。STING算法通過掃描一次數(shù)據(jù)庫來計算單元的統(tǒng)計信息，產(chǎn)生聚類的時間復雜度是On)，其中n為對象的數(shù)目。在層次結(jié)構(gòu)建好后，查詢處理的時間復雜度是O(g)，其中g(shù)是最低網(wǎng)格單元的數(shù)目，通常遠遠小于n 。 STING 算法的性能取決于最底層單元的粒度，該粒度也決定著聚類結(jié)果的質(zhì)量。STING算法在粒度較大時，速度非?？?，但這時聚類的質(zhì)量不夠好。當粒度較小時，聚類結(jié)果的質(zhì)量好，但處理的代價會增加。 模糊聚類算法 　模糊聚類算法概述模糊聚類算法是一種基于函數(shù)最優(yōu)方法的聚類算法，使用微積分計算技術(shù)求最優(yōu)代價函數(shù)。在基于概率算法的聚類方法中將使用概率密度函數(shù)，為此要假定合適的模型，模糊聚類算法的向量可以同時屬于多個聚類，從而擺脫上述問題。在模糊聚類算法中，定義了向量與聚類之間的近鄰函數(shù)，并且聚類中向量的隸屬度由隸屬函數(shù)集合提供。對模糊方法而言，在不同聚類中的向量隸屬函數(shù)值是相互關(guān)聯(lián)的。硬聚類可以看成是模糊聚類方法的一個特例。 模糊聚類算法的分類模糊聚類分析算法大致可分為三類[4]： 1）分類數(shù)不定，根據(jù)不同要求對事物進行動態(tài)聚類，此類方法是基于模糊等價矩陣聚類的，稱為模糊等價矩陣動態(tài)聚類分析法。 2）分類數(shù)給定，尋找出對事物的最佳分析方案，此類方法是基于目標函數(shù)聚類的，稱為模c均值聚類。3）在攝動有意義的情況下，根據(jù)模糊相似矩陣聚類，此類方法稱為基于攝動的模糊聚類分析法。 FCM算法FCM算法是一種基于劃分的聚類算法，它的思想就是使得被劃分到同一簇的對象之間相似度最大，而不同簇之間的相似度最小。 模糊C均值算法是普通C均值算法的改進，普通C均值算法對于數(shù)據(jù)的劃分是硬性的，而FCM則是一種柔性的模糊劃分。在介紹FCM具體算法之前我們先介紹一些模糊集合的基本知識。隸屬度函數(shù)是表示一個對象x隸屬于集合A的程度的函數(shù)，通常記做μA(x)，其自變量范圍是所有可能屬于集合A的對象（即集合A所在空間中的所有點），取值范圍是[0,1]，即0=1，μA(x)=1。μA(x)=1表示x完全隸屬于集合A，相當于傳統(tǒng)集合概念上的x∈A。一個定義在空間X={x}上的隸屬度函數(shù)就定義了一個模糊集合A，或者叫定義在論域X={x}上的模糊子集 。對于有限個對象x1，x2，……，xn模糊集合 可以表示為：FCM的目標函數(shù)一般化形式： ()這里uij介于0，1間；ci為模糊組I的聚類中心，dij=||cixj||為第I個聚類中心與第j個數(shù)據(jù)點間的歐幾里德距離；且m1是一個加權(quán)指數(shù) 構(gòu)造如下新的目標函數(shù)，可求得使（）式達到最小值的必要條件： ()這里lj，j=1到n，是（）式的n個約束式的拉格朗日乘子。對所有輸入?yún)⒘壳髮В故剑ǎ┻_到最小的必要條件為： () 和 (). 基于閾值的分割方法包括全局閾值、自適應閾值、最佳閾值等等。閾值分割算法的關(guān)鍵是確定閾值，如果能確定一個合適的閾值就可準確地將圖像分割開來。閾值確定后，將閾值與像素點的灰度值比較和像素分割可對各像素并行地進行，分割的結(jié)果直接給出圖像區(qū)域。全局閾值是指整幅圖像使用同一個閾值做分割處理，適用于背景和前景有明顯對比的圖像。它是根據(jù)整幅圖像確定的：T=T(f)。但是這種方法只考慮像素本身的灰度值，一般不考慮空間特征，因而對噪聲很敏感。常用的全局閾值選取方法有利用圖像灰度直方圖的峰谷法、最小誤差法、最大類間方差法、最大熵自動閾值法以及其它一些方法。 　　在許多情況下，物體和背景的對比度在圖像中的各處不是一樣的，這時很難用一個統(tǒng)一的閾值將物體與背景分開。這時可以根據(jù)圖像的局部特征分別采用不同的闞值進行分割。實際處理時，需要按照具體問題將圖像分成若干子區(qū)域分別選擇閾值，或者動態(tài)地根據(jù)一定的鄰域范圍選擇每點處的閾值，進行圖像分割。這時的閾值為自適應閾值。 閾值的選擇需要根據(jù)具體問題來確定，一般通過實驗來確定。對于給定的圖像，可以通過分析直方圖的方法確定最佳的閾值，例如當直方圖明顯呈現(xiàn)雙峰情況時，可以選擇兩個峰值的中點作為最佳閾值。．基于邊緣的分割方法檢測灰度級或者結(jié)構(gòu)具有突變的地方，表明一個區(qū)域的終結(jié)，也是另一個區(qū)域開始的地方。這種不連續(xù)性稱為邊緣。不同的圖像灰度不同，邊界處一般有明顯的邊緣，利用此特征可以分割圖像。圖像中邊緣處像素的灰度值不連續(xù)，這種不連續(xù)性可通過求導數(shù)來檢測到。對于階躍狀邊緣，其位置對應一階導數(shù)的極值點，對應二階導數(shù)的過零點(零交叉點)。因此常用微分算子進行邊緣檢測。常用的一階微分算子有Roberts算子、Prewitt算子和Sobel算子，二階微分算子有Laplace算子和Kirsh算子等。在實際中各種微分算子常用小區(qū)域模板來表示，微分運算是利用模板和圖像卷積來實現(xiàn)。這些算子對噪聲敏感，只適合于噪聲較小不太復雜的圖像。 由于邊緣和噪聲都是灰度不連續(xù)點，在頻域均為高頻分量，直接采用微分運算難以克服噪聲的影響。因此用微分算子檢測邊緣前要對圖像進行平滑濾波。LoG算子和Canny算子是具有平滑功能的二階和一階微分算子，邊緣檢測效果較好，如圖4所示。其中l(wèi)oG算子是采用Laplacian算子求高斯函數(shù)的二階導數(shù)，Canny算子是高斯函數(shù)的一階導數(shù)，它在噪聲抑制和邊緣檢測之間取得了較好的平衡。．基于聚類分析的圖像分割方法　　 特征空間聚類法進行圖像分割是將圖像空間中的像素用對應的特征空間點表示，根據(jù)它們在特征空間的聚集對特征空間進行分割，然后將它們映射回原圖像空間，得到分割結(jié)果。其中，K均值、模糊C均值聚類(FCM)算法是最常用的聚類算法。K均值算法先選K個初始類均值，然后將每個像素歸入均值離它最近的類并計算新的類均值。迭代執(zhí)行前面的步驟直到新舊類均值之差小于某一閾值。模糊C均值算法是在模糊數(shù)學基礎(chǔ)上對K均值算法的推廣，是通過最優(yōu)化一個模糊目標函數(shù)實現(xiàn)聚類，它不像K均值聚類那樣認為每個點只能屬于某一類，而是賦予每個點一個對各類的隸屬度，用隸屬度更好地描述邊緣像素亦此亦彼的特點，適合處理事物內(nèi)在的不確定性。利用模糊C均值(FCM)非監(jiān)督模糊聚類標定的特點進行圖像分割，可以減少人為的干預，且較適合圖像中存在不確定性和模糊性的特點。 本章主要介紹了聚類分析的概述以及定義，聚類分析的一般步驟，常見的聚類算法Kmeans 算法，D BSCAN 算法，STING算法，F(xiàn)CM算法，和常見的圖像分割方法，本章是該研究所需要的預備基礎(chǔ)知識。第三章 基于Kmeans算法的圖像分割方法對于彩色圖像的研究都是在特定的顏色空間進行的，常用的顏色空間有、等。顏色空間的選擇應盡可能與人類的視覺系統(tǒng)和心理感知一致。本章就是在空間研究Kmeans算法應用于圖像分割的效果。 彩色空間非常簡單，彩色空間是一個立方體三維坐標空間結(jié)構(gòu)，分別用紅、綠、藍表示三個坐標軸。任何顏色都落入彩色立方體內(nèi)。但是，存在如下一些不足：（1）空間用紅、綠、藍三基色的混合比例定義不同的色彩，從而不同的顏色難以用準確的數(shù)值來表示，定量分析比較困難。（2）系統(tǒng)中，彩色通道之間的相關(guān)性很好，從而合成圖像的飽和度偏低，色調(diào)變化較小，圖像視覺效果較差。（3）人眼只能夠通過感知顏色的亮度、色調(diào)以及飽和度來區(qū)分物體，不能夠直接感覺紅、綠、藍三色的比例，此外，色調(diào)和飽和度與紅、綠、藍的關(guān)系是非線性的，因此，空間中對圖像進行分析與處理難以控制其結(jié)果。kmeans算法是一種得到最廣泛使用的基于劃分的聚類算法，把n個對象分為k個簇，以使簇內(nèi)具有較高的相似度。相似度的計算根據(jù)一個簇中對象的平均值來進行。它與處理混合正態(tài)分布的最大期望算法很相似，因為他們都試圖找到數(shù)據(jù)中自然聚類的中心。算法首先隨機地選擇k個對象，每個對象初始地代表了一個簇的平均值或中心。對剩余的每個對象根據(jù)其與各個簇中心的距離，將它賦給最近的簇，然后重新計算每個簇的平均值。這個過程不斷重復，直到準則函數(shù)收斂。 ()它假設(shè)對象屬性來自于空間向量，并且目標是使各個群組內(nèi)部的均方誤差總和最小。假設(shè)有k個群組Si, i=1,2,...,k。μi是群組Si內(nèi)所有元素xj的重心，或叫中心點。kmeans 算法基本步驟：（1） 從 n個數(shù)據(jù)對象任意選擇 k 個對象作為初始聚類中心；（2） 根據(jù)每個聚類對象的均值（中心對象），計算每個對象與這些中心對象的距離；并根據(jù)最小距離重新對相應對象進行劃分；（3） 重新計算每