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

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

云南大學(xué)信息學(xué)院，昆明 650504

隨著空間數(shù)據(jù)信息的爆炸式增長，從大量空間數(shù)據(jù)中發(fā)現(xiàn)有價值的信息成為一項重要的任務(wù)?？臻gco-location（并置）模式是空間特征的一個子集，它們的實例在空間中頻繁關(guān)聯(lián)。例如，醫(yī)院和藥店經(jīng)常并置出現(xiàn)，根瘤菌時常長在豆科植物旁?？臻gcolocation 模式挖掘在地理信息系統(tǒng)、圖像數(shù)據(jù)、公共交通領(lǐng)域等許多帶有空間屬性的領(lǐng)域中有著非常廣泛的應(yīng)用。

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

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

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

主要貢獻(xiàn)包括：

（1）在嚴(yán)格定義負(fù)co-location 模式的基礎(chǔ)上，分析了負(fù)co-location 模式所具有的“向上包含”性質(zhì)?；诖?，提出了極小負(fù)co-location 模式新概念，證明了極小負(fù)co-location 模式集可推導(dǎo)出所有頻繁負(fù)colocation 模式。

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

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

1 相關(guān)工作

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

Wang 等人在空間co-location 模式挖掘領(lǐng)域進(jìn)行了一系列進(jìn)一步的研究，文獻(xiàn)[4]提出了CPI-tree（colocation pattern instance tree）算法，以樹形結(jié)構(gòu)物化空間鄰近關(guān)系；文獻(xiàn)[5]提出了iCPI-tree（improved colocation pattern instance tree）算法，進(jìn)一步優(yōu)化了基于CPI-tree的挖掘過程。

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

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

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

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

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

2 形式化定義及分析

在空間數(shù)據(jù)庫中，不同的空間特征代表不同類型的空間對象，例如某種類型的植被、某種功能的建筑等。給定一個空間特征的集合F={f1,f2,…,fm}，每個空間特征都具有一組與其對應(yīng)的空間實例分布在空間中不同的位置，與F對應(yīng)的空間實例集合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滿足空間鄰近關(guān)系R，表示為R(si,sj)。如圖1 所示的空間實例集，若兩個實例間使用實線連接，則表示這兩個實例滿足鄰近關(guān)系R。

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

一個空間co-location 模式c是一組空間特征的子集，co-location 模式c的長度稱為此co-location 模式的階，即co-location 模式里空間特征的個數(shù)，記作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的表實例中不重復(fù)出現(xiàn)的實例個數(shù)與fi總實例個數(shù)的比率。即：

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

當(dāng)用戶給定一個參與度閾值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（反單調(diào)性）參與率（PR）和參與度（PI）隨著co-location 模式階的增大單調(diào)遞減。

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

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

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

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

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

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

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

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

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

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

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

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

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

引理得證。

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

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

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

根據(jù)負(fù)模式的參與度定義，有：

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

即：

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

引理得證。

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

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

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

根據(jù)引理1 可得：

引理得證。

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

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

引理5通過極小負(fù)co-location 模式可推導(dǎo)出所有頻繁負(fù)co-location 模式。

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

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

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

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

引理得證。

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

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

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

3 相關(guān)算法

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

算法1挖掘極小負(fù)co-location 模式

算法2基于極小負(fù)co-location 模式推導(dǎo)所有頻繁負(fù)co-location 模式

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

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

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

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

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

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

具體過程見算法1。

算法1 中，首先掃描一次空間實例分布數(shù)據(jù)，計算每個實例的鄰居，構(gòu)成鄰居關(guān)系集合NT。

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

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

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

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

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

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

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

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

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

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

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

4 實驗與分析

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

4.1 真實數(shù)據(jù)集上的實驗與分析

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

Fig.2 A vegetation distribution data set圖2 一個植被分布數(shù)據(jù)集

4.1.1 參與度閾值的變化

在本小節(jié)實驗中，均固定距離閾值d=1 500 m，設(shè)置參與度閾值由0.1 到0.6 進(jìn)行實驗。

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

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

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

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

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

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

4.1.2 距離閾值的變化

在本小節(jié)實驗中，均固定參與度閾值min_prev=0.1，設(shè)置距離閾值d由1 300 m 到1 800 m 進(jìn)行實驗。

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

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

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

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

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

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

4.2 合成數(shù)據(jù)集上的實驗與分析

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

4.2.1 實例數(shù)的變化

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

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

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

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

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

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

4.2.2 參與度閾值的變化

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

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

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

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

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

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

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

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

4.2.3 距離閾值的變化

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

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

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

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

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

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

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

本文在真實及合成數(shù)據(jù)集上進(jìn)行了大量實驗，實驗均表明本文算法優(yōu)于現(xiàn)有的PNCP 算法。本文在挖掘極小負(fù)co-location模式的基礎(chǔ)上推導(dǎo)出所有頻繁負(fù)co-location模式，推導(dǎo)過程耗時極低，使用本文算法挖掘出所有頻繁負(fù)co-location模式仍是高效的。

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

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

給定一個候選負(fù)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。根據(jù)以上條件，只有當(dāng)頻繁正co-location 模式X中所有特征的參與率均為0.5 時，該剪枝才能生效，而這類模式在挖掘過程中是極其罕見的，因此與PNCP 算法相比，運行效率并未提高。同理可得，當(dāng)參與度閾值大于0.5 時，該剪枝條件無法生效，故PNCP 算法與算法1 的運行時間相同。

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

5 結(jié)束語

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