道路網(wǎng)智能選取的案例類(lèi)比推理法

郭 敏,錢(qián)海忠,黃智深,3,何海威,劉海龍

1．信息工程大學(xué)地理空間信息學(xué)院,河南鄭州 450052;2．61175部隊(duì),江蘇南京 210049;3．南疆測(cè)勤隊(duì),新疆喀什 844200

道路網(wǎng)智能選取的案例類(lèi)比推理法

郭 敏1,2,錢(qián)海忠1,黃智深1,3,何海威1,劉海龍1

1．信息工程大學(xué)地理空間信息學(xué)院,河南鄭州 450052;2．61175部隊(duì),江蘇南京 210049;3．南疆測(cè)勤隊(duì),新疆喀什 844200

從人類(lèi)學(xué)習(xí)和認(rèn)知角度,借鑒人工智能領(lǐng)域基于案例推理學(xué)習(xí)的成果,提出一種基于案例類(lèi)比推理的道路網(wǎng)智能選取新方法。該方法將制圖專(zhuān)家對(duì)某區(qū)域道路網(wǎng)的交互選取結(jié)果作為參考標(biāo)準(zhǔn),對(duì)其進(jìn)行結(jié)構(gòu)化描述并構(gòu)建和轉(zhuǎn)化為案例庫(kù);計(jì)算機(jī)采用一定的簡(jiǎn)化算法和泛化算法對(duì)該案例庫(kù)進(jìn)行分析和學(xué)習(xí),獲取檢索效率更高和適應(yīng)樣本能力更強(qiáng)的案例模型庫(kù);計(jì)算機(jī)在對(duì)相似道路網(wǎng)自動(dòng)選取時(shí),根據(jù)獲取的案例模型庫(kù),采用基于案例類(lèi)比推理的方法,分析獲取相應(yīng)的解決方案,進(jìn)而完成道路網(wǎng)智能選取。與已有研究成果相比,本方法以案例及其泛化模型來(lái)模擬專(zhuān)家思維,以計(jì)算機(jī)對(duì)案例模型的類(lèi)比學(xué)習(xí)來(lái)進(jìn)行相似道路網(wǎng)自動(dòng)選取,增強(qiáng)了道路網(wǎng)選取中的智能性。最后對(duì)本方法的科學(xué)性和適用性進(jìn)行驗(yàn)證,并對(duì)試驗(yàn)結(jié)果作分析和評(píng)價(jià),同時(shí)指出了存在的問(wèn)題和進(jìn)一步的研究方向。

道路網(wǎng);案例;案例模型庫(kù);類(lèi)比推理;智能選取

道路是人類(lèi)活動(dòng)軌跡的載體,反映著一個(gè)區(qū)域的地理特征和社會(huì)經(jīng)濟(jì)發(fā)展水平,是地圖要素的重要組成部分。正確反映道路網(wǎng)的分布特征對(duì)于客觀反映制圖區(qū)域地理特征具有重要意義[1]。道路網(wǎng)選取是制圖綜合中的重要研究?jī)?nèi)容之一,相關(guān)制圖學(xué)者圍繞道路匹配、識(shí)別、選取和沖突檢測(cè)等作了大量研究[2-7]。當(dāng)前,道路網(wǎng)選取方法比較多,總體上可以分為非智能化選取和基于智能模型的選取。其中非智能化選取主要包括:基于道路等級(jí)的簡(jiǎn)單選取[8-9],基于“Stroke”模型的選取[10-11],基于特征識(shí)別、Stroke與極化變換結(jié)合的道路網(wǎng)選取[12],基于圖論的選取[13-16],基于層次隨機(jī)圖的選取[17],基于路劃功能的選取[18]、基于網(wǎng)眼密度的選取[19]等?；谥悄苣Ｐ偷倪x取則主要包括基于遺傳算法的選取[20]和基于知識(shí)的選取[21]、基于案例歸納推理的道路網(wǎng)智能選取方法[22]等。

已有道路網(wǎng)選取方法主要存在兩方面的問(wèn)題:①道路網(wǎng)選取過(guò)程中考慮制約道路網(wǎng)選取的因素不夠全面,多數(shù)選取方法只專(zhuān)注于道路網(wǎng)的自身屬性,忽視了道路與其他地理要素的空間制約關(guān)系;②已有選取方法普遍適應(yīng)性不強(qiáng),缺乏歸納與推理能力,還難以達(dá)到智能化水平。

在剖析上述方法的基礎(chǔ)上,本文提出一種基于案例類(lèi)比推理的道路網(wǎng)智能選取方法。首先,將制圖專(zhuān)家對(duì)某區(qū)域道路網(wǎng)的交互選取結(jié)果作為參考標(biāo)準(zhǔn),對(duì)其進(jìn)行結(jié)構(gòu)化描述、簡(jiǎn)化和泛化并轉(zhuǎn)化為案例模型庫(kù)(該案例模型庫(kù)是后續(xù)計(jì)算機(jī)進(jìn)行學(xué)習(xí)和參考的標(biāo)準(zhǔn));其次,計(jì)算機(jī)在進(jìn)行相似道路網(wǎng)的自動(dòng)選取時(shí),從專(zhuān)家案例模型庫(kù)中提取相應(yīng)案例模型,采用案例類(lèi)比推理方法,分析獲取相應(yīng)的解決方案,進(jìn)而完成道路網(wǎng)選取。該方法中,采用案例對(duì)道路進(jìn)行形式化描述,既考慮其自身屬性,又顧及其與其他要素之間的空間關(guān)系,并建立了有效的案例庫(kù)簡(jiǎn)化和案例泛化機(jī)制,從而使得計(jì)算機(jī)能夠從專(zhuān)家案例庫(kù)中學(xué)習(xí)并獲取相似道路網(wǎng)選取的解決方案,實(shí)現(xiàn)道路網(wǎng)智能選取。

1 基于案例類(lèi)比推理的道路網(wǎng)智能選取原理

