案例支撐下的樸素貝葉斯樹狀河系自動分級方法

段佩祥，錢海忠，何海威，謝麗敏，羅登瀚

信息工程大學(xué)地理空間信息學(xué)院，河南 鄭州 450000

在地圖上，河流常常不單獨存在，而是由一條主流和若干級支流組成一個河系。根據(jù)平面圖形特點，河系類型可分為樹枝狀、羽毛狀、格狀、扇狀、輻射狀等，其中樹狀河系最為常見，即主流有若干支流，而各條支流又可能擁有若干亞支流等[1]。樹狀河系具有明顯的層次結(jié)構(gòu)，主流、支流蘊含著空間上的“父子關(guān)系”，對其進行綜合應(yīng)充分反映河流的主、支流關(guān)系，強調(diào)支流注入主流處的圖形特點[2]。因此，河流分級是樹狀河系綜合的關(guān)鍵所在，也是研究的重點和難點。

對此，已有不少學(xué)者進行了富有成效的探索與研究。大致可分為兩類：

(1)通過河段的局部空間關(guān)系分析來確定主、支流關(guān)系。文獻[3]提出了E關(guān)系、EC關(guān)系和序關(guān)系的河系目標基本關(guān)系；文獻[4]通過緩沖區(qū)檢索來建立河網(wǎng)的主支流父子關(guān)系。該類方法缺少屬性特征的參與，難以對河段的主支流特征進行量化評價。

(2)通過多指標綜合評價方法來確定主支流關(guān)系。文獻[5]通過計算主支流夾角等來確定各河段的流向和主支流關(guān)系；文獻[6]通過提取河流的高差、集水面積等屬性信息進行權(quán)重判別來自動判別河流的主支流；在此基礎(chǔ)上，文獻[7]使用了支流級別建立水系的Horton碼來完成分級；文獻[8]則采用最大隸屬度帶權(quán)平均規(guī)劃法來確定權(quán)重；文獻[9—10]分別顧及節(jié)點處分支河段的累計河段數(shù)、累計長度和河段深度、最大長度上游河段來識別河系主流；文獻[11]根據(jù)河流語義、長度、角度約束的樹狀河系Stroke連接來構(gòu)成樹狀河系層次關(guān)系。該類方法較少考慮到河系的整體結(jié)構(gòu)特征，易出現(xiàn)局部的主支流判別錯誤。

以上研究使用了不同方法對河系進行河流分級，取得了較好的成果。然而，河系的分級是從人的認知角度出發(fā)賦予客觀事物的屬性，自然界并不存在固有的河系等級。專家對河系的分級兼顧了局部、整體、幾何、語義等多個角度，是主觀經(jīng)驗和客觀事實進行綜合的結(jié)果。因此，單采用固定的模型和算法難以對其進行描述，還需要專家的經(jīng)驗知識進行輔助判斷。

針對上述現(xiàn)有方法的不足，本文從案例學(xué)習(xí)的角度出發(fā)，提出一種基于樸素貝葉斯的樹狀河系自動分級方法。該方法從現(xiàn)有的分級案例提取知識，通過訓(xùn)練分類模型來指導(dǎo)河段的主支流分類，從而得到更符合專家分類意圖的結(jié)果。

1 樸素貝葉斯的原理與應(yīng)用策略

1.1 樸素貝葉斯的原理

樸素貝葉斯分類模型(naive Bayes classifier,NBC)，發(fā)源于古典數(shù)學(xué)理論，有著堅實的數(shù)學(xué)基礎(chǔ)，以及穩(wěn)定的分類效率，并在實際應(yīng)用中十分成功[12]。該分類模型基于貝葉斯定理與特征條件獨立假設(shè)。設(shè)有變量集U={x,y}，假設(shè)所有的條件屬性x都作為類變量y的子節(jié)點。其中x={x1,x2,…,xn}包括n個條件屬性，y={y1,y2,…,yk}包括k個類標簽，將一個樣本劃分到y(tǒng)k的可能性P(yk|x1,x2,…,xn)為

