空間亞頻繁co-location模式的主導(dǎo)特征挖掘

馬 董，陳紅梅，王麗珍，肖 清

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

0 引言

隨著基于位置的服務(wù)（Location Based Services，LBS）和空間數(shù)據(jù)采集技術(shù)的快速發(fā)展，數(shù)據(jù)挖掘從事務(wù)型數(shù)據(jù)庫(kù)擴(kuò)展到了空間數(shù)據(jù)庫(kù)。如何從海量、高維的空間數(shù)據(jù)中挖掘潛在、有趣的知識(shí)并指導(dǎo)決策變得尤其重要?？臻gco-location（并置）模式挖掘作為空間數(shù)據(jù)挖掘的重要研究方向，在環(huán)境保護(hù)［1］、城市計(jì)算［2］、公共交通［3］等領(lǐng)域具有廣泛的應(yīng)用?？臻gco-location模式是一組空間特征的子集，它們的實(shí)例在鄰域內(nèi)頻繁并置出現(xiàn)。例如，火車站附近往往有旅館；西尼羅河病毒往往發(fā)生在蚊子泛濫、飼養(yǎng)家禽的區(qū)域［4］。

通常，空間co-location 模式挖掘方法假設(shè)空間實(shí)例相互獨(dú)立，并采用空間實(shí)例參與到模式實(shí)例的頻繁性（參與率）度量其特征在模式中的重要性，采用空間特征的最小參與率（參與度）度量模式的有趣程度，忽略了空間特征間的某些重要關(guān)系（如主導(dǎo)關(guān)系）。例如，在co-location 模式｛藥店，醫(yī)院，花店｝中，各個(gè)特征的參與率分別為0.65、0.5和0.8。這一模式反映，藥店、醫(yī)院和花店頻繁出現(xiàn)在一起，其中花店出現(xiàn)的頻率最高，但是它不能揭示特征間的主導(dǎo)關(guān)系，即醫(yī)院主導(dǎo)了花店和藥店的出現(xiàn)，花店和藥店依賴于醫(yī)院而存在。挖掘co-lo?cation模式中的主導(dǎo)特征，可以揭示模式中的哪些特征具有主導(dǎo)地位，哪些特征受主導(dǎo)特征支配，進(jìn)而為深入剖析模式中特征間的其他重要關(guān)系（如因果關(guān)系、共生關(guān)系、排斥關(guān)系）奠定基礎(chǔ)，為基于co-location 模式的決策分析（如環(huán)境監(jiān)測(cè)、城市規(guī)劃、交通控制）提供支持。

現(xiàn)有主導(dǎo)特征co-location 模式挖掘方法是基于傳統(tǒng)頻繁模式及其團(tuán)實(shí)例模型，通過計(jì)算特征在頻繁模式及其子模式的參與率變化來識(shí)別主導(dǎo)特征及主導(dǎo)特征模式［5］，方法存在兩方面的不足：1）僅考慮空間實(shí)例參與到模式實(shí)例的比重變化，沒有考慮模式中空間特征間的相互影響；2）傳統(tǒng)頻繁模式的團(tuán)實(shí)例模型要求模式中的所有空間實(shí)例兩兩鄰近，然而主導(dǎo)關(guān)系反映的是主導(dǎo)對(duì)象與受支配對(duì)象間的關(guān)系，不強(qiáng)調(diào)受支配對(duì)象間的關(guān)系，也就是說，主導(dǎo)關(guān)系不要求空間實(shí)例形成團(tuán)，因而團(tuán)實(shí)例模型可能會(huì)忽略非團(tuán)的空間特征間的主導(dǎo)關(guān)系。

為解決傳統(tǒng)頻繁模式及其團(tuán)實(shí)例模型的不足，文獻(xiàn)［6-7］提出了空間亞頻繁co-location 模式及其星型實(shí)例模型，以挖掘具有更豐富空間關(guān)系的co-location 模式。亞頻繁模式及其星型實(shí)例模型關(guān)注中心實(shí)例與其周邊空間實(shí)例間的鄰近關(guān)系，而不要求周邊空間實(shí)例兩兩鄰近，這與主導(dǎo)關(guān)系一致。因此，本文基于星型實(shí)例模型，研究空間亞頻繁co-location 模式的主導(dǎo)特征挖掘，以更好地揭示空間特征間的主導(dǎo)關(guān)系，挖掘更有價(jià)值的主導(dǎo)特征模式。

本文主要面臨兩方面的挑戰(zhàn)：1）在亞頻繁co-location 模式及其星型實(shí)例模型下，如何合理地定義度量主導(dǎo)特征模式的指標(biāo)；2）面對(duì)更大的亞頻繁co-location 模式集合，如何高效地挖掘主導(dǎo)特征模式。本文主要工作包括：1）分析特征間的相互影響，定義了兩個(gè)度量特征主導(dǎo)性的指標(biāo)：特征貢獻(xiàn)度和特征影響比指數(shù)。2）提出有效的主導(dǎo)特征co-location 模式挖掘算法。3）在合成數(shù)據(jù)集和真實(shí)數(shù)據(jù)集上進(jìn)行大量實(shí)驗(yàn)，驗(yàn)證了所提算法的有效性以及主導(dǎo)特征模式的實(shí)用性。

