模糊特征的top-k平均效用co-location模式挖掘

李金紅，王麗珍，周麗華

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

伴隨著互聯(lián)網(wǎng)和無線通信技術(shù)等各項高新技術(shù)的不斷普及和發(fā)展，大量包含空間位置信息的數(shù)據(jù)不斷產(chǎn)生，人們對空間數(shù)據(jù)挖掘越來越感興趣。空間co-location 模式挖掘作為空間數(shù)據(jù)挖掘的一個熱門研究方向，受到了更多的關(guān)注和期待?？臻gcolocation 模式是一組空間特征的子集，它們的實例在空間鄰域中頻繁并置出現(xiàn)。例如西尼羅河病毒往往發(fā)生在蚊子泛濫、飼養(yǎng)家禽的區(qū)域；醫(yī)院、藥店、花店經(jīng)常并置出現(xiàn)等。近幾年來，Huang、Yoo、Wang等學(xué)者提出了多個空間co-location 模式挖掘的算法，這些算法大多以特征實例參與并置的程度來度量空間co-location 模式的有趣性，并沒有對各特征的重要程度或價值進(jìn)行區(qū)分和研究，這種傳統(tǒng)的空間colocation 模式挖掘方法容易忽略那些不頻繁出現(xiàn)，卻十分有價值的模式。空間高效用co-location 模式挖掘在很大程度上彌補(bǔ)了頻繁co-location 模式挖掘所造成的信息遺漏。然而，空間高效用co-location 模式挖掘只考慮了并置特征的效用，忽略了模式長度帶來的影響，導(dǎo)致挖掘出的模式包含一些用戶不感興趣的模式或者不是用戶真正感興趣的模式，并且是通過用戶設(shè)定頻繁性閾值來獲取有價值的模式，但由于實際應(yīng)用的不確定性，用戶在設(shè)置閾值時需要反復(fù)嘗試、多次分析，整個過程繁瑣而復(fù)雜，設(shè)置的閾值過大可能挖掘不出有價值的模式，設(shè)定的閾值過小，導(dǎo)致挖掘到的模式過多，會消耗大量的時間和內(nèi)存，因此用top-挖掘取代設(shè)置最小效用閾值的挖掘是有積極意義的。

在實際生活中，模糊特征無處不在，比如“大型游樂場”“高檔餐廳”“嚴(yán)重污染”等，模糊特征在許多應(yīng)用中也起著十分重要的作用,例如地球科學(xué)、公共衛(wèi)生等。目前對模糊特征的研究范圍十分廣泛，但在空間co-location 模式挖掘的研究中主要還是基于模糊特征實例參與并置的程度來度量co-location 模式的有趣性，并沒有對各模糊特征的重要程度或價值進(jìn)行區(qū)分和研究，容易忽略那些不頻繁出現(xiàn)，卻十分有價值的模式。例如污染的治理，治理不同類型的污染需要投入的資金不一樣，一種不頻繁發(fā)生卻需要投入大量資金來治理的污染組合可能被傳統(tǒng)的co-location 模式挖掘忽略。

為了解決以上的問題，本文將模糊集理論與高平均效用co-location 模式挖掘結(jié)合起來，不需要用戶設(shè)定最小效用閾值，找到模糊特征的top-平均效用co-location 模式。主要貢獻(xiàn)包括：

（1）基于模糊集理論，定義了模糊特征的外部效用、內(nèi)部效用以及模糊平均效用。

（2）分析了擴(kuò)展模糊平均效用的“向下閉合”性質(zhì)，設(shè)計了一個模糊特征的top-平均效用co-location模式挖掘的基本算法。

（3）分析基本算法的性能，提出了一種基于局部擴(kuò)展模糊效用剪枝的top-平均效用co-location 模式挖掘的優(yōu)化算法。

（4）在合成數(shù)據(jù)集和真實數(shù)據(jù)集上進(jìn)行了廣泛的實驗，證明了所提出算法的實用性、高效性和魯棒性。

1 相關(guān)工作

