帶頻繁區(qū)域的空間并置模式挖掘方法

關(guān)鍵詞：空間并置模式挖掘；頻繁區(qū)域；候選區(qū)域；拓展區(qū)域；區(qū)域粗參與度中圖分類號(hào)：TP391 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：1001-3695（2025）07-022-2086-10doi：10.19734/j. issn.1001-3695. 2024.10.0456

Abstract：Thisstudy focusedonspatialco-location patern mining，aiming toexplore theco-locationrelationships between spatialfeatures.Whiletraditionalmethodscanidentifyfrequentlyco-locationpatterns，theycannotdeterminethespecificspatialregions wherethese pattersoccur.Toaddress thisissue，thisstudyproposedanovel spatialco-locationpattrmining algorithmwithfrequentregions.Thealgorithmwasdividedintotwostages：thefirststageusedanagglomerativehierarchical clustering method topartition thespacebasedonthedatacharacteristics，andthenconfirmedthe proximityrelationships between instances within each cluster.Thesecond stage introduced theconcepts ofco-location patern presence regionsand regionalparticipationdegree，ndbasedonthese，itincrementallidentifiedthefrequentregionsofco-locationpaterns.To acceleratetheidentificationoffrequent regionsandthepattmmining process，thealgorithmquicklyconstructedcandidate regionsforhigher-orderpatternsbyexpanding theregionsofsub-paternsandusedrough participation degres tofilterout candidateregionsthatwereunlikelytobefrequent inadvance.Finally，extensive experiments onrealandsyntheticdatasets havedemonstratedthepeformanceoftheproposedalgorithmintermsof thenumberof spatialco-locationpaternswith frequentregions generated，theaccuracyoffrequentregions，andtheprecisionoffrequentregions.Onreal datasets，theaccuracyof thealgorithmrangesbetweenO.83andO.95.Furthermore，inexperiments evaluating thescalabilityofthealgorithm， whenthenumberoffeaturesinthedataset ismoderate，theperformanceof thePROC-Colalgorithmisapproximatelytwiceas fast as the current state-of-the-art multi-level algorithm.

Key words：spatialco-location patern mining；frequentregions；candidateregions；expandedregions；rough regional participation index

0 引言

