顧及空間分布與注記相關(guān)性的點(diǎn)要素注記配置算法

曹 聞，彭斐琳，童曉沖，戴浩然，張 勇

1. 鄭州大學(xué)地球科學(xué)與技術(shù)學(xué)院，河南 鄭州 450000； 2. 信息工程大學(xué)地理空間信息學(xué)院，河南 鄭州 450001； 3. 鄭州眾合景軒信息技術(shù)有限公司，河南 鄭州 450000

隨著大數(shù)據(jù)時代的到來，人們對大數(shù)據(jù)中所蘊(yùn)含的內(nèi)在機(jī)理和高價值信息有著迫切的需求和期待，數(shù)據(jù)可視化成為大數(shù)據(jù)分析不可缺少的工具[1-2]。在數(shù)據(jù)可視化中，各行業(yè)數(shù)據(jù)經(jīng)常利用地理信息技術(shù)將其整合到地理空間上進(jìn)行分析和表達(dá)，因此，地理空間數(shù)據(jù)可視化是大數(shù)據(jù)分析的重要基礎(chǔ)，通常以地圖的形式展示[3-4]。注記作為可視化產(chǎn)品中重要組成部分，是最直觀傳遞信息的要素[5]，由此，提升注記質(zhì)量成了研究的熱點(diǎn)和難點(diǎn)。

數(shù)據(jù)可視化中的空間對象分為點(diǎn)、線、面、體等形式[6-9]，其中，點(diǎn)要素注記的自動配置問題(point-feature label placement problem,PFLP)最為復(fù)雜，已被證明是NP-hard問題[10]。為了解決在龐大規(guī)模的組合優(yōu)化問題中尋找最優(yōu)解的難題，國內(nèi)外學(xué)者對此進(jìn)行了大量的研究。元啟發(fā)式算法是一種使用高級策略來探索空間的方法[11]，能在有限的時間內(nèi)找到一個較好的近似最優(yōu)解，目前已被廣泛應(yīng)用到點(diǎn)要素注記配置問題的研究中，如禁忌搜索、模擬退火算法、遺傳算法和蟻群算法等[12-15]。大部分學(xué)者通常以改進(jìn)元啟發(fā)算法為主，將所有點(diǎn)要素視為一個整體進(jìn)行解算，并未考慮到點(diǎn)要素之間的獨(dú)立性，而隨著點(diǎn)要素數(shù)量的增多，組合優(yōu)化的規(guī)模呈爆炸式增長，導(dǎo)致算法求解的效率極低及求解質(zhì)量不佳。因此，有部分學(xué)者利用點(diǎn)要素的空間分布特征來指導(dǎo)注記配置問題的解算，主要分為兩類：一是采用聚類分組的方法對點(diǎn)要素進(jìn)行分析和求解。文獻(xiàn)[16]提出利用最短距離聚類的方式分析點(diǎn)要素空間分布特征的設(shè)想。文獻(xiàn)[17—18]通過構(gòu)建點(diǎn)要素沖突圖和拉格朗日松弛法進(jìn)行聚類，將其劃分為多個數(shù)據(jù)簇進(jìn)行求解。文獻(xiàn)[19]利用基于密度的聚類方法(density-based spatial clustering of applications with noise，DBSCAN)將問題空間劃分成多個子問題空間，進(jìn)而利用蟻群算法對子問題進(jìn)行求解。該類算法雖然有效地縮短了注記配置的計算時間，提高了注記效率，但其聚類的過程忽略了點(diǎn)要素注記之間的影響，從而導(dǎo)致聚類得到的不同子數(shù)據(jù)集之間的獨(dú)立性方面存在著模糊性和粗差。二是通過規(guī)劃注記次序指導(dǎo)注記配置過程的方式來優(yōu)化注記配置結(jié)果。文獻(xiàn)[20]指出利用Voronoi圖描述點(diǎn)要素的空間分布特征和要素在注記配置過程中的相互影響性，通過規(guī)劃自由度來指導(dǎo)注記配置沿著簡單、高效和高質(zhì)量的方向進(jìn)行。文獻(xiàn)[21]提出周圍要素較為密集且注記候選區(qū)域面積較小的點(diǎn)要素優(yōu)先注記，對注記配置的順序進(jìn)行了優(yōu)化。該類算法利用注記次序指導(dǎo)了注記配置過程，雖然能在一定程度上提高注記配置質(zhì)量，但在空間分布稠密的情況下易受到點(diǎn)要素注記間強(qiáng)干擾性的影響，從而導(dǎo)致算法求解更易落入局部最優(yōu)陷阱。

針對上述問題，本文通過挖掘點(diǎn)要素數(shù)據(jù)集的整體空間分布特征、局部空間分布特征和注記相關(guān)性，提出了一種顧及空間分布和注記相關(guān)性的點(diǎn)要素注記配置算法，并通過試驗證明該算法的有效性。

