田 晶，艾廷華，丁紹軍

武漢大學資源與環(huán)境科學學院地理信息系統(tǒng)教育部重點實驗室，湖北武漢430079

基于C4.5算法的道路網(wǎng)網(wǎng)格模式識別

田 晶，艾廷華，丁紹軍

武漢大學資源與環(huán)境科學學院地理信息系統(tǒng)教育部重點實驗室，湖北武漢430079

提出一種基于C4.5算法的網(wǎng)格模式識別方法。該方法以道路網(wǎng)中的網(wǎng)眼為基本單元，根據(jù)上下文關(guān)系將其標識為屬于網(wǎng)格模式和不屬于網(wǎng)格模式兩類。首先采用形狀參量和關(guān)系參量描述網(wǎng)眼，然后，基于決策樹C4.5算法分別對5參量描述和3參量描述數(shù)據(jù)構(gòu)造分類器，運用10折交叉驗證獲得具有說服力的結(jié)果，其Kappa值分別為0.63和0.66，正確率分別為81.7%和82.9%，置信度90%的置信區(qū)間分別為［0.785，0.846］和［0.797，0.857］。在新數(shù)據(jù)上進行了識別效果的驗證，結(jié)果表明該分類器可用于網(wǎng)格模式的識別。

道路網(wǎng)；網(wǎng)格模式；模式識別；C4.5算法

1 引 言

道路是GIS中的核心要素類型，它構(gòu)成了城市的結(jié)構(gòu)框架，是城市意象的主要組織元素。道路網(wǎng)的模式反映了道路的分布特點，蘊涵著特定歷史時期的政治、經(jīng)濟和文化特征。地圖綜合的智能化研究是地圖制圖學與地理信息工程學科的發(fā)展趨勢［1］，空間模式的識別是地圖綜合朝著智能化方向發(fā)展的關(guān)鍵問題［2］。道路選取是一種地圖綜合方法，隨著地圖比例尺的縮小，道路網(wǎng)密度加大，應(yīng)對道路進行選取，保留重要的道路，舍去次要的道路。道路選取應(yīng)保持道路網(wǎng)的結(jié)構(gòu)特征，文獻［3］強調(diào)應(yīng)將道路網(wǎng)的模式作為道路選取算法的參數(shù)。文獻［4］基于網(wǎng)眼密度進行道路選取也是為了在密度這個層面保持道路網(wǎng)選取前后的分布模式。

網(wǎng)格模式是道路網(wǎng)中的典型模式。對于網(wǎng)格模式的識別，已提出了兩種方法。文獻［5—6］以連通度為4的道路交叉點為起點，搜索包含該節(jié)點的網(wǎng)眼，然后通過其中一個網(wǎng)眼，尋找符合質(zhì)心排列一致的鄰近網(wǎng)眼，綜合考慮網(wǎng)眼間的相似性，完成網(wǎng)格的識別，該方法簡單高效，但對于連通度不為4的復雜道路交叉點在處理上存在困難。文獻［7］將相鄰網(wǎng)眼排列一致性、相鄰網(wǎng)眼形狀相似性、網(wǎng)眼自身形狀指標集成為一個參數(shù)，根據(jù)該參數(shù)搜索鄰近網(wǎng)眼，完成網(wǎng)格模式的識別，參數(shù)的閾值可以人為設(shè)定，以達到自適應(yīng)的效果，該方法克服了文獻［5］中的方法不能從復雜節(jié)點識別網(wǎng)格的局限。上述兩種方法均是根據(jù)網(wǎng)眼的屬性搜索相鄰網(wǎng)眼，其基本思想是利用網(wǎng)眼屬性導出一個網(wǎng)眼與其相鄰網(wǎng)眼是否構(gòu)成網(wǎng)格的程度參數(shù)。

筆者換一種思路，將網(wǎng)格模式的識別看做是考慮上下文關(guān)系的分類任務(wù)。其理由是：網(wǎng)格模式由一系列形狀和尺寸相似并滿足特定的排列方式的網(wǎng)眼多邊形構(gòu)成，構(gòu)成網(wǎng)格模式的網(wǎng)眼多邊形與其他多邊形具有不同的特征，所以可以將多邊形分為構(gòu)成網(wǎng)格模式和不構(gòu)成網(wǎng)格模式兩類。值得強調(diào)的是，群目標的模式識別與單個目標的識別有所區(qū)別，它更關(guān)心整體的分布態(tài)勢。例如，在網(wǎng)格模式中，有一兩個“壞”的網(wǎng)眼多邊形，在人的肉眼判斷上不會對網(wǎng)格模式構(gòu)成影響，而那一兩個“壞”的網(wǎng)眼將在這種上下文關(guān)系下被識別為屬于網(wǎng)格模式。

