基于網(wǎng)格空間團的多級同位模式挖掘方法

劉宇情，王麗珍，楊培忠，樸麗莎

(1.云南大學(xué) 信息學(xué)院，云南 昆明 650504；2.滇池學(xué)院 理工學(xué)院，云南 昆明 650228)

隨著遙感技術(shù)、空間定位系統(tǒng)和智慧城市等地理信息處理技術(shù)的快速發(fā)展，空間數(shù)據(jù)量與日俱增.空間數(shù)據(jù)中隱藏著無數(shù)有價值的知識，如何挖掘這些知識并應(yīng)用到實際生活變得至關(guān)重要.作為空間數(shù)據(jù)挖掘的一個重要分支，空間同位模式挖掘旨在從空間數(shù)據(jù)中發(fā)現(xiàn)空間特征之間的關(guān)聯(lián)關(guān)系.空間同位模式是空間特征集的一個子集，其實例頻繁出現(xiàn)在彼此的鄰域中，互為鄰居.空間同位模式挖掘近年來得到了發(fā)展，并在許多領(lǐng)域得到了廣泛的應(yīng)用，例如公共安全[1]、公共健康[2]、生態(tài)學(xué)[3]、社會科學(xué)[4]、城市規(guī)劃[5]等.

空間特征是指空間中不同種類的事物，空間實例是這種類別事物在具體空間位置上的出現(xiàn).由于空間實例分布的異質(zhì)性和空間特征實例數(shù)量的差異，空間實例通常分布不均，這導(dǎo)致一些同位模式只存在于有限的局部子區(qū)域中，于是空間同位模式被分為全局同位模式和區(qū)域同位模式.多級同位模式挖掘指挖掘到全局和區(qū)域所有的同位模式.

現(xiàn)有的多級同位模式挖掘研究存在諸多問題.多級同位模式挖掘方法往往沿用傳統(tǒng)同位模式挖掘中實例間的歐氏距離作為其鄰近關(guān)系的度量準則，未考慮空間數(shù)據(jù)分布的網(wǎng)格特性.例如城市網(wǎng)格布局作為城市規(guī)劃和設(shè)計的基本模式，廣泛應(yīng)用于現(xiàn)代城市的管理和規(guī)劃中；在生態(tài)環(huán)境中，由于水流和植被分布的相互作用，物種分布呈現(xiàn)網(wǎng)格狀分布的現(xiàn)象.空間實例呈現(xiàn)網(wǎng)格分布的現(xiàn)象在現(xiàn)實中非常普遍，只考慮歐氏距離的度量會忽略網(wǎng)格對角線實例間的鄰近關(guān)系，可能會遺漏某些有潛在價值的同位模式.區(qū)域劃分的目的是通過合理的劃分策略，使劃分的區(qū)域內(nèi)部具有相同的模式分布.現(xiàn)有基于點數(shù)據(jù)聚類的區(qū)域劃分方法[6-7]存在一系列不足，由于空間數(shù)據(jù)存在特征實例異質(zhì)性，只考慮點數(shù)據(jù)的密度和位置容易忽略特征實例數(shù)量的差異，可能導(dǎo)致劃分的區(qū)域內(nèi)部缺乏相同的模式分布，使得劃分的區(qū)域不合理.現(xiàn)有的多級同位模式挖掘方法采用先挖掘全局同位模式，將全局非頻繁同位模式識別為候選區(qū)域同位模式，并逐一篩選這些候選區(qū)域同位模式，以挖掘區(qū)域頻繁同位模式.這種傳統(tǒng)的多級模式挖掘方法需要消耗大量的時間與空間，計算模式的全局參與度.該方法未采用有效的剪枝策略，導(dǎo)致時間復(fù)雜度較高.

針對現(xiàn)有的多級同位模式挖掘存在的問題，本文利用網(wǎng)格劃分技術(shù)重新定義實例之間的鄰近關(guān)系，利用網(wǎng)格鄰近關(guān)系和模式參與實例的反單調(diào)性提出有效的剪枝策略，使得提出的挖掘算法不僅能夠有效地提高挖掘效率，而且挖掘結(jié)果更貼合實際應(yīng)用.在區(qū)域劃分階段，采用網(wǎng)格密度峰值聚類的方法，基于網(wǎng)格中2 階網(wǎng)格空間團定義不同網(wǎng)格的相似性，使得區(qū)域劃分更合理.因為多級同位模式挖掘方法旨在挖掘出全局和區(qū)域頻繁的同位模式，但是通過將全局不頻繁的模式作為區(qū)域候選模式并逐階篩選，時間復(fù)雜度非常高.本文考慮模式的分布情況，提出先挖掘區(qū)域同位模式再推導(dǎo)全局同位模式的新穎挖掘框架，時間效率得到了很大的提升.

1 相關(guān)工作

Huang 等[8]提出空間同位模式的挖掘，定義參與度來衡量同位模式的頻繁程度.基于參與度的反單調(diào)特性，提出類Apriori 的挖掘方法，即join-based 算法[8].隨后，人們提出各種方法來提高同位模式挖掘算法的效率，例如Partial-join 和joinless 算法[9].由于挖掘同位模式和空間實例的團關(guān)系密不可分，人們提出一系列基于團的同位模式挖掘方法，如基于order-cliques 的算法[10]、基于極大團的算法[11].傳統(tǒng)的同位模式挖掘方法只著眼于在全局空間中頻繁出現(xiàn)的同位模式，忽略了空間數(shù)據(jù)分布異質(zhì)性的存在.由于一些模式只在局部子區(qū)域內(nèi)頻繁出現(xiàn)，而全局同位模式挖掘方法無法發(fā)現(xiàn)這些頻繁出現(xiàn)的區(qū)域模式，忽略了局部區(qū)域信息.區(qū)域同位模式挖掘引起了人們的關(guān)注，它旨在尋找在局部子區(qū)域中頻繁存在的同位模式及相應(yīng)的頻繁區(qū)域.

