包旭光，王麗珍，肖 清，趙家松

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

空間數(shù)據(jù)挖掘是從空間數(shù)據(jù)庫(kù)中挖掘未知的有趣模式的過(guò)程。因?yàn)榭臻g數(shù)據(jù)的海量性、多維性、相關(guān)性等特點(diǎn)，從空間數(shù)據(jù)集中挖掘有趣模式比從事務(wù)數(shù)據(jù)集中挖掘要困難得多[1]。

傳統(tǒng)數(shù)據(jù)通常是相互獨(dú)立的，而空間上分布的數(shù)據(jù)則是相關(guān)的，或者更確切地說(shuō)是空間并置的(co-located)，即兩個(gè)對(duì)象的位置越近，就越有可能具有相似的性質(zhì)?？臻gco-location模式是空間特征的一個(gè)子集，它們的實(shí)例在空間中頻繁關(guān)聯(lián)[2]。

空間co-location模式在許多應(yīng)用領(lǐng)域發(fā)揮著重要的作用。例如，移動(dòng)服務(wù)運(yùn)營(yíng)商根據(jù)不同需求用戶的分布，搭配相應(yīng)的服務(wù)套餐以增加收入；廣告運(yùn)營(yíng)商根據(jù)特定人群的聚集地段，投放相應(yīng)的廣告；銀行根據(jù)不同地域人群的不同收入設(shè)定相應(yīng)的信用卡服務(wù)和理財(cái)產(chǎn)品?？臻gco-location模式的應(yīng)用領(lǐng)域還包括地球科學(xué)、公共衛(wèi)生、公共交通、生物信息處理、基于位置的服務(wù)、GIS信息系統(tǒng)等[3]。

空間co-location模式挖掘是空間數(shù)據(jù)挖掘的一個(gè)重要分支，已經(jīng)涌現(xiàn)了大量的高效算法。通常，這些co-location模式挖掘算法僅用一個(gè)主觀的參與度閾值來(lái)衡量co-location模式的頻繁性，如果這個(gè)數(shù)值設(shè)置得太小，會(huì)產(chǎn)生非常多的頻繁co-location模式，這會(huì)給用戶帶來(lái)很大的選擇困擾；如果這個(gè)數(shù)值設(shè)置得太高，某些用戶感興趣的稀有co-location模式[4]可能會(huì)被遺漏。特別地，如果空間數(shù)據(jù)集中有n個(gè)特征，則可能會(huì)產(chǎn)生最多2n-n-1個(gè)頻繁co-location模式，隨著n的增大，頻繁co-location模式的數(shù)量呈指數(shù)增長(zhǎng)，而實(shí)際上，用戶真正感興趣的co-location模式可能只是幾個(gè)或者幾類(lèi)co-location模式，從這種海量co-location模式中挑選幾個(gè)感興趣的co-location模式就變得非常棘手。

為了解決上面提到的問(wèn)題，以減少頻繁co-location模式數(shù)量為目的的挖掘算法受到關(guān)注，如模式的精簡(jiǎn)表示[5-7]、模式冗余處理[8]以及二次挖掘[9-10]。這些算法雖然可以減少頻繁co-location模式的數(shù)量，但是無(wú)法保證得到用戶真正感興趣的模式。我們注意到，模式的有趣程度與用戶的領(lǐng)域知識(shí)有著很大的關(guān)聯(lián)性，一個(gè)模式對(duì)某個(gè)用戶是有趣的，但是另外一個(gè)用戶可能根本不感興趣。因此，要得到用戶真正感興趣的模式，就需要與用戶進(jìn)行交互。

另一方面，用戶領(lǐng)域知識(shí)也可以指導(dǎo)有趣模式的挖掘。在語(yǔ)義網(wǎng)領(lǐng)域，本體[11-13](ontology)被認(rèn)為最適合表示復(fù)雜的用戶領(lǐng)域知識(shí)，且本體語(yǔ)言也可以更好地表達(dá)復(fù)雜的用戶領(lǐng)域知識(shí)。

鑒于此，本文提出了一個(gè)基于本體的有趣co-location模式的交互式挖掘算法OIICM(ontology-based interactive interesting co-location miner).OIICM以一組候選co-location模式集(例如：頻繁co-location模式集)為原始輸入，通過(guò)與用戶的交互，選取用戶真正感興趣的co-location模式。OIICM只需要與用戶進(jìn)行有限次的交互，每次交互送給用戶一組數(shù)量較少的代表co-location模式(例如：5個(gè))，用戶只需要在每次交互中對(duì)這一組代表co-location模式進(jìn)行喜好的選擇即可。圖1給出了OIICM的交互過(guò)程。每次交互，OIICM從候選co-location模式集中選擇幾個(gè)co-location模式作為代表co-location模式集提供給用戶，用戶對(duì)該代表co-location模式集中的每個(gè)co-location模式進(jìn)行喜好的選擇并提交自己的反饋， OIICM利用本體將對(duì)用戶的反饋進(jìn)行分類(lèi)并更新候選co-location模式集，同時(shí)，將有趣的co-location移動(dòng)到結(jié)果集，然后再?gòu)暮蜻xco-location模式集中選擇新的代表co-location模式集供用戶選擇，一直循環(huán)到候選co-location模式集為空。交互過(guò)程結(jié)束之后得到的有趣co-location模式集稱之為結(jié)果集。最后，在不丟失結(jié)果集語(yǔ)義的前提下，OIICM提供了一個(gè)有效的過(guò)濾器對(duì)結(jié)果集進(jìn)行過(guò)濾，得到最終的有趣co-location模式集。

圖1 交互過(guò)程描述Fig.1 Description of the interactive process

與用戶交互地挖掘有趣co-location模式需要解決兩個(gè)基本的問(wèn)題：第一，怎樣利用本體來(lái)更新候選co-location模式集？第二，為了減少交互次數(shù)，OIICM應(yīng)該怎樣選擇代表co-location模式集？為了解決第一個(gè)問(wèn)題，本文利用本體來(lái)度量?jī)蓚€(gè)co-location模式的相似度，如果用戶對(duì)某個(gè)co-location模式c感興趣，則對(duì)與c相似的co-location模式也同樣感興趣，這樣可以有效地減少候選co-location模式集的數(shù)量；為了解決第二個(gè)問(wèn)題，本文提出了一個(gè)貪心策略選擇盡可能不同的co-location代表模式。下面分別討論。

1 基本概念

