含關(guān)鍵特征的顯著Co-location模式挖掘研究

方 圓 王麗珍 周麗華

(云南大學(xué)信息學(xué)院，昆明，650091)

引 言

空間Co-location模式(并置模式)挖掘是空間數(shù)據(jù)挖掘的重要分支，在地理科學(xué)、城市規(guī)劃、公共交通和環(huán)境保護(hù)等領(lǐng)域有著廣泛應(yīng)用。Co-location模式是一組在空間中頻繁關(guān)聯(lián)的空間特征的子集，如學(xué)校附近往往有文具店；長(zhǎng)苞冷衫樹(shù)下往往會(huì)有松茸生長(zhǎng)等?？臻gCo-location模式挖掘一般采用最小參與率(參與度)為度量標(biāo)準(zhǔn)的挖掘框架。將特征的參與率作為空間特征頻繁性的度量指標(biāo)，并使用參與度作為度量空間Co-location模式頻繁性的指標(biāo)，通過(guò)用戶指定的參與度閾值對(duì)Co-location頻繁模式進(jìn)行挖掘。當(dāng)參與度較高時(shí)，容易得到常識(shí)性結(jié)果。當(dāng)參與度較低時(shí)，則會(huì)產(chǎn)生大量頻繁但用戶不感興趣的模式，使得用戶難以理解和識(shí)別有用的知識(shí)。

另外，雖然基于最小參與度的Co-location頻繁模式挖掘體系能夠較好地反映出空間特征并置的頻繁程度，但由于計(jì)算模式特征參與率、參與度的過(guò)程中，沒(méi)有考慮到空間實(shí)例之間的相互作用，如空間實(shí)例間的互相關(guān)性等，僅僅依靠參與率無(wú)法幫助用戶挖掘到模式中特征之間的關(guān)系。例如：對(duì)于頻繁模式{醫(yī)院，藥店，花店}，特征“醫(yī)院”、“藥店”和“花店”的參與率分別是0.65，0.5和0.8。對(duì)模式頻繁性貢獻(xiàn)最高的是“花店”特征，事實(shí)上，“醫(yī)院”是模式{醫(yī)院，藥店，花店}形成的關(guān)鍵因素。這說(shuō)明僅僅依靠參與率無(wú)法判斷醫(yī)院對(duì)其他兩個(gè)特征的影響。另外，按照基于最小參與率的類Apriori 逐階挖掘頻繁模式的方法，子模式{藥店，花店}必將作為一個(gè)頻繁模式提供給用戶，可能對(duì)用戶造成誤導(dǎo)。

基于以上思考，在挖掘到的大量頻繁Co-location模式結(jié)果集中，進(jìn)一步識(shí)別含有關(guān)鍵特征的模式，并摘取關(guān)鍵特征，將有效提高挖掘到的頻繁模式的可用性，方便用戶對(duì)挖掘結(jié)果的理解和使用。然而現(xiàn)有的參與率-參與度度量無(wú)法標(biāo)識(shí)含有關(guān)鍵特征的頻繁模式，也無(wú)法識(shí)別頻繁模式中的關(guān)鍵特征。因此，本文提出空間Co-location模式的關(guān)鍵特征新概念；給出識(shí)別含有關(guān)鍵特征的頻繁模式及摘取關(guān)鍵特征的方法。

識(shí)別空間Co-location 模式的關(guān)鍵特征主要存在兩方面的挑戰(zhàn)。目前的方法主要關(guān)注于尋找模式中特征實(shí)例的頻繁并置，忽略了不同特征對(duì)模式貢獻(xiàn)的差異。因此，如何定義和度量含有關(guān)鍵特征的Co-location頻繁模式及其關(guān)鍵特征是第一個(gè)挑戰(zhàn)。面對(duì)挖掘到的大量Co-location模式，如何高效地挖掘含有關(guān)鍵特征的Co-location模式及關(guān)鍵特征集是第二個(gè)挑戰(zhàn)。

1 相關(guān)工作

