遙感數據最小距離分類的幾種算法

馬 銘,茍長龍

(甘肅交通職業技術學院，甘肅 蘭州 730070))

測繪4.0：拓普康索佳應用方案專欄

遙感數據最小距離分類的幾種算法

馬 銘,茍長龍

(甘肅交通職業技術學院，甘肅 蘭州 730070))

近年來，遙感數據的應用在廣度和深度上不斷融合發展和拓展。遙感數據的分類已成為遙感地理信息系統的一門關鍵技術。快速、高精度的遙感圖像分類算法是目前實用、先進的技術，也是研究的熱點之一。傳統的分類器包括：最大似然分類、最小距離分類、平行算法分類。新分類器包括：模糊分類、空間結構紋理分類、神經網絡分類、決策樹分類、專家系統分類。本文擬對最小距離分類的算法進行分析和概括。

1 傳統最小距離分類

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

2 自適應最小距離分類

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

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

2.1 自適應距離最小分類的基本步驟

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

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

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

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

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

2.2 自適應最小距離分類器的訓練步驟

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

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

(3) 重復步驟(2)對各子集樹依次進行訓練，直到沒有一個子集樹被更新，訓練結束后，各個節點上的樣本集合已經沒有必要保留。

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

2.3 分類試驗結果

本文試驗所用的原始圖像是葡萄牙里斯本地區泰吉河流域遙感圖像，原始圖像為256×256像素，6個波段,地面采樣得到的樣本為14類,共8046點。14類樣本中包含土地、水和當地若干典型植被。筆者從8046點樣本中隨機選取2500點作訓練樣本集,然后對8046點采樣樣本進行分類,以便統計分類精度,得到的試驗數據見表1，對全圖進行分類的結果圖像如圖1所示。

圖1 對全圖進行分類的結果

分類算法正確點數正確率/(%)自適應最小距離分類747892．5傳統最小距離分類326040．4

從表1中可以看出，自適應最小距離分類的精度要遠遠超過傳統最小距離分類的精度。因此，它是一種有效的監督分類的算法，對訓練樣本作適當分解處理是提高有監督分類精度的有效方法。

3 加權最小距離分類

3.1 多重限制分類器

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

3.2 標稱型和字符串型屬性

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

3.3 屬性的方差

(1) 標準化歐氏距離

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

(2) 標準化歐氏距離的一種變形

式中，δi是整個訓練集的屬性i的方差。

(3) 標準歐氏距離的另一種變形

算法的步驟如下：

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

3.4 試驗結果

(1) 試驗的結果主要是將傳統最小距離與加權最小距離的性能作比較。

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

表2 試驗1數據集的構成描述

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

兩個分類器在每個數據集上分別測試了10次，每次試驗采用不同的10重劃分。表3列出了10次測試的平均正確率，并且列出了正確率的平均值。可以看出加權最小距離分類的正確率比傳統最小距離分類的正確率高出了近8個百分點。

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

4 結 語

目前，由于遙感和GIS的緊密結合，對遙感數據的質量評價也越來越高。本文對遙感數據的分類作了一個簡要說明。現對遙感數據分類補充如下：

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

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

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