CN106844736A - 基于时空网络的时空同现模式挖掘方法 - Google Patents

Abstract

本发明提供了一种基于时空网络的时空同现模式挖掘方法，包括：对时空数据集进行初始化建模，建立用以表示实例及元素之间时空关系的双层时空网络，并保存所述时空网络对应的邻接矩阵；其中，所述时空网络包括实例网络层及元素网络层，所述元素网络层用于生成候选集；从所述实例网络层中读取相应邻近关系序列，计算模式支持度及空间频繁度；从所述元素网络层读取模式的邻近关系，计算模式的时间频繁度；根据模式的各时间槽空间频繁度及时间频繁度计算模式的权重特征值；将所有同现模式按照权重特征值进行排序，根据输入的模式比例值，输出满足条件的模式集。本发明提高了时空同现模式的计算效率，解决了时空阈值难以设定的问题。

Description

基于时空网络的时空同现模式挖掘方法

技术领域

本发明属于数据挖掘技术领域，具体涉及一种基于时空网络的时空同现模式挖掘方法。

背景技术

大多数数据库都不能有效地处理数据的时间维度，时空同现模式挖掘有利于提取隐含在时空数据集中的有价值信息，目前已经成为数据挖掘研究的前沿领域之一，如时空目标的轨迹聚类、时空对象的行为异常检测、以及轨迹预测等等。由于监控摄像、手机电脑、车载导航等技术的普及，可以很方便获取时空对象的轨迹数据。时空对象的轨迹数据，从时间片维度上看，是由很多采样点依照一定的时间间隔按照时间顺序排列的位置数据序列；从空间轨迹点的信息结构上看，是由空间对象标识、采样点的位置、采样点的时间等信息组成的多维数据，因此时空数据本身具有时间和空间层面两个属性，而且这两个属性相互依存。时空对象的轨迹数据作为时空对象的历史活动数据，在某些程度上能够表现时空对象的属性、状态、行为等内部与外部特征，通过分析时空数据可以获得很多有趣模式及有价值的信息，并可以由此推导出更有实际意义的新知识。

实际生活中挖掘时空同现模式是非常有意义的。如用户交易数据中蕴含了非常有价值的用户行为信息，从这些数据中找到蕴藏的知识金块，就可以帮助企业减少不必要投资，同时提高资金回报。挖掘行人的历史位置数据中的同现模式，发现人与人之间的关系，可以将这类关系用作基于位置的广告推荐等众多领域。发现士兵的训练成绩与其他环境因素等的时空同现模式，得到不同等级的成绩与不同因素的同现关系，就可以在训练中有针对性地组织训练，提高训练水平；研究作战策略及部署方式获得的同现模式，可以用于推理当前舰队火力，提高打击的精准度。时空同现模式在其他领域如交通管制、气象研究、国防军事、基于位置的服务等也都具有极高的应用价值。

时空数据的海量生成使得时空数据挖掘的相关技术得到迅猛发展，时空同现模式挖掘是当前时空数据领域的关键技术之一，旨在从包含多个时空对象类型的时空数据集中，发现频繁在邻近位置同现且频繁在连续时间槽内共现的类型集合，给出时空对象间比较典型的同现规律。在众多技术中，时空对象的同现模式发现技术是挖掘对象活动特征的关键技术之一，其主要是通过对时空对象轨迹数据进行特征分析，发现时空对象间比较典型的活动模式。同现模式的频繁特性可以用来检测时空对象在时空领域频繁发生的活动和频繁访问的路径，也可以在对象空间活动的基础上发现重复活动的时间特征，具体表现为周期性。

现有技术中，同现模式挖掘技术已在不同领域有了一定的应用范围，但在筛选空间同位模式及发现时空同现模式的过程中存在如下技术缺点：

(1)时空同现模式的计算效率仍比较低

大多数方法没有对数据集进行建模，直接用原始数据集进行候选模式的生成及时空兴趣度的计算，导致大量重复或无用的计算，影响了同现模式的挖掘效率。其次，基于连接操作生成多元候选模式，不仅占用较大内存空间，而且计算效率也比较低。

(2)时空距离及时空兴趣度的计算方式不太贴近实际

现有方法中采用欧氏距离表示时空对象间的距离，但实际的时空对象在移动过程中，从一个对象到另一个对象的行走路线大多不是直线；其次，目前多数方法在计算时空兴趣度时，忽略了元素类型的实际存在周期，计算方法不能很好地描述同现模式的共现规律。另外，现有技术多采用时空阈值驱动同现模式的挖掘过程，但时空阈值难以预先设定。

发明内容

本发明的目的在于针对现有技术的不足，提供基于时空网络的时空同现模式挖掘方法，以解决上述技术问题。

本发明的实施例提供了一种基于时空网络的时空同现模式挖掘方法，包括如下步骤：

步骤1，对时空数据集进行初始化建模，建立用以表示实例及元素之间时空关系的双层时空网络，并保存时空网络对应的邻接矩阵；其中，时空网络包括实例网络层及元素网络层，元素网络层用于生成候选集；

步骤2，从实例网络层中读取相应邻近关系序列，计算模式支持度及空间频繁度；

步骤3，从元素网络层读取模式的邻近关系，计算模式的时间频繁度；

步骤4，根据模式的各时间槽空间频繁度及时间频繁度计算模式的权重特征值；

步骤5，将所有同现模式按照权重特征值进行排序，根据输入的模式比例值，输出满足条件的模式集。

进一步，步骤1具体包括：输入时空数据集，读取时空数据集的属性信息，获得各元素类型的元素周期；将时空数据集预处理成预定格式；其中，预定格式的内容包括实例编号、元素类型、位置信息、时间信息；将时空数据集中所有数据点按时间槽划分，计算各时间槽中元素实例的时空距离；其中，时空距离为曼哈顿距离；获取时空距离阈值D；获取元素实例间的时空距离小于等于阈值D，而且元素实例都处于元素周期的元素实例对，保存具有邻近关系的实例对；获取各时间槽内的邻近关系；根据获取的各时间槽内的邻近关系建立实例网络层，并采用邻接矩阵保存实例网络层；根据实例网络层的各实例的元素类型，建立元素网络层，并采用邻接矩阵保存元素网络层。

