一种轨迹数据中的频繁子轨迹查找方法及装置

摘要

本发明适用于数据处理技术领域，提供了一种轨迹数据中的频繁子轨迹查找方法及装置，包括：分离轨迹数据中的空间信息和时间信息；将所述空间信息编码成第一类字符，每个所述第一类字符用于表示一个地理位置；将所述时间信息编码成第二类字符，每个所述第二类字符用于表示一段间隔时间；根据编码成所述第一类字符的所述空间信息和编码成所述第二类字符的所述时间信息，建立广义后缀树；查找所述广义后缀树中的频繁子字符串；将查找出的所述频繁子字符串转换成频繁子轨迹。本发明通过使用较为高效的字符串算法来处理较为复杂的多维数值数据，使得整个频繁子轨迹查找过程的计算复杂度大大降低。

说明书

技术领域

本发明属于数据处理技术领域，尤其涉及一种轨迹数据中的频繁子轨迹查找方法及装置。

背景技术

轨迹数据就是时空环境下，通过对一个或者多个移动对象运动过程的采样所获得的数据信息，包括采样点位置、采样时间、速度等，这些采样点数据信息根据采样先后顺序构成了轨迹数据。常见的轨迹数据包括车辆行驶轨迹、移动互联网用户的旅行轨迹、移动互联网用户的签到轨迹，等等，海量的轨迹数据里蕴含着丰富的信息，其频繁子轨迹可以表现大多数人的行为模式及习惯，或者表现气候的变化规律等。

由于轨迹数据是数值数据，不能直接套用目前已相当成熟的字符串频繁子串的查找算法来查找轨迹数据中的频繁子轨迹，因此，现有技术中大多直接对轨迹数据进行划分并聚类，将长度为O(n)的轨迹划分为O(n²)个子轨迹，再对这些子轨迹进行聚类分析来发现频繁子轨迹，整个过程计算复杂度高，运算时间长。

发明内容

本发明实施例的目的在于提供一种轨迹数据中的频繁子轨迹查找方法，旨在解决现有的在轨迹数据中查找频繁子轨迹的算法计算复杂度高的问题。

本发明实施例是这样实现的，一种轨迹数据中的频繁子轨迹查找方法，包括：

分离轨迹数据中的空间信息和时间信息；

将所述空间信息编码成第一类字符，每个所述第一类字符用于表示一个地理位置；

将所述时间信息编码成第二类字符，每个所述第二类字符用于表示一段间隔时间；

根据编码成所述第一类字符的所述空间信息和编码成所述第二类字符的所述时间信息，建立广义后缀树；

查找所述广义后缀树中的频繁子字符串；

将查找出的所述频繁子字符串转换成频繁子轨迹。

本发明实施例的另一目的在于提供一种轨迹数据中的频繁子轨迹查找装置，包括：

分离单元，用于分离轨迹数据中的空间信息和时间信息；

第一编码单元，用于将所述空间信息编码成第一类字符，每个所述第一类字符用于表示一个地理位置；

第二编码单元，用于将所述时间信息编码成第二类字符，每个所述第二类字符用于表示一段间隔时间；

建立单元，用于根据编码成所述第一类字符的所述空间信息和编码成所述第二类字符的所述时间信息，建立广义后缀树；

查找单元，用于查找所述广义后缀树中的频繁子字符串；

转换单元，用于将查找出的所述频繁子字符串转换成频繁子轨迹。

本发明实施例结合了数据挖掘技术、后缀树算法以及非精确匹配，从而实现了较优的轨迹数据中的频繁子轨迹的查找，通过使用较为高效的字符串算法来处理较为复杂的多维数值数据，使得整个频繁子轨迹查找过程的计算复杂度大大降低。

附图说明

图1是本发明实施例提供的轨迹数据中的频繁子轨迹查找方法的实现流程图；

图2是本发明实施例提供的轨迹数据中的频繁子轨迹查找方法S102的具体实现流程图；

图3是本发明实施例提供的轨迹数据中的频繁子轨迹查找方法对空间信息进行聚类的示意图；

图4是本发明实施例提供的轨迹数据中的频繁子轨迹查找方法S103的具体实现流程图；

图5是本发明实施例提供的轨迹数据中的频繁子轨迹查找方法建立的广义后缀树的示意图；