長(zhǎng)期以來(lái),制圖專(zhuān)家的制圖經(jīng)驗(yàn)一直難以形式化表達(dá)。這是因?yàn)榈缆肪W(wǎng)選取時(shí),除了有顯性的制圖規(guī)則支持外,還隱性包含了制圖專(zhuān)家自身的制圖經(jīng)驗(yàn)。因此,可以將制圖專(zhuān)家對(duì)道路網(wǎng)的選取結(jié)果作為案例(該案例庫(kù)包含了專(zhuān)家隱性知識(shí)),并構(gòu)建案例庫(kù),對(duì)案例庫(kù)進(jìn)行簡(jiǎn)化和泛化處理,獲取具備一定適用范圍的案例模型;然后通過(guò)類(lèi)比推理,讓計(jì)算機(jī)從案例模型中獲取解決當(dāng)前問(wèn)題的方案,從而實(shí)現(xiàn)相同或者相似道路網(wǎng)的智能化選取。其基本原理如圖1所示。

圖1流程中包含以下4個(gè)主要步驟:

(1)將制圖專(zhuān)家對(duì)道路網(wǎng)選取結(jié)果進(jìn)行結(jié)構(gòu)化描述,構(gòu)建計(jì)算機(jī)能識(shí)別和學(xué)習(xí)的道路網(wǎng)選取案例庫(kù)。

(2)對(duì)案例庫(kù)進(jìn)行簡(jiǎn)化,對(duì)相同或者相似的案例進(jìn)行合并,降低案例庫(kù)容量,得到簡(jiǎn)化案例庫(kù)。

(3)對(duì)簡(jiǎn)化案例庫(kù)中的案例進(jìn)行泛化,形成具有一定概括能力的案例模型,這些案例模型能夠?yàn)橄嗤蛳嗨频缆肪W(wǎng)選取提供解決方案。

(4)待處理道路網(wǎng)數(shù)據(jù)輸入后,啟動(dòng)檢索和類(lèi)比推理機(jī)制,每條道路與案例模型庫(kù)中的案例模型進(jìn)行匹配,根據(jù)匹配結(jié)果得出解決方案,并依據(jù)解決方案進(jìn)行道路網(wǎng)綜合。

圖1 基于案例類(lèi)比推理的道路網(wǎng)智能選取基本原理Fig．1 Principles of intelligent road-network selection using CBR

2 專(zhuān)家案例獲取與表達(dá)

道路網(wǎng)案例來(lái)源于制圖專(zhuān)家對(duì)道路網(wǎng)交互式選取的結(jié)果。這些案例將作為學(xué)習(xí)資源,用于計(jì)算機(jī)學(xué)習(xí)與分析,從而為相似道路網(wǎng)選取任務(wù)提供解決方案。這里,首先需要對(duì)制圖專(zhuān)家選取結(jié)果進(jìn)行形式化描述(即案例表達(dá))。

2．1 道路網(wǎng)選取案例的描述結(jié)構(gòu)

案例一般有3個(gè)主要組成部分:①問(wèn)題或情景描述,即案例發(fā)生時(shí)要解決的問(wèn)題及周?chē)澜绲臓顟B(tài);②解決方案,即對(duì)問(wèn)題的解決方案;③結(jié)果,即執(zhí)行解決方案后導(dǎo)致的結(jié)果(周?chē)澜缧碌臓顟B(tài))。

任何基于案例推理的系統(tǒng)必須要有問(wèn)題或情景描述和解決方案,這是必不可少的,而結(jié)果部分在有的系統(tǒng)中可能沒(méi)有[22-24]。因此案例結(jié)構(gòu)可以用一個(gè)有序?qū)M(jìn)行描述

式中,X表示問(wèn)題或者情景描述;Y表示解決方案;Z表示導(dǎo)致的結(jié)果。

據(jù)此,道路網(wǎng)選取案例也應(yīng)包括3個(gè)部分:①問(wèn)題描述,即關(guān)于道路網(wǎng)所處的制圖環(huán)境以及制約是否被選取的各種條件的描述;②解決方案,指對(duì)道路執(zhí)行的選取或者刪除操作;③導(dǎo)致的結(jié)果,指道路要素的取舍操作對(duì)當(dāng)前制圖環(huán)境的改變(形成新的制圖綜合狀態(tài))。其中Z受到具體制圖環(huán)境制約,目前還無(wú)法進(jìn)行較為合理的定性或定量描述。因此,本文采用二元描述法,即: CASE:{X,Y}。

通過(guò)對(duì)比綜合結(jié)果,對(duì)道路網(wǎng)執(zhí)行解決方案的結(jié)果進(jìn)行評(píng)價(jià)。同時(shí)對(duì)每個(gè)案例進(jìn)行編號(hào),以便于案例搜索與統(tǒng)計(jì)。完整的道路網(wǎng)選取案例結(jié)構(gòu)如圖2所示。

圖2 道路網(wǎng)選取案例的描述結(jié)構(gòu)Fig．2 The description structure of road-network selection case

2．2 道路網(wǎng)選取案例對(duì)象狀態(tài)描述

道路網(wǎng)選取案例的對(duì)象狀態(tài)包括道路自身屬性、道路與其他地物之間的空間關(guān)系、道路網(wǎng)所處的制圖環(huán)境等。已有的道路網(wǎng)選取方法,大多只考慮道路網(wǎng)的自身屬性,忽視了道路與其他地物之間的空間制約關(guān)系。本文則采用空間分析算法獲取道路網(wǎng)與其他地物之間的空間關(guān)系,在既有道路網(wǎng)屬性信息基礎(chǔ)上,構(gòu)建了綜合考慮屬性和拓?fù)潢P(guān)系的道路狀態(tài)信息描述結(jié)構(gòu),其結(jié)構(gòu)為:“道路編碼/道路名稱(chēng)/道路類(lèi)型/道路編號(hào)/道路等級(jí)/道路寬度/載重噸數(shù)/里程/高程/比高/通行月份/最小曲率半徑/最大縱坡/圖形特征代碼/注記編號(hào)/資料說(shuō)明/道路長(zhǎng)度/路網(wǎng)密度/車(chē)道數(shù)/通達(dá)重要性/軍事價(jià)值等級(jí)/政治價(jià)值等級(jí)/經(jīng)濟(jì)價(jià)值等級(jí)/專(zhuān)用性”[22]。其中,通達(dá)重要性、軍事價(jià)值等級(jí)、政治價(jià)值等級(jí)、經(jīng)濟(jì)價(jià)值等級(jí)指標(biāo),需要通過(guò)空間分析方法,探測(cè)道路與臨近居民地、軍事目標(biāo)、經(jīng)濟(jì)目標(biāo)等之間的關(guān)系,并通過(guò)臨近目標(biāo)的重要性來(lái)評(píng)估道路相應(yīng)屬性的重要性程度。限于篇幅,此處不展開(kāi)闡述,已另文詳述。

