基于指定特征的加權co-location 模式挖掘方法

趙秦怡，黑邵敏

（大理大學數學與計算機學院，云南大理 671003）

空間co-location 模式挖掘是空間數據挖掘的研究分支，研究成果有廣泛應用。co-location 模式（并置模式）是空間特征集的一個子集，其特征實例在地理空間中頻繁出現互相近鄰，在滿足某種colocation 模式的空間中，模式的特征實例往往并置出現。例如，空間特征集｛醫院，藥店，花店｝是一個colocation 模式，則醫院、藥店和花店在地理空間中頻繁出現互相近鄰。

co-location 模式挖掘算法有大量的研究成果，基于全連接的挖掘算法〔1〕將兩個低階的模式表實例相連接，并查詢不相同特征實例的近鄰關系得到高階模式表實例。基于部分連接的挖掘算法〔1〕把實例集中的實例分割為一些不相交的團，由團中實例間的互相近鄰關系得到co-location 模式表實例，再通過掃描實例近鄰關系集獲取團之外的模式表實例。基于星型鄰居模型的無連接挖掘算法〔2〕從星型鄰居集中收集候選co-location 模式的星型表實例，再從星型表實例中去除非co-location 表實例。為解決挖掘過程中表實例生成時間復雜度高的問題，Wang 等〔3〕提出了基于前綴樹的高效挖掘算法，挖掘過程中直接通過前綴樹來快速生成所有模式的表實例集。在非經典數據挖掘研究方向，一些挖掘算法相繼提出，如基于值不確定性及存在不確定性數據的co-location 模式挖掘、基于區間數據的colocation 模式挖掘、基于模糊數據的co-location 模式挖掘、帶稀有特征的co-location 模式挖掘等方法〔4〕。而高效用co-location 模式挖掘〔5〕、主導特征colocation 模式挖掘〔6〕方法則提高了挖掘結果的指導性。

co-location 模式挖掘算法基于模式參與實例的數據度量模式的頻繁度，挖掘特征集中所有的頻繁模式，挖掘過程中不需要用戶的涉入，未考慮數據特定的應用領域以及用戶的偏好。顯著特征的colocation 模式挖掘〔7〕、領域驅動的co-location 模式挖掘〔8〕、負co-location 模式挖掘〔9〕等方法對上述問題有很好的解決，減少了對挖掘結果的再處理。co-location 模式在特定領域如城市空間規劃、植物栽培等有廣泛的應用，例如基于公交站點的colocation 模式反映了學校、居民區、商場超市、醫院、藥店等空間對象基于公交站點存在的互相近鄰關系，可用于指導在人群密集以及人員流動大的區域進行公交站點的選址。co-location 模式挖掘算法〔1〕采用特征最小參與率度量模式的頻繁程度，存在如下情況：模式在基于指定特征的實例并置程度滿足模式指導性要求，但由于部分特征的總實例數過多，使得這些特征在模式中的參與率小，模式具指導意義，但被界定為非頻繁模式。基于此，研究了定義基于指定特征的加權參與率計算規則，提出一種基于指定特征的加權co-location 模式（weighted colocation patterns based on specified feature，WCPBSF）挖掘方法。WCPBSF 挖掘方法基于指定特征度量特征參與率及模式實例間的并置程度，可以有效挖掘WCPBSF，提高挖掘結果在指定領域的指導性，實驗結果驗證了該挖掘方法的有效性。

1 WCPBSF 挖掘方法

若c 為空間特征集的一個子集，c 的特征數為n，c 的模式頻繁度用參與度度量，參與度指c 中所有特征參與率（participation ratio，PR） 的最小值（PR（c，fi）），記為PI（c）。特征參與率記為PR（c，fi），被定義為特征fi在模式c 的表實例（模式表實例中的實例之間均兩兩近鄰）中不重復出現的實例個數與fi總實例個數的比率〔5，10〕，計算式表示為：

若c 的參與度大于給定的參與度閾值，則c 是一個co-location 模式〔4，9〕。在城市空間特征實例集中，若醫院、藥店、花店3 個特征的參與率均大于參與度閾值，則{醫院，藥店，花店}是一個頻繁并置模式，稱其為co-location 模式。

例1 設醫院、藥店、花店3 個特征的實例數分別為10、20、30，實例數分別為8、10、15，則它們的參與率分別為0.8、0.5、0.5，模式參與度為0.5，大于給定的參與度閾值0.4，該模式是co-location 模式，該模式是包含了醫院特征的co-location 模式。

