胡自松，王麗珍，Vanha Tran，周麗華

云南大學 信息學院，昆明650504

當前人們正處在一個大數(shù)據(jù)時代，隨著科學技術的不斷進步以及各種電子設備的研發(fā)，人們所面對的數(shù)據(jù)呈現(xiàn)爆炸式的增長趨勢。這些數(shù)據(jù)不僅包括類別標簽信息，還包括空間地理位置信息。例如，移動設備、帶導航的車輛等所產(chǎn)生的數(shù)據(jù)；在流行病學中，記錄病人（比如新冠肺炎感染者）的信息不僅包括癥狀、發(fā)病時間、就診時間、個人基本信息，還包括家庭住址和工作地點等地理位置信息。

空間頻繁并置模式（spatial prevalent co-location pattern，SPCP）表示空間特征的子集，其實例在空間鄰域中可以被頻繁地觀察到?？臻g頻繁并置模式挖掘的目標是發(fā)現(xiàn)在鄰近區(qū)域經(jīng)常一起被觀察到的所有特征子集。圖1 為一個空間實例分布示例，其中的每個實例（數(shù)據(jù)點）通過用它的特征和實例編號表示，例如.1。這些實例可以代表某種類型（特征）的對象在空間中具體的出現(xiàn)，比如犯罪事件、酒吧、商店/餐館、植物/動物物種或者興趣點等。度量兩個實例間的鄰近關系，可以根據(jù)不同的應用需求選擇不同的度量方式，如歐氏距離和曼哈頓距離等。滿足鄰近關系的兩個實例在圖示中用一條實線連接。在圖1 中，一個空間并置模式{,,}的模式實例是{.2,.1,.2}和{.4,.2,.1}（在空間鄰近關系下形成團關系的實例子集稱為模式實例）。一個空間頻繁并置模式的頻繁度可以使用參與度（participation index）或分數(shù)評分（fraction-score）方法來度量。如果一個空間特征集的頻繁度不小于用戶給定的一個最小頻繁度閾值，則這個空間特征集被稱為頻繁并置模式。例如，特征集{,}的頻繁度為0.66，{,}的頻繁度為0.33，當給定的頻繁度閾值為0.6 時，{,}為一個頻繁并置模式。

圖1 一個空間實例分布示例Fig.1 Example of spatial instances distribution

頻繁并置模式挖掘具有許多的應用領域，包括基于位置的服務、城市規(guī)劃、地理信息系統(tǒng)、公共安全管理、環(huán)境科學等。例如，從犯罪數(shù)據(jù)集中發(fā)現(xiàn)的頻繁并置模式可以更好地給公共安全管理者提供安保預防措施；從植物分布數(shù)據(jù)集中發(fā)現(xiàn)的頻繁并置模式有助于植物地理學和植物生物學研究；在自然災害預防中，頻繁并置模式可以給應急指揮部門對自然突發(fā)災害提前做出預警，這樣就能將可能造成的損失降到最低。

圖數(shù)據(jù)庫是當前比較流行的一種非關系型數(shù)據(jù)庫，能方便地以圖形的形式表示數(shù)據(jù)和知識，提供了管理高度連接的數(shù)據(jù)和復雜的數(shù)據(jù)庫查詢以及原生圖形存儲和處理的能力。NoSQL 圖引擎中的屬性圖是帶標簽的有向圖，它由通過關系連接的結點和以鍵值對形式的一個或一組屬性組成。圖數(shù)據(jù)庫系統(tǒng)已經(jīng)在社交網(wǎng)絡、知識圖譜、推薦系統(tǒng)和欺詐檢測等領域得到應用。在空間并置模式挖掘中，模式的發(fā)現(xiàn)依賴于空間實例（數(shù)據(jù)）之間的鄰近關系，利用關系型數(shù)據(jù)庫不能很好地存儲實例間的鄰近關系，而利用圖數(shù)據(jù)庫可以將空間實例和它們之間的鄰近關系存儲為原生的圖數(shù)據(jù)，基于圖的特點能高效地對結點和邊（鄰近關系）訪問并且可以使用圖結構的自然伸展特性設計鄰居結點遍歷算法（圖的遍歷算法）來收集模式表實例。圖數(shù)據(jù)庫查找數(shù)據(jù)不受數(shù)據(jù)量大小的影響，因為鄰近查詢是對有限的局部數(shù)據(jù)搜索，不會對整個圖數(shù)據(jù)庫進行搜索。于是可以用圖數(shù)據(jù)庫來物化空間實例間的鄰近關系，將頻繁并置模式挖掘問題轉化為鄰近關系圖（neighborhood graph）數(shù)據(jù)庫上的團（clique）的查找問題，即利用圖數(shù)據(jù)庫技術有效地挖掘空間頻繁并置模式。

現(xiàn)有的頻繁并置模式挖掘算法，如基于Aprior-Like 框架提出的算法、基于分布式框架提出的算法等都具有較好的執(zhí)行表現(xiàn)，但仍存在局限。其一，面向海量空間數(shù)據(jù)集時，單機操作會出現(xiàn)內存溢出、執(zhí)行效率不可接受等問題；其二，重啟系統(tǒng)后，需要從計算空間鄰近關系開始重新執(zhí)行挖掘算法。因為基于內存挖掘的算法是將空間鄰近關系存儲在內存中（如存儲為樹型結構），當數(shù)據(jù)量較大需要內外存交換時，如果設計的數(shù)據(jù)結構不支持內外存交換將出現(xiàn)內存溢出問題，當設計的數(shù)據(jù)結構支持內外存交換，則會出現(xiàn)運行效率極低，無法滿足應用需求的問題。直接將經(jīng)典的挖掘算法移植到圖數(shù)據(jù)庫上不能發(fā)揮圖數(shù)據(jù)庫的優(yōu)勢導致效率不高。此外，對于上述相關工作所采用的方法需要先收集模式的所有表實例，但計算一個特征的參與實例數(shù)是統(tǒng)計模式特征不重疊的實例個數(shù)，保存表實例的方法重復存儲實例帶來了很大的空間開銷。例如，模式{,}涉及實例.2 的模式實例為{.1,.2}和{.2,.2}，實例.2 被重復存儲了兩次，但是在計算特征的實例參與率時，.2 的參與貢獻實際上為1。為此，提出了基于圖數(shù)據(jù)庫的一種實例參與驗證的方法來挖掘空間頻繁并置模式。

