高平均效用co-location 模式挖掘的一種有效算法

曾 新，張曉玲，李曉偉

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

空間co-location 模式表示布爾空間特征的子集，它們的實例在地理位置上是鄰近的。例如，生態(tài)學(xué)家對生態(tài)數(shù)據(jù)集進(jìn)行分析時發(fā)現(xiàn)：尼羅鱷所在附近區(qū)域內(nèi)經(jīng)常有埃及鵠鳥〔1〕。

盡管Huang 等〔1〕提出了空間co-location 模式頻繁度的衡量標(biāo)準(zhǔn)，并在確定數(shù)據(jù)集上構(gòu)建了基于全連接的模式挖掘算法full-based，但是full-based算法在計算模式表實例過程中產(chǎn)生的連接操作耗費(fèi)了大量計算時間。為了解決計算瓶頸問題，基于部分連接的partial-join 算法〔2〕、基于無連接的join-less 算法〔3〕和基于CPI-tree 結(jié)構(gòu)的新join-less算法〔4〕相繼被提出。

除基于確定數(shù)據(jù)集的數(shù)據(jù)挖掘算法之外，Wang等〔5〕提出在空間不確定數(shù)據(jù)集上高效挖掘top-k 概率頻繁co-location 模式；Yoo 等〔6〕提出一種在連續(xù)變化的空間動態(tài)數(shù)據(jù)庫中發(fā)現(xiàn)co-location 模式的方法，而Lu 等〔7〕進(jìn)一步基于挖掘出的頻繁colocation 模式〔8〕挖掘強(qiáng)共生和競爭模式；Huang 等〔9〕將實例數(shù)明顯少于其他特征實例數(shù)的特征定義為稀有特征，進(jìn)而提出含稀有特征的空間co-location模式挖掘算法，而馮嶺等〔10〕在此基礎(chǔ)上加入特征權(quán)重，提出新的含稀有特征的空間co-location 模式挖掘算法。

然而，空間co-location 模式主要考慮模式內(nèi)不同特征實例頻繁出現(xiàn)的頻率，沒有考慮特征存在的其他因素，例如，單位價值（或效用）等，因此，模式挖掘過程中忽略了即使效用值高但出現(xiàn)頻率較低的模式。為了解決這一問題，楊世晟等〔11〕將特征的效用值引入空間co-location 模式挖掘中，定義了模式效用、模式效用率等概念，構(gòu)建了空間高效用colocation 模式挖掘算法，并以擴(kuò)展模式的反單調(diào)性構(gòu)建了完全剪枝算法，提升了算法的挖掘效率?，F(xiàn)實世界中的數(shù)據(jù)是不斷更新的，Wang 等〔12〕基于動態(tài)數(shù)據(jù)庫提出構(gòu)建動態(tài)挖掘空間高效用co-location模式的有效方法；同一特征的不同實例可能具有不同的效用值，Wang 等〔13〕將實例效用值引入空間高效用co-location 模式挖掘，同時考慮模式中每個特征的內(nèi)效用和外效用，以得到特征在模式中的全局影響，并提出了相應(yīng)的挖掘算法和剪枝策略。盡管空間高效用co-location 模式挖掘方法不斷被報道，卻沒有統(tǒng)一的高效用co-location 模式衡量標(biāo)準(zhǔn)。因此，王曉璇等〔14〕提出基于特征效用參與率的空間高效用co-location 模式挖掘方法；Zeng 等〔15〕提出基于特征實例參與權(quán)重的空間高效用co-location 模式挖掘方法。

空間高效用co-location 模式挖掘以模式的效用作為主要的衡量標(biāo)準(zhǔn)，沒有考慮模式長度對模式效用的影響，因此，采用相同的模式最小效用閾值來挖掘高效用co-location 模式存在不足。盡管從事務(wù)數(shù)據(jù)庫中挖掘高平均效用項集的有效算法很多〔16-23〕，但是從空間數(shù)據(jù)集中挖掘高平均效用colocation 模式的研究還未見報道。因此，探索模式長度對高效用co-location 模式挖掘的影響是必要的。

