基于改進列計算的空間并置模式挖掘方法

昌鑫 蘆俊麗 陳書健 段鵬

摘 要：空間并置（co-location）模式挖掘旨在發現空間特征間的關聯關系，是空間數據挖掘的重要研究方向。基于列計算的空間并置模式挖掘方法（CPM-Col算法）避開挖掘過程中最耗時的表實例生成操作，直接搜索模式的參與實例，成為當前高效的方法之一。然而，回溯法搜索參與實例仍是該方法的瓶頸，尤其在稠密數據和長模式下。為加速參與實例的搜索，充分利用CPM-Col算法搜索參與實例時得到的行實例，在不增加額外計算的前提下對CPM-Col算法進行兩點改進。首先，將CPM-Col算法搜索到的行實例存儲為部分表實例，利用子模式的部分表實例快速確定參與實例，避免了大量實例的回溯計算。其次，在CPM-Col算法獲得一條行實例后，利用行實例的子團反作用于第一個特征，得到第一個特征的參與實例，避免了這些實例的回溯搜索。由此，提出了基于改進列計算的空間并置模式挖掘算法（CPM-iCol算法），并討論了算法的復雜度、正確性和完備性。在合成數據和真實數據集上進行了實驗，與經典的傳統算法join-less和CPM-Col進行對比，CPM-iCol算法明顯縮短了挖掘的時間，減少了回溯的次數。實驗結果表明，該算法比CPM-Col具有更好的性能和可擴展性，特別在稠密數據集中效果更加明顯。

關鍵詞：空間數據挖掘；空間并置模式；列計算；回溯搜索

中圖分類號：TP391?? 文獻標志碼：A??? 文章編號：1001-3695（2024）05-014-1374-07

doi： 10.19734/j.issn.1001-3695.2023.09.0448

Method for co-location pattern mining based on improved column calculation

Abstract：Spatial co-location pattern mining aims to discover the association between spatial features and has been an important research direction in spatial data mining. Spatial co-location pattern mining method based on column calculation（CPM-Col algorithm） avoids the most time-consuming operation of generating table instances and directly searches for participating instances. This method has become one of the most efficient approaches. However， backtracking search for participating instances remains a bottleneck， especially in dense datasets and long pattern mining. To accelerate the search for participating instances， this paper proposed two improvements to the CPM-Col algorithm with less extra computations. Firstly， the row instances found by CPM-Col algorithm were stored as partial table instances， for avoiding backtracking calculations of many instances. Secondly， after successfully finding a row instance， some instances of the first feature were obtained by the sub-clique reaction of the row instance. Based on these improvements， this paper proposed a co-location pattern mining method based on improved column calculation （CPM-iCol algorithm） and discussed complexity， correctness， and completeness. Experiments were conducted on synthetic and real datasets. Comparing to a classical algorithm join-less and CPM-Col， the CPM-iCol algorithm significantly reduces mining time and backtracking times. The results show that the proposed algorithm has better performance and scalability than CPM-Col algorithm， especially in dense datasets.

Key words：spatial data mining; spatial co-location pattern; column calculation; backtracking search

0 引言

空間并置模式挖掘是空間數據挖掘研究的一個重要分支，旨在發現空間特征（事物）之間的關聯關系?？臻g并置模式是空間特征集的子集，這些特征的實例在地理空間中頻繁地并置出現［1］。例如，社區附近經常伴隨超市，植物茂盛的地方有蚊蟲聚集等?？臻g并置模式挖掘是提取海量的空間數據有用信息和有價值知識的有力工具，在許多應用領域中具有重要作用。在公共衛生方面［2］，空間并置模式可以研究病例與污染物排放間的關聯關系；在公共安全方面［3～4］，可以發現城市設施對犯罪發生的影響；在城市建設方面［5～6］，可以對居民區和工廠等合理選址布局提供指導；其他應用領域還包括城市交通規劃優化［7］、生態學［8～9］、商業［10］、環境科學［11～12］、農業［13］等。

CPM-Col算法［14］采用逐階候選-測試框架挖掘空間并置模式。給定空間數據集、距離閾值、頻繁度閾值，CPM-Col包括四個步驟（圖1）：①基于k-1階頻繁并置模式生成k階候選模式；②回溯法搜索每個候選模式各個特征的參與實例集；③通過給定的頻繁度閾值來測試候選模式是否為頻繁模式；④通過迭代生成所有階頻繁的空間并置模式。

