謝麗敏，錢海忠，何海威，劉 闖，段佩祥

1.信息工程大學(xué)地理空間信息學(xué)院，河南 鄭州 450052；2.31009部隊(duì)，北京 100088

基于案例推理的居民地選取方法

謝麗敏1，錢海忠1，何海威1，劉 闖2，段佩祥1

1.信息工程大學(xué)地理空間信息學(xué)院，河南 鄭州 450052；2.31009部隊(duì)，北京 100088

針對(duì)當(dāng)前中小比例尺地圖中居民地選取面臨的專家制圖經(jīng)驗(yàn)難以形式化表達(dá)的問題，提出一種基于案例推理的居民地選取方法。首先，把制圖專家對(duì)居民地交互選取結(jié)果作為案例對(duì)象，挖掘居民地案例的屬性特征指標(biāo)，對(duì)屬性賦值和歸一化處理；然后，采用逐步消元法對(duì)居民地最佳屬性組合進(jìn)行選擇，并構(gòu)建源案例庫(kù)；最后，采用案例推理方法，結(jié)合KNN算法，訓(xùn)練案例庫(kù)確定KNN算法的最佳K值，將新案例與源案例庫(kù)檢索匹配，得出最佳決策結(jié)果，進(jìn)而指導(dǎo)待決策居民地的自動(dòng)選取。經(jīng)試驗(yàn)驗(yàn)證，該方法能夠較好地還原專家的選取意向，具有較好的抗噪聲能力，在面狀居民地自動(dòng)選取中取得了較好的效果。

KNN算法；案例推理；居民地選??；專家經(jīng)驗(yàn)

居民地是地形圖的重要要素之一[1]，其數(shù)量和分布有助于判斷地區(qū)的自然條件、土地利用、政治經(jīng)濟(jì)和文化發(fā)展等狀況。而面狀居民地又是中小比例尺地形圖上居民地的一種重要的表達(dá)形式[2]。隨著比例尺的減小，受地圖表達(dá)的限制，需要對(duì)居民地進(jìn)行選取操作。可以說，居民地選取質(zhì)量的好壞直接影響著地圖的科學(xué)性和使用價(jià)值[3]。

目前居民地選取方法主要分為兩類：一是純粹的數(shù)學(xué)和模型算法，如基于遺傳算法的選取方法[4]、基于Circle原理的選取方法[5]、基于Kohonen的選取方法[6]、基于Voronoi圖的選取方法[7]、基于屬性權(quán)重模型的選取方法[8-9]等；二是智能化的方法，即基于知識(shí)的方法，如專家系統(tǒng)[10]、基于規(guī)則推理[11]等。居民地的選取主觀性較強(qiáng)，選取的思維過程是模糊的、不確定的，難以形式化表達(dá)為精確的自動(dòng)選取模型[12]，尤其是對(duì)面狀居民地的選取。因此，第1類建立精確模型的方法對(duì)于單一分布的點(diǎn)群選取效果較好，但對(duì)于環(huán)境稍復(fù)雜的面狀居民地選取適用性較弱。從理論上講要解決居民地自動(dòng)選取的問題，應(yīng)該從智能化方法上尋找突破口。第2類方法中，傳統(tǒng)的制圖綜合專家系統(tǒng)和基于規(guī)則推理的方法，受到知識(shí)獲取瓶頸的制約，一直難以有效地應(yīng)用[13-14]。但也有一些實(shí)質(zhì)性成果面世，文獻(xiàn)[15—16]提出了基于案例類比推理和基于決策樹的道路網(wǎng)智能選取方法，計(jì)算機(jī)通過對(duì)專家選取案例的學(xué)習(xí)進(jìn)行相似道路網(wǎng)的自動(dòng)選取，該方法某種程度上突破了知識(shí)獲取與形式化表達(dá)的瓶頸。

上述研究極大地推動(dòng)了居民地選取的發(fā)展，但進(jìn)一步研究發(fā)現(xiàn)，居民地選取方法還存在以下幾個(gè)問題：①基于算法和模型的方法暫時(shí)無法形式化反映專家在居民地選取過程中復(fù)雜的思維過程；②文獻(xiàn)[15]中基于案例類比的方法中案例匹配機(jī)制研究得還不夠深入，且在靈活性等方面還有較大提升空間；③文獻(xiàn)[16]中方法在案例較少時(shí)難以構(gòu)建決策樹，易受噪聲影響。

針對(duì)以上不足，本文沿用案例類比的思想，結(jié)合KNN算法進(jìn)行居民地的案例類比選取。首先把制圖專家對(duì)居民地交互選取結(jié)果作為案例對(duì)象，采用三元法對(duì)其進(jìn)行描述、屬性賦值以及歸一化處理后構(gòu)建源案例庫(kù)；然后采用逐步消元法對(duì)居民地最佳屬性組合進(jìn)行選擇判定，并訓(xùn)練數(shù)據(jù)確定KNN算法的最佳K值；最后，基于案例推理方法，結(jié)合KNN算法，將新案例與源案例庫(kù)檢索匹配，得出決策結(jié)果，進(jìn)而指導(dǎo)居民地的自動(dòng)選取，達(dá)到學(xué)習(xí)專家綜合知識(shí)并模仿專家綜合結(jié)果的目的，同時(shí)在一定程度上使得選取結(jié)果更加符合人類的認(rèn)知習(xí)慣，增強(qiáng)地圖的可讀性。