空間 Co-location 模式挖掘最早由 Huang[1]等提出，他們形式化定義了空間鄰近關(guān)系、行實(shí)例、表實(shí)例、參與率以及參與度等概念，并提出了基于完全連接(Join-based)的空間Co-location模式挖掘算法。為解決Join-based算法中連接操作開(kāi)銷巨大的問(wèn)題，基于部分連接(Partial-join)算法[2]和基于星型鄰居擴(kuò)展的無(wú)連接(Join-less)算法[3]被相繼提出，這兩種算法有效地減少了實(shí)例連接操作，算法效率在稠密數(shù)據(jù)集上均優(yōu)于Join-based算法。研究人員對(duì)無(wú)連接Co-location挖掘方法進(jìn)行進(jìn)一步研究，提出了基于前綴樹(shù)的挖掘算法：CPI-tree(Co-location pattern instances tree)算法[4]、ICPI-tree 算法[5]和Order-Clique-Based算法[6]。其中，Order-Clique-Based算法在優(yōu)化前綴樹(shù)結(jié)構(gòu)的基礎(chǔ)上，通過(guò)生成候選極大 Co-location 模式和表實(shí)例，避免了存儲(chǔ)所有侯選模式表實(shí)例產(chǎn)生的計(jì)算開(kāi)銷，從而顯著地提高了挖掘效率。由于Co-location模式挖掘的廣泛應(yīng)用需求，研究人員提出了不同數(shù)據(jù)類型上的Co-location模式挖掘算法。針對(duì)不確定數(shù)據(jù)，Wang等[7]提出了不確定數(shù)據(jù)集上概率頻繁的空間 Co-location 模式挖掘方法。針對(duì)模糊數(shù)據(jù)，歐陽(yáng)志平等[8]提出了模糊參與率及模糊參與度概念來(lái)挖掘模糊數(shù)據(jù)的空間 Co-location 模式。針對(duì)變化的數(shù)據(jù)集，蘆俊麗等[9]提出了空間 Co-location 模式增量挖掘并給出一系列挖掘算法。在針對(duì)特定目標(biāo)的Co-location挖掘方面，Huang等[10]引入最大參與率概念解決帶稀有特征的Co-location模式的挖掘問(wèn)題；周劍云等[11]引入加權(quán)參與率(度)研究了基于加權(quán)歐氏距離的空間Co-location模式挖掘算法。為了有效地縮減頻繁Co-location模式結(jié)果，去除冗余，閉Co-location模式挖掘算法[12]，Co-location代表模式挖掘算法[13]等縮減模式結(jié)果的算法被提出。然而以上數(shù)據(jù)驅(qū)動(dòng)的Co-location挖掘方法通常只依賴于數(shù)據(jù)和挖掘算法，忽略了數(shù)據(jù)特定的領(lǐng)域和用戶的偏好，挖掘結(jié)果往往概括性差、無(wú)針對(duì)性，且包含大量用戶不感興趣的知識(shí)。為提高模式的可用性，研究人員在基于領(lǐng)域驅(qū)動(dòng)的空間數(shù)據(jù)挖掘方面做出了大量的工作。楊世晟等[14]提出了高效用Co-location模式挖掘，蘆俊麗等[15]則研究了高效用Co-location 模式的增量挖掘。包旭光等提出了基于領(lǐng)域本體的Co-location規(guī)則挖掘方法[16]，F(xiàn)ang等提出了組合Co-location模式挖掘方法[17]，得到了更加精簡(jiǎn)有效的模式結(jié)果。

上述研究工作假設(shè)空間數(shù)據(jù)滿足實(shí)例之間的獨(dú)立性，然而在現(xiàn)實(shí)中，空間數(shù)據(jù)往往是高度相關(guān)的，例如時(shí)空軌跡數(shù)據(jù)挖掘[18]、基于社會(huì)媒體的旅游數(shù)據(jù)挖掘[19]等。本文工作考慮空間特征及實(shí)例之間的耦合關(guān)系[20-22]，研究了含有關(guān)鍵特征的空間Co-location模式及其關(guān)鍵特征的挖掘和識(shí)別。

2 基本概念及相關(guān)定義

2.1 基本概念

圖1 1個(gè)空間實(shí)例集Fig．1 A data set

圖2 一部分頻繁模式表實(shí)例Fig．2 Table instances of prevalent Co-location patterns

引理1[1]：(參與率與參與度的向下閉合性)參與率(PR)和參與度(PI)隨著Co-location模式階的增大單調(diào)遞減。

傳統(tǒng)Co-location挖掘沒(méi)有考慮到特征之間、實(shí)例之間的耦合關(guān)系，本文通過(guò)分析頻繁模式與其子模式間的關(guān)系、模式中特征內(nèi)部實(shí)例間的關(guān)系和特征之間不同實(shí)例的關(guān)系，挖掘含有關(guān)鍵特征的模式，并識(shí)別關(guān)鍵特征。