盡管通過上述挖掘框架可以正確地生成所有頻繁的空間并置模式，但是第②步回溯法搜索模式的參與實例步驟仍非常耗時，尤其在稠密數據集或長模式挖掘中。一般來說，每個候選實例均要啟用回溯法搜索行實例來確定其為參與實例，這一過程較耗時，CPM-Col算法提出了實例排序優化策略，剪掉一部分待啟用回溯法的候選實例，但是做得不夠充分。其利用耗時的回溯法搜索到行實例后，存儲這些實例為參與實例就退出搜索，未能物盡其用。

針對上述CPM-Col算法在稠密數據中存在的問題，本文在其算法的兩個階段提出改進：保留CPM-Col在k-1階搜索到的部分表實例，利用保留的 k-1 階表實例得出k階參與實例，減少k階搜索的次數；利用CPM-Col在k階搜索到的k個行實例，用行實例的k-1個實例為k階搜索加速，減少搜索次數。在稠密數據中形成的團實例是極其緊湊的，利用上述改進主要解決了CPM-Col在搜索時每搜索一次k階實例就要重新啟用回溯策略的不足，有效地減少了CPM-Col的搜索次數，因此改進是有效的。

本文的主要貢獻如下：

a）存儲CPM-Col算法在生成參與實例時搜索到的部分表實例，利用子模式的部分表實例快速得到參與實例，剪掉大量待回溯搜索的候選實例。

b）每搜索完一條完整的行實例后，利用行實例的子團反作用于第一個特征，得到第一個特征的參與實例，避免了這些實例的回溯搜索。

c）在真實數據集和合成數據集上進行了全面的實驗，以證明技術的有效性、高效率和可擴展性。

1 相關工作

文獻［15］首次提出空間并置模式挖掘的概念，被認為是該領域的第一項工作，提出的join-based算法發現了完整的并置模式集合，但由于采用了全連接操作來收集和驗證候選模式的實例，影響了效率。文獻［16］提出了部分連接（partial-join）和無連接（join-less）的空間并置模式挖掘算法，partial-join基于團關系劃分模型物化鄰近關系減少連接的計算，但需要存儲被團切斷的鄰近關系。join-less采用星型鄰居劃分模型，用實例查找代替實例連接操作，但星型實例不一定滿足團關系，還需對團關系進行檢查。文獻［17］對無連接的空間并置模式進一步研究，提出CPI-tree結構物化鄰居關系，深度優先遍歷所有模式的表實例，不需要團關系檢查，但存儲CPI-tree需要大量內存。隨后文獻［18］改進了CPI-tree算法，以寬度優先遍集區域的實例。Lin等人［19］提出基于行實例擴展的NCA算法，借助每條行實例的鄰居結構，將k階模式的行實例擴展成k+1階模式的行實例，但該方法需要大量的存儲空間。文獻［20］提出基于團的并置模式挖掘方法，該方法將搜索到的完備團用C-hash表壓縮存儲，通過C-hash計算并置模式的頻繁度，但完備團的計算是耗時的。文獻［21］提出基于極大團劃分的方法，將空間數據劃分為重疊的極大團，通過組合獲得所有候選模式和表實例。基于團的算法雖然避免了逐階遞增候選模式的生成，但需要占用大量空間。文獻［22］提出基于網格的空間并置模式算法，將空間分為許多個單元，利用并行編程改進效率，每個進程包含幾個小單元的計算任務，但是單元的大小很難設置。文獻［23］提出一種利用GPU基于網格的并置模式挖掘算法。文獻［24］提出在MapReduce框架上并行挖掘空間并置模式的算法，能有效地處理大量數據，但對環境要求較高。盡管上述工作可以提升表實例生成的效率，但本質上表實例的生成仍然是耗時的。Zou等人［25］引入實例對之間在步長I內相互可達的鄰居關系，提出I-可達并置模式，研究了空間數據的最大I-可達并置模式。用［I/2］-可達鄰居列表，以二進制的搜索方式快速計算最大I-可達并置模式的參與度。Zhang等人［26］提出了單元關系操作框架，通過對單元的特征進行計數并計算單元的特征重疊率以生成并置模式，突破了傳統空間并置模式挖掘以點為實例挖掘的限制。Tran ［27］用元頻繁并置模式解決了傳統并置模式挖掘中低頻繁性閾值挖掘過多冗余模式的問題，設計了基于查詢的挖掘算法，在不生成候選的情況下挖掘元頻繁并置模式，并且不收集和保留每個模式的實例。文獻［28］設計了兩級過濾機制，通過特征過濾和相鄰實例過濾，將空間實例劃分為一組重疊的團，每個團也是并置模式的實例，用并置模式哈希圖結構存儲表實例，當頻繁性閾值改變時，不需要重新收集表實例快速挖掘并置模式。文獻［14］提出一種基于列計算的并置模式挖掘算法，它是一種高效的回溯算法，將表實例問題轉換為參與實例問題，通過搜索模式的參與實例挖掘并置模式。