區(qū)域同位模式的挖掘方法主要可以分為以下2 類.1）基于區(qū)域識別的方法，它們通過對空間實例或模式實例進行聚類來識別模式的頻繁區(qū)域，計算區(qū)域內(nèi)模式的參與度來評價模式的頻繁程度.Eick 等[12]將具有最大適配度函數(shù)的聚類結(jié)果作為挖掘同位模式的區(qū)域.Mohan 等[13]提出基于鄰域圖的方法，發(fā)現(xiàn)區(qū)域同位模式的頻繁區(qū)域.Deng 等[14]提出多級挖掘方法，將全局不頻繁模式作為候選區(qū)域模式，通過Delaunay Triangular 自適應(yīng)聚類方法識別模式的頻繁區(qū)域.Liu 等[15]提出基于自然鄰居的多級同位模式挖掘方法，建立新的局部自適應(yīng)鄰近關(guān)系，但該方法對空間特征的數(shù)量比較敏感.Liu 等[16]提出k 近鄰中加入道路網(wǎng)格約束和啟發(fā)式的兩階段方法，通過蒙特卡羅模擬方法評估模式的統(tǒng)計意義，識別每個區(qū)域同位模式的頻繁區(qū)域.2）基于區(qū)域劃分的方法.這種方法將整個研究區(qū)域劃分為多個子區(qū)域，分別在每個子區(qū)域內(nèi)挖掘同位模式.基于區(qū)域劃分方法的主要挑戰(zhàn)在于找到適當?shù)目臻g劃分方案，目前的研究提出了各種劃分區(qū)域的方法.Celik 等[17]提出基于四叉樹的結(jié)構(gòu)來挖掘頻繁的區(qū)域同位模式，但需要大量的先驗知識.Ding 等[18]使用監(jiān)督聚類算法，將基于網(wǎng)格的地理空間劃分為任意形狀的區(qū)域.Qian 等[19]提出基于k 近鄰的分區(qū)方法，用 k=1 初始化原始區(qū)域，利用迭代方法合并具有近似距離閾值和一定比例的同類型模式的區(qū)域，得到具有相似數(shù)據(jù)分布的目標區(qū)域.Wang等[20]提出挖掘區(qū)域同位模式的頻繁主義和貝葉斯框架，開發(fā)基于概率擴展的啟發(fā)式方法，尋找任意形狀的區(qū)域.

本文引用網(wǎng)格密度峰值聚類方法，通過2 階網(wǎng)格空間團來判斷不同網(wǎng)格的相似度進行區(qū)域劃分.基于數(shù)據(jù)分布的網(wǎng)格特性提出有效的剪枝策略，設(shè)計高效的多級同位模式挖掘算法，解決了傳統(tǒng)多級方法時間效率低的問題.本文提出從區(qū)域同位模式推導(dǎo)出全局同位模式的新挖掘框架，避免了將區(qū)域同位模式誤判為全局同位模式的情況，顯著減少了計算時間.這些創(chuàng)新使得算法在實際應(yīng)用中能夠更高效地挖掘多級同位模式，得到有意義且可靠的結(jié)果.

2 概念與方法

2.1 基本概念

給定空間特征集F={f1,f2,···,fn}，表示整個空間數(shù)據(jù)集中不同事務(wù)類型的集合.空間實例集S=S1∪S2∪···∪Sn中，Si(1 ≤ i ≤ n)為特征為 fi的空間實例集合.為了區(qū)別實例，給每個空間實例o 指定實例編號id，于是空間實例一般用三元組＜實例所屬特征，實例編號，(x,y)＞表示，x、y 表示該實例在空間中的具體位置坐標.給定距離閾值d，根據(jù)距離d 劃分網(wǎng)格，而實例的鄰域范圍為以該實例坐標為中心、邊長為2d 的矩形范圍.若一個實例位于另一個實例的鄰域內(nèi)，則稱2 個實例滿足空間鄰近關(guān)系R.如圖1 所示，將滿足鄰近關(guān)系的實例用一條實線連接，實例A1 的鄰域為深色虛線矩形，A1 的鄰居實例有{B1,B2,C1,D1,D2,D3}.空間特征集F 的子集c 稱為空間同位模式，模式c 中特征的個數(shù)k 稱為模式的階數(shù).在空間鄰近關(guān)系R 下，不同特征實例組成的團關(guān)系（兩兩實例之間都滿足空間鄰近關(guān)系R）稱為網(wǎng)格空間團；若該團包含模式c 的所有特征且不存在相同的特征實例，則該團被稱為k 階網(wǎng)格空間團，該團的實例集合稱為模式的一個行實例.模式的所有行實例組成了模式的表實例.表實例中不重復(fù)的實例被稱為模式c 的參與實例.如圖1 所示為包含4 個空間特征的區(qū)域數(shù)據(jù)示例，右側(cè)列出了一些模式的參與實例.圖1 中，包含A1 的網(wǎng)格空間團有{A1,B1,C1,D1}，{A1,B1,C1,D2}，{ A1,B2,C1,D1}，{ A1,B2,C1,D2}，{A1,D3}.

圖1 包含4 個空間特征A、B、C、D 的區(qū)域數(shù)據(jù)示例（左圖）和一些模式的參與實例(右圖)Fig.1 Example of regional data containing four spatial features A,B,C,D (left figure)and some examples of pattern participation instances (right figure)

2.2 區(qū)域劃分方法

密度峰值聚類[21]是基于密度的聚類算法，能夠自動確定聚類中心點和聚類數(shù)目，該聚類算法依據(jù)以下2 點獲取聚類結(jié)果.1）簇中心的局部密度較高；2）簇中心離其他簇中心距離較遠.密度峰值聚類算法中需要設(shè)置一些參數(shù)，算法對參數(shù)較敏感.本文提出自適應(yīng)網(wǎng)格密度峰值聚類算法，在簇分配的過程中利用網(wǎng)格中2 階網(wǎng)格空間團，度量網(wǎng)格之間的相似度.