1 相關(guān)工作

根據(jù)挖掘?qū)ο蟮牟煌臻gco-location 模式挖掘主要可以分為如下6類：

1）從確定空間數(shù)據(jù)中挖掘co-location 模式。這類模式挖掘主要以優(yōu)化挖掘過程、提高挖掘效率為目標(biāo)，如Join-based算法［8］、Partial-join 算法［9］、Join-less 算法［10］、CPI-tree（Co-location Pattern Instance tree）算 法［11］、iCPI-tree（improved CPI-tree）算法［12］、order-clique-based算法［13］。

2）從不確定性空間數(shù)據(jù)中挖掘co-location 模式。文獻(xiàn)［14］研究了從區(qū)間數(shù)據(jù)中挖掘co-location 模式；文獻(xiàn)［15］將Join-based 算法擴(kuò)展為UJoin-based 算法，挖掘位置不確定空間數(shù)據(jù)中的co-location 模式；文獻(xiàn)［16］通過對(duì)不確定性數(shù)據(jù)建模和處理，在分布式系統(tǒng)下定義了概率頻繁co-location 模式，并設(shè)計(jì)了高效的并行挖掘算法。

3）從帶約束的空間數(shù)據(jù)中挖掘co-location 模式。文獻(xiàn)［17］針對(duì)傳統(tǒng)模式挖掘算法在挖掘帶有稀有特征的空間數(shù)據(jù)集時(shí)，可能丟失有趣模式的問題，提出了最大參與率概念，并設(shè)計(jì)了maxPrune 算法挖掘帶稀有特征的co-location 模式；文獻(xiàn)［18］針對(duì)maxPrune 算法會(huì)挖掘到不頻繁模式的問題，提出了最小加權(quán)參與率概念，并設(shè)計(jì)了加權(quán)參與率WB（Weighted Basic）算法，挖掘帶有稀有特征的co-location 模式，同時(shí)去除非頻繁模式；文獻(xiàn)［6-7］考慮傳統(tǒng)團(tuán)實(shí)例模型可能導(dǎo)致有趣模式丟失的問題，提出了星型實(shí)例模型及空間亞頻繁co-location模式，并設(shè)計(jì)了PTBA（Prefix-Tree-Based Algorithm）和PBA（Partition-Based Algorithm）兩個(gè)高效的挖掘算法。

4）從模糊空間數(shù)據(jù)中挖掘co-location 模式。文獻(xiàn)［19］提出了模糊參與率和模糊參與度以挖掘模糊空間co-location 模式；文獻(xiàn)［20］將密度峰值聚類算法和模糊理論相結(jié)合來實(shí)現(xiàn)實(shí)例對(duì)簇的模糊劃分，并采用模糊團(tuán)代替?zhèn)鹘y(tǒng)團(tuán)以挖掘co-lo?cation 模式；文獻(xiàn)［21］基于模糊理論定義了模糊鄰近度，并利用模糊聚類算法進(jìn)行co-location模式挖掘。

5）效用co-location 模式挖掘。這類模式挖掘考慮了不同空間特征或不同空間實(shí)例的效用差異，能提高模式的實(shí)用性。文獻(xiàn)［22］考慮了不同空間實(shí)例的不同價(jià)值，將效用作為興趣度量，提出了一種演化空間數(shù)據(jù)上的高效用模式增量挖掘方法；文獻(xiàn)［23］將約束挖掘與制圖可視化相結(jié)合，提出了一種領(lǐng)域驅(qū)動(dòng)的co-location 挖掘算法；文獻(xiàn)［24］基于效用數(shù)據(jù)集確定特征實(shí)際參與權(quán)重，采用特征效用率和模式效用度度量高效用co-location模式。

6）主導(dǎo)特征co-location 模式挖掘。這類模式挖掘由文獻(xiàn)［5］提出，其基本思想是在基于團(tuán)實(shí)例模型的傳統(tǒng)頻繁co-lo?cation模式基礎(chǔ)上，進(jìn)一步考慮空間特征參與到模式及其子模式中的比重變化，挖掘主導(dǎo)特征co-location 模式，以揭示模式中特征的不同重要性。

本文研究主導(dǎo)特征co-location 模式挖掘，但與文獻(xiàn)［5］不同的是，本文針對(duì)團(tuán)實(shí)例模型可能會(huì)忽略非團(tuán)的空間特征間的主導(dǎo)關(guān)系，提出基于星型實(shí)例模型來挖掘亞頻繁co-location模式中的主導(dǎo)特征及主導(dǎo)特征模式的方法。

2 基本概念及問題定義

2.1 傳統(tǒng)co-location模式

