基于點(diǎn)過程模擬的時空級聯(lián)模式統(tǒng)計(jì)挖掘方法

徐楓，陳袁芳，蔡建南，劉啟亮，鄧敏

?

基于點(diǎn)過程模擬的時空級聯(lián)模式統(tǒng)計(jì)挖掘方法

徐楓，陳袁芳，蔡建南，劉啟亮，鄧敏

(中南大學(xué)地球科學(xué)與信息物理學(xué)院，湖南長沙，410083)

從時空統(tǒng)計(jì)的角度，將時空級聯(lián)模式的頻繁度評價建模為多元獨(dú)立分布零假設(shè)下的顯著性判別問題，提出一種基于點(diǎn)過程模擬的時空級聯(lián)模式統(tǒng)計(jì)挖掘方法。首先，采用時空點(diǎn)過程模擬每類地理要素的觀測數(shù)據(jù)集，構(gòu)建顯著性判別的零模型；其次，通過蒙特卡洛模擬獲取零假設(shè)下每種候選時空級聯(lián)模式頻繁度的實(shí)驗(yàn)分布；最后，對候選模式的觀測頻繁度進(jìn)行顯著性檢驗(yàn)，識別顯著的時空級聯(lián)模式。研究結(jié)果表明：本文方法能夠用于有效識別地理要素間的時空級聯(lián)模式，且避免了挖掘結(jié)果對頻繁度閾值設(shè)置的依賴。

時空數(shù)據(jù)挖掘；時空級聯(lián)模式；時空點(diǎn)過程；顯著性檢驗(yàn)

為了發(fā)現(xiàn)不同地理要素時空分布間的關(guān)聯(lián)關(guān)系，人們對時空關(guān)聯(lián)模式挖掘進(jìn)行了研究[1?2]。時空級聯(lián)模式是時空關(guān)聯(lián)模式的一種重要表現(xiàn)形式，旨在描述不同地理要素頻繁發(fā)生于鄰近空間位置的時間先后順序[3]。挖掘時空級聯(lián)模式對于進(jìn)一步揭示和理解不同地理要素間關(guān)聯(lián)關(guān)系的傳導(dǎo)機(jī)制具有重要價值，現(xiàn)已被廣泛應(yīng)用于公共安全、環(huán)境管理、公共衛(wèi)生等領(lǐng)域[4]。例如，在公共安全領(lǐng)域，發(fā)現(xiàn)不同類型犯罪案件及其影響因素間的誘導(dǎo)機(jī)制，可為犯罪防控提供重要的決策信息[5]。時空關(guān)聯(lián)模式主要包括時空同現(xiàn)模式和時空級聯(lián)模式，前者刻畫不同地理要素間的同現(xiàn)關(guān)系，后者在同現(xiàn)關(guān)系的基礎(chǔ)上進(jìn)一步描述鄰近要素發(fā)生的先后順序。現(xiàn)有時空關(guān)聯(lián)模式挖掘方法大多是在空間關(guān)聯(lián)模式挖掘模型[6?7]的基礎(chǔ)上，通過施加時間鄰近約束和時間次序約束，將地理要素間的關(guān)聯(lián)關(guān)系從空間域擴(kuò)展至?xí)r空域[8]。根據(jù)在挖掘模型中納入時間約束的方式，將現(xiàn)有方法的研究策略大致分為時空分治和時空耦合共2類。時空分治策略將時空數(shù)據(jù)集劃分為若干個時間切片上的空間數(shù)據(jù)集，首先挖掘每個時間切片上頻繁滿足空間鄰近約束的空間關(guān)聯(lián)模式，進(jìn)而統(tǒng)計(jì)每個空間關(guān)聯(lián)模式出現(xiàn)的時間切片個數(shù)，提取頻繁的時空關(guān)聯(lián)模式。例如，CELIK等[9]在每個時間切片上提取空間同現(xiàn)模式，將頻繁出現(xiàn)在多個時間切片上的候選模式定義為時空同現(xiàn)模式。為了發(fā)現(xiàn)時空同現(xiàn)模式的時空演化規(guī)律，CELIK等[10]進(jìn)一步提取了頻繁度隨時間持續(xù)增長的時空同現(xiàn)模式；QIAN等[11]首先識別每個時間片上若干空間子單元中的空間同現(xiàn)模式，進(jìn)而提取同現(xiàn)模式隨空間和時間的傳播規(guī)律。時空耦合的策略則是采用時空耦合的搜索半徑定義地理要素間的有向或無向的時空鄰近關(guān)系，將頻繁滿足時空鄰近關(guān)系的不同地理要素集合定義為時空關(guān)聯(lián)模式。例如，WANG等[12]基于FP-growth算法提取頻繁同時滿足空間鄰近和時間鄰近的地理要素集合，并識別為時空同現(xiàn)模式。為了分析發(fā)現(xiàn)地理要素間關(guān)聯(lián)關(guān)系的傳遞規(guī)律，HUANG等[13]將頻繁按照形如1→2→…→n的鏈?zhǔn)巾樞虬l(fā)生于鄰近時空位置的多類地理要素集合識別為時空序列模式。除了發(fā)現(xiàn)鄰近地理要素發(fā)生的全序關(guān)系外，MOHAN等[3]進(jìn)一步識別地理要素發(fā)生的偏序關(guān)系即部分地理要素按全序順序頻繁發(fā)生于鄰近時空位置，并定義為時空級聯(lián)模式。相對于時空分治的策略，時空耦合策略避免了時間切片對地理要素間關(guān)聯(lián)關(guān)系的割裂。時空分治的策略由于對連續(xù)時間域進(jìn)行了離散化處理，會破壞地理要素在不同時間切片間關(guān)聯(lián)關(guān)系，進(jìn)而可能導(dǎo)致挖掘結(jié)果遺漏[14]。而時空耦合的策略能夠很好地表達(dá)時空關(guān)聯(lián)關(guān)系，但運(yùn)行效率比時空分治策略的低。為此，QIAN等[14]將這2類策略納入統(tǒng)一挖掘框架，通過變換滑動窗口大小，將這2類策略均轉(zhuǎn)換為該框架下的特例。通過分析可以發(fā)現(xiàn)，現(xiàn)有方法多需要人為設(shè)置頻繁度閾值，一般用戶由于缺少先驗(yàn)知識，難以獲得客觀的挖掘結(jié)果。另外，在頻繁度評價過程中，未顧及地理要素本身的分布特征，導(dǎo)致挖掘結(jié)果存在誤差。針對這些問題，本文作者以時空級聯(lián)模式為例，提出一種時空級聯(lián)模式的統(tǒng)計(jì)挖掘方法。該方法無需人為設(shè)置頻繁度閾值，也可準(zhǔn)確識別地理要素間的時空級聯(lián)模式。