进一步，获取各时间槽内的邻近关系包括：当具有邻近关系的实例对首次出现：将邻近关系的两个结点连接，边上的邻近系列对应的当前时间槽位设为1；在邻近序列中在当前时间槽之前的，若是在实例对应的模式的时间框架内，设为0；在邻近序列中在当前时间槽之前的，若不在模式的时间框架内，设为-1；

当所述具有邻近关系的实例对非首次出现：在实例连接的边上，对应的时间槽位设为1。

进一步，步骤2中，计算模式支持度包括：获取未计算模式支持度的元素；统计在元素网络层中，与元素相连的实例总数；统计在对应时间槽序列中为1的实例数，即实例支持数；求出实例支持数与实例总数的比值，即元素的模式支持度。

进一步，步骤2中，计算空间频繁度包括：获取未计算空间频繁度的模式；求得模式中所有元素的元素框架交集，即模式的时间框架；在时间框架下，获取未计算空间频繁度的时间槽；求得所述时间槽下模式的最小模式支持度，即模式的空间频繁度；其中，时间槽下若没有元素实例集在实例网络层存在同现关系，则空间频繁度为0。

进一步，步骤3具体包括：获取未计算时间频繁度的模式；在元素网络层中，获取模式所有元素之间值为1的所有时间槽，即可能同现的时间槽；用同现的时间槽数除以模式时间框架时间槽数，求得模式的时间频繁度。

进一步，步骤4具体包括：获取未计算权重特征值的模式；将模式在所有时间槽的空间频繁度作为空间特征，计算空间频繁度均值；计算模式权重特征值，公式如下：权重特征值＝空间频繁度均值×时间频繁度。

进一步，步骤5具体包括：采用堆排序方法按权重特征值对所有模式进行排序，得到模式链表；按照需求，输入最需要的时空同现模式的比例值k；按照比例值k，从模式链表中取排在前k的模式集，获取时空同现模式集。

与现有技术相比本发明的有益效果是：提高了时空同现模式的计算效率，解决了时空阈值难以设定的问题。

附图说明

图1是本发明一实施例中时空数据集的示意图；

图2是根据图1的时空数据集建立的时空数据集实例网络层；

图3是根据图2的时空数据集实例网络层建立的时空数据集的元素网络层；

图4是本发明基于时空网络的时空同现模式挖掘方法的整体流程图；

图5是欧氏距离与曼哈顿距离的示意图；

图6是本发明一实施例中AC模式的元素周期内的时空数据集；

图7是本发明一实施例中初始化时空网络流程图；

图8是本发明一实施例中模式支持度计算流程图；

图9是本发明一实施例中模式的空间频繁度计算流程图；

图10是本发明一实施例中模式的时间频繁度计算流程图；

图11是本发明一实施例中同现模式挖掘流程图；

图12是本发明一实施例中建模时间与时空同现模式挖掘总时间比较图；

图13是本发明一实施例中三种方法运行效率的比较结果。

具体实施方式

下面结合附图所示的各实施方式对本发明进行详细说明，但应当说明的是，这些实施方式并非对本发明的限制，本领域普通技术人员根据这些实施方式所作的功能、方法、或者结构上的等效变换或替代，均属于本发明的保护范围之内。

本实施例针对现有技术中的两个技术缺陷，从提高同现模式计算效率及有效时空兴趣度计量方式两个方面出发，提出了如下技术方案：

(1)对时空数据集进行初始化建模，建立一种可以有效表示实例及元素之间时空关系的时空网络。本实施例在时间汇总图的基础上，提出了双层网络的时空建模方式，双层网络包含实例网络层及元素网络层，从元素网络层生成的候选集规模比直接从数据集生成要小很多，而且候选集中的模式至少存在一组实例支持模式同现，因此可以缓解由候选集规模造成的计算量过大问题。其次，时空网络中的边存储了实例之间及元素之间的时空关系，同现模式的时空频繁度计算可以直接读取对应边上的序列，而且时空网络的易于存取及可重复利用性，使同现模式的计算效率得以提升；

(2)重新设定了时空对象间的时空距离及相关时空兴趣度的计算方式。针对现有技术中欧氏距离的缺点，本实施例采用更能描述实际时空对象间距离的曼哈顿距离，使得距离更贴近实际，而且在一定程度上提高了距离计算速度。不同时空对象，其有效时间段的起始时间及终止时间都不一样，本实施例根据这一事实，重新描述了时空频繁度的计量方式，并引入了表示模式时空频繁度的计量度——权重特征值，模式按照该值排序形成模式链表，该链表保存了不同频繁度的时空同现模式，根据需要输入获取同现模式的比例值，就可以从链表中获得最终的同现模式集。权重特征值的大小表示了模式在空间及时间的频繁程度，输入比例值就可以获得高频繁率的时空同现模式集，不需要预先设定时间频繁阈值及空间频繁阈值，避免了时空阈值难以设定的问题。

下面对本发明作进一步详细说明，参图1至图13所示。

时空数据集建模方式

(1)时空网络建模

本实施例基于时间汇总图的模式，提出了一种双层网络建模方式，在初始化过程中对时空数据集进行网络建模。该双层网络分别对时空对象的实例之间以及时空对象的(元素)类型之间建立关系网络。为方便计算，本实施例对所有实例对象及元素类型进行了编号，双层网络分别采用邻接矩阵的方式进行存储，由于每层网络都是无向图，其存储在邻接矩阵中的信息是对称的，因此只存储上三角(或下三角)矩阵信息即可保留全部的同现信息。

①基于双层网络对时空数据的初始化建模方法

输入时空数据集(元素类型，当前实例，经度坐标，纬度坐标，当前时间槽)、元素及元素有效周期列表(元素类型，有效周期)、元素对象之间的邻近距离。

遍历时空数据集，形成实例网络层，具体包括：遍历元素存在周期，获得总时间框架；创建初始实例网络层邻接矩阵；初始时每个时间序列的时间槽位为-1；计算时间框架下的每个时间槽内对象之间的距离；实例对象排序时，Oj编号在Oi的后面；若两对象之间的距离小于等于给定邻近距离，时间槽位设为1，否则时间槽位设为0。

