基于位置序列的广义后缀树用户相似性计算方法

摘要：为了解决移动数据形成的轨迹间用户相似性问题，提出了一种基于位置序列的广义后缀树（LSGST）用户相似性计算方法。该算法首先从移动数据中抽取位置序列，同时将位置序列映射为字符串，完成了对位置序列的处理到对字符串处理的转化工作；然后，构建不同用户间的位置序列广义后缀树；最后，分别从经过的相似地方个数、最长公共子序列、频繁公共位置序列三方面对相似性进行具体计算。理论分析和仿真表明，该算法提出的三个计算指标在计算相似性方面具有理想的效果；除此之外，与构造后缀树的普通方法相比，时间复杂度较低；与动态规划和朴素字符串匹配方法相比，该算法在寻找最长公共子串、频繁公共位置序列时，效率更高。实验结果表明LSGST能够有效测量相似性，同时减少了寻找测量指标时需要处理的轨迹数据量，并在时间复杂度方面明显优于对比算法。

关键词：移动数据；用户相似性；位置序列；字符串匹配；广义后缀树

中图分类号： TP391

文献标志码：A

Abstract：To solve the user similarity between trajectories formed by mobility data， an algorithm based on Location Sequence Generalized Suffix Tree （LSGST） was proposed. First， the location sequence was extracted from mobility data. At the same time the location sequence was mapped to a string. The transformation from the processing of location sequence to the processing of string was completed. Then the location sequence generalized suffix tree between different users was constructed. The☿ similarity was calculated in detail from the number of similar positions， longest common subsequence and the frequent common position sequence. The theoretical analysis and simulation results show that the proposed algorithm has ideal effect in terms of similarity measure. Besides， compared to the ordinary construction method， the proposed algorithm has low time complexity. In the comparison with dynamic programming and naive stringmatching， the proposed algorithm has higher efficiency when searching for the longest common substring and frequent public position sequence. The experimental results indicate that the LSGST can measure the similarity effectively， meanwhile reduces the trajectory data when searching for the measurement index， and has better performance in time complexity.

英文关键词

Key words：mobility data； user similarity； location sequence； string matching； generalize✫d suffix tree

0 引言

本文在上述基础上，提出基于位置序列的广义后缀计算用户相似性算法。首先从原始中英全GPS轨迹中抽取位置序列，同时将其表示成字符串，将对位置序列的处理转化为了对字符串的处理；然后构造用户间位置序列广义后缀树，实现了在构造的同时对相似地方个数、最长公共子序列、频繁公共位置序列的寻找；最后，通过这三方面对相似性进行具体计算。

1 问题描述

1.1 基本定义

原始轨迹记录了移动物体的位置、时间信息，如图1所示，记录了经过位置的时刻和持续时间（通过计算相邻位置的时间差获得），从原始轨迹中抽取位置序列，只需要将时间去除即可。

位置序列获得后，需将其映射为字符串。比如，用户与字符串中的AB会混淆，是否可选用其他变量代替？LS后的字母是否应下标？可以选用其他变量。

LS后的字母是下标。

1.3 构造广义后缀树

用户位置序列映射为字符串后，构造广义后缀树，由于普通后缀树常用于处理单个字符串，而本文需要处理多条用户轨迹，即相当于处理多个字符串，因此使用广义后缀树进行处理。广义后缀树是一种压缩字典树，它将只有一个子节点的内部节点全部压缩，形成一个内部节点至少含有两个子节点的后缀树，能够处理多个字符串组的匹配问题[22]。基于后缀树基础，构造位置序列广义后缀树 （Location Sequence Generalized Suffix Tree，LSGST）实现对多个用户位置序列的处理，具体构造时利用了Ukkonen[22]构造后缀树的思想，在构造过程中通过索引对具体信息进行标记。需要用到的相关定义介绍如下。

1）对字符串进行预处理，并加入区分不同字符串和表示字符串结尾的特殊符号“#”。

2）将不同字符串按照从左至右的顺序加入后缀树，其中根节点不包含任何字符。

4）构造过程中，每加入一个字符都对每个节点进行信息的更新。

1.4 寻找相似地点及最长公共位置序列