2.2 相關(guān)定義

傳統(tǒng)Co-location挖掘算法采用參與率度量特征在模式中的作用。然而，這樣的度量只考慮單個(gè)特征的實(shí)例參與到模式中的比例，沒(méi)有考慮到特征和實(shí)例之間的相互作用。為了描述特征之間的相互作用，本文通過(guò)頻繁模式與其所有直接子模式的參與率變化來(lái)分析新特征加入時(shí)，新特征對(duì)該模式中其他特征的影響。

定義1(參與損失率和參與損失度)

給定一個(gè)k(k>2)階頻繁Co-location模式c，設(shè)c′是c的一個(gè)k-1階子模式，如果fi是c和c′的公共特征，fi關(guān)于c′和c的參與損失率(Participation_Loss_Ratio)定義為

PLR(c,c′,fi)=PR(c′,f)-PR(c,f)

(1)

引理1保證了0≤PLR(c,c′,fi)≤PR(c′,f)。

模式c對(duì)于模式c′的參與損失度(Participation_Loss_Index)PLI(c,c′)定義為兩個(gè)模式中所有公共特征fi的PLR(c,c′,fi)值中的最小值：PLI(c,c′)=min{PLR(c,c′,fi)}

例2Co-location模式{B,C,D}及其子模式{B,C}的表實(shí)例如圖2所示，則模式{B,C,D}對(duì)于模式{B,C}的參與損失度PLI({B,C,D},{B,C})為

(2)

模式參與損失率指的是特征fi從模式c′到模式c損失的參與率，損失率越小，說(shuō)明c′參與到c中的行實(shí)例越多，其脫離fk的實(shí)例單獨(dú)存在的行實(shí)例就越少，c′中的特征對(duì)特征fk的依賴越強(qiáng)。

Co-location模式的參與損失度通過(guò)分別計(jì)算特征參與在k階Co-location模式c與其子模式c′的投影個(gè)數(shù)，得到c′模式隨著新的特征fk加入形成模式c時(shí)其表實(shí)例的變化。其變化的程度體現(xiàn)fk對(duì)c′中特征的影響程度，即模式c中其他特征對(duì)fk的依賴程度。當(dāng)模式中各特征對(duì)模式的貢獻(xiàn)值有差異時(shí)，說(shuō)明模式中特征地位不平等。容易觀察到，對(duì)于含有關(guān)鍵特征的頻繁Co-location模式，由于關(guān)鍵特征是使模式頻繁的主要因素鍵特征對(duì)模式的貢獻(xiàn)高于模式內(nèi)其他特征。本文中，組成該模式的特征在模式中地位必然不平等，關(guān)提出模式顯著性定量地度量含有關(guān)鍵特征的頻繁Co-location模式。

定義2(顯著Co-location模式)

給定1個(gè)k(k≥2)階頻繁Co-location模式c={ f1, f2，…, fk}，其k個(gè)k-1階子模式集記為Ck-1，設(shè)Pi(1≤i≤k，Pi∈Ck-1)為c的任一k-1階子模式，則Co-location模式的顯著性CDS(c)定義為

(3)

設(shè)min_cds(0≤min_cds≤1)是用戶給定的最小顯著性閾值，當(dāng)CDS(c)≥min_cds時(shí)，稱Co-location模式c是一個(gè)顯著模式。

定義2合理性說(shuō)明：PLI(c,c′)值越大，特征f∈c-c′的實(shí)例參與到模式c′的鄰近關(guān)系中的比例越高，即f與c′中特征形成團(tuán)的行實(shí)例比c′行實(shí)例中不與c′形成團(tuán)的行實(shí)例越多，則f對(duì)模式c′中特征影響越大。反之，PLI(c,c″)值越小，說(shuō)明特征f′ ∈c- c″的實(shí)例參與到模式c″中特征實(shí)例的鄰近關(guān)系越少，即f′對(duì)模式c″中特征的影響越小。模式顯著性越大，則模式c中至少有兩個(gè)特征f與f′ 對(duì)模式的貢獻(xiàn)度相差越大，即模式內(nèi)特征地位對(duì)比越鮮明，越有可能含有關(guān)鍵特征。閾值的設(shè)定是為區(qū)分不同用戶或不同應(yīng)用對(duì)關(guān)鍵特征判定的差異。

