昌鑫 蘆俊麗 陳書健 段鵬

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

關(guān)鍵詞：空間數(shù)據(jù)挖掘；空間并置模式；列計(jì)算；回溯搜索

中圖分類號：TP391?? 文獻(xiàn)標(biāo)志碼：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 引言

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

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

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

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

本文的主要貢獻(xiàn)如下：

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

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

c）在真實(shí)數(shù)據(jù)集和合成數(shù)據(jù)集上進(jìn)行了全面的實(shí)驗(yàn)，以證明技術(shù)的有效性、高效率和可擴(kuò)展性。

1 相關(guān)工作

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

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

2 相關(guān)概念

在空間數(shù)據(jù)集中，一個(gè)空間特征表示一個(gè)地理對象類型，特征的空間實(shí)例是一個(gè)具有位置信息的地理對象。F={f1， f2，…， fm}表示不同特征的集合，每個(gè)特征有對應(yīng)的實(shí)例，O={o1，o2，…，on}為所有實(shí)例的集合，其中每個(gè)實(shí)例由一個(gè)〈實(shí)例編號，特征類型，位置〉三元信息構(gòu)成。如果用歐氏距離度量兩實(shí)例間的鄰近關(guān)系R，則R（o，o′）distance（o，o′），其中distance（o，o′）是兩實(shí)例間的距離，d是用戶給定的距離閾值，可用歐幾里德距離。對于實(shí)例o，o的鄰居集是與o有鄰近關(guān)系的所有實(shí)例集合，記為Neighbor（o）={o′|o′∈O，R（o，o′）}。在o的鄰居集中，相同特征f的實(shí)例集合稱為o在f下的分組鄰居集［14］，記為groupN（o，f）={o′|o′∈Neighbor（o），o′.t=f}。如圖2（a）中，對于實(shí)例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中特征的數(shù)量［14］。實(shí)例集合RI={o1，o2，…，ok}被稱為C的行實(shí)例，如果：a）RI中任意兩個(gè)實(shí)例滿足鄰近關(guān)系R，也就是RI中的實(shí)例形成團(tuán)關(guān)系；b）RI中的實(shí)例數(shù)量與C的階數(shù)相等，并且RI中的實(shí)例覆蓋C中的所有特征［14］。模式C的行實(shí)例集合稱為表實(shí)例，表示為table_instance（C）［14］。為了更好地評價(jià)并置模式的頻繁性，文獻(xiàn)［1］提出了參與率和參與度。給定空間并置模式C={f1，f2，…，fk}，C中特征fi的參與率PR定義如下：

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

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

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

給定一個(gè)并置模式C，當(dāng)PI（C）大于等于給定的最小頻繁度閾值min_prev時(shí)，稱并置模式C是一個(gè)頻繁并置模式。

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

3 改進(jìn)策略

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

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

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

例3 圖3中，模式{A，B，C}的部分參與實(shí)例可以通過其子模式{A，B}的部分表實(shí)例得到。利用引理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的參與實(shí)例。

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

CPM-iCol在搜索參與實(shí)例時(shí)，將模式的特征按參與率上界降序排列，引理3只針對第一個(gè)特征求解，因?yàn)閰⑴c率上界高的特征更有可能與其他特征形成行實(shí)例。

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

實(shí)際應(yīng)用中，實(shí)例是錯(cuò)綜復(fù)雜的，引理3可以通過已知的一條行實(shí)例生成多個(gè)參與實(shí)例。

4 算法及分析

4.1 算法描述

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

算法1 CPM-iCol算法

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

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

算法2 isPrevalent（C）

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

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

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

4.2 算法分析

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

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

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

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

5 實(shí)驗(yàn)結(jié)果與分析

5.1 對比算法以及實(shí)驗(yàn)環(huán)境

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

本文CPM-iCol和對比算法均使用Python語言編寫，實(shí)驗(yàn)環(huán)境為：Intel CoreTM i5-6300HQ CPU2.30 GHz，16 GB內(nèi)存，Windows10操作系統(tǒng)。

5.2 實(shí)驗(yàn)數(shù)據(jù)集

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

5.3 實(shí)驗(yàn)評估

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

a）可伸縮性，測試算法在不同數(shù)據(jù)集和參數(shù)上的適應(yīng)性；

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

c）改進(jìn)算法效率分析，測試算法的兩個(gè)改進(jìn)效果及各個(gè)階段挖掘團(tuán)關(guān)系的情況；

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

5.4 可伸縮性

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

5.4.1 實(shí)例數(shù)量的影響

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

5.4.2 特征數(shù)量的影響

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

5.4.3 距離閾值的影響

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

5.4.4 頻繁性閾值的影響

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

頻繁性閾值決定了頻繁并置模式的數(shù)量，當(dāng)閾值較小時(shí)，滿足條件的模式更多。從圖中可以看出，在頻繁性閾值同為0.4時(shí)，CPM-Col在Beijing-PoI的效果優(yōu)于本文算法。這是因?yàn)樵诒本㏄oI的各個(gè)特征的實(shí)例是比較分散的，參與實(shí)例的團(tuán)關(guān)系不緊密，而上海PoI的實(shí)例比較密集，參與實(shí)例的團(tuán)關(guān)系緊密，利用引理2、3的效果好，所以本文算法更傾向于使用密集的數(shù)據(jù)。隨著頻繁性閾值增加，頻繁并置模式的數(shù)量減少，算法的時(shí)間減少是自然的。

5.5 改進(jìn)算法效率分析

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

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

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

5.6 算法剖析

本實(shí)驗(yàn)測試了CPM-Col和本文CPM-iCol在data-set3上各個(gè)步驟的執(zhí)行時(shí)間。參數(shù)設(shè)置：距離閾值為25，頻繁性閾值為0.7。

表2中列出的各個(gè)步驟的含義如下：

a）T_gen_neighbor是物化鄰近關(guān)系所用時(shí)間；

b）T_gen_candidates是生成候選模式所用時(shí)間；

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

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

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

f）T_total是算法的總運(yùn)行時(shí)間。

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

5.7 實(shí)驗(yàn)結(jié)果分析

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

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

6 結(jié)束語

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

參考文獻(xiàn)：

［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ì)算的空間并置模式挖掘方法［J］. 中國科學(xué)： 信息科學(xué)，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，F(xiàn)ang 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.