運用分類思想進行網(wǎng)格模式的識別需要回答以下3個基本問題：① 運用哪些屬性參量描述道路網(wǎng)中的多邊形網(wǎng)眼，這些屬性參量對于分類的作用如何；② 運用何種算法去構(gòu)造分類器，其適宜性表現(xiàn)在哪些方面；③ 分類器的性能如何，能否將其應(yīng)用于新的數(shù)據(jù)。

本文提出一種基于C4.5算法的網(wǎng)格模式識別方法，對上述3個基本問題進行回答。與已有網(wǎng)格模式識別方法的顯著區(qū)別在于它是一種基于分類思想的方法，與傳統(tǒng)的模式識別和數(shù)據(jù)挖掘?qū)W科聯(lián)系緊密，強調(diào)將模式識別與數(shù)據(jù)挖掘的理論與方法融入到空間問題的解決中。

2 網(wǎng)眼多邊形的屬性參量定義與初步分析

2.1 參量定義

網(wǎng)眼多邊形屬性參量主要從自身的形狀、與周圍網(wǎng)眼的排列關(guān)系以及相似關(guān)系方面定義。下面介紹參量的定義與計算方法，如表1。下述參量與尺度無關(guān)，參量值的大小具有絕對性。

表1 網(wǎng)眼參量Tab.1 Mesh’s measure

2.2 參量的初步分析

箱須圖（box－whisker plot）是用于描述數(shù)據(jù)分布的統(tǒng)計圖形，它表示參量的最小值、第1四分位數(shù)、中位數(shù)、第3四分位數(shù)和最大值，利用它可以從視覺角度觀察參量值的分布情況。整個箱圖中最上方和最下方的線段分別表示數(shù)據(jù)的最大值和最小值，對于箱來說，其上下兩端的線段分別表示第3四分位數(shù)和第1四分位數(shù)，中間的粗線段表示數(shù)據(jù)的中位數(shù)，“o”標出溫和的異常值，“＊”標出極端的異常值。箱須圖常用于觀察數(shù)據(jù)的分布、識別數(shù)據(jù)中的異常值，但文獻［10］應(yīng)用箱須圖初步估計每個參量對類的可分性。圖1是由武漢市部分道路網(wǎng)構(gòu)成的427個網(wǎng)眼生成的關(guān)于上述5個參量的箱須圖。該圖由SPSS軟件生成、版本號16.0。每個箱須圖左端是參量名稱，下端是是否屬于網(wǎng)格的標識（IsGrid），yes代表屬于，no代表不屬于。從中可以觀察出凹凸度（C）和周圍排列度最大的網(wǎng)眼的凹凸度（CMHLCAD）的一維參量類可分性較差，排列一致度（CAD）的類可分性較好。受文獻［10］的啟發(fā)，后文的試驗中將分別采用5參量（R、C、CAD、RMHLCAD、CRMHLCAD）和3參量（R、CAD、RMHLCAD）進行試驗。

圖1 由427個網(wǎng)眼生成的5個參量的箱須圖Fig.1 Box－whisker plot for five measures calculated from 427meshes

3 基于C4.5算法的網(wǎng)格模式識別方法

3.1 決策樹與C4.5算法