例3模式{B,C,D}及其子模式{B,C}，{B,D}，{C,D}的表實(shí)例如圖2，設(shè)min_cds=0.2，PLI({B,C,D},{B,C})=0，PLI({B,C,D},{B,D})=0.25,PLI({B,C,D},{C,D})=0.2，模式{B,C,D}的模式顯著性為：CDS({B,C,D})=0.25≥min_cds，則稱模式{B,C,D}是一個(gè)顯著的Co-location模式。

通過(guò)模式顯著性閾值產(chǎn)生的顯著Co-location模式篩選出了頻繁Co-location模式中含有關(guān)鍵特征的Co-location模式，然而，模式中哪些特征為關(guān)鍵特征還需進(jìn)一步分析。

空間特征之間和實(shí)例之間存在差異性是Co-location關(guān)鍵特征摘取的基礎(chǔ)。下面通過(guò)同一特征的實(shí)例在表實(shí)例中出現(xiàn)的頻率及不同特征間實(shí)例的相互影響對(duì)模式中特征的重要程度進(jìn)行度量。

定義3(特征重復(fù)率)

給定一個(gè)k階頻繁Co-location模式c={f1,f2,…,fk}，該模式表實(shí)例為T(c)，T(c)中行實(shí)例的集合為L(zhǎng)={l1, l2,…, lt}，特征 fi∈c在T(c)中的重復(fù)率RR(Repeat_ratio)定義為

(4)

例4如圖2 {B,C,D}的表實(shí)例中，特征D的實(shí)例在T({B,C,D})中的重復(fù)率為

(5)

式中：πfi(T(c))代表特征fi在T(c)中的投影，L代表行實(shí)例的全集，其比值表示fi在表實(shí)例中不重復(fù)出現(xiàn)的程度。特征的重復(fù)率刻劃了該特征在模式中對(duì)其他特征的依賴程度，即特征重復(fù)率越高，該特征相同實(shí)例參與的行實(shí)例越多，對(duì)模式的貢獻(xiàn)越大，且該特征在模式中受到其他特征的影響越小。換言之，特征模式度量了該特征在模式中受到的影響。

為進(jìn)一步觀察模式中特征之間的相互作用，通過(guò)統(tǒng)計(jì)各個(gè)特征對(duì)模式內(nèi)其他特征的影響度分析特征對(duì)模式中其他特征造成的影響。

為方便表示一個(gè)Co-location表實(shí)例中各實(shí)例間的關(guān)系，首先提出一個(gè)特征間實(shí)例映射函數(shù)：

?Ik}

(6)

定義4(特征影響度)

給定一個(gè)k階頻繁Co-location模式c ={f1, f2…, fk}，該模式表實(shí)例為T(c)，T(c)中各個(gè)特征實(shí)例的集合為I={I1,I2,…,Ik}，則特征fi對(duì)整個(gè)模式c的影響度(Co-location effect index,CEI)定義為

(7)

例6如圖2中，特征D對(duì)模式{B,C,D}的影響度CEI({B,C,D},D)為

(8)

定義5(特征關(guān)鍵度和模式關(guān)鍵度)

給定一個(gè)候選k階Co-location頻繁模式c ={f1, f2，…, fk}，特征fi在c中的關(guān)鍵度定義為

KR(c,fi)=CEI(c,fi)×(RR(c,fi)+1)

(9)

3 相關(guān)算法

本文提出了一個(gè)Co-location關(guān)鍵特征挖掘框架，通過(guò)模式與模式之間、空間特征之間和實(shí)例之間的相互影響，對(duì)含有關(guān)鍵特征的Co-location模式及其關(guān)鍵特征集進(jìn)行挖掘。為了減少計(jì)算表實(shí)例的巨大開(kāi)銷，對(duì)于一個(gè)Co-location頻繁模式集中的任意一個(gè)Co-location模式，首先分析其直接子模式集與該模式的關(guān)系，基于頻繁模式進(jìn)行顯著性分析，得到顯著Co-location模式集合；然后，對(duì)顯著Co-location模式集中的任意一個(gè)Co-location模式，分析特征內(nèi)部實(shí)例間的相關(guān)性及不同特征的實(shí)例之間的相關(guān)性；在給出一系列度量對(duì)模式及其關(guān)鍵特征進(jìn)行評(píng)價(jià)，最后得到含有關(guān)鍵特征的Co-location模式及其關(guān)鍵特征集。

3.1 顯著Co-location模式挖掘