主要貢獻總結如下：

（1）將空間頻繁并置模式挖掘問題轉化為基于圖數(shù)據(jù)庫的子圖（團）查找問題。傳統(tǒng)的并置模式挖掘方法通常是將物化的空間鄰近關系存儲到內存中，然后進行挖掘。本文徹底改變傳統(tǒng)的挖掘方法，提出基于圖數(shù)據(jù)庫有效挖掘頻繁并置模式的新方法。

（2）傳統(tǒng)的方法每次啟動程序都需要重新計算實例的鄰近關系，提出的方法在第一次啟動程序時將鄰近關系圖存儲在圖數(shù)據(jù)庫中，同時一些中間計算結果也存儲在圖數(shù)據(jù)庫中。因此，冷啟動后的執(zhí)行效率得到大大提升。

（3）利用圖數(shù)據(jù)庫的優(yōu)勢，提出一種基本的子圖（團）查找算法CliqueSearch 和一種基于參與實例驗證的方法InstanceVerification 統(tǒng)計模式的參與實例。其中，為了減小搜索空間提高挖掘效率，設計了候選模式的粗過濾方法和表實例的細過濾方法以及實例的過濾與驗證方法。挖掘算法本質上是迭代的過程，即由上一階頻繁模式生成下一階的候選模式，并且生成的所有候選模式都遵循先驗原理。

（4）為了方便比較，將挖掘頻繁并置模式的經(jīng)典算法Join-based 算法、Join-less 算法和最新提出的Fraction-Score 算法移植到了圖數(shù)據(jù)庫上，分別記為GDBJoinBased、GDBJoinLess和GDBFracScore。

（5）在真實數(shù)據(jù)集和模擬數(shù)據(jù)集上進行了廣泛的實驗評估，結果證明了提出的挖掘算法的正確性和有效性。

1 相關工作

Koperski和Han討論了基于空間鄰近關系的空間關聯(lián)規(guī)則挖掘問題。這項工作挖掘與特定參考特征（例如癌癥的發(fā)病率）相關聯(lián)的空間特征子集。首先根據(jù)參考的實例計算出事務，然后使用先驗算法求關聯(lián)規(guī)則。Shekhar 和Huang提出了空間并置模式挖掘問題，并設計了Join-based 算法挖掘空間頻繁并置模式。為了解決Join-based 連接操作開銷大的問題，Yoo 等人提出了Partial-join 算法和Join-less算法。Partial-join 算法通過團劃分模型物化空間鄰近關系，基于團鄰近直接得到表實例，并掃描數(shù)據(jù)集獲得被團切斷的頻繁并置模式實例。該方法適合處理大部分空間鄰近關系都在團分區(qū)內，而很少的空間鄰近關系在團分區(qū)之間的數(shù)據(jù)集。Join-less 方法將空間鄰近關系物化為星型鄰居列表，然后表實例的生成使用實例查找的方式來代替連接操作。Wang等人提出了星型鄰居存儲結構CPI-tree，基于CPItree 所有表實例能夠快速生成，但是隨著輸入的數(shù)據(jù)量變大，存儲和遞歸搜索CPI-tree將是挑戰(zhàn)性任務。

文獻[1,14-16]采用基于MapReduce 的方法挖掘頻繁并置模式，這些方法通過Hadoop 或者Spark 來搭建分布式并行計算平臺，能高效地處理大數(shù)據(jù)，但是這些算法需要多個主機結點來向上擴展，帶來的經(jīng)濟成本十分昂貴，并且它們的Reducer 結點存在著聚集同一頻繁并置模式所有實例的瓶頸，時間和空間開銷較大。Sainju 等人提出了一種基于網(wǎng)格的GPU 頻繁并置模式挖掘算法，該算法當每個實例的鄰居數(shù)在非常小的常數(shù)范圍內或者當實例密集且分布不均勻時有較好性能，但是實例分布較為均勻時性能提升較小，且利用網(wǎng)格劃分實例割斷了一些重要的模式。

另外還有一些工作，Yoo 等人提出了極大頻繁并置模式、閉頻繁并置模式挖掘算法。Bao 等人提出了基于團的方法挖掘頻繁并置模式，該方法不用查找模式的表實例，尤其在密集數(shù)據(jù)集上有更好的性能表現(xiàn)。Xiao 等人提出了一種基于密度的方法，該方法定義了密度比來描述鄰近關系，并使用聚類技術來尋找頻繁并置模式。Yao 等人提出了一種混合密度加權距離閾值的頻繁并置模式挖掘算法，該算法考慮了密度加權和距離衰減效應，但是沒有考慮實例的空間方位和網(wǎng)絡效應的影響并且確定修正系數(shù)需要花費更多的計算時間。Chan 等人提出了一種新的支持度量方法度量并置模式的頻繁性，稱為Fraction-Score，它考慮了所有可能的行實例，同時避免了實例的重復計數(shù)的問題，但計算得到的候選模式支持度較小，當頻繁度閾值設置不合理時，發(fā)現(xiàn)的模式數(shù)量少，容易丟失重要信息。文獻[24-26]提出了挖掘局部或區(qū)域空間頻繁并置模式，這些模式的實例通常位于整個空間的子區(qū)域中，這些方法考慮了并置模式的局部頻繁性。文獻[27]探索了負并置模式的向上包含性質，提出了極小負并置模式新概念。文獻[28]利用統(tǒng)計學的方法估計表征區(qū)域密度的距離截斷參數(shù)，省去了用戶預先設定距離閾值的過程，有效提高了并置模式挖掘在未知區(qū)域上執(zhí)行的自適應性。Liu 等人提出一種基于自然鄰域的空間并置模式挖掘方法，該方法能在空間要素分布不均勻的場景中有效地發(fā)現(xiàn)并置模式。文獻[30]提出主導特征并置模式的概念，揭示了空間特征間的主導關系，通過這種主導關系能挖掘更有價值的并置模式。