給定一個(gè)空間特征集合F={f1，f2，…，fn}，對(duì)應(yīng)的空間實(shí)例集合S=S1∪S2∪…∪Sn，其中Si(1 ≤i ≤n)是特征fi的實(shí)例集合，以及距離閾值d。通常，如果兩個(gè)實(shí)例的歐幾里德距離小于等于距離閾值，則稱它們滿足空間鄰近關(guān)系R，即。對(duì)于一個(gè)k 階空間co-location 模式c={f1，f2，…，fk}(c ?F，k=|c|)，以 及 實(shí) 例 集I={i1，i2，…，ik}(I ?S)，若I 包含c 所有特征的實(shí)例且I 中沒有一個(gè)子集包含 c 所 有 特 征 的 實(shí) 例 ，并 且 I 形 成 團(tuán) ，即{R(ii，ij)|1 ≤i ≤k，1 ≤j ≤k}，則稱I 為c 的一個(gè)行實(shí)例，c 的所有行實(shí)例構(gòu)成c 的表實(shí)例，記為T（c）。如圖1 所示，圖中有3個(gè)空間特征A、B 和C，它們的實(shí)例數(shù)都為3，滿足鄰近關(guān)系的實(shí)例用實(shí)線連接，則co-location 模式{A，B，C}的表實(shí)例為：T({A，B，C})={A.1，B.1，C.1}。

圖1 空間特征及其實(shí)例分布示例Fig.1 Example of spatial features and distribution of their instances

在傳統(tǒng)co-location 模式中，特征fi在模式c 中的參與率定義為fi的實(shí)例在c 的表實(shí)例中不重復(fù)出現(xiàn)的個(gè)數(shù)與fi總實(shí)例個(gè)數(shù)的比率，即：

其中：π是關(guān)系投影操作，Si表示特征fi的所有實(shí)例集合。

模式c的參與度PI（c）定義為模式c中所有特征的參與率的最小值，即：

給定參與度閾值min_prev，當(dāng)PI(c)≥min_prev，則稱模式c 為頻繁co-location 模式。如圖1 所示，設(shè)參與度閾值min_prev=0.3，模式｛A，B，C｝的參與度為：PI({A，B，C})=，則模式｛A，B，C｝是一個(gè)頻繁colocation模式。

2.2 亞頻繁co-location模式

傳統(tǒng)co-location 模式基于團(tuán)實(shí)例模型度量模式的有趣程度，然而，在實(shí)際應(yīng)用中，嚴(yán)格的團(tuán)實(shí)例要求，可能使得空間特征間的某些重要關(guān)系被忽略。例如，在圖1 中，模式｛A，B，C｝僅 有｛A.1，B.1，C.1｝一 個(gè) 行 實(shí) 例，其 參 與 度 為，當(dāng)參與度閾值為0.5 時(shí)，模式｛A，B，C｝不是頻繁模式。但是，從圖1中可以看出，在特征A、B和C中，每個(gè)特征分別有2個(gè)實(shí)例與其余2個(gè)特征的實(shí)例有鄰近關(guān)系，即每個(gè)特征至少有2/3 的實(shí)例與模式中其他特征的實(shí)例有鄰近關(guān)系，表明特征A、B、C 具有較高的空間相關(guān)性?；谏鲜鲇^察，Wang 等［6-7］提出了星型實(shí)例模型及亞頻繁co-location模式。

定義1星型鄰居實(shí)例。給定空間實(shí)例ij和距離閾值d，實(shí)例ij的星型鄰居實(shí)例集合SNsI(ij)定義為：

圖1中，SNsI(A.2)={A.2，B.1，C.2}。

定義2星型參與實(shí)例。給定co-location模式c，特征fi在模式c 中的星型參與實(shí)例定義為特征fi的實(shí)例集合，其中每個(gè)實(shí)例的星型鄰居實(shí)例集合包含了模式c 的所有特征的實(shí)例。

圖1中，SPIns(A，{A，B，C})={A.1，A.2}。

定義3星型參與率和星型參與度。給定co-location 模式c，特征fi在模式c 中的星型參與率定義為特征fi的星型參與實(shí)例數(shù)與fi的實(shí)例個(gè)數(shù)的比率：SPR(fi，c)=模式c 的星型參與度SPI(c)定義為模式c中所有特征的星型參與率的最小值：SPI(c)=

給定星型參與度閾值min_sprev，當(dāng)SPI(c)≥min_sprev，則稱模式c為亞頻繁模式。

例1 圖1 中有3 個(gè)特征A、B 和C，它們的實(shí)例數(shù)都為3。設(shè)星型參與度閾值min_sprev=0.5，模式{A，B，C}的星型參與度：SPI({A，B，C})=min(0.67，0.67，0.67)=0.67，則模式｛A，B，C｝是一個(gè)亞頻繁co-location模式。

2.3 主導(dǎo)特征co-location模式

與傳統(tǒng)頻繁co-location 模式相比，亞頻繁co-location 模式可以發(fā)現(xiàn)更豐富的空間特征關(guān)系。但是，亞頻繁模式也沒有較好地區(qū)分模式中不同特征的不同重要性及不同特征對(duì)模式的不同貢獻(xiàn)。于是，基于亞頻繁模式及其星型實(shí)例模型，本文提出了新的主導(dǎo)特征co-location 模式。不同于基于傳統(tǒng)頻繁模式及其團(tuán)實(shí)例模型的傳統(tǒng)主導(dǎo)特征模式，該類模式僅考慮空間特征參與到模式及其子模式中的比重變化［5］，本文所提的主導(dǎo)特征模式利用特征貢獻(xiàn)度度量特征對(duì)模式的影響，采用特征影響比指數(shù)度量模式中特征間的影響，從而發(fā)現(xiàn)更有價(jià)值的主導(dǎo)特征及主導(dǎo)特征模式。

