這是模式挖掘、數據挖掘的一部分應用。

空間模式挖掘(Mining Spatiotemporal Patterns)

兩個空間實體之間存在若干拓撲關系，這些關系基于兩個實體的位置：

如圖所示地表示位置信息，可以提取類似下面的規則：

is_a(x,large_town)?intersect(x,highway)→adjacent_to(x,water)[7%,85%]$is/_a(x, large/_town) /bigwedge intersect(x, highway) → adjacent/_to(x, water) [7/%, 85/%]$

逐步求精(PRogressive Refinement)

我們可以知道語言中有很對二義性的詞語，并且可以用不同的詞匯表達相同或者相近的意思。

比如，我們表示“靠近”，可以用“臨近”、“接近”、“比鄰”等等。那么我們就可以用Progressive Refinement來解決，因此空間關系可以應用在一個更加粗糙或者更精細的層次上。

Step 1

粗略計算，用于篩選

使用MBR(Minimum Bounding Rectangle)或者R-tree粗略估計。

Step2

更加細節的處理算法，用于精細處理

只處理那些通過粗略計算的數據（不小于最小支持度），從而節約時間與空間。

共置模式(Colocation pattern)

現有如圖所示地拓撲結構，用數字表示每一個樣本點，其符號是表示樣本點的種類。

共置模式指的是一組空間事件或者物體經常發生在相同的區域，在拓撲圖中這樣的事件用線連在一起。

其中{3, 6, 17}, {4, 7, 10, 16}, {2, 8, 11, 14, 15}, {2, 9}就是一個Colocation pattern。

rowset集合

而rowset(SET)則表示SET集合中每一個元素都出現在的Colocation pattern。

rowset({A,B,C,D})={{4,7,10,16},{2,11,14,15},{8,11,14,15}} $$rowset(/{A, B, C, D/}) = /{/{4, 7, 10, 16/}, /{2, 11, 14, 15/}, /{8, 11, 14, 15/}/}$$

rowset({A,B})={{5,13},{7,10},{2,14},{8,14}} $$rowset(/{A, B/}) = /{/{5, 13/}, /{7, 10/}, /{2, 14/}, /{8, 14/}/}$$

條件概率

Condition Probability

定義如下

計算條件概率必須按照定義來。

不是恒等于的。

例如，求cp(A→B)$cp(A/rightarrow B)$。

其中Rowset(A)={1,5,6,7,14}$Rowset(A) = /{1,5,6,7,14/}$，Rowset({A,B})$Rowset(/{A,B/})$如上文的例子。

在Rowset({A,B})$Rowset(/{A,B/})$中包含14的有兩個元素，但是根據定義也只能計算一次。

所以cp(A→B)=35$cp(A/rightarrow B) = {3/over 5}$

Participation Ratio

定義如下

Participation ratio pr(C,f)$pr(C, f )$: probability that C is observed in a neighbor-set wherever feature f is observed。

表示在f$f$發生的情況下，有多少情況是在C$C$情況下發現的。（注意，我這不是原原本本地翻譯，但是應該是等價的翻譯。）

例如，pr({A,B,C,D},A)=25 $$pr(/{A,B,C,D/}, A) = {2/over 5}$$

我們可以看到總共有5$5$個A$A$，但是只有2$2$個A$A$發生在{A,B,C,D}$/{A,B,C,D/}$的情況下。

pr({A,B,C,D},D)=2÷2=1 $$pr(/{A,B,C,D/}, D) = 2/div 2 = 1$$

類Apriori算法

算法思想和Apriori算法是一致的。

產生候選集的理論依據是Participation Ratio的單調性：

現有兩個Co-location pattern：C′$C'$和C$C$，且C′?C$C'/subset C$，那么對于任意f$f$，我們都可以得到pr(C′,f)≥pr(C,f)$pr(C',f)/geq pr(C,f)$。

軌道模式挖掘(Mining and Aggregating Patterns over Multiple Trajectories)

軌跡的挖掘任務

軌跡聚類：基于空間／時空的幾何估計進行分組

軌跡聯合：給定兩個軌跡數據庫，檢索所有的相似對

通過挖掘能夠處理多種問題，包括，路線規劃、城市規劃、識別物體、模式分類。

基本定義

基本運動模式

描述移動事件，不考慮絕對位置

上圖中箭頭表示運動方向，橫坐標表示時間，縱坐標表示物體。

空間運動模式

基本運動模式＋空間約束

聚合／分離運動模式

描述聚合和分離對象的運動

基于密度的軌跡模式

Moving Cluster

Convoy

挖掘語義豐富的運動模式(Mining Semantics-Rich Movement Patterns)

Step1

找到一組反映人們粗糙的語義級轉換的模式。例如，辦公室→餐館，家庭→健身房。

粗糙的語義在之前講的progressive refinement中說過，是一些粗糙的語義定義，比如，辦公室、辦公場所，甚至是一些更加具體的名詞，如政府辦等。

Step2

通過分組，將每個粗糙分類的相似圖案分成幾個細粒度圖案運動片段。

論文：C. Zhang et al., Splitter: Mining Fine-Grained Sequential Patterns in Semantic Trajectories, VLDB 2014