1 空間co-location 模式

布爾空間特征集合F=｛f1，f2，f3，…，fn｝和特征的實例集S=｛o1，o2，o3，…，on｝，每個實例包含所屬特征類型、實例編號和位置坐標(biāo)等三部分信息，部分實例的空間分布情況見圖1。任意兩個實例oi和oj間的距離（例如歐式距離等）小于等于用戶或領(lǐng)域?qū)＜以O(shè)置的距離閾值d，則它們滿足鄰近關(guān)系R，即R（oi，oj）≤d，則在圖1 中用實線將它們連接。

圖1 部分實例的空間分布示例

圖1 中，如果co-location 模式c=｛A，B，C｝，則其模式長度為3，它包含模式c'＝｛A，B｝的所有特征，是c'的一個超集。實例集合｛A.2，B.4，C.2｝中的任意兩個實例滿足鄰近關(guān)系R 且包含模式c 的所有特征的一個實例，但是其子集卻不包含c 的所有特征的一個實例，所以，集合｛A.2，B.4，C.2｝是模式c 的一個行實例，用row_instance（c）表示，模式c的所有行實例的集合為其表實例，用table_instance（c）表示。例如，在圖1 中，table_instance（c）=｛｛A.2，B.4，C.2｝，｛A.3，B.3，C.1｝｝。

為了有效評價空間co-location 模式的頻繁度，Huang 等〔1〕提出特征參與率PR（c，fi）和模式參與度PI（c）兩個評價指標(biāo)，如公式（1）、（2）所示：

其中，π 是去除重復(fù)的關(guān)系投影操作。

例如，模式c=｛A，B，C｝，從圖1 的實例分布中可以得出table_instance（c）=｛｛A.2，B.4，C.2｝，｛A.3，B.3，C.1｝｝，而A，B，C 分別有4，5，3 個實例，所以由公式（1）有，進(jìn)一步根據(jù)公式（2）得到c的參與度PI（c）=min（0.5，0.4，0.67）=0.4。如果最小參與度閾值min_prev 為0.4，由于PI（c）≥0.4，所以c 為頻繁co-location 模式。

為了提高頻繁co-location 模式的挖掘效率，Huang 等〔1〕證明參與率和參與度滿足反單調(diào)性，即參與率和參與度會隨著co-location 模式長度的增大單調(diào)遞減。如果一個co-location 模式是非頻繁的，則它的所有超集也是非頻繁的。

2 空間高平均效用co-location 模式

以下描述空間高平均效用co-location 模式的相關(guān)基本概念和判別高平均效用co-location 模式的準(zhǔn)則。

定義1 實例外效用 實例外效用用來描述特征fi不同實例的單位價值，fi的第j 個實例fij的單位價值表示為ieu（fij）。例如，圖1 中A，B，C 特征的實例外效用，見表1。

表1 特征A，B，C 的實例外效用

定義2 實例內(nèi)效用 假定fi∈c，那么fij的內(nèi)效用為fij在模式c 的表實例中出現(xiàn)的次數(shù)，表示為iiu（c，fij）。例如，在圖1 中，如果模式c=｛A，B，C｝，它的表實例table_instance（c）=｛｛A.2，B.4，C.2｝，｛A.3，B.3，C.1｝｝，那么iiu（c，A.2）=1，iiu（c，A.3）=1，同理，iiu（c，B.4）=1，iiu（c，C.1）=1。

定義3 特征參與效用 假定fi∈c，fi有k 個實現(xiàn)出現(xiàn)在模式c 的表實例中，那么模式c 中fi的特征參與效用等于其每個參與實例的ieu（fij）與iiu（c，fij）的積之和，即fij）。例如，在圖1 中，若模式c=｛A，B，C｝，則fpu（c，A）=ieu（A.2）× iiu（c，A.2）+ieu（A.3）×iiu（c，A.3）=8。

定義4 模式效用 如果模式c=｛f1，f2，…，fk｝，則模式c 的模式效用pu（c）等于其所有特征的特征參與效用之和，即例如，對于模式c=｛A，B，C｝而言，pu（c）= fpu（c，A）+fpu（c，B）+fpu（c，C）=8+10+20=38。

