摘 要：空間并置模式是一組空間特征的子集，它們的實(shí)例在空間中頻繁關(guān)聯(lián)。空間并置模式挖掘是空間數(shù)據(jù)挖掘的一個(gè)重要分支。然而，空間數(shù)據(jù)庫隨時(shí)間不斷變化，高效的空間并置模式增量挖掘顯得尤為重要。提出基于變化參與實(shí)例的空間并置模式增量挖掘方法，相比傳統(tǒng)的增量挖掘算法，不進(jìn)行耗時(shí)的變化表實(shí)例生成操作，直接搜索變化參與實(shí)例。為加速變化參與實(shí)例搜索過程，提出了實(shí)例級(jí)搜索優(yōu)化策略、啟發(fā)式模式剪枝技術(shù)，進(jìn)而提出了IMCP-CPI，討論了算法的復(fù)雜度、正確性和完備性。在真實(shí)和模擬數(shù)據(jù)集上進(jìn)行了大量實(shí)驗(yàn)驗(yàn)證IMCP-CPI的性能。結(jié)果表明IMCP-CPI遠(yuǎn)優(yōu)于當(dāng)前已知的5個(gè)空間并置模式增量挖掘算法，其效率提升數(shù)倍甚至數(shù)個(gè)量級(jí)。在變化數(shù)據(jù)占比為原數(shù)據(jù)集5%的新數(shù)據(jù)集中，當(dāng)距離閾值d很大或者參與度閾值min_prev很小時(shí)，IMCP-CPI的性能比當(dāng)前并置模式挖掘較優(yōu)算法CPM-Col及改進(jìn)算法CPM-iCol提升2～3倍。此外，當(dāng)變化數(shù)據(jù)占比分別小于等于原數(shù)據(jù)集的25%和50%時(shí)，無論在參數(shù)變化還是可擴(kuò)展性方面，IMCP-CPI均優(yōu)于CPM-iCol和CPM-Col，這對(duì)具體實(shí)踐中的方法選取給與了參考意見。

關(guān)鍵詞： 空間并置模式挖掘； 增量挖掘； 變化參與實(shí)例； 實(shí)例搜索空間； 模式剪枝技術(shù)

中圖分類號(hào)： TP391

文獻(xiàn)標(biāo)志碼： A

文章編號(hào)： 1001-3695（2025）02-015-0431-10

doi： 10.19734/j.issn.1001-3695.2024.07.0277

Incremental mining method of spatial co-location patterns

based on changed participating instances

Lu Junli， Chang Xin， Luo Haoyu， Liu Shihu^’

（Dept. of Mathematics amp; Computer Science， Yunnan Minzu University， Kunming 650500， China）

Abstract：A spatial co-location pattern corresponds to a subset of spatial features， whose instances are frequently located in spatial neighborhoods. Spatial co-location pattern mining is an important direction of spatial data mining. However， spatial database is changing continually， efficient spatial co-location pattern incremental mining is vital. This paper presented an incremental mining method of spatial co-location patterns based on changed participating instances， which directly searched for changed participating instances without performing time-consuming operations of generating change table instances. Furthermore， to speed up the search of changed participating instances， this paper designed an instance searching optimization strategy and a heuristic pattern pruning technique. On this basis， this paper introduced incremental mining method of spatial co-location patterns based on changed participating instances（IMCP-CPI）， and comprehensively analyzed its complexity， correctness， and completeness. The extensive experiments on real and synthetic datasets validated the efficiency of IMCP-CPI algorithm. The results show that IMCP-CPI is much better than 5 known incremental mining algorithms of spatial co-location patterns， especially with a performance gain of several times or even orders of magnitude. In a new dataset where the proportion of changed data accounts for 5% of the original dataset， when the distance threshold d is very large or the participation threshold min_prev is very small， the performance of the IMCP-CPI is 2～3 times better than the current optimal algorithm for co-location pattern mining， CPM-Col， and its improved version CPM-iCol. Furthermore， when the proportion of changed data is less than or equal to 25% and 50% of the original dataset， respectively， IMCP-CPI outperforms both CPM-iCol and CPM-Col in terms of parameter variations and scalability. This provides valuable reference insights for method selection in practical applications.

Key words：spatial co-location pattern; incremental mining; changed participation instance; instance search space; pattern pruning technique

0 引言

空間數(shù)據(jù)挖掘是從空間數(shù)據(jù)庫中發(fā)現(xiàn)潛在有趣模式的過程。空間并置模式挖掘是空間數(shù)據(jù)挖掘的一個(gè)重要分支，旨在發(fā)現(xiàn)空間特征（事物）之間的關(guān)聯(lián)關(guān)系。并置模式代表了一組空間特征的子集，它們的實(shí)例在空間中頻繁關(guān)聯(lián)^［1］。例如，植物學(xué)家發(fā)現(xiàn)80%的蘭類植物生長(zhǎng)在中濕度寬葉森林中。在城市元素?cái)?shù)據(jù)庫中，醫(yī)院附近總是圍繞著花店、水果店、藥店。這些發(fā)現(xiàn)有助于人們了解事物間的關(guān)聯(lián)關(guān)系，進(jìn)而去追蹤分析事物間的共生關(guān)系^［2］、競(jìng)爭(zhēng)關(guān)系^［3］、因果關(guān)系^［4］、主導(dǎo)關(guān)系^［5］等，其應(yīng)用包括地球科學(xué)、公共衛(wèi)生、生態(tài)學(xué)、交通運(yùn)輸?shù)群芏囝I(lǐng)域。

空間并置模式的概念首次由文獻(xiàn)［1］提出，使用特征實(shí)例的最小參與率即參與度作為模式頻繁性度量（2.1節(jié)介紹相關(guān)概念），提出基于全連接的表實(shí)例生成策略。之后，很多學(xué)者從并置模式挖掘效率^［6～11］、不同應(yīng)用領(lǐng)域^{［12～16］}、閾值選擇^{［17～18］}等方面進(jìn)行了廣泛研究。

在并置模式挖掘中，表實(shí)例生成是計(jì)算模式參與度的關(guān)鍵，也是最耗時(shí)的步驟^［6］。在提升并置模式挖掘效率的研究工作中，主要集中在物化鄰近關(guān)系以快速生成模式的表實(shí)例，并提出一些優(yōu)化算法。文獻(xiàn)［6］提出joinless算法，避免了文獻(xiàn)［1］中大量表實(shí)例連接操作，使用星型鄰居物化空間鄰近關(guān)系，通過星型鄰居快速產(chǎn)生模式的星型實(shí)例，由星型實(shí)例進(jìn)行團(tuán)關(guān)系檢查生成表實(shí)例。Wang等人^［7］提出CPI-tree結(jié)構(gòu)物化空間鄰近關(guān)系，通過深度優(yōu)先遍歷CPI-tree生成所有模式的表實(shí)例，不需要團(tuán)關(guān)系檢查。隨后，文獻(xiàn)［8］改進(jìn)了CPI-tree算法，提出iCPI-tree物化模型，以寬度優(yōu)先遍歷的方式逐階生成模式的表實(shí)例。近來，文獻(xiàn)［9，10］提出了基于MapReduce^［9］和GPU^［10］的并行挖掘算法，提高了挖掘效率。文獻(xiàn)［11］突破以往依賴表實(shí)例計(jì)算參與率的思路，不生成和存儲(chǔ)模式表實(shí)例，直接計(jì)算各特征在模式中的參與實(shí)例集，得到參與率和參與度。因此，算法具有更好的性能和時(shí)空擴(kuò)展性。文獻(xiàn)［12］針對(duì)文獻(xiàn)［11］計(jì)算參與實(shí)例時(shí)啟用的耗時(shí)的回溯搜索操作提出兩點(diǎn)改進(jìn)，得到更好的算法性能和可擴(kuò)展性，尤其在稠密數(shù)據(jù)中。