空間數(shù)據(jù)挖掘，主要是在空間數(shù)據(jù)集中發(fā)現(xiàn)未知知識，提取感興趣的空間模式或特征等?？臻gcolocation 模式挖掘是空間數(shù)據(jù)挖掘的一個重要研究方向，最早在文獻(xiàn)[1]中被提出，以最小參與率（稱為參與度PI）作為空間co-location 模式挖掘的有趣性度量指標(biāo)，由于PI 滿足“向下閉合”性質(zhì)，利用這一性質(zhì)能對候選模式進(jìn)行有效的剪枝。近年來空間colocation 模式挖掘的很多研究都集中在候選模式的剪枝和表實例的計算優(yōu)化兩方面，例如基于完全連接操作的join-base 算法、基于部分連接操作的partialjoin 算法和基于無連接操作的join-less算法等。文獻(xiàn)[10]提出了在確定數(shù)據(jù)集上的top-閉co-location模式挖掘方法，文獻(xiàn)[11]提出了基于不確定數(shù)據(jù)的top-頻繁co-location 模式挖掘方法。文獻(xiàn)[12]首次將模糊特征的概念引入到空間co-location 模式挖掘中，定義了模糊參與率、模糊參與度的概念，分析其所滿足的性質(zhì)，并分別從剪枝特征、減少實例間連接、改進(jìn)剪枝步驟等幾方面提出了剪枝算法。

隨著Yao 等首次將高效用的概念引入到事務(wù)數(shù)據(jù)中，高效用模式挖掘得到了廣泛的關(guān)注與研究，目前已有許多針對事務(wù)數(shù)據(jù)庫的高效用模式挖掘方法。文獻(xiàn)[16]首次提出top-高效用模式挖掘方法，文獻(xiàn)[17]相繼提出了針對top-高效用模式挖掘的改進(jìn)方法。文獻(xiàn)[7]首次將效用的概念引入到空間co-location 模式挖掘中，定義了模式效用、模式效用率（pattern utility ratio,PUR）等概念，并把模式效用率（PUR）作為空間高效用co-location 模式有趣性的度量指標(biāo)。文獻(xiàn)[8]進(jìn)一步考慮了同一特征的不同實例的效用值差異，提出了一種新的效用參與度（utility participation index,UPI）作為高效用co-location 模式的有趣性度量指標(biāo)，但該方法注重每個實例的參與性，忽略了一些效用值很小，但對模式的貢獻(xiàn)值很大（參與度大）的特征。為此文獻(xiàn)[9]進(jìn)一步提出了一種確定特征在模式中的效用權(quán)重的方法。文獻(xiàn)[18]首次將模糊特征的概念引入到空間高效用co-location模式挖掘中。但文獻(xiàn)[7-9,18]都是通過人為設(shè)定閾值來獲取有價值的模式，而且獲取的模式?jīng)]有考慮模式長度對模式效用的影響。

高平均效用模式挖掘也叫高平均效用項集挖掘，最早在文獻(xiàn)[19]中提出，一個項集只要滿足其效用值除以項的個數(shù)不小于用戶預(yù)定義的最小平均效用閾值，那么該項集就可以稱為一個高平均效用項集。Lin 等提出了用于挖掘高平均效用項集的HAUP 樹結(jié)構(gòu)和HAUP 增長算法。Lan 等提出了一種基于預(yù)測的高平均效用項集挖掘（high averageutility itemset mining,HUAI）算法。

本文首次將模糊特征的平均效用的概念引入colocation 模式挖掘中，研究模糊特征的top-平均效用co-location 模式挖掘的問題。

2 相關(guān)定義

本章首先介紹了傳統(tǒng)co-location 模式挖掘的基本概念和一個經(jīng)典的空間數(shù)據(jù)的星型鄰居物化模型，接著定義了模糊特征的top-平均效用co-location模式挖掘的相關(guān)概念。

2.1 傳統(tǒng)co-location 模式挖掘

空間特征集是所有空間數(shù)據(jù)劃分類別的集合，常用表示，記為={,,…,f}。把一個具體位置上的特征稱為一個空間實例，將空間實例的集合稱為實例集,記為=??…?S，其中S(1 ≤≤)是對應(yīng)空間特征f的實例集合。為了區(qū)別不同特征的不同實例，給每一個實例一個唯一的編號，一個空間實例信息通常包括（實例所屬特征，實例編號，空間位置）。如圖1 所示，圖中共有5 個特征、、、和，空間特征有5 個實例1、2、3、4 和5，有4 個實例1、2、3 和4，有5 個實例1、2、3、4 和5，有4 個實例1、2、3、4，有3 個實例1、2 和3。如果兩個空間實例之間的歐氏距離小于等于用戶給定的一個距離閾值，那么就稱這兩個空間實例在空間中是鄰近的，為了便于描述，將滿足鄰近關(guān)系的空間實例在圖中用實線連接，如圖1 中的5 和3。其中（5,0.7）中的0.7 表示實例5 對模糊特征的隸屬度，具體的將在2.3 節(jié)進(jìn)行介紹。