1 研究策略

時空級聯(lián)模式挖掘的關(guān)鍵在于候選模式頻繁度的評價。采用人為設(shè)置的頻繁度閾值篩選候選模式會導(dǎo)致結(jié)果遺漏或誤判，因此，本文從時空統(tǒng)計(jì)的視角，將時空級聯(lián)模式挖掘建模為多元獨(dú)立分布零假設(shè)下候選模式頻繁度的顯著性判別問題，即判斷候選模式在觀測數(shù)據(jù)集中的頻繁度與零假設(shè)為真時的頻繁度是否存在顯著性差異。

零假設(shè)下不同類型地理要素的時空分布相互獨(dú)立，但每類地理要素應(yīng)保持原有的分布特征[15]。在現(xiàn)實(shí)世界中，由于地理要素存在時空相關(guān)性，導(dǎo)致時空點(diǎn)模式分析中假定的完全隨機(jī)分布不再適用[16]。因此，針對每類地理要素，本文首先對其分布特征進(jìn)行分析，選擇合理的點(diǎn)過程模型進(jìn)行擬合，生成與其原始分布特征相似的模擬數(shù)據(jù)，進(jìn)而構(gòu)建時空級聯(lián)模式顯著性判別的零模型。針對每個候選模式，若零假設(shè)下得到大于或等于觀測數(shù)據(jù)中頻繁度的事件是1個小概率事件，則說明該候選模式中的地理要素不服從多元獨(dú)立分布的零假設(shè)，將該候選模式定義為顯著的時空級聯(lián)模式。基于以上策略，本文方法主要包括2步：1) 多元獨(dú)立分布的零模型構(gòu)建；2) 時空級聯(lián)模式的顯著性判別。