在不同應(yīng)用領(lǐng)域中，并置模式挖掘需作相應(yīng)調(diào)整。文獻(xiàn)［13］基于極大團(tuán)和多密度聚類的方法挖掘區(qū)域并置模式，并給出每個(gè)模式的頻繁區(qū)域；文獻(xiàn)［14］將研究對(duì)象進(jìn)行擴(kuò)展，研究從空間擴(kuò)展對(duì)象（如線、面等）數(shù)據(jù)中挖掘并置模式，突破了傳統(tǒng)方法只能處理點(diǎn)對(duì)象的限制；文獻(xiàn)［15］基于分支和深度擴(kuò)展的方式快速挖掘高效用空間并置模式，把特征在實(shí)際問題中的效用作為興趣度度量指標(biāo)；文獻(xiàn)［16］挖掘高平均效用的空間并置模式，考慮效用后，進(jìn)一步考慮模式長(zhǎng)度對(duì)效用度量的干擾，重新定義更合理的度量，這些研究使得空間并置模式挖掘在實(shí)際問題中更易理解和應(yīng)用；文獻(xiàn)［17］考慮在限定不那么嚴(yán)格但可挖掘到更多信息的亞頻繁模式中挖掘帶主導(dǎo)特征的模式。

空間并置模式挖掘算法的性能和挖掘結(jié)果均受距離閾值（判定實(shí)例間鄰近關(guān)系）和頻繁度閾值（判定模式頻繁性）影響。在實(shí)際應(yīng)用中，不同應(yīng)用下的閾值很難確定，往往要重復(fù)幾次實(shí)驗(yàn)才能確定合理閾值。文獻(xiàn)［18］提出了一個(gè)基于重疊團(tuán)的對(duì)頻繁度閾值不敏感的空間并置模式挖掘框架，基于重疊團(tuán)計(jì)算模式的表實(shí)例，當(dāng)頻繁度閾值改變時(shí)，可根據(jù)表實(shí)例快速得到頻繁并置模式。為優(yōu)化表實(shí)例存儲(chǔ)和搜索，使用哈希結(jié)構(gòu)實(shí)現(xiàn)快速直接計(jì)算和定位，文獻(xiàn)［19］基于Voronoi圖劃分鄰域、定義鄰近關(guān)系。此劃分方法解決了空間實(shí)例分布密度差異顯著時(shí)，距離閾值難確定的問題。

在實(shí)際應(yīng)用中，數(shù)據(jù)庫中的數(shù)據(jù)隨時(shí)間不斷更新，其更新速度非常之快，而更新的數(shù)據(jù)量相對(duì)于基礎(chǔ)數(shù)據(jù)量并不大。因此，高效的空間并置模式增量挖掘顯得非常必要。

文獻(xiàn)［20］在數(shù)據(jù)更新中只考慮了新增的數(shù)據(jù)，沒有考慮消失的數(shù)據(jù)，實(shí)際問題中，數(shù)據(jù)更新既包含新增又包含消失。文獻(xiàn)［21，22］在并置模式增量挖掘過程中，同時(shí)考慮了數(shù)據(jù)新增和消失兩種情況。文獻(xiàn)［21］從模式在原數(shù)據(jù)集的表實(shí)例中刪除消失的行實(shí)例，加入新增的行實(shí)例，得到了模式在新數(shù)據(jù)集中的表實(shí)例，利用表實(shí)例計(jì)算參與率和參與度。文獻(xiàn)［22］利用模式在原數(shù)據(jù)集中的參與率，加之計(jì)算消失的行實(shí)例和新增的行實(shí)例，重新定義模式在新數(shù)據(jù)集中的參與率和參與度。以上兩文獻(xiàn)都是從二階模式開始按層次挖掘新數(shù)據(jù)集中的頻繁模式。文獻(xiàn)［23］從原數(shù)據(jù)集中頻繁模式與非頻繁模式邊界開始挖掘，重新尋找新數(shù)據(jù)集中頻繁模式與非頻繁模式邊界。綜上，現(xiàn)有增量挖掘算法耗時(shí)部分主要體現(xiàn)在模式消失的行實(shí)例和新增的行實(shí)例計(jì)算。

空間數(shù)據(jù)的不斷增減導(dǎo)致空間并置模式集不斷變化。因此，高效的模式增量挖掘至關(guān)重要。與以往增量挖掘算法不同，本文不生成耗時(shí)的變化表實(shí)例，通過少部分行實(shí)例搜索，直接確定各特征在模式中的所有變化參與實(shí)例，提出了IMCP-CPI算法（incremental mining of co-location patterns based on changed participating instances）。IMCP-CPI主要從三方面提升性能：a）基于變化參與實(shí)例計(jì)算模式在新數(shù)據(jù)集中的參與度，避免了變化表實(shí)例的生成在時(shí)間、空間上的巨大消耗；b）為加速變化參與實(shí)例的搜索過程，提出了實(shí)例級(jí)搜索優(yōu)化策略及剪枝技術(shù)，目的是盡可能地縮小搜索空間，高效地搜索消失（新增）參與實(shí)例；c）在搜索變化參與實(shí)例集之前，啟發(fā)式逐步感知部分模式的頻繁性，及時(shí)終止不頻繁模式的搜索，提高模式頻繁性更新效率。本文在真實(shí)和模擬數(shù)據(jù)集上進(jìn)行了大量實(shí)驗(yàn)驗(yàn)證IMCP-CPI的性能。

1 基本理論

1.1 空間并置模式挖掘基本概念及理論

a）特征^［1］。在空間數(shù)據(jù)集中，用特征表示事物，記F={f₁， f₂，…， f_n}為特征集合。

b）實(shí)例^［1］。實(shí)例為特征在某一位置的個(gè)體。記O={o₁，o₂，…，o_m}為實(shí)例集合，每個(gè)實(shí)例為一個(gè)三元組（編號(hào)、特征和位置）。

c）鄰近關(guān)系^［1］。給定距離閾值d，如果兩個(gè)實(shí)例的距離不大于d，則稱它們之間具有鄰近關(guān)系，表示為R（o，o′）distance（o，o′）≤d，其中distance（o，o′）表示實(shí)例o和o′的距離，常用歐幾里德距離。

e）分組鄰居集^［11］。若將實(shí)例o的鄰居集按其特征分組，則o在特征f（o.t≠f）中的分組鄰居集為groupN（o，f）={o′|o′∈Neigh（o），o′.t=f}。

例1 圖1（a）為空間實(shí)例集，共有{A，B，C，D}四個(gè)特征，各特征不同位置的實(shí)例使用編號(hào)區(qū)分。具有鄰近關(guān)系的實(shí)例用實(shí)線連接。對(duì)于實(shí)例A.1，有Neigh（A.1）={B.1，C.3，D.1}，groupN（A.1，B）={B.1}。

f）空間并置模式^［1］。空間并置模式是空間特征的一個(gè)子集，C={f₁，f₂，…，f_k}，k≥2，C∈F。C為一個(gè)k階模式，模式的階是指模式中的特征個(gè)數(shù)。

h）行實(shí)例^［1］。實(shí)例集合RI（C）={o₁，o₂，…，o_k}稱為模式C的一個(gè)行實(shí)例，如果RI（C）滿足（a） RI（C）中的實(shí)例涵蓋了C中的所有特征，（b） RI（C）中的任意兩個(gè)實(shí)例具有鄰近關(guān)系。也就是說，RI（C）中的實(shí)例形成團(tuán)。

i）表實(shí)例^［1］。模式的行實(shí)例集合稱為表實(shí)例，表示為TI（C）。

