基于空間占有度的主導并置模式挖掘
2022-02-11 13:32:24王麗珍王曉璇楊培忠
計算機研究與發展 2022年2期
方 圓 王麗珍 王曉璇 楊培忠
1(云南大學數學與統計學院 昆明 650500) 2(云南大學西南天文研究所 昆明 650500) 3(云南大學信息學院 昆明 650500)
空間并置模式(spatial co-location patterns, SCPs)代表一組不同類型的空間特征的組合，該組特征的實例在空間中頻繁地共存.作為空間數據挖掘及空間關聯規則挖掘領域的一個重要分支，空間并置模式挖掘(以下簡稱為SCPs挖掘)旨在發掘隱藏在空間復雜分布中的有趣知識，揭示空間特征之間的相關性，在生態學研究、公共衛生服務、基于位置的模式推薦、城市規劃、決策支持等領域有著廣泛的應用.
經典的SCPs挖掘過程首先收集位于同一鄰域(實例間滿足兩兩鄰近關系)且屬于同一特征組的實例組(并置實例)，而后通過參與度-參與率度量提取頻繁的空間并置模式.圖1(a)顯示了一個簡單的分布數據集，其中6個空間特征A
,B
,C
,D
,E
和F
的實例分別用不同形狀的頂點表示，實例之間的邊代表2個實例之間有鄰近關系.圖1(b)列出了圖1(a)數據集中模式{A
,B
,C
}的并置實例，以及模式的特征參與率(participation ratio,PR
)和參與度(participation index,PI
).假設頻繁性閾值設置為0.3，則{A
,B
,C
}是一個頻繁的SCP.
Fig. 1 An explanatory example圖1 一個說明性示例
在某些空間并置模式的應用場景中，只考慮模式的頻繁性，將參與度高的模式推薦給用戶已不能滿足用戶的需求.例如，在城市公共基礎設施規劃中，頻繁的空間并置模式代表了一組公共設施類型在城市區域分布中的普遍性.然而，這項應用更關心在模式代表的并置實例具有普遍性的基礎上，盡量提供全面的公共基礎設施，為居民的城市生活提供便利.因此，為了保證合理規劃，規劃者希望得到既具有普遍性又能較為全面地反映城市居民需求的一組公共基礎設施類型，用以指導新城區的規劃建設.在這項應用中，推薦給用戶的模式需要結合并置模式的頻繁性和完整性2方面的信息，才能更好地為用戶提供決策支持.
經典的SCPs挖掘方法采用的參與度-參與率度量很好地體現了空間并置模式代表的一組空間特征共存的強度.然而，高階SCPs的參與度往往比它的低階子模式的參與度要低.因此，在要求模式的高參與度時，往往損失了模式代表的地理空間中特征信息的完整度.為了提高并置模式的可用性，我們引入了頻繁項集挖掘中“占有度”的概念，來衡量空間并置模式的完整性，并結合空間占有度和參與度，提出了挖掘主導空間并置模式(dominant spatial co-location patterns, DSCPs)挖掘.與一般的SCPs模式只考慮模式的頻繁性相比，DSCPs同時考慮了模式的頻繁性和完整度，是一類可用性更高、信息更全面的高質量并置模式.
本文的主要貢獻包括3個方面:
1) 提出了一種等價關系，稱為實例間的連通關系，對并置模式的實例進行劃分.基于該劃分定義了空間占有率和空間占有度的概念，作為衡量并置模式完整性的指標;
2) 通過結合參與度和占有度指標，形式化定義了主導并置模式挖掘問題，并提供占有度和參與度之間的權重參數，讓用戶根據不同的偏好獲得期望的挖掘結果.然后開發了一種稱為DSCPMA算法(主導空間并置模式挖掘算法)來解決DSCPs挖掘問題;
3) 在DSCPMA算法的基礎上探索了空間占有度度量的上限.此外，設計了一種新的數據結構，稱為并置鄰域表來存儲實例，提出了一系列剪枝策略改進DSCPMA算法效率.
通過在具有不同數據密度和數據規模的幾個合成數據集上改變參數設置的實驗，測試了不同參數和所提出的剪枝策略對算法的影響.在不同數據集上的實驗結果表明我們提出的DSCPMA算法可以有效地挖掘主導并置模式.
1 相關工作
并置模式挖掘在空間數據挖掘領域有著重要的作用.基于占有度度量的頻繁項集挖掘也都有著廣泛的應用和重要的研究意義.接下來，我們概述已有的部分空間并置挖掘方法及其在不同條件下的應用.
空間并置模式表示不同類型的空間特征子集的頻繁共現.由于空間的連續性和復雜性，空間并置模式挖掘中缺乏事務數據庫中頻繁項集挖掘的事務概念.因此，Huang等人提出使用用戶指定的鄰域代替事務項來指定空間項集，并且還定義了一個頻繁性度量，該度量具有理想的反單調性，即參與度(率)，以衡量空間特征集的實例的共現頻率.同時，開發了一種稱為Join-base算法的類Apriori算法來發現所有頻繁的并置模式.之后，鑒于join-base算法進行了大量的instance-join查詢操作，為降低其在密集數據集上的計算開銷，提出了一系列方法來提高基于連接的算法的效率.同時，隨著并置模式挖掘的廣泛應用，其應用場景變得愈加多樣和復雜，為進一步提高并置模式挖掘的可用性，研究者從數據驅動和領域驅動2個方面對現有的模式挖掘方法進行改進及拓展.數據驅動方法側重于在不同數據類型上挖掘并置模式，例如針對不確定數據、模糊對象、擴展對象、時空數據等不同數據類型的并置模式挖掘以及并置模式的壓縮表示.并置模式壓縮表示包括使用極大并置模式挖掘方法的有損壓縮方法和使用閉的并置模式的無損壓縮方法.同時，一些針對特定挖掘目的或領域知識約束的并置模式挖掘被相繼提出，用以滿足各種領域應用的需求.例如挖掘高效用并置模式、含主導特征的并置模式、區域并置模式、動態并置模式、具有特定關系的并置模式等.
作為一個有趣的新度量，“占有率”的概念由Tang等人提出，旨在捕獲挖掘頻繁項集模式的完整性，用于衡量模式(項集)在其支持事務中占據的比例.文獻[38]將占有率度量擴展到序列數據，以挖掘高質量的序列模式.文獻[39]將占有率概念引入到高效用模式挖掘中，提出了一種稱為效用占有率的度量來衡量模式在支持事務中的貢獻.Shen等人根據用戶在頻繁度、效用和占有率方面的偏好來挖掘高效用占有模式.由于每個項在實際應用中可能具有不同的重要性，因此Zhang等人將不同事務項的權重納入占有率，挖掘具有頻繁性和權重占有率的高質量模式.與使用模式的絕對大小作為約束的傳統最大模式相比，占有率度量模式與其支持事務的相對大小，可以被視為一種更靈活的度量方法，并成功應用于許多需要挖掘結果的完整性信息的實際應用中，例如網頁區域推薦、網絡打印任務推薦、旅行路線推薦、商品匹配推薦等.
主導空間并置模式挖掘的任務看起來類似于基于占有率的項集挖掘問題，但實際上由于空間數據集中缺乏獨立的事務概念，二者在挖掘方法上并不相同：1)空間數據占有率(度)度量與頻繁項集挖掘工作的占有率度量定義不同.頻繁項集挖掘工作中的傳統占有率度量基于事物概念，事務數據庫中的各項事務彼此獨立.然而，空間特征的實例天然嵌入在連續空間中，并且彼此共享各種空間關系(例如鄰居關系).因此，我們為空間并置模式挖掘開發了一種新的空間占有率(度)度量.2)挖掘目標不同.傳統的基于占有率的事物數據挖掘旨在尋找頻繁并占據其大部分支持事物的模式.然而，DSCPs挖掘旨在找到一組代表空間鄰域中實例的大部分實例分布且特征之間具有強烈關聯的并置模式.3)挖掘DSCPs的技術不同于基于占有率的事務數據模式挖掘的技術.DSCPs挖掘框架基于空間實例之間的鄰近關系，而不是基于事務數據中獨立的事務項，因此需要基于空間數據的特性，為DSCPs挖掘開發新的算法和新的數據結構.此外，空間占用率(度)度量不滿足單調或反單調特性，因此需要探索新的剪枝策略來提高DSCPs挖掘的效率.
2 主導空間并置模式
2.1 基礎概念
本節給出并置模式挖掘的一些基本概念和定義.由于符號較多，為了便于讀者閱讀，表1顯示了本文對符號及其含義的統一描述.
Table 1 List of Notations
在空間數據庫中，每個空間對象都被看作一個空間實例，且屬于一個特定的事物類型(特征).
給定一個空間特征的集合F
={f
,f
…,f
}和一個空間實例集合S
=S
∪S
∪…∪S
(S
(1≤i
≤n
)是特征f
的實例集合)，一個空間并置模式c
={f
,f
…,f
}是空間特征集F
的子集,c
?F
，模式中包含的特征個數k
稱為并置模式的階.
包括所有c
的特征且在給定的鄰近關系R
下形成團的k
個實例組成的集合稱為c
的并置實例，所有并置實例的集合稱為c
的表實例，記為T
(c
).
如圖1(a)所示，{A.
1,B.
1,C.
1}是{A
,B
,C
}的一個并置實例，{A
,B
,C
}的表實例如圖1(b)所示.
值得一提的是，單個特征可以看作是階數為1的頻繁并置模式，其表實例是該特征的所有實例的集合.
min
_prev
，如果PI
(c
)≥min
_prev
，則c
是一個頻繁的空間并置模式，一般來說，頻繁的空間并置模式往往簡稱為空間并置模式(spatial co-location patterns, SCPs)或并置模式.
如圖1(b)所示，PI
({A
,B
,C
})=4/
6，假設min
_prev
=0.
3，則{A
,B
,C
}是一個頻繁共置模式.
引理1.
參與率(度)的反單調性.參與率和參與度隨著模式階數的增加而單調遞減.2.2 相關定義
定義1.
實例的鄰域.
給定一個空間特征的集合F
={f
,f
…,f
}及空間實例集S
，o
為特征f
(f
∈F
)的實例，則實例o
的鄰域定義為IN
(o
)={o
∈S
|(o
=o
)∨((f
≠f
)∧R
(o
,o
))},(1)
其中，o
為特征f
(f
∈F
)的實例，R
為空間鄰近關系.
定義2.
并置實例的鄰域.
給定一個k
階的空間并置模式c
={f
,f
…,f
}，對于c
的任一并置實例l
={o
,o
,…,o
}，并置實例l
的鄰域定義為
(2)
相應地，c
的表實例鄰域定義為c
所有并置實例鄰域的集合：TN
(c
)={RN
(l
),RN
(l
),…,RN
(l
)}.
對于圖1(b)所示的空間并置模式{A
,B
,C
}的表實例，其表實例鄰域如表2所示.
圖2(a)中的實線代表實例之間的鄰近關系R
，圓圈內區域展示了{A
,B
,C
}的并置鄰域，可以看到，模式的并置實例在空間上相互重疊.
Table 2 Table Instance Neighborhoods of {A,B,C}
Fig. 2 Sample distribution data sets of {A,B,C}圖2 {A,B,C}的數據分布樣例
定義3.
連通關系及連通鄰域.
給定一個空間實例集S
，對于任意2個空間實例o
和o
(o
,o
∈S
)，在鄰近關系R
下，若存在至少一條o
連通到o
的路徑，那么o
和o
滿足連通關系，記為CR
(o
,o
).
形式化定義如下：CR
(o
,o
))?{R
(o
,o
1),R
(o
1,o
2),…,R
(o
,o
)},(3)
其中，o
1,o
2,…,o
∈S.
若一組空間實例的子集O
={o
,o
,…,o
}(O
?S
)中的所有實例滿足兩兩連通關系，則O
稱為一個連通鄰域.
定理1.
連通關系是一個空間實例集S
上的等價關系.
證明.
1) 自反性.
對于任意實例o
(o
∈S
)，容易證明CR
(o
,o
).
2) 對稱性.
對于任意2個空間實例o
和o
(o
,o
∈S
)，容易證明CR
(o
,o
)?CR
(o
,o
).
3) 傳遞性.
對于任意3個空間實例o
,o
,o
(o
,o
,o
∈S
)，若滿足CR
(o
,o
)和CR
(o
,o
)，則：CR
(o
,o
)?{R
(o
,o
1),R
(o
1,o
2),…,R
(o
,o
)},CR
(o
,o
)?{R
(o
,o
1),R
(o
1,o
2),…,R
(o
,o
)},那么,
{R
(o
,o
1),…,R
(o
,o
),R
(o
,o
1),…,R
(o
,o
)}?CR
(o
,o
).
連通關系滿足自反性、對稱性和傳遞性，是空間實例集S
上的等價關系.
證畢.
引理2.
給定一個k
階的空間并置模式c
={f
,f
…,f
}和表實例T
(c
)={l
,l
,…,l
}，對于T
(c
)的任一并置實例l
={o
,o
,…,o
}(l
∈T
(c
))，l
中的所有實例都屬于連通關系下的一個等價類.
證明.
設2個空間實例o
和o
(o
,o
∈l
)滿足R
(o
,o
)，根據定理1，R
(o
,o
)?CR
(o
,o
)，因此l
中的所有實例都屬于連通關系下的同一等價類.
證畢.
引理3.
給定一個k
階的空間并置模式c
={f
,f
…,f
}和表實例T
(c
)={l
,l
,…,l
}，對于T
(c
)的并置實例l
,l
(l
,l
∈T
(c
))，若l
∩l
≠?，則l
∪l
中的所有實例都屬于連通關系下的一個等價類.
證明.
假設l
∩l
={o
}，根據定理1中連通關系的傳遞性，任何l
和l
中的實例都通過與o
滿足連通關系而相互滿足連通關系，因此，l
∪l
中的所有實例都屬于連通關系下的一個等價類.
證畢.
定義4.
并置實例的劃分.
給定一個k
階的空間并置模式c
={f
,f
…,f
}，表實例T
(c
)={l
,l
,…,l
}在連通關系上的劃分表示為并置實例等價類的集合：TP
(c
)={tp
,tp
,…,tp
},其中，tp
={l
,l
,…,l
}(tp
∈TP
(c
))代表T
(c
)的一個并置實例等價類,tp
∩tp
=?,1≤i
<j
≤m.
相應地，任一并置實例等價類tp
(tp
∈TP
(c
))的實例集合ip
={l
∪l
∪,…,∪l
}稱為并置模式c
的一個實例分區，則c
的實例分區集合定義為CIP
(c
)={ip
,ip
,…,ip
}.c
的實例分區滿足3個條件：1)c
的任一分區中的所有實例都相互滿足連通關系.
2) 屬于c
的不同分區的2個實例o
和o
，不滿足連通關系.
3)T
(c
)的任何實例都必須屬于且僅屬于c
的一個分區.
請注意，TP
(c
)是并置實例等價類的集合，其等價類中的元素是并置實例，而CIP
(c
)是實例等價類的集合，其等價類中的元素是實例.
定義5.
實例分區鄰域.
給定一個k
階的空間并置模式c
={f
,f
,…,f
}，表實例在連通關系上的等價類集合TP
(c
)={tp
,tp
,…,tp
}，及并置模式c
的實例分區CIP
(c
)={ip
,ip
,…,ip
}，則對于任一并置實例等價類tp
(tp
∈TP
(c
))，其對應的實例分區ip
(ip
∈CIP
(c
))的鄰域定義為
(4)
同樣地，并置模式c
的實例分區鄰域定義為c
的實例分區的鄰域集合：PN
(c
)={pn
,pn
,…,pn
}.
例如：并置模式{A
,B
,C
}的實例鄰域及分區鄰域如表2所示,模式{A
,B
,C
}的表實例劃分為TP
({A
,B
,C
})={{l
,l
,l
},{l
},{l
}},{A
,B
,C
}的實例分區鄰域的集合為PN
({A
,B
,C
})={pn
,pn
,pn
},pn
=RN
(l
)∪RN
(l
)∪RN
(l
)={A.
1,A.
2,B.
1,B.
2,C.
1,D.
1,E.
1}，pn
={A.
3,B.
3,C.
3,D.
2}，pn
={A.
5,B.
4,C.
5}.
如圖2(b)所示，實例之間的實線代表模式{A
,B
,C
}的實例之間的連通關系，圓圈內區域展示了{A
,B
,C
}模式的實例分區鄰域，可以看到，實例的連通關系劃分解決了并置模式的并置實例及其鄰域的重疊問題.
在此基礎上，我們給出了空間占有率及占有度的定義.
定義6.
空間占有率及空間占有度.
給定一個k
階并置模式c
，c
的實例分區集合CIP
(c
)={ip
,ip
,…,ip
}及實例分區的鄰域集合PN
(c
)={pn
,pn
,…,pn
}，則任一實例分區ip
(ip
∈CIP
(c
))的空間占有率定義為
(5)
空間占有度定義為并置模式c
所有實例分區的空間占有率的最小值，即：
(6)
定義7.
模式質量.
給定一個k
階并置模式c
，一個用戶指定的權重參數ω
，則并置模式c
的質量定義為Quality
(c
)=ωPI
(c
)+(1-ω
)OI
(c
).
(7)
例如：假設權重參數ω
=0.
4，則并置模式{A
,B
,C
}的質量值為Quality
({A
,B
,C
})=0.
4×0.
67+0.
6×0.
75=0.
718.
2.3 主導空間并置模式挖掘問題
定義8.
主導空間并置模式.
給定一個空間特征集F
，空間實例集合S
，鄰近關系R
，模式頻繁性閾值min
_prev
(0≤min
_prev
≤1)，占有度閾值min
_occ
(0≤min
_occ
≤1)，對于一個k
階的空間并置模式c
，當滿足：1)PI
(c
)≥min
_prev
，2)OI
(c
)≥min
_occ
時，c
稱為一個主導空間并置模式(dominant spatial co-location patterns, DSCPs).
主導空間并置模式挖掘的目的是發現同時滿足min
_prev
和min
_occ
條件的所有并置模式，并按質量值對結果進行降序輸出.
由于空間數據缺乏明確的事務概念，因此與傳統的占有率定義不同，在空間數據上需要重新定義空間占用率(度)的概念，來衡量并置模式的完整性.本文提出一種等價關系——連通關系，給出了連通關系上的并置實例的劃分，解決了空間并置實例及其鄰域的重疊問題.基于模式的實例分區和實例分區鄰域定義，我們提出了空間占有率(度)度量，用于評估并置模式的完整性并形式化了主導空間并置模式(DSCPs)挖掘問題.與事務數據的占有率度量一樣，空間占有度度量也不滿足單調或反單調性質，因此第3節將探討空間占有度的2個上界，以提高DSCPs挖掘的效率.
此外，讀者可能對DSCPs挖掘和極大并置模式挖掘之間的區別感興趣.這2項工作在挖掘目的和方法上都有不同點.極大并置模式挖掘旨在挖掘所有并置模式的代表性模式，挖掘過程仍基于實例的鄰近關系，根據極大并置模式集可推導出挖掘結果中的所有頻繁模式，可以看作SCPs模式挖掘結果的壓縮表示.DSCPs挖掘旨在找到一組同時考慮頻繁性與完整性的高質量并置模式集，根據空間占有率及占有度的定義，盡管高占有度似乎意味著并置模式的階數更高，但當并置實例的鄰域中有大量鄰居時，一個極大并置模式仍可能具有較低的空間占有率.此外，DSCPs模式的完整性的評估過程考察了并置實例鄰域中其他特征實例對并置實例的影響，因此DSCPs的特征之間更可能存在強烈的關聯.
通過將頻繁性和完整性結合，DSCPs的挖掘結果在實際應用中更具有針對性，我們將在實驗部分對DSCPs應用實例進行分析和闡述.
3 DSCPs挖掘算法
3.1 基本算法
本節中，我們首先提出一個基礎算法對主導并置模式進行挖掘.
算法1.
主導并置模式挖掘基本算法(Basic_DSCPMA).輸入：空間特征集F
、空間實例集S
、鄰近關系距離閾值d
、頻繁性閾值min
_prev
、占有度閾值min
_occ
、質量權重ω
；輸出：主導空間并置模式集D
_set.
①NI
=find
_ins
_neighbors
(S
,d
)；②P
=F
,k
=2,D
_set
=?;③ while (P
-1≠?)④C
=gen
_candi
_co
-location
(k
,P
-1);/
*引理1*/
⑤ for eachc
∈C
⑥T
(c
)=gen
_table
_ins
(NI
,c
);⑦ if (cal
_PI
(c
))≥min
_prev
⑧P
←c
;⑨TN
(c
)=find
_neighbors
(T
(c
),NI
);⑩ InitializeTP
(c
)←T
(c
);/
*對表實例進行連通關系上的劃分*/
該算法的具體流程總結如下：
1) 將輸入空間數據物化為定義2中給出的實例鄰域模型(行①).
這個過程可以看作是文獻[6]提到的星型鄰居實例模型的一個變體.
2) 生成候選DSCPs(行②～④).
根據參與度的定義將所有特征初始化為1階并置模式.
從k
-1階頻繁并置模式集P
-1(引理1)生成k
階(k
>1)候選模式.
對于一個候選模式c
，如果c
的任一k
-1子模式不頻繁，則該候選模式將被剪枝(行④).
3) 候選模式的頻繁性過濾(行⑤～⑧).
由于空間鄰近關系是對稱的，因此可以直接從每個并置實例的第1個特征的實例鄰域中獲得二階候選并置實例.
對于3階以上的候選模式，則需要在生成表實例之前檢查實例之間的團關系(行⑥).
接下來計算候選者的參與率和參與度，如果參與度超過閾值min
_prev
，將這個候選者加入k
階頻繁并置模式集P
(行⑦～⑧).
算法2.
并置實例劃分算法(divide
_instance
(TP
(c
))).
輸入：候選模式的表實例TP
(c
)；輸出：候選模式在連通關系上的劃分TP
(c
)，CIP
(c
).
①Flag
=True;② for each pair oftp
,tp
∈TP
(c
)③ if (tp
∩tp
≠?)④Flag
=False;⑤ deletetp
,tp
fromTP
(c
);⑥TP
(c
)←Union
(tp
,tp
);⑦ if (Flag
)⑧CIP
(c
)←get
_ins
_set
(TP
(c
));⑨ returnTP
(c
),CIP
(c
);⑩ else
3.2 剪枝策略
在本節中，我們探索了空間占有度的2個上限以幫助修剪DSCPs的搜索空間，并設計了一種新的數據結構來提高DSCPs挖掘的效率.
3.2.1 并置鄰居表
為了提高DSCPs挖掘過程的效率，縮減模式存儲的冗余信息，本文設計了一種新的數據結構：并置鄰居表，用于存儲模式的并置實例鄰域中的實例.基于這種新的數據結構，我們可以建立特征之間的映射關系，以加快對候選DSCPs的參與度和占有度的計算過程.
定義9.
并置鄰居表.
給定一個k
階并置模式c
，c
的并置鄰居表(co-location neighborhood table,CNT
)由下列3部分組成：①c
的表實例鄰域：TN
(c
)={RN
(l
),RN
(l
),…,RN
(l
)}及并置模式的索引；② 模式的特征集c
={f
,f
,…,f
}及出現在表實例鄰域中的鄰居特征集，記為NF
(c
)={f
+1,f
+2,…,f
},k
<o
,f
∈F
；③ 表實例鄰域中的所有特征的實例個數統計.
如圖3所示，并置鄰居表列出了并置實例及其鄰域中的所有實例，并置實例的鄰居實例按其特征類型分組并存儲為枚舉結構.
在接下來的挖掘過程中，我們將展示這種新的數據結構如何在各個DSCPs挖掘階段提高挖掘效率.
Fig. 3 Co-location neighborhood table圖3 并置鄰居表數據結構示例
3.
2.
2 基于參與度的剪枝剪枝策略1.
給定一個k
階并置模式c
，c
的鄰居特征集NF
(c
)，對于任一k
+1階候選模式c
+1=c
∪f
,f
∈NF
，若滿足：|π
(CNT
(c
))|/
|T
(f
)|≤min
_prev
，則根據引理1，該候選模式可以被剪枝.
為在不生成表實例的情況下直接計算所有k
+1階候選模式參與率及參與度，我們提出一組特征映射函數建立特征之間的映射關系.
在給出特征映射函數的定義之前，為方便描述，本文首先引入文獻[44]中集合信息函數的定義，描述特征和并置實例鄰域之間的關系.
α
表示行實例集合對某一特征的實例集合的映射，函數β
表示某一特征的實例集對一組行實例集合的映射.
基于集合信息函數α
和β
，我們給出空間特征映射函數的定義.
定義10.
特征映射函數.
給定一個k
階并置模式c
，其并置鄰居表CNT
(c
)中的特征f
到f
的映射函數定義為
(8)
例如：對于頻繁并置模式{A
,B
}，該模式的鄰居特征C
在并置鄰居表CNT
({A
,B
})中的實例集合表示為：π
(CNT
({A
,B
}))={C.
1,C.
2,C.
3,C.
5}，而與特征C
的實例位于同一并置實例的特征A
的實例可直接通過映射函數表示為φ
→({C.
1,C.
2,C.
3,C.
5})=α
(β
{C.
1,C.
2,C.
3,C.
5})=α
({l
,l
,l
,l
,l
})={A.
1,A.
2,A.
3,A.
5}.
給定一個k
階并置模式c
及其鄰居特征集NF
(c
)，對于任意k
+1階候選模式c
+1=c
∪f
,f
∈NF
(c
)，c
+1的參與度可以直接計算為
f
∈NF
(c
).
基于定義8，我們可以修剪頻繁并置模式的搜索空間，并直接從并置鄰居表CNT
(c
)計算所有以c
為前綴的k
+1階候選模式的參與度而無需生成它們的表實例.
3.
2.
3 基于空間占有度的剪枝盡管空間占有度度量不滿足單調性或反單調性，但我們仍然可以探索占有度度量的上限，以在挖掘DSCPs時減小搜索空間.
引理4.
空間占有度上界.
給定一個k
階并置模式c
，c
的實例分區集CIP
(c
)={ip
,ip
,…,ip
}，c
的實例分區鄰域PN
(c
)={pn
,pn
,…,pn
}，空間占有度OI
(c
)存在一個上界：
ip
∈CIP
(c
),pn
∈PN
(c
).
證明.
(9)
m
=n
+1時式(9)成立.
證畢.
剪枝策略2.
給定一個k
階候選模式c
，c
的實例分區集合CIP
(c
)={ip
,ip
,…,ip
}，c
的實例分區鄰域PN
(c
)={pn
,pn
,…,pn
}及空間占有度閾值min
_occ
，根據引理4，若Upp
_occ
(c
)≤min
_occ
，則該候選模式可以被剪枝.
同時，基于c
的并置鄰居表CNT
(c
)，空間占有度上界Upp
_occ
(c
)可簡單地通過下式直接計算:
基于引理4，DSCPs挖掘過程中生成實例分區鄰域的過程可以通過剪枝策略2縮減候選模式搜索空間來減少計算開銷.然而，表實例劃分算法的遞歸過程仍然需要大量的計算.在實例分區過程之前對候選模式進行再一次過濾將能夠進一步限制DSCPs的搜索空間，因此我們還為空間占有度計算了一個寬松的上限.
引理5.
寬松的空間占有度上界.
給定一個k
階并置模式c
，c
的實例分區集CIP
(c
)={ip
,ip
,…,ip
}，c
的實例分區鄰域PN
(c
)={pn
,pn
,…,pn
}，空間占有度OI
(c
)存在一個寬松的上界：
.
根據引理4：
.
剪枝策略3.
給定一個k
階候選模式c
，c
的實例分區集合CIP
(c
)={ip
,ip
,…,ip
}，c
的實例分區鄰域PN
(c
)={pn
,pn
,…,pn
}及空間占有度閾值min
_occ
，根據引理5，寬松的空間占有度上界，若Loose
_Upp
_occ
(c
)≤min
_occ
，則該候選模式可以被剪枝.
3.3 改進算法
根據3.2節中提出的并置鄰居表數據結構和3個剪枝策略，本文提出DSCPs的改進挖掘算法，表示為DSCPMA_IA算法，該算法在候選模式的生成、頻繁性過濾和及占有度過濾步驟中都進行了剪枝操作和基于并置鄰居表結構的快速計算.算法3對改進的DSCPMA_IA算法進行了詳細描述.
1) 生成候選并置模式.
對于頻繁的并置模式p
-1，其從p
-1擴展的候選k
階并置模式可以從p
-1的并置鄰居表CNT
(p
-1)中進行選擇.
根據剪枝策略1，我們通過測試直接從CNT
(p
-1)獲得的每個擴展特征的參與率過濾k
階的候選模式.
2) 頻繁性過濾.
我們計算從CNT
(p
-1)擴展的k
階候選模式的參與度.
根據定義10，我們可以計算k
階候選模式的參與度，而無需生成候選表實例.
3) 完整性過濾.
使用剪枝策略3，候選模式c
可以通過其寬松的上界Loose
_Upp
_occ
(c
)進行過濾.
然后進一步使用剪枝策略2修剪DSCPs的搜索空間，從而避免消耗為空間占有率上界低于占有度閾值的候選模式生成進行表實例劃分及實例分區的成本.
算法3.
改進的主導并置模式挖掘算法(DSCPMA_IA).輸入：空間特征集F
、空間實例集點S
、鄰近關系距離閾值d
、頻繁性閾值min
_prev
、占有度閾值min
_occ
、質量權重ω
；輸出：主導空間并置模式集D
_set.
①NI
=find
_ins
_neighbors
(S
,d
)；②P
=F
,k
=2,D
_set
=?;③ while (P
-1≠?)④ for eachf
∈Neighbor
_Feature
(CNT
(p
-1))⑤c
=p
-1∪f
;⑥ if (|π
(CNT
(p
-1))|/
|π
(T
({f
}))|≥min
_prev
)⑦PI
(c
)=calculate
_PI
(CNT
(p
-1),f
);⑧ if (PI
(c
)≥min
_prev
)⑨P
←c
;⑩CNT
(c
)=generate
_CNT
(CNT
(p
-1),f
);
min
_occ
)
CIP
(c
));
PN
(c
));
OI
(c
),PI
(c
));
Q
(c
));
3.4 算法復雜性分析
本節比較了2種算法Basic_DSCPMA(以下簡稱BA)和改進的算法DSCPMA_IA(以下簡稱IA).2種算法都涉及5個階段：1)將空間數據物化為實例鄰域模型；2)生成候選DSCPs；3)候選模式的頻繁性過濾；4)候選模式的完整性過濾；以及5)按質量值對DSCPs進行排序輸出.整個算法過程的大部分計算時間用于2)～4)三個階段.因此，下面我們將詳細分析2種算法在生成候選DSCPs、候選模式頻繁性過濾和候選模式完整性過濾3個主要算法過程中的時間及空間耗費.
1) 生成候選DSCPs過程.在BA中，該進程只根據引理1進行過濾，從而避免生成不必要的表實例.在IA中，對于頻繁的并置模式p
-1，p
-1的并置鄰居表CNT
(p
-1)提供剪枝和過濾所有由p
-1擴展的候選k
階并置模式所需的信息，因此無需生成非頻繁模式的表實例.
這個過程節省了不必要的并置候選參與度計算及其表實例的存儲空間.
同時，從p
-1的并置鄰居表CNT
(p
-1)生成p
的并置鄰居表CNT
(p
)的過程無需再進行團實例檢查，而可以通過特征映射函數，以CNT
(p
-1)的行號為索引生成新的CNT
(p
)，該過程減少了大量團關系查詢工作，生成新并置鄰居表的過程僅需要O
(n
)，n
為新并置鄰居表的行數.2) 候選模式頻繁性過濾過程.在IA中，對于每個候選c
=p
-1∪f
，f
的參與率可以直接從CNT
(p
-1)得到，其他特征在c
中的參與率可以通過映射函數計算，所以它只需要O
(m
)，m
是含有實例鄰居的擴展特征的并置實例的行數.因此，在改進算法中，我們節省了用于生成表實例和計算候選模式參與度的存儲空間與計算量.3) 候選模式完整性過濾過程.我們計算空間占有度的上限來修剪搜索空間，基于存儲參與表實例的特征投影的CNT
(p
-1)的最后一行，寬松的占有度上界可以被直接計算(剪枝策略2)，復雜度為O
(1).我們開發的剪枝策略的計算成本是恒定的.因此，這些剪枝策略不僅可以在挖掘過程中修剪DSCPs的搜索空間，而且促進了算法的效率.4 實驗評估
在本節中，我們在合成數據集和真實數據集上進行了實驗，從多個方面評估了所提出算法的運行表現和挖掘效果.所有算法均使用Visual C#語言進行開發并在2.4 GHz、8 GB內存和Intel Core i7的PC機上運行.
4.1 實驗數據集
我們在實驗中使用3個真實數據集和一系列合成數據集來評估算法的效率和有效性.
1) 合成數據.合成數據集采用類似于文獻[6]的方法生成合成數據.具體過程如下：首先，給定模擬數據的特征集合F
以及實例總數S
，并對特征集合中的特征依次編碼，以便于下一步生成各個特征的相應實例；然后，給定一個平均階數設定值k
(本文中設k
=5)，使用泊松采樣從特征集中生成階數為k
的m
個模式作為初始模式(本文中設m
=20)，在空間中為m
個初始模式隨機生成C
個并置實例的實例集合(本文選取C
為實例總數S
的1%)；之后，為每個初始模式的并置實例生成空間分布：為模擬空間實例的分布范圍，D
×D
的區域被網格化為d
×d
大小的單元(d
為給定的鄰近距離閾值)，隨機選擇一個單元網格，在給定網格大小范圍內進行隨機采樣，以生成一組并置實例的空間位置.接著，我們再將剩余的實例點隨機分配特征類型，并在D
×D
的區域隨機采樣生成實例的空間位置.Dataset-1,Dataset-2和Dataset-3在1 000×1 000空間中生成，Dataset-4在2 000×2 000空間中生成，Datasets-5～Datasets-12在100 000×100 000空間中生成.請注意，盡管Dataset-2包含的實例比Dataset-3少,但由于分布范圍更小，Dataset-2的密度高于Dataset-3.
Fig. 4 Real-1 dataset distribution圖4 Real-1數據分布
2) 真實數據.3個真實數據集的分布范圍如圖4～6所示.Real-1數據集是北京POI(point of interest)數據的空間分布數據集，如圖4所示，該數據集包含大約26 546個實例和16個特征，其實例分布均勻且密集，不同特征的實例數量差異很大，成簇狀分布.Real-2是云南“三江并流”保護區的植被分布數據集，如圖5所示，包含25個特征和13 350個實例，在空間中呈塊狀分布.Real-3數據集是云南“三江并流”保護區珍稀植物數據集，如圖6所示，包含32個特征，只有355個實例，在空間中呈明顯的帶狀分布.表3出了我們實驗中使用的所有真實數據集的分布范圍和默認參數.
Fig. 5 Real-2 dataset distribution圖5 Real-2數據分布
Fig. 6 Real-3 dataset distribution圖6 Real-3數據分布
Table 3 The Experimental Data Sets and Default Parameters
4.2 算法性能評估
本節考察Basic_DSCPMA(以下簡稱BA)和改進的DSCPMA_IA(以下簡稱IA)這2種算法在一系列合成數據集上的效率.討論在變化的距離閾值、最小頻繁閾值、占有度閾值和權重參數上2種算法的性能表現.
1) 頻繁閾值對算法的影響
BA和IA在4個不同的最小頻繁閾值(min
_prev
)下分別在4個數據集上的運行時間比較如圖7所示.BA和IA的結果分別用實線和虛線表示.不同的形狀標記代表不同數據集的結果，例如BA-1展示了BA在Dataset-1上的性能.對于每個數據集，BA和IA的運行時間都隨著min
_prev
的增加而減少.請注意，對于Dataset-1,Dataset-2,Dataset-3，在min
_prev
=0.6時BA和IA的運行時間相似，在min
_prev
=0.8時BA比IA更有效.這是因為較高的min
_prev
約束會導致生成較少的頻繁并置模式，并且其中大部分是低階模式.由于剪枝策略對2階模式沒有貢獻，IA的計算開銷反而大于BA.對于Dataset-1和Dataset-2，隨著特征數量的增加，算法效率隨之降低，所以Dataset-2的運行時間比Dataset-1長.Dataset-3的運行時間比Dataset-4長，表明效率主要受數據密度的影響.與實例數和特征數對算法的影響相比，數據密度對算法的影響更為顯著.參與度閾值min
_prev
對算法性能的影響在Dataset-3上體現得尤為明顯，因為低閾值和密集數據導致產生的大量高階模式候選，因此剪枝策略性能優勢更明顯.min
_prev
越低，修剪策略越有效，尤其是在密集數據集上.
Fig. 7 The effect of min_prev variation on different data sets圖7 頻繁性閾值變化在不同數據集上對算法性能的影響
Fig. 8 The effect of distance variation on different data sets圖8 距離閾值變化在不同數據集上對算法性能的影響
2) 距離閾值對算法的影響
圖8展示了BA和IA在Datasets-1～Datasets-4上的運行時間分別相對于它們的距離閾值變化的比較.較高的距離閾值對算法性能的影響尤為明顯，說明算法的性能主要受數據密度的影響.對于Dataset-1和Dataset-2，在d
=12時運行時間相似，這意味著當距離閾值較低時，BA和IA的效率差異很小.隨著距離閾值的不斷增加，由于IA中的一系列修剪策略有效地避免了為所有候選模式生成表實例，然后重復劃分模式的過程.IA算法的性能逐漸變得比BA的效率更高.Dataset-3上的運行時間遠大于Dataset-4上的運行時間，這表明所開發的算法對數據密度敏感，而實例數對算法影響不大.3) 空間占有度閾值對算法的影響
圖9顯示了BA和IA算法在Datasets-1～Datasets-4這4個數據集上的各自運行時間，相對于占有度閾值(min
_occ
)的變化.比較4個數據集上的運行時間，隨著每個數據集上占有度閾值的增加，運行時間沒有明顯變化.這是因為占有度度量不滿足單調性或反單調性.如果一個并置模式的參與度不小于min
_prev
，即使這個并置模式的占有度小于min
_occ
，仍然需要計算它的擴展模式的頻繁性.對于每個數據集，IA比BA更有效，因為IA可以通過使用2個上限來過濾許多候選模式，并減少模式在連通關系上的劃分過程的計算開銷.對于Dataset-1和Dataset-2，Dataset-1的計算效率優于Dataset-2，因為Dataset-2中的特征數量比Dataset-1多，但效率差異并不明顯.Dataset-3和Dataset-4的結果表明，在密集數據集上，IA算法的性能優勢尤為明顯.
Fig. 9 The effect of min_occ variation on different data sets圖9 不同數據集上占有度閾值變化對算法性能的影響
4) 算法的可伸縮性和擴展性
本節評估了BA和IA在不同情況下，即在合成數據集Dataset-5～Dataset-12上，通過在具有不同數量的空間實例和空間特征的數據上測試算法的可擴展性.
如圖10所示，當空間實例數達到400 000時，BA與IA的運行時間開始呈指數增長，當空間實例數達到500 000時，IA的運行時間仍然明顯優于BA.這意味著隨著實例的增加，IA比BA更有效.而在前期數據量較小或數據分布較為稀疏時，IA的剪枝策略效果不明顯.
Fig. 10 The effect of the number of instance variation圖10 實例個數變化對算法性能的影響
圖11顯示了BA和IA在隨著特征數量的增加算法的運行時間的變化.在特征數較少時，單個模式的并置實例數量巨大，并置鄰居表的快速生成和剪枝策略對候選模式的快速過濾使IA算法較之BA更高效.然而，當特征數量達到50時，由于空間實例的總數是固定的，單個特征的實例個數減少，則單個模式的行實例數降低，更難產生高階的DSCPs.大量高階候選并置模式在子模式頻繁性檢測階段就直接被淘汰，因此運行時間快速減少，IA的性能則與BA相近.這說明并置模式挖掘的主要瓶頸在于生成高階模式時的并置實例檢查，而本文提出的剪枝策略及數據結構有效地促進了這個階段算法的效率.
Fig. 11 The effect of the number of features variation圖11 特征數變化對算法性能的影響
Fig. 12 The effect of min_prev on real-world data sets圖12 真實數據集上min_prev對挖掘結果的影響
4.3 算法的有效性評估
頻繁性閾值min
_prev
和距離閾值d
是影響算法效率的主要因素.在本節中，我們將討論影響算法有效性的參數，并解釋DSCPs挖掘在真實數據集上的實際應用.實驗中使用了3個真實數據集來證明我們算法的有效性.與合成數據相比，真實數據集上的挖掘結果通常更有實際意義.空間占有度的概念可以看作是一個有趣的新度量和約束.根據DSCPs的定義，DSCPs需要滿足頻繁性和空間占有度約束，因此可以很容易地推斷出在相同的min
_prev
和d
下，min
_occ
=0的DSCPs的挖掘結果與傳統的頻繁空間并置模(SCPs)的挖掘結果是完全一致的.因此，我們通過改變頻繁性閾值(即min
_prev
)、占有度閾值(即min
_occ
)和權重(即ω
)來進行實驗，以揭示參數設置對DSCPs挖掘結果的影響.1)min
_prev
對挖掘結果的影響如圖12中的實驗所示，我們設置min
_occ
=0來獲得3個真實數據集上的SCPs，我們設置min
_occ
=0.
1來獲得Real-1和Real-2數據集上的DSCPs結果.我們設置min
_occ
=0.2以獲得Real-3數據集上的SCPs結果，其他默認參數如表3所示.在圖12中，我們展示了具有不同min
_prev
的SCPs和DSCPs的挖掘結果，并記錄了每個挖掘結果的不同大小模式的數量.可以看出，在每個數據集上，DSCPs和SCPs的數量都隨著min
_prev
的增加而減少，并且在相同min
_prev
下，SCPs挖掘結果的數量遠遠多于DSCPs挖掘結果的數量.值得注意的是，隨著min
_prev
的增加，SCPs結果中低階模式的比例越來越高.對于每個數據集，高階和低階的DSCPs的數量都較少，而中等階數的DSCPs的比例最大.2)min
_occ
對挖掘結果的影響圖13展示了在相同頻繁性閾值下，min
_occ
不同的優勢SCPs的挖掘結果，其中min
_prev
=0.2，其他默認參數如表3所示.對于圖13所示實驗結果中的每個數據集，SCPs挖掘結果由一個堆疊列表示，其中min
_occ
=0，不同的條紋表示不同的模式大小.可以看出，對于每個數據集，DSCPs的數量隨著min
_occ
的增加而迅速減少，尤其是對于較低階的模式.相反，隨著min
_occ
的增加，高階模式繼續保留在DSCPs結果中，表明即使空間占有度量不是嚴格單調的，模式階數越高，其空間占有度可能越高.圖13所示的實驗結果可以進一步解釋圖12中SCPs和DSCPs挖掘結果之間的差異.對于每個數據集，即使一些高階的模式被頻繁性閾值過濾，但大多數低階數的模式也被空間占有度閾值過濾.3) 權重參數ω
對挖掘結果的影響圖14顯示了使用不同權重(即改變ω
)的DSCPs挖掘結果的變化.根據定義7，權重參數ω
僅參與DSCPs挖掘過程的質量值計算部分.因此，它只能影響DSCPs結果的排序表示，而不會影響DSCPs挖掘結果.在圖14所示的實驗中，我們只選取了質量值最高的前20個DSCPs來觀察權重對DSCPs挖掘排序結果的影響，其中min
_prev
=0.
2，min
_occ
=0.
1.
對于每個數據集，隨著ω
的增加，前20位挖掘結果中，高階的DSCPs的比例減少，而挖掘結果中低階的DSCPs的比例增加.此外，在min
_prev
和min
_occ
相同的情況下，高ω
導致前20個DSCPs結果與按參與度排序的top-20個SCPs結果相似.例如，ω
=0.8時，圖14(a)中的DSCPs結果中不同階數的模式比例與圖13(a)中的SCPs結果相似；當ω
=0.2時，不同階數的DSCPs在圖14(c)中min
_occ
=0.3時的比例相似.顯然，ω
越高，參與度對DSCPs的貢獻比重越大.這表明ω
的作用在于調整空間占有度和參與度對DSCPs質量的貢獻以及對DSCPs挖掘結果進行排序，提高模式的可用性.
Fig. 13 The effect of min_occ on real-world data sets圖13 真實數據集上min_occ對挖掘結果的影響
Fig. 14 The effect of ω on real-world data sets圖14 真實數據集上ω對挖掘結果的影響
4.4 DSCPs挖掘方法應用實例分析
為進一步驗證DSCPs挖掘方法在實際應用中的有效性，我們接下來介紹在珍稀植物數據集上的DSCPs挖掘應用實例分析.
表4列出了真實數據集Real-2(珍稀植物)上按質量值降序輸出的top-5個DSCPs挖掘結果，表5列出了真實數據集Real-2輸出的top-5個按參與度值降序輸出的SCPs挖掘結果.
Table 4 The Results of top-5 DSCPs on Real-3 Data Set
Table 5 The Results of top-5 SCPs on Real-3 Data Set
與傳統的頻繁SCPs挖掘結果相比，表5中前5個參與度最高的模式都是低階模式，且都是表4中出現的模式的子集.以表4中的模式{云南楓楊(A),天女花(D)，三分三(I)，麗江雪膽(M)}為例，該模式在空間中的分布如圖15所示.可以看到模式的實例在其區域中都具有高的空間占有度，說明該組特征不僅在區域中具有很強的共存關系，且考慮了特征的多樣性，向植物學家提供參考性更強的模式，便于植物學家進一步研究DSCPs代表的一組空間特征在區域中組成的生物群落及不同植物類型之間的相關性.
Fig. 15 Spatial distribution of a DSCP圖15 一個DSCP的空間分布
5 結 論
目前，主流的空間并置模式挖掘的研究都將一組空間特征的實例在空間中共現的頻繁性，即參與率-參與度度量作為興趣度挖掘并置模式.然而，在一些并置模式的應用實例中，用戶不僅對共置模式的頻繁性感興趣，而且還關注模式的完整性，希望得到該區域內較為全面的空間特征的并置信息.為解決以上問題，我們引入了一種新的空間占用度度量來評估共置模式的完整性，并通過結合模式的頻繁性和完整性來制定主導空間并置模式(DSCPs)挖掘問題.為了解決經典并置模式(SCPs)挖掘過程中并置實例重疊問題，我們提出一種等價關系——連通關系將并置實例劃分為不重疊的實例分區集.我們還設計了一種有效的算法 DSCPMA 來發現DSCPs，并通過探索空間占用度的2個上界和一個數據結構來實施一系列剪枝，有效地減少了DSCPs的搜索空間.最后，我們在合成數據集和3個真實數據集上評估了算法的效率和有效性.將DSCPs挖掘方法在珍稀植物數據集上的應用結果表明，DSCPs挖掘結果解釋性更強，意義更明確，在實際應用中能夠為用戶提供更具有指導意義的知識.
作者貢獻聲明
：方圓提出了算法思路和實驗方案，完成實驗并撰寫論文；王麗珍提出指導性意見并修改論文；王曉璇負責收集實驗數據和完善實驗方案；楊培忠負責完善實驗方案和修改論文.猜你喜歡
數學小靈通·3-4年級(2024年2期)2024-05-15 02:02:28
小學教學研究(2022年18期)2022-06-29 02:18:18
世界科學技術-中醫藥現代化(2020年2期)2020-07-25 02:05:36
甘肅教育(2020年24期)2020-04-13 08:24:40
瘋狂英語·新策略(2019年10期)2019-12-13 08:43:28
冰雪運動(2019年5期)2019-08-24 08:04:52
當代陜西(2019年10期)2019-06-03 10:12:04
勞動保護(2019年3期)2019-05-16 02:38:06
數學小靈通·3-4年級(2017年9期)2017-10-13 08:10:54
中小學電教(2016年3期)2016-03-01 03:40:52