本文提出基于列計算的改進算法，利用部分表實例輔助加速參與實例的搜索，快速得到模式中特征的參與實例。

2 相關概念

在空間數據集中，一個空間特征表示一個地理對象類型，特征的空間實例是一個具有位置信息的地理對象。F={f1， f2，…， fm}表示不同特征的集合，每個特征有對應的實例，O={o1，o2，…，on}為所有實例的集合，其中每個實例由一個〈實例編號，特征類型，位置〉三元信息構成。如果用歐氏距離度量兩實例間的鄰近關系R，則R（o，o′）distance（o，o′），其中distance（o，o′）是兩實例間的距離，d是用戶給定的距離閾值，可用歐幾里德距離。對于實例o，o的鄰居集是與o有鄰近關系的所有實例集合，記為Neighbor（o）={o′|o′∈O，R（o，o′）}。在o的鄰居集中，相同特征f的實例集合稱為o在f下的分組鄰居集［14］，記為groupN（o，f）={o′|o′∈Neighbor（o），o′.t=f}。如圖2（a）中，對于實例A.1，有Neighbor（A.1）={B.3，B.4，C.4}，groupN（A.1，B）={B.3，B.4}。

空間并置模式是一組空間特征F的子集，C={f1，f2，…，fk}，k≥2，CF，C的階為C中特征的數量［14］。實例集合RI={o1，o2，…，ok}被稱為C的行實例，如果：a）RI中任意兩個實例滿足鄰近關系R，也就是RI中的實例形成團關系；b）RI中的實例數量與C的階數相等，并且RI中的實例覆蓋C中的所有特征［14］。模式C的行實例集合稱為表實例，表示為table_instance（C）［14］。為了更好地評價并置模式的頻繁性，文獻［1］提出了參與率和參與度。給定空間并置模式C={f1，f2，…，fk}，C中特征fi的參與率PR定義如下：

其中：N（fi）表示在空間數據集中fi的實例集合；Πfi（table_instance （C））是帶冗余消除的投影操作，用于找到表實例中fi不重復實例的集合；||表示集合中元素的個數。參與度即為模式C中各特征參與率的最小值，記為

PI（C）=minki=1（PR（C，fi））（2）

例1 圖2（a）中，{A.1，B.3，C.4}是模式{A，B，C}的行實例，因兩兩滿足鄰近關系R，且{A.1，B.3，C.4}的實例數量等于模式{A，B，C}的階數，并且覆蓋了模式{A，B，C}的所有特征。

給定一個并置模式C，當PI（C）大于等于給定的最小頻繁度閾值min_prev時，稱并置模式C是一個頻繁并置模式。

例2 圖2（a）中，{A，B，C}是一個三階并置模式，實例集合{A.1，B.3，C.4}是{A，B，C}的一條行實例，模式{A，B，C}的表實例在圖2（b）中完整列出，計算了該模式下各個特征的參與率及模式的參與度，PI（{A，B，C}）=3/5=0.6。如果0.6≥min_prev，則{A，B，C}是一個頻繁空間并置模式?？臻g并置模式挖掘旨在發現空間數據集中的所有頻繁并置模式。文獻［1］已經證明模式的參與度滿足反單調性，即對模式C及其超模式C′，CC′，不等式PI（C）≥PI（C′）恒成立。由反單調性得出模式的向下閉合性質可用于模式剪枝，即一個不頻繁模式的超模式均不頻繁，一個頻繁模式的子模式均頻繁。

3 改進策略

定義1 參與實例。給定并置模式C，實例o（o.t=f）在C的任一行實例中，則o是C中特征f的參與實例。f在C中的所有參與實例集合稱為f在C中的參與實例集，表示為Obj（C，f）［14］。

定義2 候選參與實例集。特征f在k（k>2）階并置模式C中的候選參與實例集是模式C中所有包含f的k-1階子模式f的參與實例的交集［14］，記為

定義3 部分表實例。給定一個空間并置模式C，CPM-Col算法搜索到的行實例稱為C的部分表實例，記為PT（C）。

例3 圖3中，模式{A，B，C}的部分參與實例可以通過其子模式{A，B}的部分表實例得到。利用引理2，S1=groupN（A.2，C）∩groupN（B.1，C）=C.3，S2=groupN（A.3，C）∩groupN（B.2，C）=C.5，S2=groupN（A.4，C）∩groupN（B.2，C）=C.1，由此可確定{A.2，A.3，A.4}、{B.1，B.2}、{C.1，C.3，C.5}分別為模式{A，B，C}中特征A、B、C的參與實例。

