劉文凱，劉啟亮，蔡建南

1. 中南大學(xué)有色金屬成礦預(yù)測與地質(zhì)環(huán)境監(jiān)測教育部重點實驗室，湖南 長沙 410083； 2. 中南大學(xué)地理信息系，湖南 長沙 410083

現(xiàn)實世界中的地理現(xiàn)象經(jīng)常表現(xiàn)為伴生關(guān)系，例如：生態(tài)領(lǐng)域中植被之間的共生關(guān)系(如濕地植物群落間生態(tài)位的重疊[1])、犯罪地理學(xué)中地理環(huán)境(或設(shè)施)與犯罪間的誘導(dǎo)關(guān)系(如酒精售賣點附近高犯罪率問題[2])以及城市規(guī)劃中不同類型興趣點之間在產(chǎn)業(yè)布局上的依賴關(guān)系(如學(xué)校與便利店的聚集關(guān)系[3])。此類頻繁發(fā)生在鄰近位置的事件集合通常被定義為空間同位模式(本文特指事件間均滿足互鄰近關(guān)系的團型同位模式[4])。發(fā)現(xiàn)空間同位模式對于深入理解空間要素間的交互關(guān)系具有重要意義，已經(jīng)廣泛應(yīng)用于生態(tài)學(xué)、犯罪學(xué)、城市規(guī)劃、交通運輸?shù)戎T多領(lǐng)域。

當(dāng)前空間同位模式挖掘方法主要包含兩個步驟[5]：①構(gòu)建空間要素實例的空間鄰域關(guān)系，生成候選空間同位模式實例；②計算候選空間同位模式的頻繁度(如參與指數(shù)[5])，并提取頻繁度超過給定閾值的空間同位模式及其分布區(qū)域。針對步驟①，當(dāng)前研究主要采用基于距離的策略(給定距離閾值約束下，一個空間要素實例的鄰域定義為與其距離小于該閾值的其他空間要素實例的集合)構(gòu)建鄰域關(guān)系，并采用實例連接的方法生成候選模式實例。為了提高候選模式實例生成的效率，一些改進(jìn)實例連接的方法被相繼提出，如部分連接[6]、無連接[7]及基于密度的方法[8]等。針對步驟②，一些學(xué)者相繼針對同位模式頻繁度的度量、閾值定義及局部同位模式識別開展研究。例如，為了量化空間同位模式實例間距離對頻繁度度量的影響，文獻(xiàn)[3]在參與指數(shù)基礎(chǔ)上考慮距離衰減定義了加權(quán)參與指數(shù)；為了緩解參與指數(shù)閾值設(shè)定的困難，文獻(xiàn)[9]采取參與指數(shù)進(jìn)行排序的方法選取N個最顯著的同位模式；文獻(xiàn)[10]假定所有同位模式參與指數(shù)服從正態(tài)分布，提出一種用迭代方法逐步挖掘相對顯著的空間同位模式來緩解距離閾值和參與指數(shù)設(shè)定的困難；文獻(xiàn)[11—12]借助統(tǒng)計檢驗的方法挖掘顯著同位模式，降低了參與指數(shù)閾值設(shè)定的主觀性。為了識別局部空間同位模式，一些基于區(qū)域劃分[13-15]與實例聚類分析[16-17]的方法被相繼提出。從空間同位模式的挖掘流程可以發(fā)現(xiàn)，空間要素實例的鄰域關(guān)系構(gòu)建起到了基礎(chǔ)性的作用，尤其當(dāng)空間要素的實例分布不均勻時，鄰域關(guān)系構(gòu)建的準(zhǔn)確性對挖掘結(jié)果具有直接影響：

(1) 錯誤的鄰域關(guān)系會影響實例生成的準(zhǔn)確性(過多或過少的構(gòu)建實例)，進(jìn)而影響空間同位模式頻繁度度量的準(zhǔn)確性，最終導(dǎo)致關(guān)聯(lián)模式的誤報或遺漏。以圖1(a)為例，一個包含4類空間要素的示例數(shù)據(jù)集中包含多個密度不一的區(qū)域，數(shù)據(jù)集中預(yù)設(shè)了一個全局同位模式{A,B,C}和一個局部同位模式{A,B,C,D}(位于區(qū)域I)。如圖1(b)所示，當(dāng)距離閾值過小時，低密度區(qū)域?qū)嵗裏o法生成，導(dǎo)致參與指數(shù)偏小({A,B,C}無法發(fā)現(xiàn))；當(dāng)距離閾值過大時，高密度區(qū)域生成過多錯誤實例，導(dǎo)致參與指數(shù)過高估計({A,B,C,D}錯誤識別為全局模式)。

