江萬國，王麗珍，方 圓，陳紅梅

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

(*通信作者電子郵箱lzhwang2005@126.com)

領(lǐng)域驅(qū)動的高效用co-location模式挖掘方法

江萬國，王麗珍*，方 圓，陳紅梅

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

(*通信作者電子郵箱lzhwang2005@126.com)

空間并置(co-location)模式是指其實例在空間鄰域內(nèi)頻繁共現(xiàn)的空間特征集的子集?，F(xiàn)有的空間co-location模式挖掘的有趣性度量指標(biāo)，沒有充分地考慮特征之間以及同一特征的不同實例之間的差異；另外，傳統(tǒng)的基于數(shù)據(jù)驅(qū)動的空間co-location模式挖掘方法的結(jié)果常常包含大量無用或是用戶不感興趣的知識。針對上述問題，提出一種更為一般的研究對象——帶效用值的空間實例，并定義了新的效用參與度(UPI)作為高效用co-location模式的有趣性度量指標(biāo)；將領(lǐng)域知識形式化為三種語義規(guī)則并應(yīng)用于挖掘過程中，提出一種領(lǐng)域驅(qū)動的多次迭代挖掘框架；最后通過大量實驗對比分析不同有趣性度量指標(biāo)下的挖掘結(jié)果在效用占比和頻繁性兩方面的差異，以及引入基于領(lǐng)域知識的語義規(guī)則前后挖掘結(jié)果的變化情況。實驗結(jié)果表明所提出的UPI度量是一種兼顧頻繁和效用的更為合理的度量指標(biāo)；同時，領(lǐng)域驅(qū)動的挖掘方法能有效地挖掘到用戶真正感興趣的模式。

空間模式挖掘；co-location模式；高效用co-location模式；有趣性度量指標(biāo)；領(lǐng)域驅(qū)動；語義規(guī)則

0 引言

與傳統(tǒng)的事務(wù)數(shù)據(jù)相比，空間數(shù)據(jù)具有海量性、高維性和語義信息更加豐富等特點，這些特點使得空間數(shù)據(jù)的知識發(fā)現(xiàn)比傳統(tǒng)數(shù)據(jù)更具挑戰(zhàn)性?？臻g數(shù)據(jù)往往具有較強(qiáng)的地理相關(guān)性，即兩個空間對象所處位置越近，就越有可能具有相同的性質(zhì)。空間co-location模式是空間特征集的一個子集，子集中特征的實例頻繁地在空間鄰域共現(xiàn)。空間co-location模式廣泛存在于實際生活中，例如瘧疾往往發(fā)生在蚊蟲泛濫和水污染嚴(yán)重的區(qū)域。

在現(xiàn)有的大量空間co-location模式挖掘研究中， 一般將模式中特征的最小參與率(即參與度(Participation Index, PI))作為模式有趣性的度量指標(biāo)，僅關(guān)注了模式中特征實例共現(xiàn)的頻繁性，忽略了特征之間和同一特征中不同實例之間可能存在的差異。而已有的空間高效用co-location模式挖掘研究中，雖然引入了模式效用率(Pattern Utility Ratio, PUR)作為模式有趣性的度量指標(biāo)，將模式中不同特征對模式的興趣性貢獻(xiàn)區(qū)分對待，但在實際中我們還注意到相同空間特征中不同實例對模式興趣性的貢獻(xiàn)仍然存在差異，而相關(guān)研究未見報道。

另一方面，以數(shù)據(jù)為中心的空間co-location模式挖掘通常忽略了數(shù)據(jù)特定的領(lǐng)域背景和用戶偏好等約束信息，挖掘結(jié)果往往針對性差、數(shù)量大，并包含了大量無用或用戶不感興趣的結(jié)果，這樣的挖掘結(jié)果通常是不可行動的。因此，考慮數(shù)據(jù)來源和應(yīng)用背景的領(lǐng)域知識，在空間co-location模式挖掘過程中引入基于領(lǐng)域知識的語義規(guī)則是有益的。

在本文中，我們充分考慮了特征之間和實例之間的差異性，以及數(shù)據(jù)和應(yīng)用的領(lǐng)域知識，最終能得到更有針對性的挖掘結(jié)果。

1 相關(guān)工作

空間co-location模式挖掘是空間關(guān)聯(lián)規(guī)則挖掘的一個特例，最早在文獻(xiàn)[1-2]中被提出。文獻(xiàn)[3]中提出了co-location模式的有趣性度量指標(biāo)——最小參與率(PI)。PI的定義滿足向下閉合性(先驗原理)，所以能夠利用這一性質(zhì)有效地進(jìn)行候選模式剪枝?？臻gco-location模式挖掘大體包括兩大主要工作：產(chǎn)生候選模式和計算候選模式的表實例，其中計算表實例是時間復(fù)雜度最高的部分，此后的很多研究都集中在候選模式的剪枝和表實例的計算優(yōu)化兩個方面。文獻(xiàn)[3-5]中分別提出了經(jīng)典的join-based(全連接)算法、partial-join(部分連接)算法和Join-less(無連接)算法，這些算法都是類Apriori的。Join-less算法采用了新穎的物化模型——星型鄰居，在計算表實例時通過查詢操作來代替連接操作。與上述的類Apriori算法不同，文獻(xiàn)[6]中提出了新的空間鄰近關(guān)系的物化模型，并給出了類似于FP-growth(Frequent-Pattern growth)的CPI-tree(Co-location Pattern Instance tree)算法。文獻(xiàn)[7]中又提出了一種結(jié)合“候選-測試”方式和CPI-tree模型優(yōu)勢的新物化模型——iCPI-tree，基于該模型的算法具有更高的效率。文獻(xiàn)[8]中系統(tǒng)地總結(jié)了空間co-location模式挖掘的方法和研究現(xiàn)狀。