空間特征代表了空間中不同種類(lèi)的事物，空間特征在空間位置上的一次出現(xiàn)稱為該空間特征的一個(gè)實(shí)例。給定空間特征集F及其實(shí)例集S，S上的空間鄰近關(guān)系R，即如果兩個(gè)不同實(shí)例之間的歐式距離不大于給定的距離閾值d，則這兩個(gè)空間實(shí)例滿足空間鄰近關(guān)系R.一個(gè)co-location模式c(c?F)是一組空間特征的集合，c中空間特征的個(gè)數(shù)稱為c的階(size).如果一個(gè)實(shí)例集中的任何一個(gè)實(shí)例都與該實(shí)例集中的其他實(shí)例滿足R關(guān)系，則該實(shí)例集中的實(shí)例形成一個(gè)團(tuán)。如果一個(gè)團(tuán)T’包含了co-location模式c的所有特征，且T’中沒(méi)有任何一個(gè)子集可以包含c中的所有特征，T’稱作co-location模式c的一個(gè)行實(shí)例，所有行實(shí)例的集合稱為表實(shí)例?？臻gco-location模式挖掘采用參與度PI(Participation Index)來(lái)衡量co-location模式的有趣程度，當(dāng)一個(gè)co-location模式c的參與度不小于用戶給定的最小參與度閾值min_prev時(shí)，稱c是頻繁co-location模式。

圖2給出了一個(gè)空間實(shí)例分布的例子，包含5個(gè)特征A、B、C、D和E，其中A.1表示A特征的第1個(gè)實(shí)例；該空間共有5個(gè)A的實(shí)例，4個(gè)B的實(shí)例，4個(gè)C的實(shí)例，4個(gè)D的實(shí)例以及3個(gè)E的實(shí)例；連線表示兩個(gè)空間實(shí)例滿足鄰近關(guān)系，例如A.1和B.1是互相鄰近的。{B.4,C.1,D.2}形成一個(gè)團(tuán)，且是一個(gè)3階co-location模式{B,C,D}的一個(gè)行實(shí)例。因?yàn)樵贌o(wú)其他同時(shí)包含B,C,D這3個(gè)特征的實(shí)例形成團(tuán)，則co-location模式{B,C,D}的表實(shí)例為{{B.4,C.1,D.2}}.如果{B,C,D}的參與度大于給定的參與度閾值，則{B,C,D}為頻繁co-location模式。

圖2 空間實(shí)例分布Fig.2 An example neighbor graph

本體這個(gè)概念由Gruber提出，他認(rèn)為本體是對(duì)共享概念模型的明確的規(guī)范的說(shuō)明?？梢院?jiǎn)單地認(rèn)為本體是領(lǐng)域知識(shí)的一種抽象化，把一個(gè)領(lǐng)域知識(shí)轉(zhuǎn)化為一個(gè)概念模型，這個(gè)模型里包括了各種類(lèi)型的概念描述。本體可表示為5元組O={C,E,Z,H,A}，其中C是一組本體概念的集合；E是定義在C上的本體概念關(guān)系集合；Z是本體概念的實(shí)例集；H是一個(gè)表示本體概念間包含關(guān)系(is-a關(guān)系，≤)的有向無(wú)環(huán)圖，如果本體概念C1包含本體概念C2，則C2is-aC1，在H圖上則表示為C1指向C2的有向線段；A為加在本體上的額外定理的集合。

本文將本體的概念C分為3種類(lèi)型，分別為葉概念、廣義概念和約束概念，葉概念即為本體H圖中的葉節(jié)點(diǎn)，廣義概念為包含葉概念的概念，約束概念是定義在其他本體概念上的邏輯表達(dá)式。

圖3為一個(gè)本體的H圖，其中鳥(niǎo)類(lèi)和莊稼為約束概念，虛線表示了約束概念之間的映射關(guān)系。得到的概念集如下：

所有概念集合：{生物，鳥(niǎo)類(lèi)，動(dòng)物，植物，真菌，莊稼，麻雀，松鼠，蛇，麥子，松樹(shù)，柏樹(shù)，香菇，樹(shù)菇}

葉概念集合：{麻雀，松鼠，蛇，麥子，松樹(shù)，柏樹(shù)，香菇，樹(shù)菇}

廣義概念集合：{生物，動(dòng)物，植物，真菌}

約束概念集合：{鳥(niǎo)類(lèi)，莊稼}

箭頭表示了包含與被包含關(guān)系，假設(shè)z(C)表示本體概念C所包含的本體概念映射，則：

z(生物)={動(dòng)物，植物，真菌}

z(植物)={麥子，松樹(shù)，柏樹(shù)}

z(動(dòng)物)={麻雀，松鼠，蛇}

z(莊稼)={麥子}

……

圖3 本體H圖示例Fig.3 An example H of ontology

本文將本體應(yīng)用到空間co-location模式挖掘，首先將空間特征映射到本體的葉概念，然后利用本體的語(yǔ)義將葉概念分類(lèi)并在高層提取更加有意義的co-location模式，而不像經(jīng)典co-location挖掘，僅僅只考慮本體葉概念之間的共生關(guān)系。

2 基于本體的候選模式集更新策略

本節(jié)主要討論第一個(gè)問(wèn)題：怎樣利用本體來(lái)更新候選co-location模式集？包括怎樣利用本體度量?jī)蓚€(gè)co-location模式之間的語(yǔ)義距離，以及怎樣基于這個(gè)度量準(zhǔn)則更新候選co-location模式集。

2.1 兩個(gè)co-location模式間的語(yǔ)義距離

本體將一些擁有相似屬性的特征聚集成一個(gè)類(lèi)。例如，麥子、松樹(shù)和柏樹(shù)它們都屬于植物，有著植物的一些共性，于是，本體將它們向上概括成一個(gè)“植物”的本體概念。在“植物”這個(gè)廣義概念下，麥子、松樹(shù)和柏樹(shù)是相似的。但在“莊稼”這個(gè)約束概念下，麥子、松樹(shù)和柏樹(shù)就不是相似的。因此，可以通過(guò)本體找到任何一個(gè)空間特征的相似特征集。

為了更好地解釋本文中的相關(guān)定義及算法，圖4給出了圖2的本體H圖。圖2中的空間特征被映射到圖4的葉概念，C4為約束概念，C1，C2，C3和C5為廣義概念。

圖4 圖2的本體H圖Fig.4 H of ontology of Fig.2

2.2 候選co-location模式集的更新策略

OIICM每一次交互都會(huì)選擇一些代表co-location模式提交用戶進(jìn)行選擇，用戶對(duì)這些代表co-location模式做出選擇之后，OIICM根據(jù)co-location模式間的語(yǔ)義距離，從候選co-location模式集中找到每個(gè)代表co-location模式的“相似”模式，以便進(jìn)行下一步的更新操作。

定義2 給定一個(gè)co-location模式c，以及語(yǔ)義距離閾值sdt(semantic distance threshold,簡(jiǎn)寫(xiě)為s,0≤s≤1)，如果存在一個(gè)co-location模式c’滿足SD(c,c’)≤s，c’被稱作是c的相似模式。特別地，如果SD(c,c’)=0，則c’被稱作是c的絕對(duì)相似模式。