(2) 當(dāng)前局部同位模式提取大多采用對候選實例聚類的策略識別同位模式的分布區(qū)域[16]，鄰域關(guān)系構(gòu)建不準(zhǔn)確也會造成局部關(guān)聯(lián)模式的誤報或遺漏。例如，采用文獻(xiàn)[16—17]方法發(fā)現(xiàn)圖1(a)中的局部關(guān)聯(lián)模式時，采用距離閾值過小時，低密度區(qū)域的實例無法生成，局部模式{A,B,C,D}無法發(fā)現(xiàn)或誤報。

為了提高空間要素實例鄰域關(guān)系構(gòu)建的準(zhǔn)確性，一些學(xué)者也開展了一些探索性的工作:

(1) 基于空間統(tǒng)計的方法，即利用某種空間統(tǒng)計的方法(如空間自相關(guān))估計一個全局最優(yōu)的距離閾值[9]。然而，該方法雖然避免了用戶對距離閾值的設(shè)定，但是全局統(tǒng)一的距離閾值無法在空間要素分布不均勻時建立正確的空間鄰域關(guān)系。采用文獻(xiàn)[9]中基于空間自相關(guān)方法對示例數(shù)據(jù)集估計的距離閾值為13.02，在此距離閾值下，區(qū)域I中的實例無法生成，計算模式{A,B,C}參與指數(shù)為0.4(低估)，同位模式{A,B,C,D}參與指數(shù)為0(遺漏)。

(2) 基于k近鄰的空間鄰域關(guān)系構(gòu)建策略，即一個空間要素實例的鄰域是與其最鄰近的k個其他類型空間要素實例的集合[10,13,18]。然而，k值的變化仍然對同位模式挖掘結(jié)果有較大影響，隨著k值增大，錯誤的實例增多(包含了噪聲點)，導(dǎo)致參與指數(shù)被過高估計(圖1(c))。

(3) 基于鄰近圖的空間鄰域關(guān)系構(gòu)建策略，即在所有要素實例構(gòu)建的鄰近圖中(如Delaunay三角網(wǎng))，一個空間要素實例的鄰域是在鄰近圖中與其存在鄰近關(guān)系的其他空間要素實例集合[19-20]?；卩徑鼒D所構(gòu)建的空間鄰域關(guān)系往往受限于所選鄰域圖的特性，例如，空間同位模式中要素實例間需要滿足互鄰近關(guān)系，而基于Delaunay三角網(wǎng)所構(gòu)建的空間鄰域關(guān)系中互為鄰域的空間要素實例最多為3個，導(dǎo)致了無法挖掘長度超過3的同位模式[19]。此外，鄰近圖的邊界誤差也容易導(dǎo)致不同密度區(qū)域的實例存在錯誤的鄰域關(guān)系。

圖1 示例數(shù)據(jù)集Fig.1 Simulated data set

為了克服鄰域關(guān)系構(gòu)建對空間同位模式挖掘準(zhǔn)確性和完整性的影響，本文依據(jù)數(shù)據(jù)本身的分布特征自適應(yīng)地構(gòu)建空間要素實例間的鄰域關(guān)系(即自然鄰域)，并在自然鄰域支持下自適應(yīng)發(fā)現(xiàn)由整體到局部的空間同位模式，降低人為設(shè)置鄰域參數(shù)(如鄰域距離閾值、鄰居數(shù)目)與數(shù)據(jù)實際分布不符合而帶來的挖掘誤差。

1 研究策略

空間同位模式本質(zhì)上來源于地理現(xiàn)象間自相關(guān)結(jié)構(gòu)的互相誘導(dǎo)關(guān)系(induced spatial autocorrelation)，即某個(些)空間要素的自相關(guān)結(jié)構(gòu)是受到其他具有自相關(guān)結(jié)構(gòu)要素的影響而產(chǎn)生[21]。空間同位模式的挖掘結(jié)果可能有兩種形式[22]：①空間要素的空間自相關(guān)是由其他空間要素的自相關(guān)結(jié)構(gòu)誘發(fā)的；②空間要素的空間自相關(guān)是由某些未知要素誘導(dǎo)產(chǎn)生的。本文對這兩種形式的同位模式不進(jìn)行區(qū)分。采用頻繁度度量指標(biāo)(如參與指數(shù))探測同位模式時，隨機分布的空間要素之間或隨機分布與聚集分布要素之間的頻繁度也會較高，但是這類由于隨機分布要素導(dǎo)致的同位模式并沒有地理含義，通常被視為虛假的同位模式[12,23]?；谏鲜龇治?，在發(fā)現(xiàn)同位模式時首先需要排除隨機分布空間要素的干擾，本文采用最鄰近指數(shù)法[24]識別隨機分布的空間要素。