與之對(duì)應(yīng)的道路網(wǎng)選取案例形式化實(shí)例如圖3所示(從專(zhuān)家案例庫(kù)中摘錄)。

圖3 道路網(wǎng)選取案例結(jié)構(gòu)化描述實(shí)例Fig．3 Part of structured description of road selection cases

采用案例類(lèi)比推理進(jìn)行道路網(wǎng)選取,是將高水平制圖專(zhuān)家選取結(jié)果作為參考。針對(duì)新道路網(wǎng)選取任務(wù),只有與其制圖用途、區(qū)域特點(diǎn)、制圖比例尺相同的專(zhuān)家案例庫(kù)才具有更強(qiáng)的指導(dǎo)性。因此,在建立專(zhuān)家案例庫(kù)時(shí),需按照制圖用途、區(qū)域特點(diǎn)、制圖比例尺分目錄建立,便于在處理道路選取任務(wù)時(shí),選擇相應(yīng)的案例庫(kù)讓計(jì)算機(jī)自動(dòng)學(xué)習(xí)。

3 專(zhuān)家案例庫(kù)簡(jiǎn)化與泛化原理[25]

3．1 專(zhuān)家案例庫(kù)簡(jiǎn)化原理

對(duì)從制圖專(zhuān)家交互綜合中獲取的案例,還需要進(jìn)行簡(jiǎn)化,并且對(duì)相同或相似案例進(jìn)行合并,從而縮短檢索時(shí)間、提高檢索效率,同時(shí)剔除一些在臨界條件下專(zhuān)家的不確定性操作(例如表1中在相同條件下,有的道路被選取,有的道路被刪除。這可能是同一制圖專(zhuān)家綜合尺度不統(tǒng)一,也可能是不同專(zhuān)家之間的綜合尺度不統(tǒng)一,這些因素在現(xiàn)實(shí)中都是客觀存在的)。

需要說(shuō)明的是,制圖專(zhuān)家具有豐富專(zhuān)業(yè)知識(shí)和專(zhuān)業(yè)技能,其經(jīng)驗(yàn)總體上是客觀和科學(xué)的,本文研究也是基于這一前提展開(kāi)的。少量的錯(cuò)誤經(jīng)驗(yàn),以及多個(gè)專(zhuān)家之間的經(jīng)驗(yàn)沖突,可認(rèn)為是噪聲。關(guān)于如何除去案例庫(kù)噪聲這一問(wèn)題,限于篇幅,此處不重點(diǎn)介紹,筆者已經(jīng)采用預(yù)降噪與后降噪相結(jié)合的案例庫(kù)噪聲降低策略進(jìn)行研究,將撰文另行闡述。

主要道路選取過(guò)程其實(shí)也是次要道路刪除的過(guò)程。本文設(shè)計(jì)的案例庫(kù)簡(jiǎn)化算法,計(jì)算機(jī)分別計(jì)算相同或者相似案例中執(zhí)行“選取”操作的案例數(shù)(K)和“刪除”操作的案例數(shù)(P),并比較二者大小,自動(dòng)選擇相應(yīng)的簡(jiǎn)化方案。

簡(jiǎn)化算法流程為:

(1)計(jì)算機(jī)檢索案例庫(kù),對(duì)案例描述條件相同的案例進(jìn)行自動(dòng)分類(lèi)。

(2)計(jì)算每一類(lèi)中執(zhí)行“選取”和“刪除”操作的個(gè)數(shù)K、P,判斷K和P的大小關(guān)系,選擇簡(jiǎn)化方案。

①若K＞P,保留一個(gè)執(zhí)行結(jié)果為“選取”的案例。

②若K＜P,保留一個(gè)執(zhí)行結(jié)果為“刪除”的案例。

③若K＝P,所有案例都不予保留。

以表1為例說(shuō)明案例庫(kù)簡(jiǎn)化的具體方法(表1是從制圖專(zhuān)家道路網(wǎng)選取案例庫(kù)中提取的樣例)。

表1 道路網(wǎng)選取專(zhuān)家案例庫(kù)Tab．1 Case base of road-network selection

(1)首先,對(duì)案例描述條件相同的案例進(jìn)行分類(lèi)。從表1中提取道路等級(jí)、鋪面材質(zhì)、居民地間唯一通道、道路長(zhǎng)度等4個(gè)條件相同的案例并分類(lèi),如表2、表3、表4所示。

表2 從表1中提取的相同條件案例集合1Tab．2 Case collection 1 of the same condition from tab．1

表3 從表1中提取的相同條件案例集合2Tab．3 Case collection 2 of the same condition from tab．1

表4 從表1中提取的相同條件案例集合3Tab．4 Case collection 3 of the same condition from tab．1

(2)計(jì)算每一類(lèi)中的選取案例個(gè)數(shù)(K)和刪除案例個(gè)數(shù)(P),判斷K、P的大小關(guān)系,選擇簡(jiǎn)化方案。

①K＝2、P＝1,K＞P,保留表2所示執(zhí)行結(jié)果為選取的案例。

②K＝1、P＝1,K＝P,所有案例都不予保留(如表3)。

③K＝1、P＝2,K＜P,保留一個(gè)執(zhí)行結(jié)果為刪除的案例(如表4)。

表1案例庫(kù)經(jīng)過(guò)上述兩步簡(jiǎn)化步驟后,生成如表5所示的簡(jiǎn)化案例庫(kù)。

