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

曾 新，張曉玲，李曉偉

（大理大學數學與計算機學院，云南大理 671003）

空間co-location 模式表示布爾空間特征的子集，它們的實例在地理位置上是鄰近的。例如，生態學家對生態數據集進行分析時發現：尼羅鱷所在附近區域內經常有埃及鵠鳥〔1〕。

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

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

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

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

1 空間co-location 模式

布爾空間特征集合F=｛f1，f2，f3，…，fn｝和特征的實例集S=｛o1，o2，o3，…，on｝，每個實例包含所屬特征類型、實例編號和位置坐標等三部分信息，部分實例的空間分布情況見圖1。任意兩個實例oi和oj間的距離（例如歐式距離等）小于等于用戶或領域專家設置的距離閾值d，則它們滿足鄰近關系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｝中的任意兩個實例滿足鄰近關系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）兩個評價指標，如公式（1）、（2）所示：

其中，π 是去除重復的關系投影操作。

例如，模式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）有，進一步根據公式（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〕證明參與率和參與度滿足反單調性，即參與率和參與度會隨著co-location 模式長度的增大單調遞減。如果一個co-location 模式是非頻繁的，則它的所有超集也是非頻繁的。

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

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

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

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

定義2 實例內效用 假定fi∈c，那么fij的內效用為fij在模式c 的表實例中出現的次數，表示為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 個實現出現在模式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 的平均效用

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

3 算法

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

3.1 基本算法首先，采用組合的方法產生所有候選二階co-location 模式，并基于k（k≥2）階colocation 模式，以類Apriori 算法〔24〕產生k+1 階colocation 模式。其次，根據co-location 模式和高平均效用co-location 模式的相關定義，計算出所有候選模式的表實例和平均效用。最后，基于用戶或領域專家指定的最小平均效用閾值，發現高平均效用co-location 模式的完全集。高平均效用co-location模式挖掘基本算法（HAUCP_BA）的詳細描述如下：

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

輸入：

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

b.空間實例及其外部權重集合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 能夠有效從空間數據集中發現高平均效用co-location 模式的完全集，但是大量連接操作和巨大搜索空間所產生的計算成本讓用戶難以承受。空間co-location 模式挖掘滿足反單調性〔1〕，可以有效減少連接操作和搜索空間，然而，HAUCP_BA 算法并不滿足反單調性。例如，在圖1和表1 當中，如果模式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｝｝，根據空間高效用colocation 模式的相關定義可計算出au（c）=（11+15）/2=13、au（c'）=（8+10+25）/3= 14.3。假定min_au=14，則有au（c）min_au，所以，HAUCP_BA 算法不滿足反單調性，對空間高平均效用co-location 模式挖掘算法的效率提出了巨大挑戰。

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

剪枝策略1假設兩個k（k≥2）階模式c'和c"的前k-1 個特征是相同的，經過連接后產生（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，則可以推導出pu（c'）＜k×min_au，pu（c"）＜k×min_au，兩邊相加則有pu（c'）+pu（c"）＜2×k×min_au，可進一步得出：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。根據空間co-location 模式挖掘算法滿足反單調性，可以得到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 模式。

證明：假設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 個不等式進行相加可以得到由空間colocation 模式挖掘算法滿足反單調性可知，特征fi（fi∈c 且fi∈ck-1）在模式c 中的任意一個實例的外效用不大于其在子模式ck-1中的同一實例的外效用，由此可以得到pu（c）＜k×min_au，即au（c）＜min_au，所以c 不是一個高平均效用co-location 模式，剪枝策略2 成立。

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

算法2高平均效用co-location 模式挖掘優化算法HAUCP_IA

輸入：

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

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

c.最小距離閾值d；

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

輸出：

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

變量：模式長度l；長度為l 的候選co-location模式集合Cl；利用剪枝策略1 進行剪枝后的長度為l 的候選co-location 模式集合Cl'；利用剪枝策略2進行剪枝后的長度為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，進一步基于剪枝策略1 和剪枝策略2 排除了所有的非高平均效用co-location 模式，并計算保留的候選模式的表實例，得到所有k 階高平均效用co-location 模式。最后，由于高平均效用co-location 模式挖掘算法不滿足反單調性，所以，將所有k 階候選模式連接生成k+1 階候選模式，繼續判斷模式是否為高平均效用co-location模式，并返回所有高平均效用co-location 模式。

4 實驗與結果

以下呈現實驗所需要的真實數據集、合成數據集和相關的默認參數，并在真實數據集和合成數據集上，對所提出的基本算法HAUCP_BA 和剪枝算法HAUCP_IA 的有效性、可擴展性進行大量實驗。

4.1 實驗環境和數據集本文所有實驗都是基于Intel Core i5-8500 CPU 3.00 GHz、8 GB 內存的硬件平臺和Windows 10 操作系統、Python 3.7 的軟件平臺進行的。

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

表2 基于真實數據集的樣本相關參數

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

表3 基于合成數據集的樣本相關參數

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

圖2 不同數據集下算法的運行效率

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

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

圖3 不同距離閾值下算法的運行效率

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

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

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

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

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

圖5 真實數據集下HAUCP 和HUCPM 算法挖掘結果對比

圖6 合成數據集下HAUCP 和HUCPM 算法挖掘結果對比

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

5 結論

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