(1)

樸素貝葉斯分類模型的優(yōu)點有：算法邏輯簡單，易于實現(xiàn)；算法實施的時間、空間開銷?。凰惴ㄐ阅芊€(wěn)定，對于不同特點的數(shù)據(jù)其分類性能差別不大，即模型的健壯性比較好[13]。

1.2 基于樸素貝葉斯的樹狀河系自動分級策略

河系結(jié)構(gòu)可以概括為“河系—河流—河段”的三級結(jié)構(gòu)，且每個河段由交匯點相連。從該結(jié)構(gòu)可以得出，河段間的主支流關(guān)系識別是河流主支流關(guān)系識別的基礎(chǔ)，河流主支流關(guān)系的識別則是河系層次結(jié)構(gòu)化實現(xiàn)分級的基礎(chǔ)?；诖怂枷?，本文從河口出發(fā)，自下游向上游依次對交匯點處各相連河段進行主支流關(guān)系識別，由河段的主支流關(guān)系逐級構(gòu)建河流實體，完成河系的層次結(jié)構(gòu)化，從而實現(xiàn)自動分級。

河段間主支流識別的難點在于多個主流特征的綜合考慮，即在量化表達時如何科學(xué)有效地選取相關(guān)指標和設(shè)定各指標的權(quán)重。對此，專家綜合知識的有效利用是解決該問題的有效途徑[14]。近年來，基于案例學(xué)習(xí)的方法利用機器學(xué)習(xí)算法有效獲取和利用了專家綜合案例中隱含的綜合知識，在制圖綜合領(lǐng)域取得了較好的成效[15-18]。本文從案例學(xué)習(xí)的角度出發(fā)，從已有專家制圖成果中獲取主支流案例，從案例中獲取綜合知識，即利用機器學(xué)習(xí)算法訓(xùn)練生成分類模型指導(dǎo)新樹狀河系的主支流識別。

下游河段的多個上游河段中有且只有一個河段是主流河段，其他則是支流河段。主支流識別實際上是將上游河段中最符合主流特征的分類為主流河段，其他的分類為支流河段的過程。故常用的機器學(xué)習(xí)分類方法并不完全適用于主支流識別過程，可能會出現(xiàn)上游河段中不存在或者同時存在多個河段被分類為主流河段的情況。但是在分類過程中，計算得出分類為主流類別的概率能定量評價各上游河段的主流特征，可以根據(jù)分類概率值排序得出最優(yōu)(即最符合主流特征)河段作為上游河段。由于樸素貝葉斯算法基于貝葉斯定理能科學(xué)定量地計算出分類概率，易于實現(xiàn)，且分類性能和穩(wěn)健性較好。因此，本文選用樸素貝葉斯分類模型計算上游河段分類為主流類別的概率，選取概率值最大的上游河段作為主流河段，其他則全部分類為支流河段。

綜上，本文提出基于樸素貝葉斯的樹狀河系自動分級方法，從已有的樹狀河系分級成果中自動獲取主支流案例，采用樸素貝葉斯的方法對主支流案例進行學(xué)習(xí)來得到NBC分類模型，使用分類模型自下而上對上游河段識別得到主流河流，對各級河流進行層次結(jié)構(gòu)化實現(xiàn)河系自動分級。其具體流程如圖1所示。具體步驟如下：

步驟1：主支流案例的定義與獲取。對河段計算特征描述項作為主支流案例的屬性空間，把專家分級成果中對上游河段的主支流分類結(jié)果作為主支流案例的標記。

步驟2：NBC分類模型的訓(xùn)練。采用樸素貝葉斯的機器學(xué)習(xí)方法對主支流案例進行訓(xùn)練得到NBC分類模型。

步驟3：利用NBC分類模型對新的待分級樹狀河系的河段計算分類為主流類別的概率，對每個交匯點處將主流概率最大的上游河段分類為主流河段，其余分類為支流河段。