圖1 空間模糊特征及其實例分布示例Fig.1 Example of spatial fuzzy features and instances

對于空間特征集的一個子集，稱為空間模式，記為={,,…,f}，其中的長度稱為模式的階數(shù)。對于任意一個空間實例集={,,…,i}，如果中任意兩個實例都滿足空間鄰近關(guān)系，則稱是一個團(tuán)實例，如果團(tuán)實例包含了co-location 模式中的所有特征，并且中的任何一個子集都無法包含的所有特征，那么就稱為模式的一個行實例，記為()。一個模式的所有行實例的集合稱為的表實例，記為()。

2.2 星型鄰居物化模型

空間數(shù)據(jù)的星型鄰居物化模型是Yoo等在文獻(xiàn)[4]提出的，星型鄰居模型是經(jīng)典的join-less 挖掘算法的基礎(chǔ)，以下將介紹星型鄰居和星型實例的相關(guān)定義。

（星型鄰居）給定一個空間實例i∈，它的特征類型是f∈，i的星型鄰居被定義為一些空間實例的集合={i∈|i=i∨(f＞f∧(i,i))}，其中f∈為i的特征類型，“＞”表示特征名的字典序，是空間鄰近關(guān)系。

（星型實例）的星型鄰居集={,,…,i}?，如果它們的特征類型{,,…,f}是不同的，就稱為co-location 模式={,,…,f}的一個星型實例。

數(shù)據(jù)集中所有實例的星型鄰居集組成了空間數(shù)據(jù)庫的星型鄰居物化模型。根據(jù)定義2，一個colocation 模式{,,…,f}的星型實例{,,…,i}可以從中心特征類型為的星型鄰居中收集得到。圖1 空間數(shù)據(jù)集的所有星型鄰居實例如表1 所列，每一行為一個星型鄰居，給一個序號T。

表1 圖1 的空間數(shù)據(jù)集的星型鄰居Table 1 Star neighborhoods of spatial dataset in Fig.1

2.3 模糊特征的top-k平均效用co-location模式

（模糊特征及其隸屬度）模糊特征由空間中一組離散的點(diǎn)組成，定義為={＜,()＞|()＞0}，其中表示的是空間模糊特征，是屬于模糊特征的實例，而()表示空間實例對空間模糊特征的隸屬度。圖2 為圖1 所示空間數(shù)據(jù)集中的一個模糊特征大型游樂場，其5 個游樂場分別用1、2、3、4、5 表示，根據(jù)游樂場的占地面積，各游樂場對大型游樂場的隸屬度值依次為0.1、0.4、0.8、0.9、0.5。

圖2 空間模糊特征C 及其實例分布示例Fig.2 Example of spatial fuzzy feature C and its instances

（模糊特征的外部效用）對于空間數(shù)據(jù)庫中的模糊特征集={,,…,f}，將模糊特征f的外部效用定義為(f)，如表2 對應(yīng)圖1 中空間數(shù)據(jù)集的模糊特征的外部效用。

表2 圖1 中5 個模糊特征的外部效用Table 2 External utility of 5 fuzzy features in Fig.1

內(nèi)部效用在事務(wù)數(shù)據(jù)庫中表示項的數(shù)量，如用戶訪問網(wǎng)站的次數(shù)、商品的銷售數(shù)量等。映射到空間并置模式之中，有如下定義：

（模糊特征的內(nèi)部效用）給定模糊特征的co-location 模式和中的模糊特征f，將的表實例中隸屬于該模糊特征f的不重復(fù)實例的隸屬度之和稱之為模糊特征f在模式的內(nèi)部效用，形式化為：