定義5 co-location 模式的平均效用 如果模式c=｛f1，f2，…，fk｝，它的長度和模式效用分別為k和pu（c），那么模式c 的平均效用au（c）等于pu（c）與k 的比值，即例如，模式c=｛A，B，C｝，其模式長度為3，模式效用為38，則c 的平均效用

假設(shè)用戶或領(lǐng)域?qū)＜以O(shè)定的最小平均效用閾值為min_au，如果一個co-location 模式的平均效用大于或等于min_au，那么為高平均效用co-location模式，否則為低平均效用co-location 模式。例如，設(shè)定min_au=10，對于c=｛A，B，C｝，因為au（c）=12.67＞10，所以c 為高平均效用co-location 模式。

3 算法

首先，構(gòu)建了高平均效用co-location 模式挖掘的基本算法；其次，為了提高算法的效率，提出了兩個剪枝策略，并進(jìn)一步構(gòu)建高平均效用co-location模式挖掘的剪枝算法。

3.1 基本算法首先，采用組合的方法產(chǎn)生所有候選二階co-location 模式，并基于k（k≥2）階colocation 模式，以類Apriori 算法〔24〕產(chǎn)生k+1 階colocation 模式。其次，根據(jù)co-location 模式和高平均效用co-location 模式的相關(guān)定義，計算出所有候選模式的表實例和平均效用。最后，基于用戶或領(lǐng)域?qū)＜抑付ǖ淖钚∑骄в瞄撝?，發(fā)現(xiàn)高平均效用co-location 模式的完全集。高平均效用co-location模式挖掘基本算法（HAUCP_BA）的詳細(xì)描述如下：

算法1高平均效用co-location 模式挖掘基本算法HAUCP_BA

輸入：

a.布爾空間特征集合F=｛f1，f2，…，fk｝；

b.空間實例及其外部權(quán)重集合S=｛（o1，ieu（o1）），（o2，ieu（o2）），…，（on，ieu（on））｝；

c.最小距離閾值d；

d.最小平均效用閾值min_au。

輸出：高平均效用co-location 模式集合haucp。

變量：模式長度l，模式長度為l 的候選colocation 模式集合Cl，Cl中co-location 模式的表實例集合Tl，模式長度為l 的高平均效用co-location 模式集合。

步驟：

1.l=1；Cl=F；Hl=?；

2.Tl=generate_table_instance（Cl，S）；

3.while Tl≠?

4.do

5.Hl=select_high_average-utility_co-location_pattern（Cl，S，l，Tl，min_au）；

6.haucp=haucp∪Hl；

7.Hl=?；

8.l=l+1；

9.Cl=generate_candidate_co-location_pattern（Cl-1）；

10.Tl=generate_table_instance（Cl，Tl-1，d）；

11.done

12.return haucp

盡管HAUCP_BA 能夠有效從空間數(shù)據(jù)集中發(fā)現(xiàn)高平均效用co-location 模式的完全集，但是大量連接操作和巨大搜索空間所產(chǎn)生的計算成本讓用戶難以承受?？臻gco-location 模式挖掘滿足反單調(diào)性〔1〕，可以有效減少連接操作和搜索空間，然而，HAUCP_BA 算法并不滿足反單調(diào)性。例如，在圖1和表1 當(dāng)中，如果模式c=｛A，B｝?c'=｛A，B，C｝，則c和c'的表實例分別為table_instance（c）=｛｛A.1，B.1｝，｛A.2，B.4｝，｛A.3，B.3｝｝、table_instance（c'）=｛｛A.2，B.4，C.2｝，｛A.3，B.3，C.1｝｝，根據(jù)空間高效用colocation 模式的相關(guān)定義可計算出au（c）=（11+15）/2=13、au（c'）=（8+10+25）/3= 14.3。假定min_au=14，則有au（c）min_au，所以，HAUCP_BA 算法不滿足反單調(diào)性，對空間高平均效用co-location 模式挖掘算法的效率提出了巨大挑戰(zhàn)。