1 案例推理和KNN算法原理

1.1 案例推理基本原理

長(zhǎng)期以來，制圖專家知識(shí)的表達(dá)一直是制約制圖綜合發(fā)展的瓶頸[17]。這是因?yàn)閷＜以谶M(jìn)行交互式綜合時(shí)，除了有顯性的制圖綜合規(guī)則外，還隱性包含了制圖專家自身的制圖經(jīng)驗(yàn)，難以形式化表達(dá)?；诎咐评鞢BR(case-based reasoning)符合制圖者的心理認(rèn)知過程，如圖1所示。具體是指在進(jìn)行問題求解時(shí)，使用以前求解類似問題的經(jīng)驗(yàn)和獲取的知識(shí)來推理，并且將新獲取的知識(shí)形成新的案例加入到案例庫(kù)中去，從而通過不斷充實(shí)案例庫(kù)來豐富系統(tǒng)的經(jīng)驗(yàn)[18]。

圖1 一般的CBR模型Fig.1 General CBR model

CBR基于以下兩條原則：①相似的問題有相似的解決方法；②同類的問題會(huì)再次發(fā)生[17]。這與制圖綜合的情況相符合。與基于模型推理和基于規(guī)則推理相比，案例推理降低了知識(shí)的獲取難度，簡(jiǎn)化了問題的求解途徑，提高了推理的制圖效率，不需要得出像規(guī)則那樣準(zhǔn)確和抽象的知識(shí)，而是直接使用隱含的難以提取規(guī)則的專家案例，且以獲取新案例的方式實(shí)現(xiàn)自學(xué)習(xí)，系統(tǒng)維護(hù)簡(jiǎn)單。

1.2 KNN算法基本思想

KNN是基于統(tǒng)計(jì)模式的有監(jiān)督學(xué)習(xí)的類比算法[19]，其核心思想是：首先對(duì)整個(gè)案例庫(kù)檢索，逐個(gè)進(jìn)行計(jì)算，算出待求解的目標(biāo)案例與案例庫(kù)中的源案例之間的相似度，然后選擇K個(gè)相似度高的源案例，依次統(tǒng)計(jì)出這K個(gè)案例對(duì)象的所屬類別，找出包含最多個(gè)數(shù)的類別作為案例分類決策的結(jié)果[20]。

KNN在居民地案例推理中具體定義如下：

定義1：專家選取居民地案例集合X：X={X1,X2,…,Xn}，其中Xi是集合X中第i個(gè)居民地案例，n為居民地案例的總個(gè)數(shù)。

定義2：待決策居民地案例集合Y：Y={Y1,Y2,…,Yn}，其中Yi是集合Y中第i個(gè)居民地案例，n為居民地案例的總個(gè)數(shù)。

定義3：專家選取居民地案例Xi={ai1,ai2,…air,…,aim},其中air為專家選取居民地案例Xi的第r個(gè)屬性，m為每個(gè)案例的屬性總個(gè)數(shù)。

定義4：待決策居民地案例Yj={bj1,bj2,…bir,…,bjm},其中bjr為待決策案例Yi的第r個(gè)屬性，m為每個(gè)案例的屬性個(gè)數(shù)。

定義5：待決策居民地案例Yj與專家選取居民地案例Xi之間的相似值的計(jì)算采用歐氏距離表達(dá)，即公式

(1)

定義6：待決策居民地案例Yj的K個(gè)最近鄰對(duì)象集合

Uk={Xi|Xi∈X,D(Xi,Yj)≤MAXK,

i∈{1,2,3,…,n}}

式中，MAXk表示待決策居民地案例Yj與所有專家選取居民地案例相似度按從小到大排序的第K個(gè)距離值。

KNN算法直觀，易于實(shí)現(xiàn)，且在案例較少時(shí)也能做出決策。與泛化案例構(gòu)建案例庫(kù)的簡(jiǎn)單類比推理和采用決策樹提取隱含規(guī)則方法相比，KNN算法不需要產(chǎn)生額外的數(shù)據(jù)來描述規(guī)則，它的規(guī)則就是案例本身。它并不嚴(yán)格要求數(shù)據(jù)的一致性，在一定程度上允許存在噪聲。噪聲數(shù)據(jù)是指制圖專家由于疲勞、注意力不集中等原因?qū)е碌木用竦剡x取的錯(cuò)誤結(jié)果。這些噪聲數(shù)據(jù)加入案例庫(kù)后，若采用簡(jiǎn)單類比推理和歸納推理等方法的學(xué)習(xí)機(jī)制會(huì)直接影響案例推理的效果。KNN根據(jù)待分類樣本的K個(gè)近鄰樣本來預(yù)測(cè)待分類案例的類別，在一定程度上能有效避免噪聲的影響，從而使案例分類決策更準(zhǔn)確。

2 居民地案例的設(shè)計(jì)與構(gòu)建

2.1 居民地案例的描述

