事理图谱-基于轨迹数据的团体挖掘

 

1. 轨迹数据挖掘介绍

轨迹挖掘分为伴随模式挖掘、频繁模式挖掘、周期模式挖掘等不同种类。

• 伴随模式挖掘是在轨迹数据中提取伴随的移动对象，通过分析移动对象群体的行为特征和规律，可以发现时空环境中的群体。典型的伴随模式有ｆｌｏｃｋ、ｃｏｎｖｏｙ、ｇａｔｈｅｒｉｎｇ等。
• 频繁模式挖掘是从大规模轨迹数据中发现频繁时序模式，例如挖掘公共性规律或公共性频繁路径等。一般来说轨迹数据中包含了位置、时间和语义信息，所以时空轨迹频繁模式挖掘与传统的频繁序列挖掘有一定的区别。频繁模式挖掘在生活模式挖掘、地点预测、用户相似性估计等方面有很多应用。
• 移动对象经常有一些周期性的活动行为，例如购物行为、动物的定期迁移行为等，通过挖掘此类轨迹可以预测移动对象未来的行为。一般将周期模式挖掘分为完全周期模式、部分周期模式、同步周期模式、异步周期模式等。
• 伴随关系分析将采用伴随模式挖掘。

1. 伴随模式挖掘相关算法
   1. 轨迹相似度度量算法

比较经典的轨迹相似度计算方法有最长公共子序列（LCSS）、编辑距离（ED）、动态时间规整（DTW）等

• • • DTW：

将时间序列进行延伸和缩短，来计算两个时间序列性之间的相似性，将两条轨迹上的所有点进行匹配，每个点都会匹配到另一条轨迹上距离最近的点，并且同一个点可以被另一条轨迹上的多个点所匹配。

• • • LCSS：

无需匹配所有点计算相似度的情况下，可以用LCSS算法进行相似度计算，该算法可以使用动态规划的思想实现。但该算法在低精度轨迹数据集上，导致两条轨迹上只有很少的点能够匹配上，大部分的点无法匹配，导致相似度计算结果偏低。

• • • ED：

是指两个字符串之间，由一个转成另一个所需的最少编辑次数。但是时间复杂度很高。

• • • 基于以上提到的轨迹相似度计算方法，还有一种基于轨迹形状的轨迹相似度计算方法，使用轨迹点的方向向量替代具体坐标计算相似度，该算法更倾向于关注轨迹的整体形状，而不是轨迹点之间的距离。
    • 以上算法需要高精度的轨迹数据集、时间复杂度高，需要一种算法来针对低精度的稀疏的轨迹数据集，基于相似度计算的团体识别算法GMPMS (Group Movement Pattern Mining based on Similarity)。
  • 轨迹数据降噪处理

由于设备原因或者信号问题造成的轨迹数据错误采样产生了噪声点。噪声点影响后续的轨迹挖掘与分析，因此需要首先过滤掉。一般来说有中值滤波、卡尔曼滤波与粒子滤波３种方式处理噪声点，其主要思想是通过前ｎ个点的位置预测当前点的位置，通过预测值对当前点的位置进行合理修正，达到轨迹平滑的效果。

1. 1. 计算的时间复杂度

为了减少两两计算相似度的复杂度，使用频繁项集挖掘, 发掘候选团体。候选团体发现的思想是从时间和空间两个纬度对用户轨迹进行切分,找出经常在同一时间出现在同一区域的候选团体,将这些团体的集合作为候选集。

1. 基于相似度计算的团体识别算法GMPMS
   1. 数据预处理

• 数据降噪，去除噪声点（偏差较大的数据）
• 轨迹点聚合。将每个用户的轨迹分为停留点和路过点, 停留点: 时间相差15min, 距离相差200m的点的集合。聚合结果如图所示

p2和p3的聚合为一个点sp1，sp1的地理坐标用所有点的平均值，时间使用p2的时间作为sp1的起始时间，并且计算出sp1的停留时间，停留时间越长代表该点越重要。

1. 1. 时空轨迹快照

时空轨迹快照的目的是为了减少轨迹两两计算的时间复杂度

• 按时间切分

按照时间将轨迹数据切分为连续的时间快照，快照的时间间隔为T，轨迹稀疏时，T值要设置大些。如下图所示

                                                                       图3-2

                                           S表示时间片，C表示时间片中的簇

• 按照空间切分

轨迹数据被切分成时间快照后，在每个快照中使用基于密度聚类的方法（ＤＢＳＣＡＮ）来进行聚类，得到每个快照中的轨迹簇，每个时间快照可能有一个或多个簇，为接下来候选团体的发现做准备。如图3-2中，C5,1和C5,2是时间片S5中的两个轨迹簇。

• 1. 候选团体发现
• 参考“购物车分析”

“购物车分析”是数据挖掘领域中，关联规则分析的一个经典问题，其目的是从零售记录中分析出顾客经常同时购买商品的组合，挖掘出购物篮中有价值的信息。举例来说，人们经常会同时购买面包和黄油，因此这两种物品会频繁出现在同一购物清单上。通过机器学习中的频繁项集挖掘的方法可以将具有关联的物品组合找出来。

• 轨迹分析与“购物车分析”对比

以上提到的轨迹簇类似与电商中的购物车,轨迹簇中的人相当于有关联的物品。

• 采用频繁项集挖掘算法FP-growth并设置合适的阈值K和M，可以得到候选轨迹簇的集合。FP-growth算法可以在快照的轨迹簇中挖掘满足团体最小人数M和最少出现次数K的集合，并且对于集合出现次数的连续性没有限制。该算法只需要对数据集进行两次扫描即可得出频繁项集的结果，时间复杂度很低。FP-growth算法分为构建ＦＰ树和挖掘频繁项集两个步骤。
  1. 相似性度量
• 通过计算候选团体内，每个人之间的轨迹相似度Tsim。
• 采用基于轨迹质心距离的相似度计算方法，该算法更适合低经度下的轨迹相似度计算。

• 找出两条轨迹上的匹配点，将轨迹按照匹配点切分成子轨迹。之后，对于每段子轨迹，计算其轨迹上所有点的质心坐标，对比两个轨迹的质心距离，如果质心距离在阀值之内，则认为子轨迹相似。这个算法将子轨迹段上一系列的聚合为质心进行计算，减小了轨迹点不同数量和异常点造成的影响。
• 两条轨迹总相似度S=m/n, m是相似的子轨迹, n是子轨迹的数量
  1. 团体识别

通过人之间的相似度判断是否属于伴随关系，如果存在伴随关系，则认为这两个人之间存在着边相连，在一个候选集中，将存在边的人划分为同一个群体，因此一个候选集内可能存在一个或多个伴随团体。

• 基于相似度阀值的关系判别, 通过人工指定阀值，阀值需要在具体实践中调整, 适用于大团体识别
• 基于半监督学习的关系判别, 适用于小团体识别
  1. 参数设置

候选团体最小人数为2, 最少出现次数为4. 轨迹点匹配时间阀值5min, 轨迹点匹配距离阀值是1km, 子轨迹段相似的质心距离小于1km, 轨迹相似度阀值为0.5