與上述空間頻繁并置模式挖掘的研究相比，本文將輸入的空間數(shù)據(jù)一次性物化為鄰近關系圖（neighborhood graph）存儲在圖數(shù)據(jù)庫中，改變了傳統(tǒng)將鄰近關系存儲在內存中的方法，設計了簡潔而高效的基于圖數(shù)據(jù)庫的子圖查找算法來挖掘頻繁并置模式，并設計了有效的剪枝過濾方法。此外，傳統(tǒng)的基于物化鄰近關系查找表實例的方法（如Join-less算法），都可以通過本文構造鄰近關系圖的方法進行有效的移植。

2 基本概念及問題定義

2.1 空間頻繁并置模式

（空間并置模式）空間并置模式是一組空間特征的集合={,,…,f}∈,2 ≤≤?？臻g并置模式中特征的個數(shù)稱為并置模式的階，記為()=||。例如，({,,})=|{,,}|=3。

（空間并置模式實例）給定不同空間特征的實例集合={,,…,o}∈和空間并置模式。如果同時滿足以下條件：包含了中所有實例的特征，中任意兩個實例滿足鄰近關系，則稱為的一個實例?？臻g并置模式實例也稱為團（Clique）實例或行實例。所有的行實例的集合稱為的表實例，記作_()。的表實例中，特征f∈對應不重疊的實例集合稱為的參與實例，記作_()。

如圖1 所示，={,,} 是一個并置模式，={.1,.1,.2}為的一個行實例，的表實例_()={{.2,.1,.2},{.4,.1,.1}}。_()={{.2,.4},{.1},{.1,.2}}。

（頻繁并置模式）為了衡量并置模式的頻繁性（有趣程度），在頻繁并置模式挖掘中經(jīng)常使用的度量方式是參與度（participation index，），然而的取值取決于參與率（participation ratio，）。

給定最小頻繁性閾值_，如果()不小于_，即()≥_，則稱為頻繁并置模式。

（空間并置模式的反單調性）參與率和參與度隨著并置模式階的增大而單調遞減。

參與率和參與度的反單調性證明可以參看文獻[5]。

（空間并置模式實例的反單調性）并置模式的行實例數(shù)隨著模式階的增大而單調遞減。

假設是空間并置模式的行實例，即滿足鄰近關系形成團，對于的任意子集′∈也滿足鄰近關系形成團，即的子集一定是子集對應的并置模式的行實例，反之不成立。因此并置模式的表實例條數(shù)隨著模式的階增大而單調遞減。

2.2 問題定義

給定：

（1）空間特征集合={,,…,f}。

（3）空間鄰近關系和頻繁性閾值_。

約束：基于距離度量的鄰近關系，具有對稱性質。

挖掘結果：找到滿足頻繁性閾值的所有空間頻繁并置模式。

目標：減少鄰近關系的重復計算和對內存的大量占用，利用較少的時間正確并且完整地找到所有頻繁并置模式。

3 相關算法

本章給出了基于圖數(shù)據(jù)庫的頻繁并置模式挖掘框架及相關算法，包括鄰近關系圖的構造算法和兩種頻繁并置模式挖掘算法CliqueSearch和InstanceValidation。

3.1 挖掘框架

基于圖數(shù)據(jù)庫的挖掘框架如圖2 所示，在第一次程序啟動時，計算鄰近關系并存儲在圖數(shù)據(jù)庫中，然后基于構造好的鄰近關系圖挖掘頻繁模式。在挖掘過程中，使用索引技術提高查詢效率，進而提高挖掘算法效率。該框架的重點是減少鄰近關系的重復計算，通過索引技術高效地搜索空間并置模式實例并進行有效的過濾，從而獲得頻繁并置模式。

圖2 提出的挖掘框架Fig.2 Proposed mining framework

3.2 相關算法

（鄰近關系圖（neighborhood graph））鄰近關系圖=(,)，其中中的每個結點都是中實例，中的每條邊是中特征不同的結點對，并且=(o,o)為邊的屬性。

鄰近關系圖構造包括結點和邊的創(chuàng)建，其中邊創(chuàng)建利用線性掃描的方法，具體步驟如下：

結點的創(chuàng)建和插入。首先需要遍歷空間實例集創(chuàng)建結點v并插入到中。例如，實例＜,1,(x,y)＞的結點表示為{:,:1,:(x,y)}。

構造鄰近關系圖

考慮圖1 的空間數(shù)據(jù)分布，假設實例.1 的空間位置是(3,8)，實例.1 的空間位置是(4,7)，通過方法將這兩個實例分別創(chuàng)建為結點{,1,＜3,8 ＞}和結點{,1,(4,7)}并插入到結點集合中；方法創(chuàng)建結點之間的邊，計算鄰近距離=(.1,.1)，創(chuàng)建.1 和.1 的邊為＜＜,＞,＞。如圖3 所示為一個鄰近關系圖，任意兩個特征不同的結點之間都存在一條邊。

圖3 一個鄰近關系圖Fig.3 Neighborhood relationship graph

本文挖掘頻繁并置模式的核心思想是按照模式的階，從小到大地進行模式頻繁性驗證。假設特征實例集合是有序的，如按特征名稱+實例編號的字典序升序排列。候選模式的生成是迭代的過程，1 階頻繁模式用特征集進行初始化，(＞1)階候選模式由其-1 階均為頻繁的模式生成（引理1）。模式表實例就是查找出鄰近關系圖中跟候選模式相關的滿足鄰近關系的所有團，然后根據(jù)定義4 來計算候選模式的頻繁度。提出了兩種算法計算候選模式的頻繁度，分別是CliqueSearch 和InstanceValidation。

CliqueSearch 算法包括兩個核心的步驟：查找與候選模式中特征相關的所有路徑和路徑檢查。在路徑查找步驟中使用索引技術提高查找效率，同時對查詢到的路徑進行過濾。過濾分為粗過濾和細過濾兩個子步驟。在粗過濾步驟，如果候選模式的粗行實例的頻繁度小于給定的閾值_，該候選模式一定不是頻繁并置模式，將其剪枝；否則進入細過濾步驟，即判斷路徑中任意兩個結點是否都滿足鄰近關系（任意兩個結點之間都存在邊），如果“是”保留該路徑，否則將該路徑剪枝。經(jīng)過細過濾步驟后留下的路徑一定都是并置模式的行實例。最后計算實際的頻繁度，如果不小于給定的閾值，則該模式為頻繁模式。