空間并置模式挖掘1自2001年提出以來(lái)，取得了顯著進(jìn)展?？臻g并置模式指經(jīng)常一起出現(xiàn)的空間特征（事物）子集，在生態(tài)學(xué)、城市規(guī)劃等領(lǐng)域廣泛存在，如尼羅河鱷魚與埃及鸻的共生關(guān)系或百貨商店與禮品店的商業(yè)布局。隨著全球定位和遙感技術(shù)的飛速發(fā)展，空間數(shù)據(jù)呈爆炸式增長(zhǎng)，挖掘這些數(shù)據(jù)以發(fā)現(xiàn)潛在知識(shí)成為研究熱點(diǎn)[2]。作為空間數(shù)據(jù)挖掘的重要分支，空間并置模式挖掘聚焦于揭示空間事物的關(guān)聯(lián)關(guān)系，在生態(tài)保護(hù)、公共衛(wèi)生、地球科學(xué)[2]、交通運(yùn)輸[3]和城市建設(shè)等領(lǐng)域應(yīng)用廣泛。例如，它能揭示物種共生、探索疾病與污染的關(guān)聯(lián)，并為選址和規(guī)劃提供相應(yīng)的決策支持[4]?；诟倪M(jìn)列計(jì)算的空間并置模式挖掘方法通過(guò)減少回溯計(jì)算并加速參與實(shí)例的搜索，顯著提高了挖掘效率，成為當(dāng)前高效的模式挖掘方法之一[5]。空間的異質(zhì)性使得并置模式通常只在特定區(qū)域顯著，不同區(qū)域的特征關(guān)聯(lián)因環(huán)境多樣性而變化[6]。區(qū)域性模式挖掘能夠深入揭示地理數(shù)據(jù)中空間特征的依賴性，在多個(gè)應(yīng)用領(lǐng)域發(fā)揮重要作用，推動(dòng)空間數(shù)據(jù)利用進(jìn)人深人發(fā)展階段。區(qū)域空間并置模式挖掘大致分為基于分區(qū)的方法和區(qū)域檢測(cè)策略兩類方法?；诜謪^(qū)的方法首先根據(jù)特定的空間分區(qū)方案將研究區(qū)域劃分為一系列子區(qū)域，然后使用全局并置模式發(fā)現(xiàn)方法來(lái)提取每個(gè)子區(qū)域中的所有頻繁并置模式。而區(qū)域檢測(cè)策略則旨在通過(guò)數(shù)據(jù)驅(qū)動(dòng)的方式識(shí)別并置區(qū)域，通?；诓煌卣鞯牟⒅脤?shí)例來(lái)確定這些區(qū)域?；诜謪^(qū)的方法包括了各種分區(qū)技術(shù)的應(yīng)用，如Celik等人[7于2007年提出的四叉樹劃分、Ding等人[8]于2011年提出的多分辨率網(wǎng)格和Qian等人[9于2014年提出基于K最近鄰圖的層次空間分區(qū)方法。Jiang等人[10]于2022年提出了一種基于密度峰值聚類和模糊理論的區(qū)域空間并置模式挖掘方法。然而，這些方法的一個(gè)主要缺點(diǎn)是，用戶指定的分區(qū)方案通常與區(qū)域并置模式的自然分布無(wú)關(guān)，可能導(dǎo)致真實(shí)并置區(qū)域的挖掘受損。例如，四叉樹分區(qū)方案可能錯(cuò)誤地將區(qū)域并置模式的子區(qū)域分隔開。區(qū)域檢測(cè)策略通過(guò)數(shù)據(jù)驅(qū)動(dòng)的方式識(shí)別并置區(qū)域，以克服基于分區(qū)方法的限制。這些方法通常基于不同特征的并置實(shí)例來(lái)確定并置區(qū)域，如Eick等人[11]于2008年提出的原型基聚類方法、Mohan等人[于2011年提出的鄰域圖和Deng等人[12]于2017年提出的自適應(yīng)模式聚類方法。Wang等人[13]于2024年提出了一種基于核心特征影響的區(qū)域核心模式挖掘方法。Wang等人[14]于2024年提出了一種基于最大團(tuán)和多密度聚類的區(qū)域并置模式挖掘方法。

當(dāng)前的這些有關(guān)帶頻繁區(qū)域的空間并置模式挖掘方法的一個(gè)局限性是它僅能識(shí)別出區(qū)域并置模式的頻繁區(qū)域，而忽略了全局并置模式的頻繁區(qū)域。換句話說(shuō)，當(dāng)前方法對(duì)并置模式的頻繁區(qū)域挖掘得不夠全面。以一個(gè)全局頻繁出現(xiàn)的模式{酒店，餐館，商場(chǎng)為例，在傳統(tǒng)的挖掘方法中，只知道這種模式瀕繁存在，但具體出現(xiàn)在哪些區(qū)域卻不得而知。若能對(duì)空間數(shù)據(jù)集中所有模式的頻繁區(qū)域進(jìn)行精準(zhǔn)挖掘，就能夠確切地定位每個(gè)模式在空間中的分布位置，這會(huì)帶來(lái)多方面的優(yōu)勢(shì)：a）提高模式分布的地理定位精確度和數(shù)據(jù)分析的相關(guān)性。通過(guò)識(shí)別空間中每個(gè)模式的具體區(qū)域，可以更精確地理解這些模式在不同區(qū)域的分布和影響，從而提高數(shù)據(jù)分析的相關(guān)性和實(shí)用性。b）增強(qiáng)決策支持。在城市規(guī)劃、環(huán)境管理、交通規(guī)劃等領(lǐng)域，了解模式的區(qū)域分布可以幫助制定更加有針對(duì)性的策略和決策?？稍谀Ｊ降念l繁區(qū)域分配更多資源和服務(wù)，例如增加公共交通服務(wù)或醫(yī)療設(shè)施等。c）促進(jìn)科學(xué)研究。在生態(tài)學(xué)、地理學(xué)等領(lǐng)域，挖掘模式的頻繁區(qū)域有助于深入理解空間現(xiàn)象，如物種分布、環(huán)境變化等。還可以促進(jìn)不同學(xué)科間的交叉研究，例如結(jié)合生態(tài)學(xué)和地理信息系統(tǒng)（GIS）進(jìn)行物種保護(hù)區(qū)域的規(guī)劃。d）提升風(fēng)險(xiǎn)管理能力。在自然災(zāi)害管理中，了解特定區(qū)域的風(fēng)險(xiǎn)模式有助于更好地預(yù)防和應(yīng)對(duì)潛在的災(zāi)害風(fēng)險(xiǎn)。此外，通過(guò)識(shí)別犯罪或事故頻發(fā)區(qū)域，可以加強(qiáng)這些區(qū)域的安全措施和應(yīng)急響應(yīng)。此外，上述文獻(xiàn)在挖掘區(qū)域并置模式的頻繁區(qū)域方面也存在一定的局限性。在基于分區(qū)的方法中，Jiang等人[10提出基于密度峰值聚類和模糊理論的區(qū)域空間并置模式挖掘方法。該方法首先通過(guò)密度峰值聚類對(duì)數(shù)據(jù)集進(jìn)行分組，然后在這些聚類結(jié)果中挖掘頻繁模式，這些挖掘出的頻繁模式即為區(qū)域并置模式，其所在的聚類即為該模式的頻繁區(qū)域。這種方法有效應(yīng)對(duì)了空間數(shù)據(jù)的非均勻分布，避免了傳統(tǒng)基于用戶定義分區(qū)方案的偏差問(wèn)題。然而，該方法的不足在于挖掘出的頻繁區(qū)域針對(duì)性不夠強(qiáng)，多個(gè)并置模式共用一個(gè)頻繁區(qū)域，并且這些頻繁區(qū)域與真實(shí)的并置模式分布并不完全吻合。

在區(qū)域檢測(cè)策略中，較先進(jìn)的方法，如Wang等人[14]提出的基于最大團(tuán)和多密度聚類的區(qū)域并置模式挖掘方法，大多采用了與Deng等人[1提出的自適應(yīng)模式聚類方法相同的挖掘框架。該框架首先挖掘全局頻繁的并置模式，然后將全局不頻繁的并置模式作為候選區(qū)域并置模式進(jìn)行挖掘，并判斷其是否具有頻繁區(qū)域。這種挖掘框架的主要問(wèn)題在于，為了得到一個(gè)并置模式的頻繁區(qū)域，必須首先挖掘出全部的全局瀕繁并置模式，這會(huì)耗費(fèi)大量時(shí)間在全局頻繁模式的挖掘上，延遲了并置模式的頻繁區(qū)域進(jìn)一步挖掘。

針對(duì)上述問(wèn)題，本文提出了一種帶頻繁區(qū)域的空間并置模式挖掘方法，旨在更全面地識(shí)別并置模式的頻繁區(qū)域。相較現(xiàn)有方法，本文算法的創(chuàng)新點(diǎn)和貢獻(xiàn)如下：a）專屬頻繁區(qū)域挖掘。本算法采用數(shù)據(jù)點(diǎn)驅(qū)動(dòng)的方式，通過(guò)并置模式自身的參與實(shí)例逐步確定其專屬頻繁區(qū)域，避免多個(gè)模式共用同一頻繁區(qū)域的局限性，提升了挖掘結(jié)果對(duì)真實(shí)分布的貼合度。b）聯(lián)合挖掘框架。提出一種新型挖掘框架，使頻繁模式的挖掘與其頻繁區(qū)域的挖掘同步進(jìn)行，從而減少時(shí)間開銷，提升整體效率。c）分階段設(shè)計(jì)。算法分為兩個(gè)階段：第一階段，通過(guò)凝聚層次聚類實(shí)現(xiàn)數(shù)據(jù)自適應(yīng)分區(qū)，捕獲自然分布結(jié)構(gòu)，無(wú)須預(yù)先指定分區(qū)方案，增強(qiáng)模式挖掘的準(zhǔn)確性與合理性；第二階段，在每個(gè)聚類簇內(nèi)，基于參與實(shí)例逐階挖掘頻繁并置模式，并利用凸包方法確定模式的專屬頻繁區(qū)域。d）高效擴(kuò)展策略。引入基于低階模式頻繁區(qū)域先驗(yàn)知識(shí)的高效方法，通過(guò)擴(kuò)展子模式區(qū)域快速生成高階模式候選區(qū)域，顯著優(yōu)化計(jì)算效率。e）區(qū)域粗參與度優(yōu)化。為進(jìn)一步加速計(jì)算，提出區(qū)域粗參與度概念，用于提前排除不可能成為頻繁區(qū)域的候選區(qū)域。

綜上，本文算法不僅能挖掘出更貼合實(shí)際分布的專屬頻繁區(qū)域，還顯著提高了挖掘效率，為空間數(shù)據(jù)分析提供了更加精準(zhǔn)和高效的工具。

1基本理論

1.1空間并置模式挖掘

a）特征[1]。在空間數(shù)據(jù)庫(kù)中，不同類型的事物可用不同的特征表示， F={f₁，f₂，…，f_n} 表示特征集合，每個(gè)特征有多個(gè)實(shí)例。

b）實(shí)例[1]。用集合 O={o₁，o₂，…，o_m} 表示各特征在不同位置的實(shí)例集合，每個(gè)實(shí)例由一個(gè)三元組lt;編號(hào)，特征，位置gt;構(gòu)成。

c）鄰近關(guān)系[1]。如果兩個(gè)實(shí)例 o 和 o^′ 之間的距離小于等于給定的距離閾值 d ，則稱實(shí)例 ∣o∣ 與 o^′ 具有鄰近關(guān)系，表示為R（°，o^'）?distance（o，o^'）?d ，其中 distance（o，o^'） 表示實(shí)例 o 與 ?^′ 的距離。

d）鄰居集[15]。對(duì)于實(shí)例 o ，所有與 o 具有鄰近關(guān)系的實(shí)例構(gòu)成的集合稱為 o 的鄰居集，記為 Neigh（o）={o}_o^′∈O ，其中 ξ_o，t 代表實(shí)例 o 的特征類型。

e）分組鄰居集[15]。對(duì)實(shí)例 o 的鄰居集按鄰居實(shí)例特征類型進(jìn)行分組，可得實(shí)例 o 在每個(gè)特征上的分組鄰居集。groupN（o，f）={o^′∣o^′∈Neigh（o），o^′.t=f} 為 o 在特征上 f 的分組鄰居集。

例1圖1中實(shí)例 A.1 與 _B，2 之間的距離小于距離閾值d ，所有實(shí)例A.1與 _B.2 具有鄰近關(guān)系。對(duì)于實(shí)例A1，所有與A.1具有鄰近關(guān)系的實(shí)例集合，即實(shí)例A.1的鄰居集為Neigh（A. 1）={B.2，B. 3，C. 1} 。實(shí)例A.1在特征 B 上的分組鄰居集為 groupN（A.1，B）={B.1，B.2} 。

f）空間并置模式[1]?？臻g并置模式是空間特征集合的一個(gè)子集， C={f₁，f₂，…，f_k} k?2，C?F 。

g）階數(shù)[1]?？臻g并置模式 c 的階數(shù)為集合 c 中空間特征的個(gè)數(shù)。

h）子模式，超模式[1]。如果存在兩個(gè)模式 c 和 C^′ ，其中c^′cc ，則認(rèn)為模式 C^′ 是 c 的子模式，模式 c 是 C^′ 的超模式。

i）行實(shí)例，表實(shí)例[1]。如果一個(gè)實(shí)例集合 ，∣o₂，…，o_k} 滿足：集合中任意兩個(gè)實(shí)例間都具有鄰居關(guān)系，并且 RI（C） 包含了 k 階并置模式 c 中的所有特征，則稱實(shí)例集合RI（C） 為模式 c 的一個(gè)行實(shí)例。表實(shí)例 TI（C） 為空間并置模式 c 的所有行實(shí)例的集合。為了量化空間并置模式的頻繁程度，文獻(xiàn)[1]對(duì)參與率、參與度作出了定義。

j）參與率[1]。對(duì)于模式 c 中的任意特征 f， 其在模式 c 中的參與率用PR（ C，f） 表示，計(jì)算公式為

其中： IN（f） I代表空間數(shù)據(jù)集中特征 f 的所有實(shí)例數(shù)；I為帶去重的投影操作； ）I代表參與模式 c 表實(shí)例的特征f 的實(shí)例數(shù)。

根據(jù)Yang等人[15]于2022年提出的基于列計(jì)算的空間并置模式挖掘方法，模式 c 中特征 f 的參與率也可以通過(guò)該特征的參與實(shí)例集計(jì)算。

k）參與實(shí)例集[15]。模式 c 中特征 f 的參與實(shí)例集 Obj（ δ_C，f） 定義為 Obj（C，f）={o∣o.t=fΛoinRI（C）} 。由于 obj（C） ，則模式 c 中特征 f 的參與率為 PR（C，f）=

1）參與度[1]。模式 c 的參與度為 c 中各特征的參與率最 小值，記為 PI（C） （204

m ）頻繁并置模式[1]。給定頻繁度閾值 ，如果模式 c 的參與度 PI（C） 的值大于等于頻繁閾值，則稱模式 c 為頻繁并置模式，空間并置模式的挖掘目標(biāo)為找尋出空間數(shù)據(jù)集中所有的頻繁并置模式。

例2圖1中空間并置模式 {A，B，C} 就是一個(gè)3階的空間并置模式。對(duì)于空間并置模式 {A，B，C} 和空間并置模式 {A |B} ，由于 {A，B}?{A，B，C} ，則有模式 {A，B} 是模式 {A，B，C} 的子模式，模式 {A，B，C} 是模式 {A，B} 的超模式。對(duì)于實(shí)例集合RI （{A，B，C}）={A. 1，B. 3，C. 1} 滿足條件集合中任意兩個(gè)實(shí)例間都具有鄰居關(guān)系，并且RI（ {A，B，C} ）包含了3階并置模式 {A，B，C} 中的所有特征，則稱實(shí)例集合RI（ {A，B，C} ）為模式 {A，B，C} 的一個(gè)行實(shí)例。在整個(gè)空間數(shù)據(jù)集中模式 {A B，C} 的表實(shí)例 TI（{A，B，C}）={{A.1，B.3，C.1} ， {A.2，B. 1 C.3}， {A. 3，B. 4，C. 2}{A. 4，B. 4，C. 4}，{A. 5，B. 7，C. 7}，{A. 5，B. 7}. B，8，C，7} }。模式 {A，B，C} 中特征 A 的參與實(shí)例集為Obj1 {A，B，C}，A）={A. 1，A. 2，A. 3，A. 4，A. 5} ，則在模式 {A，B，C} 中特征 A 的參與率為 454。模式 {A，B，C} 的參與率為 PI（{A，B，C}）=min {PR（{A，B，C}，A），PR（{A，B，C}，B），PR（{A，B，C}，C）∣= 。此時(shí)，假設(shè)給定的頻繁閾值min_prev為0.300，則模式 {A，B，C} 為一個(gè)頻繁并置模式。

1.2區(qū)域空間并置模式及其頻繁區(qū)域

在空間并置模式挖掘研究中，某些模式在全局范圍內(nèi)不頻繁，但在特定區(qū)域內(nèi)可能變得頻繁[16]?；诖耍芯空咛岢隽藚^(qū)域并置模式[1的定義：在空間數(shù)據(jù)集 s 中，假設(shè)存在一系列空間特征 F={f₁，f₂，…，f_n} 及其相應(yīng)實(shí)例 O={o₁，o₂，…，o_m} ，以及這些實(shí)例間的相互鄰居關(guān)系。區(qū)域并置模式 RC 是空間特征 F 的一個(gè)子集，其實(shí)例頻繁共存于一個(gè)由多個(gè)子區(qū)域 L= {l₁，l₂，…，l_i，…，l_k} （其中， l_i 是 o 的一部分）組成的集合中。

在中等規(guī)模城市的空間數(shù)據(jù)中，可能發(fā)現(xiàn)區(qū)域并置模式{學(xué)校，托兒所}。盡管這一模式在全局上不頻繁，但在某些居民區(qū)，小學(xué)與托兒所常在步行距離內(nèi)共現(xiàn)，以方便家長(zhǎng)接送孩子并滿足日托需求。此外，在新開發(fā)區(qū)，中學(xué)附近可能新增托兒所，以服務(wù)年輕家庭。城市規(guī)劃者可據(jù)此優(yōu)化教育資源布局，托兒所運(yùn)營(yíng)者亦可選擇更符合社區(qū)需求的地點(diǎn)。

2帶頻繁區(qū)域的空間并置模式挖掘算法

2.1第一階段—凝聚層次聚類劃分初始區(qū)域

利用GIS技術(shù)將空間數(shù)據(jù)庫(kù)中的數(shù)據(jù)投射到二維地圖，并標(biāo)注每個(gè)實(shí)例的具體坐標(biāo)。通過(guò)凝聚層次聚類算法對(duì)所有實(shí)例進(jìn)行聚類，可依據(jù)實(shí)例分布初步劃分空間，獲取粗略的空間分布信息。本文采用Li等人[18]提出的改進(jìn)集成聚類方法MCEMS，其核心是使用雙加權(quán)策略，綜合考慮多樣性和聚類質(zhì)量來(lái)選擇凝聚層次聚類方法的子集。MCEMS通過(guò)簇聚類與元聚類構(gòu)建一致性函數(shù)，并采用新的相似度度量結(jié)合多種聚類算法評(píng)估實(shí)例間的相似性。最終集群通過(guò)分配最高相似性的元集群生成，并通過(guò)合并相似集群和設(shè)定閾值自動(dòng)確定最佳集群數(shù)量。對(duì)凝聚層次聚類后的簇集 CL={cl₁，cl₂，…，cl_m} ，依據(jù)用戶設(shè)定的距離閾值 d 計(jì)算簇內(nèi)不同特征實(shí)例的鄰居關(guān)系。由于各簇互不相連，鄰居關(guān)系計(jì)算可并行處理。

例3圖1為對(duì)示例空間數(shù)據(jù)集進(jìn)行凝聚層次聚類及物化鄰居關(guān)系后的結(jié)果，共有3個(gè)簇，每個(gè)簇內(nèi)具有鄰居關(guān)系的實(shí)例用實(shí)線相連。

2.2第二階段一一空間并置模式及其頻繁區(qū)域挖掘

為了能夠確定并置模式在空間中所存在的位置，下面定義并置模式 c 的存在區(qū)域，再根據(jù)模式的區(qū)域參與度判斷該存在區(qū)域是否頻繁。

定義1并置模式的存在區(qū)域。給定并置模式 c ，其存在區(qū)域?yàn)樵摬⒅媚Ｊ皆诖刂械乃袇⑴c實(shí)例所構(gòu)成的凸包，記為并置模式的存在區(qū)域 ROC（C）_i 。其中，i表示該存在區(qū)域是并置模式； c 的第 i 塊存在區(qū)域。

例4圖2（a）中，簇 cl₁ 中紫色實(shí)線部分為并置模式 {A，B} 的參與實(shí)例構(gòu)成的凸包，記為存在區(qū) ROC（AB）₁ （見電子版）。

定義2并置模式的區(qū)域參與率。并置模式 c 的某一特征 f（f∈C） 在存在區(qū)域ROC （C）_i 中的區(qū)域參與率為特征 f 在該存在區(qū)域中參與到模式 c 的參與實(shí)例數(shù)與 f 在對(duì)應(yīng)簇 Δ_cli 中所有實(shí)例數(shù)的比值。區(qū)域參與率表示為PR（ROC （C）_i，C，f） 。

其中：0 ?j（ROC（C）_i，C，f） 為特征 f 在存在區(qū)域ROC （C）_i 中參與到模式 c 的參與實(shí)例； N（cl_i，f） 為特征 f 在簇 cl_i 中的所有實(shí)例。

例5在圖2（a）簇 cl₁ 中，特征 B 在簇 cl₁ 中的實(shí)例個(gè)數(shù)為5，在存在區(qū)域 ROC（AB）₁ 中參與到模式 {A，B} 的參與實(shí)例數(shù)為4，則根據(jù)式（3），特征 B 在 ROC（AB）₁ 中的區(qū)域參與率為PR（ROC（AB）₁ ， {A，B}，B）=4/5=0.800 同理，特征 A 在ROC（AB）₁ 中的參與率為 PR（ROC（AB）₁，{A，B}，A）=4/4=1.000

定義3并置模式的區(qū)域參與度。并置模式 c 在存在區(qū)域 ROC（C）_i 中的區(qū)域參與度為 c 中特征在該存在區(qū)域的參與率的最小值，即

PI（ROC（C）_i，C）=min_j=1^k{PR（ROC（C）_i，C，f_j）}

定義4并置模式的頻繁區(qū)域。對(duì)于并置模式 c 的某個(gè)存在區(qū)域 ROC（C）_i ，如果PI（ROC （C）_i，C） 大于等于給定的頻繁閾值min_prev，則該存在區(qū)域?yàn)?c 的頻繁區(qū)域，記為PROC （C）_i 。

例6在圖2（a）簇 中，模式 {A，B} 在候選存在區(qū)域ROC（AB）₁ 的區(qū)域參與度的計(jì)算為 PI（ROC（AB）₁ {A，B}=min {PR（ROC（AB）₁，{A，B}，A），PR（ROC（AB）₁，{A，B}，B）}= min{1.000，0.800}=0.800 ，若給定頻繁閾值 400，則存在區(qū)域 ROC（AB）₁ 為并置模式 {A，B} 的頻繁區(qū)域 PROC（AB）₁ 。

特別地，對(duì)于一階并置模式，將其在簇中所有實(shí)例組成的凸包記為頻繁區(qū)域。例如，圖2（b）中，紫色實(shí)線圍成的區(qū)域?yàn)橐浑A模式 {A} 在簇 cl₁ 的頻繁區(qū)域 PROC（A）₁ ，該頻繁區(qū)域是由特征 A 在簇 cl₁ 中所有實(shí)例點(diǎn)所組成的凸包。

2.3空間并置模式的存在區(qū)域替代策略

在探討并置模式 c 的頻繁區(qū)域 PROC（C）_i 時(shí)，如果都需要先生成該模式在簇 cl_i 內(nèi)的所有行實(shí)例，再依靠這些行實(shí)例對(duì)應(yīng)的參與實(shí)例的凸包來(lái)確認(rèn)模式在該簇中的存在區(qū)域ROC（C）_i ，根據(jù)區(qū)域參與度判斷頻繁區(qū)域，大量時(shí)間將耗費(fèi)在簇內(nèi)行實(shí)例搜索以及參與實(shí)例的凸包構(gòu)建上。為提高算法效率，避免在整個(gè)簇中廣泛搜索并置模式參與實(shí)例，本文引人“并置模式的候選區(qū)域”，并在區(qū)域頻繁性判斷中以候選區(qū)域替代存在區(qū)域。

定義5并置模式的拓展區(qū)域。對(duì)于并置模式 c ，在簇 Δ_cli 中的拓展區(qū)域?yàn)樵摬⒅媚Ｊ?c 的頻繁區(qū)域 PROC（C）_i 向外拓展 d 個(gè)單位后的區(qū)域，記為ExtPROC（ C）_i 。

例7圖2（a）為并置模式 {A，B} 在簇 cl₁ 中的頻繁區(qū)域PROC（AB）₁ 向外拓展 d 大小后得到的拓展區(qū)域ExtPROC（AB）₁ ，即黃色實(shí)線部分（見電子版）。

拓展區(qū)域?qū)︻l繁區(qū)域PROC （C）_i 的邊界進(jìn)行了擴(kuò)充，類似于在邊界實(shí)例 ∣o∣ 的基礎(chǔ)上建立了一個(gè)以 σ_o 為圓心、以設(shè)定的距離閾值 d 為半徑的鄰居關(guān)系搜索圓。這樣確保ExtPROC（C）_i 不會(huì)遺漏頻繁區(qū)域PROC （C）_i 內(nèi)任何實(shí)例的鄰居關(guān)系。

定義6并置模式的候選區(qū)域。對(duì)于 k 階并置模式 c ，在簇 cl_i 中其候選區(qū)域?yàn)?c 的所有 k-1 階子模式 C^′ 的拓展區(qū)域ExtPROC（C^′）_i 的交集。對(duì)于模式 C 的第 i 塊候選區(qū)域，記為 CROC（C）_i 。