定義1 網(wǎng)格密度.給定網(wǎng)格g，該網(wǎng)格密度定義為網(wǎng)格內(nèi)空間實例數(shù)量.

式中：Ins (g)為網(wǎng)格內(nèi)的實例個數(shù).

定義2 網(wǎng)格相對距離.給定網(wǎng)格g，網(wǎng)格相對距離 δg定義為網(wǎng)格密度大于 ρg的網(wǎng)格g'與網(wǎng)格g 的距離的最小值，即

式中：distg′g為網(wǎng)格g 和網(wǎng)格g'的中心點之間的距離，也稱為網(wǎng)格g 和網(wǎng)格g'之間的距離.

定義3 中心網(wǎng)格.中心網(wǎng)格gcenter的密度和相對距離經(jīng)過歸一化處理后，密度和距離都大于其閾值.

簇中心滿足以下2 個條件：1）簇中心的密度大；2）離其他簇的距離較遠.因為密度和距離的單位不一致，對網(wǎng)格密度和相對距離進行歸一化處理，max(ρ)、min(ρ)分別為所有網(wǎng)格密度的最大值和最小值，max (δ)和min (δ)分別為所有網(wǎng)格相對距離的最大值和最小值.根據(jù)式(3)、(4)計算得到所有網(wǎng)格歸一化處理后的密度和相對距離格密度的平均值和標準差，為為所有網(wǎng)格歸一化處理后的網(wǎng)所有網(wǎng)格歸一化處理后的網(wǎng)格相對距離的平均值和標準差.標準差的引入使得算法更具有魯棒性[22]，在數(shù)據(jù)分析中平均值加標準差是常用的標準化指標，能夠提供有關(guān)數(shù)據(jù)點分布情況的信息，輔助異常值的檢測.這里的異常值指局部密度和相對距離都異常大的數(shù)值，符合作為簇中心的條件，所以將歸一化處理后的結(jié)果計算平均值加標準差并作為閾值：

區(qū)域劃分的目的是通過合理的劃分策略，使劃分的區(qū)域內(nèi)存在盡可能相同的區(qū)域模式.為了使具有相同模式的區(qū)域盡可能地聚集在一起，在聚類過程中需要進一步考慮網(wǎng)格內(nèi)部的模式.在同位模式挖掘中，2 階網(wǎng)格空間團探究的是不同空間位置上對象的屬性之間的相關(guān)性，通過分析2 階網(wǎng)格空間團可以預(yù)測出更高階模式的潛在聯(lián)系，所以考慮利用2 階網(wǎng)格空間團度量不同網(wǎng)格的相似度.

定義4 網(wǎng)格相似度.給定中心網(wǎng)格gcenter和待分配的網(wǎng)格g，2 個網(wǎng)格的相似度定義如下：

gcenter和g 的2 階模式并集為c={c1，···，ci，···，cn}，其中n 為2 階模式并集中的種類個數(shù)；gcenter(ci)、g(ci)分別為中心網(wǎng)格gcenter和網(wǎng)格g 內(nèi)包含的2 階模式 ci的網(wǎng)格空間團的數(shù)量.0 ≤Sg(gcenter,g)≤1.0，相似度越接近于1，表示待分配的網(wǎng)格與中心網(wǎng)格內(nèi)部的2 階模式種類趨于相同且數(shù)量相近，則2 個網(wǎng)格內(nèi)部的同位模式相似度越高.如圖2（網(wǎng)格內(nèi)的實例都存在鄰近關(guān)系，證明見引理6）所示，網(wǎng)格2 中包含的2 階模式有{A,C}、{A,D}、{C,D}，且模式網(wǎng)格空間團個數(shù)分別為9、6、6.網(wǎng)格4 中的2 階模式有{A,C}、{A,D}、{C,D}、{A,E}、{C,E}、{D,E}，模式的網(wǎng)格空間團個數(shù)分別為4、4、4、2、2、2.這2 個網(wǎng)格的相似度

圖2 說明網(wǎng)格相似度度量的用例Fig.2 Examples for illustrating grid similarity measure

算法1(AG-DPC)將整個研究區(qū)域S 劃分成d×d 的網(wǎng)格（行1）.根據(jù)定義1 計算每個網(wǎng)格密度并將其存儲到集合 ρ中（行2），在獲得每個網(wǎng)格的密度后，根據(jù)定義2 計算網(wǎng)格的相對距離（行3）.根據(jù)定義3，找到簇中心，即中心網(wǎng)格（行4～7）.對非中心網(wǎng)格進行分配，將非中心網(wǎng)格分配到距離較近且相似度較高的中心網(wǎng)格（行8～10），得到劃分的 區(qū)域（行11）.

2.3 多級同位模式挖掘

多級同位模式挖掘旨在挖掘全局和局部區(qū)域2 個不同層次中頻繁出現(xiàn)的同位模式.傳統(tǒng)的多級同位模式挖掘算法未考慮數(shù)據(jù)的網(wǎng)格特性，將全局不頻繁的模式作為區(qū)域候選模式，進行一一篩選，在挖掘多級同位模式時需要消耗大量時間和空間搜索和存儲模式的表實例，而生成表實例對計算模式的參與度是非必要的[23]，如圖3(a)所示為傳統(tǒng)的多級模式挖掘框架.本文提出從區(qū)域同位模式推出全局模式的新框架（見圖3(b)），采用搜索參與實例的策略，結(jié)合網(wǎng)格特性和參與實例的反單調(diào)性提出剪枝策略，以有效挖掘多級同位模式.

圖3 多級同位模式挖掘框架上的對比Fig.3 Comparison of multi-level co-location pattern mining framework

定義5 區(qū)域參與度PI、區(qū)域參與率PR.給定模式c 及其所在區(qū)域r，該模式c 中特征fi在區(qū)域r 的區(qū)域參與率 PR(r,c,fi)和模式c 的區(qū)域參與度 PI(r,c)表示為