在進(jìn)行基于案例推理時(shí)，首先需要將專家選取結(jié)果轉(zhuǎn)化為專家選取案例。本文采用三元表示法，由制圖綜合案例對(duì)象(Object-O)、特征(Feature-F)以及綜合標(biāo)記(Label-L)組成的一條記錄表示制圖綜合案例。其形式化的表示為

Case:〈O,F,L〉

(2)

式中，案例對(duì)象(O)是指具體操作的居民地對(duì)象，如FID_068、FID_066；特征(F)也稱為描述性項(xiàng)或?qū)傩?，包含居民地自身信息的描述以及通過空間分析獲得的居民地所處的制圖環(huán)境的描述，現(xiàn)總結(jié)6個(gè)居民地屬性指標(biāo)[21-22]，如居民地行政等級(jí)(grade)、居民地面積(area)、鄰近道路等級(jí)(neighbor roads grade，NRG)、最近居民地距離(nearest habitation distance，NHD)、鄰近居民地等級(jí)差(nearest habitation grade difference，NHG)、居民地密度(density)等來反映居民地自身屬性，居民地與居民地之間的關(guān)系以及居民地與其他要素之間的關(guān)系；綜合標(biāo)記(L)是指居民地所處的綜合操作，例如選取(S)、刪除(D)，合并(H)等，其中刪除(D)在案例顯示時(shí)應(yīng)表示為面要素降維到點(diǎn)要素，為方便表示，文中將降維標(biāo)記為刪除，如表1所示。

表1 居民地專家選取結(jié)果示例(部分)Tab.1 Samples of expert selection result on habitation(part)

采用三元描述法，對(duì)專家選取居民地?cái)?shù)據(jù)進(jìn)行統(tǒng)一，確保在進(jìn)行案例匹配時(shí)新的目標(biāo)案例能夠在源案例庫(kù)中匹配到綜合結(jié)果，方便數(shù)據(jù)的檢索、存儲(chǔ)和管理。

2.2 居民地屬性的賦值、歸一化處理

不同變量的量綱不同，為了消除量綱的影響，便于KNN相似度的計(jì)算，需對(duì)居民地屬性賦值并進(jìn)行歸一化處理。居民地屬性類型主要包括兩種：數(shù)值型和字符型。

首先考慮字符型屬性的處理，其中為方便計(jì)算將居民地行政等級(jí)數(shù)值化為4個(gè)等級(jí)，從1到4分別對(duì)應(yīng)市(一級(jí))、區(qū)(二級(jí))、鎮(zhèn)(三級(jí))、村莊(四級(jí))。居民地行政等級(jí)賦值并進(jìn)行歸一化處理，如表2所示：

表2 居民地行政等級(jí)賦值并歸一化處理Tab.2 The result of assignment and normalization processing to executive rank of habitation

對(duì)于數(shù)值型屬性，采用min-max標(biāo)準(zhǔn)化(min-max normalization)使結(jié)果值映射到[0-1]之間。轉(zhuǎn)換函數(shù)如下

(3)

式中，max為樣本屬性數(shù)據(jù)的最大值；min為樣本屬性數(shù)據(jù)的最小值。

對(duì)area、NRG、NRD屬性特征進(jìn)行歸一化處理后結(jié)果如表3所示：

表3 預(yù)處理后的居民地專家選取結(jié)果示例(部分)Tab.3 Samples of pretreatment with expert selection result on habitation(part)

2.3 居民地屬性的篩選

居民地選取本身顧及屬性較多，屬性選擇的判定對(duì)于選取結(jié)果的好壞起到?jīng)Q定性作用，而屬性的選擇與數(shù)據(jù)類型、制圖專家的主觀判斷密切相關(guān)。本文采用逐步消元法解決居民地屬性選取多少和選取哪些的問題，并用十折交叉驗(yàn)證的方法得出分類正確百分比。十折交叉驗(yàn)證是將數(shù)據(jù)集分成10份，輪流將其中9份作為訓(xùn)練數(shù)據(jù)，1份作為測(cè)試數(shù)據(jù)，進(jìn)行試驗(yàn)，得出相應(yīng)的正確率，10次結(jié)果正確率的平均值最終試驗(yàn)結(jié)果[23]。逐步消元法的具體步驟是:首先從訓(xùn)練數(shù)據(jù)完整的屬性集中移除單個(gè)屬性，余下屬性形成一個(gè)屬性子集，對(duì)每個(gè)屬性子集進(jìn)行十折交叉驗(yàn)證，通過對(duì)比分類正確率確定最佳對(duì)象的屬性子集，按照這種方式重復(fù)，即在逐步減少屬性數(shù)量的同時(shí)進(jìn)行十折交叉驗(yàn)證，記錄分類正確的百分比，結(jié)果如表 4所示。

從試驗(yàn)結(jié)果可以看出，當(dāng)屬性個(gè)數(shù)為4且屬性組成為area、grade、NRG、density時(shí)分類正確率最高。由此確定參與決策的屬性，并依此整理專家選取結(jié)果數(shù)據(jù)，構(gòu)建居民地源案例庫(kù)。

表4 不同屬性子集的準(zhǔn)確率統(tǒng)計(jì)Tab.4 Accuracy statistics of different attribute subsets

3 基于KNN算法的居民地案例匹配