一般情况下，用户在日常生活中共同经过的地方越多，便更可能存在某种联系。通过寻找用户经过的相似地方个数、最长公共位置序列，量化具体相似度值，值的大小揭示用户间存在的特殊联系。通过抽取的位置序列可统计出用户间的相似地方个数。传统寻找最长公共子序列方法，一般在树构造后再遍历，以寻找到深度最深且同时属于两个子串的序列，这种方法在构造、遍历阶段都花费了许多时间，复杂度较大。为了减少时间开销，提出了在构造LSGST的过程中，同时查询每个节点信息的方法，并引入参数Record记录当前位置中的最长公共子序列Record（Depth， Cover，LCS），其中LCS为用户间经过的最长公共子序列。具体寻找过程如下：

1）从根节点出发记录节点信息，Record（1，，）为信息查询的初始状态。

2）加入每个字符都分别更新每个叶子节点的信息。

3）每加入一个字符，Record中的信息都与当前字符更新信息进行比较，如果节点的深度大于Record中记录的深度，且节点覆盖度大于1，则记录当前节点对应的字符串，同时更新Record。

4）最后取出Record中的最长公共子序列信息。

1.5 挖掘频繁公共位置序列

定义5 最小出现次数。公共位置序列在整个轨迹数据库中出现的最小次数。

定义6 频率计数器。表示从根节点到某个节点的轨迹字符串在全部轨迹中出现的频率。利用公式fCount=∑ni=1index.strPosition（i）缺少内容进行计算，其中n指的是叶子节点表示的后缀在不同字符串中出现的次数。

图2描述了频率计数器在广义后缀树中的具体表示方法，其中：节点用圆圈表示，连接节点的边用字符串子串表示。每个节点记录了从根节点到该节点经过边的所有子串，每个叶子节点记录了字符串对应的不同后缀，且每个节点记录了节点编号和频率计数器，以（strID：fCount）的形式来表示，当频率计数器的值大于等于最小出现次数时，该节点所对应的子序列才能被选择出来。例如，设置最小出现次数为3，则在是否错误，应为图2？为图2。

算法1描述了具体寻找♀频繁公共位置序列的方法，其中：1）～6）行将位置序列转化为字符串，并构造广义后缀树；第8）～14）行，首先寻找频率计数器大于最小出现次数的节点，然后比较节点间频率计数器的大小，寻找频率计数器最大的节点，最后在频率计数器最大的节点中分别比较该节点表示的序列长短，若长度大于最小序列长度，则将该序列加入到频繁公共位置序列集合中。

2 相似性测量

从两个用户经过的相似地方个数、最长公共位置序列和频繁公共位置序列三方面对不同用户间的相似性进行具体计算。

2.1 相似地方个数相似性

计算两个用户经过的相似地方不考虑位置的顺序性，只考虑两条轨迹中出现相似地方的个数，将经过的多个相似地方累加，能够得到一个测量指标，具体如式（1）所示。其中：LocationNumi表示位置i在具体轨迹中出现的次数；P、Q分别表示轨迹P、Q中总位置个数。计算位置i在轨迹P、Q中出现的频率，能够统计出共同出现在两条轨迹中的所有位置频率，lSim（P，Q）值越大，表示两条轨迹中经过的相似地方个数越多。

2.2 MLength最长公共位置序列相似性

利用广义后缀树能够寻找到轨迹间的最长公共位置序列，当计算相似性时，有两方面需要考虑：一是最长公共位置序列MLength的个数；二是不同轨迹的长度，即轨迹包含的位置个数。通过这两个指标来衡量，考虑原始轨迹长度的原因是，当轨迹较长时，位置点信息较多，能够获得MLength的可能性更大，因此通过它来调节不同轨迹的平衡性，使结果更加真实合理。具体通过下列公式进行计算。

2.3 频繁公共位置序列相似性

除了上述两种相似性测量之外ฏ，还利用频繁公共位置序列对轨迹间相似性进行测量。首先记录出现频率最高的公共子序列，然后利用式（5）对具体相似性进行计算，其中：Maxfre表示轨迹对间最大频率，Ratio（MLen是否代表MLength，为什么式中等式两边形式不统一？的，代表M-Length公式中出现的M-Len都代表M-Length，等式两边形式不一，是因为当初在排版的时候，M-Length太长，导致公式超出页面大小，所以用M-Len来代替了M-Length。

3 实验结果分析

3.1 数据预处理