例8在圖3（a）的 cl₁ 簇中，模式 {A，B}，{A，C} 和 {B，C} 的拓展區(qū)域ExtPROC （AB）₁ 、ExtPROC （AC）₁ 和 ExtPROC（BC）₁ 相交，得到超模式 {A，B，C} 的候選區(qū)域如圖3（b）的綠色多邊形，即CROC （ABC）₁= ExtPROC （AB）₁ ∩ ExtPROC（AC）₁∩ExtPROC（BC）₁， 0

引理1 k 階并置模式 c 的候選區(qū)域 CROC（C）_i 包含了 c 在簇 cl_i 中的所有參與實(shí)例。

證明假設(shè)實(shí)例集 RI（C） 是 k 階并置模式 c 的一條行實(shí)例，但 RI（C） 中至少有一個(gè)實(shí)例 o 不在并置模式 c 的候選區(qū)域CROC（C）_i 內(nèi)。根據(jù)候選區(qū)域的定義可知， o 沒(méi)有包含在某個(gè)k-1 階子模式 C^′（C^'?C） 的拓展區(qū)域 ExtPROC（C^′）_i 內(nèi)。情況1：實(shí)例 o 的特征 f（o，t=f） 參與了子模式 C^′ ，即 f∈C^′ 。在該情況下，實(shí)例 σ_o 未位于 k-1 階子模式 C^′ 的拓展區(qū)域ExtPROC（C^′）_i 內(nèi)，由拓展區(qū)域的生成方法可得實(shí)例 o 不是子模式 C^′ 的參與實(shí)例。根據(jù)超模式的行實(shí)例生成規(guī)則，實(shí)例 σ_o 必須是特征f 參與的所有子模式的參與實(shí)例，才有可能與其他實(shí)例組成超模式 c 的行實(shí)例。比如在超模式 {A，B，C} 中，特征 A 的實(shí)例只有同時(shí)為子模式 {A，B} 與 {A，C} 的參與實(shí)例才有可能與子模式 {B，C} 中的其他實(shí)例組合成為超模式 {A，B，C} 的行實(shí)例。綜上，實(shí)例 σ_o 不能組成超模式 c 的行實(shí)例，即實(shí)例集 RI（C） 不是并置模式 c 的行實(shí)例，與題設(shè)矛盾，得證。情況2：實(shí)例 σ_o 的特征 f（o，t=f） 未參與子模式 C^′ ，即 。在該情況下，實(shí)例 σ_o 未位于 k-1 階子模式 C^′ 的拓展區(qū)域ExtPROC （C^′）_i 內(nèi)。根據(jù)拓展區(qū)域的生成方法，可以得知拓展區(qū)域 ExtPROC（C^′）_i 內(nèi)并置模式 C^′ 的任何參與實(shí)例與拓展區(qū)域外的任何實(shí)例之間的距離都大于設(shè)定的距離閾值 d 所以實(shí)例 σ_o 無(wú)法與子模式 C^′ 的任意參與實(shí)例組成超模式 c 的行實(shí)例，這與實(shí)例集 RI（C） 是并置模式 c 的行實(shí)例的假設(shè)相矛盾，因此得證。