其中，表示關(guān)系的投影操作，例如co-location 模式={,,}中模糊特征的內(nèi)部效用為(,)=0.4+0.5=0.9，因為的表實例為{{(2,0.4),(2,0.5),(2,0.4)},{(3,0.5),(3,0.7),(3,0.8)},{(3,0.5),(3,0.7),(4,0.9)}}。

（co-location 模式中各模糊特征的效用）對于一個階co-location 模式={,,…,f}，定義模糊特征f的外部效用和它在模式中的內(nèi)部效用的乘積為模糊特征f在模式中的效用，記為(f,)=(f)×(f,)。

例如，模糊特征在co-location 模式{,,}的效用值為(,)=()×(,)=5×0.9=4.5。

（co-location 模式的模糊平均效用）對于一個階co-location 模式，把模式中所有的模糊特征在模式內(nèi)的平均效用之和與模式長度的比值定義為模式的模糊平均效用，記為：

例如co-location 模式={,,}的模糊平均效用為：

co-location 模式的模糊平均效用不滿足“向下閉合”性。

在圖1 所示的空間數(shù)據(jù)集中，co-location 模式{,} 的表實例為{{(3,0.5),(1,0.3)},{(5,0.7),(3,0.6)}}，({})=13，({})=2.1，({,})=3.45，盡 管({,})＞({})，但 是({,})＜({})，因此模式的模糊平均效用不滿足“向下閉合”性。

（top-模糊平均效用co-location 模式）在空間數(shù)據(jù)庫中，將各模式的模糊平均效用值按降序排序，取前個co-location 模式。

3 挖掘算法

傳統(tǒng)的co-location 模式挖掘中的參與度滿足“向下閉合”性，利用這一性質(zhì)，能提前過濾掉大量的候選模式，提升挖掘算法效率和節(jié)省內(nèi)存空間，但由引理1 可知，模糊平均效用值不滿足“向下閉合”性，因此其不能作為提前過濾低模糊平均效用的條件，本章將對模式的模糊平均效用值進(jìn)行擴(kuò)展，提出擴(kuò)展模糊平均效用的概念，并根據(jù)其具有的“向下閉合”性質(zhì)提出一種挖掘模糊特征的top-平均效用colocation 模式的基本挖掘算法。對基本挖掘算法的性能進(jìn)行分析，進(jìn)一步提出局部擴(kuò)展模糊平均效用的概念，并基于此概念提出一種局部擴(kuò)展模糊效用剪枝算法。

3.1 基于擴(kuò)展模糊平均效用的基本算法

（星型鄰居中模糊特征的效用）在一個星型鄰居T中，定義一個模糊特征f的外部效用(f)與內(nèi)部效用(f,T)的乘積作為星型鄰居中模糊特征的效用，記為：

例如在表3 的星型鄰居中，模糊特征的效用為()×(,)=3×1.7=5.1。

表3 圖1 的空間數(shù)據(jù)集的星型鄰居的最大模糊效用Table 3 Maximum fuzzy utility of star neighborhood of spatial dataset in Fig.1

（星型鄰居的最大模糊效用）星型鄰居T的最大模糊效用值表示為(T)，定義為該星型鄰居中所有模糊特征效用的最大值，記為：

例如在表3 中，星型鄰居的最大模糊效用值為()=max{(,),(,),(,)}=2。

（模式的擴(kuò)展模糊平均效用）對于任意一個co-location 模式={,,…,f}的擴(kuò)展模糊平均效用表示為()，定義為所有包含的星型鄰居的最大模糊效用值的和，記為：

例如在表3 中，co-location 模式={,,}的擴(kuò)展模糊平均效用值為()=()+()=2+5.1=7.1。

一個模式的擴(kuò)展模糊平均效用值不大于其子集的擴(kuò)展模糊平均效用值。

設(shè)模式為一個階的擴(kuò)展模糊平均效用模式，模式′為模式的任意一個-1 階子集。因為′為的一個子集，所以所有包含的星型鄰居一定包含′，故包含的星型鄰居是包含′的星型鄰居的子集，那么有:

例如，在表3 中({,,})=7.1,({,})=13.1,({,})=10.6,({,})=14.2，模式{,,}的擴(kuò)展模糊平均效用值不大于其子集的擴(kuò)展模糊平均效用值。