数据集记录了反映用户日常行为的连续数据和位置注释信息，将位置信息按时间排列，形成用户轨迹。抽取位置序列时，发现用户注释的位置名称多样化，如对多媒体实验室的注释，在数据集中出现“ML”“Media Laboratory”等，公园街的注释出现“Park St”“Prkst”等，预处理阶段，将多样化的词都用同一个词来表示。除此之外，许多注释并不代表一个地方，而是代表某个区域，这个区域由于覆盖范围广，并不知道具体位置，为了解决这个问题，使用这个词作为查询关键词，并在谷歌地图中查询，如“Park St”代表一个区域，它所在的区域通过查询能够获得“{车站，教堂，餐厅}”等位置序列，因此将数据集中“Park St”以“{车站，教堂，餐厅}”来表示，如图3所示。

3.2 时间复杂度分析

对于长度分别为m、n的字符串M和N，通常采用动态规划和朴素字符串匹配寻找最长公共子串，其中动态规划通常需要构造一个二维表，且表中含有mn项，利用递推方式寻找最长公共子串，其时间复杂度为O（mn）；朴素字符串匹配则通过移动步长进行寻找，其时间复杂度为O（（n-m+1）m）；利用广义后缀树寻找最长公共子串，由于在构造树时就已经对最长公共子串、频繁公共子序列进行了寻找，因此其时间复杂度也就是构造广义后缀树方法的复杂度O（n）。这三种方法中，最后一种时间复杂度最低。除此之外，对于处理多个字符串卐组问题，广义后缀树的时间复杂度为线性，而其他两种方法的时间开销则会根据字符串长度的增加而变大。 3.3 相似性计算

为了度量用户相似度具体值，分别从提出的三个角度进行计算，表1列出了不同长度的轨迹间，经过相似地方时相似度的值，以序列长度14作为比较基准，表中seqL、sameP、freApp、nlSim、lSim分别表示序列长度、相同地方个数、相同地方出现次数、不考虑序列长度时相似度值、考虑序列长度时相似度值。从表1中可以看出，不考虑位置序列长度时，相似度值根据经过的相似位置个数和出现频率获得，呈递增趋势；考虑位置序列长度时，相似度值除了依靠相似地方的个数和出现频率之外，还根据长度来决定，其值并没有出现某种递增趋势。如序列长度为73的轨迹，在和序列长度为48的轨迹进行相似度比较时，尽管其序列长度较长，但当经过相同地方个数相同时，其相似度值却相对较低。由于实际情况中，不同用户经过的位置序列长度不同，使得测量过程中出现不平衡现象，在相似度计算时，考虑长度能够减弱这种不平衡，使得相似度值更加合理。

表3通过轨迹间频繁位置序列计算相似度，从表中可以看出，考虑轨迹长度时，频率相似度在出现频率很高的情况下也不一定值最大，它和序列出现的频率、长度都有关。

从表1～3中可以看出，三种相似度值并没有呈现一种规律性变化，因为影响相似度值的因素很多，其值不会按照一定指标增长或减少。除此之外，基于频繁公共位置序列的相似度值略高于其他两种，这是因为在日常生活中，当人们频繁经过相似位置序列时，更有可能存在某种关系，如学生通常都以“寝室―实验室―食堂―宿舍”这样的位置序列出现。

4 结语

通过构造的位置序列广义后缀树对用户间相似性进行具体测量，首先通过映射方法将位置序列问题转化为字符串匹配问题，在此基础上，构造用户间位置序列广义后缀树，并在构造的同时寻找相似地方个数、最长公共子序列、频繁公共子序列，然后从这三方面测量具体相似度值。实验表明，从三个角度都能够对相似性进行很好的测量。然而本方法也存在一些不足，在对位置序列进行抽取时，选用的是具有注释位置的数据集，在抽取位置序列的工作上没有具体优化。除此之外，三种相似度测量指标间的比较体现不清晰。下一步的工作，将要对抽取位置序列工作进行算法修改，使得本方法能够应用于不同形式的移动数据集；同时将以实际移动轨迹（物理意义上的）的相似性作为参照，比较三种相似度测量指标。

参考文献：

[8]PARK S， CHU W W， YOON J， et al. Efficient searches for similar subsequences of different lengths in sequence databases [C]// Proceeding of the 16th International Conference of Data Engineering.

Piscataway： IEEE， 2000： 23-32.

[9]CAI Y， NG R. Indexing spatiotemporal trajectories with Chebyshev polynomials [C]// Proceedings of 2004 ACM SIGMOD International Conference on Management of Data. New York： ACM， 2004： 599-610.