3.2 剪枝算法為了減少不同特征的實例之間的連接操作和搜索空間的巨大耗費(fèi)，提出了兩種有效的剪枝策略，并進(jìn)一步構(gòu)建了高效的剪枝算法。

剪枝策略1假設(shè)兩個k（k≥2）階模式c'和c"的前k-1 個特征是相同的，經(jīng)過連接后產(chǎn)生（k+1）階候選模式ck+1。如果兩個模式的平均效用滿足au（c'）＜min_au，au（c"）＜min_au 且模式c'或c"的前k-1 個特征的平均效用大于或等于min_au，那么候選模式ck+1不是一個高平均效用co-location 模式。

證明：假定兩個k（k≥2）模式c' 和c"分別為c'＝｛f1，f2，…，fk-1，fk'｝，c"＝｛f1，f2，…，fk-1，fk"｝，其中fk'≠fk"，ck+1＝c' c"＝｛f1，f2，…，fk-1，fk'，fk"｝。由于au（c'）＜min_au，au（c"）＜min_au，則可以推導(dǎo)出pu（c'）＜k×min_au，pu（c"）＜k×min_au，兩邊相加則有pu（c'）+pu（c"）＜2×k×min_au，可進(jìn)一步得出：2×pu（ck-1in c'）+ fpu（c'，fk'）+ fpu（c"，fk"）＜2×k×min_au，因為au（ck－1in c'）≥min_au，所以pu（ck－1in c'）+fpu（c'，fk'）+ fpu（c"，fk"）＜2×k×min_au－（k－1）×min_au=（k+1）×min_au。根據(jù)空間co-location 模式挖掘算法滿足反單調(diào)性，可以得到pu（ck－1in ck＋1）≤pu（ck－1in c'），fpu（ck＋1，fk'）≤fpu（c'，fk'）和fpu（ck＋1，f"）≤fpu（c"，fk"）。因此pu（ck－1in ck＋1）+fpu（ck＋1，fk"）≤（k+1）×min_au 得出剪枝策略1 是成立的。

剪枝策略2如果一個k 階模式c 的所有k-1階子模式的平均效用值均小于min_au，那么c 為非高平均效用co-location 模式。

證明：假設(shè)c＝｛f1，f2，…，fk｝，則模式c 有k 個k-1 階子模式，即c1k-1＝｛f1，f2，…，fk-1｝，c2k-1＝｛f1，f3，…，fk｝等等。因為所有的k-1 階子模式的平均效用值小于min_au，所以（c2k-1）＜min_au 等等，將這k 個不等式進(jìn)行相加可以得到由空間colocation 模式挖掘算法滿足反單調(diào)性可知，特征fi（fi∈c 且fi∈ck-1）在模式c 中的任意一個實例的外效用不大于其在子模式ck-1中的同一實例的外效用，由此可以得到pu（c）＜k×min_au，即au（c）＜min_au，所以c 不是一個高平均效用co-location 模式，剪枝策略2 成立。

接下來，基于剪枝策略1 和剪枝策略2 構(gòu)建了高效的剪枝算法HAUCP_IA，具體描述如下：

算法2高平均效用co-location 模式挖掘優(yōu)化算法HAUCP_IA

輸入：

a.布爾空間特征集合F=｛f1，f2，…，fk｝；

b.空間實例及其外部權(quán)重集合S=｛（o1，ieu（o1）），（o2，ieu（o2）），…，（on，ieu（on））｝；

c.最小距離閾值d；

d.最小平均效用閾值min_au。

輸出：

高平均效用co-location 模式集合haucp。

變量：模式長度l；長度為l 的候選co-location模式集合Cl；利用剪枝策略1 進(jìn)行剪枝后的長度為l 的候選co-location 模式集合Cl'；利用剪枝策略2進(jìn)行剪枝后的長度為l 的候選co-location 模式集合Cl"；Cl中co-location 模式的表實例的集合Tl；長度為l 的高平均效用co-location 模式集合Hl；長度為l 的非高平均效用co-location 模式集合Ll。

步驟：