例如，在圖4中，co-location模式{A,D}的絕對(duì)相似模式集為{{B,D}}.

定義3 如果某個(gè)co-location模式c在候選co-location集及代表co-location模式集中均找不到其絕對(duì)相似模式，稱c為孤立co-location模式。

例如，圖4中{A,B}是一個(gè)孤立co-location模式。

在一次交互中，用戶對(duì)代表co-location模式集中的每個(gè)co-location模式進(jìn)行喜好的選擇并反饋給OIICM，OIICM得到用戶的反饋并從候選co-location模式集中提取每個(gè)代表co-location模式的相似模式集。如果用戶對(duì)某個(gè)代表co-location模式c感興趣，OIICM將c及其所有的相似模式加入結(jié)果集，并從候選co-location模式集中移除c的所有相似模式；如果用戶對(duì)c不感興趣，則OIICM從候選co-location模式集中移除c的所有相似模式。例如，如果有一個(gè)候選co-location模式集合為{{A,B},{A,C},{A,D},{B,C},{B,D},{B,E},{C,D},{D,E},{B,D,E}}，語(yǔ)義模式距離閾值為s=0，假設(shè)某個(gè)代表co-location模式c={A,E}，則c的相似模式集為{{B,E},{B,D,E}}，如果用戶對(duì)c感興趣，則將{B,E}和{B,D,E}加入結(jié)果集，并從候選co-location模式集中刪除這兩個(gè)co-location模式，即更新完畢后的候選co-location模式集為{{A,B},{A,C},{A,D},{B,C},{B,D},{C,D},{D,E}}；如果用戶對(duì)c不感興趣，則將{B,E}和{B,D,E}從候選co-location模式集中刪除。

當(dāng)s設(shè)置為0時(shí)，每個(gè)代表co-location模式c的相似模式c’都是該代表模式的絕對(duì)相似模式，它們擁有完全相同的上層語(yǔ)義(G(c)=G(c’))，此時(shí)可以完全正確地得到用戶感興趣的co-location模式。

如果s>0，則會(huì)產(chǎn)生這樣一種情形：對(duì)于兩個(gè)代表co-location模式c1和c2，用戶對(duì)c1感興趣但是對(duì)c2不感興趣，在候選co-location模式集中存在一個(gè)候選co-location模式c滿足SD(c,c1)≤s且SD(c,c2)≤s，即c同時(shí)是c1和c2的相似模式。首先，c1和c2不可能同時(shí)是c的絕對(duì)相似模式，否則就與用戶的反饋出現(xiàn)了矛盾。如果c1和c2中有1個(gè)是c的絕對(duì)相似模式，則c和與其互為絕對(duì)相似模式的代表模式的有趣性保持一致，即如果c1是c的絕對(duì)相似模式，因?yàn)閏1是有趣的，所以c是有趣的；如果c1和c2都不是c的絕對(duì)相似模式且c不是孤立co-location模式，則c放回候選co-location模式集中不做任何處理；如果c是孤立co-location模式，在這種情況下，為了減少交互次數(shù)，c的有趣性取決于與c語(yǔ)義距離最近的代表模式的有趣性，即如果SD(c,c1)

如果某個(gè)co-location模式c是孤立co-location模式，則對(duì)其有趣度的判定可能會(huì)產(chǎn)生錯(cuò)誤，其實(shí)對(duì)于該模式c也可以采用放回候選co-location模式候選集的策略，但是過(guò)多的交互次數(shù)會(huì)加重用戶的負(fù)擔(dān)，所以為了減輕用戶負(fù)擔(dān)及追求效率舍棄了小部分的準(zhǔn)確度。實(shí)際上，孤立co-location模式出現(xiàn)的概率比較小，而且這種co-location模式通常是已知的冗余模式，因?yàn)檫@種模式的組成幾乎都是同一類(lèi)的特征，即|G(c)|=1，如圖4中的模式{A,B}，因此，算法仍能保持高準(zhǔn)確率。

2.3 候選co-location模式集的更新算法

算法1給出了每次交互過(guò)程中候選co-location模式的更新過(guò)程。首先，得到用戶對(duì)代表co-location模式集的反饋(第1行)，如果反饋不為空(第2行)，則對(duì)每個(gè)候選co-location模式集中的co-location模式進(jìn)行處理(第3-18行)：如果代表co-location模式集中包含當(dāng)前候選co-location的絕對(duì)相似模式(第4-5行)，則將該模式的有趣度設(shè)置為其在代表模式集中絕對(duì)相似模式的有趣度(第6行)并刪除該候選co-location模式(第7行)。如果代表co-location模式集中不含當(dāng)前候選co-location模式的絕對(duì)相似模式(第8行)，則從候選co-location模式集中尋找該候選co-location的絕對(duì)相似模式集(第9行)，若該集合為空，說(shuō)明該候選co-location模式是孤立co-location模式(第10行)，則從代表co-location模式集中尋找與其語(yǔ)義距離最近的相似模式(第11行)，若存在該相似模式Lmp(第12行)，則設(shè)置該孤立co-location的興趣度為L(zhǎng)mp的興趣度(第13行)并刪除該候選co-location模式(第14行)。

算法1 更新候選co-location模式集輸入:P:包含m個(gè)co-location模式的集合sdt:語(yǔ)義距離閾值E:本體中本體概念之間的關(guān)系L:代表co-location模式集Fb:用戶對(duì)代表co-location模式集的反饋?zhàn)兞?Pp:P中模式p的絕對(duì)相似模式集Lp:L中模式p的絕對(duì)相似模式Lmp:L中與模式p語(yǔ)義距離最小的相似模式步驟:1:Fb=feedback_from_user(L);2:IF(Fb!=null)THEN3: FOREACH(patternpinP)DO4: Lp=find_hard_similar_co-locations(p,L,E,s);5: IF(Lpisnotempty)THEN6: setp’sinterestingnessasLp;7: P.remove(p);8: ELSE9: Pp=find_hard_similar_co-locations(p,P,E,s);10: IF(Pp=null)THEN11: Lmp=find_nearest_co-locations(p,P,E,s);12: IF(Lmp!=null)THEN13: setp’sinterestingnessasLmp;14: P.remove(p);15: ENDIF16: ENDIF17: ENDIF18: ENDFOR19:ENDIF

2.4 算法分析

在最好情況下，每個(gè)候選模式都能在代表co-location模式中找到其絕對(duì)相似模式。這種情況下，算法不會(huì)執(zhí)行第8行及以后的語(yǔ)句，算法的主要時(shí)間消耗在第4句，時(shí)間復(fù)雜度為O(km).從最好情況和最壞情況的時(shí)間復(fù)雜度分析可以看出算法1擁有較低的時(shí)間復(fù)雜度，在用戶提交反饋之后能夠在短時(shí)間內(nèi)更新候選co-location模式集。

