極小負co-location 模式及有效的挖掘算法

王光耀，王麗珍，楊培忠，陳紅梅

云南大學信息學院，昆明 650504

隨著空間數據信息的爆炸式增長，從大量空間數據中發現有價值的信息成為一項重要的任務。空間co-location（并置）模式是空間特征的一個子集，它們的實例在空間中頻繁關聯。例如，醫院和藥店經常并置出現，根瘤菌時常長在豆科植物旁。空間colocation 模式挖掘在地理信息系統、圖像數據、公共交通領域等許多帶有空間屬性的領域中有著非常廣泛的應用。

盡管已有大量有關正co-location 模式挖掘的算法，但負co-location 模式挖掘方面的研究成果卻是稀有的。原因是負關聯規則挖掘、負序列模式挖掘以及正co-location 模式挖掘的算法都難以被簡單地運用到負co-location 模式挖掘中，并且挖掘出的負colocation 模式數量具有組合爆炸的特點，因此研究負co-location 模式的挖掘具有極大的難度。

實際上，在空間數據挖掘中，負co-location 模式在許多應用中也是極其重要的，它表現了某些特征之間較少地出現在一起，但它們之間有著較強的負相關性，包含了非常有價值的信息，因此挖掘負colocation 模式具有十分重要的意義。植物學家不僅對共生植被感興趣，同時對植被的相克關系（負相關性）也感興趣，在園林設計中，需要注意樹種之間的相克關系；在植樹造林時，需要充分考慮植被的相克現象才能趨利避害，例如：通過植被數據負相關性挖掘，可得到柏樹和蘋果樹、柏樹與榆樹具有較強的負相關性；利用植被相克的原理，以植被的汁液為原料，可提取無毒、無殘留和無副作用的高效植物除草劑或殺蟲劑，例如：通過從植被及動物分布數據中可挖掘到豆蕪青與棉花具有較強的負相關性，通過進一步的研究可從棉花中提取相應的化學物質作為對豆蕪青的殺蟲劑；在養殖業和畜牧業中，考慮動植物間的相克關系，可避免不必要的生病或死亡。

為了提高頻繁負co-location 模式挖掘結果的可用性，挖掘出較少的、具有代表性的、可推導出所有頻繁負co-location 模式的模式是非常有意義的。因此，本文提出了極小負co-location 模式新概念。

主要貢獻包括：

（1）在嚴格定義負co-location 模式的基礎上，分析了負co-location 模式所具有的“向上包含”性質。基于此，提出了極小負co-location 模式新概念，證明了極小負co-location 模式集可推導出所有頻繁負colocation 模式。

（2）基于負co-location 模式的“向上包含”性質，提出一個有效的極小負co-location 模式挖掘算法及頻繁負co-location 模式的推導算法。3 個剪枝策略的提出，有效地提高了負co-location 模式挖掘的效率。

（3）在真實和合成數據集上進行了廣泛的實驗，并與現有算法進行了對比，證明了本文提出的算法挖掘出極小負co-location 模式的正確性及高效性。解決了現有負co-location 模式挖掘算法耗時長、挖掘結果數量巨大等問題。

1 相關工作

近年來許多學者對空間co-location 模式挖掘的理論和算法進行了一系列深入的研究，并取得了豐碩的成果[1-9]。文獻[1]提出了將最小參與率作為colocation 模式的有趣性度量指標，并給出了一種基于完全連接的頻繁co-location 模式挖掘算法；文獻[2]提出了一種基于部分連接的算法，減少了完全連接算法中表實例連接的巨大開銷；文獻[3]提出了一種無連接的算法，基于星型鄰居擴展，更好地優化了在表實例的連接過程的開銷的問題。

Wang 等人在空間co-location 模式挖掘領域進行了一系列進一步的研究，文獻[4]提出了CPI-tree（colocation pattern instance tree）算法，以樹形結構物化空間鄰近關系；文獻[5]提出了iCPI-tree（improved colocation pattern instance tree）算法，進一步優化了基于CPI-tree的挖掘過程。

co-location 模式挖掘當下熱點為模糊co-location模式挖掘、并行co-location 模式挖掘、高效用colocation 模式挖掘和帶稀有特征的co-location 模式挖掘等。文獻[6]提出了一種基本模糊co-location 模式挖掘算法，并提出了基于網格的距離計算和剪枝候選模式兩種優化算法；文獻[7]使用并行算法挖掘colocation 模式；文獻[8]定義了特征在模式中的效用權重，提出了基于特征效用參與率的高效用co-location模式挖掘算法；文獻[9]提出了帶稀有特征的colocation 高效挖掘算法。