基于KNN算法實(shí)現(xiàn)案例匹配的一般步驟為：

(1) 訓(xùn)練數(shù)據(jù)，確定最佳K值。

(2) 根據(jù)距離函數(shù)計(jì)算待分類居民地x與源案例庫(kù)每個(gè)訓(xùn)練樣本的距離，選擇與案例樣本距離最小的K個(gè)樣本作為x的K個(gè)最近鄰。

(3) 根據(jù)K個(gè)最近鄰判斷出x所屬類別。

判斷的依據(jù)是，設(shè)選取(S)個(gè)數(shù)為m，刪除(D)個(gè)數(shù)為n，合并(H)個(gè)數(shù)為p，K=m+n+p，其中函數(shù)max(a,b)為a、b二者最大值：①若m>max(n,p)，則待處理居民地綜合操作結(jié)果為選取(S)；②若n>max(m,p)，則待處理居民地綜合操作結(jié)果為刪除(D)；③若p>max(m,n)，則待處理居民地綜合操作結(jié)果為合并(H)；④若m=n=p，則屬于模糊結(jié)果，交由專家處理，進(jìn)行人工交互判斷，問題解決后與①、②、③決策案例一起存入源案例庫(kù)作為更新案例，實(shí)現(xiàn)案例的自學(xué)習(xí)。

3.1 K值的選擇

KNN算法中K值決定了分類模型的好壞，K值太小會(huì)導(dǎo)致分類精度下降，K值過大會(huì)導(dǎo)致誤差過大從而影響分類的效率[24]。本文采用控制變量法和十折交叉驗(yàn)證訓(xùn)練數(shù)據(jù)樣本，通過查全率(recall)、查準(zhǔn)率(precision)、F1測(cè)度值和分類正確率4個(gè)指標(biāo)來判斷最佳K的取值[23]。評(píng)價(jià)指標(biāo)值越大，說明此時(shí)的K近鄰模型的分類性能越好，案例匹配的精度越高。以選取操作為例公式如下

(4)

(5)

(6)

查全率度量分類器正確預(yù)測(cè)正例的比例，查全率越高，分類的誤判率越低；查準(zhǔn)率確定分類模型為正例的部分記錄中實(shí)際為正例的記錄所占的比例；F1測(cè)度值是查全率和查準(zhǔn)率的調(diào)和均值，即在認(rèn)為二者具有同等重要作用的前提下，將二者結(jié)合為一個(gè)指標(biāo)?，F(xiàn)將訓(xùn)練數(shù)據(jù)(206個(gè)案例)中不同K值試驗(yàn)結(jié)果如表5所示:

表5訓(xùn)練數(shù)據(jù)中不同K值推理結(jié)果統(tǒng)計(jì)
Tab.5ThestatisticsofinferenceresultsofdifferentKvaluefortrainingdata

K值大小查全率(R)查準(zhǔn)率(P)F1測(cè)度值分類正確率/(%)K=10．8990．8990．89989．90K=20．8990．90．89589．90K=30．9090．9080．90890．88K=40．9120．9130．91091．20K=50．9020．9010．90290．23K=60．8990．8980．89889．90K=70．9060．9050．90590．55K=80．9090．9080．90890．88

由推理結(jié)果可以看出，當(dāng)訓(xùn)練樣本個(gè)數(shù)為206，K=4時(shí)，采用KNN算法進(jìn)行案例分類正確率最高。

3.2 最佳K值的確定

文獻(xiàn)[25]研究發(fā)現(xiàn)最佳K值一定程度上與案例的規(guī)模存在關(guān)聯(lián)，即K取訓(xùn)練樣本的2%時(shí)可以取得的分類效果最好。為了進(jìn)一步探尋本文居民地選取案例類比推理最佳K值的選擇與案例庫(kù)規(guī)模的關(guān)系，本文采取不同的K值對(duì)其應(yīng)用效果進(jìn)行了大量的測(cè)試，并采用不同的案例個(gè)數(shù)進(jìn)行驗(yàn)證，依據(jù)3.1節(jié)提供的方法，依次確定每組訓(xùn)練數(shù)據(jù)的最佳K值，試驗(yàn)結(jié)果如表6所示。

表6不同訓(xùn)練數(shù)據(jù)最佳K值統(tǒng)計(jì)
Tab.6StatisticsofthebestKvaluefordifferenttrainingdata

分析試驗(yàn)結(jié)果發(fā)現(xiàn)，針對(duì)當(dāng)前居民地?cái)?shù)據(jù)，最佳K值與案例樣本的總數(shù)確實(shí)存在一定的相關(guān)關(guān)系，驗(yàn)證了文獻(xiàn)[24]的結(jié)論，即K取訓(xùn)練樣本的2%時(shí)可以取得的分類效果最好。

4 試驗(yàn)與分析

4.1 試驗(yàn)流程

因大比例尺地圖中居民地綜合面臨的算子較多，如選取、合并、典型化、融合、位移等，本文暫不予以考慮。本文主要針對(duì)中小比例尺面狀居民地?cái)?shù)據(jù)，采用基于KNN算法和案例推理進(jìn)行居民地選取，其基本步驟與流程如圖2所示。

圖2 基于KNN與案例推理的居民地選取技術(shù)路線Fig.2 The technology route of habitation selection based on KNN and CBR