文獻(xiàn)[9]首次提出了基于“特征外部效用(單價)”和“特征在模式中的內(nèi)部效用(數(shù)量)”的空間高效用co-location模式挖掘方法，給出了高效用co-location模式的有趣性度量指標(biāo)——PUR(模式效用率)。文獻(xiàn)[10]則進(jìn)一步提出了擴(kuò)展模式效用率的概念，并出了一個擴(kuò)展剪枝算法EPA。但文獻(xiàn)[9]和[10]的研究中沒有考慮同一特征不同實例的效用差異。

文獻(xiàn)[11]中提出了領(lǐng)域驅(qū)動數(shù)據(jù)挖掘的方法論來縮小學(xué)術(shù)研究和商業(yè)應(yīng)用的差距。在領(lǐng)域驅(qū)動數(shù)據(jù)挖掘中，需要重點考慮領(lǐng)域知識的表示以及如何在挖掘中使用領(lǐng)域知識。文獻(xiàn)[12-13]中提出了基于語義網(wǎng)絡(luò)的知識表示技術(shù);文獻(xiàn)[14]提出了基于本體的領(lǐng)域知識表示技術(shù);文獻(xiàn)[15]詳細(xì)介紹了基于領(lǐng)域驅(qū)動的知識發(fā)現(xiàn)方法，提出了獲取專家領(lǐng)域知識的算法和領(lǐng)域驅(qū)動的Semantic-Apriori算法;文獻(xiàn)[16]首次提出了一個基于本體的空間co-location規(guī)則挖掘的一般框架，通過引入約束規(guī)則和多次過濾得到了精簡有效的空間co-location挖掘結(jié)果；本文則簡化了文獻(xiàn)[16]的方法，分類基于領(lǐng)域知識的語義規(guī)則并應(yīng)用到挖掘過程中。

2 相關(guān)概念和定義

2.1 Co-location相關(guān)概念

不同的空間特征代表了不同類別的空間數(shù)據(jù)，通常也稱為空間對象(spatial object)，常用f表示。比如房子、超市、學(xué)校、人等在概念上可以形成一個類別，都可以稱為一個空間特征?？臻g特征集是所有空間數(shù)據(jù)劃分類別的集合，常用F表示，記為F={f1,f2,…,fn}。一個空間co-location模式c是F的一個子集，c中的特征個數(shù)|c|稱為模式c的階數(shù)。空間區(qū)域中一個具體位置上的一個空間數(shù)據(jù)稱為一個空間實例，為了區(qū)分不同特征的不同實例，給每個特征中的每個實例一個唯一的編號。于是，每一個空間實例被記為“特征名.實例編號”，如圖1所示，圖中共有4個空間特征A、B、C和D，空間特征A有4個實例A.1、A.2、A.3和A.4，B有5個實例B.1、B.2、B.3、B.4和B.5，C有3個實例C.1、C.2和C.3，D有2個實例D.1和D.2。如果兩個空間實例之間的歐氏距離不大于用戶給定的一個距離閾值d，那么稱這兩個空間實例滿足空間鄰近關(guān)系。為了便于描述，將滿足鄰近關(guān)系的空間實例在圖中用實線連接。

圖1 空間特征及其實例示例

如果一個空間實例集合I中，兩兩實例均滿足空間鄰近關(guān)系，則稱I是一個團(tuán)。如果團(tuán)I包含了co-location模式c中的所有特征，并且I的任何一個子集無法包含c中的所有特征，那么I被稱為c的一個行實例。例如，在圖1中，實例集合{A.3,B.3,D.1}是模式{A,B,D}的一個行實例。一個模式c的所有行實例的集合稱為c的表實例，記為T(c)。例如，圖1中，T({A,B,C})={{A.2,B.4,C.2},{A.3,B.3,C.1}}。

在co-location模式挖掘中，采用參與度PI來衡量模式的有趣性(頻繁性)，PI被定義為模式中所有特征的參與率(ParticipationRatio，PR)的最小值[1-7]。對于一個k階模式c={f1,f2,…,fk}，特征fi(1≤i≤k)在c中的參與率PR被定義為fi在T(c)中不重復(fù)出現(xiàn)的實例個數(shù)與fi的總實例個數(shù)的比值。如果模式c的參與度PI不小于用戶給定的閾值min_prev，那么稱模式c是頻繁的(有趣的)。

在圖1中，對于模式c={A,B,C}，其表實例為{{A.2,B.4,C.2},{A.3,B.3,C.1}}，由PR和PI的定義可得PI(c)=min{2/4, 2/5, 2/3}=2/5。若min_prev=0.3, 那么{A,B,C}是一個頻繁的co-location模式。

