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

關鍵詞：空間并置模式挖掘；頻繁區域；候選區域；拓展區域；區域粗參與度中圖分類號：TP391 文獻標志碼：A 文章編號：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年提出以來，取得了顯著進展。空間并置模式指經常一起出現的空間特征（事物）子集，在生態學、城市規劃等領域廣泛存在，如尼羅河鱷魚與埃及鸻的共生關系或百貨商店與禮品店的商業布局。隨著全球定位和遙感技術的飛速發展，空間數據呈爆炸式增長，挖掘這些數據以發現潛在知識成為研究熱點[2]。作為空間數據挖掘的重要分支，空間并置模式挖掘聚焦于揭示空間事物的關聯關系，在生態保護、公共衛生、地球科學[2]、交通運輸[3]和城市建設等領域應用廣泛。例如，它能揭示物種共生、探索疾病與污染的關聯，并為選址和規劃提供相應的決策支持[4]。基于改進列計算的空間并置模式挖掘方法通過減少回溯計算并加速參與實例的搜索，顯著提高了挖掘效率，成為當前高效的模式挖掘方法之一[5]。空間的異質性使得并置模式通常只在特定區域顯著，不同區域的特征關聯因環境多樣性而變化[6]。區域性模式挖掘能夠深入揭示地理數據中空間特征的依賴性，在多個應用領域發揮重要作用，推動空間數據利用進人深人發展階段。區域空間并置模式挖掘大致分為基于分區的方法和區域檢測策略兩類方法。基于分區的方法首先根據特定的空間分區方案將研究區域劃分為一系列子區域，然后使用全局并置模式發現方法來提取每個子區域中的所有頻繁并置模式。而區域檢測策略則旨在通過數據驅動的方式識別并置區域，通常基于不同特征的并置實例來確定這些區域。基于分區的方法包括了各種分區技術的應用，如Celik等人[7于2007年提出的四叉樹劃分、Ding等人[8]于2011年提出的多分辨率網格和Qian等人[9于2014年提出基于K最近鄰圖的層次空間分區方法。Jiang等人[10]于2022年提出了一種基于密度峰值聚類和模糊理論的區域空間并置模式挖掘方法。然而，這些方法的一個主要缺點是，用戶指定的分區方案通常與區域并置模式的自然分布無關，可能導致真實并置區域的挖掘受損。例如，四叉樹分區方案可能錯誤地將區域并置模式的子區域分隔開。區域檢測策略通過數據驅動的方式識別并置區域，以克服基于分區方法的限制。這些方法通常基于不同特征的并置實例來確定并置區域，如Eick等人[11]于2008年提出的原型基聚類方法、Mohan等人[于2011年提出的鄰域圖和Deng等人[12]于2017年提出的自適應模式聚類方法。Wang等人[13]于2024年提出了一種基于核心特征影響的區域核心模式挖掘方法。Wang等人[14]于2024年提出了一種基于最大團和多密度聚類的區域并置模式挖掘方法。

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

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

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

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

1基本理論

1.1空間并置模式挖掘

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

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

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

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

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

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

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

g）階數[1]。空間并置模式 c 的階數為集合 c 中空間特征的個數。

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

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

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

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

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

k）參與實例集[15]。模式 c 中特征 f 的參與實例集 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 為頻繁并置模式，空間并置模式的挖掘目標為找尋出空間數據集中所有的頻繁并置模式。

例2圖1中空間并置模式 {A，B，C} 就是一個3階的空間并置模式。對于空間并置模式 {A，B，C} 和空間并置模式 {A |B} ，由于 {A，B}?{A，B，C} ，則有模式 {A，B} 是模式 {A，B，C} 的子模式，模式 {A，B，C} 是模式 {A，B} 的超模式。對于實例集合RI （{A，B，C}）={A. 1，B. 3，C. 1} 滿足條件集合中任意兩個實例間都具有鄰居關系，并且RI（ {A，B，C} ）包含了3階并置模式 {A，B，C} 中的所有特征，則稱實例集合RI（ {A，B，C} ）為模式 {A，B，C} 的一個行實例。在整個空間數據集中模式 {A B，C} 的表實例 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 的參與實例集為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）∣= 。此時，假設給定的頻繁閾值min_prev為0.300，則模式 {A，B，C} 為一個頻繁并置模式。

1.2區域空間并置模式及其頻繁區域

在空間并置模式挖掘研究中，某些模式在全局范圍內不頻繁，但在特定區域內可能變得頻繁[16]。基于此，研究者提出了區域并置模式[1的定義：在空間數據集 s 中，假設存在一系列空間特征 F={f₁，f₂，…，f_n} 及其相應實例 O={o₁，o₂，…，o_m} ，以及這些實例間的相互鄰居關系。區域并置模式 RC 是空間特征 F 的一個子集，其實例頻繁共存于一個由多個子區域 L= {l₁，l₂，…，l_i，…，l_k} （其中， l_i 是 o 的一部分）組成的集合中。

在中等規模城市的空間數據中，可能發現區域并置模式{學校，托兒所}。盡管這一模式在全局上不頻繁，但在某些居民區，小學與托兒所常在步行距離內共現，以方便家長接送孩子并滿足日托需求。此外，在新開發區，中學附近可能新增托兒所，以服務年輕家庭。城市規劃者可據此優化教育資源布局，托兒所運營者亦可選擇更符合社區需求的地點。

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

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

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

例3圖1為對示例空間數據集進行凝聚層次聚類及物化鄰居關系后的結果，共有3個簇，每個簇內具有鄰居關系的實例用實線相連。

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

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

定義1并置模式的存在區域。給定并置模式 c ，其存在區域為該并置模式在簇中的所有參與實例所構成的凸包，記為并置模式的存在區域 ROC（C）_i 。其中，i表示該存在區域是并置模式； c 的第 i 塊存在區域。

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

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

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

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

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

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

定義4并置模式的頻繁區域。對于并置模式 c 的某個存在區域 ROC（C）_i ，如果PI（ROC （C）_i，C） 大于等于給定的頻繁閾值min_prev，則該存在區域為 c 的頻繁區域，記為PROC （C）_i 。

例6在圖2（a）簇 中，模式 {A，B} 在候選存在區域ROC（AB）₁ 的區域參與度的計算為 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，則存在區域 ROC（AB）₁ 為并置模式 {A，B} 的頻繁區域 PROC（AB）₁ 。

特別地，對于一階并置模式，將其在簇中所有實例組成的凸包記為頻繁區域。例如，圖2（b）中，紫色實線圍成的區域為一階模式 {A} 在簇 cl₁ 的頻繁區域 PROC（A）₁ ，該頻繁區域是由特征 A 在簇 cl₁ 中所有實例點所組成的凸包。

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

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

定義5并置模式的拓展區域。對于并置模式 c ，在簇 Δ_cli 中的拓展區域為該并置模式 c 的頻繁區域 PROC（C）_i 向外拓展 d 個單位后的區域，記為ExtPROC（ C）_i 。

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

拓展區域對頻繁區域PROC （C）_i 的邊界進行了擴充，類似于在邊界實例 ∣o∣ 的基礎上建立了一個以 σ_o 為圓心、以設定的距離閾值 d 為半徑的鄰居關系搜索圓。這樣確保ExtPROC（C）_i 不會遺漏頻繁區域PROC （C）_i 內任何實例的鄰居關系。

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

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

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

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

在簇 cl_i 中使用候選區域替代存在區域不會丟失并置模式的任何一個參與實例，因為引理1已證明 k 階并置模式 c 候選區域 CROC（C）_i 包含了 c 在簇 cl_i 中的所有參與實例。

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

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

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

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

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

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

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

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

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

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

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

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

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

3算法及分析

3.1算法描述

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

算法1 PROC-Col算法

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

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

2 clusters O= MCEMS_Clustering（O）

3 for each cl_i in clusters do

4 NBRs FindNeighbors （cl_i，d） //計算簇內實例的鄰居關系5 CLNBRs σ=σ CLNBRs U NBRs

6 （20號 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 根據簇內實例的分布構建一階模式的頻繁區域 /

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

13 end for

14 end for

15 while c^k-1≠? do

16 （204號 生成 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號 （C^k-1）_i）/? 根據 k-1 階模式頻繁區域生成 k-1 階模式拓展區域*／

20 CROC （C）_i= generate_candidate_region（ C^k-1 ， ExtROC（204號 （C^k-1）_i）_i^? //根據 k-1 階拓展區域生成 k 階模式候選區域

21 （2 CPI（CROC（C）_i，C）= calculate_coarse_participation_in-（20號 dex（CROC（C）_i，C）/ /計算區域粗參與度

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

23 continue

24 else

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

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

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

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

4實驗

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

4.1實驗數據

4.1.1真實數據集

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

表1真實數據集的參數

4.1.2合成數據集

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

合成數據集1總共包含{A，B，C，D，E，F，G|六個特征，其中特征A、G的實例分布是全局的，其他特征的實例分布是局部的，模擬了重疊實例分布的情況，特征A、G將與其他特征形成區域并置模式。特征B、C用于模擬檢測不同特征實例間交叉形成的區域頻繁模式B，C、 { A，B，C}、{B，C，G}和{A，B，C， 。在此合成數據集1中預構建的可能的區域頻繁并置模式為{A，B}、A，C}、{A，D}、{A，E}、{A，F}、{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頻繁區域結果有效性評價與分析

4.2.1頻繁區域結果的合理性分析

為驗證本文算法在生成頻繁區域階段的準確性和優越性，在真實數據集中進行了帶頻繁區域的并置模式挖掘。圖7展示了石林縣喀斯特地貌天然林保護區數據集上的挖掘結果（見電子版）。

a）數據與模式說明。在數據集中選擇特征Ab（云南松）、Af（桉樹）Ar（柏木）組成模式 {Ab，Af，Ar} 。這三種樹木分別適應不同的氣候條件：云南松適應高海拔和干燥環境，柏木常見于溫潤氣候，按樹因耐旱性和快速生長在多種環境中廣泛種植。盡管適應性不同，它們在云南的多樣化氣候條件下可能共存。

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

c）生態意義。頻繁區域表明這些樹種可能共存于特定生態條件下，例如適中的氣候、土壤PH值和養分水平。這些區域不僅反映了生態系統的獨特性，也可作為監測和評估生態系統健康的重要指標。實驗結果顯示，本文算法生成的頻繁區域與特征實例分布具有較高的一致性，有效體現了區域生態特征。

4.2.2帶頻繁區域的并置模式挖掘結果的比較

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

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

對于全局頻繁模式，multi-level無法識別其頻繁區域，而PROC-Col可以有效挖掘這些模式的頻繁區域，且其參與度接近全局參與度，顯示PROC-Col更準確有效，能夠更好地揭示數據特征。

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

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

由表3可以看出，multi-level的大部分并置模式的PI幾乎都趨向于1，相比之下，表3所示的PROC-Col的挖掘結果的PI值更加具有區分度。這是因為multi-level得到并置模式的頻繁區域在研究區域內通常是隨機分布的，具有面積小、子區域多的特點。相對來說，PROC-Col生成的頻繁區域面積大、數量適中。

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

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

從表4的結果可以看出，PROC-Col在低頻繁閾值和高頻繁閾值下都能正確挖掘出合成數據集中預設的帶頻繁區域的并置模式，而multi-level在低頻繁閾值和高頻繁閾值下可能無法檢測部分帶頻繁區域的并置模式。

以區域并置模式 {A，B，C} 為例，圖9（a）（b）分別展示了使用PROC-Col和multi-level對該模式的頻繁區域挖掘結果。圖9（b）中，由于對子模式頻繁區域進行并集運算，multi-level錯誤地將一些僅有模式 {A，C} 行實例存在，而無模式 {A，B，C} 行實例存在的區域劃為了模式 {A，B，C} 的頻繁區域。圖9（a）中，PROC-Col有效規避了這一問題，使挖掘出的模式 {A，B，C} 的頻繁區域很好地貼合實際上的頻繁區域，從而提高了挖掘結果的準確度。

4.2.3頻繁區域的精確度比較

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

精確度的值越大，表示算法挖掘出的頻繁區域與并置模式的真實分布區域越接近，誤差越小，說明挖掘結果更符合實際分布情況。因此，精確度可以作為評估算法準確性和結果合理性的重要指標。

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

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

表5兩種算法在石林縣喀斯特地貌天然林保護區數據集中的挖掘結果精確度比較

4.3算法可擴展性評價與分析

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

4.3.1實例數量的影響

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

圖10展示了四種算法在不同實例數量條件下的運行時間。分析發現，隨著實例數量的增加，算法間的性能差異也隨之增大。在合成數據集和真實數據集上，multi-level由于需要首先挖掘全局頻繁的并置模式，所以其運行時間相對較長。具體來說，multi-level需要額外的時間來處理全局頻繁模式，這在實例數增多時尤為明顯。而對于PROC-Col-base，隨著實例數量的增加，所需處理的表實例增多，相應地，確定模式存在區域所需的時間也會增加。對于PROC-Col-nCPI，計算區域參與度所需的時間隨實例數量增多而延長。相比之下，本文算法PROC-Col在處理增加的實例數時顯示出更佳的效率。總體上看，PROC-Col的運行時間大約是multi-level的一半。

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

4.3.2特征數量的影響

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

盡管如此，使用了替代策略的PROC-Col-nCPI和完整的PROC-Col在特征數量增加時的執行時間雖然有所上升，但仍然低于PROC-Col-base和multi-level的執行時間。這表明，盡管特征數量的增加帶來更多的計算負擔，但通過優化的策略如替代策略和區域粗參與度計算，這些方法依然能有效地提升算法整體的效率，尤其在處理大規模特征集時更顯優勢。

5結束語

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

未來可以進一步優化算法在大規模數據集上的計算效率，并探索在不同類型的空間數據集（如三維空間或時空數據）中的應用。同時，還可以嘗試結合深度學習和其他智能算法，提升空間并置模式挖掘的精度和可擴展性，從而在更多實際應用場景中發揮作用，如城市規劃、生態監測和氣象預測等領域。

參考文獻：

[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]．計算機應用研究，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.