進(jìn)而，僅針對呈現(xiàn)聚集分布的空間要素挖掘同位模式，分別針對每種候選同位模式建立鄰域關(guān)系。本文認(rèn)為空間要素實例間自然的鄰近關(guān)系需要滿足3個基本條件：

(1) 距離鄰近性約束：隨著兩個空間要素實例間的距離增大，兩者之間關(guān)聯(lián)緊密性隨之降低。因此空間要素實例與其鄰域間距離應(yīng)小于一定范圍。

(2) 密度一致性約束：在空間鄰域內(nèi)空間要素實例的密度應(yīng)盡量保持一致，密度的顯著變化預(yù)示鄰域關(guān)系的破壞。

(3) 關(guān)系緊密性約束：由社交網(wǎng)絡(luò)中好友關(guān)系的親密性度量可知，兩個關(guān)系緊密的空間鄰居需要互為鄰居且應(yīng)包含公共鄰居。

基于上述分析，自然鄰域可以定義為依據(jù)空間要素局部分布特征(即距離鄰近性、密度一致性與關(guān)系緊密性)而構(gòu)建的空間要素間的鄰近關(guān)系。自然鄰域旨在自適應(yīng)地構(gòu)建要素實例間的鄰近關(guān)系，避免在密度較稀疏區(qū)域同位模式實例構(gòu)建的遺漏，以及在密度較高區(qū)域同位模式實例構(gòu)建的冗余，且降低人為設(shè)置鄰域參數(shù)閾值對模式實例生成的干擾，保證同位模式實例生成的準(zhǔn)確性。

針對每種候選同位模式，采用自然鄰域構(gòu)建其模式實例，并采用頻繁度度量指標(biāo)(如參與指數(shù)指標(biāo))對候選模式進(jìn)行頻繁性度量。對于全局不頻繁的候選模式，可以進(jìn)一步借助鄰近圖(如Delaunay三角網(wǎng))描述其模式實例間的連通性，發(fā)現(xiàn)局部區(qū)域的同位模式。

基于上述研究策略，下面將對空間自然鄰域構(gòu)建與同位模式分布區(qū)域自適應(yīng)提取方法進(jìn)行具體闡述。

2 空間自然鄰域構(gòu)建

依據(jù)空間要素實例間自然鄰近關(guān)系評價的3條原則，本文首先提出了自然鄰域的構(gòu)建方法。

2.1 基于Delaunay三角網(wǎng)的距離鄰近性約束估計

如上文所述，每一個空間要素實例存在一定的鄰域范圍，即鄰域上限距離，處于該距離范圍內(nèi)的其他空間要素實例構(gòu)成了當(dāng)前空間要素實例的潛在鄰域。本文首先借助Delaunay三角網(wǎng)對鄰域距離上限進(jìn)行估計。Delaunay三角網(wǎng)可以一定程度上反映要素實例間的鄰近關(guān)系，其中一些過長的邊(如圖2(a)所示，不同密度區(qū)域間的邊，如實例15和51；噪聲實例之間的邊，如實例5和90)通常預(yù)示著鄰近關(guān)系的破壞，借助邊長的統(tǒng)計規(guī)律識別的長邊閾值可以用于估計鄰域上限距離。給定包含n個空間要素實例的空間數(shù)據(jù)集SDB，DT表示依據(jù)n個空間要素實例的空間位置所構(gòu)建的Delaunay三角網(wǎng)的邊長集合，針對任一的空間要素實例p，其鄰域上限距離估計值limitp表達(dá)如下

limitp=mean(DT)+SD(DT)

(1)

式中，mean(DT)表示邊長集合DT的均值；SD(DT)表示邊長集合DT的標(biāo)準(zhǔn)差。在鄰域上限距離約束下，進(jìn)一步給出候選鄰域的定義：

定義1候選鄰域：針對每個空間要素的實例p，在其鄰域上限距離內(nèi)的所有要素實例依據(jù)與p的距離大小升序排列，定義為p的候選鄰域集合，記為CN(p)。

圖2 距離鄰近性約束示例Fig.2 Spatial proximity constraint