2 時空級聯(lián)模式統(tǒng)計(jì)挖掘方法

2.1 基于時空點(diǎn)過程模擬的零模型構(gòu)建

為構(gòu)建時空級聯(lián)模式顯著性判別的零模型，首先需要對每類地理要素的時空分布特征進(jìn)行分析。針對每類地理要素f，采用時空函數(shù)[17]統(tǒng)計(jì)觀測數(shù)據(jù)中一定搜索半徑范圍內(nèi)時空點(diǎn)的個數(shù)，與完全隨機(jī)分布下的理論函數(shù)值進(jìn)行比較，進(jìn)而判斷該要素f是否存在顯著的自相關(guān)特征。時空函數(shù)定義為

進(jìn)一步，針對不同分布特征的地理要素，需要選取合理的時空點(diǎn)過程模型模擬其時空分布。若地理要素f存在時空自相關(guān)，則采用泊松簇過程[18]模擬其時空聚集分布過程，否則采用均勻泊松過程[18]進(jìn)行模擬。對于每個地理要素f，采用牛頓迭代法[19]估計(jì)其時空點(diǎn)過程的模型參數(shù)。在每次迭代過程中，采用調(diào)整后的模型參數(shù)生成大量模擬數(shù)據(jù)，并據(jù)此計(jì)算該參數(shù)下時空函數(shù)的實(shí)驗(yàn)值，進(jìn)而度量其與觀測數(shù)據(jù)中時空函數(shù)值的差異，作為參數(shù)優(yōu)化的目標(biāo)函數(shù)，具體表達(dá)為

式中：obs(,)為觀測數(shù)據(jù)中的時空函數(shù)值；null(,)為根據(jù)模擬數(shù)據(jù)計(jì)算的時空函數(shù)試驗(yàn)值；和分別為空間半徑和時間半徑的最大取值；和為調(diào)節(jié)因子(本文分別設(shè)置為1/4和2)。若小于一定閾值(本文設(shè)置為0.005)，則停止迭代，返回最優(yōu)的模型參數(shù)。

基于泊松簇過程的零模型構(gòu)建如圖1所示。從圖1(b)可以看出該要素時空函數(shù)的觀測值總大于理論值，表明其存在自相關(guān)特征，故采用泊松簇過程對其時空分布進(jìn)行模擬，得到的模擬數(shù)據(jù)如圖1(c)所示。從圖1(d)可見：模擬數(shù)據(jù)中時空函數(shù)曲面與觀測數(shù)據(jù)中的時空函數(shù)曲面基本吻合，說明模擬數(shù)據(jù)的時空分布能夠較好地保持觀測數(shù)據(jù)中的聚集特征。

2.2 時空級聯(lián)模式的顯著性檢驗(yàn)

首先，闡述時空級聯(lián)模式挖掘中一些相關(guān)概念，并給出如下定義[3]。

定義1 地理要素的實(shí)例。某類地理要素f在特定時間點(diǎn)出現(xiàn)在特定空間位置(，)的實(shí)體稱為該地理要素的實(shí)例e。

定義2 有向鄰域關(guān)系。給定空間半徑R和時間半徑R，若一地理要素實(shí)例e發(fā)生后的時間R內(nèi)發(fā)生另一地理要素實(shí)例e，且與e的空間距離不超過R，則e與e滿足有向鄰域關(guān)系e→e。

定義3 時空級聯(lián)模式及其實(shí)例。給定包含多個地理要素的時空數(shù)據(jù)集，類地理要素1，…，f的實(shí)例若頻繁按照一定時間順序出現(xiàn)在鄰近空間位置(即頻繁滿足一定有向鄰域關(guān)系)，則類地理要素構(gòu)成一個時空級聯(lián)模式，如{1→2；1→3；2→4；3→4}，類地理要素的實(shí)例中滿足該有向鄰域關(guān)系的集合稱為該級聯(lián)時空模式的實(shí)例。

(a) 示例數(shù)據(jù)集；(b) 觀測數(shù)據(jù)中的時空K函數(shù)值；(c) 模擬數(shù)據(jù)集；(d) 時空K函數(shù)的觀測值與模擬值

定義4 級聯(lián)參與指數(shù)。給定包含個地理要素1，…，f的時空級聯(lián)模式，級聯(lián)參與指數(shù)定義為