根據(jù)用戶給定的最小顯著性閾值min_cds，從所有頻繁Co-location模式中挖掘出顯著Co-location模式。最直接的方法是在挖掘到的頻繁Co-location模式集上進(jìn)行2次挖掘。然而，由于計(jì)算一個(gè)Co-location模式的顯著性需要用到該模式和其直接子模式的表實(shí)例，當(dāng)數(shù)據(jù)量較大時(shí)，表實(shí)例的存儲(chǔ)耗費(fèi)了大量存儲(chǔ)空間，為了提高計(jì)算效率，將顯著性計(jì)算融入到頻繁Co-location模式的挖掘過(guò)程中，以避免存儲(chǔ)及輸出所有頻繁模式表實(shí)例帶來(lái)的巨大內(nèi)存耗費(fèi)和I/O開(kāi)銷。具體見(jiàn)類似Join-less的算法1。

算法1SK算法

輸入：空間數(shù)據(jù)集S，空間特征集F，空間實(shí)例集I，距離閾值 d，最小參與度閾值min_prev，顯著性閾值min_cds

輸出：顯著Co-location頻繁模式集SCP

變量：k :Co-location模式的階, Ck:k 階 Co-location 候選頻繁模式集, Pk: k 階 Co-location 頻繁模式集, PR_c: k 階Co-location頻繁模式c的參與率集

步驟：

1. SN=gen_star_neighborhoods(F,S,d);//生成星型鄰居集

2. P1=F, k = 2, SCP=?;

3. WHILE(Pk-1≠?)DO

4. Ck= gen_candidate_colocation(k,Pk-1)//生成k階候選

5. FOR EACH c∈CkDO

6. IF calculate PI(c) ≥min_prev DO//計(jì)算模式參與度

7. FOR EACH p∈Pk-1(c) DO

8. calculate PLI(c, p);//計(jì)算模式損失度

9. END DO

10. IF calculate CDS (c) ≥min_cds DO//計(jì)算顯著性

11. keyset(c)←sel _key_f(c, Table_ins (c),min_key); //摘取關(guān)鍵特征

12. SCP←{c,keyset(c)};

13. END DO

14. END DO

15. END DO

16. k= k+1;

17. END DO

行1根據(jù)距離閾值生成星型實(shí)例集；行2—4生成 k 階 Co-location 候選模式集；行5—15描述含有關(guān)鍵特征的頻繁模式識(shí)別及關(guān)鍵特征摘取過(guò)程：行5—6計(jì)算參與度；行7—9對(duì)于滿足參與度閾值的模式，與該模式的直接子模式集合計(jì)算模式損失度；行10中，若得到的模式顯著性大于給定的顯著性閾值min_cds，那么行11計(jì)算其關(guān)鍵特征集；行12將含有關(guān)鍵特征的頻繁模式及其關(guān)鍵特征進(jìn)行存儲(chǔ)；隨著Co-location模式階數(shù)的增長(zhǎng)，行3—16被反復(fù)執(zhí)行，最后得到了顯著Co-location模式集合及其關(guān)鍵特征集。

3.2 Co-location關(guān)鍵特征摘取

該算法是算法1中關(guān)鍵特征摘取的子過(guò)程，通過(guò)分析顯著Co-location模式表實(shí)例中特征內(nèi)部實(shí)例之間的關(guān)系及不同特征的實(shí)例之間的影響，對(duì)模式的關(guān)鍵特征進(jìn)行摘取。根據(jù)這一思想，提出關(guān)鍵特征摘取算法。

算法2sel _key_f算法

輸入：顯著Co-location頻繁模式scp，Table_scp顯著Co-location頻繁模式的表實(shí)例，關(guān)鍵程度閾值min_key

輸出：顯著Co-location頻繁模式的關(guān)鍵特征集KeySet

變量：min_key:最小關(guān)鍵度閾值，Candidate_KeyF:關(guān)鍵特征候選集

步驟：

1. KeySet=?;

2. FOR EACH feature∈scp DO

3. calculate (RR(Table_scp , feature));//計(jì)算實(shí)例重復(fù)率

4. calculate (CEI(Table_scp，feature )); //計(jì)算特征影響度

5. calculate (KR(Table_scp，feature));//計(jì)算模式關(guān)鍵率

6. END DO

7. calculate(KI(scp))); 計(jì)算模式關(guān)鍵度

8. FOR EACH feature∈scp DO

9. IF(KR(Table_scp，feature)/ KI(scp)≥min_key)DO

10. KeySet (scp)←feature;//摘取關(guān)鍵特征