要素實例p的候選鄰域表示了其空間鄰域的最大可能范圍，對候選鄰域內(nèi)實例按照與p的距離進(jìn)行排序可以對鄰近關(guān)系的緊密度進(jìn)行度量，也決定了后續(xù)對候選鄰域集合進(jìn)行篩選的先后次序，即先從與p距離近的要素實例進(jìn)行搜索。下面以圖1中的示例數(shù)據(jù)為例，對候選鄰域的構(gòu)建進(jìn)行闡述。圖2(a)和(b)中分別展示了示例數(shù)據(jù)集與區(qū)域I構(gòu)建的Delaunay三角網(wǎng)，鄰域上限距離如圖2(a)中圓所示。實例1(高密度區(qū)域)的候選鄰域集合為{25,8,12,2,27,9,26,13,28,4,11,29,14,10,3,62}，實例7(低密度區(qū)域)的候選鄰域集合為{23,22,20,75,6,17,21,74,16,15,19}，實例90(噪聲)的候選鄰域集合為{3,10,14,29,96,28,9,11,2}。

2.2 基于局部密度變異的密度一致性約束

在每個要素實例p的候選鄰域中進(jìn)一步依據(jù)密度一致性原則進(jìn)行篩選。p依次與其候選鄰域內(nèi)要素實例CNi(p)連接，并統(tǒng)計落入以p和CNi(p)間距離為直徑的圓中的其他空間要素實例個數(shù)ni。若空間要素實例p與候選鄰域集合中實例處于同一密度區(qū)域時，則ni應(yīng)該保持不變或者處于增加的狀態(tài)，當(dāng)ni下降時，則可能預(yù)示了兩種情況[25]：

(1) 空間要素實例與其候選鄰域集合內(nèi)實例處于不同的密度區(qū)域，如圖3(a)所示。以實例1和2為直徑的圓中包含3個實例，而以1和27為直徑的圓中包含2個實例，27表示了局部區(qū)域密度下降的位置，實例1與實例27處于不同的密度區(qū)域；

(2) 空間要素實例與其候選鄰域集合內(nèi)實例處于同一密度區(qū)域但鄰域方向改變，如圖3(b)所示。以實例7和21為直徑的圓中包含2個實例，而以7和74為直徑的圓中包含1個實例，雖然圓中包含實例數(shù)目下降，但是實例7與實例74處于同一密度區(qū)域，實例21和74表示了實例7在不同方向的鄰域?qū)嶓w。

本文針對上面第1種情況，將位于局部區(qū)域密度下降位置的要素實例定義為密度斷點(如實例27為實例1的密度斷點)。為了識別密度一致的鄰域，在此基礎(chǔ)上給出密度鄰域和密度一致鄰域的定義：

定義2密度鄰域：針對每個空間要素的實例p，識別第1個密度斷點前的所有候選鄰域集合中的實例，這些實例構(gòu)成p的密度鄰域，記為DN(p)。

