基于滑动窗口的分布式轨迹流聚类

摘要

随着移动定位技术的蓬勃发展和移动定位设备的广泛应用,衍生了海量移动对象的位置信息.该类位置信息包含地理坐标、速度、方向以及时间戳等信息,被实时采集且持续增加,形成了大规模高速的分布式轨迹数据流.及时、有效地对分布式的轨迹流数据进行在线聚类分析,可以实时获取移动对象的共同移动趋势.由于轨迹数据流固有的海量、高速、偏态分布、时变进化且存在概念漂移的特性以及在线聚类的严格时空开销需求,基于静态轨迹数据的聚类方法不能直接应用于分布式轨迹流的在线聚类分析.分布式的轨迹流聚类研究面临巨大挑战,研究工作仍处于初期探索阶段.为解决上述问题,面对地理上分散采集的轨迹流数据,亟需设计高效的并行聚类分析任务及确保传输开销最小化的通信机制来满足低处理延迟的实时聚类需求.该文首先设计了分布式聚类概要数据结构以实时获取相似轨迹簇的时空特征,继而维护持续进化的分布式轨迹数据流.在此基础上,以减少通信开销提高分布式轨迹流聚类效率为目标,提出了一个在线处理分布式轨迹数据流的增量聚类算法(OCluDTS).OCluDTS方法使用基于滑动窗口模型的两层分布式框架,通过多个远程节点并行聚类局部轨迹流以及协调者节点合并局部聚类结果的方式,确保分布式轨迹流聚类获得与集中式方法相同的精度.此外,为了进一步降低OCluDTS算法的总执行开销,提出了仅限于聚类更新的远程节点传输聚类结果给协调者节点以及基于协调者节点相似性计算的剪枝策略等优化措施.最后,理论分析以及基于真实轨迹数据集的实验结果验证了OCluDTS算法处理大规模分布式轨迹流数据时的有效性和高效性.