3 代表模式集選擇策略及算法

本節(jié)主要討論第二個(gè)問(wèn)題：為了減少交互次數(shù)，怎樣選擇代表co-location模式集？包括最佳模式選擇的標(biāo)準(zhǔn)，以及代表co-location模式集的選擇策略及算法。

3.1 代表co-location模式選擇策略

例如，某個(gè)co-location模式集合s={{A,C},{B,C,E}}，G({A,C})={C1,C2,C4}，G({B,C,E})={C1,C2,C3,C4}，則s的語(yǔ)義信息量為|G({A,C})∪G({B,C,E})|=|{C1,C2,C3,C4}|=4.

本文給出選擇最佳代表co-location模式集的兩個(gè)標(biāo)準(zhǔn)。第一個(gè)標(biāo)準(zhǔn)為選擇的代表co-location模式之間應(yīng)該沒(méi)有冗余。如果有兩個(gè)代表co-location模式在模式組成(比如：空間特征)上存在某種相似性(比如：語(yǔ)義相似性)，這兩個(gè)代表co-location模式之間就存在冗余。因?yàn)槿哂郼o-location模式之間是相似的，為用戶提供冗余的co-location模式會(huì)增加交互次數(shù)且會(huì)增加用戶的負(fù)擔(dān)；第二個(gè)標(biāo)準(zhǔn)為選擇的代表co-location模式集應(yīng)該包含盡可能多的語(yǔ)義信息量。如果某個(gè)co-location模式c={A,D}被選為第一個(gè)代表co-location模式，c1={C,D}比c2={A,E}更適合作為第二個(gè)代表co-location模式，因?yàn)镚(c)={C1,C3},G(c1)={C2,C3,C4},G(c2)={C1,C3,C4},c與c1的語(yǔ)義信息量|G(c)∪G(c1)|=|{C1,C2,C3,C4}|=4,c與c2的語(yǔ)義信息量|G(c)∪G(c2)|=|{C1,C3,C4}|=3，c與c1的語(yǔ)義信息量要比c與c2的語(yǔ)義信息量大。

基于這兩個(gè)標(biāo)準(zhǔn)，本文設(shè)計(jì)了一個(gè)貪心算法來(lái)高效地選擇代表co-location模式集。貪心的選擇策略為當(dāng)前待選擇的代表co-location模式c應(yīng)該與當(dāng)前代表co-location模式集組合后語(yǔ)義信息量最大。該貪心策略滿足選擇最佳代表co-location模式集的兩個(gè)標(biāo)準(zhǔn)：首先，該算法選擇會(huì)增加當(dāng)前代表co-location模式集語(yǔ)義信息量的co-location模式，若選擇了冗余模式，代表co-location模式集的語(yǔ)義信息量不會(huì)變；其次，該算法選擇能最大程度增加當(dāng)前代表co-location模式集的語(yǔ)義信息量的co-location模式，這與第2個(gè)標(biāo)準(zhǔn)完全一致。該策略首先選擇包含最多語(yǔ)義信息量的候選co-location模式作為第一個(gè)代表co-location模式，因?yàn)檎Z(yǔ)義信息量多的模式被用戶接受的概率會(huì)比較大，接著與第1個(gè)代表co-location模式組合后語(yǔ)義信息量最大的候選co-location模式被選定為第2個(gè)代表co-location模式，第3個(gè)代表co-location模式應(yīng)該是候選co-location模式集中與前兩個(gè)代表co-location模式組合后語(yǔ)義信息量最大的co-location模式，以此類(lèi)推。例如，候選co-location模式集合為{{A,B},{A,C},{A,B,C},{D,E}}，每次交互需要選擇2個(gè)代表co-location模式。則第1個(gè)代表模式選擇{A,C}，因?yàn)閧A,C}的語(yǔ)義信息量最大(C({A,C})={C1,C2,C4})，第2個(gè)代表co-location模式會(huì)選擇{D,E}(C({D,E})={C3,C4})，因其與{A,B,C}組合之后的語(yǔ)義信息量最大。

3.2 代表co-location模式選擇算法

算法2給出了代表co-location模式集的選擇算法。首先，算法中需要維護(hù)一個(gè)最大語(yǔ)義信息量的變量max_information用來(lái)保存迭代中候選項(xiàng)與當(dāng)前代表co-location模式集合的最大信息量值，初始為0(第1行)，第1個(gè)代表co-location模式是候選co-location模式集中包含上層本體概念最多的co-location模式，如果滿足條件的co-location模式有多個(gè)，則取第一個(gè)滿足該條件的co-location模式(第2行)。接著用一個(gè)repeat-until循環(huán)尋找剩下k-1個(gè)代表co-location模式(第3-15行)。變量p保存了當(dāng)前滿足貪心策略的co-location模式，將p加入到代表模式集中并從候選co-location模式集中刪除p(第4-5行)。接著遍歷候選co-location模式集中的每個(gè)模式pp(第6行)，如果當(dāng)前候選co-location模式與代表co-location模式集中的任何一個(gè)代表co-location模式包含的上層概念是一致的(第7行)，則跳過(guò)該候選co-location模式(第8行)，否則計(jì)算該候選co-location模式與代表co-location模式集組合后的語(yǔ)義信息量，如果該語(yǔ)義信息量值大于max_information(第10行)，則修改max_information的值并將p指向該候選co-location模式(第11-12行)，經(jīng)過(guò)循環(huán)，可以保證p指向當(dāng)前候選co-location模式集中與代表模式集合并后語(yǔ)義信息量最大的候選co-location模式。

算法2 選擇代表co-location模式輸入:P:包含m個(gè)co-location模式的集合k:代表co-location模式集的模式數(shù)量E:本體中本體概念之間的關(guān)系輸出:L:代表co-location模式列表步驟:1:max_information=0;2:patternp=get_maximal_information(P,k,E)3:REPEAT4: L.add(p);5: P.remove(p);6: FOREACH(patternppinP)DO7: IF(have_same_concepts(pp,L))THEN8: CONTINUE;9: ENDIF10: IF(get_infor(L,pp)>max_information)THEN11: max_information=get_infor(L,pp);12: p=pp;13: ENDIF14: ENDFOR15:UNTILL.count>=k

3.3 算法分析

4 過(guò)濾器設(shè)計(jì)及整體算法

當(dāng)候選co-location模式集中剩下的模式數(shù)量小于需要提交給用戶反饋的co-location模式數(shù)量時(shí)，系統(tǒng)結(jié)束交互過(guò)程。此時(shí)得到的co-location模式集即為結(jié)果集，其中存放著系統(tǒng)認(rèn)為用戶感興趣的co-location模式，這個(gè)結(jié)果集中的模式數(shù)量還可以進(jìn)一步縮減。本節(jié)首先討論結(jié)果集的縮減方法，以保證提交給用戶的有趣co-location模式是最簡(jiǎn)的。然后給出OIICM的整體算法。