根据实例网络层生成元素网络层，具体包括：创建初始元素网络层邻接矩阵；初始时每个时间序列的时间槽位为-1；若两对象实例在当前时间槽存在同位关系，将其对应的元素网络层中的时间序列位设为1；若两元素都在有效周期内，且当前两对象之间不存在同位，但存在元素的其他对象，其对象之间在该时间槽同位，保留同位关系为1；不存在其他对象实例之间的同位关系，当前时间槽位TEk设为0。

输出实例网络层及元素网络层。

②具体建模步骤

对时空数据集中各对象类型进行一次建模，形成实例网络层；

从实例网络层出发，根据实例的类型属性形成元素网络层，两层网络之间类型和类型的实例之间存在映射关系。

在实例网络的建立过程中，以类型实例作为网络中的结点，结点之间在首次出现邻近时连接，结点之间的边用序列表示结点之间在各时间槽是否邻近，实例之间若满足邻近关系，设为1，不满足邻近关系，设为0，边连接的两实例不处于有效周期内设为-1。在元素网络层，结点类型之间同样在首次出现同现时连接，两个元素类型若在某一时间槽内同位，对应时间槽标记为1，不同位，则标记为0，若某一时间槽不在两个类型构成的模式的时间框架内，则设为-1。

参图1及图2所示，其中，图1为时空数据集，包含A、B、C、D四种元素类型，A元素类型有4个实例，元素周期为时间槽0～时间槽2，B元素类型有3个实例，元素周期为时间槽0～时间槽3，C元素类型有5个实例，元素周期为时间槽0～时间槽3，D元素类型有4个实例，元素周期为时间槽1～时间槽3，图1中元素实例之间的连线表示曼哈顿距离满足邻近关系，而且不在元素周期内的元素实例未计算邻近距离。图2为根据图1的时空数据集建立的时空数据集实例网络层。

对图1的数据集建立实例网络层，如图2所示。在图2中，实例之间在各时间槽的邻近关系组成序列，作为图中结点之间边的属性，可以从该网络层中高效地获取实例在所有时间槽中与其它实例的空间邻近关系。结点之间边上的序列值为1，表示所对应的时间槽中边所连接的两个实例是邻近关系，某一类型的模式支持实例数可以很容易从网络中读取出来，从而计算出模式支持度以及空间频繁度。以图1中时空数据集为例，根据图2的实例网络层建立的元素网络层如图3所示。

如图3所示，模式的时间框架可以很容易从元素网络中获得。对于一个模式，若是时空同现模式，那么模式中的所有类型在元素网络层中都相连，并在某一时间槽内所有类型之间边上的值都为1，而且至少存在一组实例支持该同现关系。依据此原则，还可以直接从元素网络层生成候选模式集，可以避免大量的连接操作。元素网络层保存的同现关系使时间频繁度可以快速计算出来。

本实施例将时间汇总图网络模型应用于时空同现模式挖掘的数据初始化过程中，在原有模型的基础上，对时空数据集建立两层时空网络，通过访问双层网络可以快速地获取到元素实例间的邻近关系以及元素间的时空关系，使得时空兴趣度的计算更便捷、快速。针对传统算法中多采用大量的连接操作以及复杂的空间区域分割，使得时空数据集的时空关系在一定程度上遭到破坏，而且连接操作产生了大量的候选集，计算量非常大，而且占用大量的内存空间，使得挖掘过程的计算效率非常低的缺陷，本实施例采用双层时空网络，避免了大量的连接操作，在一定程度上提高了计算效率，而且网络结构可以很好地保存数据集的时空关系，保障了挖掘的同现模式的有效性。

(2)时空网络存储

对数据集进行一次初始化建模后，本实施例将产生的时空网络进行保存，当后续若需要再用到时空网络，不需要进行重复建模，就可以直接使用。一次建模多次使用，后续的时空同现模式的计算效率可以显著提高。本实施例建立的双层时空网络，其本质是无向图，计算时空距离时，若元素实例集A.1B.1与B.1A.1满足邻近关系，则只存储A.1B.1，不再存储B.1A.1，本实施例从多元素类型的角度进行时空同现模式研究，因此在计算时空同现模式过程中，不考虑同元素类型的实例之间的时空关系，采用这种存储方式可以进一步对时空网络的邻接矩阵进行压缩存储，减小网络的实际占用空间。在将时空网络的邻接矩阵进行存储时，为方便计算，本实施对所有元素实例进行编号，这样在邻接矩阵中，每个行号或者列号就代表一个元素实例，图2中的实例网络层的邻接矩阵如表1所示。

表1实例网络层的邻接矩阵

从表1可以看到，邻接矩阵的有效值部分是表中非空值部分，本实施例在存储时空关系时，仅存储表中有效值部分，可以节省很大空间，这样时空网络的邻接矩阵就可以很方便地保存。给定两个元素实例，首先判断这两个实例在时间框架内的邻近关系是否合理，即这两个实例的元素类型是否是同一类型，若这两者属于同一元素类型，则不进行网络读取，若是不同元素类型，按照之前的排序编号，找出实例网络层的邻接矩阵中对应的时空关系，进行模式支持度及空间频繁度的计算。

参图4所示，图4是本发明基于时空网络的时空同现模式挖掘方法的整体流程图。

本实施例提出了基于时空网络的时空同现模式挖掘方法，首先对时空数据集中各时间槽内的元素实例之间的时空距离进行计算，满足给定的时空距离阈值构成时空邻近关系，对这些关系进行建模，形成双层时空网络，读取该网络中的邻近关系序列，快速计算各模式的空间频繁度及时间频繁度，之后计算同现模式的权重特征值。将同现模式按照权重特征值进行排序，根据所需同现模式的比例，获取满足条件的时空同现模式集。

本实施例的时空同现模式是在时空同位模式为基础的空间特性上，将时空数据的时间维度也进行频繁性分析，从而获得时空同现模式。时空同位模式研究时空空间特征依赖性，主要是指从时空数据库中挖掘出频繁出现而且紧密相邻的时空空间特征的集合，这里的特征可以指导致某一事件发生的各个因素，也可以指时空活动范围内的各种活动对象等等。判断模式是否为同位模式，主要以时空距离、模式支持度两个计量度作为判断准则。从时空数据集中发现时空同位模式后，本实施例方法以各模式的权重特征值作为挖掘有趣时空同现模式的标准。

下面分别给出各个计量度的定义及计算公式。

(1)时空距离计算