任意一個模式的模糊平均效用值不大于其的擴(kuò)展模糊平均效用值。

對于任意的co-location 模式有：

例如，對于co-location模式={,,}，有()=5.2，()=7.1，()＜()。

根據(jù)引理2 和引理3 可得：如果colocation 模式不是一個top-的模糊平均效用模式，那么的所有超集都不是top-模糊平均效用模式。

根據(jù)定理1，在計算擴(kuò)展模糊平均效用的基礎(chǔ)上，可以提前過濾掉一些不可能成為top-的模糊平均效用co-location 模式，算法1 就是基于擴(kuò)展模糊平均效用來挖掘模糊特征top-平均效用co-location 模式的基本算法。

基本算法

算法的第1 步根據(jù)輸入的空間數(shù)據(jù)集和空間鄰近關(guān)系，把空間數(shù)據(jù)集物化成不相交的星型鄰居集，其中是按照字典序排列的。第2 步初始化各變量值。第3 步是一個由低階到高階反復(fù)迭代的過程，直到不能生成候選模式為止：首先，3.1 步由-1階的候選模式生成階的候選模式。然后，3.2 步計算候選模式的()并和進(jìn)行比較,為top-模糊平均效用co-location 模式中最小的模糊平均效用值。3.3步通過表實例和外部效用表計算階候選模式的模糊平均效用值()，如果()≥，和原中各模式的模糊平均效用值進(jìn)行比較，模糊平均效用值最大的前個模式替換原中的模式。3.4 步階數(shù)自增，算法跳轉(zhuǎn)到第3 步執(zhí)行while 循環(huán)條件判斷，若此時-1 階的候選模式集不為空，則繼續(xù)執(zhí)行while 循環(huán)體內(nèi)部的子句；反之,若C為空，此時不能夠生成階的候選模式，則會跳轉(zhuǎn)到第4 步，返回top-模糊平均效用co-location 模式集，算法結(jié)束。

算法1 的時間復(fù)雜度與候選模糊平均效用colocation 模式數(shù)相關(guān)，而候選模糊平均效用co-location模式數(shù)與距離閾值、特征數(shù)、實例數(shù)等相關(guān)。對于未被剪枝的候選模糊平均效用co-location 模式，則需通過掃描鄰居關(guān)系確定該模式表實例，并通過表實例計算該模式的模糊平均效用值，從而確定top-模糊平均效用co-location 模式。假設(shè)有個候選colocation 模式未被剪枝，且其平均長度為，則確定個候選模糊平均效用co-location模式表實例的時間復(fù)雜度為×()，其中()為確定一個階模式的表實例所用時間，這也是算法最耗時的部分，擴(kuò)展模糊平均效用值的意義就在于通過提前過濾掉不可能成為top-模糊平均效用co-location 模式的候選模式以減少表實例的計算。

3.2 基于局部擴(kuò)展模糊平均效用的優(yōu)化算法

由于基本算法中擴(kuò)展模糊平均效用值過于寬松，導(dǎo)致算法的優(yōu)化效果不明顯。為了更有效地剪枝候選模式，本節(jié)將提出一種基于局部擴(kuò)展模糊平均效用來挖掘模糊特征的top-平均效用co-location模式的優(yōu)化算法。

（co-location 模式在星型鄰居中的效用值）給定一個co-location 模式={,,…,f},其在星型鄰居T中的效用值表示為T()，定義模糊特征的外部效用(f)與其在星型鄰居T中的內(nèi)部效用的乘積之和作為該co-location 模式在星型鄰居中的效用值，記為：

例如co-location模式={,,}在星型鄰居集中的效用值(,,)=5×0.4+5×0.5+3×0.4=5.2。

（星型鄰居中剩余特征的最大模糊效用）星型鄰居T的剩余特征最大模糊效用值表示為(T)，定義為在包含co-location模式={,,…,f}的星型鄰居T中除去的剩余模糊特征的外部效用(f)與內(nèi)部效用(f,T)乘積的最大值，記為：

例如在表3 的星型鄰居中，除去co-location 模式={,,}中的特征外，的剩余最大效用值為()=max{()×(,),()×(,)}=max{0.3,1}=1。