在簇 cl_i 中使用候選區(qū)域替代存在區(qū)域不會(huì)丟失并置模式的任何一個(gè)參與實(shí)例，因?yàn)橐?已證明 k 階并置模式 c 候選區(qū)域 CROC（C）_i 包含了 c 在簇 cl_i 中的所有參與實(shí)例。

引理2對(duì)于并置模式 c 有，其存在區(qū)域ROC （C）_i 被其候選區(qū)域CROC （C）_i 所包含，即 Roc（C）_i?CROC（C） ，且P ?CROC（C）_i，C?=PI（ROC（C）_i，C） 。

證明根據(jù)引理1及存在區(qū)域 ROC（C）_i 的定義，并置模式 c 的候選區(qū)域CROC （C）_i 包含了該模式的所有參與實(shí)例，而存在區(qū)域 ROC（C）_i 是并置模式 c 的所有參與實(shí)例的凸包，易得 Roc（C）_i?CROC（C）_i. 。根據(jù)區(qū)域參與度的定義，并置模式的區(qū)域參與度只與各特征的參與實(shí)例數(shù)、各特征在簇中所有實(shí)例數(shù)有關(guān)。由于模式 c 在候選區(qū)域CROC （C）_i 及存在區(qū)域ROC（C）_i 內(nèi)的參與實(shí)例數(shù)相同，所以有 PI（CROC（C）_i，C）= PI（ROC （C）_i，C） 。

引理3并置模式 c 的候選區(qū)域CROC （C）_i 是個(gè)凸多邊形。

證明根據(jù)候選區(qū)域的定義可知，候選區(qū)域CROC （C）_i 是由在簇 cl_i 中并置模式 c 的所有 k-1 階子模式 C^′ 拓展區(qū)域（20號(hào) ExtPROC（C^′）_i 的交集所組成，而拓展區(qū)域ExtPROC （C^′）_i 是由并置模式 C^′ 的頻繁區(qū)域PROC （C^′）_i 向外擴(kuò)展 d 個(gè)單位后得到的，且并置模式 C^′ 的頻繁區(qū)域PROC （C^′）_i 是凸的，所以并置模式 c 的所有 k-1 階子模式 C^′ 拓展區(qū)域 ExtPROC（C^′）_i 也是凸的。因此，引理3可以轉(zhuǎn)換為下述問(wèn)題。 n 個(gè)凸多邊形的交集仍是凸多邊形。假設(shè)有多個(gè)凸多邊形 T₁，T₂，…，T_n ，它們的交集為 T=T₁∩T₂∩…∩T_n 。顯然， T 包含在每個(gè)凸多邊形 T₁，T₂，…，T_n 中。要證明 T 是凸的，需要證明對(duì)于 T 中的任意兩點(diǎn) x 和 y ，線段xy上所有的點(diǎn)都在 T 內(nèi)。由于 x 和 y 是 T 中的任意兩點(diǎn)，那么 x 和 y 也分別屬于每個(gè)凸多邊形 T₁ ，T₂，…，T_n 。因?yàn)槊總€(gè) T_i 都是凸多邊形，所以線段xy上所有的點(diǎn)分別屬于 T₁，T₂，…，T_n 。因此，這些點(diǎn)必然也屬于 T ，即線段xy上所有的點(diǎn)都在 T 內(nèi)。綜上所述， T 被包含在每個(gè)凸多邊形T₁，T₂，…，T_n 中，又具有凸性質(zhì)，因此 T 是一個(gè)凸多邊形。回到原問(wèn)題，可得由并置模式 c 的所有 k-1 階子模式 C^′ 拓展區(qū)域 ExtPROC（C^′）_i 的交集所組成的候選區(qū)域CROC （C）_i 是個(gè)凸多邊形，問(wèn)題得證。

根據(jù)存在區(qū)域 PROC（C）_i 的定義，得知并置模式 c 的存在區(qū)域具備兩個(gè)關(guān)鍵性質(zhì)：首先，它能夠包含該并置模式的所有參與實(shí)例；其次，該存在區(qū)域是凸的?；趯?duì)候選區(qū)域的定義及引理1＼～3的研究，發(fā)現(xiàn)候選存在區(qū)域 CROC（C）_i 也符合上述兩個(gè)性質(zhì)。因此，在生成高階并置模式 c 的頻繁區(qū)域PROC （C）_i 時(shí)，可使用低階并置模式 C^′ 的拓展區(qū)域ExtPROC（C^′）_i 相交得到高階并置模式候選區(qū)域CROC （C）_i ，來(lái)替代求解高階并置模式的參與實(shí)例的凸包構(gòu)成存在區(qū)域 ROC（C）_i， 0基于模式 c 的候選區(qū)域CROC （C）_i 的區(qū)域參與度PI（ROC（C）_i，C） 即可判斷CROC （C）_i 是否為并置模式 c 的一個(gè)頻繁區(qū)域 PROC（C）_i 。特別地，對(duì)于一階并置模式 c ，其候選區(qū)域與定義1中的存在區(qū)域相同，即為特征 f（f∈C） 的簇中所有實(shí)例的凸包。在傳統(tǒng)并置模式挖掘算法中，搜索行實(shí)例是最耗時(shí)的操作。本文在搜索候選區(qū)域CROC （C）_i 內(nèi)的行實(shí)例之前，利用區(qū)域粗參與度進(jìn)行剪枝，提前剪掉不可能頻繁的區(qū)域。

定義7并置模式的區(qū)域粗參與度。在候選區(qū)域CROC（C）_i 中，對(duì)于并置模式 c 的任一特征 f（f∈C） ，其區(qū)域粗參與率可定義為該特征在候選區(qū)域CROC （C）_i 中所有實(shí)例的數(shù)量與該特征在相應(yīng)簇 cl_i 中所有實(shí)例的數(shù)量之比，表示為

其中 表示在候選區(qū)域CROC （C）_i 中特征 f 的所有實(shí)例； N（cl_i，f） 表示在相對(duì)應(yīng)簇 cl_i 中特征 f 的所有實(shí)例。在候選區(qū)域 CROC（C）_i 中，并置模式 c 的區(qū)域粗參與度為 c 中特征在該候選區(qū)域的粗參與率的最小值，即

CPI（CROC（C）_i，C）=min_j=1^k{CPR（CROC（C）_i，f_j）}

例9在圖3（b）簇 cl₁ 中，特征 B 在候選區(qū)域CROC（ABC）₁ 中的實(shí)例個(gè)數(shù)為4，在簇 cl₁ 中實(shí)例個(gè)數(shù)為5，根據(jù)式（5），特征 B 在CROC （ABC）₁ 中的區(qū)域粗參與率為：CPR1 CROC（ABC）₁，B）=4/5=0. 800。同理，特征 A 在CROC（ABC）₁ 中的區(qū)域粗參與率為： CPR（CROC（ABC）₁，A）=4/4= 1.000;特征 c 在 CROC（ABC）₁ 中的區(qū)域粗參與率為：CPR?CROC（ABC）₁，C?=4/5=0.80 0。根據(jù)式（6），在候選區(qū)域CROC（ABC）₁ 中，并置模式 {A，B，C} 的區(qū)域粗參與度為：CPI（CROC（ABC）₁ {ABC}=min{1.000，0.800，0.800}=0.800 （204號(hào)