式中：R(r,fi)為區(qū)域r 中特征 fi的實例集合，Obj(r,c,fi)為fi在區(qū)域r 中模式c 的參與實例集.模式c 在區(qū)域r 的參與度 PI(r,c)定義為模式c 的所有空間特征中參與率的最小值.

定義6 區(qū)域同位模式RCP.給定模式c 及其所在區(qū)域r，若該模式c 在區(qū)域r 內(nèi)的參與度PI(r,c)≥頻繁度閾值 θ，則稱模式c 在區(qū)域r 內(nèi)是區(qū)域頻繁同位模式，簡稱區(qū)域同位模式.

如圖1 所示，在區(qū)域中，假設(shè)區(qū)域頻繁度閾值為0.4，PI(r,{B,C})=1/2 ＞ 0.4，則模式{B,C}為區(qū)域同位模式.

定義7 全局同位模式GCP.給定模式c 和面積占比閾值 ε，若該模式所在的頻繁區(qū)域面積與全局面積的占比A(c)大于 ε，則稱該模式c 為全局同位模式.

式中：ri為模式c 的某個頻繁區(qū)域，Rc為模式c 的頻繁區(qū)域集，S(ri)為區(qū)域 ri的區(qū)域面積，global-Area 為整個研究空間的面積，0≤A(c)≤1.0.全局模式指在整個研究空間中頻繁出現(xiàn)的模式.本文的全局模式考慮了分布情況，可以避免將不小于全局頻繁度閾值的區(qū)域同位模式誤判為全局同位模式的情況.

引理1 區(qū)域模式在區(qū)域內(nèi)滿足先驗性原理.在區(qū)域r 中，若區(qū)域模式是區(qū)域頻繁的，則其子模式也是區(qū)域頻繁的；若區(qū)域模式不是區(qū)域頻繁的，則其超模式也是區(qū)域不頻繁的.

證明：若模式c 在區(qū)域r 中頻繁即滿足PI(r,c)≥θ；在區(qū)域內(nèi)參與度滿足向下閉合性[8]，c 的子集 c′，c′?c，則不等式 PI(r,c′)≥PI(r,c)≥θ恒成立，即c 的子集一定是區(qū)域頻繁的.同理可得，若區(qū)域模式不是區(qū)域頻繁的，則其超模式也一定不是區(qū)域頻繁的.

引理2 全局模式滿足先驗性原理.若全局模式是頻繁的，則其子模式也是頻繁的；若全局模式不是頻繁的，則其超模式也是非頻繁模式.

證明：由于本文的全局模式是由區(qū)域同位模式推出的，區(qū)域同位模式在其頻繁區(qū)域中滿足先驗性原理，一個模式在區(qū)域中是頻繁的，那么其子模式也是區(qū)域頻繁的(引理1).子模式subc 所占的區(qū)域面積一定大于等于該模式c 的區(qū)域面積，即整個研究空間面積globalArea 是常數(shù)值，可以得到

即ε ≤A(c)≤A(subc)，所以若全局模式是頻繁的，則其子模式也是頻繁的.因為一個模式在區(qū)域中是非頻繁的，其超模式也是非頻繁的，所以超模式supc 所占的區(qū)域面積一定小于該模式c 的區(qū)域面積.同理可得若全局模式不是頻繁的，則其超模式是非頻繁模式.

當計算區(qū)域模式的參與度時，不需要再花費大量時間和空間存儲模式的表實例，只需要存儲表實例中不重復(fù)的實例即參與實例.在區(qū)域內(nèi)從低階向高階挖掘區(qū)域同位模式，需要進一步考慮高階的候選參與模式，以減小搜索空間.

定義8 候選參與實例集.在區(qū)域r 中，特征f 在k(k ＞2)階同位模式c 中的候選參與實例集是f 在模式c 的所有包含f 的k-1 階子模式中的參與實例集的交集，表示為

引理3在 CObj(r,c,f)中搜索特征f在模式c 中的參與實例集是完備的，即

證明：若 Obj(r,c′,f)已知，當挖掘區(qū)域同位模式時，c′?c，對于f 在c 中任一參與實例o∈Obj(r,c′,f)，選取c 的某條行實例RI 包含o，取RI 中包含 c′的所有特征的行實例 RI′，則 RI′中一定包含實例o，即Obj(r,c,f)?Obj(r,c′,f).若Obj(r,c′,f)未知，則用區(qū)域特征集R(r,f)代替，R(r,f)一定包含特征f 在區(qū)域模式c 中的所有參與實例，即Obj(r,c,f)?R(r,f)，所以O(shè) bj(r,c,f)?CObj(r,c,f).

引理4在區(qū)域r 中，對于區(qū)域同位模式c 及其特征f(f∈c)，特征f在區(qū)域同位模式的參與度上界表示為RUPR(r,c,f)=||CObj(r,c,f)||/|R(r,f)|.若RUPR(r,c,f)＜θ，則該模式一定不是區(qū)域頻繁同位模式.

證明：根據(jù)引理3可知，Obj(r,c,f)?CObj(r,c,f)，則||Obj(r,c,f)||≤||CObj(r,c,f)||，因此PR(r,c,f)=|Obj(r,c,f)|/|R(r,f)|≤||CObj(r,c,f)||/| R(r,f)|＜θ，PI(r,c)＜θ.

基于參與度上界的剪枝策略.根據(jù)引理4 可知，若模式c 中存在某一特征f 的參與度上界RUPR(r,c,f)＜θ，則該模式一定不是區(qū)域同位模式.在得到模式的候選參與實例集后，可以直接計算區(qū)域模式的參與度上界.在區(qū)域內(nèi)，若該模式的參與度上界未達到頻繁度閾值，則提前將該模式進行剪枝操作，不需要再搜索該模式的參與實例.