(a) 有向鄰域關(guān)系；(b) 示例時空級聯(lián)模式

圖2 時空級聯(lián)模式示意圖

Fig. 2 Illustration of spatio-temporal cascading pattern

基于以上定義，將時空級聯(lián)模式的頻繁度度量指標(biāo)(即級聯(lián)參與指數(shù))作為顯著性檢驗(yàn)的統(tǒng)計(jì)量，通過比較候選模式在零假設(shè)下頻繁度的模擬分布與觀測數(shù)據(jù)中頻繁度的差異，對候選模式的頻繁度進(jìn)行客觀評價。針對每個候選時空級聯(lián)模式，顯著性檢驗(yàn)的具體步驟如下：

1) 在觀測數(shù)據(jù)集中，計(jì)算該候選模式的級聯(lián)參與指數(shù)，記為obs()。

進(jìn)而，給定顯著性水平，若該候選模式的顯著性小于等于，則拒絕該模式中地理要素時空分布相互獨(dú)立的零假設(shè)，將該候選模式識別為顯著時空級聯(lián)模式。

3 實(shí)驗(yàn)分析與應(yīng)用

實(shí)驗(yàn)中，采用模擬數(shù)據(jù)和實(shí)際數(shù)據(jù)驗(yàn)證本文方法的有效性，并與現(xiàn)有的基于頻繁度閾值的時空級聯(lián)模式挖掘方法[3]進(jìn)行比較。本文方法中，每類地理要素的時空分布分別模擬99次，顯著性水平設(shè)為0.05。按照文獻(xiàn)[3]建議，對該方法中級聯(lián)參與指數(shù)的閾值設(shè)為0.2。

3.1 模擬實(shí)驗(yàn)

模擬數(shù)據(jù)集空間分布范圍為[0，1]2的單元，時間分布范圍為[0，1]的單元，如圖3所示，分別采用具有不同分布特征的4組模擬數(shù)據(jù)(記為1，2，3和4)進(jìn)行實(shí)驗(yàn)分析。1中，2類要素均具有大量實(shí)例，呈隨機(jī)分布；2中，類要素具有大量實(shí)例，類要素實(shí)例數(shù)較小，但均預(yù)設(shè)在類要素的有向鄰域內(nèi)；3中，2類要素均有大量實(shí)例，呈聚集分布；4中，類要素具有大量實(shí)例，呈隨機(jī)分布，類要素具有大量實(shí)例，呈聚集分布。除2外，其他模擬數(shù)據(jù)集中均無預(yù)設(shè)級聯(lián)模式。

4組模擬數(shù)據(jù)中，時空級聯(lián)模式{→}的頻繁度評價結(jié)果見表1，可見采用本文方法所得結(jié)果與預(yù)設(shè)結(jié)果相吻合。1中，由于2類要素大量實(shí)例隨機(jī)分布，導(dǎo)致現(xiàn)有方法中頻繁度被高估，但本文方法發(fā)現(xiàn)2類要素間不存在顯著的時空關(guān)聯(lián)關(guān)系；2中，由于大量類要素的周圍不存在類要素，因此，現(xiàn)有方法中頻繁度小于所設(shè)閾值，但采用本文方法發(fā)現(xiàn)類要素顯著依賴于類要素；3中，由于2類要素的時空簇存在隨機(jī)交疊，導(dǎo)致現(xiàn)有方法中該模式具有較高頻繁度，但采用本文方法發(fā)現(xiàn)2類要素的發(fā)生不存在顯著依賴關(guān)系；4中，類要素的隨機(jī)分布同樣會導(dǎo)致現(xiàn)有方法發(fā)生誤判，但采用本文方法也可判斷2類要素間不存在顯著關(guān)聯(lián)關(guān)系。

(a) S1；(b) S2；(c) S3；(d) S4

通過分析可以發(fā)現(xiàn)：本文方法能夠有效地避免一類要素分布對多類要素關(guān)聯(lián)模式分析的干擾，同時也避免了頻繁度閾值設(shè)置的主觀性對挖掘結(jié)果的影響。下面將進(jìn)一步采用實(shí)際犯罪數(shù)據(jù)集驗(yàn)證本文方法在實(shí)際應(yīng)用中的有效性。