在co-location 模式的緊湊表示研究中，Wang 等人提出了許多有效的方法：文獻[10]提出了閉頻繁co-location 模式的有效挖掘算法；文獻[11]提出了頻繁co-location 模式的冗余縮減算法；文獻[12]提出了空間極大co-location 模式挖掘算法等。

以上文獻雖在co-location 模式挖掘領域進行了大量的研究，但均只適用于正co-location 模式。在負規則的研究中，有許多學者提出了相關的挖掘算法，但多用于關聯規則及序列模式的挖掘中。文獻[13]中對傳統關聯進行了擴展，提出了負關聯規則的概念，并定義了興趣度度量，提出了有效的剪枝策略；文獻[14]給出了負序列模式的定義和一些約束條件，提出了一種新的挖掘負序列模式的方法；文獻[15]提出了一個基于集合理論的負序列模式挖掘的算法e-NSP（efficient negative sequential pattern），該算法無需對數據庫進行重新掃描，從而有效地識別負序列模式；文獻[16]提出了一種快速的負序列模式挖掘算法（fast negative sequential patterns，f-NSP），使用位圖來存儲正序列模式的信息。

負關聯規則及負序列挖掘的算法適用于事務數據庫，而在空間數據庫中負模式的研究是稀有的。基于正co-location 模式挖掘的算法，Jiang 等人[17]首次提出了負co-location 模式的概念及負co-location 模式的有趣性度量指標，設計了一個空間正負co-location模式的挖掘算法，稱為PNCP（positive and negative colocation patterns）算法，并基于負co-location 模式的向上擴展性對候選負co-location 模式進行剪枝，該算法可挖掘出頻繁的正負co-location 模式。根據負colocation 模式參與度的定義，負co-location 模式不具備類似于正co-location 模式的向下閉合性。現有的負co-location 模式挖掘算法中，基于非頻繁模式來定義的負模式，導致從數據集中挖掘出的負模式結果數量巨大，在挖掘的過程中極其耗時。用戶在數量巨大的頻繁負co-location 模式中找出感興趣的信息是困難的。

基于PNCP 算法挖掘出的頻繁負co-location 模式數量巨大且挖掘過程耗時長等問題，本文提出了一個挖掘極小負co-location 模式的有效算法，極小負co-location 為頻繁負co-location 模式的一種緊湊表示，可有效壓縮挖掘結果，提高挖掘效率。

2 形式化定義及分析

在空間數據庫中，不同的空間特征代表不同類型的空間對象，例如某種類型的植被、某種功能的建筑等。給定一個空間特征的集合F={f1,f2,…,fm}，每個空間特征都具有一組與其對應的空間實例分布在空間中不同的位置，與F對應的空間實例集合S={s1,s2,…,sn}。其中每個si(1 ≤i≤n)都是由<實例所屬特征，實例號，空間位置>三個部分組成。如圖1所示的空間實例集中，分別有A、B、C、D四個特征，其中A1 表示特征A的第一個實例。給定一個空間鄰近距離閾值d，若實例si和sj(1 ≤i≤n,1 ≤j≤n)的距離小于閾值d，則稱實例si和sj滿足空間鄰近關系R，表示為R(si,sj)。如圖1 所示的空間實例集，若兩個實例間使用實線連接，則表示這兩個實例滿足鄰近關系R。

Fig.1 A spatial instance set圖1 一個空間實例集

一個空間co-location 模式c是一組空間特征的子集，co-location 模式c的長度稱為此co-location 模式的階，即co-location 模式里空間特征的個數，記作size(c)=|c|，例如{A,B,C}是一個三階的模式。一個k階co-location 模式c={f1,f2,…,fk}(c?F)，一組空間實例的集合I={s1,s2,…,sk}(I?S) 且{R(si,sj)|1 ≤i≤k,1 ≤j≤k} 。若I包含了co-location 模式c中的所有特征，并且I中沒有任何一個子集可以包含c中的所有特征，那么I被稱為c的一個行實例，co-location 模式c的所有行實例的集合稱為表實例，記為table_instance(c)。