圖2所示技術(shù)路線圖中主要包括以下5個(gè)步驟：

(1) 專家案例描述。對(duì)制圖專家的居民地選取結(jié)果通過三元法進(jìn)行結(jié)構(gòu)化描述，構(gòu)建專家選取居民地案例。

(2) 數(shù)值轉(zhuǎn)換。將居民地案例輸入，對(duì)案例進(jìn)行屬性賦值、歸一化等數(shù)值轉(zhuǎn)換處理。

(3) 案例屬性篩選。采用逐步消元法，確定參與決策的最佳屬性組合。構(gòu)建格式統(tǒng)一的源案例庫(kù)。

(4) 案例匹配。訓(xùn)練數(shù)據(jù)，確定最佳K值，啟動(dòng)類比推理和KNN檢索機(jī)制，將每個(gè)待處理居民地案例與源案例庫(kù)中的案例進(jìn)行匹配，根據(jù)匹配結(jié)果得出解決方案，并依據(jù)解決方案指導(dǎo)居民地的選取。

(5) 人工處理。若KNN檢索中判斷案例類別個(gè)數(shù)相等，此時(shí)機(jī)器無法做出判決，需進(jìn)行人工處理。將人工處理后的居民地?cái)?shù)據(jù)源與成功匹配的居民地?cái)?shù)據(jù)一起作為新案例加入到源案例庫(kù)中。

4.2 試驗(yàn)與分析

為了驗(yàn)證本文提出的居民地智能選取方法的有效性和優(yōu)勢(shì)性，利用居民地?cái)?shù)據(jù)進(jìn)行了相關(guān)試驗(yàn)。依據(jù)流程設(shè)計(jì)試驗(yàn)如下：以綜合的比例尺為1∶10萬至1∶20萬，北京及其周邊602個(gè)專家交互選取居民地作為源案例庫(kù)，如圖3所示。

圖3 專家案例數(shù)據(jù)示例Fig.3 Example of expert cases data

將制圖環(huán)境相似的涿州市附近150個(gè)居民地作為試驗(yàn)案例，部分如圖4所示。數(shù)據(jù)預(yù)處理完成后，進(jìn)行試驗(yàn)案例與源案例庫(kù)的KNN檢索匹配，依據(jù)3.2節(jié)的結(jié)論可知，此時(shí)最佳K值為12。圖5為KNN試驗(yàn)自動(dòng)綜合的結(jié)果，專家交互選取結(jié)果如圖6所示。圖中居民地選取的對(duì)象標(biāo)記為紅色，刪除居民地對(duì)象標(biāo)記為灰白色，藍(lán)色為合并居民地對(duì)象。從圖中可以看出，圖5與圖6對(duì)應(yīng)居民地顏色大部分一致，即綜合結(jié)果總體相似度很高，只存在少量不一致的情況。

為檢驗(yàn)KNN算法綜合結(jié)果的科學(xué)性和準(zhǔn)確性，對(duì)此方法結(jié)果與圖6專家交互選取結(jié)果進(jìn)行詳細(xì)對(duì)比與分析。為方便比較，僅顯示居民地要素，如圖7、圖8所示，相關(guān)數(shù)據(jù)統(tǒng)計(jì)見表7。

表7測(cè)試數(shù)據(jù)結(jié)果與專家交互選取結(jié)果對(duì)比統(tǒng)計(jì)
Tab.7Thestatisticsofcomparisonresultbetweentestdataandexpertinteractionselectdata

比較項(xiàng)目專家交互選取KNN算法選取個(gè)數(shù)/錯(cuò)誤選取個(gè)數(shù)103/093/10刪除個(gè)數(shù)/錯(cuò)誤刪除個(gè)數(shù)40/037/3合并個(gè)數(shù)/錯(cuò)誤合并個(gè)數(shù)7/04/3選取查全率R1/(%)10090．29刪除查全率R2/(%)10092．5合并查全率R3/(%)10057．14有效決策率/(%)100100決策正確率/(%)10089．33

分析試驗(yàn)對(duì)比結(jié)果可知，與專家交互選取結(jié)果相比，采用基于KNN的案例推理方法綜合后的居民地基本上保持了其分布特征，取得了較好的綜合效果。在復(fù)雜的制圖環(huán)境下，決策正確率達(dá)89.33%，且忠于專家經(jīng)驗(yàn)，很大程度上還原了專家的制圖水平。僅存在極少量與專家選取不一致的綜合結(jié)果，部分如圖7、圖8箭頭所示，進(jìn)一步分析發(fā)現(xiàn)該部分居民地處在專家判斷標(biāo)準(zhǔn)的邊緣，存在不可避免的模糊性，導(dǎo)致錯(cuò)誤的產(chǎn)生。

