謝麗敏,錢海忠,何海威,劉 闖,段佩祥
1.信息工程大學(xué)地理空間信息學(xué)院,河南 鄭州 450052;2.31009部隊,北京 100088
基于案例推理的居民地選取方法
謝麗敏1,錢海忠1,何海威1,劉 闖2,段佩祥1
1.信息工程大學(xué)地理空間信息學(xué)院,河南 鄭州 450052;2.31009部隊,北京 100088
針對當前中小比例尺地圖中居民地選取面臨的專家制圖經(jīng)驗難以形式化表達的問題,提出一種基于案例推理的居民地選取方法。首先,把制圖專家對居民地交互選取結(jié)果作為案例對象,挖掘居民地案例的屬性特征指標,對屬性賦值和歸一化處理;然后,采用逐步消元法對居民地最佳屬性組合進行選擇,并構(gòu)建源案例庫;最后,采用案例推理方法,結(jié)合KNN算法,訓(xùn)練案例庫確定KNN算法的最佳K值,將新案例與源案例庫檢索匹配,得出最佳決策結(jié)果,進而指導(dǎo)待決策居民地的自動選取。經(jīng)試驗驗證,該方法能夠較好地還原專家的選取意向,具有較好的抗噪聲能力,在面狀居民地自動選取中取得了較好的效果。
KNN算法;案例推理;居民地選??;專家經(jīng)驗
居民地是地形圖的重要要素之一[1],其數(shù)量和分布有助于判斷地區(qū)的自然條件、土地利用、政治經(jīng)濟和文化發(fā)展等狀況。而面狀居民地又是中小比例尺地形圖上居民地的一種重要的表達形式[2]。隨著比例尺的減小,受地圖表達的限制,需要對居民地進行選取操作。可以說,居民地選取質(zhì)量的好壞直接影響著地圖的科學(xué)性和使用價值[3]。
目前居民地選取方法主要分為兩類:一是純粹的數(shù)學(xué)和模型算法,如基于遺傳算法的選取方法[4]、基于Circle原理的選取方法[5]、基于Kohonen的選取方法[6]、基于Voronoi圖的選取方法[7]、基于屬性權(quán)重模型的選取方法[8-9]等;二是智能化的方法,即基于知識的方法,如專家系統(tǒng)[10]、基于規(guī)則推理[11]等。居民地的選取主觀性較強,選取的思維過程是模糊的、不確定的,難以形式化表達為精確的自動選取模型[12],尤其是對面狀居民地的選取。因此,第1類建立精確模型的方法對于單一分布的點群選取效果較好,但對于環(huán)境稍復(fù)雜的面狀居民地選取適用性較弱。從理論上講要解決居民地自動選取的問題,應(yīng)該從智能化方法上尋找突破口。第2類方法中,傳統(tǒng)的制圖綜合專家系統(tǒng)和基于規(guī)則推理的方法,受到知識獲取瓶頸的制約,一直難以有效地應(yīng)用[13-14]。但也有一些實質(zhì)性成果面世,文獻[15—16]提出了基于案例類比推理和基于決策樹的道路網(wǎng)智能選取方法,計算機通過對專家選取案例的學(xué)習(xí)進行相似道路網(wǎng)的自動選取,該方法某種程度上突破了知識獲取與形式化表達的瓶頸。
上述研究極大地推動了居民地選取的發(fā)展,但進一步研究發(fā)現(xiàn),居民地選取方法還存在以下幾個問題:①基于算法和模型的方法暫時無法形式化反映專家在居民地選取過程中復(fù)雜的思維過程;②文獻[15]中基于案例類比的方法中案例匹配機制研究得還不夠深入,且在靈活性等方面還有較大提升空間;③文獻[16]中方法在案例較少時難以構(gòu)建決策樹,易受噪聲影響。
針對以上不足,本文沿用案例類比的思想,結(jié)合KNN算法進行居民地的案例類比選取。首先把制圖專家對居民地交互選取結(jié)果作為案例對象,采用三元法對其進行描述、屬性賦值以及歸一化處理后構(gòu)建源案例庫;然后采用逐步消元法對居民地最佳屬性組合進行選擇判定,并訓(xùn)練數(shù)據(jù)確定KNN算法的最佳K值;最后,基于案例推理方法,結(jié)合KNN算法,將新案例與源案例庫檢索匹配,得出決策結(jié)果,進而指導(dǎo)居民地的自動選取,達到學(xué)習(xí)專家綜合知識并模仿專家綜合結(jié)果的目的,同時在一定程度上使得選取結(jié)果更加符合人類的認知習(xí)慣,增強地圖的可讀性。
1.1 案例推理基本原理
長期以來,制圖專家知識的表達一直是制約制圖綜合發(fā)展的瓶頸[17]。這是因為專家在進行交互式綜合時,除了有顯性的制圖綜合規(guī)則外,還隱性包含了制圖專家自身的制圖經(jīng)驗,難以形式化表達?;诎咐评鞢BR(case-based reasoning)符合制圖者的心理認知過程,如圖1所示。具體是指在進行問題求解時,使用以前求解類似問題的經(jīng)驗和獲取的知識來推理,并且將新獲取的知識形成新的案例加入到案例庫中去,從而通過不斷充實案例庫來豐富系統(tǒng)的經(jīng)驗[18]。
圖1 一般的CBR模型Fig.1 General CBR model
CBR基于以下兩條原則:①相似的問題有相似的解決方法;②同類的問題會再次發(fā)生[17]。這與制圖綜合的情況相符合。與基于模型推理和基于規(guī)則推理相比,案例推理降低了知識的獲取難度,簡化了問題的求解途徑,提高了推理的制圖效率,不需要得出像規(guī)則那樣準確和抽象的知識,而是直接使用隱含的難以提取規(guī)則的專家案例,且以獲取新案例的方式實現(xiàn)自學(xué)習(xí),系統(tǒng)維護簡單。
1.2 KNN算法基本思想
KNN是基于統(tǒng)計模式的有監(jiān)督學(xué)習(xí)的類比算法[19],其核心思想是:首先對整個案例庫檢索,逐個進行計算,算出待求解的目標案例與案例庫中的源案例之間的相似度,然后選擇K個相似度高的源案例,依次統(tǒng)計出這K個案例對象的所屬類別,找出包含最多個數(shù)的類別作為案例分類決策的結(jié)果[20]。
KNN在居民地案例推理中具體定義如下:
定義1:專家選取居民地案例集合X:X={X1,X2,…,Xn},其中Xi是集合X中第i個居民地案例,n為居民地案例的總個數(shù)。
定義2:待決策居民地案例集合Y:Y={Y1,Y2,…,Yn},其中Yi是集合Y中第i個居民地案例,n為居民地案例的總個數(shù)。
定義3:專家選取居民地案例Xi={ai1,ai2,…air,…,aim},其中air為專家選取居民地案例Xi的第r個屬性,m為每個案例的屬性總個數(shù)。
定義4:待決策居民地案例Yj={bj1,bj2,…bir,…,bjm},其中bjr為待決策案例Yi的第r個屬性,m為每個案例的屬性個數(shù)。
定義5:待決策居民地案例Yj與專家選取居民地案例Xi之間的相似值的計算采用歐氏距離表達,即公式
(1)
定義6:待決策居民地案例Yj的K個最近鄰對象集合
Uk={Xi|Xi∈X,D(Xi,Yj)≤MAXK,
i∈{1,2,3,…,n}}
式中,MAXk表示待決策居民地案例Yj與所有專家選取居民地案例相似度按從小到大排序的第K個距離值。
KNN算法直觀,易于實現(xiàn),且在案例較少時也能做出決策。與泛化案例構(gòu)建案例庫的簡單類比推理和采用決策樹提取隱含規(guī)則方法相比,KNN算法不需要產(chǎn)生額外的數(shù)據(jù)來描述規(guī)則,它的規(guī)則就是案例本身。它并不嚴格要求數(shù)據(jù)的一致性,在一定程度上允許存在噪聲。噪聲數(shù)據(jù)是指制圖專家由于疲勞、注意力不集中等原因?qū)е碌木用竦剡x取的錯誤結(jié)果。這些噪聲數(shù)據(jù)加入案例庫后,若采用簡單類比推理和歸納推理等方法的學(xué)習(xí)機制會直接影響案例推理的效果。KNN根據(jù)待分類樣本的K個近鄰樣本來預(yù)測待分類案例的類別,在一定程度上能有效避免噪聲的影響,從而使案例分類決策更準確。
2.1 居民地案例的描述
在進行基于案例推理時,首先需要將專家選取結(jié)果轉(zhuǎn)化為專家選取案例。本文采用三元表示法,由制圖綜合案例對象(Object-O)、特征(Feature-F)以及綜合標記(Label-L)組成的一條記錄表示制圖綜合案例。其形式化的表示為
Case:〈O,F,L〉
(2)
式中,案例對象(O)是指具體操作的居民地對象,如FID_068、FID_066;特征(F)也稱為描述性項或?qū)傩?,包含居民地自身信息的描述以及通過空間分析獲得的居民地所處的制圖環(huán)境的描述,現(xiàn)總結(jié)6個居民地屬性指標[21-22],如居民地行政等級(grade)、居民地面積(area)、鄰近道路等級(neighbor roads grade,NRG)、最近居民地距離(nearest habitation distance,NHD)、鄰近居民地等級差(nearest habitation grade difference,NHG)、居民地密度(density)等來反映居民地自身屬性,居民地與居民地之間的關(guān)系以及居民地與其他要素之間的關(guān)系;綜合標記(L)是指居民地所處的綜合操作,例如選取(S)、刪除(D),合并(H)等,其中刪除(D)在案例顯示時應(yīng)表示為面要素降維到點要素,為方便表示,文中將降維標記為刪除,如表1所示。
表1 居民地專家選取結(jié)果示例(部分)Tab.1 Samples of expert selection result on habitation(part)
采用三元描述法,對專家選取居民地數(shù)據(jù)進行統(tǒng)一,確保在進行案例匹配時新的目標案例能夠在源案例庫中匹配到綜合結(jié)果,方便數(shù)據(jù)的檢索、存儲和管理。
2.2 居民地屬性的賦值、歸一化處理
不同變量的量綱不同,為了消除量綱的影響,便于KNN相似度的計算,需對居民地屬性賦值并進行歸一化處理。居民地屬性類型主要包括兩種:數(shù)值型和字符型。
首先考慮字符型屬性的處理,其中為方便計算將居民地行政等級數(shù)值化為4個等級,從1到4分別對應(yīng)市(一級)、區(qū)(二級)、鎮(zhèn)(三級)、村莊(四級)。居民地行政等級賦值并進行歸一化處理,如表2所示:
表2 居民地行政等級賦值并歸一化處理Tab.2 The result of assignment and normalization processing to executive rank of habitation
對于數(shù)值型屬性,采用min-max標準化(min-max normalization)使結(jié)果值映射到[0-1]之間。轉(zhuǎn)換函數(shù)如下
(3)
式中,max為樣本屬性數(shù)據(jù)的最大值;min為樣本屬性數(shù)據(jù)的最小值。
對area、NRG、NRD屬性特征進行歸一化處理后結(jié)果如表3所示:
表3 預(yù)處理后的居民地專家選取結(jié)果示例(部分)Tab.3 Samples of pretreatment with expert selection result on habitation(part)
2.3 居民地屬性的篩選
居民地選取本身顧及屬性較多,屬性選擇的判定對于選取結(jié)果的好壞起到?jīng)Q定性作用,而屬性的選擇與數(shù)據(jù)類型、制圖專家的主觀判斷密切相關(guān)。本文采用逐步消元法解決居民地屬性選取多少和選取哪些的問題,并用十折交叉驗證的方法得出分類正確百分比。十折交叉驗證是將數(shù)據(jù)集分成10份,輪流將其中9份作為訓(xùn)練數(shù)據(jù),1份作為測試數(shù)據(jù),進行試驗,得出相應(yīng)的正確率,10次結(jié)果正確率的平均值最終試驗結(jié)果[23]。逐步消元法的具體步驟是:首先從訓(xùn)練數(shù)據(jù)完整的屬性集中移除單個屬性,余下屬性形成一個屬性子集,對每個屬性子集進行十折交叉驗證,通過對比分類正確率確定最佳對象的屬性子集,按照這種方式重復(fù),即在逐步減少屬性數(shù)量的同時進行十折交叉驗證,記錄分類正確的百分比,結(jié)果如表 4所示。
從試驗結(jié)果可以看出,當屬性個數(shù)為4且屬性組成為area、grade、NRG、density時分類正確率最高。由此確定參與決策的屬性,并依此整理專家選取結(jié)果數(shù)據(jù),構(gòu)建居民地源案例庫。
表4 不同屬性子集的準確率統(tǒng)計Tab.4 Accuracy statistics of different attribute subsets
基于KNN算法實現(xiàn)案例匹配的一般步驟為:
(1) 訓(xùn)練數(shù)據(jù),確定最佳K值。
(2) 根據(jù)距離函數(shù)計算待分類居民地x與源案例庫每個訓(xùn)練樣本的距離,選擇與案例樣本距離最小的K個樣本作為x的K個最近鄰。
(3) 根據(jù)K個最近鄰判斷出x所屬類別。
判斷的依據(jù)是,設(shè)選取(S)個數(shù)為m,刪除(D)個數(shù)為n,合并(H)個數(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é)果,交由專家處理,進行人工交互判斷,問題解決后與①、②、③決策案例一起存入源案例庫作為更新案例,實現(xiàn)案例的自學(xué)習(xí)。
3.1 K值的選擇
KNN算法中K值決定了分類模型的好壞,K值太小會導(dǎo)致分類精度下降,K值過大會導(dǎo)致誤差過大從而影響分類的效率[24]。本文采用控制變量法和十折交叉驗證訓(xùn)練數(shù)據(jù)樣本,通過查全率(recall)、查準率(precision)、F1測度值和分類正確率4個指標來判斷最佳K的取值[23]。評價指標值越大,說明此時的K近鄰模型的分類性能越好,案例匹配的精度越高。以選取操作為例公式如下
(4)
(5)
(6)
查全率度量分類器正確預(yù)測正例的比例,查全率越高,分類的誤判率越低;查準率確定分類模型為正例的部分記錄中實際為正例的記錄所占的比例;F1測度值是查全率和查準率的調(diào)和均值,即在認為二者具有同等重要作用的前提下,將二者結(jié)合為一個指標?,F(xiàn)將訓(xùn)練數(shù)據(jù)(206個案例)中不同K值試驗結(jié)果如表5所示:
表5訓(xùn)練數(shù)據(jù)中不同K值推理結(jié)果統(tǒng)計
Tab.5ThestatisticsofinferenceresultsofdifferentKvaluefortrainingdata
K值大小查全率(R)查準率(P)F1測度值分類正確率/(%)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é)果可以看出,當訓(xùn)練樣本個數(shù)為206,K=4時,采用KNN算法進行案例分類正確率最高。
3.2 最佳K值的確定
文獻[25]研究發(fā)現(xiàn)最佳K值一定程度上與案例的規(guī)模存在關(guān)聯(lián),即K取訓(xùn)練樣本的2%時可以取得的分類效果最好。為了進一步探尋本文居民地選取案例類比推理最佳K值的選擇與案例庫規(guī)模的關(guān)系,本文采取不同的K值對其應(yīng)用效果進行了大量的測試,并采用不同的案例個數(shù)進行驗證,依據(jù)3.1節(jié)提供的方法,依次確定每組訓(xùn)練數(shù)據(jù)的最佳K值,試驗結(jié)果如表6所示。
表6不同訓(xùn)練數(shù)據(jù)最佳K值統(tǒng)計
Tab.6StatisticsofthebestKvaluefordifferenttrainingdata
分析試驗結(jié)果發(fā)現(xiàn),針對當前居民地數(shù)據(jù),最佳K值與案例樣本的總數(shù)確實存在一定的相關(guān)關(guān)系,驗證了文獻[24]的結(jié)論,即K取訓(xùn)練樣本的2%時可以取得的分類效果最好。
4.1 試驗流程
因大比例尺地圖中居民地綜合面臨的算子較多,如選取、合并、典型化、融合、位移等,本文暫不予以考慮。本文主要針對中小比例尺面狀居民地數(shù)據(jù),采用基于KNN算法和案例推理進行居民地選取,其基本步驟與流程如圖2所示。
圖2 基于KNN與案例推理的居民地選取技術(shù)路線Fig.2 The technology route of habitation selection based on KNN and CBR
圖2所示技術(shù)路線圖中主要包括以下5個步驟:
(1) 專家案例描述。對制圖專家的居民地選取結(jié)果通過三元法進行結(jié)構(gòu)化描述,構(gòu)建專家選取居民地案例。
(2) 數(shù)值轉(zhuǎn)換。將居民地案例輸入,對案例進行屬性賦值、歸一化等數(shù)值轉(zhuǎn)換處理。
(3) 案例屬性篩選。采用逐步消元法,確定參與決策的最佳屬性組合。構(gòu)建格式統(tǒng)一的源案例庫。
(4) 案例匹配。訓(xùn)練數(shù)據(jù),確定最佳K值,啟動類比推理和KNN檢索機制,將每個待處理居民地案例與源案例庫中的案例進行匹配,根據(jù)匹配結(jié)果得出解決方案,并依據(jù)解決方案指導(dǎo)居民地的選取。
(5) 人工處理。若KNN檢索中判斷案例類別個數(shù)相等,此時機器無法做出判決,需進行人工處理。將人工處理后的居民地數(shù)據(jù)源與成功匹配的居民地數(shù)據(jù)一起作為新案例加入到源案例庫中。
4.2 試驗與分析
為了驗證本文提出的居民地智能選取方法的有效性和優(yōu)勢性,利用居民地數(shù)據(jù)進行了相關(guān)試驗。依據(jù)流程設(shè)計試驗如下:以綜合的比例尺為1∶10萬至1∶20萬,北京及其周邊602個專家交互選取居民地作為源案例庫,如圖3所示。
圖3 專家案例數(shù)據(jù)示例Fig.3 Example of expert cases data
將制圖環(huán)境相似的涿州市附近150個居民地作為試驗案例,部分如圖4所示。數(shù)據(jù)預(yù)處理完成后,進行試驗案例與源案例庫的KNN檢索匹配,依據(jù)3.2節(jié)的結(jié)論可知,此時最佳K值為12。圖5為KNN試驗自動綜合的結(jié)果,專家交互選取結(jié)果如圖6所示。圖中居民地選取的對象標記為紅色,刪除居民地對象標記為灰白色,藍色為合并居民地對象。從圖中可以看出,圖5與圖6對應(yīng)居民地顏色大部分一致,即綜合結(jié)果總體相似度很高,只存在少量不一致的情況。
為檢驗KNN算法綜合結(jié)果的科學(xué)性和準確性,對此方法結(jié)果與圖6專家交互選取結(jié)果進行詳細對比與分析。為方便比較,僅顯示居民地要素,如圖7、圖8所示,相關(guān)數(shù)據(jù)統(tǒng)計見表7。
表7測試數(shù)據(jù)結(jié)果與專家交互選取結(jié)果對比統(tǒng)計
Tab.7Thestatisticsofcomparisonresultbetweentestdataandexpertinteractionselectdata
比較項目專家交互選取KNN算法選取個數(shù)/錯誤選取個數(shù)103/093/10刪除個數(shù)/錯誤刪除個數(shù)40/037/3合并個數(shù)/錯誤合并個數(shù)7/04/3選取查全率R1/(%)10090.29刪除查全率R2/(%)10092.5合并查全率R3/(%)10057.14有效決策率/(%)100100決策正確率/(%)10089.33
分析試驗對比結(jié)果可知,與專家交互選取結(jié)果相比,采用基于KNN的案例推理方法綜合后的居民地基本上保持了其分布特征,取得了較好的綜合效果。在復(fù)雜的制圖環(huán)境下,決策正確率達89.33%,且忠于專家經(jīng)驗,很大程度上還原了專家的制圖水平。僅存在極少量與專家選取不一致的綜合結(jié)果,部分如圖7、圖8箭頭所示,進一步分析發(fā)現(xiàn)該部分居民地處在專家判斷標準的邊緣,存在不可避免的模糊性,導(dǎo)致錯誤的產(chǎn)生。
進一步研究發(fā)現(xiàn),基于案例推理的居民地選取效果高度依賴源案例庫數(shù)據(jù)的質(zhì)量。制圖專家對居民地交互選取過程中,由于疲勞、注意力不集中、視覺誤差、操作失誤等原因,會造成居民地選取的操作結(jié)果出現(xiàn)錯誤。這些被稱作噪聲的錯誤案例加入到源案例庫后會直接影響學(xué)習(xí)效果,最終影響指導(dǎo)解決新任務(wù)的質(zhì)量。本文提出的基于KNN的案例推理方法與依據(jù)案例歸納出規(guī)則的基于決策樹方法相比,抗噪能力更強,在一定程度上能夠允許噪聲的存在,能有效彌補目前案例推理模型在制圖綜合應(yīng)用中抗噪能力弱的缺點。
傳統(tǒng)的決策樹方法中每一個根節(jié)點到葉子節(jié)點的分枝都是一條由案例演繹歸納得到的規(guī)則,如圖9(a)所示,為無噪聲專家居民地綜合簡單決策樹示意圖。若加入錯誤的案例即噪聲,如:將行政等級grade為3,面積area為658 956.7 m2的居民地案例由選取錯操作為合并,則會歸納出錯誤的規(guī)則,如圖9(b)灰色標志決策所示。而案例推理模型是已解決的新問題不斷加入到案例庫中,這種“滾雪球”式的發(fā)展會指導(dǎo)更多的案例進而造成更多錯誤決策。
圖4 試驗案例示例(部分)Fig.4 Example of experiment data (part)
圖5 KNN綜合結(jié)果Fig.5 KNN generalization result
而由1.2節(jié)KNN算法基本思想可知,KNN算法是K個案例參與決策待處理案例結(jié)果,故決策時個別噪聲的存在對判斷結(jié)果影響甚微,即基于KNN的案例推理模型在一定程度上受噪聲案例影響較小。為證明本文算法在抗噪方面的優(yōu)勢性,設(shè)計試驗在源案例庫中分別添加不同比例隨機噪聲進行對比試驗,二者決策正確率具體統(tǒng)計結(jié)果如表8所示,對比趨勢圖如圖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 兩種情況決策樹生成對比示例Fig.9 Comparison of two cases of decision tree generation
表8 加噪后決策樹與KNN決策正確率結(jié)果統(tǒng)計Tab.8 The statistics of accuracy results of noised decision tree and KNN (%)
圖10 加噪后決策樹與KNN算法決策正確率結(jié)果趨勢圖Fig.10 The trend of decision tree and KNN after adding noise
分析試驗結(jié)果可知,KNN算法更穩(wěn)定。隨著噪聲數(shù)據(jù)的加入,決策樹方法正確率受影響較大,而使用KNN算法的決策正確率相對穩(wěn)定,可見KNN算法在隨機噪聲干擾下魯棒性更強,有效彌補了目前案例推理模型在制圖綜合應(yīng)用中抗噪能力弱的缺點。
本文提出一種基于KNN案例推理的居民地選取方法,該方法直接以制圖專家對居民地交互選取結(jié)果作為案例對象,利用案例類比推理和KNN算法完成了居民地選取從已有專家案例到未知結(jié)果決策的轉(zhuǎn)化,達到了學(xué)習(xí)專家綜合知識并模仿專家綜合結(jié)果的目的。本文方法決策正確率高,受噪聲影響相對較小,有效彌補了目前案例推理模型在制圖綜合應(yīng)用中抗噪能力弱的缺點,且不需要提取規(guī)則;同時能有效利用專家經(jīng)驗,一定程度上降低制圖綜合的難度,為智能化自動綜合提供了新思路。
本文案例之間相似度是根據(jù)案例的所有屬性計算的,KNN計算時默認每個屬性的作用都相同,即被賦予相同權(quán)重。如何進一步優(yōu)化KNN算法,對案例屬性合理賦權(quán)值,使得案例推理對居民地選取結(jié)果準確率更高,是本文進一步的研究方向。
[1] 王家耀.地圖制圖學(xué)與地理信息工程學(xué)科進展與成就[M].北京:測繪出版社,2011.
WANG Jiayao.Advances in Cartography and Geographic Information Engineering[M].Beijing:Surveying and Mapping Press,2011.
[2] 王家耀.普通地圖制圖綜合原理[M].北京:測繪出版社,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] 鄧紅艷,武芳,錢海忠.基于遺傳算法的點群目標選取模型[J].中國圖象圖形學(xué)報,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特征變換的點群選取算法[J].測繪科學(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ò)的點群綜合研究[J].武漢大學(xué)學(xué)報(信息科學(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] 艾廷華,劉耀林.保持空間分布特征的群點化簡方法[J].測繪學(xué)報,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] 胡慧明,錢海忠,何海威,等.采用層次分析法的面狀居民地自動選取[J].測繪學(xué)報,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] 胡慧明,錢海忠,何海威,等.采用主成分分析法的面狀居民地自動選取[J].測繪與空間地理信息,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ù)實施居民地自動綜合[J].解放軍測繪學(xué)院學(xué)報,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] 溫婉麗.基于知識的居民地地圖自動綜合的研究[D].西安:長安大學(xué),2006.
WEN Wanli.Map of Residents to Automatic Comprehensive Research Based on the Knowledge[D].Xi’an:Chang’an University,2006.
[12] 錢海忠,武芳,王家耀.自動制圖綜合及其過程控制的智能化研究[M].北京:測繪出版社,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] 武芳,錢海忠,鄧紅艷,等.面向地圖自動綜合的空間信息智能處理[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].測繪學(xué)報,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].測繪科學(xué)技術(shù)學(xué)報,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)驗學(xué)習(xí)[M].上海:華東師范大學(xué)出版社,2012.
FENG Rui.Experiential Learning on Case-based Reasoning[M].Shanghai:East China Normal University Press,2012.
[20] 周偉達.核機器學(xué)習(xí)方法研究[D].西安:西安電子科技大學(xué),2003.
ZHOU Weida.Kernel Based Learning Machines[D].Xi’an:Xidian University,2003.
[21] 王家耀,姚杰.模糊綜合評判在制圖綜合中的應(yīng)用(以居民地選取為例)[J].測繪學(xué)院學(xué)報,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].鄭州:信息工程大學(xué),2016.
HUI Huiming.Research on Automatic Habitation Selection Method Based on Hierarchical Structure Model[D].Zhengzhou:Information Engineering University,2016.
[23] 袁梅宇.數(shù)據(jù)挖掘與機器學(xué)習(xí)——WEKA應(yīng)用技術(shù)與實踐[M].北京:清華大學(xué)出版社,2014.
YUAN Meiyu.Data Mining and Machine Learning:WEKA Application Technology and Practice[M].Beijing:Tsinghua University Press,2014.
[24] 嚴愛軍,錢麗敏,王普.案例推理屬性權(quán)重的分配模型比較研究[J].自動化學(xué)報,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)算法的研究與實現(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].測繪學(xué)報,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
國家自然科學(xué)基金(41571442;41171305)
(責任編輯:宋啟凡)
2017-02-09
修回日期:2017-09-01
謝麗敏(1991—),女,碩士生,研究方向為地圖自動綜合、空間數(shù)據(jù)挖掘。
E-mail:gis_xlm@163.com
錢海忠
E-mail:qianhaizhong2005@163.com