表1 模擬數(shù)據(jù)中時空級聯(lián)模式{A→B}的挖掘結(jié)果

注：為級聯(lián)參與指數(shù)；為時空級聯(lián)模式的顯著性。

3.2 實(shí)際應(yīng)用

犯罪活動一直是嚴(yán)重威脅人類生命財產(chǎn)和社會公共秩序的社會現(xiàn)象，發(fā)現(xiàn)不同類型犯罪及其誘導(dǎo)因子間的關(guān)聯(lián)關(guān)系對犯罪防控具有重要意義[20?22]。本文采用2014年波特蘭地區(qū)的犯罪數(shù)據(jù)[23]進(jìn)行應(yīng)用分析。經(jīng)數(shù)據(jù)重分類后，數(shù)據(jù)集中包含11類犯罪案件：盜竊(30 795個實(shí)例)、擾亂治安(2 881個實(shí)例)、涉毒案 (2 599個實(shí)例)、侵害(2 313個實(shí)例)、詐騙(543個實(shí)例)、造假(1 904個實(shí)例)、渉酒案(2 241個實(shí)例)、傷害罪 (3 236個實(shí)例)、搶劫(802個實(shí)例)、蓄意破壞(4 115個實(shí)例)和涉槍案(310個實(shí)例)。現(xiàn)有研究發(fā)現(xiàn)酒吧關(guān)閉事件常會觸發(fā)犯罪案件的發(fā)生[24]，因此，本實(shí)驗(yàn)以酒吧關(guān)閉事件為例，進(jìn)一步分析各類犯罪案件與誘導(dǎo)因子間的時空級聯(lián)模式。

在現(xiàn)實(shí)地理環(huán)境中，地理要素間的交互關(guān)系錯綜復(fù)雜，采用單一的鄰域半徑難以準(zhǔn)確發(fā)現(xiàn)地理要素間的關(guān)聯(lián)關(guān)系。因此，本文采用1 km的空間半徑、從6~12 h、步長為1 h的時間半徑構(gòu)建犯罪數(shù)據(jù)集中的有向鄰域關(guān)系。4個時間鄰域下獲得的部分結(jié)果見表2，不同時間半徑下顯著時空級聯(lián)模式的數(shù)量分布見圖4(a)，不同顯著時長的模式數(shù)量分布見圖4(b)。分析挖掘結(jié)果可以發(fā)現(xiàn)：1) 時空級聯(lián)模式中涉酒案和涉毒案多為其他案件的前件案件，說明該類案件對其他案件的發(fā)生具有一定的誘導(dǎo)作用；2) 部分時空級聯(lián)模式的級聯(lián)參與指數(shù)較小，現(xiàn)有方法采用較高的頻繁度閾值難以有效發(fā)現(xiàn)，本文方法通過對頻繁度顯著性進(jìn)行判別，可以準(zhǔn)確識別有效模式；3) 隨著時間半徑增加，顯著時空級聯(lián)模式的數(shù)目逐漸增多，表明該數(shù)據(jù)集中不同犯罪案件及其誘導(dǎo)因子間多存在長期的影響關(guān)系。

下面以時空級聯(lián)模式{涉酒案→擾亂治安；涉酒案→涉毒案；擾亂治安→涉毒案}為例，對2種方法的實(shí)驗(yàn)結(jié)果進(jìn)行比較分析，如圖5所示。從圖5可見：波特蘭中心城區(qū)存在大量酒吧(圖5(a))，因而中心城區(qū)內(nèi)涉酒案件較密集(圖5(b))，同樣導(dǎo)致涉毒案件和擾亂治安案件在中心城區(qū)也具有較高的發(fā)生率(圖5(c)和(d))。除中心城區(qū)外，其他區(qū)域也發(fā)生大量的、分布相對離散的涉毒案件和擾亂治安案件，這些案件級聯(lián)參數(shù)指數(shù)的絕對值較小，現(xiàn)有方法難以發(fā)現(xiàn)該模式，本文方法通過對3類案件的時空分布進(jìn)行模擬，可以對該模式的頻繁度進(jìn)行客觀評價，發(fā)現(xiàn)其在4個時間半徑內(nèi)均具有顯著的級聯(lián)關(guān)系。進(jìn)而，政府和公安部門可以加大對涉酒案件的監(jiān)管力度，對其他級聯(lián)案件的發(fā)生進(jìn)行間接防控。

