一种基于移动对象数据流的突发事件检测方法

摘要

本发明涉及一种基于移动对象数据流的突发事件检测方法，其步骤为：1）对移动对象时空数据流进行采集，存储移动对象的位置信息；2）以每个采样时刻为单位，挖掘当前时刻t的所有移动对象聚类，根据移动对象聚类得到一邻接表，同时更新该邻接表中的聚类间关联关系；3）根据邻接表中的链接关系在不大于t时刻内向前面的采样时刻搜索，建立滚雪球模式并挖掘出所有雪球模式的异常行为；4）根据雪球模式的异常行为检测出突发事件。本发明的方法将移动对象聚类过程和雪球模式挖掘过程联系起来，使得雪球模式的挖掘可以直接从邻接表中搜索得到，不再需要额外计算开销，从而降低了计算代价，提高了效率，同时提高了挖掘结果的有效性。

说明书

技术领域

本发明涉及灾难预警领域中的一种基于移动对象数据流的突发事件检测方法。

背景技术

近年来，我国进入了非常规突发事件的高发期，非常规突发事件带来了巨大的生命与财产损失，并伴随着深远的灾难后果。为了更好的避免灾难减少损失，灾难预警技术得到了广泛的关注与研究，其中从移动对象数据流中准确地获得实时的移动对象群体异常行为具有重要的研究与实用价值。

目前的移动对象行为模式聚类方法主要分为两大类：移动对象聚类和移动轨迹聚类，然而这些方法都不能检测出复杂群体行为的突发事件。其中移动对象聚类方法研究的是行驶过程中同行或者部分同行的移动对象群体，其中具有代表性的有Joachim Gudmundsson等提出的Flock，Hoyoung Jeung等提出的Convoy，Zhenhui Li等提出的Swarm，Lu-An Tang等提出的Companions，以及Kai Zheng等提出的Gathering等等。移动轨迹聚类研究的是移动对象群体中相似的轨迹段，其中具有代表性的有Jae-Gil Lee等提出的Partition-and-Group，Huey-RuWu等提出的Dividing-and-Clustering，以及Fosca Giannotti提出的Region-of-Interest等等。

然而，上述研究都无法表示并检测移动对象群体的异常行为。在移动对象数据流中异常行为的表示与建模、异常行为模式的挖掘和检测、原型系统的实现与性能分析等，没有得到有效的研究与解决，对这些关键技术问题有待进一步的研究。

发明内容

针对上述尚无解决的关键问题，本发明提出了一种高效、高精度、实时的基于移动对象数据流的突发事件检测方法。在本发明中，移动对象群体的异常行为被抽象为滚雪球模式的异常行为，具体来说就是移动对象群体的持续急剧增大或缩小的行为模型。本发明提出了根据雪球模式进行突发事件检测的方法，即通过移动对象聚类的急剧变化来检测突发事件。

本发明所采用的技术方案是通过采集和存储的移动对象时空数据流，然后采用基于密度的聚类算法，以每个采样时刻为单位，实时地获得移动对象聚类，并高效地检测当前移动对象中滚雪球模式的异常行为，及时预示可能发生的灾难。

本发明基于移动对象数据流的突发事件检测方法，其步骤包括：

一种基于移动对象数据流的突发事件检测方法，其步骤包括：

1）对移动对象时空数据流进行采集，存储移动对象的位置信息（t，lon，lat），其中t表示采样时刻，lon和lat分别是在采样时刻t时所述移动对象所在的经纬度；

2）以每个采样时刻为单位，挖掘当前时刻t的所有移动对象聚类，根据所述移动对象聚类得到一邻接表，同时更新该邻接表中的聚类间关联关系；

3）根据所述邻接表中的链接关系在不大于t时刻内向前面的采样时刻搜索，建立滚雪球模式并挖掘出所有雪球模式的异常行为；

4）根据所述雪球模式的异常行为检测出突发事件。

更进一步，所述雪球模式的异常行为是指找出所述移动对象时空数据流中持续急剧增大或缩小的移动对象群体异常行为。

更进一步，所述雪球模式S是由一系列有序的聚类{C₁,C₂,…,C_n}组成，其中设C_i是采样时刻t_i的移动对象聚类（其中1≤i≤n），并且S满足：

（1）雪球模式的持续时间大于给定时间阈值δ_t；

（2）S中任意相邻的两个聚类C_i和C_i+1之间满足关联关系：增大或缩小比例大于给定比例阈值δ_θ；增大或缩小速度大于给定速度阈值δ_speed。

更进一步，根据所述移动对象聚类得到一邻接表的方法如下：

1）在创建邻接表的过程中，将聚类及其之间的关系转换为有向图；