定義4星型行實(shí)例。給定k 階亞頻繁co-location 模式c={f1，f2，…，fi，…，fk}及其實(shí)例集I={i1，i2，…，ii，…，ik}，其中ii(1 ≤i ≤k)是特征fi的實(shí)例。如果I 是特征fi的星型參與實(shí)例的星型鄰居實(shí)例SNsI(ii)的子集，則稱I是特征fi在模式c中的一個(gè)星型行實(shí)例。特征fi在模式c中的所有星型行實(shí)例記為，所有特征在模式c中的所有星型行實(shí)例構(gòu)成模式c的星型表實(shí)例STIns(c)。

例2 空間實(shí)例分布如圖2 所示，表1 給出了模式｛D，F(xiàn)，H｝的星型行實(shí)例。特征H的星型參與實(shí)例H.2的星型鄰居實(shí)例為｛D.1，D.4，F(xiàn).1，H.2｝，實(shí)例集｛D.1，F(xiàn).1，H.2｝是特征H在模式｛D，F(xiàn)，H｝中的一個(gè)星型行實(shí)例，特征D 在模式｛D，F(xiàn)，H｝中的所有星型行實(shí)例SRIns(D，{D，F(xiàn)，H})為：{D.2，F(xiàn).5，H.1}，{D.3，F(xiàn).6，H.1}，{D.4，F(xiàn).1，H.2}，表1 中的所有星型行實(shí)例即構(gòu)成模式｛D，F(xiàn)，H｝的星型表實(shí)例STIns({D，F(xiàn)，H})。

圖2 主導(dǎo)特征及主導(dǎo)特征模式示例Fig.2 Example of dominant features and patterns with dominant features

定義5特征貢獻(xiàn)度。給定k 階亞頻繁co-location 模式c={f1，f2，…，fk}，特征fi對(duì)模式c的貢獻(xiàn)度FCR(fi，c)定義為fi在c中的星型行實(shí)例數(shù)與c的星型行實(shí)例數(shù)的比率：

例3 模式{D，F(xiàn)，H}中各個(gè)特征的貢獻(xiàn)度分別為：FCR(D，{D，F(xiàn)，H})=FCR(F，{D，F(xiàn)，H})=FCR(H，{D，F(xiàn)，H})=，所以特征H（醫(yī)院）對(duì)模式{D，F(xiàn)，H}的貢獻(xiàn)度最大。

特征fi對(duì)模式c 的貢獻(xiàn)度表示的是以fi的實(shí)例為中心的星型行實(shí)例集在模式c 的星型行實(shí)例集的占比，用于度量特征對(duì)模式的影響，fi的貢獻(xiàn)度越大，fi在模式中越重要。為了進(jìn)一步度量模式中特征間的影響，下面引入特征影響比指數(shù)及相關(guān)概念。

定義6特征最大聚集數(shù)。給定k階亞頻繁co-location 模式c={f1，f2，…，fk}，特 征fi在 模 式c 中 的 最 大 聚 集 數(shù)MFG(fi，c)定義為c中的其余各個(gè)特征在fi的星型參與實(shí)例的星型鄰居中的實(shí)例數(shù)之和的最大值與fi的星型參與實(shí)例數(shù)的比值：

表1 模式｛D，F(xiàn)，H｝的星型行實(shí)例Tab.1 Star row instances of pattern｛D，F(xiàn)，H｝

例4 對(duì)于圖2 中的模式｛D，F(xiàn)，H｝，特征H 的最大聚集數(shù)為：MFG(H，{D，F(xiàn)，H})=max(7，6)/4=1.75。

特征最大聚集數(shù)反映了模式中某個(gè)特征實(shí)例對(duì)其余特征實(shí)例的影響程度，或其余特征實(shí)例對(duì)該特征實(shí)例的依賴程度。

定義7特征影響度。給定k 階亞頻繁co-location 模式c={f1，f2，…，fk}，特征fi對(duì)模式c 的影響度FIR(fi，c)定義為fi的最大聚集數(shù)與星型參與率的乘積：

例5 在圖2 中，模式｛D，F(xiàn)，H｝中各個(gè)特征影響度分別為：FIR(D，{D，F(xiàn)，H})=1×0.43=0.43，F(xiàn)IR(F，{D，F(xiàn)，H})=1×0.5=0.5，F(xiàn)IR(H，{D，F(xiàn)，H})=1.75×1=1.75。

事實(shí)上，特征影響度是考慮了實(shí)例間相互影響的星型參與率，兼顧了模式中特征的重要性和頻繁性。如圖2 中實(shí)例H.1和D.2，都參與到模式｛D，F(xiàn)，H｝中，但是重要性不同。