決策樹學習是應(yīng)用最廣的歸納推理算法之一，它是一種逼近離散值函數(shù)的方法，對噪聲數(shù)據(jù)有很好的抗差性且能夠?qū)W習析取表達式。決策樹通過把實例從根節(jié)點排列到某個葉子節(jié)點來分類實例，葉子節(jié)點即為實例所屬的分類。樹上的每一個結(jié)點說明了對實例的某個屬性的測試，并且該節(jié)點的每一個后繼分支對應(yīng)于該屬性的一個可能值。分類實例的方法是從這棵樹的根節(jié)點開始，測試這個節(jié)點所指定的屬性，然后按照給定實例的該屬性值對應(yīng)的樹枝向下移動。然后這個過程在以新節(jié)點為根的子樹上重復。構(gòu)造過程是從“哪一個屬性將在根節(jié)點被測試？”這個問題開始的。分類能力最好的屬性被選作樹的根節(jié)點的測試，然后為根節(jié)點屬性的每個可能值產(chǎn)生一個分支，并把訓練樣例排列到適當?shù)姆种е?。然后重復整個過程，用每個分支節(jié)點關(guān)聯(lián)到訓練樣例來選取在該點被測試的最佳屬性。這形成了貪心搜索，也就是算法從不回溯重新考慮以前的選擇［11］。C4.5算法是著名的決策樹學習算法，詳細的介紹參見文獻［12］。

判別式、神經(jīng)網(wǎng)絡(luò)和決策樹及它們對應(yīng)的算法都可用來構(gòu)造分類器，但本文選用決策樹C4.5算法作為構(gòu)造分類器的方法，原因在于：① 它具有里程碑意義，是目前為止在實踐中應(yīng)用最為廣泛的機器學習工具［13］，在地理信息科學中，有很多研究者采用決策樹ID3算法、C4.5算法及其改進版本C5.0進行問題的解答［14－16］；② 算法輸出的決策樹可以很自然地表示成規(guī)則的形式，易于理解。

3.2 網(wǎng)格模式識別方法

在介紹了參量描述和分類器構(gòu)造算法后，描述基于知識的網(wǎng)格模式的識別方法，方法的基本步驟如下：

（1）數(shù)據(jù)預處理。受文獻［17］研究的啟發(fā)，重復刪除道路網(wǎng)圖中的橋和孤立點。重復刪除的意思是刪除一個橋后，重新檢查剩余的道路網(wǎng)是否還存在橋，如果是的話，繼續(xù)刪除，直到不存在橋和孤立點，對處理完的道路網(wǎng)構(gòu)建多邊形拓撲結(jié)構(gòu)。對于已有線面拓撲關(guān)系的數(shù)據(jù)可以跳過這一步。

（2）對每個網(wǎng)眼多邊形，計算2.1節(jié)定義的參量。

（3）將訓練數(shù)據(jù)標識為屬于網(wǎng)格模式與不屬于網(wǎng)格模式兩類，運用C4.5算法構(gòu)造分類器。

（4）評估分類器性能。

（5）將待識別的道路網(wǎng)數(shù)據(jù)導入，用該分類器進行模式識別。

4 試驗與分析

4.1 試 驗

（1）訓練數(shù)據(jù)：訓練數(shù)據(jù)是武漢市部分道路網(wǎng)構(gòu)成的427個網(wǎng)眼。

（2）試驗環(huán)境與試驗平臺：試驗在Window XP操作環(huán)境下進行，數(shù)據(jù)處理功能和參量計算用Visual C＋＋6.0擴展DoMap平臺開發(fā)完成。運用開源數(shù)據(jù)挖掘軟件Weka進行分類器的構(gòu)造，該軟件的介紹與操作詳見文獻［10］。

（3）試驗結(jié)果評估：在數(shù)據(jù)量有限的情況下為獲得好的結(jié)果，運用10折交叉驗證方法。根據(jù)正確率（正確分類的樣本的比例）和Kappa統(tǒng)計值評價分類精度。

試驗1：對5個參量（R、C、CAD、RMHLCAD、CRMHLCAD）數(shù)據(jù)進行試驗，導出的決策樹如圖2，混淆矩陣如表2。其Kappa統(tǒng)計值為0.63，正確率為81.7%，置信度90%的置信區(qū)間為［0.785，0.846］。

圖2 由5參量描述的訓練數(shù)據(jù)生成的決策樹Fig.2 Decision tree inducted by five measures data

表2 5參量描述數(shù)據(jù)的混淆矩陣Tab.2 Confusion matrix for five measures data

試驗2：根據(jù)2.2節(jié)的參量分析，對3參量（R、CAD、RMHLCAD）數(shù)據(jù)進行訓練。導出的決策樹如圖3，混淆矩陣如表3。其Kappa統(tǒng)計值為0.66，正確率為82.9%，置信度90%的置信區(qū)間［0.797，0.857］。