图6是本发明实施例提供的轨迹数据中的频繁子轨迹查找装置的结构框图。

具体实施方式

为了使本发明的目的、技术方案及优点更加清楚明白，以下结合附图及实施例，对本发明进行进一步详细说明。应当理解，此处所描述的具体实施例仅仅用以解释本发明，并不用于限定本发明。

图1示出了本发明实施例提供的轨迹数据中的频繁子轨迹查找方法的实现流程，详述如下：

在S101中，分离轨迹数据中的空间信息和时间信息。

轨迹数据中包括了空间信息和时间信息，其中，空间信息一般包括所在位置的经度、纬度等，而时间信息通常通过unix时间戳进行表示。

表1为一段轨迹数据的具体示例，其中，记录的时间信息为进入对应的经度及纬度的unix时间戳：

表1

在S101中，首先对轨迹数据中的空间信息和时间信息进行分离，将轨迹数据分离成一个空间信息序列，例如{(113.333,22.368),(113.111,23.013)…}，以及一个时间信息序列，例如{1385521584,1385521233…}。

在S102中，将所述空间信息编码成第一类字符，每个所述第一类字符用于表示一个地理位置。

在本实施例中，对S101分离出的空间信息进行聚类，转化成相应的地理位置，再编码成字符，且编码成的字符用于表示对应的地理位置。如图2所示，S102具体为：

在S201中，对所述空间信息进行聚类，生成N个簇，所述N为大于1的整数。

根据S101中分离出的轨迹数据的空间信息序列，基于经度和纬度将轨迹数据的空间信息进行聚类。具体地，可以采用基于密度的聚类算法（Density-BasedSpatial Clustering of Applications with Noise，DBSCAN）来实现空间信息的聚类。作为本发明的一个实现示例，如图3所示，其中的每一个点表示空间信息序列中的一个记录，基于这些点对应的经度数值和纬度数值对这些点进行聚类，最后生成了A、B、C三个簇，而剩余的孤立点则作为噪音被排除出去，不参与接下来的计算过程。

在S202中，分别确定生成的每个簇所对应的地理位置。

在本实施例中，根据每个簇所涉及到的经度和纬度等位置信息，通过对比地图上的位置进行判别，以确定出每个簇所对应的地理位置。通常说来，在真实的数据采集过程中，生成的簇可以代表现实社会中的一个城市或者城市里的一个商圈，等等。

在S203中，根据每个簇所对应的地理位置进行字符编码，分别生成每个簇对应的所述第一类字符。

经过图2所示步骤，轨迹数据中的空间信息例如{(113.333,22.368),(113.111,23.013)…}则会被转化成{A,C,…}，其中，A表示(113.333,22.368)所在的簇对应的字符，C表示(113.111,23.013)所在的簇对应的字符，由此实现了轨迹数据中的空间信息由原始二维数值至地理区域的转换。

在S103中，将所述时间信息编码成第二类字符，每个所述第二类字符用于表示一段间隔时间。

如图4所示，S103具体为：

在S401中，将所述时间信息由时间戳转换成间隔时间。

在S102中，已将空间信息序列已经转换成字符序列格式，而原始的时间信息是一个时间戳序列，序列里的每一个时间戳均代表进入空间信息序列中相应地理位置的时间，则在S103中，需要将时间戳转换成间隔时间，以确定出从进入A到进入B之间的时间差。例如，转换后的空间信息序列为{A,A,B,…}，对应的间隔时间序列为{t₁,t₂,t₃,…}，则进入A的时间是t₁，进入B的时间是t₃，那么从进入A到进入B之间的时间间隔是t₃-t₁。

在S402中，标准化所述间隔时间。

在S402中，对转换得到的间隔时间进行标准化之前，首先先将其中过长的间隔时间作为噪音去除，再对剩余的间隔时间进行标准化。具体地，可以通过下式对间隔时间进行标准化：

