数据挖掘中的模式发现（八）轨迹模式挖掘、空间模式挖掘

这是模式挖掘、数据挖掘的一部分应用。

空间模式挖掘(Mining Spatiotemporal Patterns)

两个空间实体之间存在若干拓扑关系，这些关系基于两个实体的位置：

• 分离
• 相交
• 包含

如图所示地表示位置信息，可以提取类似下面的规则：

is_a(x,large_town)?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},9}就是一个Colocation pattern。

rowset集合

而rowset(SET)则表示SET集合中每一个元素都出现在的Colocation pattern。

条件概率

Condition Probability

定义如下

计算条件概率必须按照定义来。

例如，求 cp(A→B) 。

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

在 Rowset({A,B}) 中包含14的有两个元素，但是根据定义也只能计算一次。

所以 cp(A→B)=35

Participation Ratio

定义如下

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

表示在 f 发生的情况下，有多少情况是在 C 情况下发现的。（注意，我这不是原原本本地翻译，但是应该是等价的翻译。）

例如，

我们可以看到总共有 5 个 A ，但是只有 2 个 A 发生在 {A,B,C,D} 的情况下。

类Apriori算法

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

产生候选集的理论依据是Participation Ratio的单调性：

现有两个Co-location pattern： C′ 和 C ，且 C′?C ，那么对于任意 f ，我们都可以得到 pr(C′,f)≥pr(C,f) 。

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

轨迹的挖掘任务

轨迹聚类：基于空间／时空的几何估计进行分组

轨迹联合：给定两个轨迹数据库，检索所有的相似对

（编辑：晋中站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!