1.l=1；Cl=F；Hl=?；temp=?；Ll=?；Cl'＝?；Cl"＝?；

2.Tl=generate_table_instance（Cl，S，d）；

3.while l≤k

4.do

5.if l<2 then

6.Hl=select_high_average-utility_co-location_pattern（Cl，S，Tl，min_au）；

7.Ll=Cl-Hl；

8.else

9.Cl'=generate_pruned_co-location_pattern（Cl，l≥3，Ll-1）；

10.Cl" =generate_pruned_co -location_pattern（Cl-Cl'，l≥2，Ll-1）；

11.temp=Cl；

12.Cl=Cl-Cl'-Cl"；

13.Tl=generate_table_instance（Cl，Tl-1，d）；

14.Hl=select_high_average-utility_co-location_pattern（Cl，S，Tl，min_au）；

15.Cl=temp；

16.Ll=Cl-Hl；

17.haucp=haucp∪Hl；

18.l=l+1；

19.Cl=generate_candidate_co-location_pattern（Cl-1）；

20.Hl=?；Ll=?；Cl'＝?；Cl"＝?；

21.done

22.return haucp

首先，計算了一階模式的表實例、高平均效用co-location 模式和非高平均效用co-location 模式。其次，對于k（k≥2）階候選模式ck，進(jìn)一步基于剪枝策略1 和剪枝策略2 排除了所有的非高平均效用co-location 模式，并計算保留的候選模式的表實例，得到所有k 階高平均效用co-location 模式。最后，由于高平均效用co-location 模式挖掘算法不滿足反單調(diào)性，所以，將所有k 階候選模式連接生成k+1 階候選模式，繼續(xù)判斷模式是否為高平均效用co-location模式，并返回所有高平均效用co-location 模式。

4 實驗與結(jié)果

以下呈現(xiàn)實驗所需要的真實數(shù)據(jù)集、合成數(shù)據(jù)集和相關(guān)的默認(rèn)參數(shù)，并在真實數(shù)據(jù)集和合成數(shù)據(jù)集上，對所提出的基本算法HAUCP_BA 和剪枝算法HAUCP_IA 的有效性、可擴(kuò)展性進(jìn)行大量實驗。

4.1 實驗環(huán)境和數(shù)據(jù)集本文所有實驗都是基于Intel Core i5-8500 CPU 3.00 GHz、8 GB 內(nèi)存的硬件平臺和Windows 10 操作系統(tǒng)、Python 3.7 的軟件平臺進(jìn)行的。

真實數(shù)據(jù)集來源于重慶POI（Point of Interest）數(shù)據(jù)集，共有18 個特征和141 785 個實例，分別表示賓館、學(xué)校、醫(yī)院、購物商場等事物。實驗過程中運(yùn)行的樣本是通過非重復(fù)抽樣從真實數(shù)據(jù)集中獲取的，具體樣本大小和參數(shù)見表2。

表2 基于真實數(shù)據(jù)集的樣本相關(guān)參數(shù)

合成數(shù)據(jù)集通過隨機(jī)的方式產(chǎn)生，共包含18個特征和138 422 個實例，每個實例的坐標(biāo)范圍為［1，10 000］，實驗過程中運(yùn)行的樣本是通過非重復(fù)抽樣從合成數(shù)據(jù)集中獲取的，具體樣本大小和參數(shù)見表3。

表3 基于合成數(shù)據(jù)集的樣本相關(guān)參數(shù)

4.2 算法性能評估首先，在距離閾值和最小高平均效用閾值采用默認(rèn)值的情況下，在真實樣本和合成樣本下測試了基本算法HAUCP_BA 和剪枝算法HAUCP_IA 的運(yùn)行效率，并對兩個算法的運(yùn)行效率進(jìn)行對比，見圖2。

圖2 不同數(shù)據(jù)集下算法的運(yùn)行效率

隨著樣本數(shù)量的增多，無論是基本算法HAUCP_BA，還是剪枝算法HAUCP_IA 中實例連接的數(shù)目也會不斷增多，算法的運(yùn)行時間會呈上升趨勢。由于剪枝策略1 和剪枝策略2 主要是針對效用進(jìn)行剪枝，因此，剪枝策略在樣本數(shù)量變化中沒有起到好的效果。