InstanceValidation 算法最大的優(yōu)點是不用收集和存儲候選模式的所有行實例，搜索空間小，中間操作步驟少。其核心思想就是根據(jù)中心實例的鄰居集，判斷該中心實例是否涉及到候選模式的一條行實例中，如果找到這樣的一條行實例，就將該中心實例進行參與標記，并停止搜索其他涉及到該中心實例的行實例。判斷中心實例是否涉及到模式的某條行實例，包括過濾和驗證兩個步驟。過濾步驟判斷中心實例的鄰居集是否包含了候選模式的所有特征，如果“是”則進行驗證步驟，否則該候選模式一定不存在一條行實例涉及此中心實例，剪枝。驗證步驟是搜索一條涉及到中心實例的行實例，即在中心實例的鄰居集中找到一個任意兩個實例都滿足鄰近關系的團，如果找到，標記中心實例為模式的參與實例。在完成模式中一個特征的所有實例的過濾和驗證步驟后，計算該特征的參與率，如果小于給定閾值_，則停止模式中剩余特征的過濾和驗證操作，并將該候選模式剪枝（根據(jù)定義3，候選模式中任意一個特征的參與率小于給定閾值，那么該候選一定是非頻繁模式）。算法2 和算法3 分別給出了CliqueSearch 和InstanceValidation 算法的偽代碼。

CliqueSearch

算法2 解釋如下：

第3 行生成候選模式。根據(jù)參與度的定義可知，所有一階模式都是頻繁的。生成(＞1)階候選模式是通過-1 階頻繁模式集合中任意兩個組合生成，如果組合生成的候選模式的階數(shù)值為，則判斷該模式的所有-1 階子集是否都頻繁，如果“是”保留該候選模式，否則舍棄。

第5 行根據(jù)候選模式到鄰近關系圖中查找出所有與候選模式特征相關的候選路徑。首先需要根據(jù)候選模式構造出查詢語句，如圖4（c），存在候選模式{,,}，路徑查詢 語句構造為“-[:＜,＞]--[:＜,＞]-”。查詢圖將返回與模式{,,}相關的所有滿足鄰近關系的路徑。第7 行，如果模式為2 階直接計算頻繁度，判斷其是否為頻繁模式。

第9 行對候選表實例進行粗過濾，如果不滿足最小頻繁度閾值，則無需進行后續(xù)步驟的計算，將該模式剪枝；否則執(zhí)行第10～12 行，候選路徑細過濾，即判斷路徑中任意兩個結點是否滿足鄰近關系，如果“否”，將該路徑剪枝。路徑細過濾步驟通過引入哈希表來檢查(＞1)階行實例。哈希表中的每個元素是鍵值對結構的對象，鍵為-1 階團，值為階團中第個結點。在檢查的過程中，首先對候選路徑進行哈希轉換，鍵為路徑中前-2(＞2)個結點，值為路徑中后兩個結點，判斷值中的兩個結點是否都能夠在哈希表中查找到，如果不能找到或只能找到其中一個則將該候選團剪枝；如果兩個結點都能夠在哈希表中查找到，則檢查它們之間邊的距離是否不超過距離閾值，否則將其剪枝。這種檢查過濾方法只需對鄰近關系圖查詢一次。如圖4（c）檢查模式{,,} 的路徑{.1,.1,.1} 和{.2,.1,.1} 是否構成團，首先進行哈希轉換，對應的鍵值對分別是{:{.1},:{.1,.1}} 和{:{.2},:{.1,.1}}，查找2 階哈希表發(fā)現(xiàn)路徑{.2,.1,.1} 的在({.2})中只出現(xiàn).1，將其剪枝；而{.1,.1,.1}的在({.1})中均出現(xiàn)，因此檢查.1 和.1的鄰近關系，通過查詢鄰近關系圖發(fā)現(xiàn)它們滿足鄰近關系，故保留為候選團。

脫離臨床工作也是部分護理學博士研究生的入學動機。目前，在醫(yī)院從事臨床護理工作的護士工作負荷重、職業(yè)風險大、社會地位低、醫(yī)護關系不平等[9]，醫(yī)院對護士人力資源的分級管理不完善[10]，有的醫(yī)院領導認為不管護士是什么學歷，都應從臨床一線做起[11]，這使得護理學博士研究生擔心到醫(yī)院工作沒有時間和精力進行科研，醫(yī)院沒有合適崗位能使他們兼顧臨床護理工作和科研工作而埋沒自己的專長，不能運用所學而對醫(yī)院望而卻步，從而青睞高校教師崗位。

圖4 基于圖數(shù)據(jù)庫的頻繁并置模式挖掘過程示例Fig.4 Example of prevalent co-location pattern mining process based on graph database

第15～17 行，如果該并置模式頻繁，則將其所有表實例轉化為鍵值對保存到哈希表中，用于下一次的迭代檢查。如{,,}為一個頻繁模式，那么將其表實例轉為鍵值對保存到3 階的哈希表中，{{:{.1,.1},:{.1}},{:{.3,.1},:{.1}}}。

InstanceValidation

算法3 解釋如下：

第3 行生成候選模式，方法同算法2 所述。第4～18 行判斷候選模式是否為頻繁模式。其中，第8～10行，判斷特征每個實例是否涉及到候選模式的某個行實例中，如果存在一個行實例包含的實例，那么標記該實例為候選模式的一個參與實例。第9 行在實例的參與過濾與驗證的步驟中可以采用空間特征查詢法和枚舉法。在本文中采用枚舉法，因為枚舉法能夠確保完整地驗證所有實例的參與情況并且實現(xiàn)簡便?？臻g特征查詢法的實現(xiàn)較為復雜，且空間特征查詢是一個NP 問題，具有較大時間復雜度。在過濾階段，首先判斷模式的所有特征是否都在以實例為中心的鄰居實例集中出現(xiàn)，如果“是”進行驗證，否則進行下一個實例的過濾驗證操作。如圖4（d）所示，在進行候選模式{,,}的參與實例統(tǒng)計時，.1 的鄰居實例集中同時包含了特征和，則進入該實例的驗證步驟；同樣的，.2 的鄰居實例集中只包含特征，那么一定不存在{,,}的一個行實例涉及.2，調過實例驗證階段，直接進行.3 的過濾和驗證。在驗證階段，搜索涉及該實例的一個行實例，如果搜索到這樣的一個行實例，將實例標記為模式的一個參與實例，結束本次操作并進行下一個實例的過濾驗證操作。如圖4（d）中搜索到.1 涉及的一條行實例{.1,.1,.1}，則對.1 進行參與標記。第11 行，完成模式中一個特征所有實例的過濾和驗證操作后，計算該特征實例的參與率，如果小于給定閾值，則停止中其他特征的過濾和驗證操作，并根據(jù)定義3 將剪枝。()不小于頻繁閾值_，則進行特征的參與統(tǒng)計，否則將候選模式{,,}剪枝。采用實例驗證的方法可以看出，在整個模式實例參與數(shù)的統(tǒng)計中沒有行實例的存儲并且不用計算所有的行實例，搜索空間小。