定義8特征影響比指數(shù)。給定亞頻繁co-location 模式c=(f1，f2，…，fk)，如 果 兩 個(gè) 特 征fi，fj∈c 的 影 響 度 滿 足那 么 特 征fi對(duì) 特 征fj的 影 響 比 指 數(shù)FIQI(fi，fj)定義為：

特征影響比指數(shù)度量了模式中特征間的影響差異，影響比指數(shù)FIQI(fi，fj)越大，特征fi對(duì)特征fj主導(dǎo)性越強(qiáng)。

例6在圖2 中，模式｛D，F(xiàn)，H｝中特征H 對(duì)特征D 的影響比指數(shù)FIQI(H，D)=1-0.43/1.75=0.75。

定義9主導(dǎo)特征和主導(dǎo)特征模式。給定亞頻繁co-location 模式c={f1，f2，…，fk}，特征貢獻(xiàn)度閾值min_fcr 和影響比指數(shù)閾值min_fiqi。如果特征fi∈c滿足以下條件，則fi為主導(dǎo)特征，模式c為主導(dǎo)特征模式。

1）FCR(fi，c)≥min_fcr；

2）FIQI(fi，fmin)≥min_fiqi；

例7 設(shè)min_fcr=0.4 和min_fiqi=0.4，模式{D，F(xiàn)，H}中各個(gè)特征的貢獻(xiàn)度、影響度和影響比指數(shù)的計(jì)算結(jié)果如表2 所示。從表2 中可得出，模式｛D，F(xiàn)，H｝是主導(dǎo)特征模式，主導(dǎo)特征為H，也就是醫(yī)院主導(dǎo)了藥店和花店的共存。

表2 {D，F(xiàn)，H}中的特征指標(biāo)Tab.2 Feature indicators of{D，F(xiàn)，H}

問題定義 給定空間特征集合F，空間實(shí)例集合S，距離閾值d，星型參與度閾值min_sprev，特征貢獻(xiàn)度閾值min_fcr和影響比指數(shù)閾值min_fiqi，挖掘亞頻繁co-location 模式中的所有主導(dǎo)特征及主導(dǎo)特征模式。

3 挖掘算法

需要強(qiáng)調(diào)的是，主導(dǎo)特征模式不滿足反單調(diào)性。如圖2中，特征H 在子模式｛F，H｝與超模式｛D，F(xiàn)，H｝的貢獻(xiàn)度與影響比指數(shù)關(guān)系分別為：

所以，主導(dǎo)特征模式挖掘不能應(yīng)用模式的反單調(diào)性進(jìn)行剪枝。為了提高主導(dǎo)特征模式挖掘算法的效率，本文設(shè)計(jì)了亞頻繁co-location 模式中的主導(dǎo)特征模式挖掘算法SDFMA（Sub-prevalent based Dominant-Feature Mining Algorithm）。首先，由于亞頻繁模式滿足反單調(diào)性，利用亞頻繁模式的反單調(diào)性剪枝策略，逐階生成亞頻繁模式，同時(shí)基于生成的亞頻繁模式，挖掘主導(dǎo)特征及主導(dǎo)特征模式；其次，在挖掘主導(dǎo)特征及主導(dǎo)特征模式的過程中，僅計(jì)算貢獻(xiàn)度大于閾值的特征對(duì)最小影響度特征的影響比指數(shù)。

算法1 SDFMA。

輸入 空間數(shù)據(jù)集S，空間特征集F，距離閾值d，星型參與度閾值min_sprev，貢獻(xiàn)度閾值min_fcr，影響比指數(shù)閾值min_fiqi；

輸出 主導(dǎo)特征co-location模式集SDFCP；

變量 表示co-location 模式階數(shù)的k，表示k 階co-location 亞頻繁模式集的Pk。

第1）行根據(jù)空間數(shù)據(jù)集、空間特征集和距離閾值生成星型鄰居集；第4）行根據(jù)算法PBTA［6-7］逐階生成k 階亞頻繁co-location 模式；對(duì)每個(gè)亞頻繁模式，第7）、8）行計(jì)算模式中每個(gè)特征的最大聚集數(shù)和影響度，第9）行得到模式中的最小影響度特征，第12）、13）行計(jì)算模式中每個(gè)特征的貢獻(xiàn)度和影響比指數(shù)，如果它們均大于閾值，則該特征是模式的主導(dǎo)特征，將該特征放入模式的主導(dǎo)特征集（第14）行），如果模式有主導(dǎo)特征，則該模式是主導(dǎo)特征模式，該模式及其主導(dǎo)特征集放入結(jié)果集（第19）行）。

4 實(shí)驗(yàn)結(jié)果與分析