11. END DO

12.END DO

行1初始關(guān)鍵特征集合；行2—6描述了計(jì)算顯著Co-location模式scp中所有特征的關(guān)鍵度的過(guò)程：行3計(jì)算scp中特征內(nèi)部實(shí)例重復(fù)率；行4計(jì)算scp中特征對(duì)模式的關(guān)鍵度；行5計(jì)算所有特征的關(guān)鍵率；循環(huán)執(zhí)行2—6行直至計(jì)算完所有特征的關(guān)鍵率；行7根據(jù)所有特征的關(guān)鍵率得到模式關(guān)鍵度；行8—9測(cè)試關(guān)鍵特征；行10將關(guān)鍵率大于最小關(guān)鍵度閾值的特征加入關(guān)鍵特征集合中；循環(huán)行8—12得到所有關(guān)鍵度超過(guò)最小關(guān)鍵閾值的特征。

4 實(shí)驗(yàn)與分析

本節(jié)將在合成數(shù)據(jù)和真實(shí)數(shù)據(jù)上詳細(xì)地驗(yàn)證算法的效率和效果。實(shí)驗(yàn)評(píng)估主要從以下幾方面進(jìn)行：SK算法在不同數(shù)據(jù)集上的性能分析；SK算法與經(jīng)典的Join_less頻繁模式挖掘算法[3]的實(shí)驗(yàn)效果比較；空間關(guān)鍵特征挖掘算法在真實(shí)數(shù)據(jù)上的應(yīng)用。所有算法均在core i3,2.4 GHz CPU和8GB 內(nèi)存的 PC 機(jī)上用 C#語(yǔ)言實(shí)現(xiàn)。

本文一共選取了4個(gè)不同規(guī)模的合成數(shù)據(jù)集和2個(gè)真實(shí)數(shù)據(jù)集驗(yàn)證算法的性能及挖掘效果。真實(shí)數(shù)據(jù)集分別來(lái)自北京市部分地區(qū)的POI數(shù)據(jù)和“三江并流區(qū)域”植被數(shù)據(jù)。北京市POI數(shù)據(jù)含有26 546個(gè)空間實(shí)例及16個(gè)空間特征，“三江并流區(qū)域”植被數(shù)據(jù)含有335個(gè)空間實(shí)例及32個(gè)空間特征。表 1 顯示了各數(shù)據(jù)集的大小、特征個(gè)數(shù)以及數(shù)據(jù)集的來(lái)源。實(shí)驗(yàn)所采用的合成數(shù)據(jù)均是根據(jù)泊松分布隨機(jī)產(chǎn)生，并均勻分布在 1 000 ×1 000 空間里。

本文將傳統(tǒng)Co-location頻繁模式的挖掘結(jié)果與本文提出的SK算法進(jìn)行比較，驗(yàn)證挖掘的效果。

4.1 合成數(shù)據(jù)集上的SK算法性能分析

本文在多個(gè)合成數(shù)據(jù)集上用空間 Co-location關(guān)鍵特征挖掘算法(SK算法)，與傳統(tǒng)挖掘算法的挖掘結(jié)果進(jìn)行實(shí)驗(yàn)比較。傳統(tǒng)算法采用了經(jīng)典的Join_less算法?？紤]實(shí)例個(gè)數(shù)、參與度閾值、距離閾值以及顯著性閾值對(duì)兩種算法的影響。表2顯示了合成數(shù)據(jù)實(shí)驗(yàn)中的默認(rèn)參數(shù)。

表2 實(shí)驗(yàn)數(shù)據(jù)的參數(shù)說(shuō)明

4.1.1 參與度閾值對(duì)SK算法的影響

本節(jié)考慮變化的最小參與度閾值對(duì)SK算法性能的影響。圖3顯示在0.2,0.3,0.4,0.5和0.6五個(gè)不同的距離閾值上運(yùn)行SK算法的性能。對(duì)于每個(gè)數(shù)據(jù)集，當(dāng)最小參與度閾值增大時(shí)，運(yùn)行時(shí)間逐漸減少。對(duì)于所有數(shù)據(jù)集，隨著數(shù)據(jù)規(guī)模的增加和最小參與度閾值的減少，其運(yùn)行時(shí)間逐漸增加。對(duì)于數(shù)據(jù)集dataset4，最小參與度閾值對(duì)算法性能的影響尤其明顯，這是因?yàn)樵陂撝递^低且數(shù)據(jù)較為稠密的情況下，模式的表實(shí)例較大，對(duì)表實(shí)例的運(yùn)算的耗費(fèi)影響了算法性能。