為了衡量一個空間co-location 模式的頻繁性（有趣程度），在co-location 模式挖掘中使用參與度度量一個模式的頻繁（有趣）程度，而一個co-location 模式的參與度取決于該模式中各個特征的參與率。在colocation 模式c中，空間特征fi(1 ≤i≤k)的參與率表示為PR(c,fi)，它是fi的實例在空間co-location 模式c的表實例中不重復出現的實例個數與fi總實例個數的比率。即：

其中，π是關系的投影操作。co-location 模式c={f1,f2,…,fk}的參與度PI(c)是co-location 模式c的所有空間特征的PR值中的最小值，即：

當用戶給定一個參與度閾值min_prev，若PI(c)≥min_prev，則稱c為頻繁的co-location 模式。

例1如圖1 所示，包含4 個空間特征A、B、C和D，A有5 個實例，B有5 個實例，C有4 個實例，D有4 個實例。給定參與度閾值min_prev=0.5。co-location模式{A,B}的表實例為{{A1,B1},{A2,B2},{A3,B4},{A4,B5},{A5,B1}}，參與度為min(PR({A,B},A),PR({A,B},B))=，則co-location模式{A,B}是頻繁的。

引理1（反單調性）參與率（PR）和參與度（PI）隨著co-location 模式階的增大單調遞減。

參與率和參與度的反單調性證明可參見文獻[18]。給定兩個co-location 模式I和I′，模式I′是模式I的子集，即I′?I，對于模式I′中的每個特征fi∈I′，都有PR(I′,fi)≥PR(I,fi) 。根據參與度的定義，可得到PI(I′)≥PI(I)。

在非頻繁的co-location 模式中，某些特征之間存在著較強的負相關性，而這類模式也具有很大的挖掘價值，例如松樹與接骨木，柏樹與桔樹都具有相克現象。

定義1（負co-location 模式）一個帶有負項特征的co-location 模式，稱為負co-location 模式，一般記為T=X?，X是正項特征的集合，是負項特征的集合，且≥1，X?Y=?。

若一個co-location 模式中不含有負項特征，則稱該模式為正co-location 模式。

定義2（候選負co-location模式）一個負co-location模式T=X?，如果滿足PI(X)≥min_prev，PI(Y)≥min_prev，且PI({X?Y})

含有k個正項特征的候選負co-location 模式T=X?的參與度nPI(T)的計算公式表示如下[17]：

其中，PR({X?Y},xi)是特征xi(xi∈X)在模式X?Y中的參與率。負co-location 模式的參與度與其正項特征的參與率有著密切的關系。

定義3（頻繁負co-location 模式）[17]給定一個候選負co-location 模式T=X?，且用戶給定最小參與度閾值為min_prev，若滿足nPI(T)≥min_prev，則稱候選負co-location 模式T=X?為頻繁負co-location模式。

在文獻[17]的定義中，從非頻繁的模式中挖掘出負co-location 模式X?，其要求X和Y都是頻繁的。此條件可極大地減少無趣的負模式產生，使挖掘出的結果更有意義。將模式X與模式Y不同時出現的概率定義為負模式X?的參與度，合理地反映出了模式X與模式Y之間的負相關性。

例3如圖1 所示，若設置min_prev=0.5，模式{A}和模式{C}是頻繁的正co-location 模式，且PI({A,C})=0.25

基于正co-location 模式參與率的反單調性及負co-location 模式參與度的定義，在負co-location 模式挖掘中，找出具有可推導出所有頻繁負co-location 模式的緊湊表示，同時高效地挖掘出所有頻繁負colocation 模式是有意義的。

引理2給定一個空間候選負co-location 模式T=X?，若存在X=X1?X2，且X1?和X2?是頻繁的負co-location 模式，那么候選負co-location 模式T=X?也是頻繁的。

證明給定兩個頻繁負co-location 模式X1?和X2?，一個候選負co-location 模式T=X?，且X=X1?X2，對于任意的ai∈X1，bi∈X2，根據引理1，可得到：

引理得證。

引理3給定一個頻繁負co-location模式T=X?，若存在Y?Y′且Y′是頻繁的正co-location 模式，那么負co-location 模式T′=X?也是頻繁的。

證明給定一個頻繁負co-location模式T=X?，存在Y?Y′且PI(Y′)≥min_prev，對于任意的ai∈X，根據引理1，都有：

PR({X?Y},ai})≥PR({X?Y′},ai)