根据地理学第一定律可以得知，在空间单元中，每一元素都与其他元素相关，但邻近元素的空间相关性要比距离较远的元素之间的空间相关性大得多，因此，在时空同现模式挖掘过程中，首先需要计算时空对象的邻近关系。在计算任意两个或多个时空对象的距离时，欧氏距离是最常用的一种距离表示法，欧氏距离又称为欧几里得度量，是指在n维空间中两个时空对象之间的真实距离，若把时空对象抽象为点来处理，这个距离就是由点的n位数据构成向量的自然长度，也就是该点到空间原点的距离。在欧几里得空间中，以点x＝(x₁,...,x_n)和y＝(y₁,...,y_n)为例，两者之间的距离如公式(1)所示。

在实际生活中，从一个地点A到地点B，很少出现直线路径，尤其是在北京、上海等高楼林立的城市中，街道都是纵横交错，从A到B，其行走路线大多需要绕道，那么在实际的时空轨迹数据点集中，两个时空对象的距离计算以欧氏距离为准不是很合理，因此本实施例使用另外一种距离表示法——曼哈顿距离作为对象间的时空距离。曼哈顿距离可以很好地表示城市区块距离，其依赖坐标系统的转度，而非坐标轴上的平移或映射。在欧几里得空间的固定直角坐标系上，两点在标准坐标系上绝对轴距总和，也可以表示为两个点所形成的线段对轴产生的投影的距离总和，同样以n维空间中点x＝(x₁,...,x_n)和y＝(y₁,...,y_n)为例，其曼哈顿距离计算公式如公式(2)所示。

参图5所示，图5是欧氏距离与曼哈顿距离的示意图。

在图5中，从A到B的距离，欧氏距离表示为|AB|，若绕道C点，则曼哈顿距离可以表示为|AC|+|CB|，若绕道E点，则曼哈顿距离为|AD|+|DE|+|EF|+|FB|，在以A、B为对角点所围成的矩形中，不论选取哪一点为绕道点，其曼哈顿距离都相同，即等于|AC|+|CB|。

曼哈顿距离不仅可以更真实地表示时空距离，而且在计算时采用加减法，其计算速度要比以乘法运算为主的欧氏距离快很多。由于这两个明显的优势，本实施例选用曼哈顿距离作为时空对象间的距离。

(2)时空兴趣度计算

通过计算时空距离，可以发现数据集中满足邻近关系的时空对象集，计算该集合中各模式的模式支持度可以得到时空同位模式集，而从时空同位模式集中计算各同位模式的权重特征值，就可以得到需要的时空同现模式集。在时空数据挖掘领域中，表现显著的时空同现模式与其他同现模式相比具有更高的频繁度值，也就是时空兴趣度较高的同现模式具有较高的时间频繁度值和空间频繁度值，因此，为了更好地表征时空同现模式的用户感兴趣程度，本实施例在定义模式的权重特征值时，涉及到时间度量和空间度量这两种度量。时间度量是各同位模式的时间频繁度，也就是各模式在时间框架下的出现频率，空间度量是各同位模式在各时间槽下的空间频繁度，其计算基于模式中各元素的模式支持度，因此时空兴趣度主要需要计算模式支持度、空间频繁度、时间频繁度及模式权重特征值。

在传统的时空同现模式计算过程中，时空兴趣度的各个计量度都是以给定的整体时间框架为基础，这里的时间框架是指在其范围内所有元素在所有时间槽中都是活动状态，而在实际中，模式中某一元素可能只在某一段时间槽内是活动状态，而在该时间段外元素是失效的，将给定的整体时间框架称为整体周期，某一元素的实际活动时间框架称为元素周期，那么，某一元素的元素周期并非整体周期。若给定一个时空数据集，在计算各模式的时空兴趣度时，采用整体周期来计算，计算结果可能会产生大量无用的时空同现模式，降低了挖掘结果的有效性，因此本实施例采用将各元素的元素周期而非数据集的整体周期来计算时空兴趣度。

①模式支持度

模式支持度是指构成模式的所有元素对该模式的支持程度，由于每一元素在时空数据集中具有很多实例，在所有实例中参与到该模式中的实例数就是该元素对模式的支持度，本实施例将参与到模式中的实例数与元素的所有实例数之比作为该元素的模式支持度。在时空数据集中不同元素的元素周期不同，在确定模式的所有元素在当前时间槽都处于活动状态时，某一元素对模式的支持度计算方式如公式(3)所示。

在公式(3)中，PS(Pattern Support)是模式支持度，I表示支持当前模式处于活动状态的元素实例数，A表示元素的所有实例数。

以图1中的数据集为例，在时间槽0内，以模式AC为例，元素A和元素C都处于元素周期内，元素A有4个实例，参与支持AC模式的有A.1，A.2，A.4三个实例，因此元素A对模式AC的模式支持度PS(A)＝3/4＝0.75，元素C共有5个实例，参与支持模式AC的有C.1，C.2，C.3三个实例，因此元素C对模式AC的模式支持度为PS(C)＝3/5＝0.6。

②空间频繁度

在某一时间槽下，模式的空间频繁度是模式中元素实例处于邻近关系的频繁程度，任一元素对模式的支持程度都通过其实例表现出来，模式中各元素的实例频繁邻近的程度也就表征了该模式在当前时间槽的空间频繁程度，而实例对元素的模式支持通过模式支持度表示，所有元素的模式支持度也就表征了该模式的空间频繁程度，最小的模式支持度就是该模式的最低空间频繁程度，也就是模式中所有元素的模式支持度的最小值，就是该模式在当前时间槽的空间频繁度。假定某一模式p有k个元素，即p₀,...,p_k-1,那么模式p的空间频繁度，也就是模式p中所有元素的模式支持度的最小值，如公式(4)所示。

PS(p)＝min{PS(p_i)},0≤i≤k-1 (4)

在公式(4)中，PS(p)表示模式p的空间频繁度，PS(p_i)表示元素p_i的模式支持度。以图2中时间槽0中的AC模式为例，PS(AC)＝min{PS(A),PS(C)}＝{0.75,0.6}＝0.6。

③时间频繁度