由例3可以看出，模式{A，B，C}的子模式有{A，B}，{B，C}，{A，C}，但{A，B}形成的部分表實例最少最精簡。因此，在使用引理2時，選用部分表實例數最少的子模式，用更少的代價快速確定參與實例。

CPM-iCol在搜索參與實例時，將模式的特征按參與率上界降序排列，引理3只針對第一個特征求解，因為參與率上界高的特征更有可能與其他特征形成行實例。

例4 圖2（a）中，{A.4，B.2，C.3}為模式C={A，B，C}的一條行實例，S=groupN（B.2，A）∩groupN（C.3，A）={A.2，A.4}，可知{A.2，B.2，C.3}是模式C的一條行實例，所以A.2是模式{A，B，C}特征A的參與實例。

實際應用中，實例是錯綜復雜的，引理3可以通過已知的一條行實例生成多個參與實例。

4 算法及分析

4.1 算法描述

基于引理2、3，本文對CPM-Col算法進行改進，提出CPM-iCol算法（算法1）。第1行計算實例間的鄰近關系，物化每個實例在不同特征下的分組鄰居集。第2行初始化一階頻繁并置模式。第3～12行從二階開始，逐階生成候選模式并判斷每個候選模式的頻繁性，直到沒有頻繁模式被找到，最終返回所有的頻繁并置模式。第6行isPrevalent（C）是算法的核心。

算法1 CPM-iCol算法

在isPrevalent（C） （算法2）過程中，第1～6行與CPM-Col的剪枝策略一致，計算候選模式C中每個特征參與率的上界，并根據參與率上界（引理1）進行剪枝。如果C不能被剪枝，則第7、8行對C中的特征按照參與率上界降序排序，并初始化每個特征的參與實例集和部分表實例為空，找出包含最少部分表實例的子模式C′。第9行調用SearchPI（C，C′，PT（C′））過程利用子模式C′的部分表實例PT（C′），根據引理2提前確定C的部分候選實例。第10～28行按照排序后的次序遍歷每個特征的候選參與實例集CObj（C，f）。對于CObj（C，f）中的實例o，如果o已經在參與實例集Obj（C，f）中，則不需要再驗證；否則調用searchRI（o，C）搜索一條包含o和C的行實例RI。如果RI不為空，第15行將RI加入C的部分表實例中，第16行利用RI，根據引理3求得C的第一個特征的參與實例，第17、18行將RI中的每個實例按照特征類型保存到各自的參與實例集中。在搜索完一個特征的所有參與實例后，第25～28行計算該特征的參與率，如果不滿足min_prev，則模式C不頻繁，并且停止搜索其他特征。如果搜索完C中的所有特征，沒有任何特征的參與率小于min_prev，則C是頻繁并置模式，isPrevalent（C）返回true。

第13行searchRI（o，C）過程與文獻［14］描述一致，使用回溯算法找尋一條包含候選實例o的模式C的行實例，這里不再贅述。下面主要介紹本文的兩點改進，即第9行的SearchPI （C，C′，PT（C′））過程和第16行的interact （o，C，RI）過程。

算法2 isPrevalent（C）

算法3使用引理2找尋模式C的各個特征的參與實例。其中，第1行先找出模式C和子集C′相差的特征f′。第2～6行將RI中每個實例在特征f下的分組鄰居取交集，第7～9行將實例RI以及S的實例分別加入對應特征的Obj（C， f）中。

算法2第13行已找出實例o在模式C中的一條行實例RI。算法4利用引理3，借助RI找出C的第一個特征f1更多地參與實例。第1、2行先判斷o是不是第一個特征f1的參與實例，如果是，第3～9行對RI中除第一個特征f1外的實例o′，取其在f1下分組鄰居集groupN（o′， f1）的交集S，則S中的實例為f1在C中的參與實例，將S加入Obj（C， f1）中。

算法3 SearchPI （C，C′，PT（C′））

4.2 算法分析