步驟4：連接各級主流河段構(gòu)成各級河流實體，進行層次結(jié)構(gòu)化完成河系分級。

圖1 基于樸素貝葉斯的樹狀河系自動分級方法流程Fig.1 Flow chart of automatic classification method of tree-like river network based on NBC

2 主支流案例的設(shè)計和獲取

2.1 主支流案例設(shè)計

本文將主支流案例定義為：由主支流案例對象(object)、案例特征(feature)以及案例標記(lable)組成的一條記錄。采用三元表示法對主支流案例進行描述，每個案例由3部分組成，其形式化的表示為

case：〈O，F(xiàn)，L〉

(2)

式中，案例對象(O)是指具體的河段對象及其唯一序號，如河段_ID_001；案例特征(F)中包含多項對河段的主流特征進行描述的量化指標，特征的確定與表達是案例設(shè)計的難點；案例標記(L)是指對河段的分類標記，即主流(1)、支流(0)。

2.2 主支流案例特征提取

主支流案例設(shè)計中案例特征的提取是關(guān)鍵所在，只有選擇正確的案例特征來充分反映河段的主流特征，才能獲取隱含的主支流分類知識，從而利用機器學(xué)習(xí)算法訓(xùn)練得到行之有效的分類模型。

主流上，在河流的匯合處，上下游河段的流向幾乎在一條直線上，常被稱為“180°假設(shè)”[19]；主流往往是最長的河流，在匯合點處也符合180°假設(shè)[20]。另外，主流一般也擁有最多的支流數(shù)[8]。本文參考相關(guān)文獻，顧及語義特征、河段的局部幾何特征和河流、河系的整體結(jié)構(gòu)特征，選擇以下6項指標作為主支流案例的案例特征(F)，即NBC主支流分類模型的條件屬性：

(1)語義一致性。語義一致性指河段間的名稱是否相同。屬于同一條河流的河段名稱往往具有語義一致性，而主流與支流的河段名稱一般不同。本文對該指標值的計算方式如下：若下游河段與上游河段名稱相同，則賦值為1，否則賦值為0。

(2)匯入角度。上下游河段的匯入角度是主支流識別的重要依據(jù)，匯入角度越接近180°，作為主流河段的可能性越大。本文在計算上下游河段間夾角時，采用從交匯點處分別往外延伸3個節(jié)點所得鈍角夾角的平均值作為最后的匯入角度(若少于3個節(jié)點則使用該河段全部節(jié)點)。

(3)河段長度。河段長度指河段的長度，長度值越大，作為主流河段的可能性越大。本文計算上游河段兩端節(jié)點(即交匯點)間的線要素距離作為河段長度值。

(4)河段分叉數(shù)。河段分叉數(shù)是指河段的上游河段數(shù)量。一般來說河段分叉數(shù)越多，作為主流河段的可能性越大。

(5)最大河流長度。河流最大長度指從河段的交匯點向上游追溯所有河源點中的最大長度。河流最大長度越多，作為主流河段的可能性越大。

(6)上游河源數(shù)。上游河源數(shù)指河段上游所有河源口的數(shù)量。上游河源數(shù)越多，作為主流河段的可能性越大。

2.3 主支流案例獲取

主支流案例自動獲取流程如圖2所示，具體步驟如下。

步驟1：預(yù)處理。為避免原始數(shù)據(jù)中的河流流向錯誤，本文從河源出發(fā)，自上游向下游逐個河段檢查河流流向是否一致，若上下游河段存在不一致，則改正下游河段的河流流向。然后以河段為基本單元自動構(gòu)建樹結(jié)構(gòu)；

步驟2：案例特征和標記計算。遍歷所有河段單元，計算其上游河段如2.2節(jié)所述的特征指標值；判斷其上游河段的等級與該河段是否相同，如果相同則案例標記為1(主流)，否則案例標記為0(支流)。