2.2 領(lǐng)域驅(qū)動相關(guān)概念

領(lǐng)域知識通常是領(lǐng)域內(nèi)主體(專家、用戶)對經(jīng)驗、規(guī)律和喜好的自然表達(dá)，在實際應(yīng)用中需要將它們轉(zhuǎn)換為計算機(jī)可以理解的形式，也就是領(lǐng)域知識的形式化表達(dá)。目前對于領(lǐng)域知識的形式化表達(dá)的研究相對較成熟，常見的方法有：

1)基于產(chǎn)生式規(guī)則的表達(dá)(或基于條件式規(guī)則的表達(dá)), 其基本形式為p→q?；诋a(chǎn)生式規(guī)則的知識表達(dá)具有自然、靈活、通用性強(qiáng)和易維護(hù)等優(yōu)點。

2)基于語義網(wǎng)絡(luò)的表達(dá)。語義網(wǎng)絡(luò)通過圖(Graph)的方式刻畫領(lǐng)域知識中概念之間的關(guān)系、約束或者相關(guān)行為[15]。語義網(wǎng)絡(luò)能夠清晰直觀地將領(lǐng)域知識表達(dá)出來，易于理解和溝通，同時具有較好的可擴(kuò)展性，在目前的知識圖譜構(gòu)建中使用較多。

3)基于本體的表達(dá)。本體是針對領(lǐng)域?qū)嶓w的本質(zhì)抽象，關(guān)注領(lǐng)域?qū)嶓w的屬性、實體之間的關(guān)聯(lián)、約束和層次關(guān)系等。通常一個完整的本體包括類(概念)、關(guān)系、函數(shù)、公理系統(tǒng)和實體這五個部分。

數(shù)據(jù)挖掘過程可以分為挖掘前、挖掘中和挖掘后三個階段，領(lǐng)域知識可以應(yīng)用于任何一個階段。在挖掘前可以通過領(lǐng)域知識進(jìn)行數(shù)據(jù)預(yù)處理，比如應(yīng)用在數(shù)據(jù)的獲取、轉(zhuǎn)換和加載(ExtractionTransformationLoading,ETL)過程中；在挖掘中，利用領(lǐng)域知識過濾無效候選；在挖掘后，可以利用領(lǐng)域知識進(jìn)行冗余模式的剔除，對挖掘結(jié)果進(jìn)行分類和排序等操作。

2.3 高效用co-location相關(guān)定義

在實際中，不同特征的價值(效用值)往往是千差萬別的，比如天然水晶和玻璃。有時候，同一種特征中不同實例的價值也存在較大的差異，比如10克拉的水晶和100克拉的水晶。

在本文中，考慮更為復(fù)雜的空間實例作為研究對象——帶效用值的空間實例。圖2是六種不同植被的空間分布示例，表1是圖2中每種植被的總效用值，圖2中實例的上標(biāo)數(shù)據(jù)代表該實例的效用值。

在考慮特征中實例效用差異的情況下，采用傳統(tǒng)的PI度量指標(biāo)，可能會遺漏一些有意義的模式或者挖掘出一些沒有意義的模式。

在圖2中，以co-location模式c1={A,B,C}為例，其表實例為{{A.110,B.48,C.29}，{A.37,B.58,C.29}}, 其參與度為PI(c1)=1/4。特征A的實例在模式c1中參與的效用占A總效用的17/28，類似，特征B在c1中的實例效用占比為16/25，特征C的實例效用占比為9/12。若min_prev=0.3，那么模式c1被識別為非有趣的模式。但是，模式c1中每個特征參與的效用都超過了自身總效用的50%，所以c1應(yīng)該是一個有意義的模式。同樣，對于模式c2={E,F},PI(c2)=2/3，若min_prev=0.5，那么c2是一個有趣模式。但是特征E在c2中的實例效用僅占其總效用的4/14，特征F為3/18，在c2中的每個特征參與的效用占比都很少，不應(yīng)該被識別為有趣模式。

圖2 帶效用值的空間實例示例

表1 圖2中每種植被的實例和總效用

Tab.1InstancesandtotalutilityvalueofeachvegetationinFig.2

特征實例總效用AA．110 A．28 A．37 A．4328BB．11 B．21 B．37 B．48 B．5825CC．11 C．29 C．31 C．4112DD．19 D．21 D．3313EE．110 E．22 E．3214FF．12 F．21 F．31518

定義1 帶效用值的空間實例。帶有效用值為v的空間特征fi的第j個實例記為fi.jv，或?qū)嵗齠i.jv的效用記為：u(fi.j)=v。

例如，特征A代表水晶，A.110代表一顆10克拉水晶，其效用為u(A.1)=10。

定義2 特征的總效用。給定空間特征fi及其實例集si,fi的總效用定義為其所有實例的效用之和，形式化描述為：

定義3 特征在模式內(nèi)的參與效用。給定一個k階co-location模式c={f1,f2,…,fk}，特征fi∈c在模式c中的參與效用記為u(fi,c)，形式化為：