例1 中，若醫院、藥店、花店的表實例數分別為8、8、10，醫院的參與率為0.8，大于給定的參與度閾值，藥店參與率為0.4，花店參與率為0.33，參與度小于給定的參與度閾值，該模式不是co-location 模式。該模式所含知識解釋為：80%的醫院實例參與到{醫院，藥店，花店}的并置模式中，模式表實例中藥店相對于醫院的并置率為1，花店相對于醫院的并置率為1.25，模式的表實例中，80%的醫院意味著一個醫院有一個藥店和1.25 個花店和其互相近鄰，由醫院的參與率及其3 個特征實例之間的并置度可知該模式其實是一個具指導意義的模式。在該數據集中，由于藥店和花店的總實例數較多，其中一部分實例參與到其他的模式中，致使花店和藥店在模式{醫院，藥店，花店}中的參與率小，使得該模式不是頻繁模式。而由模式所含知識可知，基于醫院應用領域的該模式其實是具頻繁性及指導性的，在本研究中將其稱為基于醫院特征的加權co-location模式，以下提出的WCPBSF 挖掘方法可以合理挖掘上述的WCPBSF。

指定特征集中特征M，模式c=｛f1，f2，…，fn｝包含特征M，若模式c 基于M 的加權參與度大于給定閾值，則稱c 為基于特征M 的加權co-location 模式。給定空間特征集c=｛f1，f2，…，fn｝，以及c 的特征實例集O=｛O1，O2，…，On｝，其中Oi為特征fi的實例集，對于空間特征集c 的一個特征fi，fi的實例數定義為fi在該空間中出現的總實例數，即fi的實例集Oi中的元素個數，記為Nfi（Nfi=|Oi|）。設空間實例集I=｛O1，O2，…，On｝，如果I 中實例互相之間都滿足近鄰關系，稱I 是一個團實例〔11〕，如果I 包含了模式c中所有的特征，且I 中沒有任何一個子集包含c 中所有特征，則稱I 為模式c 的一個行實例〔11〕，將c所有行實例的集合稱為c 的表實例〔11〕，記為：table_instance（c）=｛I1，I2，…，Im｝，其中m 為c 中的行實例總數。特征fi的表實例數定義為fi在模式c 的表實例中不重復出現的實例個數〔10〕。記為Bfi=｜πfitable_instance（c）｜。

定義1 特征的權。給定特征M，以及含M 的模式c，c 中特征fi的權定義如下：

定義2 特征的加權參與率。給定模式c，特征fi的加權參與率WPR（fi，c）定義為fi的權與fi的參與率的乘積，計算式表示為：

定義3 模式的加權參與度。模式c 的加權參與度定義為c 中所有特征加權參與率的最小值，計算式表示為：

定義4 WCPBSF。給定特征集中特征M，若模式c 基于特征M 的加權參與度大于閾值，則c 是一個基于指定特征M 的加權co-location 模式，簡稱WCPBSF 模式。

一個高階co-location 模式的子模式均為colocation 模式〔4〕，本研究中一個高階基于特征M 的WCPBSF 的低階基于特征M 子模式均為基于M 的WCPBSF，即WCPBSF 的加權參與度滿足隨著模式階數的增大而單調遞減，證明如下：設cm為m 階頻繁模式，cm+1為cm的m+1 階超模式，①若fi=M，W（fi，cm）＝1，W（fi，cm+1）＝1，有PR（fi，cm）≥PR（fi，cm+1），故WPR（cm）≥WPR（cm+1）成立；②若Bfi≥NM且fi！＝M，有WPR（fi，cm）＝1，當B（fi，cm+1）≥NM，WPR（fi，cm+1）＝1，當B（fi，cm+1）＜NM，則，故WPR（cm）≥WPR（cm+1）成立；③若Bfi＜NM且fi！＝M，，由于B（fi+1，cm+1）＜NM，則WPR，故WPR（cm）≥WPR（cm+1）成立。

定義5 相對于M 的特征并置率。設M 為指定特征，特征fi相對于M 的特征并置率定義為fi的表實例數與M 的表實例數的比率。計算式表示為：

特征fi的并置率反映的是在一個指定特征M的實例周圍，平均出現R（fi）個特征fi的實例與其相鄰，特征M 的并置率為1。例1 模式c 中花店的并置率為1.5，說明在一個醫院實例周圍平均出現1.5個花店與其相鄰。

定義6 模式并置值。c 為n 階基于特征M 的加權co-location 模式，c 的并置值定義為M 的加權參與率與其所有特征并置率平均值的乘積，計算式表示為：

基于M 的加權co-location 模式并置值反映了地理空間中基于特征M 出現模式特征實例并置的可能性，模式并置值越大，在地理空間中出現該種模式實例并置的可能性越高，模式在特定領域的指導性越強。

例2 給定特征A、B、C 的實例數為5、10、10，查詢所得模式｛A，B｝、｛A，B，C｝表實例見表1。

表1 co-location 模式表實例示例