其次，在樣本數(shù)量和最小高平均效用閾值采用默認(rèn)值的情況下，基于真實樣本和合成樣本測試了HAUCP_BA 和HAUCP_IA 在不同距離閾值下的運(yùn)行效率，并對兩個算法的運(yùn)行效率進(jìn)行了對比，見圖3。

圖3 不同距離閾值下算法的運(yùn)行效率

距離閾值的增大，會導(dǎo)致不同特征的更多實例處于同一鄰近區(qū)域內(nèi)，模式表實例的個數(shù)也會隨之增多，連接操作也會隨之增多，算法運(yùn)行時間會呈現(xiàn)上升趨勢，由于最小高平均效用閾值仍采用默認(rèn)值，剪枝效果仍然不明顯。

最后，在樣本數(shù)量和距離閾值采用默認(rèn)值的情況下，基于真實樣本和合成樣本測試了HAUCP_BA和HAUCP_IA 在不同的最小高平均效用閾值下的運(yùn)行效率，并對兩個算法的運(yùn)行效率進(jìn)行了對比，見圖4。

圖4 最小高平均效用閾值對算法運(yùn)行效率的影響

由于高平均效用算法不滿足反單調(diào)性，因此，需要考慮計算每個候選模式是否為高效用colocation 模式，所以整體的連接操作變化不大，算法的運(yùn)行時間波動也不大，然而，采用剪枝策略后，減少了部分模式的效用值計算，剪枝算法的效率要高于基本算法的效率。

4.3 實驗結(jié)果與分析數(shù)據(jù)集或距離閾值的不斷增大導(dǎo)致不同特征實例連接的數(shù)目隨之增大，根據(jù)特征實例內(nèi)部效用的定義可知，實例的內(nèi)部效用也會不斷增大。然而，最小高平均效用閾值是由用戶或領(lǐng)域?qū)＜以O(shè)定的，因此，在設(shè)定的最小高平均效用閾值下，高平均效用模式的數(shù)目會不斷增加，但是，隨著最小高平均效用閾值的增大，符合高平均效用co-location 模式的數(shù)目也會不斷減少。同時，為了進(jìn)一步證明模式的長度越大，模式的總效用值越大，其成為高效用模式的概率也越大。在相關(guān)參數(shù)采用默認(rèn)值的情況下，基于真實樣本和合成樣本，將高平均效用co-location 模式挖掘算法（簡稱為HAUCP 算法）與不考慮模式長度的高效用colocation 模式挖掘算法（簡稱為HUCPM 算法）的挖掘結(jié)果進(jìn)行了對比，見圖5~6。

圖5 真實數(shù)據(jù)集下HAUCP 和HUCPM 算法挖掘結(jié)果對比

圖6 合成數(shù)據(jù)集下HAUCP 和HUCPM 算法挖掘結(jié)果對比

從圖5~6 中可以得出：模式的長度對模式的效用值有一定的影響，因此，在考慮模式長度的情況下，挖掘出的高平均效用co-location 模式更符合實際，對決策支持更有價值。

5 結(jié)論

本文基于空間數(shù)據(jù)庫，主要考慮模式長度對高效用co-location 模式的影響，提出高平均效用colocation 模式挖掘的相關(guān)定義、基本算法和剪枝策略。最終，在真實數(shù)據(jù)集和合成數(shù)據(jù)集上進(jìn)行充分實驗，實驗結(jié)果表明：模式長度對高效用co-location模式有一定影響，高平均效用co-location 模式挖掘比高效用co-location 模式挖掘更符合實際需求。由于高平均效用模式挖掘算法不滿足反單調(diào)性，計算所有模式的表實例所帶來的時間耗費(fèi)過長，雖然本文提出了兩個針對性的剪枝策略，但是，剪枝效果并不明顯，因此，在未來的工作中，我們將繼續(xù)研究高平均效用co-location 模式挖掘的剪枝算法，進(jìn)一步提高算法的挖掘效率。