表5 簡(jiǎn)化后案例庫(kù)Tab．5 Case base after simplification

可以看出,生成的簡(jiǎn)化案例庫(kù)較原案例庫(kù)案例數(shù)量大幅減少,案例檢索效率較原案例庫(kù)有大幅提高,但仍然能有效反映專(zhuān)家案例庫(kù)的本質(zhì)特征。

3．2 專(zhuān)家案例泛化原理

泛化是指當(dāng)某一反應(yīng)與某種刺激形成條件聯(lián)系后,這一反應(yīng)也會(huì)與其他類(lèi)似刺激形成某種程度條件聯(lián)系的過(guò)程。由于案例庫(kù)中每個(gè)案例僅代表某一種綜合情況,而完全相同的情況在新任務(wù)中幾乎很少出現(xiàn)。因此,必須完成案例從“個(gè)別”到“一般”的泛化。原始案例庫(kù)經(jīng)過(guò)3．1節(jié)的簡(jiǎn)化處理,獲得了簡(jiǎn)化后的案例庫(kù),需進(jìn)一步泛化,增強(qiáng)案例的適用范圍,形成具有更強(qiáng)適應(yīng)性的案例模型庫(kù)。

根據(jù)“優(yōu)先選取評(píng)價(jià)指標(biāo)重要的道路”這一基本原則。為計(jì)算機(jī)設(shè)計(jì)泛化規(guī)則(即泛化算法),

可總結(jié)為以下4條:

(1)用變量代替常量。如:railway(50 km,雙軌),泛化為:railway(X,雙軌)。

(2)去掉合取表達(dá)式中一些條件。如:grade (X,一級(jí))∧length(X,5 km)∧character(X,瀝青),泛化為:grade(X,一級(jí))∧length(X,5 km)。

(3)合取表達(dá)式中析取一些條件。如grade (X,一級(jí))∧length(X,5 km)∧character(X,瀝青),泛化為:

grade(X,一級(jí))∧character(X,瀝青)∧length(X,5 km)∨length(X,10 km)。

(4)用屬性的超類(lèi)來(lái)替換屬性。如:road (5 km,瀝青),泛化為road(5 km,材質(zhì))。

按照泛化規(guī)則,對(duì)表5所示的簡(jiǎn)化案例庫(kù)進(jìn)行泛化。其中:

表6 案例模型庫(kù)Tab．6 Model base of cases

表7是案例模型庫(kù)(表6)與原始案例庫(kù)(表1)的容量及適用性對(duì)比結(jié)果。結(jié)果顯示,案例模型庫(kù)容量大幅減少,適用范圍顯著擴(kuò)大,適應(yīng)能力有效增強(qiáng),且具備了為計(jì)算機(jī)所識(shí)別的概括和類(lèi)比推理能力,可為相同或相似道路網(wǎng)的計(jì)算機(jī)智能選取提供決策支持。

表7 案例泛化前后案例庫(kù)適用情況比較表Tab．7 The adaptability comparison between the original and simplified case bases

4 基于專(zhuān)家案例類(lèi)比推理的道路網(wǎng)智能選取流程

在獲取制圖專(zhuān)家道路網(wǎng)選取案例、案例庫(kù)和案例模型庫(kù)的基礎(chǔ)上,設(shè)計(jì)了基于專(zhuān)家案例類(lèi)比推理的道路網(wǎng)智能選取流程(圖4)。算法具體步驟為:

(1)任務(wù)初始化。選擇需要處理的道路網(wǎng),通過(guò)空間分析,獲取道路網(wǎng)與其他空間要素之間的空間關(guān)系,并通過(guò)格式轉(zhuǎn)換,形成道路網(wǎng)案例格式(這樣才能與專(zhuān)家案例庫(kù)進(jìn)行類(lèi)比分析)。

(2)案例庫(kù)調(diào)用。根據(jù)給定道路網(wǎng)選取任務(wù),調(diào)用相似環(huán)境專(zhuān)家案例庫(kù)作為計(jì)算機(jī)學(xué)習(xí)和分析資源。

(3)生成簡(jiǎn)化案例庫(kù)和案例模型庫(kù)。按照3．1節(jié)方法,對(duì)專(zhuān)家案例庫(kù)進(jìn)行簡(jiǎn)化處理,生成簡(jiǎn)化案例庫(kù)。并在此基礎(chǔ)上,按照3．2節(jié)所述原理對(duì)簡(jiǎn)化案例庫(kù)中的案例進(jìn)行泛化,生成案例模型庫(kù)。

(4)檢索判斷。將每條待處理道路與案例模型庫(kù)中的案例模型匹配。記錄匹配成功的案例模型個(gè)數(shù)c,并分別記錄其中執(zhí)行選取操作的模型個(gè)數(shù)m和執(zhí)行刪除操作的模型個(gè)數(shù)n,則有c＝m＋n。

①如果c＝0,說(shuō)明無(wú)案例模型相匹配,待選道路無(wú)法自動(dòng)處理,需進(jìn)行人工交互。

②如果c≠0且m＞n,則對(duì)待處理道路執(zhí)行“選取”操作。

③如果c≠0且m＜n,則對(duì)待處理道路執(zhí)行“刪除”操作。

④如果c≠0且m＝n,說(shuō)明專(zhuān)家案例模型庫(kù)中出現(xiàn)模棱兩可情況;該情況下認(rèn)為推理不充分,案例庫(kù)無(wú)法給出解決方案,需進(jìn)行人工交互。

(5)人工交互處理。針對(duì)步驟(4)中的情況①和④,需要進(jìn)行人工交互綜合。

需要說(shuō)明的是,決定人工交互工作量的因素包括專(zhuān)家案例庫(kù)質(zhì)量及完備性等諸多因素。限于篇幅,專(zhuān)家案例庫(kù)質(zhì)量及完備性問(wèn)題將另文介紹,此處不贅述。

5 實(shí) 例

本試驗(yàn)用于驗(yàn)證本文提出道路網(wǎng)智能選取方法的合理性、推理過(guò)程的科學(xué)性與智能性和獲取案例模型的適應(yīng)性。