進(jìn)一步研究發(fā)現(xiàn)，基于案例推理的居民地選取效果高度依賴源案例庫(kù)數(shù)據(jù)的質(zhì)量。制圖專家對(duì)居民地交互選取過程中，由于疲勞、注意力不集中、視覺誤差、操作失誤等原因，會(huì)造成居民地選取的操作結(jié)果出現(xiàn)錯(cuò)誤。這些被稱作噪聲的錯(cuò)誤案例加入到源案例庫(kù)后會(huì)直接影響學(xué)習(xí)效果，最終影響指導(dǎo)解決新任務(wù)的質(zhì)量。本文提出的基于KNN的案例推理方法與依據(jù)案例歸納出規(guī)則的基于決策樹方法相比，抗噪能力更強(qiáng)，在一定程度上能夠允許噪聲的存在，能有效彌補(bǔ)目前案例推理模型在制圖綜合應(yīng)用中抗噪能力弱的缺點(diǎn)。

傳統(tǒng)的決策樹方法中每一個(gè)根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的分枝都是一條由案例演繹歸納得到的規(guī)則，如圖9(a)所示，為無噪聲專家居民地綜合簡(jiǎn)單決策樹示意圖。若加入錯(cuò)誤的案例即噪聲，如：將行政等級(jí)grade為3，面積area為658 956.7 m2的居民地案例由選取錯(cuò)操作為合并，則會(huì)歸納出錯(cuò)誤的規(guī)則，如圖9(b)灰色標(biāo)志決策所示。而案例推理模型是已解決的新問題不斷加入到案例庫(kù)中，這種“滾雪球”式的發(fā)展會(huì)指導(dǎo)更多的案例進(jìn)而造成更多錯(cuò)誤決策。

圖4 試驗(yàn)案例示例(部分)Fig.4 Example of experiment data (part)

圖5 KNN綜合結(jié)果Fig.5 KNN generalization result

而由1.2節(jié)KNN算法基本思想可知，KNN算法是K個(gè)案例參與決策待處理案例結(jié)果，故決策時(shí)個(gè)別噪聲的存在對(duì)判斷結(jié)果影響甚微，即基于KNN的案例推理模型在一定程度上受噪聲案例影響較小。為證明本文算法在抗噪方面的優(yōu)勢(shì)性，設(shè)計(jì)試驗(yàn)在源案例庫(kù)中分別添加不同比例隨機(jī)噪聲進(jìn)行對(duì)比試驗(yàn)，二者決策正確率具體統(tǒng)計(jì)結(jié)果如表8所示，對(duì)比趨勢(shì)圖如圖10所示。

圖6 專家綜合結(jié)果Fig.6 Expert generalization result

圖7 KNN綜合結(jié)果(從圖5提取)Fig.7 KNN generalization result (from Fig.5)

圖8 專家綜合結(jié)果(從圖6提取)Fig.8 Expert generalization result (from Fig.6)

圖9 兩種情況決策樹生成對(duì)比示例Fig.9 Comparison of two cases of decision tree generation

表8 加噪后決策樹與KNN決策正確率結(jié)果統(tǒng)計(jì)Tab.8 The statistics of accuracy results of noised decision tree and KNN (%)

圖10 加噪后決策樹與KNN算法決策正確率結(jié)果趨勢(shì)圖Fig.10 The trend of decision tree and KNN after adding noise

分析試驗(yàn)結(jié)果可知，KNN算法更穩(wěn)定。隨著噪聲數(shù)據(jù)的加入，決策樹方法正確率受影響較大，而使用KNN算法的決策正確率相對(duì)穩(wěn)定，可見KNN算法在隨機(jī)噪聲干擾下魯棒性更強(qiáng)，有效彌補(bǔ)了目前案例推理模型在制圖綜合應(yīng)用中抗噪能力弱的缺點(diǎn)。

5 結(jié) 論

本文提出一種基于KNN案例推理的居民地選取方法，該方法直接以制圖專家對(duì)居民地交互選取結(jié)果作為案例對(duì)象，利用案例類比推理和KNN算法完成了居民地選取從已有專家案例到未知結(jié)果決策的轉(zhuǎn)化，達(dá)到了學(xué)習(xí)專家綜合知識(shí)并模仿專家綜合結(jié)果的目的。本文方法決策正確率高，受噪聲影響相對(duì)較小，有效彌補(bǔ)了目前案例推理模型在制圖綜合應(yīng)用中抗噪能力弱的缺點(diǎn)，且不需要提取規(guī)則；同時(shí)能有效利用專家經(jīng)驗(yàn)，一定程度上降低制圖綜合的難度，為智能化自動(dòng)綜合提供了新思路。

本文案例之間相似度是根據(jù)案例的所有屬性計(jì)算的，KNN計(jì)算時(shí)默認(rèn)每個(gè)屬性的作用都相同，即被賦予相同權(quán)重。如何進(jìn)一步優(yōu)化KNN算法，對(duì)案例屬性合理賦權(quán)值，使得案例推理對(duì)居民地選取結(jié)果準(zhǔn)確率更高，是本文進(jìn)一步的研究方向。

[1] 王家耀.地圖制圖學(xué)與地理信息工程學(xué)科進(jìn)展與成就[M].北京：測(cè)繪出版社，2011.

WANG Jiayao.Advances in Cartography and Geographic Information Engineering[M].Beijing：Surveying and Mapping Press，2011.

[2] 王家耀.普通地圖制圖綜合原理[M].北京：測(cè)繪出版社，1993.

WANG Jiayao.The Principles of General Cartographic Generalization[M].Beijing：Surveying and Mapping Press，1993.