引理5包含模式c 的參與實例的網(wǎng)格為c 中所有特征f(f∈c)的候選參與實例所在網(wǎng)格的交集網(wǎng)格.

證明：由引理3 可得，模式c 的參與實例一定存在于模式c 的候選參與實例中，可以得到模式c 的參與實例所在的網(wǎng)格一定包含于候選模式參與實例所在的網(wǎng)格范圍內(nèi).如果要找到包含模式c 的參與實例的網(wǎng)格，那么這些網(wǎng)格一定包含在所有特征的候選參與實例所在的網(wǎng)格的交集中.如圖4 所示為區(qū)域r 的實例分布，(gridX,gridY)為網(wǎng)格的編號.根據(jù)定義8 列出模式{A,B,C}的候選參與實例集，顯示了候選參與實例所在的網(wǎng)格標號，可以看出網(wǎng)格(1,2)是模式{A,B,C}的所有特征所在網(wǎng)格的交集，即網(wǎng)格(1,2)內(nèi)存在{A,B,C}的網(wǎng)格空間團.

圖4 候選參與實例的示例Fig.4 Examplesofcandidateparticipatinginstances

引理6若某一網(wǎng)格內(nèi)包含模式c 的所有特征，則這些特征實例o(o.f∈c)都為模式c 的參與實例.

證明：由鄰近關(guān)系的定義可知，實例的鄰域范圍是以該實例坐標為中心、邊長為2d 的矩形，則實例的鄰域范圍一定包括實例所在的網(wǎng)格.網(wǎng)格內(nèi)的所有實例都存在鄰近關(guān)系，即滿足團關(guān)系，所以只要網(wǎng)格內(nèi)包含模式c 的所有特征，則這些特征實例o(o.f∈c)一定為模式c 的參與實例.如圖4 中A1 所在的網(wǎng)格(1,2)，都存在鄰近關(guān)系，則在網(wǎng)格(1,2)內(nèi)，特征B 在模式c={A,B,C,D}中的參與實例為Obj(r,c,B)={B1,B2}.

引理7在區(qū)域r 內(nèi)，若模式c 在網(wǎng)格內(nèi)的區(qū)域參與度為 PIintra(r,c)，則稱其為區(qū)域參與度下界.因為真實的區(qū)域參與度一定大于等于 PIintra(r,c)，若區(qū)域參與度下界達到頻繁度閾值，則模式c 一定是區(qū)域頻繁的.

證明：區(qū)域模式c 存在以下2 種情況.1）模式的網(wǎng)格團關(guān)系完全存在于網(wǎng)格內(nèi)，如圖4 的團關(guān)系(A1,B2,C1).2）模式的網(wǎng)格團關(guān)系存在于網(wǎng)格間，如圖4 的(A3,B1,C2).模式的區(qū)域參與度由2 部分組成：PI(r,c)=PIintra(r,c)+PIinter(r,c).若模式c 在網(wǎng)格內(nèi)的區(qū)域參與度已經(jīng)達到頻繁度閾值，即 PIintra(r,c)≥θ，則PI(r,c)=PIintra(r,c)+PIinter(r,c)≥θ，即模式一定是頻繁的.

基于參與度下界的剪枝策略.根據(jù)引理5 找到區(qū)域模式c 完全存在于網(wǎng)格內(nèi)的情況，可以進一步縮小搜索范圍.根據(jù)引理6 可知，網(wǎng)格內(nèi)部的特征實例o (o.f∈c)可以直接被認為是參與實例，無須再搜索區(qū)域模式的團關(guān)系.根據(jù)引理7 計算模式的區(qū)域參與度下界，若模式的區(qū)域參與度下界不小于頻繁度閾值，則該模式一定是區(qū)域頻繁的，不需要搜索出所有的參與實例.

3 算法與分析

3.1 算法描述

提出的算法利用2.2 節(jié)中網(wǎng)格密度峰值聚類的方法進行區(qū)域劃分，開展多級同位模式挖掘.采用先挖掘區(qū)域頻繁模式再推導(dǎo)出全局頻繁模式的 多級同位模式挖掘框架，具體算法如下.

在算法2(S-ML)中，根據(jù)算法1 的網(wǎng)格密度峰值聚類獲得劃分區(qū)域(行1).在區(qū)域劃分的基礎(chǔ)上，對每個區(qū)域進行區(qū)域同位模式挖掘（行3～12）.根據(jù)區(qū)域內(nèi)上一階的頻繁區(qū)域模式生成候選模式（行6），驗證每個候選模式是否在區(qū)域內(nèi)頻繁（行7～9，具體見算法3）.與傳統(tǒng)的多級同位模式挖掘不同，算法2 從區(qū)域同位模式推出全局模式（行10、11），該全局模式不需要計算參與度，因此不需要存儲全局的參與實例集，節(jié)省了空間消耗，只需要計算模式c 的區(qū)域面積與全局空間面積的比值.若模式c 在之前區(qū)域中未被判定為頻繁全局模式，則計算模式當前頻繁區(qū)域的面積之和與全局面積的比值 A′(c).若A′(c)≥ε（A′(c)≥A(c)），則認為該模式為全局模式.

算法3 (IsRegionalCo-location)描述了如何判斷模式c 在區(qū)域r 中的頻繁性.在區(qū)域中挖掘同位模式先通過模式的參與度上界和下界進行剪枝，根據(jù)定義8 得到模式中特征的候選參與實例，根據(jù)引理4 計算得到參與度上界（行2）.若存在某一特征的區(qū)域參與度上界未達到頻繁度閾值，則說明該模式在區(qū)域r 中不是頻繁的，直接返回False（行3）；否則根據(jù)引理7 計算模式的區(qū)域參與度下界，記錄網(wǎng)格內(nèi)模式的參與實例（行4）.若模式的區(qū)域參與度下界達到頻繁度閾值，直接返回True（行5、6）；否則在區(qū)域中搜索模式的所有參與實例，計算參與度，判斷頻繁性（行7～12），具體見算法4.