5．1 專(zhuān)家案例庫(kù)生成

圖5(見(jiàn)文末)所示的是某比例尺試驗(yàn)數(shù)據(jù)(其中,居民地、境界與政區(qū)用于對(duì)道路通達(dá)重要性等指標(biāo)的輔助評(píng)價(jià)),道路總數(shù)556條。圖6(見(jiàn)文末)是制圖專(zhuān)家按照某目標(biāo)比例尺,對(duì)原始數(shù)據(jù)中道路網(wǎng)進(jìn)行選取后的結(jié)果(選取442,刪除114條)。圖中,道路等級(jí)用線條粗細(xì)區(qū)分,居民之間唯一聯(lián)通道路(原始道路數(shù)據(jù)與居民地?cái)?shù)據(jù)通過(guò)空間分析計(jì)算獲取)用紅色表示(下同)。以圖6制圖專(zhuān)家選取結(jié)果作為案例,構(gòu)建了如圖7所示的案例庫(kù)(局部截圖)。

圖7 道路網(wǎng)選取專(zhuān)家案例庫(kù)(局部)Fig．7 The expert case base of road network selection(part)

5．2 案例庫(kù)簡(jiǎn)化

根據(jù)3．1節(jié)案例庫(kù)簡(jiǎn)化算法,對(duì)圖7所示的專(zhuān)家案例庫(kù)進(jìn)行簡(jiǎn)化,結(jié)果如圖8所示。

圖8 簡(jiǎn)化后的道路網(wǎng)選取專(zhuān)家案例庫(kù)(局部)Fig．8 The expert case base of road network selection after simplification(part)

表8 案例庫(kù)簡(jiǎn)化前后案例數(shù)量的比較結(jié)果Tab．8 The comparison outcome of expert cases before and after simplified

5．3 案例泛化

根據(jù)3．2節(jié)的案例泛化規(guī)則,對(duì)簡(jiǎn)化后的案例庫(kù)(圖8)中的案例進(jìn)行泛化,泛化結(jié)果如圖9所示,共獲得99個(gè)案例模型。

圖9 案例泛化后的案例模型(局部)Fig．9 The case model after case generalization(part)

5．4 對(duì)專(zhuān)家案例庫(kù)構(gòu)建及泛化方法的科學(xué)性驗(yàn)證

采用案例庫(kù)(圖7)和泛化案例庫(kù)(圖9)分別對(duì)原始道路網(wǎng)進(jìn)行反選,以檢驗(yàn)案例庫(kù)構(gòu)建和泛化算法的科學(xué)性。

5．4．1 對(duì)專(zhuān)家案例庫(kù)構(gòu)建方法的科學(xué)性驗(yàn)證

采用專(zhuān)家選取的原始案例庫(kù)(圖7),對(duì)原始試驗(yàn)數(shù)據(jù)(圖5)進(jìn)行指導(dǎo)反選,其結(jié)果如圖10所示。

對(duì)比顯示,選取和刪除的結(jié)果與專(zhuān)家完全一致(計(jì)算機(jī)選取442條、刪除114條,道路完全一樣)。選取的正確率為100%。說(shuō)明采用案例記錄專(zhuān)家的案例知識(shí)這一途徑,能有效地反映專(zhuān)家的實(shí)際制圖經(jīng)驗(yàn)。

5．4．2 對(duì)專(zhuān)家案例庫(kù)簡(jiǎn)化與泛化方法的科學(xué)性驗(yàn)證

采用泛化后的案例模型庫(kù)(如圖9,從圖7的案例庫(kù)中泛化得到)對(duì)原始試驗(yàn)道路網(wǎng)數(shù)據(jù)(圖5)進(jìn)行反選,以繼續(xù)驗(yàn)證在原始專(zhuān)家案例庫(kù)(圖7)基礎(chǔ)上進(jìn)行智能推理過(guò)程及其結(jié)果的科學(xué)性。結(jié)果如圖11所示。計(jì)算機(jī)選取結(jié)果與專(zhuān)家選取結(jié)果的對(duì)比情況如圖12所示(圈形標(biāo)識(shí)為計(jì)算機(jī)選取結(jié)果與專(zhuān)家選取結(jié)果的不同之處),表9是具體數(shù)據(jù)統(tǒng)計(jì)情況。

表9 基于案例類(lèi)比推理結(jié)果統(tǒng)計(jì)(1)Tab．9 The statistics outcome(1)based on CBR

從表9可知,原始道路556條,類(lèi)比推理處理做出決策459條(刪除61條,選取398條)。另外因沒(méi)有相應(yīng)案例模型匹配而無(wú)法完成決策的有10條,因案例模型推理不充分而無(wú)法完成決策有87條。為確保刪除道路的正確性,對(duì)無(wú)法完成決策的道路保留現(xiàn)狀,待人工交互處理。

計(jì)算機(jī)基于案例類(lèi)比推理選取結(jié)果與專(zhuān)家選取結(jié)果的對(duì)比分析如表10所示。其中,“有效決策率”指案例模型指導(dǎo)處理道路數(shù)占有案例相匹配的道路總數(shù)的比率;“決策正確率”指案例模型正確指導(dǎo)處理道路數(shù)占案例模型指導(dǎo)處理道路總數(shù)的比率。

表10 計(jì)算機(jī)基于案例類(lèi)比推理選取結(jié)果與專(zhuān)家選取結(jié)果對(duì)比Tab．10 The comparing of road selection results of computer with CBR and expert

表10統(tǒng)計(jì)分析結(jié)果表明本試驗(yàn)中基于案例類(lèi)比推理的有效決策率為84．07%,決策正確率為89．35%。說(shuō)明計(jì)算機(jī)對(duì)案例簡(jiǎn)化和泛化后,案例模型對(duì)專(zhuān)家案例中的選取知識(shí)概括率達(dá)84．07%。這些案例模型對(duì)專(zhuān)家案例知識(shí)的正確反映率達(dá)89．35%。試驗(yàn)表明,泛化后的案例模型能夠有效的反映制圖專(zhuān)家的大部分經(jīng)驗(yàn),說(shuō)明本文的案例庫(kù)簡(jiǎn)化和泛化算法以及得到的案例模型是科學(xué)的。