3.3 計算復雜度分析

（1）算法的時間復雜度分析。假設空間數(shù)據(jù)集有個實例，對應的空間特征集有個空間特征，每個特征f∈,1 ≤≤對應的實例最多有個，階頻繁并置模式最多有個，為實例o∈,1 ≤≤的特征，候選模式的候選實例個數(shù)最大為。中心實例o的鄰居實例中每個特征的實例數(shù)最大為，其中?。

表實例的收集通過候選模式查詢鄰近關系圖數(shù)據(jù)庫，每個候選模式粗表實例的收集需要的最大時間復雜度為(s)，每個模式查詢得到的粗行實例個數(shù)為，第一次過濾需要的時間為()。

對于算法2，引入哈希表來檢查階模式實例。檢查一個階候選團所需要的查詢次數(shù)為一次哈希表和一次鄰近關系圖查詢，總共需要兩次查詢，檢查完一個模式的所有實例需要的操作次數(shù)為2×。頻繁度的計算需要的執(zhí)行次數(shù)為×+，其中特征實例的參與統(tǒng)計操作次數(shù)為×，完成模式中每個特征的參與率計算需要的操作次數(shù)為。有個階候選模式完成頻繁度計算，算法2 需要的最大執(zhí)行次數(shù)是×[2+(×+)]。

對于算法3 在過濾步驟，完成對一個中心實例鄰居的過濾需要的最大執(zhí)行次數(shù)是(-1)×；在驗證步驟，判斷是否存在一條行實例包含中心實例，需要的最大搜索次數(shù)為l。完成一個候選模式的參與實例統(tǒng)計需要的最大執(zhí)行次數(shù)為×[(-1)×+l] 。完成第階頻繁模式選擇需要的最大執(zhí)行次數(shù)為××[(-1)×+l]。

算法2 和算法3 經(jīng)過次迭代的最大執(zhí)行次數(shù)分別為××[2×+(×+)+s]和×××[(-1)×+l]，因此最大時間復雜度分別為(××s) 和(×××l)且(××s)＞(×××l)。

（2）算法的空間復雜度分析。算法1 構造的鄰居圖的空間復雜度為(||)≤()。每次迭代生成階候選模式數(shù)量為=|C|，該步驟的空間復雜度為()。算法2 每個候選模式的最大行實例數(shù)為，每次迭代的哈希表最大空間占用為，因此算法2 的空間復雜度為(2×)。算法3 無表實例生成，每次保存的是每個特征的參與實例數(shù)，空間復雜度為(1)。

3.4 完整性和正確性分析

所提出的算法能完整和正確地發(fā)現(xiàn)空間頻繁并置模式。

（1）完整性。完整性意味著算法能夠發(fā)現(xiàn)所有的空間并置模式。下面分別證明算法1～算法3 的完整性。對于算法1，構造鄰近關系圖第一次線性掃描完成后，所有實例被構造為圖的結點，沒有實例丟失。構造出來的鄰近關系圖任意兩個不同特征的實例結點之間都有一條邊，在構造的過程中沒有邊丟失，因此構造出來的鄰近關系圖是完整的。對于算法2，第一步，生成候選模式的方法根據(jù)引理1 是正確的，沒有+1 階候選模式丟失。第二步，通過候選模式收集表實例和進行第一次過濾（粗過濾）是正確的，因為過濾掉的候選模式頻繁度小于用戶給定的最小頻繁度閾值。第三步，定義2 和鄰近關系確保了形成的模式實例是正確的，并且在團的檢查中沒有對候選模式實例誤判而影響參與度的準確度。第四步，候選模式頻繁度計算根據(jù)定義3 是正確的且被剪枝候選模式的真正頻繁度小于用戶給定的頻繁閾值。對于算法3，統(tǒng)計一個模式的參與實例，分為過濾和驗證兩個步驟。在過濾步驟，判斷每個中心實例鄰居集所構成的團中是否包含了候選模式中所有的特征，根據(jù)定義1 和定義2 可知該步驟是正確的。在驗證步驟，搜索一條包含中心實例的行實例，如果找到這樣的行實例，則將中心實例標記為參與實例，在此過程中沒有錯誤的標記模式參與實例，根據(jù)定義2 可證明該步驟的正確性。完成候選模式中一個特征的參與實例統(tǒng)計后，計算參與率根據(jù)定義3是正確的，同時利用剪枝來縮小搜索空間根據(jù)引理2 是正確的，因此沒有頻繁模式丟失和錯誤地選擇非頻繁模式。

（2）正確性。正確性意味著發(fā)現(xiàn)的所有空間并置模式都是頻繁的。算法的正確性是通過過濾步驟和頻繁度計算步驟來保證的。因為算法具有完整性，沒有任何候選模式和候選模式實例的丟失，所計算的頻繁度也是正確的，所以得到的頻繁模式一定滿足用戶給定的頻繁閾值。

4 實驗與分析