a）時間復雜度。在算法1中，計算空間鄰近關系使用平面掃描等技術，其復雜度小于O（n2）。第3～12行從二階開始進行挖掘，在第k-1（k≥2）次迭代中，需要搜索的候選模式數量為|Ck|，復雜度即為O（|Ck|）。對于每個候選模式C，調用算法2判斷模式的頻繁性，isPrevalent（C）算法中，第9～27行是最耗時的，最壞的情況需要遍歷所有特征的候選參與實例，復雜度為O（k×（n1）），n1為候選參與實例集CObj（C，f）的最大長度，其中第9行調用SearchPI（C，C′，PT（C′）），需要遍歷子模式中具有最小長度的部分表實例PT（C′），復雜度為O（（k－1）×n2），n2是PT（C′）的長度。對每個候選參與實例，第13行調用searchRI（o，C）搜索包含實例o的模式C的一條行實例，最壞情況下需要搜索其他特征實例的所有組合，復雜度為O（nk－13），n3是Oss（o，f，C）的最大長度［14］。第16行interact （o，C，RI），只需要將RI中k-1個實例的分組鄰居集取交集，時間復雜度為O（k－1）。借助SearchPI（C，C′，PT（C′））和interact（o，C，RI）的作用，調用searchRI（o，C）實際搜索的組合數將遠小于O（nk－13）。綜上所述，判斷候選模式C頻繁性的時間復雜度為O（k×n11×（k－1）×n2+k×n12×nk－13+k×n13×（k－1））。其中n11+n12+n13=n1，n1個候選參與實例中分別有n11、n12、n13個，由SearchPI （C，C′，PT（C′））、searchRI （o，C）、interact （o，C，RI）識別。每輪迭代中k為常數，由于距離閾值和頻繁性閾值的約束，需要搜索的模式階數k不會無限制增長。

b）空間復雜度。CPM-iCol空間耗費主要來自三個方面：（a）每個實例的分組鄰居集groupN（o，f），空間耗費為O（|n|×|F|×m1），其中m1為groupN（o，f）的最大長度，保存鄰近關系的空間消耗在并置模式挖掘算法中普遍存在；（b）在挖掘k階模式時，保存k階頻繁并置模式的參與實例集，用來計算候選參與實例集，空間消耗為O（|Pk|×k×m2），Pk是k階頻繁并置模式的數量，m2為參與實例集Obj（C，f）的最大長度；（c）搜索k+1階模式的參與實例時，需要保存每個k階模式的部分表實例用于輔助k+1階模式的參與實例搜索，空間消耗為O（|Pk|×k×m3），其中m3為k階模式部分表實例的最大長度。k+1階候選模式搜索完成后，k階頻繁并置模式的參與實例和k階部分表實例都將被釋放。

c）完備性。完備性表示CPM-iCol算法能挖掘到所有的頻繁并置模式。算法從二階開始逐階測試候選模式的頻繁性，生成候選模式的完備性由參與度的向下閉合性保證，因此CPM-iCol算法一定能搜索到所有的頻繁并置模式。

d）正確性。算法2分成兩階段計算模式的參與實例，第9行未能識別的參與實例，會在第13、16行中識別，所以沒有遺漏任何參與實例的搜索。引理2、3也可以保證正確性。

5 實驗結果與分析

5.1 對比算法以及實驗環境

實驗的對比算法選取了CPM-Col［14］算法和Join-less［16］。CPM-Col采用了回溯算法驗證模式中的參與實例，解決了表實例所產生的開銷問題，是目前逐階候選-測試框架中的最優算法。Join-less是應用最廣泛的經典算法之一。

本文CPM-iCol和對比算法均使用Python語言編寫，實驗環境為：Intel CoreTM i5-6300HQ CPU2.30 GHz，16 GB內存，Windows10操作系統。

5.2 實驗數據集

本文采用合成數據集和真實數據集。合成數據集實例的坐標范圍均為1000×1000，根據需要的特征數量，在坐標范圍內不重復地隨機生成點，直至滿足需要的實例數量。真實數據集采用北京市興趣點（PoI）數據集（Beijing-PoI）和上海市興趣點（PoI）數據集（Shanghai-PoI），真實數據集均從谷歌地圖中爬取。上述數據集的具體參數如表1所示，其中data-set表示合成數據集。

5.3 實驗評估

本文從以下四個方面評估提出的算法：

a）可伸縮性，測試算法在不同數據集和參數上的適應性；

b）空間耗用，測試算法在不同閾值下的空間消耗情況；

c）改進算法效率分析，測試算法的兩個改進效果及各個階段挖掘團關系的情況；

d）算法剖析，測試算法每個步驟的性能。

5.4 可伸縮性

本節測試了實例數量、特征數量、距離閾值、頻繁性閾值對CPM-Col、CPM-iCol和Join-less的影響，來驗證算法的可伸縮性。前兩個實驗使用合成數據集測試了實例數量和特征數量對算法的影響。后兩個實驗使用Beijing-PoI和Shanghai-PoI來測試距離閾值和頻繁性閾值對算法的影響。