錯(cuò)誤刪除的15條道路主要集中在等級(jí)較低和長(zhǎng)度較短的道路上,這些道路的錯(cuò)誤刪除對(duì)道路網(wǎng)局部拓?fù)浣Y(jié)構(gòu)造成了一定的破壞。出現(xiàn)這種情況主要原因在于:所構(gòu)建的案例庫(kù)還不能完全反映專(zhuān)家的制圖經(jīng)驗(yàn)(如許多屬性項(xiàng)為空、有些指標(biāo)還未形式化表達(dá)等),同時(shí)案例庫(kù)中的錯(cuò)誤案例,也會(huì)對(duì)案例推理結(jié)果產(chǎn)生影響。

5．5 對(duì)案例類(lèi)比推理模型的科學(xué)性驗(yàn)證

為繼續(xù)驗(yàn)證本文案例類(lèi)比推理過(guò)程的科學(xué)性,采用與制圖專(zhuān)家相似制圖環(huán)境下的其他數(shù)據(jù)進(jìn)行試驗(yàn)驗(yàn)證(圖13是與圖5同一地區(qū)、相同比例尺的另一幅道路網(wǎng)數(shù)據(jù))。計(jì)算機(jī)用圖9中的案例模型庫(kù)對(duì)圖13中的道路網(wǎng)進(jìn)行自動(dòng)選取,自動(dòng)選取結(jié)果如圖14所示,具體數(shù)據(jù)統(tǒng)計(jì)情況如表11所示。

從表11可知,原始道路為1046條,類(lèi)比推理做出決策645條,其中刪除168條、選取477條。有300條道路由于沒(méi)有相應(yīng)案例模型匹配無(wú)法完成決策,101條道路由于案例模型推理不充分無(wú)法完成決策。同樣,對(duì)無(wú)法完成決策的道路全部做保留現(xiàn)狀處理,待人工交互處理。在存在模型匹配的746(645＋101)條道路中,有效決策道路645條,有效決策率為645/746＝86．46%。

圖5 原始試驗(yàn)數(shù)據(jù)Fig．5 The original test data

圖6 專(zhuān)家選取結(jié)果Fig．6 The outcome of expert selection

圖10 計(jì)算機(jī)對(duì)原始數(shù)據(jù)的反選結(jié)果Fig．10 The computer reverse selection outcome to original data

圖11 計(jì)算機(jī)基于案例類(lèi)比推理道路網(wǎng)選取結(jié)果Fig．11 The computer selection outcome of road network based on CBR

圖13 相似區(qū)域另一幅原始道路網(wǎng)數(shù)據(jù)Fig．13 Another original data of road that has similar characters

圖14 對(duì)圖13采用案例類(lèi)比推理選取的結(jié)果Fig．14 Selection result to fig．13 based on CBR

表11 基于案例類(lèi)比推理結(jié)果統(tǒng)計(jì)(2)Tab．11 The statistics outcome(2)based on CBR

對(duì)比圖13與圖14,選取后的道路網(wǎng)整體結(jié)構(gòu)保持較好,道路選取數(shù)量和道路網(wǎng)密度比較適中,高等級(jí)道路和具有重要連通性道路選取質(zhì)量較高。說(shuō)明本文的案例類(lèi)比推理過(guò)程是科學(xué)的,具有普適性,即只要與案例數(shù)據(jù)具有相同制圖環(huán)境(區(qū)域特點(diǎn)、比例尺)的空間數(shù)據(jù),均可以采用案例類(lèi)比推理進(jìn)行自動(dòng)綜合。

5．6 存在問(wèn)題及改進(jìn)方向

上述試驗(yàn)表明,本文提出的基于案例類(lèi)比推理的道路網(wǎng)智能選取方法可行且科學(xué),能有效地為相同或相似制圖環(huán)境的道路網(wǎng)選取提供解決方案。但還不能完全實(shí)現(xiàn)道路網(wǎng)智能選取,其原因在于:

(1)目前很多道路網(wǎng)數(shù)據(jù)的屬性信息描述不完整,因此還不能將所有制約道路網(wǎng)選取的因素都考慮周全并形式化表達(dá)。

(2)由于制圖綜合的復(fù)雜性,目前制圖專(zhuān)家的案例數(shù)量、類(lèi)型還沒(méi)有覆蓋所有可能出現(xiàn)的道路網(wǎng)選取類(lèi)型,還需要長(zhǎng)期積累。

(3)本文所提出的道路網(wǎng)選取方法,是基于專(zhuān)家案例進(jìn)行的。即使是高水平制圖專(zhuān)家,其在制圖過(guò)程中,由于疲勞、操作失誤等,會(huì)出現(xiàn)個(gè)別錯(cuò)誤案例,影響學(xué)習(xí)結(jié)果。這就需要對(duì)這些錯(cuò)誤案例進(jìn)行有效的識(shí)別和剔除。

(4)需要深入研究道路網(wǎng)智能選取結(jié)果的量化評(píng)估機(jī)制。

以上都是有待進(jìn)一步研究和改進(jìn)之處。

6 結(jié)束語(yǔ)

本文是將人工智能成果應(yīng)用到制圖綜合的一種嘗試,為道路網(wǎng)智能選取提供了一種借鑒途徑。較傳統(tǒng)選取方法,本方法的優(yōu)勢(shì)在于:以案例庫(kù)為知識(shí)的存儲(chǔ)形式,降低了知識(shí)形式化表達(dá)難度;采用案例類(lèi)比推理機(jī)制,忠于專(zhuān)家經(jīng)驗(yàn),減少了推理過(guò)程中知識(shí)畸變;擁有自主學(xué)習(xí)能力,具備智能性;降低了制圖技術(shù)人員的專(zhuān)業(yè)知識(shí)門(mén)檻,作業(yè)人員不需要具備豐富的道路網(wǎng)選取知識(shí),直接調(diào)用以案例形式存儲(chǔ)的專(zhuān)家知識(shí),計(jì)算機(jī)自動(dòng)完成學(xué)習(xí)和選取。同時(shí),本方法也可為其他要素的智能化自動(dòng)綜合研究提供方法與技術(shù)借鑒。