首先，為了更好地進行算法的對比與分析，將已有的挖掘算法Fraction-Score、Join-based和Joinless移植到了圖數(shù)據(jù)庫上，分別記為GDBFracScore、GDBJoinbased 和GDBJoinless。然后，收集了真實數(shù)據(jù)集并進行數(shù)據(jù)清洗。最后，為了驗證提出算法的效果和效率，分別在真實數(shù)據(jù)集和合成數(shù)據(jù)集上開展了不同維度的對比實驗。此外，利用合成數(shù)據(jù)比較了基于圖數(shù)據(jù)庫和基于內存物化鄰近關系對算法的執(zhí)行時間和空間占用的影響。實驗所用圖數(shù)據(jù)庫為Neo4j，所有算法都采用Java 語言實現(xiàn)，實驗環(huán)境為Win10，Core i5 GPU、240 GB固態(tài)硬盤和16 GB內存。

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

實驗數(shù)據(jù)集的相關信息如表1 所示。其中真實數(shù)據(jù)集1 是商業(yè)數(shù)據(jù)集，它是Yelp 數(shù)據(jù)集（https://www.yelp.com/dataset）的一部分。Yelp 數(shù)據(jù)集是一個公共數(shù)據(jù)集，包括美國許多城市的業(yè)務類別、屬性和位置。真實數(shù)據(jù)集2 是北京植被數(shù)據(jù)，包括26 種植被類型（特征）和25 276株植被實例。真實數(shù)據(jù)集3是北京POI 數(shù)據(jù)，包括56 種POI 類型（特征）和207 198個POI（實例）。

表1 真實數(shù)據(jù)集說明Table 1 Description of real datasets

本文使用類似文獻[3-4]中所提出的空間數(shù)據(jù)生成器來生成合成數(shù)據(jù)集?？臻g實例的分布密度和范圍，由×的空間和決定，為空間邊長。整個空間劃分為×大小的網(wǎng)格，是鄰近距離閾值。特征的密度由特征數(shù)決定。數(shù)據(jù)的分布滿足泊松分布。表2 為合成數(shù)據(jù)生成器的幾個重要參數(shù)說明。

表2 合成數(shù)據(jù)參數(shù)說明Table 2 Description of synthetic data parameters

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

為了評估不同的參數(shù)設置對挖掘算法效率的影響，將本文提出算法CliqueSearch、InstanceValidation和基準算法GDBJoinbased、GDBJoinless、GDBFracScore分別在3 種真實數(shù)據(jù)集上進行實驗。各個數(shù)據(jù)集的默認參數(shù)設置如表3 所示。

表3 真實數(shù)據(jù)集默認參數(shù)Table 3 Default parameters of real datasets

在3種真實數(shù)據(jù)集上，5種算法在不同距離閾值和不同頻繁度閾值的運行時間如圖5所示。當距離閾值增加，Join-based、Join-less和CliqueSearch算法的執(zhí)行時間增加最明顯；Fraction-Score方法和InstanceValidation算法的執(zhí)行時間趨于穩(wěn)定。提出的兩個算法執(zhí)行時間優(yōu)于傳統(tǒng)的方法和最新的技術，其中InstanceValidation算法的表現(xiàn)優(yōu)于CliqueSearch。Fraction-Score 算法執(zhí)行時間較Join-based 和Join-less 少，主要原因是所采用的頻繁性度量方法不同，F(xiàn)raction-Score 所用的度量方式先計算出每個特征對實例的貢獻分數(shù)，然后通過特征分數(shù)累加的方式求并置模式的頻繁度，不用收集表實例，因此時間開銷較經(jīng)典方法少。提出的方法挖掘出來的結果跟Join-based 和Join-less 方法一致，并且在時間開銷上更少。同樣地，由圖5 可以看出，隨著頻繁度閾值的增加，執(zhí)行時間都在減少。其中，在傳統(tǒng)方法和最新技術的表現(xiàn)中，F(xiàn)raction-Score 方法仍然優(yōu)于Join-based 和Join-less 方法，這是因為Fraction-Score 方法的優(yōu)化剪枝效率很高，每次減去的模式更多。提出的兩個算法的表現(xiàn)仍然是最優(yōu)的，因為在團的查找中，直接過濾了與模式無關的特征，只需檢查團；而Join-less 方法在過濾與模式特征相關的實例時，需要遍歷中心實例的所有星型鄰居，然后利用組合的方法生成所有候選團，因此時間開銷大。從表1 可知，真實數(shù)據(jù)集1 有80 個特征，屬于特征密集型數(shù)據(jù)集，但實例密度較小。特征越密集，生成的2 階候選模式越多，對于Join-based 方法，表實例的連接次數(shù)越多，時間開銷增加。Join-less 和Fraction-Score 方法的過濾步驟能更快對非頻繁候選模式剪枝，但是Fraction-Score 需要通過組合搜索判斷候選模式是否存在一個實例，Join-less 方法要通過組合的方式收集表實例，比較耗時。提出的方法，基于圖數(shù)據(jù)庫查詢團可以直接過濾非頻繁模式，中間操作次數(shù)少，并且InstanceValidation 算法采用中心實例過濾與驗證的方法不用存儲表實例，直接對參與實例進行標記計數(shù)，因此時間開銷更少。真實數(shù)據(jù)集3 實例數(shù)最多并且實例和特征密度較大。根據(jù)實驗結果可以看出特征密集或者實例密集對Join-based方法都產(chǎn)生較大的影響，而Join-less 和CliqueSearch方式次之，F(xiàn)raction-Score 和InstanceValidation 受到特征數(shù)量影響最小。如表4 所示，在3 個真實數(shù)據(jù)集上，根據(jù)默認參數(shù)對算法的時間效率加速比進行了計算。因為基準算法中GDBFracScore 算法的表現(xiàn)最優(yōu)，所以提出的CliqueSearch 和InstanceValidation 僅與該算法的執(zhí)行時間進行計算。從表中可以看出，算法2 的時間效率提升了至少7 倍，算法3 至少提升了11.5 倍，其中算法3 較算法2 執(zhí)行時間效率至少提升了1.6 倍。綜上，提出的兩個算法在不同大小和分布的實際數(shù)據(jù)集上都表現(xiàn)出了良好的性能。

圖5 真實數(shù)據(jù)集上不同參數(shù)對執(zhí)行時間的影響Fig.5 Effect of different parameters on running time on real datasets

表4 提出算法與基準的執(zhí)行時間和加速比Table 4 Execution time and speed-up ratio of proposed algorithm and benchmark

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