模式｛A，B｝基于A 的并置值為0.6，該模式表實例中3 個特征A 實例鄰接了3 個特征B 的實例。模式｛A，B，C｝基于A 的并置值為0.67，該模式表實例中3 個特征A 實例鄰接了3 個特征B 實例，且鄰接了4 個特征C 的實例，基于特征A 的模式｛A，B，C｝指導性高于基于A 的模式｛A，B｝。

2 WCPBSF 挖掘算法

WCPBSF 挖掘算法基于星型鄰居模型，采用無連接的co-location 模式挖掘方法，用實例近鄰關系查詢方法代替實例連接操作。算法檢測含指定特征的候選模式是否為WCPBSF，相對于特征集中所有頻繁模式挖掘的算法，本算法僅檢測模式中含指定特征的候選模式，提升了算法時間復雜度，且挖掘結果具領域驅動性，減少了在特定應用領域下對挖掘結果的再處理。在數據預處理階段隨機生成空間實例集，計算實例間距離，查詢得實例集的星型鄰居集。算法基于實例星型鄰居集查詢候選模式對應的星型表實例集，計算模式的星型參與度，進行第一次過濾。從模式的星型表實例集中去除候選模式中實例間不互相近鄰的星型行實例，生成候選模式的表實例集，根據式（3）和式（4）計算候選模式基于指定特征的加權參與度，進行第二次過濾，挖掘得WCPBSF。根據式（6）計算WCPBSF 并置值，提供給用戶用于評價模式的指導性。

算法描述如下：

輸入：特征集F、特征數n、指定特征M、加權參與度閾值e、距離閾值w、實例集的星型鄰居集N

輸出：基于特征M 的WCPBSF、模式加權參與度、模式并置值算法步驟：

第1 步：產生一個含M 的特征子集→c。

第2 步：若c 是候選模式（新的子集），則轉第3步，否則算法結束。

第3 步：查詢c 的星型表實例集。

第4 步：計算c 的星型參與度，若大于等于e 則轉第5 步，否則轉第8 步。

第5 步：查詢c 的表實例集。

第6 步：計算c 中每一特征的權以及特征的加權參與率，得c 的加權參與度。

第7 步：若c 的加權參與度超過閾值e，則c 是基于M 的WCPBSF，計算c 的模式并置值并輸出。

第8 步：產生一個含M 的特征子集→c，轉第2步。

設特征集中的特征數為n，其實例集中實例的星型鄰居數最多為m，c 的星型表實例集行數最多為a，c 的表實例集行數最多為u，算法檢測2n-1個候選模式，候選模式的表實例集查詢復雜度為mn，模式表實例集查詢時間復雜度為，加權參與率計算時間復雜度為u×n，不計特征加權參與率計算時間，則算法時間復雜度為O（2n-1mn）。

3 WCPBSF 挖掘算法與co-location 模式挖掘算法挖掘結果

例3 算法挖掘結果。給定特征集｛A，B，C｝、5個不同的特征實例集（不同的實例數及不同的實例近鄰關系），給定co-location 挖掘算法參與度閾值0.4，WCPBSF 挖掘算法加權參與度閾值0.6，用colocation 模式挖掘算法挖掘co-location 模式｛A，B，C｝，用WCPBSF 挖掘算法挖掘基于特征A 的WCPBSF 模式｛A，B，C｝，挖掘結果見表2。

表2 co-location 模式挖掘算法與WCPBSF 挖掘算法挖掘結果

挖掘結果分析如下：

（1）實例集1 中模式｛A，B，C｝是co-location 模式，由于模式中含特征A，稱其為包含特征A 的colocation 模式；由WCPBSF 挖掘算法也將該模式判定為基于特征A 的WCPBSF。實例集2 中的｛A，B，C｝ 不是co-location 模式，但它是基于A 的WCPBSF。實例集4 中的｛A，B，C｝不是co-location模式，也不是基于特征A 的WCPBSF，但該模式其實是基于特征B 的WCPBSF，也是基于特征C 的WCPBSF。實例集5 中的模式｛A，B，C｝是co-location模式，也是基于特征A 的WCPBSF。

（2）上述3 個基于特征A 的WCPBSF 并置值則反映了模式的可指導性，基于特征A 的WCPBSF 模式1 的并置值最大，出現模式實例并置的概率最大。

（3）實例集3 中模式｛A，B，C｝不是co-location模式，雖然特征B 和特征C 基于特征A 的并置率較高，平均一個特征A 實例并置3 個特征B 實例、4 個特征C 實例，但由于指定特征A 的實例參與率太小，僅為0.3，模式不具備頻繁性，故該模式不是基于特征A 的WCPBSF。

4 算法驗證