[1] WANG Jiayao．Normal Map Cartographic Generalization Principle[M]．Beijing:Surveying and Mapping Press, 1992．(王家耀．普通地圖制圖綜合原理[M]．北京:測(cè)繪出版社,1992．)

[2] WU Xiaofang,DU Qingyun,XU Zhiyong．Disposal of Spatial Conflict between Road and Buildings Based on the Multilevel Displacement[J]．Acta Geodaetica et Cartographica Sinica,2010,39(6):649-654．(吳小芳,杜清運(yùn),徐智勇．多層次位移原則的道路與建筑物空間沖突處理[J]．測(cè)繪學(xué)報(bào),2010,39(6):649-654．)

[3] QIAN Haizhong,WU Fang,WANG Jiayao．Theory and Technology Model of Automatic Generalization Chain[J]．Acta Geodaetica et Cartographica Sinica,2006,35(4): 400-408．(錢(qián)海忠,武芳,王家耀．自動(dòng)制圖綜合鏈理論與技術(shù)模型[J]．測(cè)繪學(xué)報(bào),2006,35(4):400-408．)

[4] CHEN Yuming,GONG Jianya,SHI Wenzhong．A Distancebased Matching Algorithm for Multi-scale Road Networks [J]．Acta Geodaetica et Cartographica Sinica,2007,36 (1):84-89．(陳玉敏,龔建雅,史文中．多尺度道路網(wǎng)的距離匹配算法研究[J]．測(cè)繪學(xué)報(bào),2007,36(1):84-89．)

[5] TIAN Jing,AI Tinghua,DING Shaojun．Grid Pattern Recognition in Road Networks Based on C4．5 Algorithm [J]．Acta Geodaetica et Cartographica Sinica,2012,41 (1):121-126．(田晶,艾廷華,丁紹軍．基于C4．5算法的道路網(wǎng)網(wǎng)格模式識(shí)別[J]．測(cè)繪學(xué)報(bào),2012,41(1): 121-126．)

[6] WU Xiaofang,DU Qingyun,HU Yueming,et al．Disposal of Spatial Conflict between the Roads Networks Based on Improved Snake Model[J]．Acta Geodaetica et Cartographica Sinica,2008,37(5):223-229．(吳小芳,杜清運(yùn),胡月明,等．基于改進(jìn)Snake模型的道路網(wǎng)空間沖突處理[J]．測(cè)繪學(xué)報(bào),2008,37(5):223-229．)

[7] WU Fang,HOU Xuan,QIAN Haizhong,et al．A Model for Road Network Displacement in Automated Map Generalization[J]．Acta Geodaetica et Cartographica Sinica．2005,34(2):262-268．(武芳,侯漩,錢(qián)海忠,等．自動(dòng)制圖綜合中的線目標(biāo)位移模型[J]．測(cè)繪學(xué)報(bào),2005,34 (2):262-268．)

[8] GUO Jian．Residential Areas Road Network Automated Generalization Supported by 1∶250 000 Database[D]．Zhengzhou:Information Engineering University,1993．(郭健．1∶25萬(wàn)數(shù)據(jù)庫(kù)支持下居民地道路的自動(dòng)綜合[D]．鄭州:信息工程大學(xué),1993．)

[9] WANG Guangxia．The Research of Automated Cartographic Generalization System and the Realization of Residential Areas Road Network Automated Generalization[D]．Zhengzhou:Information Engineering University,1994．(王光霞．自動(dòng)制圖綜合系統(tǒng)的研究及居民地道路自動(dòng)綜合的實(shí)現(xiàn)[D]．鄭州:信息工程大學(xué),1994．)

[10] GUO Qingsheng．Liner Elements Automated Generalization Algorithm Based on Objective Generalization Nature[J]．The Translation of Wuhan Surveying and Mapping College,1994(1):49-58．(郭慶勝．基于客觀綜合自然規(guī)律的線狀要素自動(dòng)綜合的算法[J]．武測(cè)譯文,1994(1): 49-58．)

[11] THOMSON R C,RICHARDSON D E．The‘Good Continuation’Principle of Perceptual Organization Applied to Generalization of Road Networks[C]∥Proceedings of the ICA 19th International Cartographic Conference．Ottawa: [s．n．],1999:1215-1223．

[12] QIAN Haizhong,ZHANG Zhao,ZHAI Yinfeng．et al．Road Selection Method Based on Character Recognition,Stroke and Polarization Transformation[J]．Journal of Geomatics Science and Technology,2010,27(5):371-374．(錢(qián)海忠,張釗,翟銀鳳,等．特征識(shí)別、Stroke與極化變換結(jié)合的道路網(wǎng)選取[J]．測(cè)繪科學(xué)技術(shù)學(xué)報(bào),2010,27(5): 371-374．)

[13] WANG Jiayao,CUI Tiejun,WANG Guangxia．The Application of Graph Theory in Automatic Selection of Road Networks[J]．Journal of the PLA Institute of Surveying and Mapping,1985,1:79-86．(王家耀,崔鐵軍,王光霞．圖論在道路網(wǎng)自動(dòng)選取中的應(yīng)用[J]．解放軍測(cè)繪學(xué)院學(xué)報(bào),1985,1:79-86．)

[14] H E Zongyi．The Principle and Method of Map Data Processing Model[M]．Wuhan:Wuhan University Press, 2004．(何宗宜．地圖數(shù)據(jù)處理模型的原理與方法[M]．武漢:武漢大學(xué)出版社,2004．)

[15] CHEN Bo,WU Fang,QIAN Haizhong．Study on Road Networks’Auto-selection Algorithms[J]．Journal of Image and Graphics[J]．2008,13(12):2388-2393．(陳波,武芳,錢(qián)海忠．道路網(wǎng)自動(dòng)選取方法研究[J]．中國(guó)圖象圖形學(xué)報(bào),2008,13(12):2388-2393．)