j）參與率^［1］。特征f在C中的參與率表示為PR（C， f）。

PR（C， f）=|∏_f（TI（C））||N（f）|（1）

其中：|N（f）|表示特征 f的實(shí)例集；∏為帶去重的投影操作，用于找到表實(shí)例中f的不重復(fù)實(shí)例集；|·|為集合元素?cái)?shù)。

k）參與度^［1］。模式C的參與度記作PI（C），是C中各特征的參與率最小值，即

PI（C）=min^k_i=1{PR（C， f_i）}（2）

l）頻繁并置模式^［1］。給定頻繁度閾值min_prev，如果模式C滿足PI（C）≥min_prev，則稱C為頻繁并置模式?？臻g并置模式挖掘旨在發(fā)現(xiàn)空間實(shí)例集中的所有頻繁并置模式。

例2 圖1中，{A， D}為一個(gè)2階模式，{A， C， D}為{A， D}的超模式，{A， D}為{A， C， D}的子模式。{A.1， D.1}為{A， D}的一條行實(shí)例，圖1（b）列出{A， D}的表實(shí)例，并計(jì)算了每個(gè)特征的參與率和模式參與度。設(shè)頻繁度閾值min_prev=0.3，則PI（{A，D}）=1gt;min_prev，{A， D}為頻繁并置模式。

文獻(xiàn)［1］已經(jīng)證明模式參與度的反單調(diào)性，即模式的參與度隨著模式階的增大非遞增。由此可得模式的向下閉合性，即一個(gè)不頻繁模式的超模式均不頻繁，一個(gè)頻繁模式的子模式均頻繁。模式的向下閉合性質(zhì)可用于模式剪枝。

1.2 基于列計(jì)算的空間并置模式挖掘

在空間并置模式挖掘中，最耗時(shí)的操作是生成模式的表實(shí)例。當(dāng)特征數(shù)量眾多、鄰近關(guān)系復(fù)雜時(shí)，表實(shí)例可能是巨大的。文獻(xiàn)［11］提出基于列計(jì)算的空間并置模式挖掘方法。該方法不需要生成、存儲(chǔ)完整的表實(shí)例，而是通過部分行實(shí)例搜索，確定模式中每個(gè)特征的參與實(shí)例集計(jì)算特征的參與率，進(jìn)而計(jì)算參與度。

參與實(shí)例^［11］：模式C中特征f的參與實(shí)例集Obj（C， f）定義為Obj（C， f）={o|o.t=f∧oinRI（C）}。則模式C中特征f的參與率為PR（C， f）=|Obj（C， f）||N（f）|。

圖1（c）列出了{(lán)A， D}中特征A和D的參與實(shí)例集，并計(jì)算了參與率和模式參與度，結(jié)果與基于表實(shí)例方法相同。

2 基于列計(jì)算的并置模式增量挖掘

高效的增量挖掘算法，一定是充分利用原數(shù)據(jù)集的挖掘結(jié)果，只計(jì)算變化數(shù)據(jù)對(duì)模式頻繁性的影響，來確定模式在新數(shù)據(jù)集中的頻繁性。

實(shí)例消失，其鄰近關(guān)系及在模式中的參與實(shí)例都會(huì)隨之消失。實(shí)例新增，會(huì)帶來新增的鄰近關(guān)系，進(jìn)而在模式中產(chǎn)生新的參與實(shí)例。參與實(shí)例發(fā)生改變，就可能會(huì)影響模式的頻繁性。接下來，確定每個(gè)消失（新增）實(shí)例的鄰居集，以確定其影響范圍。

例3 圖2為相對(duì)于圖1中的原空間實(shí)例集在部分實(shí)例消失和新增后得到的新空間實(shí)例集。其中藍(lán)色代表消失的實(shí)例，紅色代表新增的實(shí)例（見電子版），虛線代表消失的鄰近關(guān)系。消失實(shí)例A.1的鄰居集為Neigh（A.1）={B.1，C.3，D.1}，在特征C中的分組鄰居集為groupN（A.1，C）={C.3}。

定義1 新數(shù)據(jù)集中的參與率。一個(gè)空間實(shí)例集在經(jīng)歷部分實(shí)例變化后，得到新數(shù)據(jù)集。新數(shù)據(jù)集中特征f在模式C中的參與率為

NPR（C， f）=|Obj（C， f）－Dobj（C， f）∪Aobj（C， f）||N（f）|－|O_dis（f）|+|O_add（f）|（3）

其中：N（f）為原空間實(shí)例集中特征f的實(shí)例集；O_dis（f）和O_add（f）分別為f的消失實(shí)例集和新增實(shí)例集。Obj（C， f）為原空間實(shí)例集中特征f參與到模式C中的參與實(shí)例集，D_obj（C， f）和A_obj（C， f）分別為f在C中的消失參與實(shí)例集和新增參與實(shí)例集，消失參與實(shí)例集和新增參與實(shí)例集構(gòu)成模式在特征f下的變化參與實(shí)例集。|·|表示集合元素個(gè)數(shù)。

圖2 新空間實(shí)例集及各特征實(shí)例數(shù)Fig.2 New dataset and the number of instances of each feature

模式C中特征f（f∈C）的消失參與實(shí)例指原本是f在C中的參與實(shí)例，因自身消失或C中除f外其他特征的實(shí)例消失，不能再形成C的任何行實(shí)例的實(shí)例。其中D_obj（C， f）=D_{obj_self}（C， f）+D_{obj_in}（C， f），D_{obj_self}（C， f）中的消失參與實(shí)例是因自身消失而致（由4.1.1節(jié)計(jì)算），D_{obj_in}（C， f）中的消失參與實(shí)例是因消失參與實(shí)例影響而致（由4.1.2節(jié)計(jì)算）。

模式C中特征f（f∈C）的新增參與實(shí)例指f的某一實(shí)例，原本不是f在C中的參與實(shí)例，因自身新增或C中除f外其他特征的實(shí)例新增，形成了C的行實(shí)例的實(shí)例。其中A_obj（C， f）=A_{obj_self}（C， f）+A_{obj_in}（C， f），A_{obj_self}（C， f）中的新增參與實(shí)例是因自身新增而致（由4.1.1節(jié)計(jì)算），A_{obj_in}（C， f）中的新增參與實(shí)例是因新增參與實(shí)例影響而致（由4.1.2節(jié)計(jì)算）。

模式C（假設(shè)C為一k階模式）在新數(shù)據(jù)集中的參與度為C中特征的參與率最小值，即

NPI（C）=min^k_i=1{NPR（C， f_i）}（4）

引理1 正確性。定義1計(jì)算的新數(shù)據(jù)集中特征f在模式C中的參與率與直接在新數(shù)據(jù)集中計(jì)算結(jié)果是一樣的。

證明 分母|N（f）|－|O_dis（f）|+|O_add（f）|就是特征f在新數(shù)據(jù)集中的實(shí)例總數(shù)，分子用原數(shù)據(jù)集中特征f在C中的參與實(shí)例集，減去f在C中的消失參與實(shí)例，并入f在C中的新增參與實(shí)例，即為新數(shù)據(jù)集中f在C中的參與實(shí)例集。

由于NPR（C， f）和NPI（C）就是模式C在新數(shù)據(jù)集中的參與率和參與度，根據(jù)文獻(xiàn)［1］對(duì)模式參與度的反單調(diào)性和模式向下閉合性質(zhì)的闡述，NPR（C， f）滿足反單調(diào)性，模式滿足向下閉合性，所以可提前剪掉子模式不頻繁的超模式。