时间频繁度是指某一模式在不同时间槽下频繁出现的程度。对于某一模式p，其时间频繁度的计算首先要计算该模式的时间框架，该时间框架就是该模式有效的时间槽段，也就是求出所有元素的元素周期交集，在该交集内所有元素都是有效的，该模式也就处于有效计算状态。假定模式p中有n个元素，p₀,...,p_n-1，各元素对应的时间框架为T₀,...,T_n-1，则该模式p的时间频繁度计算方式如公式(5)所示。

其中，TP(p)(Time Support of Pattern)是模式p的时间频繁度，T_i表示p中某一元素p_i所对应的时间框架。以图1中的AC模式为例，A的元素周期为时间槽0～时间槽2，C的元素周期为时间槽0～时间槽3，元素A与元素C的元素周期交集为时间槽0～时间槽2。模式AC出现时间槽有：时间槽0、时间槽1、时间槽2，因此TP(AC)＝3/3＝1。

④权重特征值

时空同现模式不仅表示模式中各元素的时空邻近关系，还表示了这种关系的时空频繁程度，包括时间维度和空间维度，因此，为了简便计算，在传统的同现模式挖掘过程中，通常预先设定表示时间频繁最低程度的时间阈值和表示空间频繁最低程度的空间阈值，这两个阈值在不同的领域需要各领域的专家多次试验才能给出较合理的阈值，较大或较小的阈值参数都会引起高估或低估时空同现模式的问题，为了解决该问题，本实施例定义了模式的权重特征值，该特征值将同现模式在各个活动时间框架下的空间频繁度和时间频繁度作为特征，并根据该特征组计算同现模式的权重特征值。假定模式p中有n个元素，p₀,...,p_n-1，各元素对应的时间框架为T₀,...,T_n-1，则同现模式p的时间框架为T₀,...,T_n-1的交集，设该交集的各时间槽为：TF_v,…,TF_w。若在该时间槽段内，模式p在m个时间槽内出现，0≤m≤w-v+1，则各时间槽的空间频繁度也就是模式的各空间特征值，记为PS(p)_i，0≤i≤m-1，同现模式的权重特征值计算方式如公式(6)所示。

在公式(6)中，W(p)表示模式p的权重特征值，该特征值将同现模式p的空间频繁度分散到时间框架内的各时间槽中，这样能更好地表示同现模式的实际空间频繁程度，从公式(6)可以看到，W(p)等于p频繁的所有时间槽的空间频繁度的均值与p时间频繁度之积。如果同现模式的空间频繁度均值一定，权重特征值随着模式的时间频繁度单调增加，该式也体现了模式的时间频繁程度。

以图1中的AC模式为例，A的元素周期为时间槽0～时间槽2，C的元素周期为时间槽0～时间槽3，元素A与元素C的元素周期交集为时间槽0～时间槽2。因此模式的时间框架内的时空数据集如图6所示。

图6给出了模式AC的时空数据集，模式AC出现时间槽有：时间槽0、时间槽1、时间槽2，计算得到模式AC在时间槽0到时间槽2的空间频繁度分别为：

PS(AC)₀＝min{PS(A),PS(C)}＝{0.75,0.6}＝0.6

PS(AC)₁＝min{PS(A),PS(C)}＝{0.75,0.8}＝0.75

PS(AC)₂＝min{PS(A),PS(C)}＝{0.5,0.4}＝0.4

模式AC的时间频繁度为TP(AC)＝3/3＝1，因此同现模式AC的权重特征值为：W(AC)＝(0.6+0.75+0.4)/3*1≈0.58。

本实施例采用的时空关系建模方式不仅可以很好地保存时空关系，其存取的方便性使得时空兴趣度的计算效率得到一定程度提高，时空邻近距离采用曼哈顿距离，不仅可以使元素实例的实际轨迹距离更符合实际情况，而且这种距离计算方式主要是加、减法运算，比传统的欧氏距离计算效率要高，进一步提高了本发明所提出的基于时空网络的时空同现模式挖掘方法的挖掘效率。在计算时空同现模式的时空兴趣度时，本实施例采用各元素的元素周期而非整体周期作为模式的时间框架，使模式的计算更符合实际，同现模式的权重特征值的引入，进一步使挖掘结果的有效性有了一定程度提高，下面对本实施例基于时空网络的时空同现模式挖掘方法作进一步详细说明。

(1)模式挖掘方法

输入时空数据集(元素类型，当前实例，经度坐标，纬度坐标，当前时间槽)、元素及元素存在周期列表(元素类型，有效周期)、元素对象之间的邻近距离。

初始化网络，采用上述建模方法初始化。

生成候选模式集，具体包括：生成候选模式；访问元素网络层的每个时间序列；存在同现关系，将对应的两个元素保存在当前候选模式列表中；根据当前候选列表连接生成多元素候选模式；合并各时间槽下的候选模式。

计算模式支持度及空间频繁度，具体包括：统计模式各元素的实例支持数；计算各元素的实例支持度，各元素实例支持度的最小值为当前时间槽下该模式的空间频繁度；保存各时间槽下各模式的空间频繁度。

计算时间频繁度，具体包括：统计同现时间槽数；统计模式有效时间槽数；计算模式时间频繁度。

计算模式权重特征值，具体包括：计算模式特征值；模式按照权重值排序；删除权值为0的模式；排序后若链表中某一个模式的权重值为0，则其后的模式的权重值也为0。

输出时空同现模式链co-occurrence_pattern_list。

(2)同现模式挖掘具体步骤

①初始化时空网络。首先读取数据集，确定数据集中各时空对象类型的存在周期；然后将数据格式处理成{实例编号，元素类型，位置信息，时间信息}的格式；再根据给定时空距离阈值，确定时间槽中各实例之间的邻近关系；最后遍历各时间槽的邻近关系，建立实例网络层，并根据实例网络层中各结点的类型属性，构建元素网络层。实例网络层使模式支持度以及空间频繁度的计算速度加快，元素网络层支持时间频繁度的快速计算，从而加快了整体计算速度。图7给出了初始化时空网络流程图。

本实施例设计了双层网络来存储元素实例间的时空关系以及元素类型之间的时空同现关系，相比传统方法的计算方式，实例网络层的建立使得同现模式的模式支持度以及空间频繁度的计算速率有了一定提高，根据实例网络层建立的元素网络层，可以较方便地计算同现模式的时间频繁度，从时空数据集中发现时空同现模式的整体计算效率有了一定提高。另外，这种双层网络模式仅在首次对时空数据集建模时消耗大量时间，时空网络建立以后，本实施例对该模式进行了保存，后续若再需要使用该数据集进行多次同现模式发现，不需要重复建模，只需要读取首次使用时保存的时空网络，这种方式在多次针对同一数据集进行同现模式发现时，进一步提高了同现模式的发现效率。