4.1 過(guò)濾器設(shè)計(jì)

因?yàn)閰⑴c度滿足向下閉合性[3]，即如果某個(gè)co-location模式是不頻繁的，那么它的任何超集都不是頻繁的?；蛘撸绻硞€(gè)co-location模式是頻繁的，則其任何子集都是頻繁的?；谶@個(gè)性質(zhì)，本文設(shè)計(jì)了一個(gè)在不遺漏任何語(yǔ)義的前提下進(jìn)一步縮減結(jié)果集的過(guò)濾器。

極大co-location模式[6]是co-location模式的一種壓縮表示。極大co-location模式是指其任何超集都不可能頻繁的co-location模式。例如模式集{{A，B},{A,C},{B,C},{A,B,C}}可以壓縮為{{A,B,C}}，因?yàn)閧A,B,C}是頻繁的，其任何子集都是頻繁的。由于結(jié)果集中的每個(gè)co-location模式都加入了語(yǔ)義，若只取結(jié)果集中的極大co-location模式則可能產(chǎn)生錯(cuò)誤結(jié)果。例如用戶對(duì){A,B,C}感興趣，用戶未必對(duì){A,B}感興趣，因?yàn)閧A,B,C}和{A,B}所包含的語(yǔ)義概念是不同的。所以，為了進(jìn)一步壓縮結(jié)果集，過(guò)濾器需要加一個(gè)限定條件：在相同語(yǔ)義環(huán)境下的模式集中，求該集合的極大co-location模式不會(huì)造成語(yǔ)義的遺漏。

過(guò)濾器的過(guò)濾過(guò)程為：首先，將結(jié)果集中的co-location模式按語(yǔ)義分組，每個(gè)co-location模式與其絕對(duì)相似模式構(gòu)成一個(gè)分組；然后，在每個(gè)分組內(nèi)求其極大co-location模式集；最后，將每個(gè)分組內(nèi)求得的極大co-location模式集進(jìn)行合并，即得到最終的有趣co-location模式結(jié)果集。

例如，若結(jié)果集為{{A,C},{B,C},{A,B,C},{A,C,D},{B,C,D},{A,B,C,D}}，該結(jié)果集的極大co-location頻繁模式為{A,B,C,D}，但實(shí)際上，該結(jié)果集包含了2個(gè)語(yǔ)義(見(jiàn)圖4)：{C1,C2,C4}和{C1,C2,C3,C4}，所以該結(jié)果集按語(yǔ)義分成兩組：在語(yǔ)義{C1,C2,C4}組的模式集為{{A,C},{B,C},{A,B,C}}，這個(gè)模式集的極大co-location模式為{A,B,C}；在語(yǔ)義{C1,C2,C3,C4}組的模式集為{{A,C,D},{B,C,D},{A,B,C,D}}，這個(gè)模式集的極大co-location模式集為{A,B,C,D}，所以，經(jīng)過(guò)過(guò)濾器之后得到的有趣co-location模式集合為{{A,B,C},{A,B,C,D}}.

4.2 OIICM整體算法描述

算法3給出了OIICM的整體算法描述。首先，系統(tǒng)從本體文件中找到本體概念之間的關(guān)系(第1行)，在本體概念關(guān)系確定之后，開(kāi)始對(duì)候選co-location模式集進(jìn)行循環(huán)地選擇代表co-location模式并進(jìn)行更新操作(第2～9行)。在循環(huán)中，如果當(dāng)前候選co-location模式的數(shù)量少于需要提交給用戶的模式數(shù)量，則系統(tǒng)將所有候選co-location模式作為代表模式集提交用戶進(jìn)行反饋(第3～4行)，這也意味著進(jìn)行最后一次交互，否則，利用第4節(jié)給出的算法選擇代表co-location模式集(第6行)。用戶將對(duì)代表co-location模式集的喜好反饋給OIICM，OIICM則利用本體對(duì)候選co-location模式集進(jìn)行更新操作(第8行)，這個(gè)算法在第3節(jié)有詳細(xì)介紹，需要注意的是更新操作的過(guò)程中會(huì)將所有有趣的co-location模式全部放在Res中，交互過(guò)程結(jié)束之后，Res中保存了所有的有趣co-location模式(結(jié)果集)。最后，利用過(guò)濾器對(duì)結(jié)果集進(jìn)行壓縮(第10行)，并輸出最終的有趣co-location模式結(jié)果集(第11行)。

算法3 挖掘有趣co-location模式(OIICM)輸入:P:包含m個(gè)co-location模式的集合k:代表co-location模式集的模式數(shù)量sdt:語(yǔ)義距離閾值o:XML形式存放的本體文件變量:E:本體中本體概念之間的關(guān)系L:代表co-location模式列表F:用戶對(duì)代表co-location模式集的反饋輸出:Res:有趣co-location模式結(jié)果集步驟:1:E=generate_relations_by_ontology(o);2:WHILE(P.count>=0)DO3: IF(P.count<=k)THEN4: L=P;5: ELSE6: L=sample_selection(P,k,E);//算法27: ENDIF8: update_candidtes(P,sdt,E,L,F);//算法19:ENDWHILE10:Res=do_filter(Res);11:output(Res);

4.3 算法分析

前面的章節(jié)已經(jīng)分析了算法1和算法2的時(shí)間復(fù)雜度，在算法3中，時(shí)間消耗主要在第2行到第9行的while循環(huán)中。從算法3中可以看出，OIICM整體算法與本體概念的數(shù)量及候選co-location模式的語(yǔ)義組成有很大的關(guān)系。在極限情況下，即所有候選co-location模式都屬于同一個(gè)語(yǔ)義組合，即使設(shè)置k=1也可以一次將所有的co-location分類(lèi)，在這種情形下，過(guò)濾器就變成了一個(gè)簡(jiǎn)單的極大co-location模式的提取器。