定義3密度一致鄰域：針對每個空間要素的實例p，將其密度鄰域初始化為密度一致鄰域，遍歷p的斷點，若該斷點pbreak與p的密度鄰域有重疊(DN(pbreak)∩DN(p)≠Φ，則將該斷點與下一斷點之前的候選鄰域加入p的密度一致鄰域中，記為HN(p)，否則停止遍歷。

以圖2(a)中實例7和圖2(b)中實例1為例對密度鄰域與密度一致鄰域構(gòu)建進(jìn)行闡述。以實例7與CN(7)中各個實例為直徑的圓中落入實例的數(shù)目依次為{0,0,0,0,1,1,2,1,2,2,2}，密度斷點為{74}，則DN(7)={23,22,20,75,6,17,21}，實例7與實例74(DN(74)={75,76,77})密度鄰域存在重疊(兩者處于相同密度區(qū)域)，得HN(7)={23,22,20,75,6,17,21,74,16,15,19}。以實例1與CN(1)中各個要素為直徑的圓中落入實例的數(shù)目依次為{0,1,2,3,2,4,4,5,5,7,8,9,8,11,11,1}，密度斷點為{27,14,62}，得DN(1)={25,8,12,2}，由于實例1與實例27(DN(27)={26,13,4,28,11})密度鄰域不重疊(兩者處于不同的密度區(qū)域)，得HN(1)={25,8,12,2}。

2.3 基于共享鄰近的關(guān)系緊密性約束

在密度一致鄰域內(nèi)，進(jìn)一步對要素實例間的關(guān)系緊密性進(jìn)行約束。本文受到社交網(wǎng)絡(luò)(如微信)中好友關(guān)系的親密度評價的啟發(fā)對要素實例間的關(guān)系緊密度進(jìn)行度量。在社交網(wǎng)絡(luò)中兩個關(guān)系緊密的用戶需要同時滿足兩個條件：①兩人互為好友；②兩人具有公共好友。據(jù)此，本文定義了判斷兩個要素實例間關(guān)系緊密性的兩個約束條件；

(1) 互鄰域約束條件：兩個要素實例同時包含在二者的密度擴展鄰域內(nèi)；

(2) 共享鄰居約束條件：兩個要素實例的密度擴展鄰域有重疊。

在上述兩個約束條件的約束下，進(jìn)一步給出自然鄰域的定義：

定義4自然鄰域：針對每個空間要素的實例p，遍歷其密度一致鄰域中的要素實例qi，若p與qi互為密度一致鄰域且擁有共同密度一致鄰域(p∈HN(qi)，qi∈HN(p)且HN(p)∩HN(qi)≠Φ)，則將qi加入p的自然鄰域中，記為NN(p)，否則停止遍歷。

以圖2(a)中實例7、實例90和圖2(b)中實例1為例對自然鄰域的構(gòu)建進(jìn)行闡述?？臻g要素實例1與HN(1)中要素均滿足互鄰域約束條件和共享鄰居約束條件，得NN(1)={25,8,12,2}；實例7與實例74(HN(74)={75,76,77})不滿足互鄰域約束條件，得NN(7)={23,22,20,75,6,17,21}；實例90與實例3(HN(90)={3,10,14,29}，HN(3)={10,14,29,9,2})不滿足互鄰域約束條件，得NN(90)=Φ，即實例90為噪聲。

3 空間同位模式分布區(qū)域自適應(yīng)提取

要素實例間的自然鄰域構(gòu)建后，分別針對每種候選模式生成其實例，采用參與指數(shù)[5]對該模式的頻繁度進(jìn)行度量：

空間同位模式參與指數(shù)：對于長度為k的候選空間同位模式C={f1,f2,…,fk}，其參與指數(shù)定義如下

(2)

式中，|πfi(table_instance(C))|表示參與同位模式C的要素fi的實例數(shù)目；|instance(fi)|表示要素fi實例的數(shù)目。

若候選同位模式在整個研究區(qū)域內(nèi)的參與指數(shù)大于給定閾值，則將該模式識別為全局同位模式?，F(xiàn)有研究認(rèn)為有效的同位模式其參與指數(shù)一般應(yīng)大于0.5，因此本文將參與指數(shù)閾值設(shè)為0.5(文獻(xiàn)[12])。若候選同位模式參與指數(shù)小于0.5(即在全局不顯著)，進(jìn)一步借助模式實例間Delaunay三角網(wǎng)的連通性對候選同位模式的局部分布區(qū)域進(jìn)行探測：

(1) 針對候選同位模式中所有要素實例構(gòu)建Delaunay三角網(wǎng)，三角網(wǎng)的邊可以區(qū)分為兩種類型：連接候選模式要素實例的邊EI(如圖4(a)所示)與連接候選模式實例之間邊Eo(如圖4(b)邊1所示)。從每個候選模式實例出發(fā)，若兩個候選模式實例間所有邊長均小于統(tǒng)計約束條件SC，則將兩個候選模式實例進(jìn)行連通，直到每個候選模式實例均與滿足約束條件候選模式實例連通

SC=mean(Eo)+SD(Eo)

(3)

式中,mean(Eo)表示候選模式實例之間邊長平均值；SD(Eo)表示候選模式實例之間邊長的標(biāo)準(zhǔn)差。

(2) 在每個候選模式實例連通后構(gòu)成的子圖中，借助Delaunay三角網(wǎng)中三角形邊長共享特性搜索候選同位模式的分布區(qū)域邊界。若Delaunay三角網(wǎng)中邊僅存在于一個唯一的三角形，則該邊被識別為邊界邊，通過連接具有公共頂點的邊界邊生成候選同位模式的分布區(qū)域邊界，如圖4(c)所示。

(3) 在每個候選模式分布區(qū)域內(nèi)，若該候選模式的參與指數(shù)超過給定閾值且模式實例規(guī)模足夠多，則將該候選模式識別為一個局部的同位模式。候選模式的實例規(guī)模度量指數(shù)SI(C)定義如下

(4)

式中，|regional_instance(C)|表示C在相應(yīng)局部區(qū)域中的實例個數(shù)；|global_instance(C)|表示C在整個研究區(qū)域中的實例個數(shù)。

圖4 同位模式分布區(qū)域提取Fig.4 Discovery of localities of co-location pattern

4 試驗分析

4.1 模擬試驗與比較

本文首先設(shè)計了一組模擬試驗對本文方法的有效性進(jìn)行驗證，同時與當(dāng)前3種空間同位模式RCMNG[16]、RCMKNN[13]和多層次方法[17]進(jìn)行比較。本文方法需要設(shè)置參與指數(shù)閾值與實例規(guī)模度量指數(shù)閾值兩個參數(shù)。依據(jù)現(xiàn)有研究建議，本文將參與指數(shù)閾值設(shè)為0.5(文獻(xiàn)[12])，參考空間聚類領(lǐng)域?qū)Υ匾?guī)模的閾值設(shè)定，本文將實例規(guī)模度量指數(shù)閾值設(shè)為0.02(文獻(xiàn)[26])。依據(jù)文獻(xiàn)[16]的試驗分析，RCMNG方法中局部參與指數(shù)閾值設(shè)為0.07，鄰域距離根據(jù)文獻(xiàn)[9]中的L函數(shù)進(jìn)行估計；依據(jù)文獻(xiàn)[13]建議，RCMKNN方法中距離變化系數(shù)閾值設(shè)置為0.6，α參數(shù)設(shè)置為0.01；依據(jù)文獻(xiàn)[17]建議，多層次方法距離閾值也采用L函數(shù)估計。模擬數(shù)據(jù)生成步驟如下所示：