定義4 特征在模式中的內(nèi)效用率(Intra-Utility Ratio， IntraUR)。給定一個k階co-location模式c={f1,f2,…,fk}，特征fi∈c在模式內(nèi)的參與效用占其總效用的比值被定義為特征fi在模式c中的內(nèi)效用率，形式化為：

IntraUR(fi,c)代表特征fi對模式c的直接貢獻(xiàn)或者影響。例如，在圖2中，特征A在模式c={A,B,C}中的內(nèi)效用率為:

定義5 特征在模式中的間效用率(Inter-Utility Ratio, InterUR, InterUR)。給定一個k階co-location模式c={f1,f2,…,fk}，特征fi∈c在模式c中的間效用率定義為：

InterUR(fi,c)代表特征fi對模式c內(nèi)其他特征的影響程度(或貢獻(xiàn)程度)，代表特征的一種間接影響。比如，電子產(chǎn)品促銷活動中，電腦的銷售會對鼠標(biāo)、鍵盤等外部設(shè)備的銷售有一定的影響。在圖2中，特征A在模式c={A,B,C}中的間效用率為:

定義6 特征的效用參與率(Utility Participation Ratio, UPR)。給定一個k階co-location模式c={f1,f2,…,fk}，特征fi∈c在模式c中的效用參與率UPR(fi,c)定義為特征在模式c中的內(nèi)效用率(IntraUR)和間效用率(InterUR)的加權(quán)和，形式化為：

UPR(fi,c)=w1×IntraUR(fi,c)+w2×InterUR(fi,c)

其中:0≤w1,w2≤1,w1+w2=1。

UPR考慮了特征在模式中的直接影響(內(nèi)效用率)和間接影響(間效用率)，綜合地評價了特征在模式中的重要程度。w1、w2分別代表IntraUR和InterUR的權(quán)重，通常由用戶指定。以圖2為例，設(shè)w1=0.7,w2=0.3, 對于模式c={A,B,C}，特征B的效用參與率計算如下：

UPR(B,c)=0.7×IntraUR(B,c)+

0.3×InterUR(B,c)=0.643

定義7 模式的效用參與度(Utility Participation Index, UPI)。給定一個k階co-location模式c={f1,f2,…,fk}，模式c的效用參與度UPI(c)被定義為c中所有特征的UPR值中的最小值，形式化描述如下：

由定義7可知，UPI的取值范圍為[0,1]。當(dāng)忽略特征之間和同一特征的不同實例之間的差異性以及特征之間影響時，UPI就等于PI。所以，基于PI的co-location模式挖掘是基于UPI的模式挖掘的一種特例。當(dāng)一個模式c的UPI(c)≥λ(用戶指定的效用參與度閾值)時，稱c是一個高效用co-location模式。

傳統(tǒng)的頻繁co-location模式不一定是高效用模式；同樣，高效用co-location模式未必是頻繁模式。例如，在圖2中，當(dāng)w1=w2=0.5，λ=0.5時，模式{E,F}的表實例為{{E.22,F.21}, {E.32,F.12}}，PI=0.67>λ，UPI({E,F})=0.23<λ；模式{C,D}的表實例為{{C.29,D.19}, {C.29,D.21}}，PI({C,D})=0.25<λ，UPI({C,D})=0.76>λ。