2）将每个聚类转换为有向图中的顶点，聚类之间的关联关系转化为有向图中的边，有关联关系的聚类之间相交的移动对象个数映射为有向图中的边权重；得到加权有向图G；

3）采用邻接表表示所述有向图G。

更进一步，所述移动对象聚类是由一组密集的移动对象组成的任意形状的移动对象集合C，其中C中的任意两个移动对象p、q之间都满足距离可达关系，即p，q之间存在一串移动对象Q，Q中任意相邻的两个移动对象O_i和O_i+1之间满足：

1）O_i距离可达近邻内的移动对象密度大于给定密度阈值μ；

2）O_i+1在O_i的距离可达近邻内；

所述移动对象p的距离可达近邻是一个移动对象集合N，其中N内的任意移动对象_q与p之间的距离在时间窗h内都小于给定距离阈值ε。

更进一步，所述滚雪球模式的方法如下：

1）访问当前未被访问过的移动对象o，并标记o为已访问，并且根据距离阈值ε、时间窗阈值h、及所述移动对象的位置信息找出o的距离可达近邻N；

2）若o的距离可达近邻N的移动对象个数小于给定密度阈值μ，则标记o为噪声点；若大于给定密度阈值μ，则创建新的聚类C，扩展聚类C并更新邻接表AL;

3）扫描聚类C的邻接表中所有的链接关系，删除邻接表中不满足关联关系的链接：得到更新的邻接表AL；

4）根据更新的邻接表AL，从当前时刻的聚类C开始，沿着聚类C的邻接表的链接关系往前面的时刻搜索，直至不存在链接关系为止，找出所有持续时间大于时间阈值δ_t的雪球模式的异常行为，得到当前时刻最长的雪球模式。

更进一步，所述步骤3）中采用剪枝算法删除邻接表中不满足关联关系的链接。

更进一步，所述更新邻接表AL的方法如下：

1）将移动对象o添加至聚类C中，检索上一个采样时刻o所属的聚类C'_o，在邻接表AL中创建一条从C指向C'_o的链接关系<C，C'_o>，并设置权重ω(C,C'_o)为1；

2）访问距离可达近邻N内的移动对象p，若p未被访问过，则标记p为已访问，并且根据距离阈值ε、时间窗阈值h、及移动对象的位置信息找出p的距离可达近邻N_p；若N_p内的移动对象个数大于给定密度阈值μ，则将N_p合并至N内；

3）若p不属于任何聚类，则将p添加至聚类C中，检索上一个采样时刻p所属的聚类C'_p，查找邻接表AL中是否存在链接关系<C,C'_p>；