圖3 由3參量描述的訓練數(shù)據(jù)生成的決策樹Fig.3 Decision tree inducted by three measures data

表3 3參量描述數(shù)據(jù)的混淆矩陣Tab.3 Confusion matrix for three measures data

4.2 分 析

（1）從構(gòu)造的分類器的性能來說，在10折交叉驗證方法下，5參量描述和3參量描述的正確率均大于80%，雖然3參量描述的正確率和Kappa統(tǒng)計值略高于5參量描述，但不能說明可用3參量描述代替5參量描述。

（2）遍歷決策樹中由根節(jié)點到葉節(jié)點的路徑，經(jīng)過提煉（保留葉節(jié)點是yes的規(guī)則，合并某些規(guī)則），得到的規(guī)則如表4。由決策樹導出的規(guī)則易于理解，實現(xiàn)了知識的顯示表達。例如，if（R＞0.81）and（CAD＞0.7）then yes，表達了如果網(wǎng)眼自身矩形度和排列度較大，則該網(wǎng)眼屬于網(wǎng)格模式。

表4 由決策樹導出的規(guī)則Tab.4 Rules derived from decision tree

對于在決策樹中參量的取值是由C4.5算法決定的。例如圖2中，決策樹第一個分支在R上為什么要取0.81，這是因為，對于連續(xù)值，C4.5算法處理過程如下［18］：根據(jù)參量的值，對數(shù)據(jù)集排序；用不用的閾值將數(shù)據(jù)集動態(tài)的進行劃分；當輸出改變時，確定一個閾值；取兩個實際值中的中點作為一個閾值；取兩個劃分，所有樣本都在這兩個劃分中；得到所有可能的閾值以及增益比率；每一個參量會變?yōu)閮蓚€取值。下面舉一個例子：參量A具有連續(xù)值，則在訓練數(shù)樣本中可以按照升序方式排列A的值，如果A共有n種取值，則對每個取值將所有的數(shù)據(jù)進行劃分，針對每個劃分計算信息增益比率，選擇最大的劃分來對相應(yīng)的參量進行離散化。

（3）在新的數(shù)據(jù)上進行方法驗證試驗，數(shù)據(jù)是深圳市道路網(wǎng)的一部分，包含399個網(wǎng)眼，其識別結(jié)果如圖4。其中，灰色填充——僅由3參量描述的訓練數(shù)據(jù)生成的決策樹所導出的規(guī)則的識別結(jié)果；灰色＋暈線——由3參量描述的訓練數(shù)據(jù)生成的決策樹所導出的規(guī)則和由5參量描述的訓練數(shù)據(jù)生成的決策樹所導出的規(guī)則均識別為網(wǎng)格模式的結(jié)果；空白＋暈線——僅由5參量描述的訓練數(shù)據(jù)生成的決策樹所導出的規(guī)則的識別結(jié)果；空白——由本方法判定不屬于網(wǎng)格模式的網(wǎng)眼。由上述兩組規(guī)則分別進行識別的結(jié)果與肉眼識別結(jié)果相似，部分地實現(xiàn)了對某些“壞”網(wǎng)眼的正確識別。

值得一提的有兩點：第一，訓練數(shù)據(jù)與測試數(shù)據(jù)來自不同的城市道路網(wǎng)，不存在用訓練數(shù)據(jù)進行測試所產(chǎn)生的重新帶入誤差（re－substitution error）；第二，不是將同一城市的數(shù)據(jù)分為訓練數(shù)據(jù)和測試數(shù)據(jù)，而是將一個城市的道路網(wǎng)作為訓練數(shù)據(jù)，另一個城市的道路網(wǎng)作為測試數(shù)據(jù)，使得結(jié)果更具說服力，總體上表明本文提出的方法可行。

圖4 深圳數(shù)據(jù)的驗證Fig.4 Validation by Shenzhen data