4.1.2 距離閾值對(duì)SK算法的影響

本節(jié)考慮變化的距離閾值對(duì)SK算法性能的影響。圖4顯示在10,20,30和40四個(gè)距離閾值上運(yùn)行SK算法的性能。對(duì)于每個(gè)數(shù)據(jù)集，當(dāng)距離閾值增大時(shí)，運(yùn)行時(shí)間逐漸減少。對(duì)于所有數(shù)據(jù)集，隨著數(shù)據(jù)規(guī)模和距離閾值的增加，其運(yùn)行時(shí)間逐漸增加。距離閾值較大時(shí)，算法性能的影響尤其明顯，這說(shuō)明算法性能主要受到數(shù)據(jù)稠密性的影響。

圖3 參與度閾值在不同數(shù)據(jù)集上的性能比較 圖4 距離閾值在不同合成數(shù)據(jù)集上的性能比較 Fig．3 Comparison of running time with different Fig. 4 Comparison of running time with different min_prev on synthesized data sets distance thresholds on synthesized data sets

4.1.3 顯著性閾值對(duì)SK算法的影響

本節(jié)考慮變化的顯著性閾值對(duì)SK算法性能的影響。圖5顯示在0.1,0.15,0.2和0.25四個(gè)顯著閾值上運(yùn)行SK算法的性能。對(duì)于每個(gè)數(shù)據(jù)集，當(dāng)顯著性閾值增大時(shí)，運(yùn)行時(shí)間減少較快。因?yàn)殡S著顯著性閾值的升高，需要計(jì)算的頻繁模式表實(shí)例減少，顯著性閾值的變化對(duì)稠密數(shù)據(jù)集上算法性能的影響更加明顯。

4.2 真實(shí)數(shù)據(jù)集上的SK算法與Join_less算法比較

在本節(jié)，本文將空間 Co-location關(guān)鍵特征挖掘算法與傳統(tǒng)挖掘算法的挖掘結(jié)果在真實(shí)數(shù)據(jù)上進(jìn)行實(shí)驗(yàn)比較。由于SK算法針對(duì)挖掘含有關(guān)鍵特征的模式，并非進(jìn)行低損失率的模式壓縮，相較于模擬數(shù)據(jù)，真實(shí)數(shù)據(jù)的挖掘結(jié)果更有實(shí)際意義。

4.2.1 SK算法在北京POI數(shù)據(jù)集上的結(jié)果比較

圖5 顯著性閾值在不同數(shù)據(jù)集上的 圖6 不同參與度閾值在POI數(shù)據(jù)集上的挖掘性能比較 效果比較Fig．5 Comparison of running time with different Fig. 6 Comparison of mining results with different min_cds on synthesized data sets min_prev on POI data set

圖6顯示POI數(shù)據(jù)在距離閾值為50，顯著性閾值為0.2，特征關(guān)鍵度為0.3的條件下通過(guò)變化的最小參與度閾值觀察SK算法產(chǎn)生含有關(guān)鍵特征的頻繁模式的結(jié)果。

圖7顯示POI數(shù)據(jù)參與度閾值為0.3，顯著性閾值為0.2，特征關(guān)鍵度為0.3的條件下通過(guò)距離閾值的變化觀察SK算法產(chǎn)生含有關(guān)鍵特征的頻繁模式的結(jié)果。

4.2.2 SK算法在植被數(shù)據(jù)集上的結(jié)果比較

圖8顯示植被數(shù)據(jù)在距離閾值為6 000，顯著性閾值為0.2，特征關(guān)鍵度為0.3的條件下通過(guò)最小參與度閾值的變化觀察SK算法產(chǎn)生含有關(guān)鍵特征的頻繁模式的結(jié)果。

圖7 不同距離閾值在POI數(shù)據(jù)集上的挖掘 圖8 不同參與度閾值在植被數(shù)據(jù)集上的挖掘效果比較 效果比較 Fig. 7 Comparison of mining results with different Fig. 8 Comparison of mining results with differentdistance thresholds on Beijing POI data set min_prev on vegetation data set

圖9 不同距離閾值在植被數(shù)據(jù)集上的挖掘效果比較 Fig．9 Comparison of mining results with different distance thresholds on vegetation data set