②计算候选模式的模式支持度。对于一个模式，选择模式中未计算模式支持度的一个类型，统计该类型的全部实例数，以及该类型支持模式构成的实例数，求出当前类型的模式支持度，重复上述过程，可以计算所有类型的模式支持度。元素网络层保存了时空对象类型之间是否有过同现关系，根据类型之间的边的序列选出候选模式集。通过元素网络层产生的候选模式集，其数量要比直接通过组合产生的模式集要小很多，减少了大量计算。图8给出了模式支持度计算流程图。

计算模式支持度主要的操作是访问元素网络层和实例网络层。传统方法中候选集的产生首先是将时空数据集中的所有元素进行组合，再计算组合出来的所有模式的时空频繁度。由于本实施例中对数据进行了建模，元素网络层保存了元素之间是否有过同现关系，因此可以直接访问元素网络层，根据元素之间的边的序列选出候选模式集。该候选模式集中至少可以保证模式在某一时间槽下出现过同现实例，其模式是有一定计算价值的，而且通过元素网络层产生的候选模式集，数量要比直接通过组合产生的模式集要小很多，传统模式产生的候选集出现了大量在所有时间槽内未存在同现关系的模式，这些模式的相关计算是没有意义的，因此本实施例在计算时空同现模式的过程中，采用元素网络层，降低了候选模式集的产生，减少了大量计算，在一定程度上提高了同现模式的计算效率。

③计算各模式在各时间槽的空间频繁度。模式在其时间框架下，各时间槽的空间频繁度值不同，当该模式中所有元素类型都处于有效状态时，该模式的计算才有意义。对于一个未计算模式支持度的候选模式，首先求出该模式的时间框架，然后依据模式支持度求出时间框架下各时间槽内的空间频繁度。模式时间框架的引入，使得模式在该框架外不再计算模式支持度及空间频繁度，减少了空间频繁度的计算量，而且只计算有效时间槽内的兴趣度，增加了结果的有效性。图9给出了模式的空间频繁度计算流程图。

元素有元素框架，在其元素框架外，该元素类型的实例可能存在，但是已经失效，这时计算同现模式时，将其作为一个元素类型是没有价值的，因此本实施例首先计算模式中所有元素的元素框架的交集，确保模式的空间频繁度计算有意义，这个交集称为模式的时间框架。在模式的时间框架下，若某一时间槽内，模式元素的实例不存在同现关系，则将该时间槽下模式的空间频繁度记为0，在模式的时间框架外，不计算空间频繁度。模式时间框架的引入，减少了模式在各时间槽的空间频繁度计算，提高了模式计算的有效性。

④计算模式的时间频繁度。在时空双层网络中，对于任意一个模式，其模式同现的时间槽上，各类型之间的边对应的值同时为1，而且至少存在一组实例使得任意两个实例之间在实例网络层对应的边序列值也为1。对于一个候选模式，首先计算模式的时间框架中时间槽总数，然后从双层网络统计出模式同现的时间槽位数，计算得到模式的时间频繁度。双层网络的使用使得模式的时间频繁度只需查询结点之间对应时间槽位的值，加快了时间频繁度的计算，模式时间框架的引入，也使时间频繁度的计算更有价值。图10给出了模式的时间频繁度计算流程图。

在图10中，统计元素网络层模式各元素之间对应时间序列值为1，而且实例网络层存在一组实例，对应边的时间位为1，这样的时间槽是模式同现的时间槽位。由公式(5)可知，同现的时间槽位数，除以同现模式的时间框架时间槽位数，就是模式的时间频繁度。双层网络的使用使模式的时间频繁度只需查询结点之间对应时间槽位的值，加快了时间频繁度的计算，模式时间框架的引入，也使时间频繁度的计算更有价值。

⑤计算模式权重特征值，并根据特征值对同现模式集排序，筛选符合要求的模式集。权重特征值基于模式的时空特征，将模式的各空间频繁度作为模式的空间特征，模式的时间频繁度作为模式的时间特征，根据公式(6)计算所有模式的权重特征值。在计算同现模式的权重特征值后，对所有模式进行排序，采用效率较高的堆排序方法构成模式链表，根据需求输入最需要的同现模式的比例值，从模式链表中按照比例找到模式集并输出。在传统方法中，时空阈值的设定除去了大量不满足阈值的候选模式，但这些频繁度较低候选模式也出现了同现关系，直接剔除这些频繁度较低的模式可能会丢失某些具有较高价值的同现模式，因此本实施例采用模式链表保存了所有同现模式，若在实际中需要这些频繁度较低但价值较高的模式，可以很方便地从链表中获取。权重特征值的引入使时空阈值不需要预先设定，只需要指定最频繁的模式比例，就可以从模式链表中得到满足条件的时空同现模式，解决了时空阈值难以设定的问题。图11给出了同现模式挖掘流程图。

相比传统同现模式挖掘方法，本实施例提出的基于时空网络的时空同现模式挖掘方法的优越性体现在如下几个方面：①曼哈顿距离表示法的优越性使同现模式能更好地表示时空对象的实际距离；②对时空数据进行建模形成双层网络，使同现模式时空兴趣度的计算效率得到一定程度提高，而且时空网络的可重复利用性使同现模式的相关计算更加便捷；③空间频繁度及时间频繁度中采用的模式时间框架，使同现模式更贴近实际应用；④权重特征值的引入避免了需提前设定时空阈值的问题，而且在很大程度上保存了频繁率低的时空同现模式。

(3)同现模式挖掘算法分析

①建模方法的时空复杂度分析