(1) 將整個研究區(qū)域(400×400)均勻地劃分為4個100×100的子區(qū)域，在每個區(qū)域隨機生成數(shù)目為nseed的種子點，如圖5(a)所示(為了方便說明，僅用一個區(qū)域說明模擬數(shù)據(jù)生成過程)。

(2) 每個區(qū)域內(nèi)，以每個種子點為圓心，以半徑rseed畫圓，在每個圓內(nèi)生成數(shù)目為ninstance的獨立分布的實例點并移除種子點，如圖5(b)所示。

(3) 以每個實例點為圓心，以給定半徑rinstance畫圓，在每個圓內(nèi)隨機生成數(shù)目為nfeature的同位模式要素實例并移除實例點，如圖5(c)所示。

(4) 在整個研究區(qū)域內(nèi)生成數(shù)目為nnoise的噪聲點(分布隨機且空間要素類型隨機)，如圖5(d)所示。

由上述模擬數(shù)據(jù)產(chǎn)生過程可以發(fā)現(xiàn)，nseed控制同位模式在某個子區(qū)域分布區(qū)域的數(shù)目，rseed控制同位模式分布區(qū)域的大小，通過修改rseed和ninstance的值，可以控制不同分布區(qū)域要素實例的密度。模擬數(shù)據(jù)均包含一個全局同位模式(分布于4個區(qū)域)和一個局部同位模式(分布于區(qū)域2和區(qū)域3)。首先將nseed和ninstance固定(區(qū)域1：nseed=4，ninstance=10；區(qū)域2：nseed=2，ninstance=10；區(qū)域3：nseed=2，ninstance=10；區(qū)域4：nseed=5，ninstance=10)。進(jìn)一步分別改變rseed、nfeature和nnoise探索要素實例密度變化、同位模式長度變化及噪聲數(shù)目變化對本文及對比方法影響。若挖掘結(jié)果區(qū)域和設(shè)定區(qū)域相交區(qū)域占挖掘結(jié)果區(qū)域和設(shè)定區(qū)域面積均大于50%以上時，本文認(rèn)為挖掘結(jié)果是正確的。本文采用召回率和精確率作為評定算法挖掘結(jié)果的定量標(biāo)準(zhǔn)。

圖5 模擬數(shù)據(jù)生成Fig.5 Experimental setup of synthetic data sets

4.1.1 要素實例密度變化對挖掘結(jié)果的影響