1 算法原理

稠密型點(diǎn)要素的注記自動配置問題主要受限于注記效率和質(zhì)量，針對該問題，本文考慮到點(diǎn)數(shù)據(jù)集的空間分布特征和注記間的相關(guān)性，設(shè)計了一種注記關(guān)聯(lián)度模型，繼而對點(diǎn)要素數(shù)據(jù)集進(jìn)行空間聚類分析和注記次序規(guī)則制定，最后采用多層次元啟發(fā)算法求解注記配置問題的近似最優(yōu)解。

1.1 注記關(guān)聯(lián)度模型

1.1.1 注記候選位置模型

注記候選位置模型的選擇是注記配置的重要基礎(chǔ)之一[22-23]，直接影響著注記配置的質(zhì)量和效率。為了增加固定位置模型的靈活性和降低滑動模型的運(yùn)算量，采用文獻(xiàn)[19]提出的多級多方位模型，如圖1所示，可通過細(xì)化參數(shù)半徑r和等分角θ兩個參數(shù)提升空間利用率，但勢必帶來較大的運(yùn)算量而降低注記效率。因此，綜合考慮注記配置質(zhì)量和運(yùn)算時間兩方面的平衡，本文選擇等分角θ為45°，并使用優(yōu)先級度量構(gòu)建8位置模型。其中，圖1中的數(shù)字從小至大表示注記位置優(yōu)先級由強(qiáng)至弱的程度，同時為了注記美觀性，將點(diǎn)要素的符號外接圓加入多級多方位模型中，即要求點(diǎn)要素符號化區(qū)域半徑r1要小于注記多級半徑r，實線橢圓和虛線矩形分別為不同位置、字符高度、字符串長度所形成的外接橢圓和最小外接矩形。

圖1 多級多方位注記候選模型Fig.1 The multi-levels and multi-orientations label candidate location model

點(diǎn)要素注記自動配置算法通常是以某種規(guī)則選擇不同的注記候選位置得到近似最優(yōu)解，在此過程中每個已注記點(diǎn)要素的位置會直接影響到隨后點(diǎn)要素的注記位置，因此如何利用其多樣性和互干擾性指導(dǎo)算法求解是值得重點(diǎn)關(guān)注的問題。

1.1.2 注記關(guān)聯(lián)度規(guī)則

在點(diǎn)要素注記配置問題的求解過程中，注記間的干擾會導(dǎo)致算法極易陷入局部最優(yōu)陷阱和求解效率低下。由于注記最小候選外接矩形包括了點(diǎn)要素所有的候選位置，因此可根據(jù)注記最小候選外接矩形為計算基礎(chǔ)設(shè)計相應(yīng)的注記關(guān)聯(lián)度規(guī)則量化不同點(diǎn)要素在注記配置過程的相互干擾關(guān)系。

假設(shè)圖面待配置點(diǎn)要素的集合為P={p1,p2,…,pN}，點(diǎn)要素pi和pj的最小候選外接矩形分別為Ri和Rj，定義一個二進(jìn)制變量αij表示點(diǎn)pi和pj之間是否存在相互干擾性。若αij=0，表示點(diǎn)要素pi和pj在注記配置過程中不存在干擾性，即Ri∩Rj=φ，不需考慮二者注記的先后順序；若αij=1，表示點(diǎn)要素pi和pj間具有干擾性，需考慮二者具體注記對注記配置的影響，如圖2中點(diǎn)要素pi和pj，Ri∩Rj≠φ，表示其最小候選外接矩形存在相交的部分，則該相交部分定義為注記影響面Aij，即Aij=Ri∩Rj。顯然，二進(jìn)制變量α和注記影響面A均具有對稱性，即αij=αji和Aij=Aji。

圖2 注記影響面Fig.2 Label influence surface pattern

考慮到點(diǎn)要素間的干擾性將直接影響到注記配置的效率和質(zhì)量，依據(jù)點(diǎn)要素最小注記外接矩形之間的關(guān)系，定義注記支持度η和注記關(guān)聯(lián)度ξ兩個變量對點(diǎn)要素注記間的干擾程度進(jìn)行量化描述，以此挖掘點(diǎn)要素數(shù)據(jù)集合的局部空間分布特性和注記相關(guān)性。

1.1.2.1 注記支持度ηi

注記支持度是指任一點(diǎn)要素pi在注記配置過程中與其注記最小候選外接矩形相關(guān)的其他點(diǎn)要素的個數(shù)，記為ηi

(1)

