馬 銘,茍長龍

(甘肅交通職業(yè)技術(shù)學(xué)院，甘肅 蘭州 730070))

測繪4.0：拓普康索佳應(yīng)用方案專欄

遙感數(shù)據(jù)最小距離分類的幾種算法

馬 銘,茍長龍

(甘肅交通職業(yè)技術(shù)學(xué)院，甘肅 蘭州 730070))

近年來，遙感數(shù)據(jù)的應(yīng)用在廣度和深度上不斷融合發(fā)展和拓展。遙感數(shù)據(jù)的分類已成為遙感地理信息系統(tǒng)的一門關(guān)鍵技術(shù)?？焖佟⒏呔鹊倪b感圖像分類算法是目前實用、先進(jìn)的技術(shù)，也是研究的熱點之一。傳統(tǒng)的分類器包括：最大似然分類、最小距離分類、平行算法分類。新分類器包括：模糊分類、空間結(jié)構(gòu)紋理分類、神經(jīng)網(wǎng)絡(luò)分類、決策樹分類、專家系統(tǒng)分類。本文擬對最小距離分類的算法進(jìn)行分析和概括。

1 傳統(tǒng)最小距離分類

最小距離是一種傳統(tǒng)的分類方法，其原理是根據(jù)待分類點到各類樣本訓(xùn)練向量中心的距離，將其納入距離最小的一類。通常對n個波段m個類別采用歐氏距離對其分類

2 自適應(yīng)最小距離分類

根據(jù)多維模式空間中的連續(xù)點集可以用多維球體的并集來逼近，通常采用集合細(xì)分方法K- means算法，每次分解為兩個子集，以二叉樹進(jìn)行。每一類生成一棵二叉樹，二叉樹的一個節(jié)點對應(yīng)一個球體，記錄每個球體的球心及半徑，球心定義為該節(jié)點上樣本子集的中心，半徑為該節(jié)點上的樣本點到球心的歐氏距離的最大值。

自適應(yīng)最小距離分類的基本原理是將每一個類模式點集近似為一組球體的并集，對待分類點判斷其落在哪個球體，并賦予對應(yīng)的類編號。首先求得所有模式集合的球體中心半徑參數(shù)。自適應(yīng)最小距離集合劃分是一個由上而下、逐步細(xì)化的過程，即先用半徑大的球體逼近，再用半徑小的球體逼近，逐步進(jìn)行細(xì)化直到達(dá)到相應(yīng)的分類精度為止。根據(jù)對樣本分類的精度要求自適應(yīng)地控制樣本集合的分解過程，就可以使不同類的小球盡可能分離，從而提高精度。

2.1 自適應(yīng)距離最小分類的基本步驟

求出該點到各類對應(yīng)的子集樹的距離D，待分類點P到子集樹T的距離D(T,p)定義為：

(1) 如果P到T的根節(jié)點對應(yīng)的球心歐氏距離d大于該節(jié)點球體的半徑的兩倍，則忽略該節(jié)點細(xì)分得到的所有小球，并令D=d。

(2) 如果T的根節(jié)點已經(jīng)是葉節(jié)點，則令D=d。

(3) 若步驟(1)、(2)均不滿足，則D遞歸定義為P到T的左右子樹T1、T2的距離D1、D2的最小者，即：D1=D(T1,P)，D2=D(T2,P)；D=min(D1,D2)。

根據(jù)最小距離原理，將距離D最小的一子集樹的類號賦予待分類點。

2.2 自適應(yīng)最小距離分類器的訓(xùn)練步驟

(1) 初始化各個類的子集樹為只有一個根節(jié)點的情況，即根節(jié)點上的樣本點集均為訓(xùn)練樣本集合中屬于該類的子集，同時求出各個根節(jié)點上樣本點集的中心和半徑。

(2) 對各個子集樹進(jìn)行訓(xùn)練，對各個葉節(jié)點，如果按照前述分類算法對該節(jié)點上的樣本點集進(jìn)行細(xì)分，即生成其左右子節(jié)點，將樣本點集用K- means分類算法分解為兩個子集，分別作為兩個子節(jié)點的樣本點集，并求出左右子節(jié)點對應(yīng)球體的中心和半徑等參數(shù)。

(3) 重復(fù)步驟(2)對各子集樹依次進(jìn)行訓(xùn)練，直到?jīng)]有一個子集樹被更新，訓(xùn)練結(jié)束后，各個節(jié)點上的樣本集合已經(jīng)沒有必要保留。

自適應(yīng)最小距離分類用一組球體的中心來定義距離，較單個中心更準(zhǔn)確，由于樣本的集合分解是在對樣本分類試驗的反饋指導(dǎo)下自適應(yīng)進(jìn)行的，因此這一算法能有效地提高分類精度。

2.3 分類試驗結(jié)果

本文試驗所用的原始圖像是葡萄牙里斯本地區(qū)泰吉河流域遙感圖像，原始圖像為256×256像素，6個波段,地面采樣得到的樣本為14類,共8046點。14類樣本中包含土地、水和當(dāng)?shù)厝舾傻湫椭脖?。筆者從8046點樣本中隨機(jī)選取2500點作訓(xùn)練樣本集,然后對8046點采樣樣本進(jìn)行分類,以便統(tǒng)計分類精度,得到的試驗數(shù)據(jù)見表1，對全圖進(jìn)行分類的結(jié)果圖像如圖1所示。

圖1 對全圖進(jìn)行分類的結(jié)果

分類算法正確點數(shù)正確率/(%)自適應(yīng)最小距離分類747892．5傳統(tǒng)最小距離分類326040．4