算法4(Search)描述了如何在區(qū)域r 中搜索c 的參與實例，由引理3 可知，在區(qū)域模式的候選參與實例集 CObj(r,c,f)中搜索參與實例是完備的，所以只須在候選參與實例集中驗證實例是否為區(qū)域模式的參與實例（行1、2）.根據(jù)引理7 可知，當計算模式的區(qū)域參與度下界時，已經(jīng)得到了區(qū)域內(nèi)包含模式c 的所有網(wǎng)格，并記錄了網(wǎng)格內(nèi)的參與實例.對于網(wǎng)格內(nèi)的參與實例，直接返回true（行3、4）.若實例o 不是網(wǎng)格內(nèi)參與實例，則將搜索空間擴展到實例o 所在的網(wǎng)格o.g 及其周圍8 個鄰近網(wǎng)格（實例o 的鄰域范圍）.若該搜索空間不包含c 的所有特征實例，則實例o 一定不是c 的區(qū)域參與實例（行5～7）；若該搜索空間包含c 的所有特征實例，則采用回溯法BracktrackingSreaching(S,X,i,flag)進行搜索.回溯搜索首先初始化解空間S 和數(shù)組X，其中X[i]用于記錄當前解空間的第i 個特征f 的實例，flag 標記是否找到模式c 的網(wǎng)格空間團包含實例o，搜索實例集為o 的鄰域中除o.f 以外的特征實例Oss {f,o'.f}（o'.f≠o.f）(行9).初始搜索空間為實例o 的鄰域范圍，每往X 中加入一個實例o'（加入的實例需要滿足在搜索空間內(nèi)且與當前X 中的實例都存在鄰近關(guān)系），則將搜索空間縮小為實例o 與實例o'的鄰域范圍的交集.若X 中沒有實例可加入且X 不滿足解空間，則進行回溯，同時搜索空間也還原至上一級；以此類推直至找到滿足條件的解空間或者搜索完Oss 的可行路徑（行10）.若最后返回的S 不只包含實例o，則說明找到了包含實例o 的網(wǎng)格 空間團，記錄相應(yīng)的參與實例（行11～13）.

3.2 算法時間復(fù)雜度的分析

分析算法AG-DPC 和S-ML 的時間復(fù)雜度，以下均假設(shè)數(shù)據(jù)集擁有y 個特征、m 個網(wǎng)格、z 個區(qū)域.

AG-DPC：提出的基于網(wǎng)格的密度峰值聚類算法將數(shù)據(jù)分布空間劃分為m 個網(wǎng)格，假設(shè)中心網(wǎng)格數(shù)量為g 個，每個網(wǎng)格內(nèi)的特征數(shù)量為x 個(x＜＜y)，則網(wǎng)格內(nèi)的2 階網(wǎng)格團的種類有種，AG-DPC 的時間復(fù)雜度為O (g (m-g)).

S-ML：算法S-ML 采用分區(qū)后逐階挖掘區(qū)域同位模式，該算法僅挖掘區(qū)域同位模式，并由區(qū)域模式推導(dǎo)出全局模式，不需要計算模式的全局參與度.最壞情況下區(qū)域內(nèi)的特征數(shù)有y 個，區(qū)域每個特征的實例數(shù)最多為n.在每個區(qū)域中從2 階開始逐階進行區(qū)域同位模式挖掘，最壞情況下模式的最高階數(shù)為y (一般情況下，由于鄰近關(guān)系和頻繁度閾值的約束，模式的最高階數(shù)遠小于y).假設(shè)每次迭代中搜索的候選區(qū)域模式個數(shù)為 |RCP|.每個模式都需要判斷其區(qū)域頻繁性和全局頻繁性.當判斷區(qū)域頻繁性時，最壞情況下通過模式的上、下界無法判斷頻繁性，且模式的網(wǎng)格空間團都存在于網(wǎng)格間，因此需要通過調(diào)用BracktrackingSreaching(S,X,i,flag)搜索模式的參與實例.每次調(diào)用BracktrackingSreaching(S,X,i,flag)的時間復(fù)雜度為O(knk)，其中k 為當前階數(shù)，則在每個區(qū)域內(nèi)挖掘區(qū)域模式的時間復(fù)雜度為

在推出全局模式時，僅需要考慮模式所在區(qū)域面積與全局面積的比值.在最壞情況下，每個模式都在其最后一個頻繁區(qū)域中判斷出全局頻繁性，即在每個區(qū)域中的每個模式都需要計算A(c)，則推導(dǎo)出全局同位模式的時間復(fù)雜度為O (zy×|RCP|).綜上所述，S-M L 總的時間復(fù)雜度為O (zny+1|RCP|)+O (zy|RCP|).

4 實驗結(jié)果與分析

使用真實和合成數(shù)據(jù)集，評估所提出的多級同位模式挖掘算法的有效性、效率和可擴展性.實驗中的算法均由C++實現(xiàn)的.硬件環(huán)境為Intel Core i7 3.70 GHz CPU、16 GB RAM.運行環(huán)境為Microsoft Windows 10、Clion2021.

4.1 實驗數(shù)據(jù)集

采取2 個真實數(shù)據(jù)集對算法展開測試：1）深圳POI 數(shù)據(jù)集，包含13 個空間特征、71 606 個空間實例，數(shù)據(jù)分布形狀偏向于簇狀分布；2）高黎貢山的植物數(shù)據(jù)分布集，包含25 個空間特征，13348個空間實例，數(shù)據(jù)偏向于均勻分布.2 個真實數(shù)據(jù)集的實例分布及其分區(qū)結(jié)果如圖5 所示.采用文獻[7]的數(shù)據(jù)合成方法生成合成數(shù)據(jù)集，實驗?zāi)M數(shù)據(jù)在10 000×10 000 的范圍內(nèi)生成.