注記支持度ηi反映了點(diǎn)要素pi注記后影響到數(shù)據(jù)集中其他點(diǎn)要素的個數(shù)，數(shù)值越大說明更多的點(diǎn)要素需根據(jù)pi的注記位置進(jìn)行調(diào)整，以避免注記出現(xiàn)重疊和沖突問題。根據(jù)注記支持度ηi的物理意義，可將所有參與注記配置的點(diǎn)要素概括為獨(dú)立點(diǎn)、直接關(guān)聯(lián)點(diǎn)和間接關(guān)聯(lián)點(diǎn)3類。

(1) 獨(dú)立點(diǎn)。對于點(diǎn)要素pi，如果相對于其他任意點(diǎn)要素pj(i≠j)均存在Ri∩Rj=φ，則稱pi為獨(dú)立點(diǎn)，如圖2中pt和ps。獨(dú)立點(diǎn)形成的數(shù)據(jù)集合稱為獨(dú)立點(diǎn)集，記為ΩI(ΩI?P)。在注記配置的過程中，獨(dú)立點(diǎn)注記位置的隨機(jī)性選擇會降低算法尋優(yōu)速度，因此可根據(jù)注記位置的優(yōu)先性和圖面美觀性直接注記。

注記支持度ηi通過統(tǒng)計點(diǎn)要素pi直接關(guān)聯(lián)點(diǎn)的個數(shù)來描述其局部空間分布特性，數(shù)值越大表示其局部空間分布越稠密，將其視為優(yōu)先注記點(diǎn)就意味著其他關(guān)聯(lián)點(diǎn)要素注記位置的可選擇性將減小，導(dǎo)致注記配置質(zhì)量不佳。

1.1.2.2 注記關(guān)聯(lián)度ξi

注記支持度ηi雖然描述了點(diǎn)要素的局部空間分布特征，但忽略了存在關(guān)聯(lián)性點(diǎn)要素間的相關(guān)性，點(diǎn)要素pi和pj間注記影響面Aij和Aji相等，由于兩點(diǎn)注記最小候選外接矩形不同，因此二者的互干擾程度也將不同。如圖3(a)所示，點(diǎn)要素pj優(yōu)先注記后，注記影響面Aij覆蓋點(diǎn)要素pi候選區(qū)域中的8個區(qū)塊；而圖3(b)中點(diǎn)要素pi優(yōu)先注記后，注記影響面Aji覆蓋點(diǎn)要素pj候選區(qū)域中的4個區(qū)塊。因此需引入注記關(guān)聯(lián)度ξi描述點(diǎn)要素注記間的相關(guān)性。

圖3 注記關(guān)聯(lián)度原理Fig.3 Label relevance principle

假設(shè)點(diǎn)要素pi優(yōu)先注記對點(diǎn)要素pj的后續(xù)注記位置的干擾概率Pij可定義為

(2)

(3)

式中，ωk表示干擾概率Pij等間隔區(qū)間對應(yīng)的權(quán)值，其中0<ω1<…<ωk<…<ωM。注記關(guān)聯(lián)度ξi描述了點(diǎn)要素pi優(yōu)先注記后對其局部區(qū)域內(nèi)其他點(diǎn)要素的干擾程度，量化了注記間的相關(guān)性。

綜上所述，通過注記支持度ηi和注記關(guān)聯(lián)度ξi兩個參數(shù)制定點(diǎn)要素pi的注記關(guān)聯(lián)規(guī)則，以此描述點(diǎn)要素pi的局部空間分布特征和注記互相關(guān)性，從而為注記配置求解提供先驗輔助決策信息。

1.2 基于注記關(guān)聯(lián)度模型的空間分布特征分析

稠密型點(diǎn)要素數(shù)據(jù)集的空間分布是較為復(fù)雜的，會存在一定數(shù)量的獨(dú)立點(diǎn)或不相關(guān)的多個子數(shù)據(jù)集，而這些點(diǎn)要素和子集在整體答解時，會引入較大的模糊性和干擾性，同時注記候選位置模型的多樣性會使注記組合規(guī)模隨點(diǎn)要素數(shù)量的增加呈指數(shù)型增長，從而導(dǎo)致算法求解質(zhì)量不佳和效率降低等問題，其根本原因在于忽略了點(diǎn)要素數(shù)據(jù)集的整體空間分布特征。