同時，與PI不同，UPI并不滿足向下閉合性質(zhì)，例如在圖2中，設(shè)w1=w2=0.5，模式{A,D}的表實例為{{A.37,D.19},UPI({A,D})=0.47；模式{A,C,D}的表實例為{{A.37,C.29,D.19},UPI({A,C,D})=0.485>UPI({A,D})。不滿足向下閉合性質(zhì)意味著挖掘基于UPI的高效用co-location模式比挖掘基于PI的頻繁co-location模式的難度更大。

不過，根據(jù)UPI的定義，可以證明以下引理：

引理1 若co-location模式c的表實例為空，那么c的所有超模式c′?c的UPI(c′)=0。

證明 假設(shè)模式c的表實例為空，則c的任意超集c′?c的表實例一定為空，所以，對于任意fi∈c′有UPR(fi,c′)=0，則UPI(c′)=0。

根據(jù)引理1，如果一個模式c的表實例為空，那么它的所有超集c′?c都是非高效用co-location模式。

本文采用語義約束規(guī)則來形式化表達(dá)高效用co-location模式挖掘中涉及到的領(lǐng)域知識。結(jié)合co-location模式的挖掘目標(biāo)，定義了三種語義規(guī)則，分別為：抽象語義規(guī)則、分類語義規(guī)則和互斥語義規(guī)則，具體如下：

定義8 抽象語義規(guī)則。給定空間特征集F={f1,f2,…,fn}， 將m(m

例如：在植被分布數(shù)據(jù)集中，可以將“青岡林、石櫟林、潤楠林、木荷林、白克木林和蚊母樹林”等特征抽象為“常綠闊葉林”。抽象語義規(guī)則有助于獲取更高層次的知識。

定義9 分類語義規(guī)則。給定空間特征集F, 根據(jù)特征fi∈F的某個屬性取值將特征fi具體細(xì)分為m(m≥1)個特征，形式化定義如下:

在植被分布數(shù)據(jù)集中，可以根據(jù)植被實例的位置信息對植被進(jìn)行細(xì)分。比如對松樹根據(jù)實例所在位置細(xì)分為三葉松(秦嶺地區(qū))、白皮松(關(guān)山林區(qū))和云南松(川滇地區(qū))，即：

分類語義規(guī)則可以有效地細(xì)分空間特征，使挖掘結(jié)果更加具有可行動性，通常這些結(jié)果對具體事務(wù)的執(zhí)行者或者實施者可能更加有效。

定義10 互斥語義規(guī)則。給定空間特征集F，若特征fi,fj∈F不能同時出現(xiàn)，則稱fi與fj互斥，形式化表述為：

例如，在植被數(shù)據(jù)集中，耐旱植物和喜濕植物不會生長在一起，如鴨跖草和仙人掌?；コ庹Z義規(guī)則能夠有效地排除異常數(shù)據(jù)導(dǎo)致的錯誤挖掘結(jié)果。

下面是一條分類語義規(guī)則的XML信息示例：

F1 F2 91.0 25.0 65.0

150.0 75.0 165.0

…

…

其中：rule標(biāo)簽代表一條規(guī)則；type屬性表示語義規(guī)則的類型，取值空間為“AR”(抽象語義規(guī)則)、“CR”(分類語義規(guī)則)或“MR”(互斥語義規(guī)則)；location子標(biāo)簽規(guī)定了該條規(guī)則作用的空間區(qū)域。

3 領(lǐng)域驅(qū)動挖掘的一般框架

對于基于UPI的空間高效用co-location模式挖掘，可以采用“生成-測試”形式的類Apriori方法。整個挖掘過程主要包含三個階段：

PhaseⅠ: 數(shù)據(jù)預(yù)處理、空間鄰近關(guān)系計算；

PhaseⅡ: 候選模式的生成以及候選剪枝；

PhaseⅢ: 候選模式的表實例計算，UPI值計算，以及篩選高效用co-location模式。

將領(lǐng)域知識作為一種額外的數(shù)據(jù)資源，進(jìn)行形式化表示并應(yīng)用于空間高效用co-location模式的挖掘過程中。圖3給出了一個領(lǐng)域驅(qū)動的空間高效用co-location模式挖掘的一般框架。

在圖3的挖掘框架中，將抽象語義規(guī)則和分類語義規(guī)則作用于PhaseⅠ階段，將互斥規(guī)則作用于PhaseⅡ階段，通過互斥規(guī)則來提前剪枝候選模式。一次挖掘工作結(jié)束后，如果專家從挖掘結(jié)果中獲取了新的領(lǐng)域知識，算法利用擴(kuò)增后的領(lǐng)域知識再次進(jìn)行挖掘；反復(fù)執(zhí)行此過程，直到?jīng)]有新的領(lǐng)域知識加入。

圖3 一個領(lǐng)域驅(qū)動的高效用co-location挖掘框架

下面給出領(lǐng)域驅(qū)動的空間高效用co-location模式挖掘的基本算法：

輸入：

F={f1,f2,…,fn}：空間特征集；

S：帶效用值的空間實例集；

R：空間鄰近關(guān)系(實際中用距離閾值d來度量)；

w1：特征的IntraUR權(quán)重；

w2：特征的InterUR權(quán)重；

λ：高效用模式的UPI閾值；

ARs：抽象語義規(guī)則集；

CRs：分類語義規(guī)則集；

MRs：互斥語義規(guī)則集。

輸出：

UPI值大于等于λ的高效用co-location模式。

變量：

SN={SNf1,SNf2,…,SNfn}：所有空間特征的星型鄰居；

k：co-location模式的階數(shù)；

Ck：k階候選高效用co-location模式；

CTIk：k階候選高效用co-location模式的表實例；

Hk：k階高效用co-location模式集；

H：所有高效用co-location模式集；

NonHk：k階非高效用co-location模式集；

new_DK_flag：代表是否有新的領(lǐng)域知識加入。

過程：

1)

new_DK_flag=true;

//當(dāng)有新的領(lǐng)域知識加入時需要反復(fù)挖掘

2)

while(new_DK_flag) do

//利用抽象規(guī)則，分類規(guī)則進(jìn)行預(yù)處理

3)

abstract_features(F,S,ARs);

4)

classify_features(F,S,CRs);

//生成星型鄰居集合

5)

SN=gen_star_neighborhoods(F,S,R);

6)

H1=F;k=2;

//判斷是否還能夠生成k+1階候選模式

7)

while (not emptyHk-1and not emptyNonHk-1) do

//通過k-1階模式生成k階候選模式

8)

Ck=gen_candidate_colocations(Hk-1,NonHk-1);

//利用互斥規(guī)則和引理進(jìn)行剪枝

9)

Ck=mutex_rules_pruning(Ck,MRs);

10)

Ck=other_pruning(Ck);

//計算未被剪枝模式的表實例

11)

CTIk=gen_table_instance(Ck,SN);

//計算模式的效用參與度

12)

compute_UPI(Ck,CTIk);

13)

Hk=select_high_utility_colocations(Ck，λ);

14)

NonHk=U(Ck-Hk);

15)

k=k+1;

16)

End do

17)

ReturnH=∪(H1,H2,…,Hk);