在海量空間數(shù)據(jù)尤其是稠密數(shù)據(jù)中，實(shí)例間的鄰近關(guān)系是錯(cuò)綜復(fù)雜的，實(shí)例變化會(huì)引起大量鄰近關(guān)系的變化。因此，針對(duì)某一模式，如何篩選其變化實(shí)例，如何快速搜索變化實(shí)例對(duì)模式中其他特征參與實(shí)例的影響，以便確定模式中每個(gè)特征的變化參與實(shí)例集，是空間并置模式增量挖掘急需解決的問題。接下來，將探索變化實(shí)例篩選策略及影響實(shí)例搜索策略，提升搜索效率。

3 變化參與實(shí)例求解策略

判斷一個(gè)消失（新增）實(shí)例及其影響實(shí)例是否為消失（新增）參與實(shí)例時(shí)，往往需要驗(yàn)證它能否在模式下其他特征的所有實(shí)例中形成一條行實(shí)例，由于搜索空間較大以及團(tuán)關(guān)系判斷的復(fù)雜性，這一操作往往非常耗時(shí)。此外，若在增量挖掘過程中，能提前感知模式的頻繁性，及時(shí)終止不頻繁模式，就可以提高挖掘效率。針對(duì)以上兩種情況，本章設(shè)計(jì)了實(shí)例級(jí)和模式級(jí)兩級(jí)優(yōu)化策略，縮小實(shí)例搜索空間，提前剪掉不頻繁的模式。

3.1 實(shí)例級(jí)優(yōu)化策略——縮小實(shí)例搜索空間

本節(jié)對(duì)實(shí)例搜索空間進(jìn)行優(yōu)化，首先介紹變化實(shí)例篩選策略，即判斷變化實(shí)例因自身變化導(dǎo)致的變化參與實(shí)例時(shí)進(jìn)行的實(shí)例篩選策略，再介紹影響實(shí)例搜索策略，即判斷影響實(shí)例是否為模式的變化參與實(shí)例時(shí)進(jìn)行的搜索空間優(yōu)化。

3.1.1 變化實(shí)例篩選策略

針對(duì)某一模式C，不是每個(gè)變化實(shí)例都會(huì)對(duì)其頻繁性造成影響。下面定義C中f（f∈C）的候選變化實(shí)例集，再確定候選變化實(shí)例是否為變化參與實(shí)例。

定義2 候選消失實(shí)例集。模式C在特征f（f∈C）中的候選消失實(shí)例o_dis需來自于f在C中的原參與實(shí)例集Obj（C， f）。則候選消失實(shí)例集DOC（C， f）為

DOC（C， f）={o_dis|o_dis∈O_dis∩Obj（C， f）}（5）

定義3 候選新增實(shí)例集。模式C在特征f（f∈C）中的候選新增實(shí)例o_add需滿足o_add的特征等于f，且o_add及其鄰居集對(duì)應(yīng)的特征集包含C。則候選新增實(shí)例集AOC（C， f）為

其中：（{o_add}∪Neigh（o_add））.t為新增實(shí)例o_add及其在O_new中鄰居集對(duì)應(yīng)的特征集合。

引理2 完備性。模式C在特征f（f∈C）中的候選變化實(shí)例集是完備的。

例4 若一變化實(shí)例已經(jīng)被確定為模式C在特征f（f∈C）中的候選變化實(shí)例，如何確定它就為C在f中的變化參與實(shí)例呢？圖3為候選變化實(shí)例確定為變化參與實(shí)例示意圖。對(duì)于消失情況，模式C在f中的候選消失實(shí)例顯然就是C在f中的消失參與實(shí)例，即DOC（C， f）=D_{obj_self}（C， f）。

3.1.2 影響實(shí)例搜索策略

上節(jié)確定了模式C特征f中因自身變化而產(chǎn)生的變化參與實(shí)例，本節(jié)將計(jì)算f中被C的其他特征f′（f′∈C－{f}）的變化參與實(shí)例影響的實(shí)例，并判斷影響實(shí)例是否為變化參與實(shí)例。

定義4 消失參與實(shí)例的影響實(shí)例集。對(duì)于模式C和特征f（f∈C），C中其他特征f′（f′∈C－{f}）的消失參與實(shí)例對(duì)f的影響實(shí)例集定義為

3.2 模式級(jí)優(yōu)化策略——啟發(fā)式模式剪枝

在并置模式增量挖掘算法中，為驗(yàn)證某一實(shí)例是否為變化參與實(shí)例而進(jìn)行的行實(shí)例搜索是最耗時(shí)步驟。3.1節(jié)已經(jīng)通過縮小實(shí)例搜索空間來提高搜索效率，本節(jié)將從模式級(jí)進(jìn)行剪枝。在驗(yàn)證變化參與實(shí)例集過程中，提出啟發(fā)式的模式剪枝策略，逐步感知模式的頻繁性，及時(shí)終止不頻繁模式的變化參與實(shí)例搜索，提高模式頻繁性更新效率。給定一模式C，C中特征f（f∈C） 變化參與實(shí)例集搜索流程包含四個(gè)步驟如圖6所示，由于候選消失實(shí)例即為消失參與實(shí)例，圖6中的第一步不必搜索行實(shí)例，啟發(fā)式模式剪枝策略在a）～c）三處實(shí)施，表1給出啟發(fā)式模式剪枝策略使用的模式參與率上限。

空間并置模式增量挖掘中最耗時(shí)的步驟是為驗(yàn)證某一候選變化實(shí)例或某一影響實(shí)例是否為變化參與實(shí)例時(shí)進(jìn)行的行實(shí)例搜索。而啟發(fā)式模式剪枝策略使用的參與率上限無需搜索行實(shí)例。因此，借助引理7可以在進(jìn)行耗時(shí)操作之前剪掉不頻繁模式，提高挖掘效率。

4 算法設(shè)計(jì)與分析

4.1 算法設(shè)計(jì)

基于第2章新數(shù)據(jù)集O_new中模式參與度度量公式和第3章的變化參與實(shí)例求解策略，本章提出IMCP-CPI算法（算法1），在O_new中進(jìn)行增量挖掘空間并置模式。首先將原、新數(shù)據(jù)集相減，獲得消失實(shí)例集O_dis和新增實(shí)例集O_add（第1行）。第2行計(jì)算空間鄰近關(guān)系，并以每個(gè)實(shí)例在不同特征中的分組鄰居進(jìn)行物化。第3行初始化每個(gè)特征為一階頻繁并置模式，作為迭代的開始。第4～13行從二階開始，逐階生成候選模式，并判斷每個(gè)候選模式的頻繁性，直到?jīng)]有任何頻繁并置模式被找到為止，算法最終返回所有的頻繁并置模式。第7行調(diào)用isPrevalent_newdataset（C）過程是IMCP-CPI算法的核心。

在isPrevalent_newdataset（C）過程（算法2）中，若C的任一子模式在新數(shù)據(jù)集中不頻繁，根據(jù)模式向下閉合性理論^［1］，則C不頻繁（第1～3行）。第4～8行針對(duì)模式C在原數(shù)據(jù)集中不頻繁的情況，補(bǔ)充計(jì)算其在原數(shù)據(jù)集各特征f中未計(jì)算的參與實(shí)例集Obj（C， f）。第9～15行計(jì)算特征f的候選消失實(shí)例集DOC（C， f）、候選新增實(shí)例集AOC（C， f）、f′（f′∈C－{f}）中消失參與實(shí)例對(duì)特征f的Din_set（C， f）和新增參與實(shí)例對(duì)特征f的Ain_set（C， f），為啟發(fā)式模式剪枝策略中的參與率上限計(jì)算做準(zhǔn)備。第16～20行計(jì)算模式C中每個(gè)特征f因自身消失而產(chǎn)生的消失參與實(shí)例集Dobj_self（C， f），第21～32行計(jì)算模式C中每個(gè)特征f的Dobj_in（C， f）、Aobj_self（C， f）和Aobj_in（C， f）。第19、23、26行計(jì)算相應(yīng)參與率上限執(zhí)行啟發(fā)式模式剪枝策略，并在第28行計(jì)算參與率，進(jìn)行模式頻繁性判斷。