（模式的局部擴(kuò)展模糊平均效用）對于任意一個co-location 模式={,,…,f}的局部擴(kuò)展模糊平均效用表示為(),定義為在包含的所有星型鄰居中，在星型鄰居T中的效用值與T的剩余最大模糊效用值之和與模式的長度加1 的比值，即：

一個模式的局部擴(kuò)展模糊平均效用值不小于其超集的局部擴(kuò)展模糊平均效用值。

設(shè)模式為一個階的局部擴(kuò)展模糊平均效用模式，模式′為模式的任意一個+1 階超集。因為為′的一個超集，所有包含′的星型鄰居一定包含，所以包含′的星型鄰居是包含的星型鄰居的子集，那么有：

例如，在表3 中，({,,})=4.5，({,})=28.2/3，({,})=18.8/3，模 式{,}、{,}的局部擴(kuò)展模糊平均效用值不小于其超集的局部擴(kuò)展模糊平均效用值。

模式的模糊平均效用值不大于其子集的局部擴(kuò)展模糊平均效用值。

設(shè)模式為一個階的局部擴(kuò)展模糊平均效用模式，模式′為模式的任意一個-1 階子集。因為′為的一個子集，所有包含的星型鄰居一定包含′，所以有：

例如，在表3 中，({,})=28.2/3，({,})=26/3,({,})=18.8/3,({,,})=5.2,({,,})＜({,}),({,,})＜({,}),({,,})＜({,})，可得模式{,,}的模糊平均效用值不大于其子集的局部擴(kuò)展模糊平均效用值。

根據(jù)引理4 和引理5 可得：如果模式的局部擴(kuò)展模糊平均效用值小于top-中的最小模糊平均效用值，那么其超集不是top-模糊平均效用colocation 模式。

對于任意co-location模式，有() ≥()成立。

對于任意的co-location 模式有：

例如，在表3中，co-location 模式={,,},()=4.5,()=7.1,()＜()。

根據(jù)定理2，可以設(shè)計算法2：基于局部擴(kuò)展模糊平均效用剪枝的優(yōu)化算法。

優(yōu)化算法

第1、2 步和算法1 一樣，這里將不再贅述。第3步是一個由低階到高階反復(fù)迭代的過程，直到不能生成候選模式為止：首先，3.1 步由-1 階的候選模式生成階的候選模式。然后，在3.2 步中，階的擴(kuò)展模式M等于階的候選模式C。在3.3 步中計算候選模式的()并和進(jìn)行比較。3.4 步通過表實例和外部效用表計算M中每個模式的模糊平均效用值()，如果()≥，和原中各模式的模糊平均效用值進(jìn)行比較，模糊平均效用值最大的前個模式替換原中的模式。3.5 步階數(shù)自增，算法跳轉(zhuǎn)到第3 步執(zhí)行while 循環(huán)條件判斷，若此時-1 階的候選模式集不為空，則繼續(xù)執(zhí)行while 循環(huán)體內(nèi)部的子句；反之，若C為空，此時不能夠生成階的候選模式，則會跳轉(zhuǎn)到第4 步，返回top-模糊平均效用co-location 模式集，算法結(jié)束。

由于本文所提出的兩個算法只是在生成候選模式數(shù)量方面有區(qū)別，根據(jù)定理3 對于任意co-location模式，有()≥()成立，可得算法2 能剪去更多的候選模式，在top-模糊平均效用co-location模式挖掘中，查找模式的表實例為最耗時的部分。在算法2 中，通過減少更多的候選模式的數(shù)量，進(jìn)一步減少查找表實例的過程。因此算法2 的效率將高于算法1。

4 實驗結(jié)果與分析

本文所提出的模糊特征的top-平均效用colocation 模式挖掘的基本算法和進(jìn)一步基于局部擴(kuò)展模糊效用剪枝算法（AFU）以及用于比較的算法FHUCO（這是文獻(xiàn)[18]中提出的方法，本文對其進(jìn)行了改進(jìn)，考慮了模式長度對效用的影響）都采用Java編寫，實驗環(huán)境為Win10 系統(tǒng)，Core i7 CPU 和16 GB內(nèi)存的計算機(jī)。

4.1 真實數(shù)據(jù)集上的實驗與分析