空間聚類算法能夠發(fā)現(xiàn)空間實體對象的空間聚集模式，通常被用來揭示其內(nèi)部分布規(guī)律和空間結(jié)構(gòu)特征，在地理空間數(shù)據(jù)挖掘領(lǐng)域得到了廣泛應(yīng)用。其中，DBCSAN算法能較好地應(yīng)用于點(diǎn)要素注記配置研究中[19]，有效降低問題求解的復(fù)雜度和提升注記配置的效率。DBSCAN空間聚類算法是通過判斷點(diǎn)是否落在另一點(diǎn)搜索鄰域范圍內(nèi)確定兩點(diǎn)之間是否存在關(guān)聯(lián)性，其關(guān)鍵在于搜索半徑和核心點(diǎn)判斷閾值兩個參數(shù)的確定，在注記配置問題中的搜索半徑和核心點(diǎn)判斷閾值通常選擇點(diǎn)要素注記的候選區(qū)域和1。如圖4(a)所示，點(diǎn)4、6、7、8被歸為獨(dú)立點(diǎn)，但實際其注記存在互相干擾性，容易出現(xiàn)注記疊加的現(xiàn)象。為了適應(yīng)點(diǎn)要素注記配置的特點(diǎn)，利用注記關(guān)聯(lián)度模型中的直接關(guān)聯(lián)點(diǎn)和間接關(guān)聯(lián)點(diǎn)兩個集合進(jìn)行遞歸類推最終得到互不關(guān)聯(lián)的獨(dú)立點(diǎn)集ΩI和M個子數(shù)據(jù)集Ωk,k∈[1,M]，繼而消除具有獨(dú)立性點(diǎn)集對注記配置求解產(chǎn)生的模糊性和干擾性，如圖4(b)所示，獨(dú)立點(diǎn)集可根據(jù)注記位置優(yōu)先性和圖面美觀性直接注記，而關(guān)聯(lián)點(diǎn)集則視為一個局部整體進(jìn)行問題求解，從而全局問題轉(zhuǎn)換為多個局部問題提升注記配置解算效率和注記質(zhì)量。

圖4 空間聚類算法Fig.4 Spatial clustering based on association model

空間聚類算法主要是對點(diǎn)數(shù)據(jù)集的空間聚集性進(jìn)行數(shù)據(jù)挖掘和分析，雖然降低了互不關(guān)聯(lián)的數(shù)據(jù)集對注記配置解算的干擾性和模糊性，但由于沒有充分利用子集中內(nèi)部點(diǎn)要素間的干擾性，將導(dǎo)致無法獲得更佳的注記質(zhì)量。

1.3 基于注記關(guān)聯(lián)度模型的次序規(guī)則

對關(guān)聯(lián)點(diǎn)子數(shù)據(jù)集進(jìn)行注記配置是旨在有限的空間內(nèi)獲取最大化可注記數(shù)量，而點(diǎn)要素注記之間的干擾性其實反映的是這些點(diǎn)要素之間的空間競爭關(guān)系，因此該注記配置求解問題也可被視為注記的取舍問題。在注記配置求解過程中，點(diǎn)要素注記的取舍是根據(jù)之前的注記結(jié)果來判斷是否存在合適的空間配置注記，同時該注記也會影響到之后點(diǎn)要素能否注記。注記配置算法通常以隨機(jī)次序進(jìn)行注記，忽略了點(diǎn)要素數(shù)據(jù)集的內(nèi)在空間結(jié)構(gòu)和秩序信息，從而無法得到更加合理的注記結(jié)果。

注記關(guān)聯(lián)度模型通過定義注記支持度ηi和注記關(guān)聯(lián)度ξi兩個參數(shù)分別描述點(diǎn)要素pi的局部空間分布特征和其直接關(guān)聯(lián)點(diǎn)注記間的相關(guān)性，本文依次按照兩個參數(shù)值增序?qū)c(diǎn)要素進(jìn)行排序，構(gòu)建基于增序注記關(guān)聯(lián)度模型的次序規(guī)則，其中，注記支持度ηi對點(diǎn)要素間的干擾程度具有強(qiáng)相關(guān)性，而注記關(guān)聯(lián)度ξi具有弱相關(guān)性，因此基于增序注記關(guān)聯(lián)度次序可表示為：對于不同規(guī)模的點(diǎn)要素集合，先以注記支持度ηi從小到大對所有點(diǎn)要素進(jìn)行排序；然后對相同注記支持度ηi的點(diǎn)要素再按照注記關(guān)聯(lián)度ξi從小到大排序；最后對兩個參數(shù)均相同的點(diǎn)要素按照隨機(jī)的方式進(jìn)行排序。如圖5所示，增序注記關(guān)聯(lián)度模型較降序注記關(guān)聯(lián)度模型的注記次序規(guī)則，可以有效降低優(yōu)先注記點(diǎn)要素對后續(xù)待注記點(diǎn)要素的干擾性，指導(dǎo)著注記配置過程，提高算法的尋優(yōu)速率，從而使近似最優(yōu)解更加逼近最優(yōu)解。

圖5 不同次序規(guī)則結(jié)果Fig.5 Labeling cases for different labeling orders

1.4 基于注記關(guān)聯(lián)度模型框架的注記自動配置