圖2 主支流案例自動獲取方法流程Fig.2 Flow chart of automatic acquisition of main-tributary case

為驗證本節(jié)主支流案例自動獲取方法的有效性，本文通過人工篩選出某流域河系分級地圖中的所有樹狀河系專家已分級數(shù)據(jù)作為主支流案例獲取的數(shù)據(jù)源，該流域范圍內(nèi)的樹狀河系種類復(fù)雜，不同樹狀河系具有不同的結(jié)構(gòu)和特征，能較好地反映主支流的一般關(guān)系和代表樹狀河系總體，其中部分河系如圖3(a)所示，圖3(b)為各級主流賦以不同顏色和寬度的可視化顯示。

對該數(shù)據(jù)源使用本文案例獲取方法一共得到446個主支流案例，其中主流案例為223個，支流案例為223個，部分案例如表1所示。

表1 部分主支流案例示例Tab.1 Examples of main-tributary case

圖3 某流域樹狀河系分級數(shù)據(jù)Fig.3 Classification data of tree-like river network

3 主支流樸素貝葉斯分類模型的訓(xùn)練和測試

將2.3節(jié)中獲取的主支流案例作為訓(xùn)練樣本利用樸素貝葉斯算法進行訓(xùn)練生成主支流樸素貝葉斯分類模型。訓(xùn)練樣本的數(shù)據(jù)總量為446個，其中主流案例樣本為223個，支流案例樣本為223個，并按2∶1的比例隨機分為訓(xùn)練集和測試集。

建立樸素貝葉斯分類器有3種常用模型：高斯模型、多項式模型和多元伯努利模型。

高斯模型中，每個特征都是連續(xù)的，并且都呈高斯分布。由于特征的所有屬于某個類別的觀測值被假設(shè)符合高斯分布，其條件概率函數(shù)為

(3)

多元伯努利模型中，特征是獨立的布爾(二進制變量)類型來描述輸入。如果特征值xi為1，則P(xi|yk)=P(xi=1|yk)；如果特征值xi為0，則P(xi|yk)=1-P(xi=1|yk)。

本文對3個模型使用相同的數(shù)據(jù)樣本進行訓(xùn)練和測試，從中選擇分類效果最好的模型，其中對模型分類效果通過訓(xùn)練集分類正確率、測試集分類正確率和主流識別正確率3項指標進行衡量。訓(xùn)練集分類正確率和測試集分類正確率分別是分類模型在訓(xùn)練集和測試集上的分類正確率，主流識別正確率是指分類模型在測試集上能正確識別出上游的主流河段的比率。其中對主流識別正確的定義為主流河段分類為主流類別的概率大于其他任何上游河段。經(jīng)訓(xùn)練，對不同模型的分類效果指標統(tǒng)計如表2所示。

表2 不同模型下NBC分類效果統(tǒng)計Tab.2 Statistics of NBC classification results in different models (%)

需要說明的是，測試集分類正確率不高，但并不影響本文方法的主支流識別結(jié)果，其相對不高的原因是由于主支流分類的特殊性。因為主支流分類是相對的，并無絕對的分類標準，主支流識別實際上是將上游河段中最符合主流特征的分類為主流河段，其他的分類為支流河段的過程。故存在較多主流特征不明顯的主流河段(同一交匯處的支流河段主流特征更不明顯)和主流特征較為明顯的支流河段(同一交匯處的主流河段主流特征更加明顯)。而這些河段同樣也作為案例出現(xiàn)在訓(xùn)練集和測試集中，從而導(dǎo)致主流特征不明顯的主流河段被分類為“支流”，與主流特征較為明顯的支流河段被分類為“主流”，因而測試集的分類正確率不高。例如，表3中同一交匯處上游的5號和6號河段由于匯入角度、河段長度等主流特征均不明顯，均被直接分類為支流河段；相反，另一交匯處上游的8號、17號河段由于主流特征明顯，均被直接分類為主流河段。該直接分類結(jié)果與案例原始的標記不符，所以造成了測試集分類正確率不高。

