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

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

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

0 引言

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

通常，空間co-location 模式挖掘方法假設(shè)空間實例相互獨立，并采用空間實例參與到模式實例的頻繁性（參與率）度量其特征在模式中的重要性，采用空間特征的最小參與率（參與度）度量模式的有趣程度，忽略了空間特征間的某些重要關(guān)系（如主導(dǎo)關(guān)系）。例如，在co-location 模式｛藥店，醫(yī)院，花店｝中，各個特征的參與率分別為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)特征支配，進而為深入剖析模式中特征間的其他重要關(guān)系（如因果關(guān)系、共生關(guān)系、排斥關(guān)系）奠定基礎(chǔ)，為基于co-location 模式的決策分析（如環(huán)境監(jiān)測、城市規(guī)劃、交通控制）提供支持。

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

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

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

1 相關(guān)工作

根據(jù)挖掘?qū)ο蟮牟煌?，空間co-location 模式挖掘主要可以分為如下6類：

1）從確定空間數(shù)據(jù)中挖掘co-location 模式。這類模式挖掘主要以優(yōu)化挖掘過程、提高挖掘效率為目標，如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 模式。文獻［14］研究了從區(qū)間數(shù)據(jù)中挖掘co-location 模式；文獻［15］將Join-based 算法擴展為UJoin-based 算法，挖掘位置不確定空間數(shù)據(jù)中的co-location 模式；文獻［16］通過對不確定性數(shù)據(jù)建模和處理，在分布式系統(tǒng)下定義了概率頻繁co-location 模式，并設(shè)計了高效的并行挖掘算法。

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

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

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

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

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

2 基本概念及問題定義

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

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

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

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

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

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

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

2.2 亞頻繁co-location模式

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

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

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

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

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

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

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

例1 圖1 中有3 個特征A、B 和C，它們的實例數(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｝是一個亞頻繁co-location模式。

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

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

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

例2 空間實例分布如圖2 所示，表1 給出了模式｛D，F(xiàn)，H｝的星型行實例。特征H的星型參與實例H.2的星型鄰居實例為｛D.1，D.4，F(xiàn).1，H.2｝，實例集｛D.1，F(xiàn).1，H.2｝是特征H在模式｛D，F(xiàn)，H｝中的一個星型行實例，特征D 在模式｛D，F(xiàn)，H｝中的所有星型行實例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 中的所有星型行實例即構(gòu)成模式｛D，F(xiàn)，H｝的星型表實例STIns({D，F(xiàn)，H})。

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

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

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

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

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

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

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

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

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

例5 在圖2 中，模式｛D，F(xiàn)，H｝中各個特征影響度分別為：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。

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

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

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

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

定義9主導(dǎo)特征和主導(dǎo)特征模式。給定亞頻繁co-location 模式c={f1，f2，…，fk}，特征貢獻度閾值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}中各個特征的貢獻度、影響度和影響比指數(shù)的計算結(jié)果如表2 所示。從表2 中可得出，模式｛D，F(xiàn)，H｝是主導(dǎo)特征模式，主導(dǎo)特征為H，也就是醫(yī)院主導(dǎo)了藥店和花店的共存。

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

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

3 挖掘算法

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

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

算法1 SDFMA。

輸入 空間數(shù)據(jù)集S，空間特征集F，距離閾值d，星型參與度閾值min_sprev，貢獻度閾值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 模式；對每個亞頻繁模式，第7）、8）行計算模式中每個特征的最大聚集數(shù)和影響度，第9）行得到模式中的最小影響度特征，第12）、13）行計算模式中每個特征的貢獻度和影響比指數(shù)，如果它們均大于閾值，則該特征是模式的主導(dǎo)特征，將該特征放入模式的主導(dǎo)特征集（第14）行），如果模式有主導(dǎo)特征，則該模式是主導(dǎo)特征模式，該模式及其主導(dǎo)特征集放入結(jié)果集（第19）行）。

4 實驗結(jié)果與分析

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

4.1 實驗設(shè)置

實驗數(shù)據(jù)集的統(tǒng)計信息如表3 所示，其中：Plantdata 是一個包含31 種植物類型（特征）共356 棵植物（實例）的“三江并流”區(qū)域珍稀植物數(shù)據(jù)集，其分布呈圖3 所示的帶狀分布；Beijing-POI 是一個包含16 種POI 類型（特征）共23 025 個POI（實例）的北京市POI數(shù)據(jù)集，其分布如圖4所示。合成數(shù)據(jù)集分別在500×500、1 000×1 000、1 000×1 000的范圍內(nèi)根據(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ù)據(jù)集統(tǒng)計信息Tab.3 Experimental data set statistics

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

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

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

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

4.2.1 距離閾值對算法運行時間的影響

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

表4 SDFMA的實驗參數(shù)默認值Tab.4 Default values of experimental parameters of SDFMA algorithm

圖5 不同距離閾值d下的運行時間比較Fig.5 Comparison of running time at different d

4.2.2 星型參與度閾值對算法運行時間的影響

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

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

4.2.3 貢獻度閾值對算法效率的影響

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

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

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

圖7 不同貢獻度閾值min_fcr下的運行時間對比Fig.7 Comparison of running time at different min_fcr

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

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

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

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

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

三個算法在不同距離閾值下挖掘得到的模式數(shù)量如圖9（b）所示。隨著距離閾值的增大，對鄰近關(guān)系的約束性變?nèi)酰l繁模式數(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ù)量對比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ù)集上，三個算法在不同（星型）參與度閾值、距離閾值下挖掘得到的模式數(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ù)量均增長平緩，這是因為POI 在市中心分布密集，在郊區(qū)分布稀疏，距離閾值影響不明顯。

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

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

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

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

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

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

5 結(jié)語

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