第17行將特征f的消失參與實(shí)例集Dobj_self（C， f）和Dobj_in（C， f）初始化為空，將原數(shù)據(jù)集中f的參與實(shí)例集Obj（C， f）賦給當(dāng)前參與實(shí)例集Cur_Obj（C， f）。由于特征f的候選消失實(shí)例即為f的消失參與實(shí)例，將消失參與實(shí)例從Cur_Obj（C， f）中移除，放入Dobj_self（C， f）（第18行）。第22行調(diào)用Dis_Influence_object（C， f，Din_set（C， f））過程驗(yàn)證Din_set（C， f）中的影響實(shí)例是否為消失參與實(shí)例。

第24行將特征f的新增實(shí)例集Aobj_self（C， f）和Aobj_in（C， f）初始化為空。第25行調(diào)用Add_Influence_object（C， f，AOC（C， f））過程驗(yàn)證AOC（C， f）中的候選新增實(shí)例是否為新增參與實(shí)例，第27行調(diào)用Add_Influence_object（C， f，Ain_set（C， f））過程驗(yàn)證Ain_set（C， f）中的影響實(shí)例是否為新增參與實(shí)例。第22、25、27行調(diào)用了Dis_Influence_object和Add_Influence_object過程。

算法2 isPrevalent_newdataset（C）過程

1 if C的任一子集不在P_new then

2 return 1

3 end if

4 if C is not in P_old then // C在原數(shù)據(jù)集中不頻繁

5 for each f∈C do

6

若Obj（C， f）=，計(jì)算原數(shù)據(jù)集上模式C中特征f的參與實(shí)例集Obj（C， f）;

7 end for

8 end if

9 for each f∈C do

10 根據(jù)式（5）（6）計(jì)算特征f的候選消失實(shí)例集DOC（C， f）和候選新增實(shí)例集AOC（C， f）;

11 for each f′∈C－{f} do

12

根據(jù)式（8）計(jì)算f′中消失參與實(shí)例對(duì)特征f的Din_set（C， f）;

13

根據(jù)式（9）計(jì)算f′中新增參與實(shí)例對(duì)特征f的Ain_set（C， f）;

14

end for

15 end for

16 for each f∈C do

17

Dobj_self（C， f）=，Dobj_in（C， f）=，Cur_Obj（C， f）=Obj（C， f）;

18

對(duì)每個(gè)o_dis∈DOC（C， f），Cur_Obj（C， f）－={o_dis}， Dobj_self（C， f）∪={o_dis}; //求解 Dobj_self（C， f）

19

計(jì)算UP_NPR1（C， f），并利用引理7進(jìn)行剪枝;

20 end for

21 for each f∈C do

22

Dis_Influence_object（C， f，Din_set（C， f））; /*求解 Dobj_in（C， f）*/

23

計(jì)算UP_NPR2（C， f），并利用引理7進(jìn)行剪枝;

24

Aobj_self（C， f）=U，Aobj_in（C， f）=;

25

Add_Influence_object（C， f，AOC（C， f））; /*求解 Aobj_self（C， f）*/

26

計(jì)算UP_NPR3（C， f），并利用引理7進(jìn)行剪枝;

27

Add_Influence_object（C， f，Ain_set（C， f））; /*求解 Aobj_in（C， f）*/

28

根據(jù)式（3）計(jì)算NPR（C， f）;

29

if NPR（C， f）lt;min_prev then

30

return 1

31 end for

32 return true

Dis_Influence_object過程（算法3）對(duì)Din_set（C， f）中每個(gè)影響實(shí)例o_in進(jìn)行判斷，搜索o_in與C的特征f′（C－{f}）中的實(shí)例搜索空間（式（10））中的實(shí)例形成行實(shí)例情況（第2行），o_in不能形成行實(shí)例意味著它是消失參與實(shí)例，將其從Cur_Obj（C， f）中移除，放入Dobj_in（C， f）（第3～5行）。

Add_Influence_object過程（算法4）對(duì)AOC（C， f）（Ain_set（C， f））中沒有被識(shí)別的實(shí)例o進(jìn)行判斷，搜索o與C的特征f′（C－{f}）中的實(shí)例搜索空間（式（7）（11））中的實(shí)例形成行實(shí)例情況（第3行）， o形成行實(shí)例意味著它是新增參與實(shí)例，則行實(shí)例中每個(gè)不在Cur_Obj（C，o′.t）中的實(shí)例均為C的新增參與實(shí)例，將其同時(shí)放入Cur_Obj（C，o′.t）和Aobj_self（C，o′.t）或Aobj_in（C，o′.t）（第4～15行）。

算法2～4中的ResearchRI（o， C）過程是利用回溯算法搜索實(shí)例o在C的特征f′（C－{o.t}）中位于實(shí)例搜索空間中的實(shí)例形成行實(shí)例過程，此算法與文獻(xiàn)［11］中的ResearchRI（o， C）過程完全相同，這里就不再贅述。

4.2 示例分析

圖4為空間并置模式增量挖掘過程示例（數(shù)據(jù)集的變化情況如圖2所示）。設(shè)min_prev=0.3，原數(shù)據(jù)集中頻繁模式為{A， B}、{A， C}、{A， D}、{B， C}、{C， D}、{A， C， D}。

從二階模式開始，按階進(jìn)行增量挖掘。圖6（a）中藍(lán)色實(shí)例為消失實(shí)例，對(duì)于每個(gè)模式的每個(gè)特征，移除消失實(shí)例，放入相應(yīng)Dobj_self（C， f）（算法2第16～20行）。計(jì)算每個(gè)模式的UP_NPR1（C， f）（算法2第19行），可得UP_NPR1（{B，C}，C）=1/4lt;min_prev，則{B， C}及其超模式{A， B， C}、{B， C， D}、{A， B， C， D}均被剪掉，如圖4（a）所示。

接下來，根據(jù)算法2第22行，判定模式中其它特征的消失參與實(shí)例對(duì)該特征的影響實(shí)例是否為消失參與實(shí)例，得到圖4（b）。利用UP_NPR2（C， f）未能剪掉任何模式（算法2第23行）。接下來處理新增情況，將候選新增實(shí)例及影響實(shí)例均進(jìn)行新增參與實(shí)例判定（算法2第24～27行），得到圖4（c）。利用UP_NPR3（C， f）未能剪掉任何模式（算法2第26行）。根據(jù)計(jì)算得增量挖掘結(jié)果即新數(shù)據(jù)集中的頻繁并置模式為{A， B}、{A， C}、{A， D}、{B， D}、{C， D}、{A， C， D}。

算法3 Dis_Influence_object（C， f，Din_set（C， f））過程

1 for each o_in∈Din_set（C， f） do

2 RI（C）=ResearchRI（o_in， C） //回溯搜索行實(shí)例

3 if RI（C）== then //若不存在行實(shí)例，說明o_in是消失參與實(shí)例

4

Cur_Obj（C， f）－={o_in}，DObj_in（C， f）∪={o_in}

5 end if

6 end for

算法4 Add_Influence_object（C， f，AocorAin_set（C， f））

1 for each o∈AocorAin_set（C， f） do

2 if o （AObj_self（C， f）∪AObj_in（C， f）） then

3

RI（C）=ResearchRI（o， C） //回溯搜索行實(shí)例

4

if RI（C）≠ then /*存在行實(shí)例，說明o是新增參與實(shí)例*/