4）若不存在，则在AL中创建新的链接关系<C,C'_p>，并设置权重ω(C,C'_p)为1；否则将权重ω(C,C'_p)增加1。

本发明使用了邻接表方法挖掘出基于移动对象数据流的滚雪球模式的突发事件，它不仅能有效地检测当前移动对象中的异常行为，而且能高效地提供实时监测。与现有的移动对象行为模式聚类方法无法检测当前移动对象中的异常行为相比，本发明具有如下优势：

（1）本发明采用邻接表存储聚类之间的关联关系，将移动对象聚类过程和雪球模式挖掘过程联系起来，使得雪球模式的挖掘可以直接从邻接表中搜索得到，不再需要额外计算开销，从而降低了计算代价，提高了效率。如图4（a）—4（b）所示，图4(a)，4(b)分别是算法执行时间与速度阈值和比例阈值的关系图，其中纵坐标runtime表示执行时间，横坐标δ_speed表示速度阈值，δ_θ表示比例阈值。本发明中基于邻接表的挖掘算法相较于未采用邻接表的算法时间效率提高了35%。

（2）本发明所挖掘的雪球模式避免了冗余的模式挖掘，挖掘出当前时刻最长的雪球模式，提高了挖掘结果的有效性。

综合以上分析，本发明可以保证突发事件检测的高效性、高准确性和实时性。该发明的最终结果可以提供给相关的用户使用，例如应急管理中心、交通控制中心、珍惜动物管理保护中心等，可以支持对移动对象群体行为的异常检测，实现对突发异常事件的及时响应及处理，最大限度地降低突发事件的灾难性后果。

附图说明

图1是距离可达近邻的示意图。

图2聚类中雪球模式的示意图。

图3（a）是图2中的聚类及其之间的关系转化的有向图，图3（b）是相应的邻接表。

图4（a）是算法的执行时间与速度阈值的关系图，图4（b）是算法执行时间与比例阈值的关系图。

图5是本发明雪球模式挖掘的流程图。

具体实施方式

下面结合附图，通过实例进一步说明本发明，但不以任何方式限制本发明的范围。

本发明的原理是：

首先需要在每个采样时刻挖掘出所有移动对象聚类，在本发明中移动对象聚类是由一组密集的移动对象组成的任意形状的移动对象集合C，其中C中的任意两个移动对象p、q之间都满足距离可达关系，即p，q之间存在一串移动对象Q，Q中任意相邻的两个移动对象o_i和o_i+1之间满足：

（1）o_i距离可达近邻内的移动对象密度大于给定密度阈值μ；

（2）o_i+1在o_i的距离可达近邻内。

移动对象p的距离可达近邻是一个移动对象集合N，其中N内的任意移动对象q与p之间的距离在时间窗h内都小于给定距离阈值ε。如图1所示，假设时间窗h等于3，移动对象o₃在t₃时刻的距离可达近邻是{o₂,o₄}，即采样时间[t₁,t₃]内o₃与o₂，o₄的距离都小于ε。

其次根据所有挖掘出的移动对象聚类，找出所有持续急剧增大或缩小的移动对象群体异常行为。雪球模式S是由一系列有序的聚类{C₁,C₂,…,C_n}组成，其中C_i是采样时刻t_i的移动对象聚类（其中1≤i≤n），并且S满足：

（1）雪球模式的持续时间大于给定时间阈值δ_t；

（2）S中任意相邻的两个聚类C_i和C_i+1之间满足关联关系，即满足增大（或缩小）比例大于给定比例阈值δ_θ以及增大（或缩小）速度大于给定速度阈值δ_speed。增大（或缩小）比例的表示方法为：|C_i∩C_i+1|/|C_i|（或|C_i∩C_i+1|/|C_i+1|）；增大（或缩小）速度的表示方法为：(|C_i+1|－|C_i|)/|C_i|（或(|C_i|－|C_i+1|)/|C_i|）。如图2所示，移动对象不断聚集，且呈现急剧增大的变化趋势。假设时间阈值δ_t等于4，速度阈值δ_speed等于0.3，比例阈值δ_θ等于0.5，则<C₁₂,C₂₃,C₃₁,C₄₁>是一个满足条件的雪球模式。

在创建邻接表的过程中，将聚类及其之间的关系转换为有向图,，其中每个聚类转换为有向图中的顶点；聚类之间的关联关系转化为有向图中的边；有关联关系的聚类之间相交的移动对象个数映射为有向图中的边权重，最后用邻接表表示有向图。为了表示移动对象聚类之间的关联关系，本发明采用加权有向图G表示聚类及其之间的关系，并用邻接表来描述G。G包含了聚类的信息V、聚类之间的关联关系E和关联关系的加权值W，即(V,E,W)。其中每个聚类信息即某个时刻的移动对象聚类C_i；每对关联关系<C_i,C_j>即两个聚类C_i和C_j之间满足关联关系；每对关联关系<C_i,C_j>的加权值即C_i和C_j之间相交的移动对象个数。如图3（a）—图3（b）所示，将图2中的聚类及其之间的关系转化为图3（a）中的有向图及图3（b）相应的邻接表。

滚雪球模式的具体挖掘过程包括：

第一步：每一个采样时刻，对当前采集和存储的移动对象时空数据流，通过基于密度的聚类算法，实时地获得移动对象聚类，并保存各个采样时刻移动对象聚类之间的关联关系，具体方法如下：

1.访问当前未被访问过的移动对象o，并扩展新的聚类及更新聚类之间的邻接表，具体扩展及更新方法如下：

⑴标记当前移动对象o为已访问，并且根据距离阈值ε、时间窗阈值h、及移动对象的位置信息找出o的距离可达近邻N。

⑵若o的距离可达近邻N的移动对象个数小于给定密度阈值μ，则标记o为噪声点。

⑶否则，创建新的聚类C，扩展聚类C并更新邻接表AL，具体方法如下：

①将移动对象o添加至聚类C中，检索上一个采样时刻o所属的聚类C_o’，在邻接表AL中创建一条从C指向C_o’的链接关系<C,C_o’>，并设置权重w(C,C_o’)为1。此处创建C与C_o’之间的链接关系，每新创建一个聚类C，就创建C与前面时刻聚类之间的链接关系。搜索雪球模式时，根据链接关系往前搜索。

②访问距离可达近邻N内的移动对象p，判断p是否能添加至聚类C中，并更新对应的邻接表AL，具体方法如下：

·若p未被访问过，则标记p为已访问，并且根据距离阈值ε、时间窗阈值h、及移动对象的位置信息找出p的距离可达近邻N_p。若N_p内的移动对象个数大于给定密度阈值μ，则将N_p合并至N内。

·若p不属于任何聚类，则将p添加至聚类C中，检索上一个采样时刻p所属的聚类C_p’，查找邻接表AL中是否存在链接关系<C,C_p’>。若不存在，则在AL中创建新的链接关系<C,C_p’>，并设置权重w(C,C_p’)为1；否则将权重w(C,C_p’)增加1。

2.扫描聚类C的邻接表中所有的链接关系<C,C’>，删除邻接表中不满足关联关系的链接，具体剪枝方法如下：

⑴判断聚类增大（或缩小）比例是否大于给定比例阈值δ_θ，即|C∩C’|/|C’|（或|C∩C’|/|C|）是否大于δ_θ，δ_θ的值根据应用场景不同可选择不同的值。例如，在研究水牛群体的迁徙行为中，δ_θ的取值范围可以选择（0.5，0.9）；在监测交通状况变化趋势时，δ_θ的取值范围可以选择（0.75，0.95）。⑵判断聚类增大（或缩小）速度是否大于给定速度阈值δ_speed，即(|C|－|C’|)/|C’|（或(|C’|－|C|)/|C’|）是否大于δ_speed，δ_speed的值根据应用场景不同可选择不同的值。例如，在研究水牛群体的迁徙行为中，δ_speed的取值范围可以选择（0.5，0.6）；在监测交通状况变化趋势时，δ_speed的取值范围可以选择（0.1，0.5）。

⑶若上述判断都满足，则保留链接关系<C,C’>；否则，删除链接关系<C,C’>。

第二步：根据第一步中更新的邻接表，从当前时刻的聚类C开始，沿着聚类C的邻接表的链接关系往前面的时刻搜索，直至不存在链接关系为止，找出所有持续时间大于时间阈值δ_t的雪球模式的异常行为，得到当前时刻最长的雪球模式。

当前场景如图2所示，服务器端收集了t₁至t₄四个时刻的移动对象及其位置信息，假设当前时刻是t₄时刻，根据图5所示的流程进行如下具体操作：

1.利用时间窗找出位置关系更紧密的距离可达近邻，即动态可达近邻，再采样基于密度的聚类方法，挖掘出当前时刻所有的移动对象聚类，具体方法如下：根据距离阈值ε、时间窗阈值h、密度阈值_μ及移动对象的位置信息找出t₄时刻的所有移动对象聚类。

例如：当前时刻t₄的移动对象聚类包括C₄₁={o₁,o₂,…,o₁₃}，而其前面时刻的移动对象聚类分别是：t₃时刻的移动对象聚类包括C₃₁={o₁,o₂,…,o₇}、C₃₂={o₈,o₉,…,o₁₃}；t₂时刻的移动对象聚类包括C₂₁={o₁,o₂}、C₂₂={o₃,o₄,o₅,o₈}、C₂₃={o₆,o₇,o₉,o₁₀}、C₂₄={o₁₁,o₁₂,o₁₃}；t1时刻的移动对象聚类包括C₁₁={o₃,o₄,o₈}、C₁₂={o₇,o₉}、C₁₃={o₁₁,o₁₂}。

2.创建并扩展当前时刻t₄的移动对象聚类的同时，创建新聚类的邻接表，并更新聚类之间关联关系的权重值。

例如：当前时刻新创建的聚类C₄₁的邻接表如图3(b)所示，创建C₄₁的邻接表及其链接关系：<C₄₁,C₃₁>及W(C₄₁,C₃₁)=7；<C₄₁,C₃₂>及W(C₄₁,C₃₂)=6。

3.删除新创建的邻接表中不满足关联关系的链接关系。

例如：假设比例阈值δ_θ为0.5，速度阈值δ_speed为0.3。则链接关系<C₄₁,C₃₁>和<C₄₁,C₃₂>都满足关联关系。

4.搜索当前时刻t₄的邻接表，根据邻接表的链接关系，往前搜索邻接表，直至没有链接关系为止，找出t₄时刻所有满足要求的雪球模式。

例如：假设时间阈值δ_t为4，搜索路径如表1所示根据邻接表找出雪球模式的搜索路径，从当前时刻的C₄₁的邻接表开始搜索，沿着邻接表的链接关系依次找到<C₄₁,C₃₁>和<C₄₁,C₃₂>；再根据C₃₁与C₃₂的邻接表的链接关系依次往前搜索，直至没有链接关系为止。可以看出，满足时间阈值的雪球模式共有4个，分别是：<C₄₁,C₃₁,C₂₂,C₁₁>、<C₄₁,C₃₁,C₂₃,C₁₂>、<C₄₁,C₃₂,C₂₃,C₁₂>和<C₄₁,C₃₂,C₂₄,C₁₃>。

表1

以上通过实施例对本发明进行了详细的描述，本领域的技术人员应当理解，在不超出本发明的精神和实质的范围内，对本发明做出一定的修改和变动，比如移动对象聚类过程中可以使用其他聚类方法代替本发明中基于密度的聚类方法，如k-means聚类方法，仍然可以实现本发明的目的。