（4）對圖4的識別結(jié)果進一步分析，發(fā)現(xiàn)其中有些地方不盡如人意，如圖5所舉的3個例子（對應(yīng)于圖4的圈出部分）。究其原因，主要有3點：第一，構(gòu)面對識別結(jié)果的影響，如圖5（a），這是基于網(wǎng)眼的網(wǎng)格模式識別方法的通病，其改進有待于Gestalt原則的應(yīng)用；第二，網(wǎng)眼參量的影響，如圖5（b），矩形度的計算方式使得它對于網(wǎng)眼上小突出很敏感；第三，人為因素的影響，對于較為規(guī)則的情況沒有異議，但對于一些退化較為嚴重的情況，“壞”的網(wǎng)眼是否屬于網(wǎng)格模式那就是仁者見仁，智者見智了，從而導致訓練樣本的類標識不同，直接影響由此得到的分類器的性能，從而影響識別結(jié)果，如圖5（c）所示，如果該圖中的網(wǎng)眼被標識為屬于網(wǎng)格模式，那么根據(jù)監(jiān)督學習的特點，遇到類似情況，它們會將其判斷為屬于網(wǎng)格模式。決策樹的泛化功能取決于樣本的選擇和參量的描述。

圖5 異常情況Fig.5 Exceptional situation

5 結(jié) 論

本文提出一種基于C4.5算法的網(wǎng)格模式識別方法。該方法以道路網(wǎng)中的網(wǎng)眼多邊形為基本單元，將其分為屬于網(wǎng)格模式和不屬于網(wǎng)格模式兩類。采用矩形度、凹凸度、排列一致度、周圍排列度最大的網(wǎng)眼的矩形度、周圍排列度最大的網(wǎng)眼的凹凸度來描述網(wǎng)眼多邊形，然后，基于決策樹C4.5算法分別對5參量描述和3參量描述數(shù)據(jù)構(gòu)造分類器。試驗結(jié)果表明該方法有效，能夠運用于新的數(shù)據(jù)進行網(wǎng)格模式識別。

進一步的研究工作將在以下幾個方面展開：① 組織不同年齡、不同專業(yè)、不同文化背景的人員進行認知試驗，對網(wǎng)眼是否屬于網(wǎng)格模式進行分析；② 網(wǎng)眼多邊形屬性參量的進一步分析與甄選，研究其他一些形狀參量，如緊湊度、延展度等對識別產(chǎn)生的作用；③ 判別式、神經(jīng)網(wǎng)絡(luò)等其他分類器構(gòu)造方法與決策樹方法在分類性能上的比較。

［1］ WANG Jiayao.Development Trends of Cartography and Geographic Information Engineering［J］.Acta Geodaetica et Cartographica Sinica，2010，39（2）：115－119.（王家耀.地圖制圖學與地理信息工程學科發(fā)展趨勢［J］.測繪學報，2010，39（2）：115－119.）

［2］ MACKANESS W，EDWARDS G.The Importance of Modeling Pattern and Structures in Automated Map Generalization［C］∥Proceedings of the Joint ISPRS／ICA Workshop on Multi－scale Representations of Spatial Data.Ottawa：［s.n.］，2002.

［3］ ZHANG Qingnian.Modeling Structure and Patterns in Road Network Generalization［C］∥Proceedings of ICA Workshop on Generalization and Multiple Representation.Leicester：［s.n.］，2004.

［4］ HU Yungang，CHEN Jun，LI Zhilin，et al.Selective Omission of Road Features Based on Mesh Density for Digital Map Generalization［J］.Acta Geodaetica et Cartographica Sinica，2007，36（3）：351－357.（胡云崗，陳軍，李志林，等.基于網(wǎng)眼密度的道路選取方法［J］.測繪學報，2007，36（3）：351－357.）

［5］ HEINZLE F，ANDERS K H，SESTER M.Graph Based Approaches for Recognition of Patterns and Implicit Information in Road Networks［C］∥Proceedings of the 22nd International Cartographic Conference.La Coruna：［s.n.］，2005.

［6］ HEINZLE F，ANDERS K H.Characterising Space via Pattern Recognition Techniques：Identifying Patterns in Road Networks［C］∥Generalisation of Geographic Information：Cartographic Modelling and Applications.［S.l.］：Elsevier Ltd，2007：233－253.

［7］ YANG Bisheng，LUAN Xuechen，LI Qingquan.An Adaptive Method for Identifying the Spatial Patterns in Road Networks［J］.Computers，Environment and Urban Systems，2010，34（1）：40－48.

［8］ ROSIN P L.Measuring Rectangularity［J］.Machine Vision and Application，1999，11（4）：191－196.