首先，生成3 個(gè)不同規(guī)模的合成數(shù)據(jù)集（Synthetic data 1～3），并在這3 個(gè)數(shù)據(jù)集上評(píng)估不同參數(shù)設(shè)置對(duì)本文提出的主導(dǎo)特征模式挖掘算法SDFMA 效率的影響。然后，在2 個(gè)真實(shí)數(shù)據(jù)集上比較分析了SDFMA 與基準(zhǔn)算法的挖掘結(jié)果。選取的基準(zhǔn)算法包括亞頻繁模式挖掘算法PTBA［6-7］和傳統(tǒng)主導(dǎo)特征模式挖掘算法AMDFCP（Algorithm of Dominant Feature Co-location Pattern Mining）［5］。PTBA 用于比較分析亞頻繁模式與本文提出的主導(dǎo)特征模式（基于亞頻繁模式及星型實(shí)例模型的主導(dǎo)特征模式）的異同；而AMDFCP 據(jù)我們了解是僅有的主導(dǎo)特征模式挖掘算法，用于比較分析基于傳統(tǒng)頻繁模式及團(tuán)實(shí)例模型的主導(dǎo)特征模式與本文提出的主導(dǎo)特征模式的異同。最后，選取SDFMA 和AMDFCP 在2 個(gè)真實(shí)數(shù)據(jù)集上挖掘得出的主導(dǎo)特征模式進(jìn)行實(shí)例分析，驗(yàn)證本文提出的主導(dǎo)特征模式的實(shí)用性。

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

實(shí)驗(yàn)數(shù)據(jù)集的統(tǒng)計(jì)信息如表3 所示，其中：Plantdata 是一個(gè)包含31 種植物類型（特征）共356 棵植物（實(shí)例）的“三江并流”區(qū)域珍稀植物數(shù)據(jù)集，其分布呈圖3 所示的帶狀分布；Beijing-POI 是一個(gè)包含16 種POI 類型（特征）共23 025 個(gè)POI（實(shí)例）的北京市POI數(shù)據(jù)集，其分布如圖4所示。合成數(shù)據(jù)集分別在500×500、1 000×1 000、1 000×1 000的范圍內(nèi)根據(jù)泊松分布隨機(jī)生成。

圖3 Plantdata數(shù)據(jù)集分布圖Fig.3 Distribution of Plantdata dataset

圖4 Beijing-POI數(shù)據(jù)集分布圖Fig.4 Distribution of Beijing-POI dataset

表3 實(shí)驗(yàn)數(shù)據(jù)集統(tǒng)計(jì)信息Tab.3 Experimental data set statistics

實(shí)驗(yàn)運(yùn)行環(huán)境：所有算法采用python語(yǔ)言實(shí)現(xiàn)，并運(yùn)行于具有Intel Core i7 CPU、8 GB 內(nèi)存、Windows 10 及pycharm2017的PC上。

參數(shù)設(shè)置：本文提出的主導(dǎo)特征模式挖掘算法SDFMA 在各個(gè)數(shù)據(jù)集上的實(shí)驗(yàn)參數(shù)默認(rèn)設(shè)置如表4所示。

4.2 不同參數(shù)設(shè)置對(duì)SDFMA的運(yùn)行時(shí)間影響

首先在3 個(gè)不同規(guī)模的合成數(shù)據(jù)集上分析不同參數(shù)設(shè)置對(duì)SDFMA運(yùn)行時(shí)間的影響。

4.2.1 距離閾值對(duì)算法運(yùn)行時(shí)間的影響

距離閾值d 分別取10、15、20 和25 時(shí)的算法運(yùn)行時(shí)間結(jié)果如圖5 所示。在每個(gè)數(shù)據(jù)集上，隨著距離閾值的增加，算法運(yùn)行時(shí)間逐漸增加，并且隨著數(shù)據(jù)集規(guī)模的增大，運(yùn)行時(shí)間也逐漸增加。合成數(shù)據(jù)集1比合成數(shù)據(jù)集2分布稠密，距離閾值的影響較明顯，并且運(yùn)行時(shí)間也相對(duì)較長(zhǎng)。

表4 SDFMA的實(shí)驗(yàn)參數(shù)默認(rèn)值Tab.4 Default values of experimental parameters of SDFMA algorithm

圖5 不同距離閾值d下的運(yùn)行時(shí)間比較Fig.5 Comparison of running time at different d

4.2.2 星型參與度閾值對(duì)算法運(yùn)行時(shí)間的影響

星型參與度閾值min_sprev 分別取0.3、0.4、0.5、0.6 和0.7時(shí)的算法運(yùn)行時(shí)間結(jié)果如圖6所示。在所有數(shù)據(jù)集上，隨著星型參與度閾值增大，算法運(yùn)行時(shí)間逐漸減少。合成數(shù)據(jù)集3 的數(shù)據(jù)量較大，閾值影響較為明顯，合成數(shù)據(jù)集1 和合成數(shù)據(jù)集2 實(shí)例數(shù)和特征數(shù)一樣，但是分布范圍不同，合成數(shù)據(jù)集1 比合成數(shù)據(jù)集2 分布稠密，數(shù)據(jù)集1 的運(yùn)行時(shí)間比數(shù)據(jù)集2的運(yùn)行時(shí)間長(zhǎng)。

圖6 不同星型參與度閾值min_sprev下的運(yùn)行時(shí)間比較Fig.6 Comparison of running time at different min_sprev

4.2.3 貢獻(xiàn)度閾值對(duì)算法效率的影響