interval(k）=interval(k)/max_m＝１：ninterval(m)

其中，interval(k)表示第k个间隔时间，max_m＝1：ninterval(m)表示n个有效间隔时间里的最大值，具体的标准化方法，即是取所有有效间隔时间里的最大值，再将第k个间隔时间除以该最大值，即得到了标准化的第k个间隔时间。对于标准化的第k个间隔时间，作为本发明的一个实现示例，其结果可以精确到0.001。

通过对间隔时间进行标准化之后，所有的间隔时间就会转换成类似0.303、0.349、0.788等数值。

在S403中，为每个标准化后的所述间隔时间匹配第二类字符。

通常，可以将数值转化成字符最简单的办法是对其进行四舍五入，例如：

间隔时间1=0.349≈0.3，间隔时间2=0.350≈0.4，则根据预设的数值与字符的对应关系，将0.3转换成字符3，将0.4转换成字符4。然而，实际上，间隔时间1与间隔时间2的真实数值极为相近，但却被匹配成了不同的字符，使得匹配结果无法反映出不同数值之间的真实差距，因此，作为本发明的一个实施例，可以采用非精确匹配的办法来解决这个问题，通过非精确匹配，为每个标准化后的所述间隔时间匹配一个第二类字符的组合，所述第二类字符的组合中包含两个第二类字符。

具体地：可以采用如下的非精确匹配方法：

间隔时间1=0.349≈0.3||0.35=字符6||字符7；

间隔时间2=0.350≈0.35||0.4=字符7||字符8。

即，首先确定标准化后的间隔时间所在的预设数值区间，并确定该预设数值区间的两个数值端点，然后，根据预设的第二类字符与数值端点的对应关系，将这两个数值所分别对应的两个第二类字符匹配给该标准化后的间隔时间，从而将每个标准化后的间隔时间转换成包含了两个第二类字符的组合(字符k,字符k+1)。

在经过了S102和S103之后，轨迹数据即可以被转换成空间信息和时间信息交叉的字符串序列，例如：

A（字符6）B（字符6）C…

在S104中，根据编码成所述第一类字符的所述空间信息和编码成所述第二类字符的所述时间信息，建立广义后缀树。

后缀树（suffix tree）作为一种数据结构，能够用来支持有效的字符串匹配和查询，在本实施例中，由于时间信息是通过包含了两个第二类字符的组合来编码表示的，因此，在建树的时候，可以用第二类字符的组合中代表较小数值的那个字符来表示。例如，间隔时间1=字符6||字符7，则在建树过程中，可以用字符6来表示该间隔时间1。

在将后缀树节点上的时间信息和还未放到后缀树上的时间信息进行比较的时候，非精确匹配的具体场景如下：

节点n=字符k=字符k||字符(k+1)，

例如，节点n=字符6=字符6||字符7，即，需要比较的间隔时间被编码为字符6和字符7时，均能够匹配上字符6所对应的节点n。

而对于空间信息，仍采用精确匹配的方式来放置到后缀树上。

在本实施例中，可以采用Ukkonen算法来完成广义后缀树的建树过程，通过上述方法建立好的广义后缀树如图5所示，其中，每一个非根节点均表示一个子字符串，且通过为后缀树中的每个节点新增一个count属性，用于对该节点对应的字符串在广义后缀树中出现的次数进行计数，那么，这个子字符串出现的次数就是这个节点的所有子节点里叶节点的count属性之和：

Count(s)=count_leaf1+count_leaf2+count_leaf3+…，

其中，s表示一个字符串，而Count(s)则表示由根节点出发路径为s所到达的节点的count属性值，count_leaf1，count_leaf2，count_leaf3，…则分别代表该节点的子节点里所有叶节点的count属性值。

而反过来，每个叶节点的count属性则表示该叶节点所含二维索引的多少，设in代表一个叶节点的二维索引，则：

in=(index1,index2)，

其中，index1表示该叶节点对应的子字符串在哪一个字符串出现过，index2表示该叶节点对应的子字符串在该字符串出现的起始位置。

如图5所示，(0,5)、(1,2)是其中位于最左边的叶节点的两个二维索引，该叶节点代表的字符串是后缀“A”，则(0,5)表示的是后缀“A”在第0个字符串“BANANA”中出现且出现的起始位置为5（注:按照计算机科学的习惯，此处索引号码及位置的计数都从0开始），(1,2)则代表后缀”A”在第1个字符串”ANA”里出现且出现的起始位置为2。

在S105中，查找所述广义后缀树中的频繁子字符串。

对于S104中建立好的广义后缀树，采取广度优先遍历的办法来进行树的遍历，如果一个节点的count属性的数值满足如下条件：

Count(节点A)>min_repeat_times，其中，Count(节点A)表示广义后缀树中节点A的count属性值，min_repeat_times用于表示一预设阈值，

则该节点代表的子字符串是频繁子字符串，即，将广义后缀树中的count属性大于预设阈值的节点所对应的字符串确定为所述频繁子字符串

反之，若一个节点被判断为不是频繁子字符串，则对以节点为根的子树进行剪树，后续过程中不再遍历该节点的子节点，以此来提高频繁子字符串的查找效率。

在S106中，将查找出的所述频繁子字符串转换成频繁子轨迹。

对于S105中所查找出的频繁子字符串，如A(字符6)B(字符7)C…，可以逐个字符地将其转化为该字符代表的空间信息或者时间信息，具体地：

若该字符为第一类字符，则表示该字符代表的是空间信息，因此将该字符转化成该字符对应的地理位置；

若该字符为第二类字符，则表示该字符代表的是时间信息，因此取该字符以及该字符的邻居字符，转化成对应的数值并取均值。例如，当用第二类字符的组合中代表较小数值的那个字符来表示时间信息时，若字符为6，则其邻居字符为7，上述两个字符分别对应的数值为0.3和0.35，那么则对0.3和0.35取均值，从而还原出该时间信息。

表2示出了根据图5展示的广义后缀树最后生成的频繁子轨迹的示例：

表2

本发明实施例结合了数据挖掘技术、后缀树算法以及非精确匹配，从而实现了较优的轨迹数据中的频繁子轨迹的查找，通过使用较为高效的字符串算法来处理较为复杂的多维数值数据，使得整个频繁子轨迹查找过程的计算复杂度大大降低，且合理的聚类方法也使得本发明实施例对轨迹数据空间信息的聚类划分更加准确。

图6示出了本发明实施例提供的轨迹数据中的频繁子轨迹查找装置的结构框图，该装置可以用于运行本发明图1至图5实施例所述的轨迹数据中的频繁子轨迹查找方法。为了便于说明，仅示出了与本实施例相关的部分。

参照图6，该装置包括；

分离单元61，分离轨迹数据中的空间信息和时间信息。

第一编码单元62，将所述空间信息编码成第一类字符，每个所述第一类字符用于表示一个地理位置。

第二编码单元63，将所述时间信息编码成第二类字符，每个所述第二类字符用于表示一段间隔时间。

建立单元64，根据编码成所述第一类字符的所述空间信息和编码成所述第二类字符的所述时间信息，建立广义后缀树。

查找单元65，查找所述广义后缀树中的频繁子字符串。

转换单元66，将查找出的所述频繁子字符串转换成频繁子轨迹。

可选地，所述第一编码单元62包括：

聚类子单元，对所述空间信息进行聚类，生成N个簇，所述N为大于1的整数。

确定子单元，分别确定生成的每个簇所对应的地理位置。

编码子单元，根据为生成的每个簇所对应的地理位置进行字符编码，分别生成每个簇对应的所述第一类字符。

可选地，所述第二编码单元63包括：

转换子单元，将所述时间信息由时间戳转换成间隔时间。

标准化子单元，标准化所述间隔时间。

匹配子单元，为每个标准化后的所述间隔时间匹配第二类字符。

可选地，所述匹配子单元具体用于：

确定所述标准化后的所述间隔时间所在的预设数值区间的两个数值端点；

将所述两个数值端点分别对应的两个第二类字符匹配给该标准化后的所述间隔时间。

可选地，所述装置还包括：

增加单元，为所述广义后缀树中的每个节点增加一个计数属性，所述计数属性用于对该节点对应的字符串在所述广义后缀树中出现的次数进行计数；

所述查找单元65具体用于：

将所述广义后缀树中的所述计数属性大于预设阈值的节点所对应的字符串确定为所述频繁子字符串。

本发明实施例结合了数据挖掘技术、后缀树算法以及非精确匹配，从而实现了较优的轨迹数据中的频繁子轨迹的查找，通过使用较为高效的字符串算法来处理较为复杂的多维数值数据，使得整个频繁子轨迹查找过程的计算复杂度大大降低，且合理的聚类方法也使得本发明实施例对轨迹数据空间信息的聚类划分更加准确。

以上所述仅为本发明的较佳实施例而已，并不用以限制本发明，凡在本发明的精神和原则之内所作的任何修改、等同替换和改进等，均应包含在本发明的保护范围之内。