引理4在并置模式 c 的候選區(qū)域CROC （C）_i 中，PI（CROC（C）_i，C）?CPI（CROC（C）_i，C） 。

證明根據(jù)引理1可知，候選區(qū)域 CROC（C）_i 包含模式 c 在簇 cl_i 中的所有參與實(shí)例，則有Obj（ROC （C）_i ， C，f）? N（CROC（C）_i，f） 。對(duì)于模式 c 的任一特征 f（f∈C） ，根據(jù)定義2與7可知，其區(qū)域參與率與區(qū)域粗參與率的分母都為∣N（cl_i，f）∣ ，對(duì)于分子有丨Obj（ROC （C）_i，C，f）∣?∣N （CROC（C）_i，f） 1。因此，有PR（CROC （C）_i，C，f）?CPR （ CROC（C）_i，f） ，進(jìn)而 PI（CROC（C）_i，C）?CPI（CROC（C）_i，C） 。

圖4（a）展示了基線算法在單簇中生成并置模式頻繁區(qū)域的過(guò)程：先在整個(gè)簇中挖掘模式 c 的所有參與實(shí)例，根據(jù)實(shí)例生成存在區(qū)域，計(jì)算區(qū)域參與度 PI（ROC（C）_i，C） ，判斷其是否為頻繁區(qū)域。該方法在生成高階并置模式的頻繁區(qū)域時(shí)需重新搜索參與實(shí)例，范圍廣且驗(yàn)證行實(shí)例耗時(shí)，尤其當(dāng)實(shí)例數(shù)目較多時(shí)。圖4（b）描述了替代策略在單個(gè)簇中從低階模式的頻繁區(qū)域生成高階模式的頻繁區(qū)域的過(guò)程。替代策略在生成并置模式 c 的頻繁區(qū)域時(shí)，首先將其所有k-1階子模式 C^′ 的頻繁區(qū)域向外拓展 d 個(gè)單位得到拓展區(qū)域ExtPROC （C^′）_i ，根據(jù)所有子模式的拓展區(qū)域的交集得到并置模式 c 的候選區(qū)域CROC （C）_i 。計(jì)算該候選區(qū)域的區(qū)域粗參與度CPI（CROC（C）_i，C） 進(jìn)行剪枝。如果區(qū)域粗參與度CPI（CROC （C）_i，C）? min_prev，則將并置模式的參與實(shí)例的搜索范圍限制在候選區(qū)域中，計(jì)算區(qū)域參與度] PI（CROC（C）_i，C） ，依此判斷該候選區(qū)域是否為模式的頻繁區(qū)域。替代策略可依靠低階模式的頻繁區(qū)域較快地生成高階模式的頻繁區(qū)域，且參與實(shí)例的搜索范圍被限定到一個(gè)相對(duì)較小的區(qū)域，加快搜索進(jìn)程。

盡管替代策略中的頻繁區(qū)域生成方法會(huì)導(dǎo)致并置模式的頻繁區(qū)域面積增大、區(qū)域描述的精確度略微降低，但與基線方法相比，它可以顯著加快瀕繁區(qū)域的生成速度。在替代策略中，首先，基于子模式的先驗(yàn)信息確定了超模式在各簇中的存在位置，即候選區(qū)域，這比基線算法更高效；其次，替代策略利用模式的區(qū)域粗參與度，提前判斷候選區(qū)域的頻繁性，避免了不必要的實(shí)例搜索；最后，替代策略先生成模式的候選區(qū)域，再在其中搜索模式的參與實(shí)例，將搜索范圍限定在更小區(qū)域。

3算法及分析

3.1算法描述

基于替代策略的空間并置模式及其頻繁區(qū)域挖掘算法如算法1所示，稱之為PROC-Col算法，分為數(shù)據(jù)預(yù)處理、生成一階并置模式的頻繁區(qū)域，以及生成高階并置模式的頻繁區(qū)域三個(gè)部分。a）數(shù)據(jù)預(yù)處理。對(duì)數(shù)據(jù)集進(jìn)行凝聚層次聚類，針對(duì)聚類得到的每個(gè)簇 Δ_cli ，計(jì)算簇內(nèi)各實(shí)例的鄰居關(guān)系（1＼～7行）。b）生成一階并置模式的頻繁區(qū)域。首先對(duì)一階并置模式集合C¹ 及并置模式的頻繁區(qū)域集合PROCSet進(jìn)行初始化（第8行）。對(duì)于一階模式集合 C¹ 中的每一個(gè)并置模式 c ，循環(huán)遍歷簇集合 CL 中的每一個(gè)簇 cl_i ，在每一個(gè)簇中使用實(shí)例集合 o 生成一階并置模式 c 的頻繁區(qū)域PROC （C）_i ，并將PROC （C）_i 存儲(chǔ)到集合 PROCSet 里，直到遍歷完所有一階并置模式 c 的簇 cl_i ，循環(huán)結(jié)束 （9～14 行）。c）生成高階并置模式的頻繁區(qū)域。當(dāng)集合 C^k-1 不為空的時(shí)候，用apriori_gen函數(shù)從k-1階并置模式集合 C^k-1 中生成 k 階并置模式集合 C^k（15，16 行）。對(duì)集合 C^k 中的每一個(gè) k 階并置模式 c ，循環(huán)遍歷簇集合 CL 中的每一個(gè)簇 cl_i ，將 c 的每個(gè) k-1 階子模式 C^k-1 在本簇中的頻繁區(qū)域PROC （C）_i 擴(kuò)展成拓展區(qū)域 ExtPROC（C）_i 。利用所有k-1階子模式的拓展區(qū)域 ExtPROC（C）_i 的交集生成 c 的候選區(qū)域CROC （C）_i 。然后在候選區(qū)域CROC （C）_i 中計(jì)算區(qū)域粗參與度C PI（CROC（C）_i，C） （17＼～21行）。如果CPI（CROC（?C）_i，C）-prev ，則此簇被剪枝，循環(huán)跳轉(zhuǎn)到下一個(gè)簇（22、23行）。否則，使用join-based算法[1]得到并置模式 c 的參與實(shí)例集合Objset。根據(jù)并置模式 c 的參與實(shí)例集Objset計(jì)算其在該區(qū)域的區(qū)域參與度 PI（CROC（C）_i，C） （24＼～26行）。如果PI（CROC （C）_i，C） 大于等于給定的頻繁閾值min_prev，則把判定為頻繁區(qū)域的 CROC（C）_i 放入集合PROCSet中（27＼～29行）。直到循環(huán)完每個(gè)模式所有的簇。算法最后得到所有的并置模式 c 反這些開直俁式的頻系區(qū)域柒日「u3eJ行）。

算法1 PROC-Col算法

輸入：實(shí)例集 o ；特征集 F ；距離閾值 d ;頻繁性閾值min_prev。輸出：所有的并置模式 c 及其頻繁區(qū)域集合 PROCSet 。

1CL←{}，CLNBRs←{} （20

2 clusters O= MCEMS_Clustering（O）

3 for each cl_i in clusters do

4 NBRs FindNeighbors （cl_i，d） //計(jì)算簇內(nèi)實(shí)例的鄰居關(guān)系5 CLNBRs σ=σ CLNBRs U NBRs

6 （20號(hào) CL=CL∪cl_i （204

7 return CL ，CLNBRs

8初始化 C¹=F;k=2;PROCSet{}

9 for C in C¹ do

10 for cl_i in CL do

11 根據(jù)簇內(nèi)實(shí)例的分布構(gòu)建一階模式的頻繁區(qū)域 /

12 PROCSet=PROCSet∪PROC（C）_i （20

13 end for

14 end for

15 while c^k-1≠? do

16 （204號(hào) 生成 k 階并置模式集合

17 for c in C^k do

18 for cl_i in CL do

19 ExtROC （C^k-1）_i= generate _extend_region（PROC（204號(hào) （C^k-1）_i）/? 根據(jù) k-1 階模式頻繁區(qū)域生成 k-1 階模式拓展區(qū)域*／

20 CROC （C）_i= generate_candidate_region（ C^k-1 ， ExtROC（204號(hào) （C^k-1）_i）_i^? //根據(jù) k-1 階拓展區(qū)域生成 k 階模式候選區(qū)域

21 （2 CPI（CROC（C）_i，C）= calculate_coarse_participation_in-（20號(hào) dex（CROC（C）_i，C）/ /計(jì)算區(qū)域粗參與度

22 證 CPI（CROC（C）_i，C）

23 continue

24 else