為了更好地分析OIICM算法的效率，假設(shè)輸入的候選co-location模式一共有n個(gè)本體語(yǔ)義組合，則可以近似地認(rèn)為第2行的while循環(huán)將總共執(zhí)行ceil(n/k)次，其中“ceil(q)”表示取大于某個(gè)浮點(diǎn)數(shù)q的最小整數(shù)，例如ceil(4.2)=5.在算法3中，第3行和第4行最多只執(zhí)行一次且只在最后一次循環(huán)中執(zhí)行，算法1和算法2的執(zhí)行次數(shù)是近似相同的(最多相差1次)，近似為ceil(n/k)次，第10行的時(shí)間復(fù)雜度為O(w)，w為結(jié)果集中co-location模式的數(shù)量，則算法3的整體時(shí)間復(fù)雜度為O(ceil(n/k)[(m+k2+n)m]+w).由此可見(jiàn)候選co-location模式所包含的語(yǔ)義個(gè)數(shù)n對(duì)OIICM有著很大的影響，若n≤k，則OIICM執(zhí)行效率最高，1次交互就可以得到用戶感興趣的co-location模式，若n很大，假設(shè)某個(gè)本體含有v個(gè)非葉概念，則最多可能會(huì)產(chǎn)生2v個(gè)語(yǔ)義組合，當(dāng)v比較大的時(shí)候，n有可能會(huì)等于m，即每個(gè)候選co-location之間的語(yǔ)義各不相同，在這種最壞情況下，OIICM的時(shí)間效率將會(huì)達(dá)到O(m3)級(jí)別。這個(gè)分析是假設(shè)沒(méi)有用戶的參與，而實(shí)際中，每次交互OIICM都會(huì)等待用戶的反饋，在兩次交互之間的時(shí)間復(fù)雜度為O(m+nm)，OIICM可以在短時(shí)間內(nèi)分析用戶的反饋并再次提供代表co-location模式集。

5 實(shí)驗(yàn)評(píng)估

本節(jié)將在實(shí)際數(shù)據(jù)和合成數(shù)據(jù)上驗(yàn)證OIICM的準(zhǔn)確率、壓縮率和算法有效性。

5.1 實(shí)際數(shù)據(jù)的實(shí)驗(yàn)分析

實(shí)際數(shù)據(jù)下的實(shí)驗(yàn)分析主要用來(lái)驗(yàn)證OIICM的準(zhǔn)確率。

5.1.1 實(shí)驗(yàn)設(shè)計(jì)

實(shí)際數(shù)據(jù)集選取北京市與旅游有關(guān)的城市元素分布數(shù)據(jù)。該數(shù)據(jù)集包含16個(gè)空間特征(標(biāo)識(shí)從A到P)，空間實(shí)例個(gè)數(shù)為90 458個(gè)，空間范圍為18 km×18 km，為了不遺漏稀有的有趣co-location模式，參與度設(shè)置為0.1，距離閾值設(shè)置為100 m.在此參數(shù)設(shè)置下共產(chǎn)生947個(gè)頻繁co-location模式。

實(shí)際數(shù)據(jù)上定義的本體H圖如圖5所示，在本體H圖下方給出了每個(gè)概念所代表的具體含義。假設(shè)本系統(tǒng)是針對(duì)第一次到北京旅游的用戶而開(kāi)發(fā)的，那么如果某個(gè)用戶想知道美食周?chē)欠裼幸恍┚包c(diǎn)，他可能認(rèn)為co-location模式{A,B,G}是有趣的，而如果另外一個(gè)用戶想知道在景點(diǎn)周?chē)欠駮?huì)有賓館，他可能會(huì)認(rèn)為co-location模式{D,G}是有趣的。

為了更好地評(píng)估OIICM的準(zhǔn)確性，用1個(gè)模擬過(guò)程來(lái)進(jìn)行準(zhǔn)確率的度量。一次模擬過(guò)程如下：模擬算法首先從圖5所示的本體中隨機(jī)選取2～5個(gè)不同廣義概念的組合(語(yǔ)義)，再在每個(gè)語(yǔ)義的指導(dǎo)下從947個(gè)頻繁co-location模式選擇滿足該語(yǔ)義的所有co-location模式，最終得到的co-location模式集合即為用戶感興趣的模式集；接著模擬過(guò)程啟動(dòng)OIICM開(kāi)始進(jìn)行交互，每次的反饋由模擬過(guò)程完成：若OIICM提供的代表模式中存在感興趣的模式，則進(jìn)行反饋。實(shí)驗(yàn)中默認(rèn)的代表co-location模式集的數(shù)量k設(shè)置為5，默認(rèn)的語(yǔ)義距離閾值s設(shè)置為0.1.實(shí)驗(yàn)中每一個(gè)測(cè)試項(xiàng)的準(zhǔn)確率為10次模擬過(guò)程的均值。

圖5 實(shí)際數(shù)據(jù)的本體H圖Fig.5 H of ontology using real data set

5.1.2 OIICM的準(zhǔn)確率分析

圖6顯示了OIICM在不同k值和s值下的準(zhǔn)確率以及與其他算法的比較。在實(shí)驗(yàn)中，設(shè)置Top-kClosed[7]算法產(chǎn)生所有的閉co-location模式，Order-Clique[6]算法則產(chǎn)生所有的極大co-location模式。在圖6(a)中，系統(tǒng)所需的交互次數(shù)隨著k的增大而減少，例如在k=8時(shí)，系統(tǒng)只需要交互4次就可以得到完整的有趣co-location模式集。同時(shí)，k=5時(shí)系統(tǒng)得到的有趣co-location模式的準(zhǔn)確率最高，將近90%，而k=3時(shí)交互6次后的準(zhǔn)確率為70%左右，這是因?yàn)槊看翁峁┑拇韈o-location數(shù)目過(guò)少，候選co-location模式集更新速度比較慢，交互過(guò)程還未完成；而當(dāng)k=8時(shí)最終準(zhǔn)確率變少為80%左右，這是因?yàn)樘峁┻^(guò)多的代表co-location模式會(huì)有更大機(jī)會(huì)誤判孤立co-location模式。在圖6(b)中，隨著s閾值的增大，準(zhǔn)確率逐漸降低，當(dāng)s=0時(shí)，準(zhǔn)確率達(dá)到了100%.對(duì)于非孤立模式，OIICM對(duì)其興趣度的判斷不會(huì)出現(xiàn)差錯(cuò)，當(dāng)s=0時(shí)，因?yàn)楣铝⒛Ｊ讲豢赡苡邢嗨颇Ｊ剑總€(gè)孤立模式都會(huì)被作為代表模式由用戶判斷，因而需要更多地交互次數(shù)，隨著s的增大，孤立模式會(huì)出現(xiàn)與其相似的代表模式，判錯(cuò)的概率會(huì)加大，因?yàn)閟的增大會(huì)使得模式間的語(yǔ)義的關(guān)聯(lián)度降低。在圖6(c)中，可以看到單純地從統(tǒng)計(jì)方面壓縮co-location模式并不會(huì)得到令用戶滿意的結(jié)果。這兩種壓縮方式都僅僅是從模式組合的角度對(duì)結(jié)果進(jìn)行壓縮，而沒(méi)有考慮用戶的主觀意愿。

圖6 OIICM的準(zhǔn)確率實(shí)驗(yàn)Fig.6 Experiments on accuracy ratio

5.2 合成數(shù)據(jù)的實(shí)驗(yàn)分析