注記關(guān)聯(lián)度模型框架(annotation association model framework，AAMF)是通過基于注記關(guān)聯(lián)度模型的DBSCAN空間聚類算法和次序規(guī)則挖掘點(diǎn)要素的空間分布信息和注記相關(guān)性，進(jìn)而對注記配置算法求解進(jìn)行指導(dǎo)。基于注記關(guān)聯(lián)度模型框架下的注記配置通過制定注記質(zhì)量評價函數(shù)、沖突檢測方法和多層次元啟發(fā)算法等環(huán)節(jié)獲取更具合理性的注記配置結(jié)果。

1.4.1 注記質(zhì)量評價函數(shù)

注記配置旨在獲得最大化清晰、美觀和可讀的無沖突注記數(shù)目，因此本文參照文獻(xiàn)[24—25]中的方法以無沖突的注記數(shù)因子Fo、注記位置的優(yōu)先性因子Fp和注記的關(guān)聯(lián)性因子Fa構(gòu)建注記質(zhì)量評價函數(shù)F

F=λ1Fo+λ2Fp+λ3Fa

(4)

式中，λ1、λ2、λ3分別為各因子對注記質(zhì)量影響力的占比系數(shù)，一般而言λ1=0.5，λ2=0.3，λ3=0.2，但其中關(guān)聯(lián)性與人眼能識別出的最小距離有關(guān)，不能準(zhǔn)確衡量歧義距離，因此設(shè)置λ3=0。設(shè)質(zhì)量評價函數(shù)較小對應(yīng)著較好的注記配置結(jié)果，因此點(diǎn)要素注記配置的目標(biāo)是獲得最小化質(zhì)量評價函數(shù)值。

1.4.2 注記沖突檢測

點(diǎn)要素注記配置過程中，要求注記之間不可出現(xiàn)重疊或壓蓋現(xiàn)象，因此，在注記配置的過程中需制定注記沖突檢測方法加以解決。目前常用的空間索引方法主要有R樹空間索引和格網(wǎng)空間填充等多種方法[26-27]。R樹索引是以規(guī)則矩形的方式進(jìn)行碰撞檢測，對于不規(guī)則的地物要素與存在旋轉(zhuǎn)等情況存在著查詢不準(zhǔn)確的缺點(diǎn)，浪費(fèi)大量的圖面空間。格網(wǎng)空間填充索引是使用一種行排序的空間曲線填充方式進(jìn)行編碼[28]，原理簡單易懂，在沖突碰撞檢測過程中只需要判斷某點(diǎn)注記所在位置的格網(wǎng)是否被占用，相當(dāng)于一個局部小范圍的遍歷尋址，同時對于不規(guī)則的地物要素有較強(qiáng)的適應(yīng)性和穩(wěn)健性。因此，本文考慮到矢量背景要素符號的不規(guī)則性及點(diǎn)狀要素的注記旋轉(zhuǎn)等因素，采用格網(wǎng)空間填充的索引方式進(jìn)行沖突檢測。

1.4.3 多層次元啟發(fā)式算法

點(diǎn)數(shù)據(jù)集的空間分布通常疏密不均，經(jīng)空間聚類后關(guān)聯(lián)點(diǎn)子數(shù)據(jù)集中的點(diǎn)要素數(shù)量不均勻。蟻群算法、模擬退火算法和遺傳算法常應(yīng)用于解決點(diǎn)要素注記配置問題，但當(dāng)關(guān)聯(lián)點(diǎn)集中點(diǎn)要素數(shù)量較少時，直接求解則會導(dǎo)致容易陷入局部最優(yōu)等問題，因此需要針對不同數(shù)量的點(diǎn)要素數(shù)據(jù)集設(shè)計多層次元啟發(fā)算法提升其普適性和穩(wěn)健性。

多層次元啟發(fā)算法是依據(jù)關(guān)聯(lián)點(diǎn)集的大小采用不同搜索策略的元啟發(fā)式算法進(jìn)行求解。首先根據(jù)數(shù)據(jù)集中點(diǎn)要素的數(shù)量定義一級、二級和三級3種等級的數(shù)據(jù)集，同時設(shè)置兩個閾值分別為：低閾值δ1和高閾值δ2(δ1,δ2∈N+,δ1<δ2)，當(dāng)點(diǎn)要素數(shù)量n<δ1(δ1∈[1，10])，即為一級數(shù)據(jù)集。利用注記無沖突性的要求，采用文獻(xiàn)[14]中注記沖突調(diào)整的方式進(jìn)行注記配置。針對具有注記沖突的點(diǎn)要素更新注記方向的選擇，能更快地獲得較優(yōu)的注記結(jié)果。點(diǎn)要素數(shù)量δ1δ2，即為三級數(shù)據(jù)集，依據(jù)文獻(xiàn)[14]中精英保留策略進(jìn)行問題求解。而模擬退火算法與蟻群算法對二級和三級數(shù)據(jù)集解算方式相同，分別參考文獻(xiàn)[14]和文獻(xiàn)[19]的方法進(jìn)行迭代尋優(yōu)。3種元啟發(fā)式算法試驗參數(shù)取值見表1。