圖5 真實數(shù)據(jù)集分布及其分區(qū)結(jié)果Fig.5 Distribution of real datasets and their partition results

4.2 真實數(shù)據(jù)集上的實驗分析

4.2.1 網(wǎng)格空間團的網(wǎng)格相似性度量方法的有效性 區(qū)域劃分的目的是通過合理的劃分策略使劃分的區(qū)域內(nèi)存在盡可能相同的區(qū)域模式.為了驗證提出的利用2 階網(wǎng)格空間團獲取目標區(qū)域的效果，定義區(qū)域劃分的評估指數(shù)EI.

式中：R1、R2為2 個相鄰的區(qū)域；n 為區(qū)域個數(shù)，SR(R1,R2)為2 個區(qū)域內(nèi)的區(qū)域同位模式之間的相似度，RC1i、RC2i分別為區(qū)域R1、R2的i 階同位模式，J 為Jaccard 指數(shù).EI 反映了整體空間的區(qū)域劃分的合理性，且0 ≤ EI ≤1.0.EI 越大說明相鄰區(qū)域之間挖掘到的同位模式越不相同，EI 越小說明相鄰區(qū)域之間挖掘到的同位模式越相同.相鄰的不同區(qū)域之間應(yīng)該具有明顯的分割特征，不應(yīng)該具有相似度較高的挖掘結(jié)果，間接反映出區(qū)域劃分的不合理性.

與基于區(qū)域劃分的方法FDPC-RCPM[6]方法及不采用網(wǎng)格相似度的區(qū)域劃分方法進行對比.將頻繁度閾值設(shè)置為0.4.如表1 所示為這些方法在真實數(shù)據(jù)集上的EI 值.可以看出，利用2 階網(wǎng)格空間團劃分區(qū)域的合理性最高.FDPC-RCPM 方法采用模糊密度峰值聚類的方法劃分區(qū)域，在劃分過程中僅考慮實例數(shù)據(jù)點的密度和距離，未考慮同位模式，導(dǎo)致相鄰的區(qū)域中存在很多相同的同位模式，即劃分的區(qū)域存在不合理性.為了對比網(wǎng)格空間團的網(wǎng)格相似性度量方法的有效性，對網(wǎng)格相似性度量進行消融實驗，設(shè)計不采用網(wǎng)格相似度的區(qū)域劃分方法S-ML-2.S-ML-2 存在與FDPC-RCPM[6]方法同樣的問題.

表1 不同方法的EI 值Tab.1 EI values for different methods

4.2.2 挖掘結(jié)果的有效性 深圳POI 數(shù)據(jù)集中特征A 和特征B 的實例分布情況如圖6(a)所示，可以看出模式{A,B}分布的范圍較廣.ML 方法[14]是傳統(tǒng)的多級同位模式挖掘方法，采用模式聚類的方法獲取頻繁區(qū)域.圖6(c)中被框出的區(qū)域表示在ML 方法下挖掘到的模式{A,B}的頻繁區(qū)域.可以看出，僅找到了模式{A,B}的部分區(qū)域.本文的挖掘結(jié)果（見圖6(b)）更加符合實例的分布情況，挖掘的區(qū)域更全面.

圖6 挖掘到的區(qū)域模式頻繁區(qū)域的比較Fig.6 Comparison of mined prevalent regions of regional co-location patterns

在傳統(tǒng)的多級挖掘方法中，全局同位模式是滿足全局頻繁度閾值的模式，即表示該模式在整個研究空間中頻繁出現(xiàn)的模式；本文的全局模式不從參與度的角度考慮，從區(qū)域同位模式考慮，頻繁的區(qū)域同位模式出現(xiàn)在多個區(qū)域，且這些區(qū)域的面積占整個研究區(qū)域面積的比值達到給定閾值時，認為該模式為全局頻繁模式.當挖掘全局模式時，ML 方法僅考慮模式的全局參與度，忽略了模式的分布情況，會造成僅分布在局部小區(qū)域的模式被誤判為全局模式，如圖7 所示，深色部分表示該模式存在的區(qū)域，這些區(qū)域面積占比很小，不滿足模式在全局范圍內(nèi)頻繁共現(xiàn).本文挖掘的全局模式在區(qū)域模式的基礎(chǔ)上考慮了模式的分布情況，從圖8 可以看出，模式在全局范圍內(nèi)頻繁出現(xiàn)（淺色為模式分布的區(qū)域）.

圖7 利用ML 方法識別的全局模式的分布Fig.7 Distribution of global patterns identified by ML

圖8 利用提出方法識別的全局模式的分布Fig.8 Distribution of global patterns identified by proposed method

通過對比挖掘到的區(qū)域模式和全局模式，可知提出的挖掘方法的結(jié)果更加合理.

4.2.3 挖掘效率 為了對比本文方法與其他多級同位模式挖掘方法的執(zhí)行效率，對比了3 個傳統(tǒng)多級同位模式挖掘方法(ML[14]、NN[15]、QGFR[24])和2 個僅挖掘區(qū)域同位模式的方法(KNNG[19]、FDPC-RCPM[6]).將深圳POI 數(shù)據(jù)的鄰近閾值設(shè)置為100，高黎貢山的鄰近閾值設(shè)置為1 500 (深圳POI 屬于城市建筑數(shù)據(jù)，實例之間的距離較近；高黎貢山屬于植被數(shù)據(jù)，實例之間的距離較遠.在考慮數(shù)據(jù)集內(nèi)實例的平均距離后分別設(shè)置了相對較合理的距離閾值).其中采用k 近鄰生成鄰近關(guān)系的方法（KNNG、FDPC-RCPM），將輸入距離閾值的平均鄰居個數(shù)作為k 值.NN 方法是基于自然鄰居挖掘多級同位模式，建立新的局部自適應(yīng)鄰近關(guān)系，對特征數(shù)量極其敏感.QGFR 方法使用最小正交包圍矩形作為模式的區(qū)域,但得到的區(qū)域形狀固定為正交矩形,且即使在帶有剪枝策略的情況下,算法的時間復(fù)雜度仍極高.在本實驗中僅限于比較方法的時間效率，無法在24 h 內(nèi)獲取到NN 方法和QGFR 方法的實驗結(jié)果.