5.4.1 實例數量的影響

本實驗測試了不同實例數量對算法的影響。使用了四個合成數據集data-set1～data-set4進行實驗對比，實驗數據設置：范圍為1k×1k，特征數量為10，距離閾值為25，頻繁度閾值為0.8。如圖4所示，當實例數量從20k到50k時，可以看出，三種算法的運行時間都隨著實例數量的增加而增加，但是CPM-iCol算法運行時間的增長速度小于CPM-Col和Join-less算法，且Join-less算法在實例數量為30 k時，運行時間已經超出了900 s。實驗證明在同一個空間范圍、不同實例數量下，CPM-iCol算法能有效提高CPM-Col挖掘并置模式的效率。

5.4.2 特征數量的影響

本實驗測試了不同特征數量對算法的影響。使用了四個合成數據集data-set5～data-set8進行實驗，實驗數據設置：范圍為1k×1k，實例數量為30k，距離閾值為25，頻繁性閾值為0.5。如圖5所示：a）當特征數量從10到25時，CPM-iCol和CPM-Col的變化都不明顯，CPM-iCol的運行時間小于CPM-Col，因為實例數量較大，Join-less的運行時間超過600 s，就不在圖中顯示；b）隨著特征數量增多，頻繁模式的長度和數量與之增加，兩個算法時間都呈增加趨勢。由于CPM-iCol算法避免了一部分回溯時間，所以運行時間小于CPM-Col。

5.4.3 距離閾值的影響

本實驗測試了不同距離閾值下對算法的影響，使用Beijing-PoI和Shanghai-PoI兩個真實數據進行實驗，頻繁性閾值都設置為0.7。圖6和7顯示了三種算法在Beijing-PoI和Shanghai-PoI兩個真實數據集中隨距離閾值變化的運行時間。從圖中可以看出，CPM-Col和CPM-iCol明顯優于Join-less算法；CPM-Col和CPM-iCol兩種算法的運行時間都隨著距離閾值的增加而增長，當距離閾值較小時，兩者運行時間相當，當距離閾值達到400后，CPM-iCol優于CPM-Col，距離閾值越大，能夠滿足的團關系就越多越緊密，利用引理2、3的效果明顯提升。

5.4.4 頻繁性閾值的影響

本實驗測試了不同頻繁性閾值對算法的影響，使用Beijing-PoI和Shanghai-PoI進行實驗，距離閾值都設置為400。圖8顯示了三種算法的運行時間，因Join-less算法在Shanghai-PoI數據中運行時間都超過了1 000 s，所以在圖9中不顯示Join-less的折線圖。顯然，CPM-Col、CPM-iCol和Join-less的運行時間隨著頻繁性閾值的增加而減少。

頻繁性閾值決定了頻繁并置模式的數量，當閾值較小時，滿足條件的模式更多。從圖中可以看出，在頻繁性閾值同為0.4時，CPM-Col在Beijing-PoI的效果優于本文算法。這是因為在北京PoI的各個特征的實例是比較分散的，參與實例的團關系不緊密，而上海PoI的實例比較密集，參與實例的團關系緊密，利用引理2、3的效果好，所以本文算法更傾向于使用密集的數據。隨著頻繁性閾值增加，頻繁并置模式的數量減少，算法的時間減少是自然的。

5.5 改進算法效率分析

本節分別驗證引理2、3的挖掘效率。引理2、3在搜索模式的參與實例時，分別通過子模式的部分表實例和獲得的每條行實例快速計算得到參與實例，避免這些實例啟動耗時的回溯法搜索。那么，引理2、3能夠確定的參與實例越多，搜索過程提速就會越快。本實驗在data-set3數據集上運行，距離閾值設置為25。圖10分別統計在頻繁性閾值min_prev改變時，CPM-iCol算法由回溯法（SearchRI）、 引理2（SearchPI）及引理3（interact）確定的參與實例數占總實例數的比率。

從圖10可以看出，引理2（SearchPI）確定的參與實例數大于回溯法，而引理3（interact） 確定的參與實例數與回溯法相當。故引理2的提速效果非常明顯，引理3也具有一定程度的提速。

為進一步驗證上述結論，繼續檢驗CPM-Col、 CPM-pCol（CPM-Col算法中只引入引理2）和CPM-iCol（CPM-Col算法中引入兩個引理）隨min_prev變化時的性能，如圖11所示。從圖中可以看出，相對CPM-Col，CPM-pCol算法性能提升非常大，CPM-iCol算法在此基礎上也有較為明顯的性能提升。