18)

new_DK_flag=

update_domain_knowledges(ARs,CRs,MRs,H);

19)

End do

算法第3)～6)行屬于Phase I階段, 利用抽象語義規(guī)則對多個特征進(jìn)行抽象，利用分類語義規(guī)則對特征進(jìn)行細(xì)分，這個過程會調(diào)整空間數(shù)據(jù)中的特征集和特征實例的分布。然后，采用網(wǎng)格劃分或者平面掃描的方式[3]計算出所有空間鄰近關(guān)系，將空間鄰近關(guān)系物化為星型鄰居模式[5]，初始化所有1階模式的UPI為1.0，并將其放入H1。

第8)～10)行屬于PhaseⅡ段，第8)行主要負(fù)責(zé)從k-1(k≥2)階模式(高效用Hk-1和非高效用NonHk-1)中擴(kuò)展生成k階候選高效用co-location模式。生成候選模式的方式為：

Ck={c′|c′=c∪{fk},

c∈Hk-1∪NonHk-1,fk>fi∈c}

其中Ck是候選模式，特征按照字典序有序。當(dāng)k=2時，直接從星型鄰居模型中產(chǎn)生二階候選模式。該方法不會遺漏任何候選模式，同時也不會重復(fù)生成候選模式。接著，在第9)行采用互斥語義規(guī)則，過濾同時包含互斥語義規(guī)則中的特征的候選模式。第10)行采用前文介紹的引理過濾候選模式。

第11)～14)行屬于PhaseⅢ階段，第11)行主要通過擴(kuò)展k-1階模式的表實例來計算k(k≥2)階候選模式的表實例。當(dāng)k=2時，可以直接從星型鄰居模型中查找2階候選模式的表實例；當(dāng)k>2時，通過擴(kuò)展k-1階模式的表實例，計算表實例方式采用join-less算法的方法[5]。然后在第12行)根據(jù)候選模式的表實例計算UPI值，在第13)～14)行將UPI大于等于λ的模式放入Hk中，將其余模式放入NonHk中。

第15)行執(zhí)行k=k+1，代表接下來的循環(huán)中將挖掘k+1階模式。隨著co-location模式階數(shù)的增長，重復(fù)執(zhí)行第8)～10)行，直到無法生成更高階模式為止。

第18)行執(zhí)行和用戶的交互，若用戶有新的領(lǐng)域知識加入，則重新執(zhí)行整個挖掘過程，直到?jīng)]有新的規(guī)則加入為止。

4 實驗評估與分析

4.1 實驗數(shù)據(jù)集

實驗中采用的數(shù)據(jù)為人工合成數(shù)據(jù)，所有人工合成數(shù)據(jù)分布在1 000×1 000的區(qū)域中，特征實例的效用在服從正態(tài)分布情況下隨機(jī)產(chǎn)生，特征的實例個數(shù)和特征的總效用均為隨機(jī)生成。在實驗部分，F(xiàn)代表空間特征集，d代表空間鄰近關(guān)系距離閾值，n代表實例個數(shù)，w1代表IntraUR的權(quán)重，w2代表InterUR的權(quán)重，λ代表UPI閾值，ARs代表抽象語義規(guī)則集，CRs代表分類語義規(guī)則集，MRs代表互斥語義規(guī)則集。

4.2 實驗運(yùn)行環(huán)境

實驗中涉及的所有算法均用Java語言實現(xiàn)，硬件環(huán)境為：IntelCorei3 2.13GHz，4GB內(nèi)存；軟件環(huán)境為：Windows10，JRE1.8。

4.3 效用占比評估

為了驗證本文提出的度量指標(biāo)UPI相比傳統(tǒng)的PI[3]和PUR[9-10]興趣度度量更為合理，設(shè)置實驗數(shù)據(jù)集信息為：|F|=15，d=30，n=10 000；實驗參數(shù)為：w1=0.9，w2=0.1，λ=0.01，語義規(guī)則集為空。圖4(a)展示的是在PI、PUR和UPI三種不同興趣度度量指標(biāo)下挖掘到的top-k有趣模式的Q(c)值之和，而圖4(b)則展示了三種不同度量指標(biāo)挖掘結(jié)果中不同階數(shù)的top-20有趣模式的平均效用。結(jié)果表明，基于UPI的挖掘結(jié)果在上述兩方面的值均高于基于PI和PUR的結(jié)果，反映了基于UPI度量挖掘到co-location模式的總效用和平均效用均更高。

4.4 頻繁性評價

模式的頻繁性代表了模式存在的普遍性，其對挖掘結(jié)果的可用性具有重要意義。PI(參與度)是模式頻繁性的經(jīng)典衡量指標(biāo)，本節(jié)在實驗數(shù)據(jù)集及參數(shù)信息設(shè)置不變的情況下，對比基于不同興趣度度量的挖掘結(jié)果的頻繁性。

圖5(a)顯示了三種度量指標(biāo)下的挖掘結(jié)果中top-k模式的頻繁性之和；圖5(b)顯示了三種度量指標(biāo)下挖掘到的有趣模式中各階的top-20有趣模式的平均頻繁性。由于基于PI度量指標(biāo)的目標(biāo)是挖掘頻繁性高的模式，基于PI的挖掘結(jié)果總是具有最高的頻繁性。實驗結(jié)果表明，基于UPI的結(jié)果的頻繁性在各階上都高于基于PUR的結(jié)果，并且僅僅略低于PI的結(jié)果。