5

for each o′∈RI（C） do

6

if o′ is not in Cur_Obj（C，o′.t） then /*不在，才是新增*/

7

Cur_Obj（C，o′.t）∪={o′}

8

if o′∈O_add（o′.t） then//若o′為新增實(shí)例

9

AObj_self（C，o′.t）∪={o′}；

10

else

11

AObj_in（C，o′.t）∪={o′}；

12

end if

13

end if

14

end for

15

end if

16 end if

17 end for

4.3 算法分析

1）時(shí)間復(fù)雜度

設(shè)O_old、O_new、O_dis、O_add四個(gè)數(shù)據(jù)集大小分別為|O_old|、|O_new|、|O_dis|和|O_add|，算法1的時(shí)間復(fù)雜度為O（∑k_numk=2|C_k|×k×n₁×n^k－1₂），其中，k為模式的階數(shù)，k_num為能夠挖掘到的候選模式最大階數(shù)，|C_k|為k階候選模式數(shù)，k×n₁×n^k－1₂為判斷每個(gè)k階候選模式的時(shí)間耗費(fèi)，具體如下。

第1行若采用哈希表存儲(chǔ)兩數(shù)據(jù)集，集合相減最壞情況下的復(fù)雜度為O（max（|O_old|，|O_new|）），第2行計(jì)算空間鄰近關(guān)系最壞情況下的復(fù)雜度為O（|O_dis|×（|O_old|－|O_dis|）+|O_add|×|O_new|）。第4～13行從二階模式開始逐階挖掘，在第k（k≥2）次迭代中，生成候選模式數(shù)量為|C_k|，復(fù)雜度為O（|C_k|）。對(duì)于C_k中的每個(gè)候選模式C，調(diào)用isPrevalent_newdataset（C）過程判斷其頻繁性，在isPrevalent_newdataset（C）過程（算法2）中，第22、25、27行調(diào)用Dis_Influence_object和Add_Influence_object過程是最耗時(shí)的。Dis_Influence_object和Add_Influence_object過程需要遍歷C中每個(gè)特征f的候選新增實(shí)例集AOC（C， f），影響實(shí)例集Ain_set（C， f）和Din_set（C， f），復(fù)雜度為O（k×n₁），n₁為AOC（C， f）、Ain_set（C， f）和Din_set（C， f）三個(gè)集合的最大長(zhǎng)度。對(duì)每個(gè)候選新增實(shí)例或影響實(shí)例，調(diào)用ResearchRI（o， C）（算法3第2步和算法4第3步）搜索包含實(shí)例o的模式C的行實(shí)例是最耗時(shí)的，最壞情況下，需要遍歷來自不同特征上的實(shí)例搜索空間O_ss（o，f，C）的實(shí)例的所有組合，復(fù)雜度為O（n^k－1₂），n₂為O_ss（o，f，C）的最大長(zhǎng)度。借助回溯算法的剪枝作用，實(shí)際搜索的組合數(shù)遠(yuǎn)小于O（n^k－1₂）。綜上，判斷候選模式C頻繁性的時(shí)間復(fù)雜度為O（k×n₁×n^k－1₂）。由式（7）（10）（11）可知n₂n₁，并且隨著階數(shù)增長(zhǎng)，n₁和n₂都將變小，主要得益于引理7的剪枝作用和模式向下閉合性質(zhì)。此外，因鄰近關(guān)系和頻繁性閾值限制，階數(shù)k不會(huì)無限制增長(zhǎng)。

2）空間復(fù)雜度

IMCP-CPI的空間耗費(fèi)主要來自三個(gè)方面：a）保存每個(gè)模式在O_old中的參與實(shí)例集Obj（C， f），空間耗費(fèi)為O（∑Kk=1|P^old_k|×m_k×k），K為O_old中頻繁模式的最大階數(shù)，|p_k|為O_old中k階頻繁模式的數(shù)量，m_k為k階模式的參與實(shí)例最大數(shù)量。這一存儲(chǔ)是增量挖掘算法不可避免的；b）保存每個(gè)o_dis、o_din在O_old-O_dis中的分組鄰居集groupN（o_dis，f）和groupN（o_din，f），每個(gè)o_add、o_ain在O_new中的分組鄰居集groupN（o_add，f）和groupN（o_ain，f），空間耗費(fèi)為O（（|o_dis|+|o_din|+|o_add|+|o_ain|）×|F|×m₂），m₂為分組鄰居集的最大長(zhǎng)度；c）增量挖掘k+1階模式時(shí)，需要額外保存k階頻繁模式的當(dāng)前參與實(shí)例集用于計(jì)算候選參與實(shí)例，空間消耗為O（|P^new_k|×k×m₃），其中|P^new_k|為O_new中k階頻繁并置模式的數(shù)量，m₃是當(dāng)前參與實(shí)例集的最大長(zhǎng)度，在k+1階候選模式搜索完成后，這部分空間占用將釋放。

3）完備性和正確性

kIMCP-CPI從二階開始逐階測(cè)試每個(gè)候選模式在新數(shù)據(jù)集中的頻繁性，生成候選模式的完備性由參與度的向下閉合性保證，因此IMCP-CPI一定能搜索到新數(shù)據(jù)集中所有的頻繁并置模式。在isPrevalent_newdataset（C）過程：a）生成候選變化實(shí)例的正確性由引理2保證，候選消失實(shí)例就是消失參與實(shí)例的道理顯而易見，判斷候選新增實(shí)例是否為新增參與實(shí)例的正確性由引理3保證；b）生成變化參與實(shí)例的影響實(shí)例的正確性由引理4保證，判斷影響實(shí)例是否為變化參與實(shí)例的正確性由引理5保證；c）啟發(fā)式模式剪枝策略的正確性由引理6、7保證。最后，新數(shù)據(jù)集中參與率的正確性由引理1保證。

5 實(shí)驗(yàn)評(píng)估

5.1 實(shí)驗(yàn)設(shè)置

a）真實(shí)數(shù)據(jù)集。real-set1是2012年和2014年北京城市元素空間分布數(shù)據(jù)集，包含20個(gè)特征28 635個(gè)實(shí)例。real-set2是2006年和2008年的石林自然保護(hù)區(qū)天然生態(tài)公益林，包括17個(gè)特征14 839個(gè)實(shí)例；每個(gè)空間實(shí)例在空間數(shù)據(jù)庫中的表示形式為〈實(shí)例id，特征，位置〉。

b）模擬數(shù)據(jù)集。表2顯示了本文使用的各模擬數(shù)據(jù)集的實(shí)例數(shù)、特征數(shù)，在每個(gè)實(shí)驗(yàn)的作用、閾值設(shè)定和對(duì)應(yīng)的圖表展示。模擬數(shù)據(jù)集中實(shí)例的坐標(biāo)范圍均為1000×1000。圖10檢驗(yàn)變化數(shù)據(jù)對(duì)算法性能的影響，調(diào)整了變化數(shù)據(jù)率。除此之外，每個(gè)數(shù)據(jù)集相對(duì)于其原始數(shù)據(jù)集的變化率均為5%。

c）對(duì)比算法。對(duì)比算法包括基于列計(jì)算的頻繁并置模式挖掘算法（CPM-Col）^［11］，基于改進(jìn)列計(jì)算的頻繁并置模式挖掘算法（CPM-iCol）^［12］和5個(gè)增量挖掘算法：自底向上的表實(shí)例法（BUCI）^［21］、自底向上的公式法（BUF）^［22］、自原分界線向兩邊擴(kuò)展的表實(shí)例法（DLCI）^［23］、自原分界線向兩邊擴(kuò)展的公式法（DLF）^［24］、擴(kuò)展文獻(xiàn)［20］的EUCOLOC算法以適應(yīng)數(shù)據(jù)消失和新增情況^［24］（本文仍稱其為EUCOLOC算法）。5個(gè)增量挖掘算法和CPM-Col及CPM-iCol算法挖掘的頻繁并置模式集相同，即挖掘準(zhǔn)確率均為100%。