5.6 算法剖析

本實驗測試了CPM-Col和本文CPM-iCol在data-set3上各個步驟的執行時間。參數設置：距離閾值為25，頻繁性閾值為0.7。

表2中列出的各個步驟的含義如下：

a）T_gen_neighbor是物化鄰近關系所用時間；

b）T_gen_candidates是生成候選模式所用時間；

c）T_gen_partial_table是部分表實例獲取參與實例所用時間；

d）T_ gen_obj是回溯法搜索參與實例所用時間；

e）T_interaction是利用回溯法搜索到的行實例快速獲取參與實例所用時間；

f）T_total是算法的總運行時間。

兩種算法都挖掘出了相同且正確的模式，從表2可以看出，CPM-iCol算法雖然空間耗費上高于CPM-Col，時間上是少于CPM-Col的。CPM-Col是一種回溯搜索算法，使用參與實例機制避免了所有實例的團關系檢查，所以CPM-Col的運行時間主要耗費在回溯法搜索參與實例，即表2中第5步。CPM-iCol算法避免所有候選實例都啟用回溯法來生成參與實例進行兩處改進，體現在表2中的第3、4步。從表2可以看出，CPM-iCol算法第4步的運行時間可以忽略不計，第3、5步的總運行時間之和遠小于CPM-Col算法的第5步運行時間。

5.7 實驗結果分析

從前面分析已知，每個候選實例均要啟用回溯法搜索行實例來確定其為參與實例，這一過程較耗時，回溯搜索行實例是CPM-Col算法最耗時的步驟，尤其當數據集比較稠密時。CPM-iCol算法的兩個改進策略正是為避免實例的回溯搜索而提出的。

本節分析兩個算法對同一模式{Ad，Ai，Am，As}啟用的回溯搜索次數。使用Beijing-PoI數據進行實驗對比，實驗參數設置：距離閾值為400，頻繁度閾值為0.5。對于每個候選實例，確定其為參與實例而啟動的行實例回溯搜索的回溯次數往往是不一樣的。圖12橫軸為回溯次數，縱軸為啟動此回溯次數的實例數，將每個回溯次數下的實例數求和即為算法在此模式中啟動的總回溯次數。本文統計到CPM-Col算法在這個模式中總計啟用回溯搜索283次，而CPM-iCol算法在這個模式中總計啟用回溯搜索了47次。因此圖12表明在此模式中，大量實例由改進策略搜索到，避免了回溯搜索，表明本文方法是有效的。

6 結束語

空間并置模式挖掘因其可以發現空間特征間關聯關系而被廣泛應用。本文分析了現有CPM-Col算法的效率問題，提出了基于部分表實例和行實例間相互作用的改進措施，加速了參與實例的搜索，并在此基礎上提出了CPM-iCol算法。實驗結果證明，相對于CPM-Col，CPM-iCol空間占用略高，但具有更好的時間性能。在未來的工作中，考慮根據先驗知識保存部分表實例，以優化時空性能。

參考文獻：

［1］Huang Yan，Shekhar S，Xiong Hui. Discovering colocation patterns from spatial data sets： a general approach［J］. IEEE Trans on Knowledge & Data Engineering，2004，16（12）： 1472-1485.

［2］Li Jundong，Adilmagambetov A，Jabbar M，et al. On discovering co-location patterns in datasets： a case study of pollutants and child cancers［J］. Geoinformatica，2016，20： 651-692.

［3］He Zhanjun，Deng Min，Xie Zhong，et al. Discovering the joint influence of urban facilities on crime occurrence using spatial co-location pattern mining［J］. Cities，2020，99： 102612.

［4］Li Yan，Shekhar S. Local co-location pattern detection： a summary of results［C］// Proc of the 10th International Conference on Geographic Information Science. 2018： 1-10.

［5］Yao Xiaojing，Jiang Xufeng，Wang Dacheng，et al. Efficiently mining maximal co-locations in a spatial continuous field under directed road networks［J］. Information Sciences，2021，542： 357-379.

［6］Yu Wenhao. Spatial co-location pattern mining for location-based services in road networks［J］. Expert Systems with Applications，2016，46： 324-335.

［7］Cai Jiannan，Deng Min，Guo Yiwen，et al. Discovering regions of anomalous spatial co-locations［J］. International Journal of Geographical Information Science，2021，35（5）： 974-998.

［8］Cai Jiannan，Liu Qiliang，Deng Min，et al. Adaptive detection of statistically significant regional spatial co-location patterns［J］. Computers，Environment and Urban Systems，2018，68： 53-63.