算法驗證數據集為隨機生成的合成數據，實例位置在4 000×4 000 坐標之內隨機生成，特征實例數在0 到之內隨機生成。實驗驗證了3個算法：①co-location 模式挖掘算法（算法①）。算法挖掘特征實例集中所有的頻繁模式。②含指定特征的co-location 模式挖掘算法（算法②）。給定特征集中某一特征，算法僅挖掘實例集中含該特征的頻繁模式。③WCPBSF 挖掘算法（算法③）。給定特征集中某一特征，算法挖掘實例集中基于該特征的加權頻繁模式。算法中模式表實例查詢采用基于星型鄰居模型的無連接方法。

（1）給定距離閾值100，參與度閾值0.2，加權參與度閾值0.6，特征數10，驗證總實例數對算法效率的影響，實驗結果見表3。

表3 總實例數對算法運行時間的影響

由于算法①挖掘特征集中的所有頻繁模式，算法②和算法③僅在包含指定特征的特征子集中挖掘，算法②和算法③的時間復雜度低于算法①。實驗結果表明，算法②和算法③的運行時間較算法①少，3 種算法在給定特征數不變的情況下，隨著特征實例數遞增，算法運行時間遞增。但從應用驅動的角度看，算法②和算法③挖掘結果具應用驅動性。

（2）給定距離閾值100，參與度閾值0.2，加權參與度閾值0.6，實例總數10 000，驗證特征總數對算法效率的影響，實驗結果見表4。

表4 特征總數對算法運行時間的影響

給定總實例數不變，隨著特征總數增加，特征實例數遞減，但3 種算法的運行時間總體呈遞增趨勢。在10 個特征與12 個特征之間，特征數增加，總實例數不變，特征實例數減少，算法運行時間有略微遞減。

（3）給定距離閾值100，特征數10，總實例數10 000，驗證參與度（加權參與度）閾值對挖掘結果的影響，實驗結果見表5。

表5 參與度（加權參與度）閾值對算法挖掘所得頻繁模式數量的影響

若給定距離閾值不變，隨著參與度（加權參與度）閾值增大，挖掘所得頻繁模式數量應該減少。實驗結果表明，3 種算法挖掘所得頻繁模式數量均隨參與度（加權參與度）閾值的增大而相應遞減。實驗中隨機生成的指定特征的實例數較少，挖掘到含該指定特征的co-location 模式數量較少，挖掘結果和算法①挖掘所得的模式中包含指定特征的模式結果一致。但算法③在不同的參與度閾值下均有效挖掘到基于該指定特征的加權頻繁模式，算法③有效性明顯。

（4）給定參與度閾值0.2，加權參與度閾值0.6，特征數10，總實例數10 000，驗證距離閾值對挖掘結果的影響，實驗結果見表6。

表6 距離閾值對算法挖掘所得頻繁模式數量的影響

給定參與度（加權參與度）閾值不變，隨著距離閾值增大，實例的星型鄰居數量增加，挖掘到的頻繁模式數量應該遞增，實驗結果表明，算法①和算法③隨著距離閾值的增大，挖掘所得的頻繁模式數量遞增。由于本次實驗中隨機生成的指定特征的實例數較少，算法②未挖掘到含該指定特征的co-location模式，其挖掘結果和算法①挖掘結果是吻合的，而算法③有效挖掘到WCPBSF，算法③有效性明顯。

（5）給定距離閾值100，加權參與度閾值0.4，特征總數10 ，總實例數10 000，指定特征1，驗證基于指定特征1 的WCPBSF 參與度的反單調性及模式并置值，實驗結果見表7。

表7 WCPBSF 挖掘算法挖掘所得頻繁模式的加權參與度及其模式并置值

算法③挖掘到20 條基于指定特征1 的WCPBSF，模式在基于特征1 的應用領域具指導性。挖掘所得頻繁模式的加權參與度值隨著模式階數的增大而單調遞減。模式｛1，7｝基于特征1 的并置值最大，指導性最強；模式｛1，3｝基于特征1 的并置值最小，指導性最弱。模式｛1，5，7｝及｛1，2，10｝的加權參與度均為0.48，模式并置值較大的｛1，5，7｝基于特征1 的指導性更強。

在挖掘co-location 模式時，若實例集中部分特征實例數量較多，在模式中的參與實例數量不夠多而使得特征的參與率小，模式界定為非頻繁模式，但模式基于指定特征具并置頻繁性及指導性。本研究提出一種WCPBSF 挖掘方法，算法合理挖掘WCPBSF，挖掘所得模式適用于特定應用領域，模式并置值評估基于指定特征的模式實例出現并置的可能性，可用于評價模式的指導性。算法挖掘所得模式具應用驅動性，算法時間復雜度理想，實驗結果驗證了算法的時間效率及挖掘結果的有效性。