d）實(shí)驗(yàn)環(huán)境。所有算法均在主頻為2.30 GHz的Intel i5-6300HQ處理器，16 GB內(nèi)存，Windows 10操作系統(tǒng)的筆記本電腦上運(yùn)行，算法程序使用Python語言實(shí)現(xiàn)。

5.2 閾值影響

8個(gè)算法都受距離閾值和頻繁度閾值影響，本節(jié)使用模擬數(shù)據(jù)集dataset1和兩個(gè)真實(shí)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，比較8個(gè)算法在兩個(gè)閾值改變時(shí)的時(shí)間性能。

a）距離閾值影響。距離閾值影響空間實(shí)例間的鄰近關(guān)系，距離閾值越大，鄰近關(guān)系越多，形成越多的團(tuán)關(guān)系。圖7（a）為8個(gè)算法在模擬數(shù)據(jù)集dataset1上隨距離閾值d變化的性能。從圖中可以看出：a）8個(gè)算法性能均隨d的增大有不同程度下降；b）相比其它5個(gè)算法，CPM-Col、CPM-iCol和本文IMCP-CPI性能隨d增大下降的最少。當(dāng)d=25時(shí)，IMCP-CPI的效率是DLF和DLCI的52倍，是BUCI和BUF的320倍，是EUCOLOC的366倍；c） CPM-Col、CPM-iCol和IMCP-CPI性能不相上下。

b）頻繁度閾值影響。頻繁度閾值影響候選模式的數(shù)量，頻繁度閾值越大，頻繁模式越少，生成的下一階候選模式就越少。圖7（b）為8個(gè)算法在模擬數(shù)據(jù)集data-set1上隨頻繁度閾值min_prev變化的性能。從圖中可以看出：a）8個(gè)算法性能均隨min_prev的增大有不同程度的提升；b）相比其它5個(gè)算法，CPM-Col、CPM-iCol和本文IMCP-CPI性能隨min_prev變化不明顯，即使在min_prev很小時(shí)兩個(gè)算法依然表現(xiàn)很好，當(dāng)min_prev=0.5時(shí)，IMCP-CPI的效率是DLF和DLCI的35倍，是BUCI和BUF的70倍，是EUCOLOC的78倍；c）在此數(shù)據(jù)集里CPM-Col、CPM-iCol和IMCP-CPI的性能相當(dāng)。

從以上結(jié)果可發(fā)現(xiàn)一個(gè)共性結(jié)論，即CPM-Col、CPM-iCol和IMCP-CPI性能遠(yuǎn)優(yōu)于其他5個(gè)算法，且性能相當(dāng)。因?yàn)檫@三個(gè)算法在挖掘頻繁并置模式時(shí)均不生成和檢驗(yàn)表實(shí)例，而通過行實(shí)例搜索直接生成參與實(shí)例，進(jìn)而計(jì)算參與率。接下來的實(shí)驗(yàn)對(duì)三個(gè)算法進(jìn)行細(xì)致比較。

圖8為CPM-Col、CPM-iCol和IMCP-CPI在兩個(gè)真實(shí)數(shù)據(jù)集中受閾值影響的性能變化情況。從圖中可以看出：a）三個(gè)算法的性能隨閾值變化具有相同的變化趨勢(shì)；b）IMCP-CPI在兩個(gè)真實(shí)數(shù)據(jù)集和兩個(gè)閾值下性能均優(yōu)于CPM-Col和CPM-iCol，CPM-iCol性能優(yōu)于CPM-Col。圖8（a）中d=800和圖8（b）中min_prev=0.1時(shí)，IMCP-CPI性能比CPM-Col提升兩倍多，比CPM-iCol提升近兩倍。圖8（c）中d=0.04時(shí)，IMCP-CPI性能比CPM-Col和CPM-iCol提升近兩倍。圖8（d）中min_prev=0.2時(shí)，IMCP-CPI性能比CPM-Col和CPM-iCol提升三倍左右。三個(gè)算法為生成參與實(shí)例而進(jìn)行的行實(shí)例搜索是最耗時(shí)步驟。IMCP-CPI不需要重新生成每個(gè)模式中各特征的所有參與實(shí)例，只生成新數(shù)據(jù)集中的變化參與實(shí)例，即可得到模式在新數(shù)據(jù)集中的參與實(shí)例集。

5.3 可擴(kuò)展性

使用模擬數(shù)據(jù)集dataset2_1、dataset2_4和dataset3_1、dataset3_4通過增加實(shí)例數(shù)量和特征數(shù)量來驗(yàn)證算法的可擴(kuò)展性。

a）實(shí)例數(shù)量影響。從圖9（a）可以看出，隨著實(shí)例數(shù)量增加，IMCP-CPI比CPM-Col和CPM-iCol性能下降得慢，具有更好的可擴(kuò)展性。

b）特征數(shù)量影響。圖9（b）中兩算法隨著特征數(shù)量F的增加，并沒有呈現(xiàn)遞增趨勢(shì)，且IMCP-CPI優(yōu)于CPM-Col和CPM-iCol，尤其當(dāng)算法處于性能下降高峰時(shí)。從F=10到F=15，隨著特征數(shù)增多，候選模式的長(zhǎng)度增加，為生成特征參與實(shí)例而進(jìn)行的行實(shí)例搜索耗時(shí)增加，兩算法的性能均下降。當(dāng)從F=15到F=25，隨著特征數(shù)繼續(xù)增多，而總實(shí)例數(shù)不變，平均分配到每個(gè)特征的實(shí)例數(shù)減少，能夠形成行實(shí)例的數(shù)量減少，模式的頻繁性受到影響，因此算法的執(zhí)行時(shí)間更快。

5.4 變化的實(shí)例影響

由前述實(shí)驗(yàn)和分析可知，IMCP-CPI因只生成變化參與實(shí)例來還原模式在O_new中的參與實(shí)例集（定義1），得到很好的時(shí)間性能。然而，隨著變化的實(shí)例數(shù)在原數(shù)據(jù)集中的占比（簡(jiǎn)稱變化實(shí)例占比）增加，IMCP-CPI的性能會(huì)受影響。本實(shí)驗(yàn)在模擬數(shù)據(jù)集dataset2_1上執(zhí)行，調(diào)整變化實(shí)例占比分別為20%，30%，40%，50%，具體情況如圖10所示。

從圖10可以看出，CPM-Col和CPM-iCol基本不受變化實(shí)例占比影響，因?yàn)檫@兩個(gè)算法對(duì)新數(shù)據(jù)集進(jìn)行重新挖掘，只要數(shù)據(jù)規(guī)模和參數(shù)固定，其在隨機(jī)生成的數(shù)據(jù)集中的性能不會(huì)有太大差別。但I(xiàn)MCP-CPI的性能隨變化實(shí)例占比的增加而下降，當(dāng)變化實(shí)例占比分別為25%和55%以上時(shí)，IMCP-CPI的性能低于CPM-iCol 和CPM-Col。

此實(shí)驗(yàn)可以為選擇IMCP-CPI增量挖掘和CPM-iCol重新挖掘提供參考。經(jīng)多個(gè)數(shù)據(jù)集實(shí)驗(yàn)發(fā)現(xiàn)，當(dāng)變化實(shí)例占比在25%以下時(shí)，IMCP-CPI性能均優(yōu)于CPM-iCol。

5.5 啟發(fā)式剪枝策略性能檢測(cè)