表1 元啟發(fā)式參數(shù)Tab.1 Metaheuristic parameter

2 試驗與分析

為了驗證本文所提注記關(guān)聯(lián)度模型對點(diǎn)要素注記自動配置算法的優(yōu)越性，利用網(wǎng)絡(luò)爬蟲技術(shù)從某地圖網(wǎng)站獲取鄭州市興趣點(diǎn)POI數(shù)據(jù)，以其隨機(jī)生成3000和6000點(diǎn)規(guī)模的數(shù)據(jù)集合為試驗數(shù)據(jù)，采用模擬退火算法、蟻群算法和遺傳算法討論和分析反映注記關(guān)聯(lián)度模型框架對提升點(diǎn)要素注記自動配置算法效率和質(zhì)量的意義。試驗與分析中的所有算法均通過Visual C++編程實現(xiàn)，試驗環(huán)境的處理器和內(nèi)存分別為Intel(R) Core(TM) i5-8500 3.0 GHz和8 GB。

2.1 顧及空間分布和注記關(guān)聯(lián)性點(diǎn)要素注記配置對比試驗

點(diǎn)要素注記自動配置的質(zhì)量和效率主要受到點(diǎn)要素數(shù)量和注記方向多樣性的影響。本文依據(jù)數(shù)據(jù)集的空間分布特征與注記相關(guān)性構(gòu)建基于注記關(guān)聯(lián)度模型的算法框架AAMF，并應(yīng)用于元啟發(fā)式算法來進(jìn)行點(diǎn)要素注記配置試驗，主要包括基于注記關(guān)聯(lián)度模型框架下的模擬退火算法AAMF-SA、遺傳算法AAMF-GA和蟻群算法AAMF-ACA，考慮到數(shù)據(jù)集空間分布的稀疏稠密特征對基于注記關(guān)聯(lián)度模型算法效果的影響，設(shè)計在常用的8種注記密度ρ為5%、10%、15%、20%、25%、30%、35%和40%下,比較AAMF算法與傳統(tǒng)算法的優(yōu)劣性。試驗以所有的點(diǎn)要素視為同一細(xì)節(jié)層級為前提，采用模擬退火算法、遺傳算法和蟻群算法比較隨機(jī)次序規(guī)則R1、基于降序注記關(guān)聯(lián)度模型的次序規(guī)則R2和基于增序注記關(guān)聯(lián)度模型的次序規(guī)則R3的試驗結(jié)果，討論與分析基于注記關(guān)聯(lián)度模型的次序規(guī)則在不同元啟發(fā)式算法下的有效性。每組試驗重復(fù)10次取平均值，點(diǎn)要素數(shù)量低閾值δ1與高閾值δ2分別為7和100，參數(shù)r、r1和注記字體分別設(shè)置為10、5和12像素。記錄每組試驗的耗時T和注記質(zhì)量評價函數(shù)值E，試驗結(jié)果見表2—表7和圖6、圖7。

圖6 算法注記配置結(jié)果Fig.6 Labeling result of algorithm

圖7 注記結(jié)果細(xì)節(jié)對比Fig.7 Detailed comparison of labeling results

表2 注記密度為5%～20%模擬退火算法的試驗結(jié)果統(tǒng)計Tab.2 The statistical results of SA with label density range from 5% to 20%

由表2、表3可知，不同的規(guī)則算法對注記配置結(jié)果產(chǎn)生了較大的影響。首先，從次序規(guī)則上來說，基于增序注記關(guān)聯(lián)度模型的次序規(guī)則R3的質(zhì)量評價函數(shù)值相較于隨機(jī)次序規(guī)則R1降低3～8.5，相較于基于降序注記關(guān)聯(lián)度模型的次序規(guī)則R2降低6～15.8，規(guī)則R3的結(jié)果均優(yōu)于規(guī)則R1和R2；其次，AAMF-SA算法比SA算法求解的效率平均提升16.78%，且評價函數(shù)值降低了12.28；通過試驗分析可以看出，AAMF-SA取得了較好的注記配置結(jié)果和注記效率。

表3 注記密度為25%～40%模擬退火算法的試驗結(jié)果統(tǒng)計Tab.3 The statistical results of SA with label density range from 25% to 40%

