遙感影像識別-第三章 聚類分析 Part Ⅰ課件

1、遙感影像識別第三章: 聚類分析 Part 3-1 相似性準(zhǔn)則 3-2 聚類準(zhǔn)則函數(shù) 3-3 兩種簡單的聚類算法 3-4 動態(tài)聚類算法 主要內(nèi)容上一章針對確定性的模式分類方法進(jìn)行了討論，所謂確定性的模式是指：如果試驗(yàn)對象和測量條件相同，所有的測量具有重復(fù)性，即在多次的測量中，它們的結(jié)果不變，這樣獲得的模式，簡稱確定性的模式。 與之相對應(yīng)的，測量結(jié)果是隨機(jī)的，這樣的模式稱為隨機(jī)模式。隨機(jī)模式可以采用基于Bayes理論的分類方法進(jìn)行分類，其前提是各類別總體的概率分布已知，要決策的分類的類別數(shù)一定。 對于確定性的模式，如果類別已知（訓(xùn)練樣本屬性也已知），則可以通過上一章介紹的方法進(jìn)行分類。 當(dāng)預(yù)先不知

2、道類型數(shù)目，或者用參數(shù)估計(jì)和非參數(shù)估計(jì)難以確定不同類型的類概率密度函數(shù)時，為了確定分類器的性能，可以利用聚類分析的方法。 聚類分析無訓(xùn)練過程，訓(xùn)練與識別混合在一起。 設(shè)有樣本集 ，要求按某種相似性把 X分類，怎樣實(shí)現(xiàn)？ 利用參數(shù)估計(jì)或非參數(shù)估計(jì)的方法，在混合密度的局部極大值區(qū)域?qū)?yīng)著一個類型，但是這個方法需要大量的樣本。況且，有時混合訓(xùn)練樣本集X的數(shù)據(jù)結(jié)構(gòu)具有相同的統(tǒng)計(jì)特征，它們都包含著不同數(shù)目的類型。 如下圖所示，表示具有相同的試驗(yàn)平均值和樣本協(xié)方差矩陣的三個數(shù)據(jù)集。 3-1 相似性準(zhǔn)則 聚類分析符合“物以類聚，人以群分“的原則，它把相似性大的樣本聚集為一個類型，在特征空間里占據(jù)著一個局部區(qū)

3、域。每個局部區(qū)域都形成一個聚合中心，聚合中心代表相應(yīng)類型。如上圖中，(a)有一個聚合中心，(b)、(c)有兩個。 聚類分析避免了估計(jì)類概率密度的困難，對每個聚合中心來說都是局部密度極大值位置，其附近密度高，距離越遠(yuǎn)密度越小。因此，聚類分析方法與估計(jì)密度函數(shù)的方法還是一致的，只是采用了不同的技術(shù)途徑。 聚類分析的關(guān)鍵問題：如何在聚類過程中自動地確定類型數(shù)目c。 實(shí)際工作中，也可以給定c值作為算法終止的條件。 聚類分析的結(jié)果與特征的選取有很大的關(guān)系。不同的特征，分類的結(jié)果不同。 因此，如何衡量樣本相似性，對聚類有直接影響。 （1）歐氏距離歐氏距離簡稱距離，模式樣本向量x與y之間的歐氏距離定義為：

4、這里， d為特征空間的維數(shù)。當(dāng) 較小時，表示x和y在一個類型區(qū)域，反之，則不在一個類型區(qū)域。 這里有一個門限 的選擇問題。 若 選擇過大，則全部樣本被視作一個唯一類型；若 選取過小，則可能造成每個樣本都單獨(dú)構(gòu)成一個類型。必須正確選擇門限值以保證正確分類。 另外，模式特征坐標(biāo)單位的選取也會強(qiáng)烈地影響聚類結(jié)果。 例如：一個二維模式，一個特征是長度，另一個特征是壓力。 當(dāng)長度由厘米變?yōu)槊?，?中長度特征的比重會下降，同樣，若把比重單位由毫米汞柱高度變成厘米汞柱高度， 值中壓力特征的影響也會下降。 可以用圖表示上述情況： （2）馬氏（Mahalanobis）距離 定義：馬氏距離的平方 其中， 為均值向

