基于指定特征的加權(quán)co-location 模式挖掘方法

趙秦怡，黑邵敏

（大理大學(xué)數(shù)學(xué)與計(jì)算機(jī)學(xué)院，云南大理 671003）

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

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

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

1 WCPBSF 挖掘方法

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

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

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

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

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

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

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

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

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

一個(gè)高階co-location 模式的子模式均為colocation 模式〔4〕，本研究中一個(gè)高階基于特征M 的WCPBSF 的低階基于特征M 子模式均為基于M 的WCPBSF，即WCPBSF 的加權(quán)參與度滿足隨著模式階數(shù)的增大而單調(diào)遞減，證明如下：設(shè)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?。組，有WPR（fi，cm）＝1，當(dāng)B（fi，cm+1）≥NM，WPR（fi，cm+1）＝1，當(dāng)B（fi，cm+1）＜NM，則，故WPR（cm）≥WPR（cm+1）成立；③若Bfi＜NM且fi?。組，，由于B（fi+1，cm+1）＜NM，則WPR，故WPR（cm）≥WPR（cm+1）成立。

定義5 相對(duì)于M 的特征并置率。設(shè)M 為指定特征，特征fi相對(duì)于M 的特征并置率定義為fi的表實(shí)例數(shù)與M 的表實(shí)例數(shù)的比率。計(jì)算式表示為：

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

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

基于M 的加權(quán)co-location 模式并置值反映了地理空間中基于特征M 出現(xiàn)模式特征實(shí)例并置的可能性，模式并置值越大，在地理空間中出現(xiàn)該種模式實(shí)例并置的可能性越高，模式在特定領(lǐng)域的指導(dǎo)性越強(qiáng)。

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

表1 co-location 模式表實(shí)例示例

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

2 WCPBSF 挖掘算法

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

算法描述如下：

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

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

第1 步：產(chǎn)生一個(gè)含M 的特征子集→c。

第2 步：若c 是候選模式（新的子集），則轉(zhuǎn)第3步，否則算法結(jié)束。

第3 步：查詢c 的星型表實(shí)例集。

第4 步：計(jì)算c 的星型參與度，若大于等于e 則轉(zhuǎn)第5 步，否則轉(zhuǎn)第8 步。

第5 步：查詢c 的表實(shí)例集。

第6 步：計(jì)算c 中每一特征的權(quán)以及特征的加權(quán)參與率，得c 的加權(quán)參與度。

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

第8 步：產(chǎn)生一個(gè)含M 的特征子集→c，轉(zhuǎn)第2步。

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

3 WCPBSF 挖掘算法與co-location 模式挖掘算法挖掘結(jié)果

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

表2 co-location 模式挖掘算法與WCPBSF 挖掘算法挖掘結(jié)果

挖掘結(jié)果分析如下：

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

（2）上述3 個(gè)基于特征A 的WCPBSF 并置值則反映了模式的可指導(dǎo)性，基于特征A 的WCPBSF 模式1 的并置值最大，出現(xiàn)模式實(shí)例并置的概率最大。

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

4 算法驗(yàn)證

算法驗(yàn)證數(shù)據(jù)集為隨機(jī)生成的合成數(shù)據(jù)，實(shí)例位置在4 000×4 000 坐標(biāo)之內(nèi)隨機(jī)生成，特征實(shí)例數(shù)在0 到之內(nèi)隨機(jī)生成。實(shí)驗(yàn)驗(yàn)證了3個(gè)算法：①co-location 模式挖掘算法（算法①）。算法挖掘特征實(shí)例集中所有的頻繁模式。②含指定特征的co-location 模式挖掘算法（算法②）。給定特征集中某一特征，算法僅挖掘?qū)嵗泻撎卣鞯念l繁模式。③WCPBSF 挖掘算法（算法③）。給定特征集中某一特征，算法挖掘?qū)嵗谢谠撎卣鞯募訖?quán)頻繁模式。算法中模式表實(shí)例查詢采用基于星型鄰居模型的無連接方法。

（1）給定距離閾值100，參與度閾值0.2，加權(quán)參與度閾值0.6，特征數(shù)10，驗(yàn)證總實(shí)例數(shù)對(duì)算法效率的影響，實(shí)驗(yàn)結(jié)果見表3。

表3 總實(shí)例數(shù)對(duì)算法運(yùn)行時(shí)間的影響

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

（2）給定距離閾值100，參與度閾值0.2，加權(quán)參與度閾值0.6，實(shí)例總數(shù)10 000，驗(yàn)證特征總數(shù)對(duì)算法效率的影響，實(shí)驗(yàn)結(jié)果見表4。

表4 特征總數(shù)對(duì)算法運(yùn)行時(shí)間的影響

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

（3）給定距離閾值100，特征數(shù)10，總實(shí)例數(shù)10 000，驗(yàn)證參與度（加權(quán)參與度）閾值對(duì)挖掘結(jié)果的影響，實(shí)驗(yàn)結(jié)果見表5。

表5 參與度（加權(quán)參與度）閾值對(duì)算法挖掘所得頻繁模式數(shù)量的影響

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

（4）給定參與度閾值0.2，加權(quán)參與度閾值0.6，特征數(shù)10，總實(shí)例數(shù)10 000，驗(yàn)證距離閾值對(duì)挖掘結(jié)果的影響，實(shí)驗(yàn)結(jié)果見表6。

表6 距離閾值對(duì)算法挖掘所得頻繁模式數(shù)量的影響

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

（5）給定距離閾值100，加權(quán)參與度閾值0.4，特征總數(shù)10 ，總實(shí)例數(shù)10 000，指定特征1，驗(yàn)證基于指定特征1 的WCPBSF 參與度的反單調(diào)性及模式并置值，實(shí)驗(yàn)結(jié)果見表7。

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

算法③挖掘到20 條基于指定特征1 的WCPBSF，模式在基于特征1 的應(yīng)用領(lǐng)域具指導(dǎo)性。挖掘所得頻繁模式的加權(quán)參與度值隨著模式階數(shù)的增大而單調(diào)遞減。模式｛1，7｝基于特征1 的并置值最大，指導(dǎo)性最強(qiáng)；模式｛1，3｝基于特征1 的并置值最小，指導(dǎo)性最弱。模式｛1，5，7｝及｛1，2，10｝的加權(quán)參與度均為0.48，模式并置值較大的｛1，5，7｝基于特征1 的指導(dǎo)性更強(qiáng)。

在挖掘co-location 模式時(shí)，若實(shí)例集中部分特征實(shí)例數(shù)量較多，在模式中的參與實(shí)例數(shù)量不夠多而使得特征的參與率小，模式界定為非頻繁模式，但模式基于指定特征具并置頻繁性及指導(dǎo)性。本研究提出一種WCPBSF 挖掘方法，算法合理挖掘WCPBSF，挖掘所得模式適用于特定應(yīng)用領(lǐng)域，模式并置值評(píng)估基于指定特征的模式實(shí)例出現(xiàn)并置的可能性，可用于評(píng)價(jià)模式的指導(dǎo)性。算法挖掘所得模式具應(yīng)用驅(qū)動(dòng)性，算法時(shí)間復(fù)雜度理想，實(shí)驗(yàn)結(jié)果驗(yàn)證了算法的時(shí)間效率及挖掘結(jié)果的有效性。