根據負模式的參與度定義，有：

min(1-PR({X?Y′},ai))≥min(1-PR({X?Y},ai}))

即：

nPI(X?=min(1-PR({X?Y′},ai))≥min_prev

引理得證。

引理4給定含k個正項特征的候選負co-location模式T=X?，若頻繁正co-location 模式X的最大參與率滿足max(PR({X},x1),PR({X},x2),…,PR({X},xk))≤1-min_prev(xi∈X)，則候選負co-location 模式T=X?是頻繁的。

證明給定含有k個正項特征的候選負co-location模式T=X?，若滿足：

max{PR({X},x1),PR({X},x2),…,PR({X},xk)}≤1-min_prev

根據引理1 可得：

引理得證。

由引理2 和引理3，看到了負co-location 模式具有一種“向上包含”性質，該性質類似頻繁項集挖掘中的“向下閉合”性質。為此，本文提出了極小負colocation 模式新概念。

定義4（極小負co-location 模式）給定一個頻繁負co-location 模式T=X?，存在X′?X″=X，Y′?Y，且X′、X″和Y′均為頻繁的正co-location 模式。若負co-location 模式X′?和X″?不同時為頻繁負colocation 模式，且X?也不是頻繁負co-location 模式，則稱模式T=X?為極小負co-location 模式。

引理5通過極小負co-location 模式可推導出所有頻繁負co-location 模式。

證明給定一個非極小負co-location 模式的頻繁負co-location 模式T=X?。若該模式不能由極小負co-location 模式推導得到，則該模式需同時滿足如下條件：

（1）對于模式Y的任一子集Y′，負co-location 模式X?′均不是頻繁co-location 模式；

（2）對于X=X′?X″，模式X′?和X″?不能同時為頻繁負co-location 模式。

由定義4 可知，滿足上述兩個條件的頻繁負colocation 模式為極小負co-location 模式，與給定條件沖突，故極小負co-location 模式可推導出所有頻繁負co-location 模式。

引理得證。

例4如圖1 所示的實例分布中，給定最小支持度閾值min_prev=0.5，極小負co-location 模式及被其“向上包含”的頻繁負co-location 模式如表1 所示。

由表1 可知，在這個例子中，頻繁負co-location模式共有20 個，而極小負co-location 模式僅為10 個。

Table 1 Minimal negative patterns and their contained negative patterns表1 極小負模式及其包含的負模式

3 相關算法

本章給出了極小負co-location模式挖掘算法和基于極小負co-location 模式推導出所有頻繁負colocation模式的算法，具體步驟分別見算法1和算法2。

算法1挖掘極小負co-location 模式

算法2基于極小負co-location 模式推導所有頻繁負co-location 模式

極小負co-location 模式挖掘算法包含如下五步：

（1）計算所有實例的鄰居關系NT，使用任一已有算法挖掘頻繁正co-location 模式，并存儲每個模式的最大參與率。

（2）由低階模式到高階模式，將頻繁正co-location模式通過兩兩組合的方式產生候選負co-location模式。

（3）使用引理2、引理3 及引理4 對該候選模式進行剪枝，并識別候選模式是否為極小負co-location模式。

（4）若該候選模式未被剪枝，則掃描實例的鄰居關系NT確定其表實例。

（5）通過表實例計算出該候選負co-location 模式的參與度，若該模式參與度大于用戶給定參與度閾值，則其為極小負co-location 模式。

具體過程見算法1。

算法1 中，首先掃描一次空間實例分布數據，計算每個實例的鄰居，構成鄰居關系集合NT。

基于鄰居關系集合NT，通過任一已有算法挖掘出所有頻繁正co-location 模式，同時保存所有頻繁正co-location 模式的最大參與率。

將所有頻繁正co-location 模式按字典序排序，字典序保證了在計算高階模式時，該模式的低階子集已被計算。通過頻繁正co-location 模式兩兩組合的方式形成候選負co-location 模式。根據候選負colocation 模式的定義，當頻繁正co-location 模式數量增加時，候選負co-location 模式數量也隨之增加。

若候選負co-location 模式未被剪枝，則對鄰居關系集合進行掃描，確定該模式的表實例，通過表實例計算出該模式的參與度nPI，并判斷該模式是否為極小負co-location 模式。

本算法的時間復雜度與候選模式數相關，而候選模式數與距離閾值、參與度閾值、特征數、實例數等相關，下面的分析從假設正頻繁模式數開始。假設頻繁正co-location 模式個數為k，則循環次數為，則可生成個候選負co-location 模式，該過程的時間復雜度為O(k2)。

若候選負co-location 模式未被剪枝，則需通過掃描鄰居關系NT確定該模式表實例，并通過表實例計算該模式的參與度nPI，從而確定其是否為極小負co-location 模式。假設有m個候選負co-location模式未被剪枝，且其平均長度為Navg，則確定m個候選負co-location 模式表實例的時間復雜度為m×Tfilter_clique_inst(Navg)，其中Tfilter_clique_inst(Navg)為確定一個Navg階模式的表實例所用時間，這也是算法最耗時的部分，剪枝引理的意義就在于通過提前剪枝減少表實例的計算。

引理5 證明了基于挖掘到的極小負co-location模式可以推導出所有頻繁負co-location 模式，算法2給出了推導過程。

算法2 中，通過將頻繁正co-location 模式兩兩組合生成候選負co-location 模式，若候選負co-location模式滿足引理2 或引理3，則該模式為頻繁負colocation 模式，并將該模式加入集合中。

在算法2 的過程2 及2.1 中，假設頻繁正colocation 模式個數為k，則循環次數為則可生成個候選負co-location 模式，該過程的時間復雜度為O(k2) 。算法2 的過程2.1.1 及2.1.2 為查詢及判斷，在算法的存儲結構中使用了哈希表的形式，故該過程的時間復雜度為O(1)。

在給定的空間數據集中，參與度閾值min_prev一定時，距離閾值d越大，鄰居關系NT越多，挖掘到的頻繁正co-location 模式越多，階數越大，產生的頻繁負co-location 模式也越多。距離閾值d一定時，參與度閾值min_prev越小，挖掘到的頻繁正co-location模式越多，階數越大，掃描鄰居關系集合NT的次數越多，算法的運行時間越長，產生的頻繁負colocation 模式也越多。

現有的PNCP 算法中[17]，假設頻繁正co-location模式個數為k，通過兩兩組合產生候選負co-location模式的方式，可組合產生個候選負co-location模式，其時間復雜度為O(k2)。假設有l個候選負co-location模式未被剪枝，且其平均長度為Navg，則確定l個候選負co-location模式表實例的時間復雜度為l×Tfilter_clique_inst(Navg)，其中Tfilter_clique_inst(Navg)為確定一個Navg階模式的表實例所用時間。在負colocation 模式挖掘中，查找模式的表實例為最耗時的部分且頻繁的負co-location 模式數量巨大，本文在剪枝效率上有較大提升，算法1 的時間復雜度中未被剪枝的候選模式數m?l，故本文算法效率優于現有PNCP 算法。

算法1 基于引理2 及引理3，通過判斷候選模式是否滿足這兩個引理，只有都不滿足且該候選模式的參與度大于參與度閾值時，該候選模式才為極小負co-location 模式；同樣，算法2 基于極小負colocation 模式，若候選模式滿足引理2 或引理3，則該模式為頻繁的負co-location 模式。引理5 基于引理2及引理3 證明了極小負co-location 模式推導所有頻繁負co-location 模式的完備性。

4 實驗與分析

目前，僅有文獻[17]的工作是挖掘頻繁負colocation 模式的，為評估本文提出的極小負co-location模式的壓縮率和基于極小負co-location 模式挖掘所有頻繁負co-location 模式方法的有效性，在真實和合成數據集上將本文中提出的算法1 及算法2 和文獻[17]中的PNCP 算法進行了比較（https://github.com/GuangyaoWang/e-NCP）。由引理5 及實驗證實，算法2 中，由極小負co-location 模式推導出的頻繁負colocation 模式與PNCP 算法挖掘得到的頻繁負colocation 模式數量一致。所有算法都采用Java 編寫，實驗環境為Win10 系統，Core i7 CPU 和16 GB 內存的計算機。

4.1 真實數據集上的實驗與分析

在實驗中選取的真實數據集為云南貢山某區域的植被分布數據，數據分布圖如圖2 所示，該數據集包含箭竹、冷杉、榿木、鐵杉、云南松等25 個樹種，共有13 349 個植株實例。考慮參與度閾值和距離閾值的變化，比較極小負co-location 模式的壓縮率、算法1與PNCP 算法的剪枝率和3 個算法的運行效率。

Fig.2 A vegetation distribution data set圖2 一個植被分布數據集

4.1.1 參與度閾值的變化

在本小節實驗中，均固定距離閾值d=1 500 m，設置參與度閾值由0.1 到0.6 進行實驗。

隨著參與度閾值的變化，算法1 挖掘出的極小負co-location 模式數量、算法2 推導出的頻繁負colocation 模式數量及PNCP 算法挖掘得到的頻繁負co-location 模式數量如圖3 中的柱狀圖所示，極小負co-location 模式的壓縮率如圖3 中的折線圖所示。當參與度閾值增大時，頻繁負co-location 模式數量有較大的減少趨勢，而極小負co-location 模式數量一直較少，并有較小的減少趨勢。由于頻繁負co-location 模式數量的減少，極小負co-location 模式“向上包含”的模式數量也隨之減少，進而壓縮率減少。不過，當參與度閾值為0.1 時，極小負co-location 模式數量的壓縮率高達80%。

Fig.3 Effect of min_prev on the number of negative patterns in real data圖3 真實數據中參與度閾值對負模式數量的影響

算法1、算法2 與PNCP 算法隨著參與度閾值的變化，挖掘耗時如圖4 所示，算法1 的運行效率優于PNCP 算法，算法2 的運行耗時非常小。說明挖掘極小負co-location 模式，得到精簡的、用戶更易理解和使用的極小集合，再由極小負co-location 模式推導出所有頻繁負co-location 模式，其效率仍優于直接挖掘所有頻繁負co-location 模式的效率。從圖4 可以看到，當參與度閾值為0.1 時，算法1 的效率是PNCP 算法的4 倍。

Fig.4 Effect of min_prev on running time in real data圖4 真實數據中參與度閾值對運行時間的影響

算法1 與PNCP 算法隨著參與度閾值的變化，剪枝率如圖5 所示，隨著參與度閾值的增大，剪枝率出現了明顯的下降趨勢，當參與度閾值小于等于0.5時，算法1 的剪枝率均高于PNCP 算法，當參與度閾值大于0.5 時，由于在該閾值下引理4 的剪枝失效，兩種算法的剪枝率相同，該問題在本小節的討論中進行了詳細分析。特別地，當參與度閾值等于0.1 時，算法1 的剪枝率達到85%。

Fig.5 Effect of min_prev on pruning ratio in real data圖5 真實數據中參與度閾值對剪枝率的影響

4.1.2 距離閾值的變化

在本小節實驗中，均固定參與度閾值min_prev=0.1，設置距離閾值d由1 300 m 到1 800 m 進行實驗。

隨著距離閾值的變化，算法1 挖掘出的極小負co-location 模式數量、算法2 推導出的頻繁負colocation 模式數量及PNCP 算法挖掘得到的頻繁負co-location 模式數量如圖6 中的柱狀圖所示，極小負co-location 模式的壓縮率如圖6 中的折線圖所示。由柱狀圖可看出，隨著距離閾值的增大，導致了鄰居關系的增加，進而使頻繁負co-location 模式數量逐漸增加，而極小負co-location 模式數量沒有明顯的增加，頻繁負co-location 模式的增加使得極小負co-location模式壓縮率也隨著增加。從實驗發現，極小負colocation 模式的壓縮率均保持在80%以上。

Fig.6 Effect of d on the number of negative patterns in real data圖6 真實數據中距離閾值對負模式數量的影響

算法1、算法2 和PNCP 算法隨著距離閾值變化，挖掘耗時的變化如圖7 所示。PNCP 算法隨著距離閾值的增加，挖掘時間有較大幅度的上升趨勢，而算法1 則較為平緩，算法2 的運行耗時均處于極低的狀態，算法1 的運行時間均優于PNCP 算法。而當距離閾值取1 800 m 時，PNCP 算法的運行時間是算法1 的4 倍。

Fig.7 Effect of d on running time in real data圖7 真實數據中距離閾值對運行時間的影響

算法1 和PNCP 算法隨著距離閾值的變化，剪枝率如圖8 所示，隨著距離閾值增大，剪枝效率越來越高，算法1 的剪枝率明顯優于PNCP 算法，且算法1 的剪枝率均高于80%。

Fig.8 Effect of d on pruning ratio in real data圖8 真實數據中距離閾值對剪枝率的影響

4.2 合成數據集上的實驗與分析

在合成數據集上的實驗，使用的數據為6 個特征數為26，實例分布范圍為（20 000×20 000）的合成數據集，每個特征的實例數隨機產生，總實例數由50 000 到100 000。考慮實例數、參與度閾值及距離閾值的變化，分別對比極小負co-location 模式的壓縮率、3 個算法的運行耗時和算法1 與PNCP 算法的剪枝率。

4.2.1 實例數的變化

在本小節實驗中，均固定距離閾值d=170，參與度閾值min_prev=0.2，實例數由50 000 到100 000，在6 個合成數據集下進行實驗。

隨著實例數的變化，算法1 挖掘出的極小負colocation 模式數量、算法2 推導出的頻繁負co-location模式數量及PNCP 算法挖掘得到的頻繁負co-location模式數量如圖9 中的柱狀圖所示，極小負co-location模式壓縮率如圖9 中的折線圖所示。隨著實例數的增加，實例的分布密度逐漸增大，在同樣的距離閾值下產生的鄰居關系增多，使得挖掘的頻繁正colocation 模式數量增加，進而使得負co-location 模式數量也隨之增加。頻繁負co-location 模式數量有較大的增幅，而極小負co-location 模式數量較少且增幅較小，壓縮率基本維持在90%左右。

Fig.9 Effect of number of instances on the number of negative patterns in synthetic data圖9 合成數據中實例數對負模式數量的影響

算法1、算法2 和PNCP 算法隨著實例數的變化，挖掘耗時如圖10 所示。當實例數增大時，PNCP 算法的頻繁負co-location 模式挖掘時間呈現較大幅度的上升，而算法1 挖掘極小負co-location 模式的耗時上升趨勢較緩，算法2 的耗時極低，呈現小幅度上升趨勢。當實例數達到100 000 時，算法1 的運行時間僅為PNCP 算法運行時間的17%。

Fig.10 Effect of number of instances on running time in synthetic data圖10 合成數據中實例數對運行時間的影響

隨著實例數的增加，算法1 與PNCP 算法的剪枝率如圖11 所示。隨著實例數的增大，PNCP 算法和算法1 的剪枝率均呈現上升趨勢，由于合成數據為隨機生成，實例的位置分布不同，根據剪枝策略的條件，滿足剪枝條件的模式數量可能存在差異，故在實例數為80 000 的數據中，PNCP 算法的剪枝率有所下降。

4.2.2 參與度閾值的變化

本小節實驗在特征數為26，實例總數為80 000的合成數據集下進行實驗。均固定距離閾值d=170，設置參與度閾值由0.1 到0.6 進行實驗。

Fig.11 Effect of number of instances on pruning ratio in synthetic data圖11 合成數據中實例數對剪枝率的影響

隨著參與度閾值的變化，算法1 挖掘出的極小負co-location 模式數量、算法2 推導出的頻繁負colocation 模式數量及PNCP 算法挖掘得到的頻繁負co-location 模式數量如圖12 中的柱狀圖所示，極小負co-location 模式壓縮率如圖12 中的折線圖所示。當參與度閾值增大時，挖掘到的頻繁負co-location 模式數量明顯減少，極小負co-location 模式也逐漸減少，“向上包含”的模式數量逐漸減少，進而使得極小負co-location 模式的壓縮率由91%逐漸減小為26%。

Fig.12 Effect of min_prev on the number of negative patterns in synthetic data圖12 合成數據中參與度閾值對負模式數量的影響

算法1、算法2 和PNCP 算法隨著參與度閾值變化，挖掘耗時如圖13 所示。3 個算法的運行時間均隨著參與度閾值的增大呈現下降趨勢。當參與度閾值較低時，PNCP 算法的挖掘耗時長，算法1 耗時明顯優于PNCP 算法，當參與度閾值較高時，由于引理4的剪枝失效，算法1 與PNCP 算法的挖掘的耗時相同。算法2 的挖掘耗時均處于較低水平。比起PNCP 算法，算法1 將耗時都調整到較低的水平，當參與度閾值為0.1時，算法1的運行時間較PNCP算法提高了84%。

Fig.13 Effect of min_prev on running time in synthetic data圖13 合成數據中參與度閾值對運行時間的影響

隨著參與度閾值的變化，PNCP 算法與算法1 的剪枝率如圖14 所示。隨著參與度閾值增大，挖掘出的頻繁負co-location 模式數量逐漸減少，故剪枝率也呈現下降趨勢，當參與度閾值為0.1 時，算法1 的剪枝率高達99%。

Fig.14 Effect of min_prev on pruning ratio in synthetic data圖14 合成數據中參與度閾值對剪枝率的影響

4.2.3 距離閾值的變化

本小節在特征數為26，實例數為90 000 的合成數據集下進行實驗。均固定參與度閾值min_prev=0.3，設置距離閾值由150 到200 進行實驗。

隨著距離閾值的變化，算法1 挖掘出的極小負co-location 模式數量、算法2 推導出的頻繁負colocation 模式數量及PNCP 算法挖掘得到的頻繁負co-location 模式數量如圖15 中的柱狀圖所示，極小負co-location 模式壓縮率如圖15 中的折線圖所示。隨著距離閾值的增大，頻繁負co-location 模式數量有大幅的增長，而極小負co-location 模式數量增長較緩慢且壓縮率較高并有小幅的增長，極小負co-location 模式的壓縮率均高于80%。

Fig.15 Effect of d on the number of negative patterns in synthetic data圖15 合成數據中距離閾值對負模式數量的影響

算法1、算法2 和PNCP 算法隨著距離閾值變化，挖掘耗時如圖16 所示。當距離閾值增大時，PNCP 算法呈現較快的上升趨勢，算法1 呈現較緩的上升趨勢，而算法2 的耗時均維持在極低的水平。

Fig.16 Effect of d on running time in synthetic data圖16 合成數據中距離閾值對運行時間的影響

隨著距離閾值的變化，PNCP 算法與算法1 的剪枝率如圖17 所示，隨著距離閾值的增大，兩個算法的剪枝率均呈現上升趨勢，算法1 的剪枝率均高于PNCP 算法。

Fig.17 Effect of d on pruning ratio in synthetic data圖17 合成數據中距離閾值對剪枝率的影響

本文在真實及合成數據集上進行了大量實驗，實驗均表明本文算法優于現有的PNCP 算法。本文在挖掘極小負co-location模式的基礎上推導出所有頻繁負co-location模式，推導過程耗時極低，使用本文算法挖掘出所有頻繁負co-location模式仍是高效的。

近年許多學者提出了高效的正co-location 模式的挖掘方法，由于本文旨在提高負co-location 模式挖掘效率，且使用不同的正co-location 模式挖掘算法的運行時間不盡相同，故本文實驗的運行時間僅為挖掘負co-location 模式的時間。

討論：在參與度閾值變化的實驗中，當參與度閾值大于等于0.5 時，算法1 與PNCP 算法的運行時間及剪枝率相同。當參與度閾值等于0.5時，由引理4可得：

給定一個候選負co-location 模式T=X?，頻繁正co-location 模式X的最大參與率滿足max(PR({X},x1),PR({X},x2),…,PR({X},xk))≥0.5。使用引理4 的剪枝條件為max(PR({X},x1),PR({X},x2),…,PR({X},xk))≤0.5。根據以上條件，只有當頻繁正co-location 模式X中所有特征的參與率均為0.5 時，該剪枝才能生效，而這類模式在挖掘過程中是極其罕見的，因此與PNCP 算法相比，運行效率并未提高。同理可得，當參與度閾值大于0.5 時，該剪枝條件無法生效，故PNCP 算法與算法1 的運行時間相同。

在負co-location 模式挖掘中，隨著參與度閾值的增大，挖掘出的模式數量呈現極大程度的下降，從實驗的運行時間也可看出，在參與度閾值較低時時間耗費是巨大的。當參與度閾值小于0.5時，負co-location模式的挖掘結果數量非常巨大，剪枝策略運用到這類情況下具有重要的意義。

5 結束語

由于負co-location 模式自身的特點，現有的負關聯規則、負序列等挖掘算法難以直接運用到負colocation 模式挖掘中來。本文提出極小負co-location模式新概念，研究了極小負模式與頻繁負模式的關系、負模式挖掘的有效剪枝策略等，從而設計了有效的算法來挖掘極小負co-location 模式，進而由極小負colocation 模式推導出所有頻繁負co-location 模式。在真實和合成數據集上進行了廣泛的實驗，與現有負colocation模式挖掘算法在效果及效率上進行了比較，驗證了其正確性及高效性。在未來工作中將會考慮基于模糊集論方法研究負co-location 模式的挖掘等。