空間亞頻繁co-location模式的主導特征挖掘

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

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

0 引言

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

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

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

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

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

1 相關工作

根據挖掘對象的不同，空間co-location 模式挖掘主要可以分為如下6類：

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

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

4）從模糊空間數據中挖掘co-location 模式。文獻［19］提出了模糊參與率和模糊參與度以挖掘模糊空間co-location 模式；文獻［20］將密度峰值聚類算法和模糊理論相結合來實現實例對簇的模糊劃分，并采用模糊團代替傳統團以挖掘co-lo?cation 模式；文獻［21］基于模糊理論定義了模糊鄰近度，并利用模糊聚類算法進行co-location模式挖掘。

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

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

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

2 基本概念及問題定義

2.1 傳統co-location模式

給定一個空間特征集合F={f1，f2，…，fn}，對應的空間實例集合S=S1∪S2∪…∪Sn，其中Si(1 ≤i ≤n)是特征fi的實例集合，以及距離閾值d。通常，如果兩個實例的歐幾里德距離小于等于距離閾值，則稱它們滿足空間鄰近關系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 的所有行實例構成c 的表實例，記為T（c）。如圖1 所示，圖中有3個空間特征A、B 和C，它們的實例數都為3，滿足鄰近關系的實例用實線連接，則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

在傳統co-location 模式中，特征fi在模式c 中的參與率定義為fi的實例在c 的表實例中不重復出現的個數與fi總實例個數的比率，即：

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

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

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

2.2 亞頻繁co-location模式

傳統co-location 模式基于團實例模型度量模式的有趣程度，然而，在實際應用中，嚴格的團實例要求，可能使得空間特征間的某些重要關系被忽略。例如，在圖1 中，模式｛A，B，C｝僅 有｛A.1，B.1，C.1｝一 個 行 實 例，其 參 與 度 為，當參與度閾值為0.5 時，模式｛A，B，C｝不是頻繁模式。但是，從圖1中可以看出，在特征A、B和C中，每個特征分別有2個實例與其余2個特征的實例有鄰近關系，即每個特征至少有2/3 的實例與模式中其他特征的實例有鄰近關系，表明特征A、B、C 具有較高的空間相關性。基于上述觀察，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的星型參與實例數與fi的實例個數的比率：SPR(fi，c)=模式c 的星型參與度SPI(c)定義為模式c中所有特征的星型參與率的最小值：SPI(c)=

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

例1 圖1 中有3 個特征A、B 和C，它們的實例數都為3。設星型參與度閾值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 主導特征co-location模式

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

定義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中的所有星型行實例構成模式c的星型表實例STIns(c)。

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

圖2 主導特征及主導特征模式示例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中的星型行實例數與c的星型行實例數的比率：

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

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

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

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

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

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

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

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

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

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

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

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

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

1）FCR(fi，c)≥min_fcr；

2）FIQI(fi，fmin)≥min_fiqi；

例7 設min_fcr=0.4 和min_fiqi=0.4，模式{D，F，H}中各個特征的貢獻度、影響度和影響比指數的計算結果如表2 所示。從表2 中可得出，模式｛D，F，H｝是主導特征模式，主導特征為H，也就是醫院主導了藥店和花店的共存。

表2 {D，F，H}中的特征指標Tab.2 Feature indicators of{D，F，H}

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

3 挖掘算法

需要強調的是，主導特征模式不滿足反單調性。如圖2中，特征H 在子模式｛F，H｝與超模式｛D，F，H｝的貢獻度與影響比指數關系分別為：

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

算法1 SDFMA。

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

輸出 主導特征co-location模式集SDFCP；

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

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

4 實驗結果與分析

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

4.1 實驗設置

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

圖3 Plantdata數據集分布圖Fig.3 Distribution of Plantdata dataset

圖4 Beijing-POI數據集分布圖Fig.4 Distribution of Beijing-POI dataset

表3 實驗數據集統計信息Tab.3 Experimental data set statistics

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

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

4.2 不同參數設置對SDFMA的運行時間影響

首先在3 個不同規模的合成數據集上分析不同參數設置對SDFMA運行時間的影響。

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

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

表4 SDFMA的實驗參數默認值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時的算法運行時間結果如圖6所示。在所有數據集上，隨著星型參與度閾值增大，算法運行時間逐漸減少。合成數據集3 的數據量較大，閾值影響較為明顯，合成數據集1 和合成數據集2 實例數和特征數一樣，但是分布范圍不同，合成數據集1 比合成數據集2 分布稠密，數據集1 的運行時間比數據集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時的算法運行時間結果如圖7 所示。算法運行時間不隨貢獻度閾值的變化而大幅波動，這是因為算法的主要開銷是亞頻繁模式挖掘。另外，貢獻度閾值不滿足反單調性，即使特征在模式中的貢獻度小于閾值，特征在超模式中的貢獻度也需要計算。算法運行時間在貢獻度閾值介于0.5 到0.6 區間時有較大波動，這是因為二階亞頻繁模式中的特征貢獻度都為0.5，當貢獻度閾值大于0.5 時，所有這些二階模式都不是主導特征模式。

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

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

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

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

4.3 SDFMA的挖掘結果分析

在2個真實數據集Plantdata和Beijing-POI上比較SDFMA與亞頻繁模式挖掘算法PTBA、傳統主導特征模式挖掘算法AMDFCP的挖掘結果。

4.3.1 在Plantdata數據集上的結果比較

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

三個算法在不同距離閾值下挖掘得到的模式數量如圖9（b）所示。隨著距離閾值的增大，對鄰近關系的約束性變弱，頻繁模式數量增多。從圖9（b）中同樣可以看到，SDFMA 的主導特征模式數量為PTBA 的亞頻繁模式數量的60%左右，AMDFCP 的傳統主導特征模式數量少于SDFMA 的主導特征模式數量。

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

4.3.2 在Beijing-POI數據集上的結果比較

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

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

4.4 主導特征co-location模式實例分析

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

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

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

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

5 結語

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