[16] CHEN Bo．Study and Practice to the Automated Generalization of Road Networks[D]．Zhengzhou:Information Engineering University,2006．(陳波．道路網(wǎng)自動(dòng)綜合的研究與實(shí)踐[D]．鄭州:信息工程大學(xué),2006．)

[17] LI Muzi,XU Zhu,LI Zhilin．et al．A Hierarchical Random Graph Based Selection Method for Road Network Generalization[J]．Journal of Geo-information Science．2012,14 (16):719-726．(李木梓,徐柱,李志林,等．基于層次隨機(jī)圖的道路選取方[J]．地球信息科學(xué)學(xué)報(bào),2012,14(16): 719-726．)

[18] LIU Caifeng．Stroke Function-based Approach to Extracting Backbone of Urban Road Network[D]．Chengdu:Southwest Jiaotong University,2010．(劉彩鳳．基于路劃功能的城市道路主干網(wǎng)選取方法[D]．成都:西南交通大學(xué),2010．)

[19] HU Yungang,CHEN Jun,LI Zhilin．et al．Selective Omission of Road Features Based on Map Generalization[J]．Acta Geodaetica et Cartographica Sinica,2007,36(3):351-357．(胡云崗,陳軍,李志林,等．基于網(wǎng)眼密度的道路選取方法[J]．測(cè)繪學(xué)報(bào),2007,36(3):351-357．)

[20] DENG Hongyan．Research of Automated Generalization Base on Genetic Algorithm[D]．Zhengzhou:Information Engineering University,2003．(鄧紅艷．基于遺傳算法的自動(dòng)綜合研究[D]．鄭州:信息工程大學(xué),2003．)

[21] QIAN Haizhong．Research of Intelligent Automatic Cartographic Generalization and Process Control[D]．Zhengzhou:Information Engineering University,2006．(錢(qián)海忠．自動(dòng)制圖綜合以及過(guò)程控制的智能化研究[D]．鄭州:信息工程大學(xué),2006．)

[22] GUO Min,QIAN Haizhong,HUANG Zhishen．et al．Intelligent Road Network Selection Method Based on Cases Inductive Reasoning[J]．Journal of Image and Graphics,2013,18 (10):1343-1353．(郭敏,錢(qián)海忠,黃智深,等．采用案例歸納推理進(jìn)行道路網(wǎng)智能選取[J]．中國(guó)圖象圖形學(xué)報(bào), 2013,18(10):1343-1353．)

[23] SHI Chunyi,HUANG Changning,WANG Jiakang．Principle of Artificial Intelligence[M]．Beijing:Tsinghua University Press,1993．(石純一,黃昌寧,王家康．人工智能原理[M]．北京:清華大學(xué)出版社,1993．)

[24] LI J Y,NI Z W,LIU X,et al．Case-base Maintenance Based on Multi-layer Alternative-covering Algorithm[C]∥Proceedings of the Fifth International Conference on Machine Learning and Cybernetics 2006．Berlin:Springer 2006:2035-2039．

[25] GUO Min．Research on Intelligent Road-network Selection Method Based on Cases Reasoning[D]．Zhengzhou:Information Engineering University,2013．(郭敏．基于案例學(xué)習(xí)的道路網(wǎng)智能選取方法研究[D]．鄭州:信息工程大學(xué),2013．)

(責(zé)任編輯:叢樹(shù)平)

Intelligent Road-network Selection Using Cases Based Reasoning

GUO Min1,2,QIAN Haizhong1,HUANG Zhishen1,3,HE Haiwei1,LIU Hailong1
1．Institute of Geographical Spatial Information,Information Engineering University,Zhengzhou 450052,China;2．61175 Troops,Nanjing 210049,China;3 Surveying and Mapping Support Unit of South Xinjiang,Kashgar 844200,China

A new approach of intelligent road-network selection using cases based reasoning(CBR)is put forward．In this approach,learning and cognition techniques of human being in artificial intelligence are used to establish,learn and reason the cases of cartographers．First,it takes a certain area’s road-network selection result achieved from interactive selection of cartographic experts as reference templates, and transform the templates into selection cases after establishing the description structure of cases．Second,the cases are analyzed and reasoned with enhanced simplifying and generalizing methods so as to get more effective case model base．Finally,the computer finishes the similar road selection using CBR technique supported with the enhanced case model base．Compared with the past algorithms,the proposed approach uses enhanced road selection cases to simulate the thinking of human being,and CBR model to select similar road-work intelligently,which enhances the intelligence of traditional road selection methods．Examples and related analyzing and assessing results illustrate the scientificity and usability of the new approach．And further works to be improved are also suggested．

road-network;case;case model base;case based reasoning(CBR);intelligent roadnetwork selection

GUO Min(1986—),male,master,assistant enjineer,majors in automated generalization and geographic information science etc．

QIAN Haizhong

P283

A

1001-1595(2014)07-0761-10

2013-03-11

郭敏(1986—),男,碩士,助理工程師,研究方向?yàn)榭臻g數(shù)據(jù)自動(dòng)綜合、地理信息系統(tǒng)等。

E-mail:haizhongqian＠163．com

錢(qián)海忠

E-mail:qianhaizhong2005＠163．com

GUO Min,QIAN Haizhong,HUANG Zhishen,et al．Intelligent Road-network Selection Using Cases Based Reasoning[J]．Acta Geodaetica et Cartographica Sinica,2014,43(7):761-770．(郭敏,錢(qián)海忠,黃智深,等．道路網(wǎng)智能選取的案例類(lèi)比推理法[J]．測(cè)繪學(xué)報(bào),2014,43(7):761-770．)

10．13485/j．cnki．11-2089．2014．0120

國(guó)家自然科學(xué)基金(41171305;41171354;40701157);信息工程大學(xué)地理空間信息學(xué)院碩士學(xué)位論文創(chuàng)新與創(chuàng)優(yōu)基金(S201208;S201207)

修回日期:2014-04-02