為了研究實例數(shù)目對算法運行時間的影響，利用合成數(shù)據(jù)（合成數(shù)據(jù)集1～5）來進行實驗，實例數(shù)量()分別取值2.4×10、2.8×10、3.2×10、3.6×10和4.0×10，數(shù)據(jù)分布空間大小為50 000×50 000，空間特征個數(shù)為40。5 種合成數(shù)據(jù)集的默認距離閾值設置為200 m，頻繁度閾值設置為0.1。

如圖6（a）所示，隨著實例數(shù)增加，在相同的空間分布下，數(shù)據(jù)的密度變大，執(zhí)行時間增加，提出的算法效率要遠高于基準。因為隨著實例數(shù)的增多，實例之間的鄰近關系增多，形成的行實例增多，Joinbased 方法需要進行的表連接操作也增多，需要的時間開銷也就越大。同樣地，隨著鄰近關系的增加，Join-less 方法過濾得到的鄰居就越多，組合生成表實例需要的時間就越長。Fraction-Score 方法搜索判定是否為模式實例的操作次數(shù)變多，時間開銷增加。CliqueSearch 方法在表實例的查找中，沒有連接操作也不用進行組合搜索操作，而InstanceValidation 方法不收集表實例，當實例數(shù)取值為4×10時，CliqueSearch算法的執(zhí)行時間只需Fraction-Score 方法的28%，而InstanceValidation算法只需其16%，可以看出時間開銷遠小于基準，有更好的執(zhí)行表現(xiàn)。圖6（b）對本文所提的兩個算法進行了比較，可以看出InstanceValidation算法的表現(xiàn)始終優(yōu)于CliqueSearch。InstanceValidation算法采用實例過濾和驗證的方法，統(tǒng)計一個候選模式的參與實例，不生成表實例，內存開銷小。而CliqueSearch算法在選擇頻繁模式時，需要收集候選模式的所有表實例并且將-1階頻繁模式的每條實例轉為鍵值對存儲在哈希表中用于階候選團（粗表實例）的檢查，內存開銷較大。當實例數(shù)增大到4×10時，CliqueSearch算法的內存使用為InstanceValidation算法的4.6 倍。

本小節(jié)通過實驗比較不同特征數(shù)對算法運行時間的影響。數(shù)據(jù)的空間分布設置為50 000×50 000，實例個數(shù)設置為1×10，空間特征數(shù)分別取值為30、50、70、90、110。默認距離閾值為200 m，頻繁閾值為0.2。

如圖6（c）所示，當空間特征數(shù)為30 時，5 種算法之間有較大的執(zhí)行時間差距，特征數(shù)增加到50 執(zhí)行時間也增加，是因為特征數(shù)增多生成的候選模式增多，對于Join-based 方法，表的連接操作次數(shù)增多，因此時間增加；而對于Join-less 和Fraction-Score 方法，盡管沒有大量的表實例的連接操作，但是組合搜索方法中組合操作的次數(shù)同樣增多，執(zhí)行時間增加。當空間特征數(shù)目增加到70、90 和110 時，盡管候選并置模式數(shù)目在增多，但算法的執(zhí)行時間都在減少，因為在實例總數(shù)不變的情況下，隨著特征數(shù)繼續(xù)增加，每個特征對應的實例數(shù)在減少，因此模式的行實例數(shù)目也在減少。對于Join-less 方法，表實例的連接操作次數(shù)減少，收集到的表實例數(shù)也減少；而Fraction-Score 方法的組合操作次數(shù)減少，因此執(zhí)行時間減少。同樣地，提出的CliqueSearch 方法在特征數(shù)少的情況下，特征實例密集，收集到的模式實例更多，過濾需要的時間更多，因此需要的頻繁模式計算耗時也多。特征實例稀疏時，收集到的模式實例更少，頻繁模式計算耗時也在減少；InstanceValidation 方法，隨著特征數(shù)目增加，時間開銷有一定的增加但是受到的影響較小，整體表現(xiàn)趨于穩(wěn)定?？傮w上，提出的算法在執(zhí)行的時間效率表現(xiàn)上優(yōu)于移植到圖數(shù)據(jù)庫上的經(jīng)典算法和最新技術。

圖6 合成數(shù)據(jù)集上不同參數(shù)對算法運行時間的影響Fig.6 Effect of different parameters on running time of algorithms on synthetic datasets

在本次實驗中研究鄰域內模式實例數(shù)量（參數(shù)的變化）對算法執(zhí)行的影響。數(shù)據(jù)的空間分布設置為50 000×50 000，實例個數(shù)設置為9×10，空間特征數(shù)取值為30，距離閾值設置為200 m，頻繁度閾值設置為0.2，參數(shù)的取值范圍為1、2、3、4、5。

由圖6（d）可以看出，隨著取值增大，算法的執(zhí)行時間都在增加，這是因為隨著的增大，并置模式數(shù)量在增加。Join-based、Join-less 和CliqueSearch 方法收集表實例的中間操作次數(shù)增多；而Fraction-Score 方法計算模式分數(shù)評分需要的組合搜索操作次數(shù)同樣增多，時間開銷增加。對于InstanceValidation 方法，鄰域內模式數(shù)量增多導致了中心實例需要執(zhí)行的過濾與驗證操作次數(shù)增加，從而時間開銷增加，但它表現(xiàn)仍然是幾種方法中表現(xiàn)最優(yōu)的且具有一定的穩(wěn)定性。

在合成數(shù)據(jù)上改變重疊實例比（）的實驗結果，如圖6（e）所示。數(shù)據(jù)的空間分布設置為25 000×25 000，實例個數(shù)設置為5×10，空間特征數(shù)取值為30，距離閾值設置為800 m，頻繁度閾值設置為0.2，取值設置為2，重疊實例比的取值范圍為5、10、15、20、25。隨著特征的重疊實例比增大，算法的執(zhí)行時間都在增加。因為收集表實例的方法中間計算步驟增多，所以時間開銷增加。例如一個中心實例周圍是特征相同的幾個實例，那么中心實例在表實例收集的過程中將被重復連接或者組合。在5 種方法中，實例的過濾和驗證方法的表現(xiàn)最優(yōu)并且更加穩(wěn)定。算法的剪枝率實驗結果如圖6（f）所示。當重疊實例比增大，算法的剪枝率都在增加，其中本文提出的兩種算法在剪枝率上有較好的表現(xiàn)，InstanceValidation算法剪枝率均高于80%，CliqueSearch算法保持在70%以上，并且提出的算法剪枝率都較基準高。因為隨著重疊率的增加，重疊實例的特征參與率降低，候選模式的剪枝機會增大（剪枝率為非頻繁模式總數(shù)與候選模式總數(shù)之比）。