合成數(shù)據(jù)下的實(shí)驗(yàn)分析主要用來(lái)驗(yàn)證OIICM產(chǎn)生的有趣co-location模式相對(duì)于原始輸入co-location模式集的壓縮率、代表模式選擇算法的效率、過(guò)濾器的壓縮效率以及本體非葉概念個(gè)數(shù)對(duì)算法的影響。

5.2.1 實(shí)驗(yàn)設(shè)計(jì)

合成數(shù)據(jù)的空間范圍為10 000*10 000，空間特征個(gè)數(shù)為50個(gè)，空間實(shí)例個(gè)數(shù)為50萬(wàn)個(gè)，按照泊松分布來(lái)分配每個(gè)空間特征下的實(shí)例個(gè)數(shù)，空間實(shí)例的位置隨機(jī)生成，距離閾值為50，參與度閾值為0.15，本體設(shè)置了10個(gè)廣義概念，且每個(gè)概念下有5個(gè)特征，在這種分布下，產(chǎn)生了1 022 211個(gè)頻繁co-location模式，用戶要在這么多co-location模式中選擇感興趣的模式是幾乎不可能的事情，利用OIICM，用戶可以在幾分鐘之內(nèi)得到感興趣的模式。在合成實(shí)驗(yàn)中默認(rèn)的代表co-location模式集的數(shù)量k設(shè)置為15，默認(rèn)的語(yǔ)義距離閾值s設(shè)置為0.1，在某些極限情況下，若某個(gè)用戶只想知道某幾類(lèi)概念之間的關(guān)系，這樣選出來(lái)的有趣模式可能只有幾十個(gè)，為了表示一般情況，在每輪的代表模式選取中，至少會(huì)選擇2個(gè)代表模式為有趣模式。因?yàn)閿?shù)據(jù)量比較大，為了更快地得到相應(yīng)的結(jié)果信息，在實(shí)驗(yàn)過(guò)程中，OIICM會(huì)模擬用戶行為進(jìn)行代表模式的喜好反饋，且興趣度選擇策略符合本文的語(yǔ)義環(huán)境。每一個(gè)試驗(yàn)項(xiàng)均進(jìn)行10次并取平均值。

5.2.2 OIICM壓縮率分析

5.2.3 代表模式選擇策略的有效性分析

本文的第4節(jié)給出了兩個(gè)代表模式最佳選擇標(biāo)準(zhǔn)，并根據(jù)這兩個(gè)標(biāo)準(zhǔn)設(shè)計(jì)了一個(gè)貪心算法尋找最佳代表co-location模式集。本節(jié)實(shí)驗(yàn)主要用來(lái)驗(yàn)證該貪心算法的有效性，并設(shè)計(jì)了一個(gè)隨機(jī)選擇算法來(lái)與之進(jìn)行對(duì)比。該隨機(jī)算法每輪從候選co-location模式集中隨機(jī)地選擇k個(gè)模式提交用戶進(jìn)行交互。

圖7 OIICM壓縮率實(shí)驗(yàn)Fig.7 Experiments on redundancy ratio

圖8給出了不同k值和s值下兩個(gè)算法的交互次數(shù)?？梢悦黠@地看出，貪心算法比隨機(jī)算法所需要的交互次數(shù)要少很多，且貪心算法比隨機(jī)算法更加穩(wěn)定。圖8(a)中，隨著k值的增加，兩個(gè)算法的交互次數(shù)都在減少，這是因?yàn)閗值越大，代表模式集的語(yǔ)義信息量就越大，就會(huì)更多地減少候選co-location模式的數(shù)量；圖8(b)中隨機(jī)算法的次數(shù)非常不穩(wěn)定且遠(yuǎn)高于貪心算法的交互次數(shù)。由圖8可以看出，貪心算法尋找代表co-location模式是有效的。

圖8 貪心算法有效性實(shí)驗(yàn)Fig.8 Experiments on the effectiveness of selection strategy

5.2.4 過(guò)濾器的壓縮效率分析

本節(jié)主要驗(yàn)證過(guò)濾器的壓縮效率。在合成數(shù)據(jù)的實(shí)驗(yàn)中，OIICM在完成交互之后，依然還有將近40萬(wàn)的有趣co-location模式，這同樣會(huì)給用戶的選擇帶來(lái)很大負(fù)擔(dān)。表1給出了合成數(shù)據(jù)生成的每階co-location模式的數(shù)量和在s=0.1，k=15時(shí)通過(guò)交互得到的各階co-location模式的數(shù)量以及經(jīng)過(guò)過(guò)濾器之后最終得到的co-location模式的數(shù)量，在表格中，括號(hào)里的百分?jǐn)?shù)表示壓縮后的co-location模式數(shù)量與原始同階頻繁co-location模式數(shù)量的比率。

如表1所示，原始的頻繁co-location模式中5階，6階和7階co-location模式占了很大一部分比例，經(jīng)過(guò)OIICM的多次交互之后，低階co-location模式的壓縮率明顯要低于高階co-location模式的壓縮率，這是因?yàn)榈碗Aco-location模式更容易被加進(jìn)結(jié)果集或者被排除在外，例如{A,B,C,D,E}同屬于一個(gè)本體概念，如果{A,B,D,E}被用戶標(biāo)識(shí)為有趣的，則該集合的所有組合co-location模式都被加入到了結(jié)果集之中。而過(guò)濾器的壓縮效果正好相反，低階的壓縮效果明顯高于高階的壓縮效果，這是因?yàn)橥徽Z(yǔ)義環(huán)境下高階co-location模式可以代表低階co-location模式，例如{A,B,C,D,E}同屬于一個(gè)本體概念，則如果c={A,B,C,D,E}被用戶標(biāo)識(shí)為有趣的，則c的全部子集都會(huì)被剔除掉。這兩個(gè)階段的壓縮過(guò)程相輔相成，交互過(guò)程得到全部滿足語(yǔ)義的co-location模式，而過(guò)濾器則在此基礎(chǔ)上提取出每個(gè)語(yǔ)義的極大co-location模式。由表1可以看出OIICM最終的壓縮率可以達(dá)到99.2%，壓縮效果非常明顯，有效地減輕了用戶的選擇負(fù)擔(dān)。

表1 各階co-location模式數(shù)量及占比Table 1 The number and proportion of each order co-location pattern

5.2.5 本體非葉概念數(shù)目對(duì)算法的影響

4.3節(jié)討論了非葉概念數(shù)目v對(duì)OIICM算法效率的影響。本節(jié)實(shí)驗(yàn)主要分析非葉概念數(shù)目對(duì)OIICM算法效率的影響程度。

