Computer Engineering and Applications ›› 2016, Vol. 52 ›› Issue (7): 74-78.

Previous Articles     Next Articles

Clustering algorithm for moving objects based on road network

WANG Jinfeng, XING Changzheng   

  1. School of Electronic and Information Engineering, Liaoning Technical University, Huludao, Liaoning 125105, China
  • Online:2016-04-01 Published:2016-04-19

基于道路网络的移动对象聚类

王金凤,邢长征   

  1. 辽宁工程技术大学 电子与信息工程学院,辽宁 葫芦岛 125105

Abstract: Existing objects based on road network clustering algorithm eb-cls uses the network distance to describe similarity between moving objects. It does not make full use of time and space properties of the objects, which may lead to the algorithm can’t reflect the movement pattern of mobile object dynamic evolution, frequently updated clustering results, not satisfactory clustering accuracy, low efficiency and so on. Aimed at these deficiencies, this paper puts forward the Moving Objects Based on Road Network (MOBORN) clustering algorithm. It introduces the similarity coefficient of time and space, takes the speed, the direction and the position of mobile object into account. When the similarity coefficient of space and time between moving objects reach to the given threshold, it assigns them to the same cluster, and at the same time, dynamically maintenances clustering results, reduces the time of clustering. The experimental results show that the algorithm achieves 97% accuracy and 40% higher efficiency for clustering moving objects in real road network than the eb-cls algorithm.

Key words: road network, moving objects, clustering, temporal and spatial similarity coefficient, data mining

摘要: 现有的基于道路网络对象聚类算法eb-cls采用网络距离描述移动对象间的相似性,没有充分利用对象的时间和空间属性,造成算法不能体现移动对象动态演化的移动模式,频繁更新聚类结果并且聚类精度不理想,执行效率低等问题。针对这些不足,提出基于道路网络的移动对象聚类算法MOBORN(Moving Objects Based on Road Network),该算法引入时空相似系数,考虑了移动对象速度、方向和位置。当移动对象间的时空相似系数达到给定阈值,将其分到同一聚类,并动态维护聚类结果,减少聚类次数。实验结果证明,与eb-cls算法相比,该算法聚类精度保持在97%以上,运行效率提高了40%。

关键词: 道路网络, 移动对象, 聚类, 时空相似系数, 数据挖掘