表2 犯罪數(shù)據(jù)集中的部分顯著時空級聯(lián)模式

(a) 不同時間半徑下的模式數(shù)量分布；(b) 不同顯著時長的模式數(shù)量分布

(a) 酒吧關(guān)閉；(b) 涉酒案；(c) 涉毒案；(d) 擾亂治安

4 結(jié)論

1) 針對現(xiàn)有時空級聯(lián)模式挖掘方法嚴(yán)重依賴于頻繁度閾值設(shè)置的不足，將時空級聯(lián)模式挖掘建模為多元獨(dú)立分布零假設(shè)下候選模式頻繁度的顯著性判別問題，發(fā)展了一種時空級聯(lián)模式的統(tǒng)計(jì)挖掘方法。

2) 與現(xiàn)有方法相比，本文方法能夠有效識別地理要素間的時空級聯(lián)模式，且無需人為設(shè)置頻繁度閾值。降低了現(xiàn)有方法的主觀性，并進(jìn)一步提高了時空級聯(lián)模式挖掘結(jié)果輔助案件偵查的可靠性。

[1] 李德仁, 王樹良, 李德毅. 空間數(shù)據(jù)挖掘理論與應(yīng)用[M]. 2版. 北京: 科學(xué)出版社, 2013: 1?10. LI Deren, WANG Shuliang, LI Deyi. Spatial data mining theories and applications[M]. 2nd ed. Beijing: Science Press, 2013: 1?10.

[2] SHEKHAR S, JIANG Z, ALI R, et al. Spatiotemporal data mining: a computational perspective[J]. ISPRS International Journal of Geo-Information, 2015, 4(4): 2306?2338.

[3] MOHAN P, SHEKHAR S, SHINE J A, et al. Cascading spatio-temporal pattern discovery[J]. IEEE Transactions on Knowledge & Data Engineering, 2012, 24(11): 1977?1992.

[4] CELIK M. Partial spatio-temporal co-occurrence pattern mining[J]. Knowledge and Information Systems, 2015, 44(1): 27?49.

[5] 葉文菁, 吳升. 基于加權(quán)時空關(guān)聯(lián)規(guī)則的公交扒竊犯罪模式識別[J]. 地球信息科學(xué)學(xué)報, 2014, 16(4): 537?544. YE Wenjing, WU Sheng. Identifying crime patterns of bus pickpocket using weighted spatio temporal association rules mining[J]. Journal of Geo?information Science, 2014, 16(4): 537?544.

[6] HUANG Y, SHEKHAR S, XIONG H. Discovering colocation patterns from spatial data sets: a general approach[J]. IEEE Transactions on Knowledge & Data Engineering, 2004, 16(12): 1472?1485.

[7] 邊馥苓, 萬幼. k-鄰近空間關(guān)系下的同位模式挖掘算法[J]. 武漢大學(xué)學(xué)報(信息科學(xué)版), 2009, 34(3): 331?334. BIAN Fuling, WAN You. A novel spatial co-location pattern mining algorithm based on k-nearest feature relationship [J]. Geomatics and Information Science of Wuhan University, 2009, 34(3): 331?334.

[8] 柴思躍, 蘇奮振, 周成虎. 基于周期表的時空關(guān)聯(lián)規(guī)則挖掘方法與實(shí)驗(yàn)[J]. 地球信息科學(xué)學(xué)報, 2011, 13(4): 455?464. CHAI Siyue, SU Fenzhen, ZHOU Chenghu. Period table based spatio-temporal association rules mining[J]. Journal of Geo-information Science, 2011, 13(4): 455?464.

[9] CELIK M, SHEKHAR S, ROGERS J P, et al. Mixed-drove spatio-temporal co-occurence pattern mining: a summary of results[C]//Proceedings of the 6th International Conference on Data Mining. Hong Kong, China, 2006: 119?128.

[10] CELIK M, SHEKHAR S, ROGERS J P, et al. Sustained emerging spatio-temporal co-occurrence pattern mining: a summary of results[C]//Proceedings of the 18th IEEE International Conference on Tools with Artificial Intelligence. Arlington, Virginia, USA, 2006: 106?115.