在試驗(yàn)中，分別設(shè)置本體非葉概念的數(shù)量為1，5，10及20，合成數(shù)據(jù)共有50個(gè)特征，按照泊松分布給每個(gè)葉概念分配相應(yīng)的特征。每次交互送給用戶代表模式的數(shù)量k=15，語(yǔ)義距離閾值s=0.1.實(shí)驗(yàn)主要分析不同v值下OIICM交互所花費(fèi)的時(shí)間，而不考慮用戶的反饋時(shí)間，即實(shí)驗(yàn)中得到的時(shí)間是每次交互從用戶提交反饋到OIICM選擇代表co-location模式集提交用戶的時(shí)間總和。

圖9給出了v值對(duì)算法的影響，可以看到隨著v的增大，OIICM交互所需要的時(shí)間也急劇地增加。隨著v值的增加，可以生成的語(yǔ)義組合數(shù)n(n最多為2v-1)呈指數(shù)性地增加，而OIICM的整體復(fù)雜度為與ceil(n/k)成正比(見(jiàn)4.3的算法分析)，隨著n指數(shù)性地增加，OIICM的耗時(shí)也會(huì)呈指數(shù)性地增加。圖9中，OIICM的耗時(shí)與OIICM的時(shí)間效率分析保持一致。

圖9 v值對(duì)算法的影響Fig.9 Efficiency on v value

6 總結(jié)

本文提出了一個(gè)基于本體的有趣co-location模式的交互式挖掘方法。不同于之前大多數(shù)基于統(tǒng)計(jì)信息的挖掘方式，本文利用本體來(lái)聚合用戶的領(lǐng)域知識(shí)，并給出了co-location模式之間語(yǔ)義距離的度量方式，通過(guò)語(yǔ)義距離，可以更快地將co-location模式進(jìn)行分類(lèi)，快速得到用戶真正感興趣的co-location模式；為了減少交互次數(shù)，本文提出了一個(gè)高效的貪心算法來(lái)“最大化”地提取用戶感興趣的語(yǔ)義；最后設(shè)計(jì)了一個(gè)過(guò)濾器可以有效地縮減結(jié)果集的數(shù)量。對(duì)算法的復(fù)雜度分析說(shuō)明了本文提出的算法的高效性。通過(guò)大量實(shí)驗(yàn)分析并驗(yàn)證了所提方法的高準(zhǔn)確率、高壓縮率及高效性。

未來(lái)，我們將進(jìn)一步研究本體下的用戶交互性問(wèn)題，對(duì)交互方式以及交互算法進(jìn)行進(jìn)一步的優(yōu)化，加入一些約束條件，使得算法可以以更少的交互次數(shù)，更快地交互時(shí)間挖掘用戶感興趣的co-location相關(guān)模式。

[1] HAN J,KAMBER M.Data mining:Concepts and techniques.2nd ed[M].Beijing:China Machine Press,2006.

[2] 王麗珍，陳紅梅.空間模式挖掘理論與方法[M].北京:科學(xué)出版社,2014.

[3] HUANG Y,SHEKHAR S,XIONG H.Discovering co-location patterns from spatial data sets:A general approach[J].IEEE Transactions on Knowledge and Data Engineering,2004,16:1472-1485.

[4] SILBERPCHATZ A,TUZHILIN A.What makes patterns interesting in knowledge discovery systems[J].Knowledge and Data Eng,1996,8(6):970-974.

[5] YOO J,BOW M.Mining top-kclosed co-location patterns[C]∥Proceedings of the IEEE International Conference on Spatial Data Mining and Geographical Knowledge Services.Fuzhou,China,2011:100-105.

[6] WANG L,ZHOU L,LU J.An order-clique-based approach for mining maximal co-locations[J].Information Sciences,2009,179:3370-3382.

[7] BAO X,WANG L,ZHAO J.Mining top-ksize co-location patterns[C]∥Proceedings of the 2016 International Conference on Computer,Information and Telecommunication Systems.Kunming,China,2016:36-41.

[8] XIN D,SHEN X,MEI Q.Discovering interesting patterns through user's interactive feedback[C]∥Proceedings of Twelfth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.Philadelphia,Pa,USA,2006:773-778.

[9] 包旭光，王麗珍，方圓.OSCRM：一個(gè)基于本體的空間co-location規(guī)則挖掘框架[J].計(jì)算機(jī)研究與發(fā)展,2015,52(Suppl.):74-80.

BAO X,WANG L,FANG Y.OSCRM:A framework of ontology-based spatial co-location rule mining[J].Journal of Computer Research and Development,2015,52(Suppl.):74-80.

[10] MARINICA C,GUILLET F.Knowledge-based interactive postmining of association rules using ontologies[J].IEEE Transactions on Knowledge and Data Engineering,2010,22(6):784-797.

[11] GRUBER T.A translation approach to portable ontology specifications[J].Knowledge Acquisition,1993,5:199-220.

[12] GUARINO N.Formal ontology in information systems[C]∥Proceedings of First Int'l Conf Formal Ontology in Information Systems.Trento,Italy,1998:3-15.

[13] MAEDCHE A,STABB S.Ontology learning for the semantic web[J].IEEE Intelligent Systems,2001,16(2):72-79.

[14] AGRAWAL R,LMIELINSKI T,SWAMI A.Mining association rules between sets of items in LaRPe databases[C]∥Proceedings of ACM SIGMOD.1993:207-216.

[15] YOO J,SHEKHAR S.A partial join approach for mining co-location patterns[C]∥Proceedings of the 12th ACM Int'l Workshop on Geographic Information Systems (GIS 04).USA：Washington DC,2004:241-249.

[16] YOO J,SHEKHAR S.A joinless approach for mining spatial collocation patterns[J].IEEE Transactions on Knowledge and Data Engineering (TKDE),2006,18(10):1323-1337.

[17] GINKEL L,WORDEMAN L.A new join-less approach for co-location pattern mining[C]∥Proceedings of the IEEE International Conference on Computer and Information Technology.2008:197-202.

[18] WANG L,BAO Y,LU Z.Efficient discovery of spatial co-location patterns using the iCPI-tree[J].The Open Information Systems Journal,2009,3(1):69-80.

[19] FANG Y,WANG L,LU J,et al.A combined co-location pattern mining approach for post-analyzing co-location patterns[C]∥Proceedings of the International Conference on Artificial Intelligence:Technologies and Applications.2016:38-43.

[20] SONG D,BRUZA P,HUANG Z,et al.Classifying document titles based on information inference[C]∥Proceedings of the Foundations of Intelligent Systems,International Symposium.Japan：Maebashi City,2003:297-306.

[21] SARNOVSKY M,PARALIC M.Text mining workflows construction with support of ontologies[C]∥Proceedings of the International Symposium on Applied Machine Intelligence and Informatics.2008:173-177.

[22] JAIN A,DUBES R.Algorithms for clustering data[M].USA:Prentice Hall,1998.