貢獻(xiàn)度閾值min_fcr分別取0.2、0.3、0.4、0.5和0.6時(shí)的算法運(yùn)行時(shí)間結(jié)果如圖7 所示。算法運(yùn)行時(shí)間不隨貢獻(xiàn)度閾值的變化而大幅波動(dòng)，這是因?yàn)樗惴ǖ闹饕_銷是亞頻繁模式挖掘。另外，貢獻(xiàn)度閾值不滿足反單調(diào)性，即使特征在模式中的貢獻(xiàn)度小于閾值，特征在超模式中的貢獻(xiàn)度也需要計(jì)算。算法運(yùn)行時(shí)間在貢獻(xiàn)度閾值介于0.5 到0.6 區(qū)間時(shí)有較大波動(dòng)，這是因?yàn)槎A亞頻繁模式中的特征貢獻(xiàn)度都為0.5，當(dāng)貢獻(xiàn)度閾值大于0.5 時(shí)，所有這些二階模式都不是主導(dǎo)特征模式。

4.2.4 影響比指數(shù)閾值對(duì)算法運(yùn)行時(shí)間的影響

影響比指數(shù)閾值min_fiqi分別取0.2、0.3、0.4、0.5和0.6時(shí)的算法運(yùn)行時(shí)間結(jié)果如圖8 所示。隨著影響比指數(shù)閾值的變化，算法運(yùn)行時(shí)間基本不變。這也是因?yàn)橛绊懕戎笖?shù)閾值不滿足反單調(diào)性。合成數(shù)據(jù)集2 的運(yùn)行效率優(yōu)于合成數(shù)據(jù)集1，這是因?yàn)楹铣蓴?shù)據(jù)集1比合成數(shù)據(jù)集2稠密，容易形成較多的星型參與實(shí)例。

圖7 不同貢獻(xiàn)度閾值min_fcr下的運(yùn)行時(shí)間對(duì)比Fig.7 Comparison of running time at different min_fcr

圖8 不同影響比指數(shù)閾值min_fiqi下的運(yùn)行時(shí)間對(duì)比Fig.8 Comparison of running time at different min_fiqi

4.3 SDFMA的挖掘結(jié)果分析

在2個(gè)真實(shí)數(shù)據(jù)集Plantdata和Beijing-POI上比較SDFMA與亞頻繁模式挖掘算法PTBA、傳統(tǒng)主導(dǎo)特征模式挖掘算法AMDFCP的挖掘結(jié)果。

4.3.1 在Plantdata數(shù)據(jù)集上的結(jié)果比較

在Plantdata 數(shù)據(jù)集上，三個(gè)算法在不同（星型）參與度閾值下挖掘得到的模式數(shù)量如圖9（a）所示。從圖中可以看出，SDFMA 挖掘的主導(dǎo)特征模式數(shù)量大約為PTBA 挖掘的亞頻繁模式數(shù)量的60%，這是因?yàn)镾DFMA 有效去除了不含主導(dǎo)特征的亞頻繁模式。SDFMA 的主導(dǎo)特征模式明顯比AMDFCP 的傳統(tǒng)主導(dǎo)特征模式數(shù)量多，這是因?yàn)锳MDFCP 忽略了大量不能形成團(tuán)的主導(dǎo)特征模式，而SDFMA 找到了空間關(guān)系更豐富的主導(dǎo)特征模式。

三個(gè)算法在不同距離閾值下挖掘得到的模式數(shù)量如圖9（b）所示。隨著距離閾值的增大，對(duì)鄰近關(guān)系的約束性變?nèi)?，頻繁模式數(shù)量增多。從圖9（b）中同樣可以看到，SDFMA 的主導(dǎo)特征模式數(shù)量為PTBA 的亞頻繁模式數(shù)量的60%左右，AMDFCP 的傳統(tǒng)主導(dǎo)特征模式數(shù)量少于SDFMA 的主導(dǎo)特征模式數(shù)量。

圖9 Plantdata數(shù)據(jù)集上不同（星型）參與度閾值和距離閾值下的模式數(shù)量對(duì)比Fig.9 Comparison of pattern number with different min_sprev or d on Plantdata dataset

4.3.2 在Beijing-POI數(shù)據(jù)集上的結(jié)果比較

在Beijing-POI 數(shù)據(jù)集上，三個(gè)算法在不同（星型）參與度閾值、距離閾值下挖掘得到的模式數(shù)量分別如圖10（a）、（b）所示。從圖中可以看出，SDFMA 的主導(dǎo)特征模式數(shù)量平均為PTBA 的亞頻繁模式數(shù)量的60%，SDFMA 的主導(dǎo)特征模式數(shù)量多于AMDFCP 的傳統(tǒng)主導(dǎo)特征的模式數(shù)量。隨著星型參與度閾值的增加，主導(dǎo)特征模式在亞頻繁模式中的占比增加，這說明SDFMA 能夠保留高參與度的主導(dǎo)特征模式；隨著距離閾值增加，SDFMA 和AMDFCP 的主導(dǎo)特征模式數(shù)量均增長(zhǎng)平緩，這是因?yàn)镻OI 在市中心分布密集，在郊區(qū)分布稀疏，距離閾值影響不明顯。

圖10 Beijing-POI數(shù)據(jù)集上不同（星型）參與度閾值和距離閾值下的模式數(shù)量對(duì)比Fig.10 Comparison of pattern number with different min_sprev or d on Beijing-POI dataset