從表1中可以看出，自適應(yīng)最小距離分類的精度要遠(yuǎn)遠(yuǎn)超過傳統(tǒng)最小距離分類的精度。因此，它是一種有效的監(jiān)督分類的算法，對訓(xùn)練樣本作適當(dāng)分解處理是提高有監(jiān)督分類精度的有效方法。

3 加權(quán)最小距離分類

3.1 多重限制分類器

多重限制分類器將多重特征空間的每一條軸線分割,每一個類的分割區(qū)間基于其在該軸上的最大和最小值。該分類器的準(zhǔn)確性依賴于每類數(shù)據(jù)統(tǒng)計后對最大值和最小值的選擇。多重限制分類器簡單、易理解，與其他分類器相比計算時間最短。但是該算法的準(zhǔn)確性低,尤其在特征空間的分布中傾斜軸存在協(xié)方程和依賴時。執(zhí)行該算法前,應(yīng)使用主要成分分析作正交化。借鑒多重限制分類器,加權(quán)最小距離分類器為(Xi-Uki)2增加權(quán)值Vki。在訓(xùn)練過程中統(tǒng)計每類每個屬性的最大最小值,在分類過程中如果待分類數(shù)據(jù)元組X的屬性i的值超出第k類屬性i的最大最小值范圍,Vki取一個較大的值,其他情況Vki=1。Vki權(quán)值的大小通過試驗確定。針對不同的數(shù)據(jù)集,權(quán)值的最優(yōu)解不同,因此只能通過試驗確定一個模糊最優(yōu)值，結(jié)果為n(屬性個數(shù))。

3.2 標(biāo)稱型和字符串型屬性

傳統(tǒng)的最小距離分類器使用歐氏距離和馬哈利諾貝斯距離時,無法處理有標(biāo)稱型和字符串型屬性的數(shù)據(jù)。為了處理該類數(shù)據(jù),需要特別定義標(biāo)稱型和字符串型屬性的標(biāo)準(zhǔn)值。若屬性i是標(biāo)稱型或字符串型屬性,中心向量UK的屬性值UKi取該類的所有數(shù)據(jù)元組中屬性i的最頻繁值。定義標(biāo)稱型和字符串型屬性i的標(biāo)準(zhǔn)值,UKi的標(biāo)準(zhǔn)值定為0,與UKi相等的屬性值為0,不等的為1。當(dāng)?shù)趉類屬性i的方差δki為0,即第k類該屬性的值都相同時,待分類數(shù)據(jù)X的屬性i的值Xi是否與UKi相等可能決定了其是否屬于第k類,或與其他屬性相比對分類有較大的貢獻(xiàn);當(dāng)方差δki不為0時,Xi對決定X是否屬于第k類,很可能貢獻(xiàn)不大。因此為(Xi-Uki)2增加權(quán)值Wki,當(dāng)δki≠0時,Wki=1;當(dāng)δki=0時,Wki=100。Wki的值通過試驗確定。針對不同的數(shù)據(jù)集,Wki的最優(yōu)解不同,通過試驗確定了一個模糊最優(yōu)值100。

3.3 屬性的方差

(1) 標(biāo)準(zhǔn)化歐氏距離

式中，δki是第k類屬性i的方差。

(2) 標(biāo)準(zhǔn)化歐氏距離的一種變形

式中，δi是整個訓(xùn)練集的屬性i的方差。

(3) 標(biāo)準(zhǔn)歐氏距離的另一種變形

算法的步驟如下：

(2) 判定Xi與之距離最近的類，則屬于該類。

3.4 試驗結(jié)果

(1) 試驗的結(jié)果主要是將傳統(tǒng)最小距離與加權(quán)最小距離的性能作比較。

(2) 試驗數(shù)據(jù)選自UCI資源集。表2列出了試驗1使用的每個數(shù)據(jù)集的實例個數(shù)、類個數(shù)、屬性個數(shù)等數(shù)據(jù)信息。由于傳統(tǒng)的最小距離算法不能處理標(biāo)稱型數(shù)值數(shù)據(jù)，因此對于某些分類的試驗結(jié)果沒有列出。

表2 試驗1數(shù)據(jù)集的構(gòu)成描述

試驗的主要目的是將傳統(tǒng)最小距離分類與加權(quán)最小距離分類在各數(shù)據(jù)集上的分類正確率進(jìn)行比較。每個分類器的分類正確率是在測試集上成功預(yù)測的實例占總實例的百分比，采用10重交叉驗證估計分類器的正確率。

兩個分類器在每個數(shù)據(jù)集上分別測試了10次，每次試驗采用不同的10重劃分。表3列出了10次測試的平均正確率，并且列出了正確率的平均值?？梢钥闯黾訖?quán)最小距離分類的正確率比傳統(tǒng)最小距離分類的正確率高出了近8個百分點。

表3 兩種最小距離分類器的試驗結(jié)果 (%)

4 結(jié) 語

目前，由于遙感和GIS的緊密結(jié)合，對遙感數(shù)據(jù)的質(zhì)量評價也越來越高。本文對遙感數(shù)據(jù)的分類作了一個簡要說明?，F(xiàn)對遙感數(shù)據(jù)分類補(bǔ)充如下：

(1) 本文對傳統(tǒng)分類及其他兩種改進(jìn)方法作了比較，通過數(shù)據(jù)分析比較可得出加權(quán)最小距離分類是一種更有效的方法。

(2) 可以根據(jù)具體的精度要求進(jìn)行選擇性分類。

(3) 對加權(quán)最小距離分類和自適應(yīng)最小距離分類精度的比較，將是下一個要研究的課題。