圖4 三種度量指標(biāo)的效用占比評估

圖5 三種度量指標(biāo)的頻繁性評估

4.5 領(lǐng)域知識對挖掘過程的影響

本節(jié)的實驗在模擬數(shù)據(jù)上加入了一些領(lǐng)域知識，以對比加入領(lǐng)域知識以后高效用模式的數(shù)量變化。數(shù)據(jù)集和參數(shù)信息為：|F|=15，n=20 000，d=20，w1=0.9，w2=0.1，λ=0.7，ARs語義規(guī)則集減少了5個特征，CRs語義規(guī)則集新增了5個特征，MRs語義規(guī)則定義了3對特征集。表2給出了單獨使用每個規(guī)則集對高效用模式數(shù)量的影響。在表2中，ARs規(guī)則集減少了特征，但是增加了抽象特征實例數(shù)和分布范圍，所以增加了部分高效用模式；CRs規(guī)則集增加了空間特征，將特征的實例劃分到不同的新特征，降低了新特征實例的部分范圍，從而會減少高效用模式的數(shù)量。對于MRs規(guī)則集，互斥規(guī)則使得原來可能高效的模式由于保存了互斥特征而直接變?yōu)闊o效模式。在實際情況中，尤其是在植被數(shù)據(jù)中，互斥的植物在自然條件下基本不會出現(xiàn)在同一鄰域內(nèi)，所以可以通過互斥規(guī)則剔除異常模式。由于領(lǐng)域知識會改變數(shù)據(jù)集中的特征和實例的分布情況，所以實驗中發(fā)現(xiàn)領(lǐng)域知識對算法效率的影響是不確定的。

表2 不同語義規(guī)則對高效用模式數(shù)量的影響

5 結(jié)語

在實際中，不同空間特征和同一特征的不同實例的價值(效用)存在差異性，因此，本文提出研究帶效用值的空間實例，同時，提出了IntraUR(內(nèi)效用率)和InterUR(間效用率)分別衡量特征對模式的直接影響和間接影響，通過UPR(效用參與率)來衡量特征對模式的綜合影響，提出的度量指標(biāo)兼顧了模式的普遍性和效用兩方面。另一方面，通過引入語義規(guī)則將領(lǐng)域背景知識和約束條件等用于挖掘過程，以挖掘用戶真正感興趣的模式。在未來研究工作中需要進(jìn)一步研究高效的剪枝策略；在領(lǐng)域驅(qū)動挖掘方面，將考慮基于本體的高效用co-location模式挖掘。

)

[1]MORIMOTOY.Miningfrequentneighboringclasssetsinspatialdatabases[C]//KDD’01:Proceedingsofthe7thACMSIGKDDInternationalConferenceonKnowledgeDiscoveryandDataMining.NewYork:ACM, 2001: 353-358.

[2]SHEKHARS,HUANGY.Discoveryspatialco-locationpatterns:asummaryofresults[C]//SSTD2001:Proceedingsofthe7thInternationalSysmposiumonAdvancesinSpatialandTemporalDatabases,LNCS2121.Berlin:Springer-Verlag, 2001: 236-256.

[3]HUANGY,SHEKHARS,XIONGH.Discoveringcolocationpatternsfromspatialdatasets:ageneralapproach[J].IEEETransactionsonKnowledgeandDataEngineering, 2004, 16(12): 1472-1485.

[4]YOOJS,SHEKHARS,SMITHJ,etal.Apartialjoinapproachforminingco-locationpatterns[C]//GIS’04:Proceedingsofthethe12thAnnualACMInternationalWorkshoponGeographicInformationSystems.NewYork:ACM, 2004: 241-249.

[5]YOOJS,SHEKHARS,CELIKM.Ajoin-lessapproachforspatialco-locationpatternmining:asummaryofresult[C]//ICDM’05:Proceedingsofthethe5thIEEEInternationalConferenceonDataMining.Washington,DC:IEEEComputerSociety, 2005: 813-816.

[6]WANGL,BAOY,LUJ,etal.Anewjoin-lessapproachforco-locationpatternmining[C]//CIT2008:Proceedingsofthe8thIEEEInternationalConferenceonComputerandInformationTechnology.Piscataway,NJ:IEEE, 2008: 197-202.

[7]WANGL,BAOY,LUZ.Efficientdiscoveryofspatialco-locationpatternsusingtheiCPI-tree[J].TheOpenInformationSystemsJournal, 2009, 3(2): 69-80.

[8] 王麗珍,陳紅梅.空間模式挖掘理論與方法[M].北京:科學(xué)出版社,2014: 4-13.(WANGLZ,CHENHM.TheoryandMethodofSpatialPatternMining[M].Beijing:SciencePress, 2014: 4-13.)