實驗中用了兩類數(shù)據(jù)集，即合成數(shù)據(jù)集和真實的“云南貢山某區(qū)域植被”數(shù)據(jù)集1 和“上海市POI”數(shù)據(jù)集2。數(shù)據(jù)集1 的數(shù)據(jù)分布如圖3（a）所示，該數(shù)據(jù)集包含箭竹、冷杉、榿木、鐵杉、云南松等25 個樹種，共有13 349 個植株。數(shù)據(jù)集2 的數(shù)據(jù)分布如圖3（b）所示，該數(shù)據(jù)集包含23 個空間特征和14 446 個空間實例。在以下實驗中，表示模糊特征數(shù)，表示鄰近距離閾值，表示實例總數(shù)量。

圖3 真實數(shù)據(jù)集數(shù)據(jù)分布Fig.3 Distribution of real dataset

4.2 真實數(shù)據(jù)集上的實驗與分析

在本小節(jié)實驗中，數(shù)據(jù)集1 中的范圍從2 200 m到2 600 m，數(shù)據(jù)集2 中的范圍從250 m 到300 m，值為40 和80，在實驗中也嘗試取不同的距離閾值，但如果距離閾值設(shè)置小于這個范圍，由于數(shù)據(jù)集本身的分布情況，挖掘不到鄰近的實例對或者挖掘到的鄰近實例對很少，同樣如果距離閾值設(shè)置大于這個范圍，所有的實例對幾乎都滿足鄰近關(guān)系，導(dǎo)致結(jié)果沒有可比性。在實際生活中值的取值是根據(jù)用戶的需要進(jìn)行取值的，本文中值的選取可以隨機(jī)選取，得到的實驗結(jié)論都是一樣的。FHUCO 中的最小效用閾值對應(yīng)top-模糊平均的最小效用值。

在圖4 中，圖4（a）為真實數(shù)據(jù)集1，圖4（b）為真實數(shù)據(jù)集2。兩個圖都由于AFU 算法基于局部擴(kuò)展模糊平均效用值進(jìn)行了進(jìn)一步的剪枝，提前過濾掉了更多不可能成為top-模糊平均效用模式，使得候選模式的數(shù)量小于基本算法。FHUCO 算法以top-中的最小模糊平均效用值作為效用閾值來挖掘模式，由于FHUCO 算法本身剪枝策略的效用上限值過于寬松，導(dǎo)致FHUCO 中的候選模式始終比提出的AFU 和基本算法多。在圖5（a）數(shù)據(jù)集1 和圖5（b）數(shù)據(jù)集2 中由于AFU 算法可以提前減少更多的低效用模式，其運(yùn)行時間低于基本算法和FHUCO 的運(yùn)行時間，F(xiàn)HUCO 所需運(yùn)行時間最長。值變大，候選模式的數(shù)量增加，運(yùn)行時間也隨之增加，top-中的模糊平均效用閾值也降低，使得三個算法top-80 的整體候選模式數(shù)多于top-40 的，運(yùn)行時間整體也增多。隨著值的增加，鄰近區(qū)域的面積也隨著增大，鄰近區(qū)域中實例數(shù)相應(yīng)增多，鄰近實例對增多，導(dǎo)致其中團(tuán)的數(shù)量也急劇增多，從而增加了表實例的計算。因此隨著距離閾值的增加，三種算法的候選模式和運(yùn)行時間都隨之增加。

圖4 真實數(shù)據(jù)中距離閾值d 對候選模式數(shù)量的影響Fig.4 Effect of d on the number of candidate patterns in real data

圖5 真實數(shù)據(jù)中距離閾值d 對運(yùn)行時間的影響Fig.5 Effect of d on running time in real data

在本小節(jié)實驗中，數(shù)據(jù)集1 中=2 500 m，數(shù)據(jù)集2 中=250 m，值為40 和80，F(xiàn)HUCO 中的最小效用閾值對應(yīng)top-模糊平均效用co-location 模式的最小效用值。

從圖6（a）數(shù)據(jù)集1 和圖6（b）數(shù)據(jù)集2 中各階數(shù)下候選模式數(shù)的變化可以看出，AFU 算法在相同階數(shù)下能過濾掉更多的候選模式，在數(shù)據(jù)集1 中AFU和基本算法超過5 階就不再生成候選模式，在數(shù)據(jù)集2 中AFU 超過6 階就不再生成候選模式，提前終止了不必要的計算。