本发明建模方法的建模过程包括实例网络层初始化及元素网络层初始化两部分。在形成实例网络层过程中，遍历元素及元素有效周期列表，只与元素个数有关，用OT表示元素个数，其时间复杂度为O(OT)，空间消耗只需要两个表示时间框架起始与结束的变量，空间复杂度为O(1)；用于保存同位信息的邻接矩阵，用T表示时间槽个数，用N表示所有对象个数，需占据空间O(N*N)。在创建实例网络层的过程中，需要计算每个时间槽下对象之间的距离，并判断是否同位，该环节在最坏情况下的时间复杂度为O(T*N*(N+1)/2)，而且该过程只需要一个额外的存储空间来暂存计算距离，空间复杂度为O(1)。因此实例网络层形成的时间复杂度为：O(OT+T*N*(N+1)/2)，空间复杂度为O(N*N)。在元素网络层的生成过程中，需要遍历一遍实例网络层，根据实例网络层的时间序列设置元素网络层的时间序列，其时间复杂度为O(T*N*(N+1)/2)，保存元素网络层时间序列的矩阵需占据空间O(OT*OT)。

初始化过程中，总的时间复杂度为：O(OT+T*N*(N+1)/2)+O(T*N*(N+1)/2)＝O(OT+T*N*(N+1))，总的空间复杂度为：O(N*N)+O(OT*OT)＝O(N*N+OT*OT)，时间复杂度与元素类型个数、时间槽数、对象实例个数有关，空间复杂度与元素类型个数及对象实例个数有关。在对象个数远大于元素类型数时，时间复杂度约为O(N²)，空间复杂度约为O(N²)。

在最坏情况下，候选模式的生成时间复杂度为O(OT*OT)，所需空间复杂度为O(L)，L表示模式链表的长度，在计算模式支持度及空间频繁度过程中，直接从实例网络层读取相应的同位信息并进行统计计算，不需要遍历全部数据集，其时间复杂度为O(L)，在计算过程中最多需要T个存储空间保存各时间槽的空间频繁度，因此空间复杂度为O(T*L)；在计算时间频繁度时，需要访问各时间槽下模式的空间频繁度，其时间复杂度为O(T*L)，需要为各模式开辟存储空间存储模式的时间频繁度，空间复杂度为O(L)，最后计算模式的权重特征值，将时间频繁度及空间频繁度作为特征组，其计算时间复杂度为O(L)，而且链表中各模式的计算结果都需要保存，因此其空间复杂度为O(L)，在算法实现过程中，采用高效排序算法进行模式的排序，其时间复杂度为O(Llog₂L)，空间复杂度为O(log₂L)。从初始化到时空同现模式链表的最终生成，忽略较小时间和空间，总的时间复杂度约为：O(OT²+T*N²)，总的空间复杂度约为O(OT²+N²+T*L)，在对象实例数远大于元素类型数的情况下，总的时间复杂度为O(N²)，空间复杂度为O(N²)，由此可以看到，算法的时空消耗主要发生在初始化建模过程。相比传统方法的时间复杂度O(2^N)及空间复杂度O(2^N)，在数据量较大时，本发明所提出的基于时空网络的时空同现模式挖掘方法明显提高了效率。

如图12所示，建模时间与时空同现模式挖掘总的时间相比，在数据量较大时，挖掘算法的性能消耗主要是建模过程，与上述分析的结果一致，当对象个数远大于类型数时，算法总的时空复杂度与建模过程的时空复杂度是一个数量级，而实际时空计量度的计算所消耗的时间占比很小。而且建模结果可以保存再复用，当有新的对象加入到数据集中，不需要重新建模，只需要在网络中增加相应节点，并更新时间序列即可。

②时空同现模式挖掘算法分析

在时空网络初始化后，时空同现模式挖掘算法主要进行候选模式集生成、模式支持度及空间频繁度计算、时间频繁度及权重特征值计算四部分。候选模式集从元素网络层出发，遍历元素网络层生成二元候选模式，由于元素网络层中保存的元素间的时间序列依据实例网络层生成，而在实例网络层，各对象之间的时间序列由原始时空数据的时空关系直接计算决定，而且在计算过程中对各时间槽内的全部元素进行了计算，因此实例网络层存储的时空信息是可靠、全面的。实例网络层中的时间序列中为1的位，是在各时间槽内存在同现关系的位，由此实例网络层生成的元素网络层，其对应的时间序列也是元素之间在各时间槽是否同现的具体体现，实例网络层的可靠保证了元素网络层存储的同现信息的可靠性。在各时间槽内，元素网络层根据时间序列中时间位为1的同现元素，筛选出的候选模式是当前时间槽内的全部二元同现模式，多元模式在二元模式集的基础上采用连接生成，合并各时间槽内的同现模式就构成了全部的候选模式。时空双层网络的可靠性保证了此候选模式集的完整性，候选模式集中的各模式，只要在某一个时间槽内出现过同现关系就会被存储在候选集中，不会遗漏部分模式，而且各模式都是有效的。

在传统方法中，直接从原始时空数据集中采用连接生成候选模式集，需要在全部的时间槽下，都计算相关时空计量度，默认在所有时间槽下，候选模式集是相同的，而本发明产生的候选模式集在不同时间槽下可能是不同的，因为在不同时间槽下时空对象的同现关系可能不同，剔除了在各时间槽下都没有同位关系的候选模式，这样就减少了候选模式的数量。在空间频繁度及时间频繁度的计算过程中，因为双层网络已经保存了对象之间及元素之间的时空同现关系，因此直接读取对应矩阵中的时间序列即可，加快了计算效率。

相比传统同现模式挖掘方法，本发明所提出的基于网络的时空同现模式挖掘算法的优越性体现在：双层网络的建模方式，提高了候选时空同现模式的时空兴趣度的计算效率；模式时间框架的引入，减少了模式的模式支持度及空间频繁度的计算量，使得空间频繁度及时间频繁度的计算更有效，挖掘得到的时空同现模式更贴近实际应用；采用权重特征值及模式链表，根据需要比例输出时空同现模式集，避免了传统方法中使用阈值造成的部分同现模式丢失问题。

③本发明算法与其他方法的比较

为验证本发明算法的效率，将本发明算法与王占全等人所提的方法以及Celik所提的方法进行了比较。Celik提出的局部时空同现模式挖掘算法考虑了同现模式中不同目标类型的生命周期，重新定义了模式的时间频繁度的计算方法，这种方式挖掘出来的时空同现模式适用性更强，是目前比较优越的算法之一。WANG等人提出的Top-k％混合时空同现模式挖掘方法，对时空数据集进行实例间空间关系的建模，一定程度上提高了同现模式挖掘效率，采用top-k％方法选择得到在时间维度下最频繁的时空同现模式集，解决了时间频繁度的设置问题。本发明以三种方法获取到全部时空同现模式集为结果，分别采用上述不同的数据集，在小数据量以及较大数据量上分别对三种方法进行测试，并取每类测试结果的平均值作为最终结果，运行效果如图13所示。