4.4 基于圖數(shù)據(jù)庫和基于內存物化鄰近關系的實驗與分析

從真實數(shù)據(jù)集和合成數(shù)據(jù)集上的實驗可以看出，F(xiàn)raction-Score 在基準算法中的執(zhí)行表現(xiàn)最優(yōu)。因此本節(jié)在合成數(shù)據(jù)集上將提出的算法與Fraction-Score算法分別利用內存和圖數(shù)據(jù)庫物化鄰近關系在執(zhí)行時間和空間占用上進行比較。數(shù)據(jù)空間分布大小為40 000×40 000，實例個數(shù)為6×10，空間特征數(shù)為30。參與度閾值設置為0.3，和設置為1。距離閾值的變化范圍是100 m、120 m、140 m、160 m、180 m。Fraction-Score方法利用圖數(shù)據(jù)集庫和內存物化鄰近關系的執(zhí)行時間比較如圖7（a）所示。隨著距離閾值增大執(zhí)行時間都在增加，因為當距離閾值較小時，中心實例的鄰近關系少，搜索空間??；當距離閾值變大時，鄰近關系增多，搜索空間增大，時間開銷增加。當距離閾值較小時，基于內存的方法執(zhí)行時間少于基于圖數(shù)據(jù)庫的方法，但是當距離閾值變大時，基于內存的方法時間開銷迅速增加且超過了移植到圖數(shù)據(jù)庫的方法，原因是基于內存方法計算鄰近關系需要的時間開銷增大，而移植到圖數(shù)據(jù)庫的方法只需要對鄰近關系圖進行查詢而不用每次啟動程序重新計算。提出的兩種挖掘方法時間表現(xiàn)優(yōu)于最新技術的兩種實現(xiàn)方式。當距離閾值取值為180 m時，GDBFracScore、CliqueSearch 和InstanceValidation算法相對于MemFracScore 算法的時間效率提升倍數(shù)分別為2.2、3.6 和9.3。

算法執(zhí)行的內存使用如圖7（b）所示，隨著距離閾值增大，CliqueSearch 和Fraction-Score 利用內存物化鄰近關系方法的內存消耗都在增加，其中Fraction-Score 方法的內存消耗最多，因為Fraction-Score 方法隨著距離閾值增加鄰近關系增多，導致內存使用增加。CliqueSearch 方法的內存增加，因為查詢到的模式實例數(shù)增多，即收集到的表實例增多。Fraction-Score 移植到圖數(shù)據(jù)庫上的方法的內存使用趨于穩(wěn)定，因為鄰近關系不用存儲在內存中，需要存儲的是每個空間特征對每個實例的評分，當實例數(shù)不變時內存使用大小趨于穩(wěn)定。InstanceValidation 算法執(zhí)行內存消耗最少并且隨著距離閾值增加趨于穩(wěn)定，因為不用收集和保存表實例。隨著距離閾值增大，空間鄰近關系增多，距離閾值取值為180 m 時，基于圖數(shù)據(jù)庫的方法較基于內存物化鄰近關系的方法有著較明顯的優(yōu)勢，GDBFracScore、CliqueSearch 和InstanceValidation算法與基于內存方式實現(xiàn)的Fraction-Score 算法內存占用比分別為1∶4.1、1∶1.7 和1∶6.6，其中InstanceValidation 的內存使用約為CliqueSearch的1/4。CliqueSearch 算法內存使用較GDBFracScore算法高，是因為前者保存表實例占用了大量的內存空間。綜上，可以看出移植到圖數(shù)據(jù)庫上的方法在時間開銷和內存使用上都有較好的表現(xiàn)。

圖7 圖數(shù)據(jù)庫和內存物化鄰近關系的實驗比較Fig.7 Experimental comparison between graph database and memory materialized neighbor relationship

5 結束語

空間頻繁并置模式挖掘是發(fā)現(xiàn)一些先前未知的但是具有重要指導意義的空間知識的重要工具。傳統(tǒng)方法能夠對這些有著重要意義的模式進行挖掘，但當空間數(shù)據(jù)量較大時，存儲空間鄰近關系會占用大量的內存空間，帶來內存不足的問題，并且查找表實例時間開銷很大。圖數(shù)據(jù)庫是當前比較流行的一種非關系型數(shù)據(jù)庫，能方便地以圖的形式表示數(shù)據(jù)和關系，并且提供了管理高度連接的數(shù)據(jù)和復雜的數(shù)據(jù)庫查詢以及原生圖形存儲和處理的能力?？臻g實例之間存在著復雜的鄰近關系，利用圖數(shù)據(jù)庫能夠很好地把這些空間數(shù)據(jù)和它們對應的關系存儲下來，然后挖掘空間頻繁并置模式。根據(jù)圖數(shù)據(jù)庫的優(yōu)點，利用圖數(shù)據(jù)庫來存儲實例的鄰近關系，即構造鄰近關系圖，減少了內存占用。移植到基于圖數(shù)據(jù)庫的經(jīng)典的挖掘算法沒有充分發(fā)揮圖數(shù)據(jù)庫的優(yōu)勢導致效率很低。因此，本文將傳統(tǒng)表實例的生成方法轉變?yōu)榛趫D數(shù)據(jù)庫的團查找方法可以直接獲得與候選模式相關的候選團，而不需要組合或連接操作來生成候選團，減少了時間開銷。此外，本文還提出一種實例過濾和驗證的無表實例收集的新方法，進一步提高了算法的時間效率和空間效率。最后，通過實驗驗證了所提算法的正確性、高效性和可擴展性。

在未來的工作中，計劃進一步應用圖數(shù)據(jù)庫的特性，研究時空數(shù)據(jù)和帶更多屬性的數(shù)據(jù)的空間并置模式挖掘問題。此外，將進一步考慮在挖掘過程中融入應用領域的背景知識，研究基于知識圖譜的空間并置模式挖掘技術。