［9］ ZUNIC J，ROSIN P L.A New Convexity Measure for Polygons［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2004，26（7）：923－934.

［10］ STEINIGER S，LANGE T，BURGHARDT D，et al.An Approach for the Classification of Urban Building Structures Based on Discriminant Analysis Techniques［J］.Transactions in GIS，2008，12（1）：31－59.

［11］ MITCHELL T M.Machine Learning［M］.ZENG Huajun，ZHANG Yinkui，translation.Beijing：Mechanical Industry Press，2003.（MITCHELL T M.機器學習［M］.曾華軍，張銀奎，譯.北京：機械工業(yè)出版，2003.）

［12］ QUINLAN J R.C4.5：Programs for Machine Learning［M］.San Francisco：Morgan Kaufmann Publishers Inc，1993.

［13］ WITTEN I H，F(xiàn)RANK E.Data Mining：Practical Machine Learning Tools and Techniques［M］.DONG Lin，QIU Quan，YU Xiaofeng，translation.2nd ed.Beijing：Mechanical Industry Press，2005.（WITTEN I H，F(xiàn)RANK E.數(shù)據(jù)挖掘：實用機器學習技術(shù)［M］.董琳，邱泉，于曉峰，譯.第2版.北京：機械工業(yè)出版社，2005.）

［14］ SESTER M.Knowledge Acquisition for the Automatic Interpretation of Spatial Data［J］.International Journal of Geographical Information Science，2000，14（1）：1－24.

［15］ QI F，ZHU A X.Knowledge Discovery from Soil Maps Using Inductive Learning［J］.International Journal of Geographical Information Science，2003，17（8）：771－795.

［16］ MUSTIERE S.Cartographic Generalization of Roads in a Local and Adaptive Approach：a Knowledge Acquisition Problem［J］.International Journal of Geographical Information Science，2005，19（8－9）：937－955.

［17］ XIE F，LEVINSON D.Measuring the Structure of Road Networks［J］.Geographical Analysis，2007，39（3）：336－356.

［18］ MAO Guojun，DUAN Lijuan，WANG Shi，et al.Principles and Algorithms of Data Mining［M］.Beijing：Tsinghua University Press，2005：123.（毛國君，段立娟，王實，等.數(shù)據(jù)挖掘原理與算法［M］.北京：清華大學出版社，2005：123.）

Grid Pattern Recognition in Road Networks Based on C4.5 Algorithm

TIAN Jing，AI Tinghua，DING Shaojun
Key Laboratory of Geographic Information System，School of Resources and Environment Science，Wuhan University，Wuhan 430079，China

A method for grid pattern recognition based on C4.5 algorithm is proposed.Meshes in road networks can be classified as belonging to grid and not belonging to grid according to their context.Firstly，shape measures and relation measures are defined to characterize meshes in road networks.Secondly，two classifiers are trained using C4.5 algorithm based on five measures data and three measures data.A10－fold cross validation process is applied in order to obtain a sounder result.Finally，the performance of the classifiers is evaluated by means of the Kappa index and the overall correct rate.The Kappa classification accuracy for five dimensions data and three dimensions data is 0.63 and0.66.The overall correct rate is 81.7%and82.9%for each.The confidence interval of 90% confidence is［0.785，0.846］and［0.797，0.857］respectively.The classifiers are tested by a new data set and the results show that the classifiers are valid in grid pattern recognition.

road network；grid pattern；pattern recognition；C4.5 algorithm

TIAN Jing（1982—），male，postdoctoral fellow，lecturer，majors in automated map generalization and pattern recognition.

TIAN Jing，AI Tinghua，DING Shaojun.Grid Pattern Recognition in Road Networks Based on C4.5Algorithm［J］.Acta Geodaetica et Cartographica Sinica，2012，41（1）：121－126.（田晶，艾廷華，丁紹軍.基于C4.5算法的道路網(wǎng)網(wǎng)格模式識別［J］.測繪學報，2012，41（1）：121－126.）

P208

A

1001－1595（2012）01－0121－06

中國博士后科學基金（20100480863）；國家863計劃（2009AA121404）；武漢大學自主科研資助項目（111156）

雷秀麗）

2010－12－13

2011－02－23

田晶（1982—），男，博士后，講師，主要從事地圖自動綜合和模式識別的研究。

E－mail：yutaka－2010＠163.com