25 Objset join_based_algorithm（CROC （C）_i，C）/* 生成參與實(shí)例集 * /

26 PI（CROC （C）_i c）= calculate_participation_index0 χ_{CROC（C）i，C}） //計(jì)算區(qū)域參與度

27 if PI（CROC（C），，C）≥min_prev then//判斷頻繁性28 （204 （PROCSet，C）=（C，PROCSet）∪（C，CROC（C）_i） 29 endif

30 end if

31 end for

32 end for

33end while

34 return （PROCSet，C）

3.2算法分析

a）時(shí)間復(fù)雜度。在算法1中，數(shù)據(jù)預(yù)處理部分的算法需要對(duì)數(shù)據(jù)集進(jìn)行凝聚層次聚類，并計(jì)算每個(gè)簇中實(shí)例的鄰居關(guān)系。在最壞情況下，計(jì)算每個(gè)簇中鄰居關(guān)系的復(fù)雜度為O（n²） ，其中 n 是實(shí)例的數(shù)量。層次聚類的復(fù)雜度一般為O（n³） ，因此數(shù)據(jù)預(yù)處理的總時(shí)間復(fù)雜度為 O（n³） 。生成一階并置模式的頻繁區(qū)域部分，對(duì)每個(gè)一階并置模式循環(huán)遍歷所有的簇。假設(shè)有 m 個(gè)簇，特征集大小為 f ，生成頻繁區(qū)域的操作時(shí)間復(fù)雜度取決于簇中實(shí)例的數(shù)量。該部分的時(shí)間復(fù)雜度為O（f×m×n） ，其中 n 是簇中實(shí)例的數(shù)量。生成高階并置模式的頻繁區(qū)域部分，這部分使用了Apriori算法來(lái)生成高階模式，時(shí)間復(fù)雜度取決于模式的階數(shù) k Apriori算法本身的時(shí)間復(fù)雜度是指數(shù)級(jí)的， O（2^f） ，其中 f 是特征的數(shù)量。每一階的頻繁區(qū)域生成需要遍歷所有簇，并對(duì)候選區(qū)域進(jìn)行計(jì)算。因此，這部分的復(fù)雜度為 O（k×m×n×2^f） ，其中 k 是模式的最大階數(shù)。綜上，PROC-Col算法的總體時(shí)間復(fù)雜度約為 O（n³+f×m×n+k×m× n×2^f ，其中 n 是實(shí)例數(shù)量， m 是簇的數(shù)量 ，f 是特征數(shù)量， k 是模式的最大階數(shù)。

b）空間復(fù)雜度。在算法1中，數(shù)據(jù)存儲(chǔ)部分的算法需要存儲(chǔ)實(shí)例集 o 、特征集 F 以及每個(gè)簇的鄰居關(guān)系。存儲(chǔ)實(shí)例和鄰居關(guān)系的空間復(fù)雜度為 O（n²） ，其中 n 是實(shí)例數(shù)量。頻繁區(qū)域存儲(chǔ)部分，每個(gè)頻繁區(qū)域需要存儲(chǔ)簇中的實(shí)例及其鄰居關(guān)系，因此空間復(fù)雜度為 O（m×n） ，其中 ?_m 是簇的數(shù)量， n 是簇中實(shí)例的數(shù)量。候選區(qū)域和參與實(shí)例集部分，在生成高階并置模式時(shí)，需要存儲(chǔ)候選區(qū)域和參與實(shí)例集合，空間復(fù)雜度與特征的數(shù)量 f 與簇的數(shù)量 m 相關(guān)，為 O（m×2^f） 。綜合考慮，PROC-Col算法的空間復(fù)雜度為 O（n²+m×n+m×2^f） 。

4實(shí)驗(yàn)

本章分別在兩個(gè)合成數(shù)據(jù)集和兩個(gè)真實(shí)數(shù)據(jù)集（石林縣喀斯特地貌天然林保護(hù)區(qū)數(shù)據(jù)集和深圳POI數(shù)據(jù)集）上進(jìn)行了大量實(shí)驗(yàn)，以評(píng)估所提PROC-Col算法的有效性。將近年來(lái)優(yōu)秀的區(qū)域并置模式挖掘算法（multi-level算法）[12]、基于密度峰值聚類和模糊理論的區(qū)域空間并置模式挖掘方法（FDPC-PRCPM）[1°]與PROC-Col進(jìn)行了比較。

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

4.1.1真實(shí)數(shù)據(jù)集

表1描述了兩個(gè)真實(shí)數(shù)據(jù)集的主要參數(shù)。石林縣喀斯特地貌天然林保護(hù)區(qū)數(shù)據(jù)集共有64個(gè)特征，16918個(gè)空間實(shí)例，空間數(shù)據(jù)分布較為集中。深圳POI數(shù)據(jù)集具有13個(gè)特征和71606個(gè)空間實(shí)例，空間數(shù)據(jù)呈聚類分布。圖5分別為兩個(gè)數(shù)據(jù)集不同特征實(shí)例在空間上的空間分布。

表1真實(shí)數(shù)據(jù)集的參數(shù)

4.1.2合成數(shù)據(jù)集

為了更深入地研究不同數(shù)據(jù)分布對(duì)算法的影響，本文對(duì)不同分布的數(shù)據(jù)集進(jìn)行了實(shí)驗(yàn)分析，以了解本文算法更適合哪種類型的數(shù)據(jù)。圖6展示了兩個(gè)空間分布不同的模擬數(shù)據(jù)集：圖6（a）展示了合成數(shù)據(jù)集1（各特征參數(shù)見表2），包含兩個(gè)全局分布的特征和四個(gè)局部分布的特征，用于模擬具有區(qū)域并置模式的空間數(shù)據(jù)集。圖6（b）展示了合成數(shù)據(jù)集2，由9個(gè)全局分布的特征組成。

合成數(shù)據(jù)集1總共包含{A，B，C，D，E，F(xiàn)，G|六個(gè)特征，其中特征A、G的實(shí)例分布是全局的，其他特征的實(shí)例分布是局部的，模擬了重疊實(shí)例分布的情況，特征A、G將與其他特征形成區(qū)域并置模式。特征B、C用于模擬檢測(cè)不同特征實(shí)例間交叉形成的區(qū)域頻繁模式B，C、 { A，B，C}、{B，C，G}和{A，B，C， 。在此合成數(shù)據(jù)集1中預(yù)構(gòu)建的可能的區(qū)域頻繁并置模式為{A，B}、A，C}、{A，D}、{A，E}、{A，F(xiàn)}、{A，G}、B，C、B，G}、{C，G}，D，G}、E，G}、{F，G}、A，B，C}、{B，C，G}、{A，B，C，G}。

4.2頻繁區(qū)域結(jié)果有效性評(píng)價(jià)與分析

4.2.1頻繁區(qū)域結(jié)果的合理性分析

為驗(yàn)證本文算法在生成頻繁區(qū)域階段的準(zhǔn)確性和優(yōu)越性，在真實(shí)數(shù)據(jù)集中進(jìn)行了帶頻繁區(qū)域的并置模式挖掘。圖7展示了石林縣喀斯特地貌天然林保護(hù)區(qū)數(shù)據(jù)集上的挖掘結(jié)果（見電子版）。

a）數(shù)據(jù)與模式說(shuō)明。在數(shù)據(jù)集中選擇特征Ab（云南松）、Af（桉樹）Ar（柏木）組成模式 {Ab，Af，Ar} 。這三種樹木分別適應(yīng)不同的氣候條件：云南松適應(yīng)高海拔和干燥環(huán)境，柏木常見于溫潤(rùn)氣候，按樹因耐旱性和快速生長(zhǎng)在多種環(huán)境中廣泛種植。盡管適應(yīng)性不同，它們?cè)谠颇系亩鄻踊瘹夂驐l件下可能共存。

b）結(jié)果展示。圖7（a）為原始數(shù)據(jù)集中各特征的空間分布，綠色、紅色、藍(lán)色分別表示Ab、Af、Ar實(shí)例，灰色為其他實(shí)例。圖7（b）為模式 {Ab，Af} 的頻繁區(qū)域劃分，紫色為不同簇中的頻繁區(qū)域，灰色為其他實(shí)例。圖7（c）為模式 {Af，Ar} 的頻繁區(qū)域劃分，綠色為不同簇中的頻繁區(qū)域，灰色為其他實(shí)例。圖7（d為使用替代策略得到的模式 {Ab，Af，Ar} 的頻繁區(qū)域，結(jié)果與特征分布高度吻合。

c）生態(tài)意義。頻繁區(qū)域表明這些樹種可能共存于特定生態(tài)條件下，例如適中的氣候、土壤PH值和養(yǎng)分水平。這些區(qū)域不僅反映了生態(tài)系統(tǒng)的獨(dú)特性，也可作為監(jiān)測(cè)和評(píng)估生態(tài)系統(tǒng)健康的重要指標(biāo)。實(shí)驗(yàn)結(jié)果顯示，本文算法生成的頻繁區(qū)域與特征實(shí)例分布具有較高的一致性，有效體現(xiàn)了區(qū)域生態(tài)特征。

4.2.2帶頻繁區(qū)域的并置模式挖掘結(jié)果的比較

本研究使用近年來(lái)提出的高效的區(qū)域并置模式挖掘算法，即Deng等人[1在2017年提出的multi-level算法，在深圳POI數(shù)據(jù)集上進(jìn)行了對(duì)比實(shí)驗(yàn)。值得注意的是，multi-level算法旨在挖掘所有頻繁的區(qū)域并置模式，而本文算法特別關(guān)注于挖掘帶頻繁區(qū)域的并置模式。因此，在進(jìn)行對(duì)比挖掘結(jié)果的實(shí)驗(yàn)時(shí)，只關(guān)注具有頻繁區(qū)域的并置模式。在深圳POI數(shù)據(jù)集中，將頻繁閾值設(shè)置為0.5。根據(jù)POI數(shù)據(jù)集的空間分布范圍，將距離閾值 d 設(shè)置為 120m 。對(duì)于multi-level的豐度閥值，使用0.05 。

表3列出了并置模式、頻繁水平（全局/區(qū)域）參與度及是否有頻繁區(qū)域。由于PROC-Col和multi-level在不同頻繁區(qū)域中同一模式的參與度不同，所以選取最小參與度值作為代表。表3展示了在深圳POI數(shù)據(jù)集上的挖掘結(jié)果，虛線表示無(wú)結(jié)果。PROC-Col不區(qū)分頻繁水平，因此其結(jié)果的頻繁水平與multi-level定義一致。

對(duì)于全局頻繁模式，multi-level無(wú)法識(shí)別其頻繁區(qū)域，而PROC-Col可以有效挖掘這些模式的頻繁區(qū)域，且其參與度接近全局參與度，顯示PROC-Col更準(zhǔn)確有效，能夠更好地揭示數(shù)據(jù)特征。

從表3可見，兩種算法挖掘出的區(qū)域并置模式大多重合，但PROC-Col還能識(shí)別出multi-level未能挖掘的頻繁區(qū)域，如{B，C，H}，{B，D，H}，{C，D，H} ，進(jìn)一步凸顯其優(yōu)勢(shì)。

兩種方法產(chǎn)生不同結(jié)果的原因有：a）框架不同，PROC-Col對(duì)所有可能模式進(jìn)行挖掘，而multi-level僅針對(duì)全局不頻繁模式；b）頻繁區(qū)域生成方法不同，PROC-Col通過(guò)低階模式頻繁區(qū)域迭代生成高階模式，而multi-level采用Delaunay三角剖分法進(jìn)行聚類。這導(dǎo)致了頻繁區(qū)域結(jié)果的差異。

由表3可以看出，multi-level的大部分并置模式的PI幾乎都趨向于1，相比之下，表3所示的PROC-Col的挖掘結(jié)果的PI值更加具有區(qū)分度。這是因?yàn)閙ulti-level得到并置模式的頻繁區(qū)域在研究區(qū)域內(nèi)通常是隨機(jī)分布的，具有面積小、子區(qū)域多的特點(diǎn)。相對(duì)來(lái)說(shuō)，PROC-Col生成的頻繁區(qū)域面積大、數(shù)量適中。

以區(qū)域并置模式 {C，F(xiàn)，H} 為例，圖8（a）（b）分別展示了使用PROC-Col和multi-level對(duì)該模式的頻繁區(qū)域挖掘結(jié)果。從圖中可以看出，PROC-Col挖掘出的頻繁區(qū)域數(shù)為6，而multi-level得到的頻繁區(qū)域數(shù)為9。此外，multi-level得到的頻繁區(qū)域存在大量重疊，且對(duì)于某些特定類型的頻繁區(qū)域，其挖掘出的區(qū)域范圍明顯大于模式實(shí)際存在的頻繁區(qū)域。這是由于這些特定類型的頻繁區(qū)域中，子模式的行實(shí)例大量存在，而超模式的行實(shí)例較少。multi-level通過(guò)對(duì)子模式頻繁區(qū)域進(jìn)行并集運(yùn)算來(lái)獲得超模式的頻繁區(qū)域，導(dǎo)致了一些實(shí)際并不頻繁的區(qū)域也被錯(cuò)誤地劃入頻繁區(qū)域。相比之下，PROC-Col算法通過(guò)對(duì)超模式的所有子模式的拓展區(qū)域進(jìn)行交集運(yùn)算來(lái)確定該超模式的頻繁區(qū)域，從而有效避免了將實(shí)際不頻繁的區(qū)域錯(cuò)誤劃入頻繁區(qū)域的問(wèn)題。同時(shí)，PROC-Col還能確保各頻繁區(qū)域之間不存在交叉重疊，進(jìn)一步提高了挖掘結(jié)果的精度。

表4展示了PROC-Col與multi-level在合成數(shù)據(jù)集1上距離閾值為0.02時(shí)的執(zhí)行結(jié)果。表中詳細(xì)列出了預(yù)定義的區(qū)域并置模式及兩種算法在識(shí)別這些區(qū)域并置模式的頻繁區(qū)域方面的成功與否。由于multi-level致力于區(qū)域并置模式的挖掘，所以理論上它能成功識(shí)別的帶頻繁區(qū)域的并置模式均為區(qū)域并置模式。因此，在評(píng)估PROC-Col與multi-level在挖掘帶頻繁區(qū)域的并置模式的準(zhǔn)確率時(shí)，僅考慮了這些區(qū)域并置模式。

從表4的結(jié)果可以看出，PROC-Col在低頻繁閾值和高頻繁閾值下都能正確挖掘出合成數(shù)據(jù)集中預(yù)設(shè)的帶頻繁區(qū)域的并置模式，而multi-level在低頻繁閾值和高頻繁閾值下可能無(wú)法檢測(cè)部分帶頻繁區(qū)域的并置模式。

以區(qū)域并置模式 {A，B，C} 為例，圖9（a）（b）分別展示了使用PROC-Col和multi-level對(duì)該模式的頻繁區(qū)域挖掘結(jié)果。圖9（b）中，由于對(duì)子模式頻繁區(qū)域進(jìn)行并集運(yùn)算，multi-level錯(cuò)誤地將一些僅有模式 {A，C} 行實(shí)例存在，而無(wú)模式 {A，B，C} 行實(shí)例存在的區(qū)域劃為了模式 {A，B，C} 的頻繁區(qū)域。圖9（a）中，PROC-Col有效規(guī)避了這一問(wèn)題，使挖掘出的模式 {A，B，C} 的頻繁區(qū)域很好地貼合實(shí)際上的頻繁區(qū)域，從而提高了挖掘結(jié)果的準(zhǔn)確度。

4.2.3頻繁區(qū)域的精確度比較

本文算法與FDPC-PRCPM[\"在石林縣喀斯特地貌天然林保護(hù)區(qū)數(shù)據(jù)集、合成數(shù)據(jù)集2上進(jìn)行挖掘結(jié)果精確度的比較。對(duì)于一個(gè)并置模式的頻繁區(qū)域而言，最理想的挖掘結(jié)果應(yīng)為由該并置模式的所有參與實(shí)例構(gòu)成的凸包。因此，可以引入頻繁區(qū)域精確度的概念，用于對(duì)算法的挖掘結(jié)果進(jìn)行定量分析，以評(píng)估其與理想分布的契合程度。精確度是用于衡量算法挖掘出的并置模式頻繁區(qū)域與其實(shí)際分布區(qū)域契合程度的一個(gè)指標(biāo)。定義為簇內(nèi)并置模式 c 的參與實(shí)例的凸包面積與算法挖掘出的并置模式 c 的瀕繁區(qū)域的面積之比，公式如下：

精確度的值越大，表示算法挖掘出的頻繁區(qū)域與并置模式的真實(shí)分布區(qū)域越接近，誤差越小，說(shuō)明挖掘結(jié)果更符合實(shí)際分布情況。因此，精確度可以作為評(píng)估算法準(zhǔn)確性和結(jié)果合理性的重要指標(biāo)。

表5、6分別展示了本文PROC-Col與FDPC-PRCPM在石林縣喀斯特地貌天然林保護(hù)區(qū)數(shù)據(jù)集和合成數(shù)據(jù)集2上，距離閾值設(shè)為30和0.02、頻繁閾值設(shè)為0.5時(shí)挖掘出的頻繁區(qū)域精確度。由于每個(gè)算法對(duì)每個(gè)模式均挖掘出多個(gè)頻繁區(qū)域，所以選取精確度最高的頻繁區(qū)域作為算法挖掘結(jié)果的代表。

從表中可以看出，在真實(shí)數(shù)據(jù)集和合成數(shù)據(jù)集上，PROC-Col挖掘出的頻繁區(qū)域精確度均顯著高于FDPC-PRCPM。這主要是因?yàn)镕DPC-PRCPM基于密度峰值聚類，將密度相似的數(shù)據(jù)點(diǎn)歸為同一類。然而，由于實(shí)驗(yàn)中的兩個(gè)數(shù)據(jù)集的數(shù)據(jù)分布較為均勻，聚類簇通常較大，但類內(nèi)并置模式的分布并不均勻散布，導(dǎo)致由并置模式參與實(shí)例構(gòu)建的凸包面積較小。而FDPC-PRCPM直接將聚類簇作為并置模式的頻繁區(qū)域，最終導(dǎo)致挖掘出的頻繁區(qū)域精確度較低。相比之下，PROC-Col首先通過(guò)凝聚層次聚類對(duì)數(shù)據(jù)集進(jìn)行初步劃分，然后在每個(gè)簇內(nèi)根據(jù)數(shù)據(jù)點(diǎn)的實(shí)際分布逐步生成并置模式的頻繁區(qū)域。盡管在提高算法效率的過(guò)程中采用了一些替代策略，犧牲了一定程度的精確度，但從最終的精確度結(jié)果來(lái)看，這種犧牲是可接受的，且PROC-Col的精確度整體上顯著優(yōu)于FDPC-PRCPM。

表5兩種算法在石林縣喀斯特地貌天然林保護(hù)區(qū)數(shù)據(jù)集中的挖掘結(jié)果精確度比較

4.3算法可擴(kuò)展性評(píng)價(jià)與分析

本節(jié)實(shí)驗(yàn)主要探討了在改變空間特征的數(shù)量和實(shí)例數(shù)量時(shí)，本文算法的可擴(kuò)展性。除了multi-level外，本次實(shí)驗(yàn)還將本文算法的不同版本進(jìn)行了對(duì)比。其中，PROC-Col-base為一種不采用替代策略的基線版本，而PROC-Col-nCPI則在采用替代策略的同時(shí)，不考慮區(qū)域粗參與度的情況。這樣的設(shè)置可以更細(xì)致地評(píng)估算法在不同配置下的性能變化。

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

為了測(cè)試實(shí)例數(shù)對(duì)PROC-Col運(yùn)行時(shí)間的影響，本文通過(guò)實(shí)驗(yàn)比較了四種算法在不同實(shí)例數(shù)下的運(yùn)行時(shí)間。在本實(shí)驗(yàn)中，為了挖掘有效的帶頻繁區(qū)域的并置模式，本文使用了如圖6（a）所示分布類型的合成數(shù)據(jù)集。使用數(shù)據(jù)生成器生成合成數(shù)據(jù)集，將特征數(shù)量固定為5，實(shí)例數(shù)量分別設(shè)置為5000、10000、15000、20000和25000。除了合成數(shù)據(jù)集，本文還在深圳POI數(shù)據(jù)集上進(jìn)行同樣的實(shí)驗(yàn)。在深圳POI數(shù)據(jù)集中隨機(jī)抽取5個(gè)特征，并在這5個(gè)特征中隨機(jī)抽取5000、10.000、15000、20000和25000個(gè)實(shí)例。

圖10展示了四種算法在不同實(shí)例數(shù)量條件下的運(yùn)行時(shí)間。分析發(fā)現(xiàn)，隨著實(shí)例數(shù)量的增加，算法間的性能差異也隨之增大。在合成數(shù)據(jù)集和真實(shí)數(shù)據(jù)集上，multi-level由于需要首先挖掘全局頻繁的并置模式，所以其運(yùn)行時(shí)間相對(duì)較長(zhǎng)。具體來(lái)說(shuō)，multi-level需要額外的時(shí)間來(lái)處理全局頻繁模式，這在實(shí)例數(shù)增多時(shí)尤為明顯。而對(duì)于PROC-Col-base，隨著實(shí)例數(shù)量的增加，所需處理的表實(shí)例增多，相應(yīng)地，確定模式存在區(qū)域所需的時(shí)間也會(huì)增加。對(duì)于PROC-Col-nCPI，計(jì)算區(qū)域參與度所需的時(shí)間隨實(shí)例數(shù)量增多而延長(zhǎng)。相比之下，本文算法PROC-Col在處理增加的實(shí)例數(shù)時(shí)顯示出更佳的效率?？傮w上看，PROC-Col的運(yùn)行時(shí)間大約是multi-level的一半。

綜上所述，研究表明提出的三種版本的帶頻繁區(qū)域的并置模式挖掘框架在實(shí)例數(shù)量增多的情況下，所需的執(zhí)行時(shí)間均短于multi-level。通過(guò)比較PROC-Col-base、PROC-Col-nCPI以及完整的PROC-Col的執(zhí)行時(shí)間發(fā)現(xiàn)，引入的替代策略及區(qū)域粗參與度過(guò)濾有效縮短了運(yùn)行時(shí)間，尤其是替代策略，在大規(guī)模數(shù)據(jù)集上尤為有效，顯著縮短了算法的運(yùn)行時(shí)間。

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

在合成數(shù)據(jù)集上，考慮最壞情況，在類似圖6（b）的數(shù)據(jù)分布下進(jìn)行實(shí)驗(yàn)，更直觀地研究增加特征數(shù)量對(duì)算法效率的影響。本文將實(shí)例數(shù)量固定為20000，并分別使用6、8、10、12、14和16個(gè)特征進(jìn)行實(shí)驗(yàn)。類似地，在深圳POI數(shù)據(jù)集上做了相同的實(shí)驗(yàn)，其中實(shí)例數(shù)量固定為20000，并隨機(jī)選擇不同數(shù)量的特征。圖11描述了四種算法在不同特征數(shù)下的運(yùn)行時(shí)間和帶頻繁區(qū)域的并置模式數(shù)。圖11顯示了，無(wú)論是在合成數(shù)據(jù)集還是真實(shí)數(shù)據(jù)集上，隨著特征數(shù)量的增加，PROC-Col-nCPI和PROC-Col的執(zhí)行時(shí)間均顯著增加。這種現(xiàn)象主要是由于隨著特征數(shù)量的增長(zhǎng)，潛在的帶頻繁區(qū)域并置模式的數(shù)量和復(fù)雜性也相應(yīng)增加。在這種情況下，替代策略需要處理更多的超模式以及它們的子模式，尤其是在計(jì)算這些模式的拓展區(qū)域并求取它們的交集時(shí)，操作數(shù)量會(huì)顯著增多，從而導(dǎo)致執(zhí)行時(shí)間的增加。

盡管如此，使用了替代策略的PROC-Col-nCPI和完整的PROC-Col在特征數(shù)量增加時(shí)的執(zhí)行時(shí)間雖然有所上升，但仍然低于PROC-Col-base和multi-level的執(zhí)行時(shí)間。這表明，盡管特征數(shù)量的增加帶來(lái)更多的計(jì)算負(fù)擔(dān)，但通過(guò)優(yōu)化的策略如替代策略和區(qū)域粗參與度計(jì)算，這些方法依然能有效地提升算法整體的效率，尤其在處理大規(guī)模特征集時(shí)更顯優(yōu)勢(shì)。

5結(jié)束語(yǔ)

本文針對(duì)傳統(tǒng)空間并置模式挖掘過(guò)程中難以確定模式頻繁出現(xiàn)的具體區(qū)域這一問(wèn)題，提出了一種新穎的帶頻繁區(qū)域的空間并置模式挖掘算法。該算法通過(guò)兩階段方法，首先利用凝聚層次聚類方法進(jìn)行空間分區(qū)，確認(rèn)實(shí)例間的鄰近關(guān)系；隨后引入并置模式存在區(qū)域與區(qū)域參與度的概念，逐階識(shí)別出模式的頻繁區(qū)域。同時(shí)，算法通過(guò)子模式的擴(kuò)展區(qū)域構(gòu)建高階模式的候選區(qū)域，并利用區(qū)域粗參與度有效篩除不可能頻繁的候選區(qū)域，從而加速了整個(gè)挖掘過(guò)程。實(shí)驗(yàn)結(jié)果表明，該算法在真實(shí)和模擬數(shù)據(jù)集上的性能和效果顯著，能夠更準(zhǔn)確地識(shí)別出空間并置模式的頻繁區(qū)域。

未來(lái)可以進(jìn)一步優(yōu)化算法在大規(guī)模數(shù)據(jù)集上的計(jì)算效率，并探索在不同類型的空間數(shù)據(jù)集（如三維空間或時(shí)空數(shù)據(jù)）中的應(yīng)用。同時(shí)，還可以嘗試結(jié)合深度學(xué)習(xí)和其他智能算法，提升空間并置模式挖掘的精度和可擴(kuò)展性，從而在更多實(shí)際應(yīng)用場(chǎng)景中發(fā)揮作用，如城市規(guī)劃、生態(tài)監(jiān)測(cè)和氣象預(yù)測(cè)等領(lǐng)域。

參考文獻(xiàn)：

[1]Li Deren，WangShuliang，Li Deyi.Spatial data mining[M]．Berlin：Springer，2015

[2]HuangY， Shekhar S，Xiong H. Discovering colocation patterns from spatial data sets：a general approach [J]. IEEE Trans on Knowledge and Data Engineering，2004，16（12）： 1472-1485.

[3]Li Jundong，Adilmagambetov A， Mohomed Jabbar M S，et al. On discovering co-location patterns in datasets：a case study of pollutants and child cancers[J].Geolnformatica，2016，20（4）：651-692.

[4]Yao Xiaojing，Jiang Xufeng，Wang Dacheng，et al.Efficiently mining maximal co-locationsin aspatial continuous field under directed road networks[J]. Information Sciences，2021，542：357-379.

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

[6]Mohan P，Shekhar S，Shine JA，et al.A neighborhood graph based approach to regional co-location pattern discovery [C]//Proc of the 19th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems.New York：ACMPress，2011：122-132.

[7]Celik M，Kang JM，Shekhar S.Zonal co-location pattern discovery with dynamic parameters [C]//Proc of the 7th IEEE International Conference on Data Mining. Piscataway，NJ： IEEE Press，20O7： 433-438.

[8]Ding Wei，Eick CF，Yuan Xiaojing，etal.Aframework for regional association rule mining and scoping in spatial datasets [J].Geolnformatica，2011，15（1）：1-28.

[9]Qian Feng，Chiew K，He Qinming，et al. Mining regional co-location patterns with kNNG [J]. Journal of Intelligent Information Systems，2014，42（3）： 485-505.

[10] Jiang Xiwen，Wang Lizhen，Tran V.A parallelalgorithm for regional co-location mining based on fuzzy density peak clustering[J].Scientia Sinica Informationis，2023，53：1281-1298.

[11]Eick CF，Parmar R，Ding Wei，etal.Finding regional co-location patterns for sets of continuous variables in spatial datasets [C]//Proc of the 16th ACM SIGSPATIAL International Conference on Advances in Geographic InformationSystems.New York：ACMPress，2008：1-10.

[12]Deng Min，Cai Jiannan，Liu Qiliang，etal.Multi-level method for discovery of regional co-location patterns[J].International Joumal of Geographical Information Science，2017， 31（9）：1846-1870.

[13]Wang Dongsheng，Wang Lizhen，Jiang Xiwen，et al.RCPM_CFI：a regional core pattern mining method based on core feature influence [J].Information Sciences，2024，658：119895.

[14]Wang Dongsheng，Wang Lizhen，Wang Xiaoxu，et al.An approach based on maximal cliques and multi-density clustering for regional colocation pattern mining [J]. Expert Systems with Applications， 2024，248：123414.

[15]Yang Peizhong，Wang Lozhen， Wang Xiaoxuan， et al. A spatial colocation pattern mining approach based on column calculation[J]. Scientia Sinica Informationis，2022，52（6）：1053.

[16]Mohamed，Hashim H， Sihan Wei.Regional co-location pattern detection[EB/OL].（2020）. https：//api.semanticscholar.org/CorpusID：221585036.

[17]Cai Jiannan，Liu Qiliang，Deng Min，etal.Adaptive detection of statistically significant regional spatial co-location patterns[J].Computers，Environment and Urban Systems，2018，68：53-63.

[18]Li Teng，Rezaeipanah A， Tag El Din E M. An ensemble agglomerative hierarchical clustering algorithm based on clusters clustering technique and the novel similarity measurement[J].Journal of King Saud University-Computer and Information Sciences，2022，34 （6）：3828-3842.