[11] QIAN F, HE Q, HE J. Mining spread patterns of spatio-temporal co-occurrences over zones[C]//International Conference on Computational Science and Its Applications. Heidelberg: Springer, 2009: 677?692.

[12] WANG J, HSU W, LEE M L. A framework for mining topological patterns in spatio?temporal databases[C]// Proceedings of the 14th ACM International Conference on Information and Knowledge Management.Bremen, Germany, 2005: 429?436.

[13] HUANG Y, ZHANG L, ZHANG P. A framework for mining sequential patterns from spatio-temporal event data sets[J]. IEEE Transactions on Knowledge and Data Engineering, 2008, 20(4):433?448.

[14] QIAN F, YIN L, HE Q, et al. Mining spatio-temporal co-location patterns with weighted sliding window[C]// IEEE International Conference on Intelligent Computing and Intelligent Systems. Shanghai, China, 2009: 181?185.

[15] DIGGLE P J. Statistical analysis of spatial point patterns[M]. 2nd ed. London, U.K.: Arnold, 2003: 30?40.

[16] ILLIAN J, PENTTINEN A, STOYAN H, et al. Statistical analysis and modelling of spatial point patterns[M]. Hoboken, NJ, USA: Wiley, 2008: 311?323.

[17] DIGGLE P J, CHETWYND A G, H?GGKVIST R, et al. Second-order analysis of space-time clustering[J]. Statistical Methods in Medical Research, 1995, 4(2): 124?136.

[18] DIGGLE P J. Statistical analysis of spatial and spatio-temporal point patterns[M]. Boca Raton, FL, USA: CRC Press, 2013: 101?110.

[19] BYRD R H, LU P, NOCEDAL J, et al. A limited memory algorithm for bound constrained optimization[J]. Siam Journal on Scientific Computing, 1995, 16(5):1190?1208.

[20] ROSSMO D K. Geographic profiling[M]. CRC press. Boca Raton, FL, USA: 1999: 111?122.

[21] 姜超, 唐煥麗, 柳林. 中國犯罪地理研究述評[J]. 地理科學(xué)進(jìn)展, 2014, 33(4): 561?573.JIANG Chao, TANG Huanli, LIU Lin. Review of crime geography in China[J]. Progress in Geography, 2014, 33(4):561?573.

[22] 祝曉光. 論犯罪地理學(xué)[J]. 人文地理, 1989, 4(2): 40?46. ZHU Xiaoguang. A discussion on the geography of crime[J]. Human Geography, 1989, 4(2): 40?46.

[23] Portland crime dataset[EB/OL]. [2016?10?15] http://www. civicapps.org/datasets.

[24] SCOTT M S, DEDEL K.Assaults in and around bars[M]. 2nd ed. Washington, DC: Office of Community Oriented Policing Services, 2006: 4?10.

(編輯 陳燦華)

A statistical approach for discovering spatio-temporal cascading patterns based on point process simulation

XU Feng, CHEN Yuanfang, CAI Jiannan, LIU Qiliang, DENG Min

(School of Geosciences and Info-physics, Central South University, Changsha 410083, China)

The discovery of spatio-temporal cascading patterns was modeled as a significance test for prevalence of candidate patterns under the null model of independence, and a statistical approach based on point process simulation was proposed. Firstly, null model was constructed by simulating the point process of different features. Then, the empirical distribution of prevalence of each candidate pattern was estimated by using Monte Carlo simulation. Lastly, significant spatio-temporal cascading patterns were identified by performing the significant test for the observed prevalence. The results show that the approach can effectively detect the meaningful spatio-temporal cascading patterns without threshold of prevalence measure.

spatio-temporal data mining; spatio-temporal cascading patterns; spatio-temporal point process; significance test

10.11817/j.issn.1672?7207.2017.10.022

P208

A

1672?7207(2017)10?2715?08

2017?04?21；

修回日期：2017?06?22

國家自然科學(xué)基金資助項(xiàng)目(41471385)；湖南省自然科學(xué)杰出青年基金資助項(xiàng)目(14JJ1007)(Project(41471385) supported by the National Natural Science Foundation of China; Project(14JJ1007) supported by the Science Foundation for Distinguished Young Scholars of Hunan Province)

蔡建南，博士，從事時空關(guān)聯(lián)模式挖掘研究；E-mail：jiannan.cai@csu.edu.cn