[3] 杜鳳艷.ArcGIS環(huán)境下居民地屬性綜合的研究[D].太原：太原理工大學(xué)，2007.

DU Fengyan.Study on the Attribute Generalization of City Settlements in ArcGIS[D].Taiyuan：Taiyuan University of Technology，2007.

[4] 鄧紅艷，武芳，錢海忠.基于遺傳算法的點(diǎn)群目標(biāo)選取模型[J].中國(guó)圖象圖形學(xué)報(bào)，2003，8(8)：970-976.

DENG Hongyan，WU Fang，QIAN Haizhong.A Model of Point Cluster Selection Based on Genetic Algorithms[J].Journal of Image and Graphics，2003，8(8)：970-976.

[5] 錢海忠，武芳，鄧紅艷.基于CIRCLE特征變換的點(diǎn)群選取算法[J].測(cè)繪科學(xué)，2005，30(3)：83-85.

QIAN Haizhong，WU Fang，DENG Hongyan.A Model of Point Cluster Selection with CIRCLE Characters[J].Science of Surveying and Mapping，2005，30(3)：83-85.

[6] 蔡永香，郭慶勝.基于Kohonen網(wǎng)絡(luò)的點(diǎn)群綜合研究[J].武漢大學(xué)學(xué)報(bào)(信息科學(xué)版)，2007，32(7)：626-629.

CAI Yongxiang，GUO Qingsheng.Points Group Generalization Based on Konhonen Net[J].Geomatics and Information Science of Wuhan University，2007，32(7)：626-629.

[7] 艾廷華，劉耀林.保持空間分布特征的群點(diǎn)化簡(jiǎn)方法[J].測(cè)繪學(xué)報(bào)，2002，31(2)：175-181.

AI Tinghua，LIU Yaolin.A Method of Point Cluster Simplification with Spatial Distribution Properties Preserved[J].Acta Geodaetica et Cartographica Sinica，2002，31(2)：175-181.

[8] 胡慧明，錢海忠，何海威，等.采用層次分析法的面狀居民地自動(dòng)選取[J].測(cè)繪學(xué)報(bào)，2016，45(6)：740-746.DOI：10.11947/j.AGCS.2016.20150078.

HU Huiming，QIAN Haizhong，HE Haiwei，et al.Auto-selection of Areal Habitation Based on Analytic Hierarchy Process[J].Acta Geodaetica et Cartographica Sinica，2016，45(6)：740-746.DOI：10.11947/j.AGCS.2016.20150078.

[9] 胡慧明，錢海忠，何海威，等.采用主成分分析法的面狀居民地自動(dòng)選取[J].測(cè)繪與空間地理信息，2016，39(4)：41-45，49.

HU Huiming，QIAN Haizhong，HE Haiwei,et al.Auto-selection of Areal Habitation Based on Analytic Hierarchy Process[J].Geomatics & Spatial Information Technology，2016，39(4)：41-45，49.

[10] 王光霞.用專家系統(tǒng)技術(shù)實(shí)施居民地自動(dòng)綜合[J].解放軍測(cè)繪學(xué)院學(xué)報(bào)，1996，13(1)：55-59.

WANG Guangxia.The Expert System Method for Inhabited Place Automatic Generalization[J].Journal of Geomatics Science and Technology，1996，13(1)：55-59.

[11] 溫婉麗.基于知識(shí)的居民地地圖自動(dòng)綜合的研究[D].西安：長(zhǎng)安大學(xué)，2006.

WEN Wanli.Map of Residents to Automatic Comprehensive Research Based on the Knowledge[D].Xi’an：Chang’an University，2006.

[12] 錢海忠，武芳，王家耀.自動(dòng)制圖綜合及其過程控制的智能化研究[M].北京：測(cè)繪出版社，2012.

QIAN Haizhong，WU Fang，WANG Jiayao.Study of Automated Cartographic Generalization and Intelligentized Generalization Process Control[M].Beijing：Surveying and Mapping Press，2012.

[13] 武芳，錢海忠，鄧紅艷，等.面向地圖自動(dòng)綜合的空間信息智能處理[M].北京：科學(xué)出版社，2008.

WU Fang，QIAN Haizhong，DENG Hongyan，et al.Intelligent Processing of Spatial Information for Automatic Map Generalization[M].Beijing：Science Press，2008.

[14] RUAS A.Automating the Generalisation of Geographical Data：the Age of Maturity[C]∥Proceedings of the 20th International Cartographic Conference.Beijing：[s.n.]，2001.

[15] 郭敏，錢海忠，黃智深.道路網(wǎng)智能選取的案例類比推理法[J].測(cè)繪學(xué)報(bào)，2014，43(7)：761-770.DOI：10.13485/j.cnki.11-2089.2014.0120.

GUO Min，QIAN Haizhong，HUANG Zhishen.Intelligent Road-network Selection Using Cases Based Reasoning[J].Acta Geodaetica et Cartographica Sinica，2014，43(7)：761-770.DOI：10.13485/j.cnki.11-2089.2014.0120.

[16] 郭敏，錢海忠，黃智深，等.ID3決策樹推理模型及其在道路網(wǎng)選取中的應(yīng)用[J].測(cè)繪科學(xué)技術(shù)學(xué)報(bào)，2012，29(4)：308-312.