表3 部分測試集案例分類結(jié)果Tab.3 Examples of classification results of test setdata

也正是因為主支流分類的特殊性，本文方法不是通過簡單的直接分類來識別主支流，而是使用分類模型對待分類樹狀河系中的河段計算其分類為主流的概率，在每個交匯點處以概率最大的上游河段作為主流河段。例如，上表中的5號和6號河段二者計算所得的主流分類概率分別為0.002 382 33和0.003 662 27，通過比較概率將原本直接分類為“支流”的6號河段最終分類為“主流”，而8號、17號河段分別為0.525 914 3和0.985 438 81，則將原本分類為“主流”的8號河段最終分類為“支流”，從而避免了主支流分類模型直接分類所導(dǎo)致的錯誤識別結(jié)果。因此，較訓(xùn)練集分類正確率和測試集分類正確率而言，主流識別正確率指標能更好地衡量本文方法中分類模型對主支流識別效果。

由統(tǒng)計數(shù)據(jù)可以看出，多元伯努利模型的3項指標均為最低，說明其在主支流分類效果最差；多項式模型雖然其訓(xùn)練集分類正確率最高，但測試集分類正確率卻略低于高斯模型，且主流識別正確率遠低于高斯模型，這說明高斯模型的主支流分類的實用效果要強于多項式模型。因此，本文選用高斯模型訓(xùn)練得到主支流樸素貝葉斯分類模型。

4 試驗與分析

為驗證本文方法的有效性和實用性，分別對某流域未分級的樹狀河系1和樹狀河系2(如圖4所示)進行主支流識別的試驗(河系1為典型樹狀河系，即河系的主流現(xiàn)象較為明顯，各級河流之間的主流特征差別較大，共擁有89個河段；河系2為非典型樹狀河系，即河系的主流現(xiàn)象不明顯，各級河流之間的主流特征差別較小，共擁有97個河段)，其中部分計算過程和數(shù)值如表4所示。同時選用多準則決策方法(文獻[8])和Stroke特征約束方法(文獻[11])作為對比，試驗結(jié)果如圖5和圖6所示。圖5(a)、圖6(a)分別是典型樹狀河系和非典型樹狀河系的Stroke特征約束方法一級主流識別結(jié)果，圖5(b)、圖6(b)分別是典型樹狀河系和非典型樹狀河系的多準則決策方法一級主流識別結(jié)果，圖5(c)、圖6(c)分別為典型樹狀河系和非典型樹狀河系的本文方法分級結(jié)果，其中藍色線條為一級主流。

為進一步驗證本文方法對復(fù)雜樹狀河系的分級效果，選用樹狀河系3(某流域全部樹狀河系，共擁有424個河段，如圖7所示)進行分級試驗，分級結(jié)果如圖8所示。

由主流識別結(jié)果可以看出：

(1)Stroke特征約束方法通過長度優(yōu)先性和方向一致性來確定主流，僅考慮上游河段的局部幾何特征，而忽略了河流的整體結(jié)構(gòu)特征，導(dǎo)致其主流識別趨向于局部的長度最大和方向一致。在典型樹狀河系和非典型樹狀河系中都存在有將較長的支流河段誤分類為主流河段的情況，其主流識別結(jié)果并不符合主流擁有最多、最復(fù)雜的支流的整體結(jié)構(gòu)特征。

圖4 河系1和河系2分級試驗數(shù)據(jù)Fig.4 River network 1&2 experimental data

表4 部分計算過程及數(shù)值Tab.4 Examples of calculation process and values

圖5 典型樹狀河系的不同方法試驗結(jié)果Fig.5 Results of different methods(atypical tree-like river network)

圖6 非典型樹狀河系的不同方法試驗結(jié)果Fig.6 Results of different methods(atypical tree-like river network)