由表4、表5可知，基于增序注記關(guān)聯(lián)度模型的次序規(guī)則R3比隨機(jī)次序規(guī)則R1的質(zhì)量評價函數(shù)值平均降低5.95、比基于降序注記關(guān)聯(lián)度模型的次序規(guī)則R2平均降低12.82，由此可見，次序規(guī)則R3優(yōu)于規(guī)則R1和R2，提高了注記配置質(zhì)量。AAMF-GA算法比GA算法求解效率平均提高18.1%；其評價函數(shù)值平均降低9.2。其中，在注記密度為5%下的6000點(diǎn)規(guī)模試驗中，AAMF-GA的評價函數(shù)值比GA降低32.8，注記質(zhì)量大幅度提升，但其注記效率比GA降低了4.97%，這是因為空間聚類算法將大規(guī)模單一數(shù)據(jù)集分成了若干個子數(shù)據(jù)集，減少了要素注記間的干擾性，使得每個子數(shù)據(jù)集求解時不斷地進(jìn)行迭代優(yōu)化從而提升了注記質(zhì)量，同時也增加了算法的迭代時間，由此損失的效率是可以接受的。

表4 注記密度為5%～20%遺傳算法的試驗結(jié)果統(tǒng)計Tab.4 The statistical results of GA with label density range from 5% to 20%

表5 注記密度為25%～40%遺傳算法的試驗結(jié)果統(tǒng)計Tab.5 The statistical results of GA with label density range from 25% to 40%

蟻群算法試驗結(jié)果見表6、表7。首先，AAMF-ACA算法比ACA算法效率平均提升17.70%，評價函數(shù)值平均降低7.71；其次，基于增序注記關(guān)聯(lián)度模型的次序規(guī)則R3比隨機(jī)次序規(guī)則R1的質(zhì)量評價函數(shù)值平均降低了8.11，同時，比基于降序注記關(guān)聯(lián)度模型的次序規(guī)則R2平均降低15.6。試驗分析表明，AAMF-ACA能有效提升注記配置效率和注記配置質(zhì)量。

表6 注記密度為5%～20%蟻群算法的試驗結(jié)果統(tǒng)計Tab.6 The statistical results of ACA with label density range from 5% to 20%

表7 注記密度為25%～40%蟻群算法的試驗結(jié)果統(tǒng)計Tab.7 The statistical results of ACA with label density range from 25% to 40%

綜上所述，基于注記關(guān)聯(lián)度模型框架能較好地應(yīng)用于模擬退火算法、遺傳算法和蟻群算法，并取得了注記效率和注記質(zhì)量的提高?；谠鲂蜃⒂涥P(guān)聯(lián)度模型的次序規(guī)則R3取得了最好的配置優(yōu)化效果，其次是隨機(jī)次序規(guī)則R1，基于降序注記關(guān)聯(lián)度模型的次序規(guī)則R2配置結(jié)果質(zhì)量最差。結(jié)合表2—表7試驗結(jié)果統(tǒng)計進(jìn)行分析，首先，在注記密度為5%～40%下，規(guī)則R3比規(guī)則R1注記配置的質(zhì)量評價函數(shù)值分別降低3.0～5.7、5.0～8.4、6.9～8.5、4.6～9.2、6.0～8.9、5.2～10.9、5.5～9.8、7.3～9.4，比次序規(guī)則R2降低5.9～10.7、8.6～15.4、13.0～17.5、11.4～18.2、13.1～17.6、13.4～17.3、14.8～17.6、15.1～17.5。數(shù)據(jù)分析表明，隨著注記密度由5%至40%，注記次序規(guī)則R3與R1、R2的差值由小逐漸增大，這是因為當(dāng)數(shù)據(jù)集空間分布較為稀疏時，大部分的點(diǎn)注記候選區(qū)域只影響少量個別其他點(diǎn)注記候選區(qū)域，無論采用哪種注記次序，注記都有較大的可能性找到空間放置，因此，在這種情況下，3種規(guī)則的注記配置結(jié)果區(qū)別較小。當(dāng)數(shù)據(jù)集空間分布較為稠密時，注記間的沖突性和關(guān)聯(lián)性增大，規(guī)劃以增序注記關(guān)聯(lián)度模型的次序令關(guān)聯(lián)性較小的點(diǎn)要素優(yōu)先注記，能大幅度地減少已配置的注記對待配置注記的影響，對注記配置的結(jié)果有著較好的優(yōu)化效果。其次，新算法相較于傳統(tǒng)元啟發(fā)式算法效率平均提高了28.92%、19.23%、16.47%、16.42%、14.30%、14.59%、13.79%、10.41%，且質(zhì)量評價函數(shù)值平均下降了26.5、13.4、8.7、6.1、4.5、4.1、3.5、2.5。由此可見，注記效率和質(zhì)量的提升幅度有著明顯的下滑趨勢，這是因為注記密度變大，數(shù)據(jù)集的空間分布較為集中，空間聚類后獲得最大子集的點(diǎn)要素數(shù)量與整體數(shù)據(jù)集相差無幾，空間聚類算法已經(jīng)不能大幅度地減少干擾性和降低計算復(fù)雜度，同時又增加了聚類這一過程的耗時，從而降低了注記效率和質(zhì)量的提升，因此，當(dāng)點(diǎn)要素空間分布較為稠密時，空間聚類算法對注記配置的作用會減小。

