1. 简介

干货 面向大数据的时空数据挖掘

2. 基础知识

XML可扩展标记语言

可扩展标记语言，标准通用标记语言的子集，是一种用于标记电子文件使其具有结构性的标记语言。
在电子计算机中，标记指计算机所能理解的信息符号，通过此种标记，计算机之间可以处理包含各种的信息比如文章等。它可以用来标记数据、定义数据类型，是一种允许用户对自己的标记语言进行定义的源语言。 它非常适合万维网传输，提供统一的方法来描述和交换独立于应用程序或供应商的结构化数据。是Internet环境中跨平台的、依赖于内容的技术，也是当今处理分布式结构信息的有效工具。早在1998年，W3C就发布了XML1.0规范，使用它来简化Internet的文档信息传输。

时空数据

时空数据是同时具有时间和空间维度的数据，现实世界中的数据超过80%与地理位置有关。
时空大数据包括时间、空间、专题属性三维信息，具有多源、海量、更新快速的综合特点。
时空数据是指具有时间元素并随时间变化而变化的空间数据，是描述地球环境中地物要素信息的一种表达方式。这些时空数据涉及到各式各样的数据，如地球环境地物要素的数量、形状、纹理、空间分布特征、内在联系及规律等的数字、文本、图形和图像等,不仅具有明显的空间分布特征，而且具有数据量庞大、非线性以及时变等特征。

时空数据索引

数据索引技术也称作数据获取方法，大多数研究主要是从以下几个方面入手：1）历史数据的高效存储和获取，对于这个方面的研究，目前已经有学者提出了很多种基于R树或四叉树的时空索引技术，这样建立索引是为了减少建立索引占据的空间及提高查询效率；2）对于未来状态的查询，人们先假定已知一个时空地物坐标及速率，预测时空地物在以后的某个时刻坐标等信息，目前仅有TPR树及其改进型支持未来预测查询。
目前学者们提出的时空数据索引主要有HR-tree、PPR-tree、MVR-tree、RT-tree、3DR-tree、TPR-tree、TPR*树、Q+R树等。

时空数据查询

时空数据查询是指在过去、现在、未来某个时刻或时间段，检索对象的位置状态等信息。高效的时空查询对于时空数据库来说非常重要，是衡量一个数据库好坏的标准之一。常见空间查询有：

  • 点查询：给出某个点对象，找出所有包含该点的空间对象的方法。
  • 窗口查询：给出一个查询范围，找出与窗口相交或在范围内的空间对象。
  • 最近邻查询：找出与给定对象距离最小的一个空间对象。
  • 反最近邻查询：找出以给定对象为最近邻的空间对象。
    在空间查询的基础上给定时间条件来限制的查询就是时空查询。常见时间约束条件是给定时间点或一个时间段前提下查询空间对象信息。因此常规时空查询有：简单时间点查询、时间点窗口查询、时间段窗口查询、时间点最近邻查询、时间段最近邻查询、时间点反最近邻查询等

案例一 - 时空数据分析预测

第一个案例是关于亚特兰大某地区如何根据 1997 年到 2005 年的人口普查数据从而选择 2006 年需要新建银行分行的地点。我们收集的数据包括：1）该地区的地理信息（地图文件）；2）该地区从 1997 年到 2005 年已有银行分行的位置分布情况，包括每个分行的具体地址等；3）该地区从 1997 年到 2005 年的人口统计信息，包括区域 ID，人口密度，家庭收入，男女比例，人种比例等。通过时空数据预测分析，我们可以根据往年银行分行的发展趋势预测出该城市银行分行在下一年即 2006 年的分布密度，同时可以根据该城市家庭收入预测出 2006 年的客户需求，从而得出基于时空数据的银行分行的供求关系，继而确定需要在下一年新建银行分行的准确地点，即选择供不应求的地点进行银行新建。

案例二- 时空数据关联规则

第二个案例是基于一件发生在美国华盛顿州斯波坎市的一个真实的犯罪历史的犯罪模型分析。这则犯罪事故共发生犯罪事件 816 起，犯罪类型包括吸毒（167 起），抢劫（97 起）和车辆盗窃（552 起），发生时间从 2009 年 1 月到 2010 年 3 月，涉及斯波坎市的 10 个区和 23 条主要街道。我们得到的数据包括斯波坎市的部分地图信息，三种犯罪类型的统计信息以及该地区的人口统计信息，包括人口密度，家庭收入，男女比例，人种比例等。通过时空数据关联规则分析，我们可以根据每种犯罪事件发生的时间和地点得出该种犯罪类型和特定时间段和地理位置的关联关系，比如周末在公路附近多发吸毒事件等。同时我们还可以从时空数据分析中得到非时空数据的关联关系，比如人口密度小的地区多发抢劫事件等。

R树

R树是GUTTMAN于1984年提出的最早支持有序扩展的对象存取方法之一，也是目前应用最为广泛的一种空间索引结构。许多商用空间数据库系统，如MapInfo SpatialWaro和Oracle Spatial等均提供对R树的支持，开放源码系统PostgreSQL也实现了R树。近二十多年来，许多学者致力于R树的研究，在R树的基础上衍生出了许多变种。比较典型的有R+树、R*树、压缩R树等。

B树