為了評估要素實例密度變化對挖掘結(jié)果的影響，首先將nnoise(50)和nfeature(區(qū)域1和區(qū)域4：nfeature=2，區(qū)域2、3：nfeature=3)取值固定，進(jìn)而4個區(qū)域的rseed隨機選擇10次(區(qū)域1和4的rseed取值范圍為10～30，區(qū)域2和3的rseed取值范圍為20～50)。本文方法與對比方法的試驗結(jié)果如圖6(a)—(c)所示。本文方法可以有效發(fā)現(xiàn)整體與局部的同位模式，而其他幾種方法的挖掘結(jié)果受要素實例密度變化的干擾較大：RCMNG方法計算的局部參與指數(shù)是基于局部子圖中要素實例個數(shù)與全局實例個數(shù)的比值，低密度區(qū)域或范圍較小的局部同位模式的要素實例數(shù)目相對較少，導(dǎo)致局部參與指數(shù)計算值普遍過小，容易出現(xiàn)遺漏；RCMKNN方法中當(dāng)要素密度變化時，鄰居數(shù)目k估計的誤差極易導(dǎo)致模式實例生成的錯誤，進(jìn)而造成挖掘結(jié)果經(jīng)常出現(xiàn)誤判和漏判的情況；多層次方法采用全局統(tǒng)一的距離閾值(估計的距離為30～40，遠(yuǎn)大于本文預(yù)設(shè)的閾值(2～5))，在生成候選模式實例時存在較多錯誤，故挖掘結(jié)果經(jīng)常出現(xiàn)誤判。

4.1.2 空間同位模式長度對挖掘結(jié)果的影響

為了在要素實例分布不均勻的前提下評估同位模式長度對挖掘結(jié)果的影響，首先將nnoise(50)、rseed(區(qū)域1和2：rseed=25，區(qū)域3：rseed=40，區(qū)域4：rseed=20)和rinstance(區(qū)域1和2：rinstance=5，區(qū)域3：rinstance=8，區(qū)域4：rinstance=4)取值固定，進(jìn)而改變nfeature的取值進(jìn)行試驗。針對每個nfeature隨機生成10組數(shù)據(jù)(共生成50組隨機數(shù)據(jù))，挖掘結(jié)果定量評價指標(biāo)取平均值。試驗結(jié)果如圖6(d)—(f)所示：本文方法的挖掘結(jié)果不受模式長度的影響，均可準(zhǔn)確識別預(yù)設(shè)的同位模式；RCMKNN方法的挖掘結(jié)果質(zhì)量在不同模式長度情況下波動較大，其主要原因在于鄰居數(shù)目k值的估計策略比較敏感；RCMNG與多層次方法的挖掘結(jié)果質(zhì)量在不同模式長度情況下波動較小，但是RCMNG方法由于局部參與指數(shù)估計偏低導(dǎo)致的漏判問題以及多層次方法由于候選模式實例生成誤差導(dǎo)致的誤判問題總是存在。

4.1.3 噪聲數(shù)量對挖掘結(jié)果的影響

為了在要素實例分布不均勻的前提下評估噪聲數(shù)量對挖掘結(jié)果的影響，首先將nfeature(區(qū)域1和4：nfeature=2，區(qū)域2和3：nfeature=3)、rseed(區(qū)域1和2：rseed=25，區(qū)域3：rseed=40，區(qū)域4：rseed=20)、rinstance(區(qū)域1和2：rinstance=5，區(qū)域3：rinstance=8，區(qū)域4：rinstance=4)取值固定，進(jìn)而改變nnoise的取值進(jìn)行試驗。針對每個nnoise隨機生成10組數(shù)據(jù)(共生成50組隨機數(shù)據(jù))，挖掘結(jié)果定量評價指標(biāo)取平均值。試驗結(jié)果如圖6(g)—(h)所示：本文方法對噪聲不敏感；RCMKNN方法對噪聲最為敏感，主要原因還是在于鄰居數(shù)目k值估計的不穩(wěn)定；RCMNG方法和多層次方法在不同噪聲情況下的表現(xiàn)相對穩(wěn)定，但是結(jié)果漏判與誤判問題依然存在。

圖6 模擬試驗對比Fig.6 Comparison of three methods

通過上述試驗可以發(fā)現(xiàn)：自然鄰域方法在不同密度、不同模式長度及噪聲數(shù)目情況下均可以可靠地構(gòu)建空間要素實例間鄰近關(guān)系，從而保證了同位模式實例生成的準(zhǔn)確性，進(jìn)而可以有效避免同位模式挖掘結(jié)果的誤判與遺漏問題。

4.2 犯罪同位關(guān)聯(lián)模式挖掘

進(jìn)一步采用本文方法挖掘犯罪事件、城市興趣點數(shù)據(jù)集中的空間同位模式。犯罪地理學(xué)研究表明，犯罪事件在空間上具有互相誘導(dǎo)關(guān)系而且受到城市地理環(huán)境的影響，發(fā)現(xiàn)犯罪事件間及犯罪與城市興趣點間的同位模式對于犯罪預(yù)防與犯罪管控具有重要價值[27]。本文以美國波特蘭市作為研究區(qū)域，收集了2014年1—3月傷害罪(740)、搶劫罪(188)和盜竊罪(7143)3種犯罪事件以及餐飲(食品、咖啡和餐館，共715條記錄)、娛樂設(shè)施(夜店和酒吧，共131條記錄)、車站(公交站點與車站，共1764條記錄)和購物場所(購物中心、商店、便利店和雜貨店，共715條記錄)4類興趣點。