如圖9 所示為在不同的頻繁度閾值P 下多個方法的運行時間T.可以看出，在不同的頻繁度閾值下，本文方法的時間效率最優(yōu).ML 方法將全局不頻繁的模式全部作為區(qū)域候選模式.隨著頻繁度閾值的增加，全局同位模式數(shù)量減少導(dǎo)致區(qū)域候選模式數(shù)量增加，ML 方法需要對每個候選區(qū)域模式計算區(qū)域參與度，導(dǎo)致消耗大量的運行時間.KNNG 方法需要花費大量的時間驗證相似的模式，獲取目標區(qū)域，計算參與度.FDPC-RCPM 方法在每個區(qū)域中采用原始的join-less 方法進行挖掘,并未優(yōu)化算法效率.本文提出的方法采用參與度的上下界進行有效剪枝，只需要對不能剪枝的模式計算區(qū)域頻繁度，時間效率有了很大的提升，甚至優(yōu)于僅挖掘區(qū)域同位模式方法的時間效率.

圖9 在不同頻繁度閾值下的運行時間對比Fig.9 Comparison of running time under different prevalent thresholds

本文方法是新穎的多級同位模式挖掘方法，將其挖掘結(jié)果與傳統(tǒng)多級方法ML 進行對比.隨著頻繁度閾值的增大，利用這2 個方法挖掘到的模式數(shù)量遞減.本文所挖掘到的區(qū)域模式數(shù)量多于ML 方法挖掘到的模式數(shù)量，如圖10 所示.圖中，N 為模式數(shù)量.這是因為考慮了實例之間的網(wǎng)格特性，且鄰近關(guān)系包括對角線可達性，相比于ML 方法中的鄰近關(guān)系，本文的鄰近關(guān)系更豐富，可以捕捉到更多有潛在價值的模式.此外，本文避免了將區(qū)域模式誤判為全局模式，而ML 方法存在誤判的情況，這導(dǎo)致ML方法挖掘到的區(qū)域模式數(shù)量較少.

圖10 在不同頻繁度閾值下的區(qū)域模式數(shù)量對比Fig.10 Comparison of number of regional patterns under different prevalent thresholds

4.2.4 剪枝效率 圖11 中，Nc為候選模式的數(shù)量，Np為剪枝模式的數(shù)量，R 為剪枝率.如圖11 所示，隨著頻繁度的增加，剪枝率逐漸上升.由于本文方法利用網(wǎng)格特性和模式參與實例的反單調(diào)性，對候選模式進行剪枝.隨著頻繁度的增加，提前被剪枝的模式數(shù)量也增加，剪枝率一直上升.在高黎貢山數(shù)據(jù)集上，當頻繁度為0.8 時，剪枝率可以達到78%.通過實驗驗證了提出的S-ML 算法在2 個真實數(shù)據(jù)集上剪枝策略的有效性.

圖11 S-ML 算法的剪枝率Fig.11 Pruning rate of S-ML algorithm

4.3 合成數(shù)據(jù)集上算法的可擴展性分析

根據(jù)文獻[7]的數(shù)據(jù)生成方法，合成7 個數(shù)據(jù)集，實例個數(shù)為10 000～60 000，將頻繁度閾值設(shè)置為0.4.實驗結(jié)果如圖12(a)所示，Ni為實例的數(shù)量，Nf為空間特征的數(shù)量，隨著實例數(shù)量的增加，所有算法的耗時均呈上升趨勢.其中FDPCRCPM 方法在實例數(shù)為10 000 時時間消耗已達到587 s，在實例數(shù)超過20 000 后運行時間超過600 s.與其他算法相比，提出的算法在效率上表現(xiàn)顯著更高，并一直保持較高的運行效率.

圖12 合成數(shù)據(jù)集上的實驗對比Fig.12 Experimental contrasts on synthetic datasets

空間特征數(shù)量對同位模式的階數(shù)有著較大的影響.為了研究特征數(shù)量對算法運行效率的影響，合成了5 個不同特征數(shù)量的數(shù)據(jù)集，實例數(shù)量為10 000.實驗結(jié)果如圖12(b)所示，S-ML 算法的運行效率較高.

綜上所述，提出的算法具有良好的時間效率，在處理大規(guī)模實例數(shù)量時具有更好的可擴展性.

5 結(jié) 語

本文提出基于網(wǎng)格空間團的多級同位模式挖掘方法.傳統(tǒng)的鄰近關(guān)系定義通常只考慮空間實例之間的歐氏距離，忽略了真實數(shù)據(jù)普遍的網(wǎng)格化分布.為了彌補這一不足，采用網(wǎng)格鄰近關(guān)系來替代傳統(tǒng)的基于距離的鄰近關(guān)系.在區(qū)域劃分階段，針對點聚類劃分區(qū)域方法的不足，提出優(yōu)化的網(wǎng)格密度峰值聚類方法，在聚類的基礎(chǔ)上進一步考慮網(wǎng)格內(nèi)模式的相似情況.在模式挖掘階段，提出從區(qū)域同位模式推導(dǎo)出全局同位模式的挖掘新框架，設(shè)計帶有剪枝策略的多級同位模式挖掘算法.該算法不僅避免了將區(qū)域同位模式誤判為全局同位模式的情況，還減少了計算全局參與度的時間，顯著提升了時間效率.本文的全局模式考慮了模式的分布情況，使得結(jié)果更加準確.通過實驗驗證了挖掘結(jié)果的有效性和合理性，在真實和合成數(shù)據(jù)集上進行了廣泛的實驗，驗證了本文算法的高效性和可擴展性.