5、量， 為協(xié)方差矩陣。馬氏距離排除了不同特征之間相關(guān)性的影響，其關(guān)鍵在于協(xié)方差矩陣的計(jì)算。當(dāng)為對角陣時，各特征之間才完全獨(dú)立；當(dāng)為單位矩陣時，馬氏距離等于歐氏距離。馬氏距離 比較適用于對樣本已有初步分類的情況，做進(jìn)一步考核、修正。 （3）明氏（Minkowsky）距離 定義：明氏距離: 它是若干距離函數(shù)的通式： 時，等于歐氏距離； 時，稱為“街坊”（city block）距離。 滿足： 當(dāng) 時， 達(dá)到最大。 對于坐標(biāo)系的旋轉(zhuǎn)及放大、縮小是不變的量，但對位移和一般性的線性變換不是不變的。 當(dāng)模式的各特征僅為(0,1)二元取值時， 的意義如下： 若模式樣本的第i維特征取值為1，則該樣本占有第i維特征

6、。 若模式樣本的第i維特征取值為0，則該樣本無此維特征。此時， 等于x與y兩個向量中，共有的特征數(shù)目。 為x占有的特征數(shù)目與y占有的特征數(shù)目的幾何平均。 因此，二元取值情況下， 反映x與y共有的特征數(shù)目的相似性度量。顯然， 越大，共有特征數(shù)目越多，相似性越高。 除上述相似性度量外，還有許多相似性度量，如“樣本與核的相似性度量”，“近鄰函數(shù)值相等”相似性度量，這些都是為解決某一特殊問題的相似性度量，都是從上述相似性度量派生出來的。 樣本相似性度量是聚類分析的基礎(chǔ)，針對具體問題，選擇適當(dāng)?shù)南嗨菩远攘渴潜ＷC聚類質(zhì)量的重要問題。但有了相似性度量還不夠，還必須有適當(dāng)?shù)木垲悳?zhǔn)則函數(shù)。聚類準(zhǔn)則函數(shù)對聚類質(zhì)量

7、也有重大影響。 相似性度量 集合與集合的相似性。 相似性準(zhǔn)則 分類效果好壞的評價準(zhǔn)則。 在樣本相似性度量的基礎(chǔ)上，聚類分析還需要一定的準(zhǔn)則函數(shù)，才能把真正屬于同一類的樣本聚合成一個類型的子集，而把不同類的樣本分離開來。 如果聚類準(zhǔn)則函數(shù)選得好，聚類質(zhì)量就會高。同時，聚類準(zhǔn)則函數(shù)還可以用來評價一種聚類結(jié)果的質(zhì)量，如果聚類質(zhì)量不滿足要求，就要重復(fù)執(zhí)行聚類過程，以優(yōu)化結(jié)果。 在重復(fù)優(yōu)化中，可以改變相似性度量，也可以選用新的聚類準(zhǔn)則。 3-2 聚類準(zhǔn)則函數(shù) 假定有混合樣本 ，采用某種相似性度量，X被聚合成c個分離開的子集，每個子集是一個類型，它們分別包含 個樣本。為了衡量聚類的質(zhì)量，采用誤差平方和 聚

8、類準(zhǔn)則函數(shù)，定義為：式中 為類型 中樣本的均值： 1. 誤差平方和準(zhǔn)則（最常用的） 是c個集合的中心，可以用來代表c個類型。 是樣本和集合中心的函數(shù)。在樣本集X給定的情況下， 的取值取決于c個集合中心。 描述n個試驗(yàn)樣本聚合成c個類型時，所產(chǎn)生的總誤差平方和。 越小越好。 最小方差劃分：尋找 最小的聚類結(jié)果，也就是在誤差平方和準(zhǔn)則下的最優(yōu)結(jié)果。 注意：如果不同類型的樣本數(shù)目相差很大，采用誤差平方和準(zhǔn)則，有可能把樣本數(shù)目多的類型分開，以便達(dá)到總的 最小。如下圖所示： 定義：加權(quán)平均平方距離和準(zhǔn)則 式中： 是類內(nèi)樣本間平均平方距離。 即所有的樣本之間距離的平均值。 2. 加權(quán)平均平方距離和準(zhǔn)則 類間距離和可用于描述聚類結(jié)果的類間距離分布狀態(tài)。它定義為：加權(quán)類間距離和： 式中， 為 類型的樣本均值向量： 3. 類間距離和準(zhǔn)則 m為全部樣本的均值向量： 為 類型的先驗(yàn)概率，可以用 來估計(jì)。對于兩類問題 ，類間距離常用