圖6 真實數(shù)據(jù)中模式階數(shù)對候選模式數(shù)量的影響Fig.6 Effect of pattern size on the number of candidate patterns in real data

4.3 合成數(shù)據(jù)集上的實驗與分析

在本節(jié)實驗中，F(xiàn)HUCO 中的最小效用閾值對應(yīng)top-模糊平均效用co-location 模式的最小效用值。

設(shè)置=15，=25，從30 000 增大到80 000。

從圖7中可以看到，隨著實例數(shù)目的增加，三種算法的候選模式的數(shù)量都隨之增加，這是因為隨著實例數(shù)目的增加，數(shù)據(jù)集變得越來越密集。當(dāng)≥60 000時，F(xiàn)HUCO 算法候選模式數(shù)增加速度較快；當(dāng)=60 000 時，F(xiàn)HUCO 生成的候選模式數(shù)是基本算法的12 倍，是AFU 算法的43 倍；當(dāng)=70 000 時，F(xiàn)HUCO生成的候選模式數(shù)是基本算法的12 倍，是AFU 算法的58 倍，其中AFU 產(chǎn)生的候選模式數(shù)最少，剪枝效果最明顯，這是因為AFU 算法基于局部擴(kuò)展模糊平均效用值進(jìn)行了進(jìn)一步的剪枝，提前過濾掉了更多不可能成為top-模糊平均效用模式，使得候選模式的數(shù)量小于基本算法。FHUCO 算法以top-中的最小模糊平均效用值作為效用閾值來挖掘模式，由于FHUCO 算法本身剪枝策略的效用上限值過于寬松，導(dǎo)致FHUCO 中的候選模式始終比本文提出的AFU和基本算法多。在圖8 中，由于實例數(shù)目的增加會導(dǎo)致實例間距離計算、連接操作的增加，三種算法的候選模式和運(yùn)行時間都隨著實例數(shù)目的增加而增加。當(dāng)實例數(shù)目每增加10 000 時，F(xiàn)HUCO 算法的運(yùn)行時間是前者的3倍左右，基本算法的運(yùn)行時間是前者的2倍左右。在AFU算法中，運(yùn)行時間依次增加，是前者的1.6 倍左右，且本文提出的兩個算法的運(yùn)行時間始終少于FHUCO，AFU 所需的運(yùn)行時間最少，效果最優(yōu)。

圖7 合成數(shù)據(jù)中實例數(shù)量對候選模式數(shù)量的影響Fig.7 Effect of the number of instances on the number of candidate patterns in synthetic data

圖8 合成數(shù)據(jù)中實例數(shù)量對運(yùn)行時間的影響Fig.8 Effect of the number of instances on running time in synthetic data

設(shè) 置=10，=80 000，=10，從5 到25。在圖9 中，隨著特征個數(shù)的增加，三種算法的候選模式個數(shù)都在增加。由于AFU 算法的優(yōu)勢，AFU 的候選模式個數(shù)增長速度最慢。在圖10 中，隨著特征數(shù)的增加，三個算法的整體運(yùn)行時間都在增加，但由于FHUCO 能過濾掉的候選模式數(shù)較少，其整體運(yùn)行速度比基本算法和AFU 都慢。

圖9 合成數(shù)據(jù)中特征數(shù)量對候選模式數(shù)量的影響Fig.9 Effect of the number of features on the number of candidate patterns in synthetic data

圖10 合成數(shù)據(jù)中特征數(shù)量對運(yùn)行時間的影響Fig.10 Effect of the number of features on running time in synthetic data

5 結(jié)束語

本文將top-高平均模糊效用引入到co-location模式挖掘框架中。針對模糊平均效用值不滿足“向下閉合”的特性，提出了擴(kuò)展模糊平均效用的概念，并基于此概念提出了一種模式挖掘的基本算法。為了提高基本算法的效率，又提出了一種局部擴(kuò)展模糊效用剪枝方法。大量實驗結(jié)果表明，改進(jìn)后的算法能夠有效、準(zhǔn)確地挖掘出用戶感興趣的模式。下一步將繼續(xù)優(yōu)化算法，改善其在稠密數(shù)據(jù)集上的性能。同時考慮基于本體的空間高平均效用co-location模式挖掘問題。