[9] 楊世晟,王麗珍,蘆俊麗,等.空間高效用co-location模式挖掘技術(shù)初探[J].小型微型計算機(jī)系統(tǒng),2014,35(10):2302-2307.(YANGSC,WANGLZ,LUJL,etal.Primaryexplorationforspatialhighutilityco-locationpatterns[J].JournalofChineseComputerSystems, 2014, 35(10): 2302-2307.)

[10]YANGS,WANGL,BAOX,etal.Aframeworkforminingspatialhighutilityco-locationpatterns[C] //FSKD2015:Proceedingsofthethe12thInternationalConferenceonFuzzySystemsandKnowledgeDiscovery.Washington,DC:IEEEComputerSociety, 2015: 631-637.

[11]CAOL.ZHANGC.Domain-drivenactionableknowledgediscoveryintherealworld[C]//PAKDD2006:Proceedingsofthe10thPacific-AsiaConferenceeonAdvancesinKnowledgeDiscoveryandDataMining,LNCS3918.Berlin:Springer-Verlag, 2006: 821-830.

[12]SIMMONSRF.Storageandretrievalofaspectsofmeaningindirectedgraphstructures[J].CommunicationsoftheACM, 1966, 9(3): 211-215.

[13]QUILLIANMR.Semanticmemory[M]//ReadingsinCognitiveScience.SanFrancisco,CA:MorganKaufmannPublishersInc., 1968: 80-101.

[14]GRUBERTR.Atranslationapproachtoportableontologyspecifications[J].KnowledgeAcquisition—SpecialIssue:CurrentIssuesinKnowledge, 1993, 5(2): 199-220.

[15] 朱正祥.領(lǐng)域驅(qū)動知識發(fā)現(xiàn)方法研究[D].大連：大連理工大學(xué),2010:23-56.(ZHUZX.Researchonthemethodofdomain-drivenknowledgediscovery[D].Dalian:DalianUniversityofTechnology, 2010: 23-56.)

[16] 包旭光,王麗珍,方園.OSCRM:一個基于本體的空間co-location規(guī)則挖掘框架[J].計算機(jī)研究與發(fā)展,2015,52(S1):74-80.(BAOXG,WANGLZ,FANGY.OSCRM:Aframeworkofontology-basedspatialco-locationrulemining[J].JournalofComputerResearchandDevelopment, 2015, 52(S1): 74-80.)

ThisworkispartiallysupportedbytheNationalNaturalScienceFoundationofChina(61472346, 61662086),theNaturalScienceFoundationofYunnanProvince(2016FA026, 2015FB114, 2015FB149).

JIANG Wanguo, born in 1990, M.S.candidate.His research interests include spatial data mining, knowledge discovery.

WANG Lizhen, born in 1962, Ph.D., professor.Her research interests include data mining, database.

FANG Yuan, born in 1990, Ph.D.candidate.Her research interests include spatial data mining, knowledge discovery.

CHEN Hongmei, born in 1976, Ph.D., associate professor.Her research interests include data mining, knowledge discovery.

Domain-driven high utility co-location pattern mining method

JIANG Wanguo, WANG Lizhen*, FANG Yuan, CHEN Hongmei

(SchoolofInformationScienceandEngineering,YunnanUniversity,KunmingYunnan650091,China)

A spatial co-location pattern represents a subset of spatial features whose instances are frequently located together in spatial neighborhoods.The existing interesting metrics for spatial co-location pattern mining do not take account of the difference between features and the diversity between instances belonging to the same feature.In addition, using the traditional data-driven spatial co-location pattern mining method, the mining results often contain a lot of useless or uninteresting patterns.In view of the above problems, firstly, a more general study object — spatial instance with utility value was proposed, and the Utility Participation Index (UPI) was defined as the new interesting metric of the spatial high utility co-location patterns.Secondly, the domain knowledge was formalized into three kinds of semantic rules and applied to the mining process, and a new domain-driven iterative mining framework was put forward.Finally, by the extensive experiments, the differences between mined results with different interesting metrics were compared in two aspects of utility ratio and frequency, as well as the changes of the mining results after taking the domain knowledge into account.Experimental results show that the proposed UPI metric is a more reasonable measure in consideration of both frequency and utility, and the domain-driven mining method can effectively find the co-location patterns that users are really interested in.

spatial pattern mining; co-location pattern; high utility co-location pattern; interesting metric; domain-driven; semantic rule

2016- 08- 12;

2016- 09- 11。

國家自然科學(xué)基金資助項目(61472346, 61662086)；云南省自然科學(xué)基金資助項目(2016FA026, 2015FB114, 2015FB149)。

江萬國(1990—),男,陜西漢中人,碩士研究生,主要研究方向:空間數(shù)據(jù)挖掘、知識發(fā)現(xiàn); 王麗珍(1962—),女,山東博興人,教授,博士,CCF高級會員,主要研究方向:數(shù)據(jù)挖掘、數(shù)據(jù)庫; 方圓(1990—),女,云南麗江人,博士研究生,主要研究方向:空間數(shù)據(jù)挖掘、知識發(fā)現(xiàn); 陳紅梅(1976—),女,重慶人,副教授,博士,主要研究方向:數(shù)據(jù)挖掘、知識發(fā)現(xiàn)。

1001- 9081(2017)02- 0322- 07

10.11772/j.issn.1001- 9081.2017.02.0322

TP311.13

A