4.4 主導(dǎo)特征co-location模式實(shí)例分析

為了驗(yàn)證本文提出的主導(dǎo)特征模式的實(shí)用性，對(duì)SDFMA和傳統(tǒng)AMDFCP 在2個(gè)真實(shí)數(shù)據(jù)集上挖掘得到的主導(dǎo)特征模式進(jìn)行實(shí)例分析。表5 列出了它們?cè)谶@兩個(gè)數(shù)據(jù)集上的二階和三階模式。

表5 SDFMA和AMDFCP在不同數(shù)據(jù)上的挖掘結(jié)果對(duì)比Tab.5 Mining result comparison of SDFMA and AMDFCP on different datasets

從表1中可以看到：首先，SDFMA可以挖掘到二階及以上主導(dǎo)特征模式，而AMDFCP 只能挖掘到三階及以上主導(dǎo)特征模式，這是因?yàn)锳MDFCP 通過分析特征在模式與其子模式中的參與率變化來挖掘主導(dǎo)特征，模式挖掘只能從三階開始。更進(jìn)一步，SDFMA 挖掘得到的這些二階主導(dǎo)特征模式具有重要的現(xiàn)實(shí)意義。例如，在Plantdata 數(shù)據(jù)集上的模式｛冬蟲夏草，梭砂貝母*｝中，冬蟲夏草的生長(zhǎng)基礎(chǔ)是蝙蝠蛾，蝙蝠蛾一般生長(zhǎng)在貝母、珠芽蓼等植物的根部附近，所以梭砂貝母能夠?yàn)轵鸲晏峁┥L(zhǎng)環(huán)境，間接地促進(jìn)冬蟲夏草的生長(zhǎng)，梭砂貝母構(gòu)成這一模式的主導(dǎo)特征。再例如，在Beijing-POI 數(shù)據(jù)集上的二階主導(dǎo)特征模式對(duì)城市規(guī)劃和商業(yè)選址等應(yīng)用具有較高的實(shí)用性。在模式｛中餐館，酒店*｝和｛咖啡館，花園*｝中，主導(dǎo)特征分別是酒店和花園，那么可以得出，在酒店附近開中餐館是有價(jià)值的，在花園附近開咖啡館也是合理的。

其次，與AMDFCP 相比，SDFMA 能夠挖掘到更多的高階主導(dǎo)特征模式以及更合理的主導(dǎo)特征。例如，AMDFCP 不能挖掘到模式｛云南榧木*，云南紅豆杉，貢山三尖杉*｝和｛中餐館，咖啡屋*，招待所*｝。再例如，AMDFCP 和SDFMA 都能挖掘到模式｛冬蟲夏草*，梭砂貝母*，長(zhǎng)苞冷杉｝，但是SDFMA 識(shí)別的主導(dǎo)特征為梭砂貝母和長(zhǎng)苞冷杉，AMDFCP 識(shí)別的主導(dǎo)特征為冬蟲夏草和梭砂貝母。我們知道，梭砂貝母和長(zhǎng)苞冷杉都能為冬蟲夏草提供適宜的生長(zhǎng)環(huán)境，而長(zhǎng)苞冷杉的生長(zhǎng)并不依賴于冬蟲夏草和梭砂貝母。再看模式｛酒店，停車場(chǎng)，服裝店｝，SDFMA 識(shí)別的主導(dǎo)特征為酒店和服裝店，AMDFCP識(shí)別的主導(dǎo)特征為酒店和停車場(chǎng)。在實(shí)際生活中，停車場(chǎng)大多存在于酒店或者服裝店周邊，也就是酒店和服裝店主導(dǎo)了停車場(chǎng)的存在，而酒店和停車場(chǎng)對(duì)服裝店并不存在著直接的主導(dǎo)作用。因此，SDFMA識(shí)別的主導(dǎo)特征更合理。

5 結(jié)語(yǔ)

主導(dǎo)關(guān)系體現(xiàn)的是中心事物對(duì)周邊事物的吸引力或者周邊事物對(duì)中心事物的依賴性，本文基于星型實(shí)例模型研究空間亞頻繁co-location 模式的主導(dǎo)特征挖掘，以更好地揭示空間特征間的主導(dǎo)關(guān)系，挖掘更有價(jià)值的主導(dǎo)特征模式。首先，本文在亞頻繁模式及其星型實(shí)例模型的基礎(chǔ)上給出了相關(guān)定義，并通過特征貢獻(xiàn)度和特征影響比指數(shù)兩個(gè)指標(biāo)度量特征的主導(dǎo)性；然后，提出了有效的主導(dǎo)特征模式挖掘算法；最后，通過在合成數(shù)據(jù)集和真實(shí)數(shù)據(jù)集上的大量實(shí)驗(yàn)驗(yàn)證了本文算法能夠挖掘到更豐富、更有價(jià)值的主導(dǎo)特征模式。在未來的研究工作中，我們將設(shè)計(jì)高效的哈希結(jié)構(gòu)和有效的剪枝策略，進(jìn)一步提高算法的挖掘效率。