圖7 河系3試驗數(shù)據(jù)Fig.7 River network 3 experimental data

圖8 河系3的分級試驗結(jié)果Fig.8 Classification result of river network 3

(2)多準則決策方法僅包含長度、角度、支流數(shù)3項指標，沒有考慮到最大河流長度、上游河源數(shù)等反映整體結(jié)構(gòu)特征的指標，導(dǎo)致其主流識別結(jié)果在復(fù)雜情況下容易出現(xiàn)判斷錯誤，尤其是對于主流與支流差異較小的非典型樹狀河系時誤分類現(xiàn)象較為明顯。且該方法識別每一級主流時都需要遍歷河系全部河流造成計算開銷較大，主流識別效率較低。

(3)本文方法的主流識別結(jié)果則有效兼顧了長度最大、角度最平緩和支流最多的主流特征，識別效果較上述方法更好，在典型樹狀河系、較為復(fù)雜的非典型樹狀河系和更為復(fù)雜的整幅流域河系中都能正確識別主支流，分類后所得主流的主流特征明顯，與人工識別結(jié)果較為一致。

由分級結(jié)果可以看出：由于主支流識別合理，本文對于典型樹狀河系和非典型樹狀河系的自動分級方法都取得了良好的效果，河系層次結(jié)構(gòu)合理，各級主流等級關(guān)系分明，父子關(guān)系和左右支關(guān)系清晰，滿足制圖要求。

經(jīng)分析總結(jié)，本文樹狀河系自動分級方法的特點如下：

(1)本文使用語義一致性、匯入角度、河段長度、河段分叉數(shù)、最大河流長度和上游河源數(shù)6項指標來描述河段的主流特征，兼顧了局部幾何特征和整體結(jié)構(gòu)特征，使NBC分類模型能更好地識別出主流河段。

(2)本文方法基于案例學(xué)習(xí)，采用了樸素貝葉斯的機器學(xué)習(xí)方法對從已有分級成果中獲取的主支流案例進行訓(xùn)練，較好地利用了專家分級經(jīng)驗和知識，有效解決了多指標綜合評價的權(quán)重設(shè)定模糊問題，提高了河系分級的智能化和知識化水平。

(3)本文方法具有較強的學(xué)習(xí)能力，隨著案例樣本數(shù)據(jù)質(zhì)量和數(shù)量的增加以及對河段主流特征的屬性描述項的完善，本文方法將會進一步提升獲取主支流分類的綜合知識的質(zhì)量和數(shù)量，從而提高對河段的主支流分類性能，實現(xiàn)更好的分級效果。

5 結(jié) 論

本文提出了一種基于樸素貝葉斯的樹狀河系自動分級方法，通過對上游河段分類為主流類別的概率來確定主流河段。首先從已有分級成果中獲取主支流案例，案例特征項對河段的主流特征描述兼顧了局部幾何特征和整體結(jié)構(gòu)特征，然后使用樸素貝葉斯的機器學(xué)習(xí)方法訓(xùn)練得到NBC分類模型，將待分級河系中的河段自下游向上游進行主支流分類識別，最后完成層次結(jié)構(gòu)化實現(xiàn)自動分級。本文方法NBC分類模型的分類正確率較高，主支流識別結(jié)果有效反映了長度最大、角度最平緩和支流最多的主流特征，較好地還原了專家意圖，分級結(jié)果等級清晰，層次分明。整個分級過程實現(xiàn)了河系分級知識由專家分級成果至專家主支流案例再到主支流分類NBC分類模型的有效獲取和表達，提高了樹狀河系分級的智能化和知識化水平。

本文進一步的研究工作是：對河系中河流方向錯誤的自動判別方法研究；結(jié)合圖論等數(shù)學(xué)方法繼續(xù)挖掘更能反映主流特征的主支流案例特征項和獲取更多高質(zhì)量主支流案例以增強NBC分類模型的分類性能。