参图13所示，13a为小数据量下对象类型数对算法的影响，13b为小数据量下平均时间槽数对算法的影响，13c为较大数据量下对象类型数对算法的影响，13d为较大数据量下平均时间槽数对算法的影响。

从图13可以看到，随着对象类型的增加，本发明所提算法比WANG等人的方法以及Celik方法运行效率高，而且类型数量越大，其优越性越显著。采用平均有效周期的时间槽个数作为测量指标，随着时间槽数的增加，三种方法呈单调增加趋势，本发明算法比其他两种方法的运行时间要少。当数据量增大时，从图13可以看到，本发明算法相比其他两种方法其运行效率更有优势。WANG等人的方法仅对时空实例间的时空关系进行建模，相比本发明的双层网络，单实例网络模式在计算时空同现模式的时间频繁度中速率较低，因此运行时间要比本发明算法长。相比Celik方法，本发明的候选集从元素网络层生成，其产生的候选模式的数量，比从数据集中采用连接操作生成的候选模式集少，减少了计算量，因此本发明算法的运行效率较高。

上面所列出的一系列的详细说明仅仅是针对本发明的可行性实施方式的具体说明，它们并非用以限制本发明的保护范围，凡未脱离本发明技艺精神所作的等效实施方式或变更均应包含在本发明的保护范围之内。

对于本领域技术人员而言，显然本发明不限于上述示范性实施例的细节，而且在不背离本发明的精神或基本特征的情况下，能够以其他的具体形式实现本发明。因此，无论从哪一点来看，均应将实施例看作是示范性的，而且是非限制性的，本发明的范围由所附权利要求而不是上述说明限定，因此旨在将落在权利要求的等同要件的含义和范围内的所有变化囊括在本发明内。

Claims (8)

1.一种基于时空网络的时空同现模式挖掘方法，其特征在于，包括如下步骤：

步骤1，对时空数据集进行初始化建模，建立用以表示实例及元素之间时空关系的双层时空网络，并保存所述时空网络对应的邻接矩阵；其中，所述时空网络包括实例网络层及元素网络层，所述元素网络层用于生成候选集；

步骤2，从所述实例网络层中读取相应邻近关系序列，计算模式支持度及空间频繁度；

步骤3，从所述元素网络层读取模式的邻近关系，计算模式的时间频繁度；

步骤4，根据模式的各时间槽空间频繁度及时间频繁度计算模式的权重特征值；

步骤5，将所有同现模式按照权重特征值进行排序，根据输入的模式比例值，输出满足条件的模式集。

2.根据权利要求1所述的基于时空网络的时空同现模式挖掘方法，其特征在于，所述步骤1具体包括：

输入时空数据集，读取时空数据集的属性信息，获得各元素类型的元素周期；

将时空数据集预处理成预定格式；其中，所述预定格式的内容包括实例编号、元素类型、位置信息、时间信息；

将时空数据集中所有数据点按时间槽划分，计算各时间槽中元素实例的时空距离；其中，所述时空距离为曼哈顿距离；

获取时空距离阈值D；

获取元素实例间的时空距离小于等于阈值D，而且元素实例都处于所述元素周期的元素实例对，保存具有邻近关系的实例对；

获取各时间槽内的邻近关系；

根据获取的各时间槽内的邻近关系建立实例网络层，并采用邻接矩阵保存所述实例网络层；

根据所述实例网络层的各实例的元素类型，建立元素网络层，并采用邻接矩阵保存所述元素网络层。

3.根据权利要求2所述的基于时空网络的时空同现模式挖掘方法，其特征在于，获取各时间槽内的邻近关系包括：

当所述具有邻近关系的实例对首次出现：

将邻近关系的两个结点连接，边上的邻近系列对应的当前时间槽位设为1；

在邻近序列中在当前时间槽之前的，若是在实例对应的模式的时间框架内，设为0；

在邻近序列中在当前时间槽之前的，若不在模式的时间框架内，设为-1；

当所述具有邻近关系的实例对非首次出现：

在实例连接的边上，对应的时间槽位设为1。

4.根据权利要求3所述的基于时空网络的时空同现模式挖掘方法，其特征在于，步骤2中，所述计算模式支持度包括：

获取未计算模式支持度的元素；

统计在元素网络层中，与所述元素相连的实例总数；

统计在对应时间槽序列中为1的实例数，即实例支持数；

求出实例支持数与实例总数的比值，即所述元素的模式支持度。

5.根据权利要求4所述的基于时空网络的时空同现模式挖掘方法，其特征在于，步骤2中，所述计算空间频繁度包括：

获取未计算空间频繁度的模式；

求得所述模式中所有元素的元素框架交集，即模式的时间框架；

在时间框架下，获取未计算空间频繁度的时间槽；

求得所述时间槽下模式最小模式支持度，即模式的空间频繁度；其中，所述时间槽下若没有元素实例集在实例网络层存在同现关系，则空间频繁度为0。

6.根据权利要求5所述的基于时空网络的时空同现模式挖掘方法，其特征在于，所述步骤3具体包括：

获取未计算时间频繁度的模式；

在元素网络中，获取所述模式所有元素之间值为1的所有时间槽，即可能同现的时间槽；

用同现的时间槽数除以模式时间框架时间槽数，求得模式的时间频繁度。

7.根据权利要求6所述的基于时空网络的时空同现模式挖掘方法，其特征在于，所述步骤4具体包括：

获取未计算权重特征值的模式；

将所述模式在所有时间槽的空间频繁度作为空间特征，计算空间频繁度均值；

计算同现模式的权重特征值，公式如下：

权重特征值＝空间频繁度均值×时间频繁度。

8.根据权利要求7所述的基于时空网络的时空同现模式挖掘方法，其特征在于，所述步骤5具体包括：

采用堆排序方法按所述权重特征值对所有模式进行排序，得到模式链表；

按照需求，输入最需要的时空同现模式的比例值k；

按照比例值k，从模式链表中取排在前k的模式集，获取时空同现模式集。