圖9顯示植被數(shù)據(jù)在最小參與度閾值為0.3，顯著性閾值為0.2，特征關(guān)鍵度為0.3的條件下通過(guò)距離閾值的變化觀察SK算法產(chǎn)生含有關(guān)鍵特征的頻繁模式結(jié)果。

4.3 實(shí)例分析

含有關(guān)鍵特征的Co-location模式挖掘目的是識(shí)別顯著性模式及其關(guān)鍵特征、縮減模式結(jié)果并提高模式的可用性。上述在模擬數(shù)據(jù)集和真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)已經(jīng)證明SK算法能夠有效地減少模式結(jié)果，使挖掘結(jié)果只留下含有關(guān)鍵特征的頻繁模式及其關(guān)鍵特征，因此，該方法更具有針對(duì)性和用戶實(shí)用性。

4.3.1 模式挖掘結(jié)果實(shí)例分析

本節(jié)在北京POI數(shù)據(jù)集上將頻繁模式挖掘結(jié)果與含有關(guān)鍵特征的模式挖掘結(jié)果進(jìn)行對(duì)比。通過(guò)實(shí)驗(yàn)結(jié)果可看出SK算法能夠有效地識(shí)別頻繁模式中含有關(guān)鍵特征的模式并摘取關(guān)鍵特征，過(guò)濾由于頻繁模式向下閉合性產(chǎn)生的可能給用戶帶來(lái)誤導(dǎo)的子模式，達(dá)到了較好的應(yīng)用效果。

本節(jié)僅以三階頻繁模式及含有關(guān)鍵特征的模式為例，北京POI數(shù)據(jù)集在21個(gè)三階模式中識(shí)別出5個(gè)含有關(guān)鍵特征的模式及其關(guān)鍵特征。表3列出了含有關(guān)鍵特征的頻繁模式，給出了每個(gè)模式的參與度、模式顯著性和模式關(guān)鍵度，將模式通過(guò)關(guān)鍵度排序。其中，模式的關(guān)鍵特征用粗體標(biāo)識(shí)。

表3 真實(shí)數(shù)據(jù)集關(guān)鍵特征挖掘結(jié)果

注:表中Min_prev=0.2;cds_prev=0.2;key_min=0.2;d=50

從表3中可以看出，含有關(guān)鍵特征的模式在保持模式頻繁的基礎(chǔ)上對(duì)模式進(jìn)一步分析后，得到的模式及其關(guān)鍵特征更好地對(duì)模式進(jìn)行了解釋，使得用戶面對(duì)更加精簡(jiǎn)的模式結(jié)果時(shí)更易理解和使用。

表4 真實(shí)數(shù)據(jù)集關(guān)鍵特征度量值

4.3.2 關(guān)鍵特征摘取實(shí)例分析

本節(jié)以含有關(guān)鍵特征的{酒店,公園,停車場(chǎng)}的Co-location頻繁模式為例，觀察參與率與關(guān)鍵度兩種模式特征度量方法的區(qū)別。從表4中可以看出，當(dāng)設(shè)關(guān)鍵度閾值min_key=0.2時(shí)，酒店和公園是模式{酒店,公園,停車場(chǎng)}模式的關(guān)鍵特征，且其關(guān)鍵度度量通過(guò)對(duì)模式中特征實(shí)例的相關(guān)性分析，得出更有針對(duì)性、更有指導(dǎo)性的結(jié)果。

5 結(jié)束語(yǔ)

本文根據(jù)Co-location頻繁模式挖掘結(jié)果數(shù)量大、針對(duì)性不足的問(wèn)題，為讓用戶更好地理解和使用挖掘結(jié)果，提出了含有關(guān)鍵特征的頻繁Co-location模式及其挖掘算法。本文針對(duì)含有關(guān)鍵特征的空間 Co-location 模式挖掘問(wèn)題, 給出了一系列相關(guān)定義、度量標(biāo)準(zhǔn)和挖掘算法。 通過(guò)大量的實(shí)驗(yàn)表明，本文提出的算法能夠有效地縮減模式結(jié)果，為用戶提供含有關(guān)鍵特征的Co-location模式和相應(yīng)的關(guān)鍵特征，為特定應(yīng)用提供有效的支持。下一步的工作將在此基礎(chǔ)上，通過(guò)特征提取和數(shù)據(jù)壓縮等方法減少挖掘過(guò)程中產(chǎn)生的Co-location表實(shí)例的存儲(chǔ)和計(jì)算開(kāi)銷，進(jìn)一步提高該算法的效率。