使用real-set1檢驗(yàn)啟發(fā)式剪枝策略的性能，共涉及關(guān)于模式參與率上限UP_NPR1、UP_NPR2和UP_NPR3的三次剪枝。圖11（a）顯示在剪枝策略層層加入后算法的性能變化，圖11（b）顯示每個(gè)剪枝策略的剪枝率。剪枝率被定義為該策略剪掉的模式數(shù)與候選模式總數(shù)的比值。

從圖11可看出：a）三個(gè)剪枝策略都對(duì)算法性能提升起到作用；b）和UP_NPR1、UP_NPR2相比，UP_NPR3在每個(gè)min_prev參數(shù)下剪掉的模式均最多，對(duì)算法的性能改進(jìn)最大。由引理6可知， UP_NPR3更接近NPR，故剪枝效果更好。

6 結(jié)束語

空間并置模式增量挖掘由于數(shù)據(jù)的時(shí)空特性而變得普遍且必要。本文基于變化參與實(shí)例實(shí)現(xiàn)空間并置模式高效增量挖掘。避免生成和驗(yàn)證變化數(shù)據(jù)導(dǎo)致的所有表實(shí)例，而是生成變化數(shù)據(jù)導(dǎo)致的變化參與實(shí)例。為加速對(duì)變化參與實(shí)例的搜索過程，提出了實(shí)例級(jí)搜索優(yōu)化策略和啟發(fā)式模式剪枝技術(shù)，設(shè)計(jì)了IMCP-CPI算法。實(shí)驗(yàn)結(jié)果表明，IMCP-CPI相比其它的空間并置模式增量挖掘算法具有更好的性能，其效率提升數(shù)倍甚至數(shù)個(gè)量級(jí)，并有更好的擴(kuò)展性。與CPM-iCol相比，當(dāng)變化數(shù)據(jù)占比小于等于原數(shù)據(jù)集的25%時(shí)，無論在參數(shù)變化還是可擴(kuò)展性方面，IMCP-CPI均有絕對(duì)優(yōu)勢(shì)。將IMCP-CPI擴(kuò)展以適用于高效用空間并置模式增量挖掘是下一步的研究方向。

參考文獻(xiàn)：

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

［2］Lu Junli， Wang Lizhen， Fang Yuan， et al. Mining strong symbiotic patterns hidden in spatial prevalent co-location patterns［J］. Know-ledge Based Systems， 2018， 146： 190-202.

［3］Lu Junli， Wang Lizhen， Fang Yuan， et al. Mining competitive pairs hidden in co-location patterns from dynamic spatial databases［C］// Proc of Pacific-Asia Conference on Knowledge Discovery and Data Mining. Cham： Springer， 2017： 467-480.

［4］Li Jiuyong， Le T D， Liu Lin， et al. Mining causal association rules［C］// Proc of the 13th International Conference on Data Mining Workshops. Piscataway， NJ： IEEE Press， 2013： 114-123.

［5］Fang Yuan， Wang Lizhen， Lu Junli， et al. A combined co-location pattern mining approach for post-analyzing co-location patterns［C］// Proc of International Conference on Artificial Intelligence： Technologies and Applications. ［S.l.］： Atlantis Press， 2016： 38-43.

［6］Yoo J S， Shekhar S. A joinless approach for mining spatial colocation patterns ［J］. IEEE Trans on Knowledge and Data Engineering， 2006， 18： 1323-1337.

［7］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.

［8］Wang Lizhen， Bao Yuzhen， Lu Zhongy. Efficient discovery of spatial co-location patterns using the iCPI-tree ［J］. Open Information Systems Journal， 2009， 3： 69-80.

［9］Yoo J S， Boulware D， Kimmey D. Parallel co-location mining with MapReduce and NoSQL systems［J］. Knowledge and Information Systems， 2020， 62： 1433-1463.

［10］Andrzejewski W， Boinski P. Efficient spatial co-location pattern mi-ning on multiple GPUs［J］. Expert Systems with Applications， 2018， 93： 465-483.

［11］楊培忠， 王麗珍， 王曉璇， 等. 一種基于列計(jì)算的空間并置模式挖掘方法［J］. 中國(guó)科學(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 China： Information Sciences， 2022， 52（6）： 1053-1068.）

［12］昌鑫， 蘆俊麗， 陳書健， 等. 基于改進(jìn)列計(jì)算的空間并置模式挖掘方法［J］. 計(jì)算機(jī)應(yīng)用研究， 2024， 41（5）： 1374-1380. （Chang Xin， Lu Junli， Chen Shujian， et al. Method for co-location pattern mining based on improved column calculation［J］. Application Research of Computers， 2024， 41（5）： 1374-1380.）

［13］Wang Dongsheng， Wang Lizhen， Wang Xiaoxu， et al. An approach based on maximal cliques and multi-density clustering for regional co-location pattern mining［J］. Expert Systems with Applications， 2024， 248： 123414.

［14］Ge Yong， Yao Zijun， Li Huayu. Computing co-location patterns in spatial data with extended objects： a scalable buffer-based approach［J］. IEEE Trans on Knowledge and Data Engineering， 2021， 33（2）： 401-414.

［15］Yang Peizhong， Wang Lizhen， Zhou Lihua， et al. A fast spatial high utility co-location pattern mining approach based on branch-and-depth-extension［J］. Information Sciences， 2024， 666： 120407.

［16］Li Jinhong， Wang Lizhen， Chen Hongmei， et al. Mining spatial high-average utility co-location patterns from spatial data sets［J］. Intelligent Data Analysis， 2022， 26（4）： 911-931.

［17］Xiong Kaifang， Chen Hongmei， Wang Lizhen， et al. Mining fuzzy sub-prevalent co-location pattern with dominant feature［C］// Proc of the 30th International Conference on Advances in Geographic Information Systems. New York： ACM Press， 2022： 1-10.

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

［19］鄒目權(quán)， 王麗珍， 吳萍萍， 等. 基于Voronoi圖的空間Co-location核模式挖掘［J］. 計(jì)算機(jī)學(xué)報(bào)， 2022， 45（9）： 1908-1925. （Zou Muquan， Wang Lizhen， Wu Pingping， et al. Mining co-location core patterns in spatial data sets based on the Voronoi diagram［J］. Chinese Journal of Computers， 2022， 45（9）： 1908-1925.）

［20］Yoo J S， Vasudevan H. Effectively updating co-location patterns in evolving spatial databases［C］// Proc of the 6th International Confe-rence on Pervasive Patterns and Applications. 2014： 96-99.

［21］蘆俊麗，王麗珍，肖清，等.空間co-location模式增量挖掘及演化分析［J］. 軟件學(xué)報(bào)，2014，25（S2）：189-200. （Lu Junli， Wang Lizhen， Xiao Qing， et al. Incremental mining and evolutional analysis of co-locations［J］. Journal of Software， 2013， 25（S2）： 189-200.）

［22］Lu Junli， Wang Lizhen， Xiao Qing， et al. Incremental mining of co-locations from spatial database［C］// Proc of the 12th International Conference on Fuzzy Systems and Knowledge Discovery. Piscataway， NJ： IEEE Press， 2015： 612-617.

［23］Lu Junli， Wang Lizhen， Fang Yuan， et al. A novel method on incremental mining of spatial co-locations ［C］// Proc of International Conference on Big Data and Smart Computing. Piscataway， NJ： IEEE Press， 2016： 69-76.

［24］蘆俊麗. 從動(dòng)態(tài)空間數(shù)據(jù)庫中挖掘有趣的空間模式［D］. 昆明： 云南大學(xué)， 2017： 21-38. （Lu Junli. Discover interesting spatial patterns from dynamic spatial databases［D］. Kunming： Yunnan University， 2017.）