本文方法挖掘結(jié)果共包含9個全局同位模式和36個局部同位模式，部分挖掘結(jié)果如表(1)所示。分析挖掘結(jié)果，可以發(fā)現(xiàn)：

(1) 犯罪與興趣點、不同犯罪類型之間均存在同位關(guān)系，充分說明了犯罪間的誘導(dǎo)關(guān)系與環(huán)境設(shè)施對犯罪事件的影響，可以為犯罪管控提供針對性指導(dǎo)意見。

(2) 某些同位模式在整個波特蘭市都是頻繁出現(xiàn)的(如{餐飲設(shè)施，傷害罪}、{娛樂設(shè)施，搶劫罪}和{餐飲設(shè)施，盜竊罪})，這表明這些模式是一種普遍模式，而某些同位模式僅發(fā)生在局部區(qū)域(如圖7所示局部同位模式)，這表明同位模式分布具有異質(zhì)性的特點，本文的挖掘結(jié)果可以為差異性犯罪防控提供參考。

以{娛樂設(shè)施，傷害罪}和{車站，傷害罪}兩個局部同位模式為例，對本文挖掘結(jié)果進(jìn)行分析。傷害罪分布于整個研究區(qū)域且分布不均勻(篇幅所限未進(jìn)行展示)，在研究區(qū)域中部的市中心最集中，在研究區(qū)域西部最稀疏。娛樂設(shè)施興趣點主要分布在研究區(qū)域中部和東南部，車站主要分布在研究區(qū)域西部、中部和東部部分區(qū)域(篇幅所限未進(jìn)行展示)。{娛樂設(shè)施，傷害罪}局部同位模式(如圖7(c)所示)主要是由于娛樂設(shè)施主要集中于市中心，酒吧、夜店等人員來源復(fù)雜、流動較大的興趣點誘發(fā)傷害性犯罪機率較大，未來應(yīng)進(jìn)一步加強管控；{車站，傷害罪}局部同位模式(如圖7(d)所示)主要出現(xiàn)在車站分布密集的市中心和東部部分區(qū)域，這說明人員流動和聚集是誘發(fā)傷害性犯罪的重要因素，但是該同位模式并沒有在車站最密集的西部區(qū)域出現(xiàn)，這間接說明西部區(qū)域的犯罪防控是比較有效的。

表1 興趣點與犯罪間的同位模式

5 結(jié)論與展望

本文提出了一種基于自然鄰域的空間同位模式自適應(yīng)挖掘方法，從距離鄰近性、密度變化一致性、關(guān)系緊密性3個角度建?？臻g數(shù)據(jù)的局部分布特征，能夠在空間要素實例分布不均情況下準(zhǔn)確構(gòu)建要素實例間鄰近關(guān)系(即自然鄰域)，并借助要素實例Delaunay三角網(wǎng)的連通性自適應(yīng)地發(fā)現(xiàn)局部的同位模式。通過模擬試驗與實例驗證發(fā)現(xiàn)：本文方法不需要人為設(shè)置參數(shù)構(gòu)建要素實例間的鄰近關(guān)系；與當(dāng)前幾種代表性方法比較，本文方法在要素實例分布不均勻的復(fù)雜情況下能更準(zhǔn)確、穩(wěn)定地發(fā)現(xiàn)全局與局部的同位模式，同時挖掘得到的犯罪與興趣點同位模式分布區(qū)域?qū)τ诜缸镱A(yù)防與管控具有一定的指導(dǎo)價值。

進(jìn)一步研究工作將主要集中在3個方面：①本文方法的復(fù)雜度約為2O(n2)(創(chuàng)建自然鄰域和構(gòu)建候選同位模式實例)+O(nlogn)(局部同位模式提取)，為了適應(yīng)在大規(guī)模數(shù)據(jù)集中的應(yīng)用需求需要進(jìn)一步研究自然鄰域的高效構(gòu)建方法；②本文采用經(jīng)驗閾值的策略設(shè)置參與指數(shù)閾值在實踐中可能存在一定偏差，未來需要進(jìn)一步研究參與指數(shù)的自適應(yīng)估計；③當(dāng)前空間要素的記錄數(shù)據(jù)多具有時間屬性，需要進(jìn)一步研究時空自然鄰域的構(gòu)建方法。