［9］Deng Min，Cai Jiannan，Liu Qiliang，et al. Multi-level method for discovery of regional co-location patterns［J］. International Journal of Geographical Information Science，2017，31（9）： 1846-1870.

［10］Tran V，Wang Lizhen，Chen Hongmei，et al. MCHT： a maximal clique and hash table-based maximal prevalent co-location pattern mining algorithm［J］. Expert Systems with Applications，2021，175： 114830.

［11］Akbari M，Samadzadegan F，Weibel R. A generic regional spatio-temporal co-occurrence pattern mining model： a case study for air pollution［J］. Journal of Geographical Systems，2015，17： 249-274.

［12］Hu Zisong，Wang Lizhen，Tran V，et al. Efficiently mining spatial co-location patterns utilizing fuzzy grid cliques［J］. Information Sciences，2022，592： 361-388.

［13］Liu Qiliang，Liu Wenkai，Deng Min，et al. An adaptive detection of multilevel co-location patterns based on natural neighborhoods［J］. International Journal of Geographical Information Science，2021，35（3）： 556-581.

［14］楊培忠，王麗珍，王曉璇，等. 一種基于列計算的空間并置模式挖掘方法［J］. 中國科學： 信息科學，2022，52（6）： 1053-1068. （Yang Peizhong，Wang Lizhen，Wang Xiaoxuan，et al. A spatial co-location pattern mining approach based on column calculation［J］. Science in China： Information Sciences，2022，52（6）： 1053-1068.）

［15］Huang Yan，Shekhar S，Xiong Hui. Discovering colocation patterns from spatial data sets： a general approach［J］. IEEE Trans on Knowledge and Data Engineering，2004，16（12）： 1472-1485.

［16］Yoo J S，Shekhar S，Celik M. A join-less approach for co-location pattern mining： a summary of results［C］// Proc of the 5th IEEE International Conference on Data Mining. Piscataway，NJ： IEEE Press，2005： 4.

［17］Wang Lizhen，Bao Yuzhen，Lu J，et al. A new join-less approach for co-location pattern mining［C］// Proc of the 8th IEEE International Conference on Computer and Information Technology. Piscataway，NJ： IEEE Press，2008： 197-202.

［18］Wang Lizhen，Bao Yuzhen，Lu Zhongyu. Efficient discovery of spatial co-location patterns using the iCPI-tree［J］. The Open Information Systems Journal，2009，3（2）： 69-80.

［19］Lin Zhongshan，Lim S. Fast spatial co-location mining without cliqueness checking［C］// Proc of the 17th ACM Conference on Information and Knowledge Management. New York： ACM Press，2008： 1461-1462.

［20］Bao Xuguang，Wang Lizhen. A clique-based approach for co-location pattern mining［J］. Information Sciences，2019，490： 244-264.

［21］Tran V，Wang Lizhen，Zhou Lihua. Mining spatial co-location patterns based on overlap maximal clique partitioning［C］// Proc of the 20th IEEE International Conference on Mobile Data Management. Pisca-taway，NJ： IEEE Press，2019： 467-47.

［22］He Fei，Deng Xuemin，Fang Jinyun. A fast approach for spatial co-location pattern mining［C］// Proc of IEEE International Geoscience and Remote Sensing Symposium. Piscataway，NJ： IEEE Press，2013： 3654-3657.

［23］Sainju A M，Aghajarian D，Jiang Zhe，et al. Parallel grid-based co-location mining algorithms on GPUs for big spatial event data［J］. IEEE Trans on Big Data，2020，6（1）： 107-118.

［24］Yang Peizhong，Wang Lizhen，Wang Xiaoxuan. A MapReduce approach for spatial co-location pattern mining via ordered-clique-growth［J］. Distributed and Parallel Databases，2020，38： 531-560.

［25］Zou Muquan，Wang Lizhen，Wu Pingping. Efficiently mining maximal L-reachability co-location patterns from spatial data sets［J］. Intelligent Data Analysis，2023，27（1）： 269-295.

［26］Zhang Jinpeng，Wang Lizhen，Tran V. Spatial co-location pattern mining over extended objects based on cell-relation operations［J］. Expert Systems with Applications，2023，213： 119253.

［27］Tran V. Meta-PCP： a concise representation of prevalent co-location patterns discovered from spatial data［J］. Expert Systems with Applications，2023，213： 119255.

［28］Tran V，Wang Lizhen，Zhou Lihua. A spatial co-location pattern mining framework insensitive to prevalence thresholds based on overlapping cliques［J］. Distributed Parallel Databases，2023，41： 511-548.