GUO Min，QIAN Haizhong，HUANG Zhishen，et al.ID3 Decision Tree Oriented Knowledge Reasoning Model and Its Application in Road Network Selection[J].Journal of Geomatics Science and Technology，2012，29(4)：308-312.

[17] HOLT A.Applying Case-based Reasoning Techniques in GIS[J].International Journal of Geographical Information Science，1999，13(1)：9-25.

[18] AAMODT A，PLAZA E.Case-based Reasoning：Foundational Issues，Methodological Variations，and System Approaches[J].Ai Communications，1994，7(1)：39-59.

[19] 馮銳.基于案例推理的經(jīng)驗(yàn)學(xué)習(xí)[M].上海：華東師范大學(xué)出版社，2012.

FENG Rui.Experiential Learning on Case-based Reasoning[M].Shanghai：East China Normal University Press，2012.

[20] 周偉達(dá).核機(jī)器學(xué)習(xí)方法研究[D].西安：西安電子科技大學(xué)，2003.

ZHOU Weida.Kernel Based Learning Machines[D].Xi’an：Xidian University，2003.

[21] 王家耀，姚杰.模糊綜合評(píng)判在制圖綜合中的應(yīng)用(以居民地選取為例)[J].測(cè)繪學(xué)院學(xué)報(bào)，1985，(2)：47-54.

WANG Jiayao，YAO Jie.An Application of Fuzzy Comprehensive Estimation in Cartographic Generalization[J].Journal of the Institute of Surveying and Mapping，1985，(2)：47-54.

[22] 胡慧明.基于層次結(jié)構(gòu)模型的居民地自動(dòng)選取方法研究[D].鄭州：信息工程大學(xué)，2016.

HUI Huiming.Research on Automatic Habitation Selection Method Based on Hierarchical Structure Model[D].Zhengzhou：Information Engineering University，2016.

[23] 袁梅宇.數(shù)據(jù)挖掘與機(jī)器學(xué)習(xí)——WEKA應(yīng)用技術(shù)與實(shí)踐[M].北京：清華大學(xué)出版社，2014.

YUAN Meiyu.Data Mining and Machine Learning:WEKA Application Technology and Practice[M].Beijing：Tsinghua University Press，2014.

[24] 嚴(yán)愛軍，錢麗敏，王普.案例推理屬性權(quán)重的分配模型比較研究[J].自動(dòng)化學(xué)報(bào)，2014，40(9)：1896-1902.

YAN Aijun，QIAN Limin，WANG Pu.A Comparative Study of Attribute Weights Assignment for Case-based Reasoning[J].Acta Automatica Sinica，2014，40(9)：1896-1902.

[25] 于瑞萍.中文文本分類相關(guān)算法的研究與實(shí)現(xiàn)[D].西安：西北大學(xué)，2007.

YU Ruiping.Research and Implement on the Related Algorithms of Chinese Text Classification[D].Xi’an：Northwest University，2007.

A Habitation Selection Method by Using Case-based Reasoning

XIE Limin1,QIAN Haizhong1,HE Haiwei1,LIU Chuang2,DUAN Peixiang1

1.Institute of Geospatial Information, Information Engineering University, Zhengzhou 450052, China；2.31009 Troop， Beijing 100088, China

Aiming at the problem that the experience of expert in small and medium scale maps is difficult to be expressed in the habitation selection, this paper puts forward a method based on KNN and case-based reasoning on the habitation selection.First of all, the experts selection result on the habitation as cases.Mining habitation property attribute of cases , attribute assignment and the normalization before construction of source database; then, the method of stepwise elimination is used to select the best attribute combination, and training data to determine the optimal K value of KNN algorithm; finally, combined CBR and KNN algorithm to match the new case with the source case library, and get decision result to guide the automatic selection of habitation.The experimental results show that the proposed method can reduce the selection intention of experts, and has better noise immunity.It achieved a good result in the automatic selection of areal habitation.

KNN algorithm; case-based reasoning(CBR); habitation selection; expert experience

The National Natural Science Foundation of China (Nos.41571442；41171305)

XIE Limin(1991—),female,postgraduate，majors in map automatic generalization and spatial data mining.

QIAN Haizhong

謝麗敏，錢海忠，何海威，等.基于案例推理的居民地選取方法[J].測(cè)繪學(xué)報(bào)，2017,46(11)：1910-1918.

10.11947/j.AGCS.2017.20170061.

XIE Limin,QIAN Haizhong,HE Haiwei,et al.A Habitation Selection Method by Using Case-based Reasoning[J].Acta Geodaetica et Cartographica Sinica,2017,46(11):1910-1918.DOI:10.11947/j.AGCS.2017.20170061.

P208

A

1001-1595(2017)11-1910-09

國(guó)家自然科學(xué)基金(41571442；41171305)

(責(zé)任編輯：宋啟凡)

2017-02-09

修回日期：2017-09-01

謝麗敏(1991—)，女，碩士生，研究方向?yàn)榈貓D自動(dòng)綜合、空間數(shù)據(jù)挖掘。

E-mail：gis_xlm@163.com

錢海忠

E-mail：qianhaizhong2005@163.com