在B-树中查找给定关键字的方法是，首先把根结点取来，在根结点所包含的关键字K1,…,Kn查找给定的关键字（可用顺序查找或二分查找法），若找到等于给定值的关键字，则查找成功；否则，一定可以确定要查找的关键字在Ki与Ki+1之间，Pi为指向子树根节点的指针，此时取指针Pi所指的结点继续查找，直至找到，或指针Pi为空时查找失败。

可能世界模型

时空对象的位置信息可以用最小外接矩形表示，最小外接矩形用坐标信息表示为{(x1,y1),(x2,y2)},x1=min{x1,x2,…,xn},x2=max{x1,x2,…,xn},y1=min{y1,y2,…,yn}, y2= max{y1,y2,…,yn}。

由于度量误差以及在网络传输过程的失真等原因影响了时空数据的精确性，产生了不确定时空数据。不确定时空数据在原有的时空数据的属性中加入概率属性，用概率属性来表示不确定性。

1
假设数据库中只有5行数据，且5行数据都带有概率值，且概率值分别为0.3、0.4、0.7、0.6、1，1行数据称为1个元组。假设第1个和第3个元组不能同时出现，第2个和第4个元组不能同时出现，则该数据库基于可能世界语义的所有可能实例有4个。4个可能世界实例表示为W={{1,2,5}，{1,4,5}，{3,2,5}，{3,4,5}}，则可能世界W1{1,2,5}的概率为0.12，可能世界W2{1,4,5}的概率为0.18，可能世界W3{3,2,5}的概率为0.28，可能世界W4{3,4,5}的概率为0.42。显然，4个可能世界的概率和为1。

p-文档模型

（1）ind型节点即独立型节点，独立型节点的某个孩子节点的存在不受其他孩子节点的影响，两个独立型节点同时出现的概率即两个独立型节点各自概率的乘积。
（2）mux型节点即互斥型节点，互斥型节点的孩子节点只能出现一个或者一个都不出现，即这些节点同时出现的概率为0，并且互斥型节点的孩子节点的概率值之和不大于1。
（3）孩子节点组合型节点exp，exp节点的孩子是节点集，并且这些节点集的概率和为1[12-14]。
（4）外部事件驱动型节点cie,cie节点的存在是由多个独立的外部事件决定的[18-19]。
（5）确定型节点det，如果某个节点是det型，则它的孩子节点必定出现[19]。
（6）独立事件驱动型节点fie,fie节点在cie节点定义的基础上，增加了逻辑并运算。
（7）连续分布型节点cont，cont节点只能在叶子节点上出现，con节点表示该节点是连续的[19]。

节点编码方案

XML的编码方式主要有基于区间的编码和基于路径的编码，本文采用的是基于路径的编码—Dewey编码。

普通Dewey的编码规则

XML文档的结构是一个有根有顺序的树，首先，分类节点是为了能够更清楚的表达不确定时空数据模型。

XML树的根节点的编码记为0。
如果某节点的Dewey编码是m，则其孩子节点的编码形式为m.n。如果孩子节点是父节点的第一个孩子，则n=0；如果此孩子节点是父节点的第x个孩子，则n的值为x-1;

扩展的Dewey编码

以根据叶节点的扩展的Dewey编码得到其祖先节点的标签序列，此过程需要用到转换规则FST和XML文档的DTD。这种扩展的Dewey编码的编码规则如下：
假设节点a是节点b的父节点，节点a的编码是A，节点b的编码是B，将B记为A.C，C的确定如下：
如果节点b是一个文本节点，则C=-1；
如果节点b不是文本节点，则C的确定方法如下：假设节点a的标签是Ta，节点b的标签是Tb，并且Tb处在节点a所有孩子标签中的第M位。此时，如果节点b是节点a的第一个孩子，则C=M，否则，假设D是节点b左兄弟的扩展编码的最后一部分，则

1
2
3
        D/N*N+M      (D mod N)<M
C=   D/N *N+N+M    (D mod N)=M                                 
       D/N  *N+M     (D mod N)>M

定义2-2：给出节点的扩展Dewey编码和孩子标签线索，可以通过有穷状态转换机FST将扩展Dewey编码转换为节点祖先标签序列。FST用一个五元组来表示，
FST={IN,ST,RT,FS,TB}：
(1)IN表示的是输入，IN为-1和正整数集的并集。
(2)ST表示XML文档中所有字符串和标签集的集合。
(3)RT表示根节点标签。
(4)FS是一个函数，设Ti为标签集中的某个标签，当C等于-1时，函数FS(Ti,C)返回当前字符串, 当C不等于-1时，返回标签tM，与函数F(Ti,D)返回的值相同。
(5)TB表示所返回的标签。

LCA语义

LCA（Lowest Common Ancestor）即最低公共祖先,LCA语义相关定义如下：
定义2-3 节点集合S={s1, s2, …, sm}有m个节点元素，如果节点A满足以下两个条件时，节点A是这m个节点的最低公共祖先：
（1）A是m个节点的公共祖先。
（2）不存在这样一个节点B：它是节点A的后代，并且它是m个节点的公共祖先,
记为A=LCA(S)= S={s1, s2, …, sm}。

SLCA语义

SLCA语义是基于LCA语义提出的，SLCA语义的相关定义如下：
定义2-4假设节点t1,t2,…,tn，分别是节点集S1,S2,…,Sn中的一个节点，节点A是节点t1,t2,…,tn的最低公共祖先，则节点A属于LCA(S1,S2,…,Sn),如果节点B也属于LCA(S1,S2,…,Sn),并且节点A不是节点B的祖先节点，则节点A是SLCA节点。