圖6和圖7展示了對6000點(diǎn)要素使用AAMF算法與傳統(tǒng)算法得到的同一區(qū)域注記結(jié)果局部對比圖和細(xì)節(jié)對比圖。在本組注記配置結(jié)果中，AAMF算法獲得的無沖突注記數(shù)總計3218個，在圖6中展示的局部區(qū)域有256個注記，傳統(tǒng)算法獲得的無沖突注記數(shù)總計3065個，在圖6中展示的局部區(qū)域212個注記，AAMF算法取得了153個注記的提升。圖7(a)和7(b)分別是圖6(a)和圖6(b)的典型細(xì)節(jié)注記結(jié)果示例，由該圖可以看出，圖7(a)中的點(diǎn)注記方向和注記數(shù)量更有優(yōu)勢，其基于注記關(guān)聯(lián)度模型的空間聚類算法與注記次序規(guī)則，既降低了組合優(yōu)化問題的復(fù)雜度又提高了每個點(diǎn)要素可注記概率，取得了較好的注記效果。而圖7(b)注記數(shù)目和注記方向較AAMF算法的注記配置結(jié)果有一定的差距，這是因為其整體求解方式不能反映單個點(diǎn)要素或者某塊獨(dú)立數(shù)據(jù)集的注記配置的需求，且注記的隨機(jī)性無法為配置過程提供先驗輔助決策信息，令注記配置的結(jié)果質(zhì)量不佳。因此，本文提出的AAMF算法相較于傳統(tǒng)算法更有優(yōu)勢。

2.2 與MapLex智能標(biāo)注系統(tǒng)的對比試驗

為了對比新算法與MapLex智能標(biāo)注系統(tǒng)的注記質(zhì)量，采用基于關(guān)聯(lián)度模型框架的模擬退火算法與ArcGIS 10.5版本下的MapLex注記配置進(jìn)行對比，由于MapLex無法統(tǒng)計注記方向，僅將無沖突注記個數(shù)作為比較標(biāo)準(zhǔn)，試驗統(tǒng)計結(jié)果見表8。試驗參數(shù)r、r1和注記字體分別設(shè)置為2、2和12像素，MapLex系統(tǒng)中r、r1和字體設(shè)置為2、2和9磅。

表8 試驗結(jié)果統(tǒng)計Tab.8 The statistical result of the experimental data

由表8的試驗統(tǒng)計結(jié)果可知，新算法獲得的無沖突注記數(shù)均比MapLex智能標(biāo)注系統(tǒng)多，注記配置質(zhì)量更為合理，但新算法在時間效率方面仍然需要得到進(jìn)一步提高。

3 結(jié) 論

本文針對稠密型點(diǎn)狀要素注記自動配置問題，通過構(gòu)建注記關(guān)聯(lián)度模型對點(diǎn)要素數(shù)據(jù)集的全局空間分布特征、局部空間分布特征以及注記之間的相關(guān)性進(jìn)行表達(dá)和描述，進(jìn)而利用基于注記關(guān)聯(lián)度模型的多層次元啟發(fā)式算法求解點(diǎn)要素注記配置的近似最優(yōu)解。其中，用于描述點(diǎn)要素數(shù)據(jù)集整體空間分布特征的空間聚類算法對稀疏性點(diǎn)要素數(shù)據(jù)集的注記配置更具優(yōu)勢，而用于描述局部空間分布特征和注記相關(guān)性的次序規(guī)則對稠密性點(diǎn)要素數(shù)據(jù)集的注記配置更具優(yōu)勢。新算法雖然通過空間數(shù)據(jù)挖掘在注記配置效率和質(zhì)量上得到了明顯提升，但仍然存在不足之處：①注記關(guān)聯(lián)度模型缺乏圖面空白區(qū)域指導(dǎo)點(diǎn)要素具體注記方向的能力，需進(jìn)一步地提升注記配置算法的效率和質(zhì)量；②新算法使用格網(wǎng)空間填充方法雖然可有效解決不規(guī)則對象和旋轉(zhuǎn)等復(fù)雜環(huán)境下的注記沖突檢測問題，但隨著注記范圍的增大，會產(chǎn)生占用內(nèi)存空間過大和局部尋址效率低下的問題；③需進(jìn)一步研究如何在質(zhì)量評價函數(shù)中根據(jù)人們視覺制定更為合理的歧義性因子，以增強(qiáng)注記的可讀性和視覺美觀性。