基于R-tree的高效异常轨迹检测算法  

EFFICIENT OUTLIER DETECTION ALGORITHM FOR TRAJECTORY BASED ON R-TREE

作　　者：陈锦阳[1,2] 刘良旭[2] 宋加涛[2] 王让定[1] 管博[2] 

机构地区：[1]宁波大学信息科学与工程学院,浙江宁波315211 [2]宁波工程学院电子与信息工程学院,浙江宁波315016

出　　处：《计算机应用与软件》2011年第10期34-37,共4页Computer Applications and Software

基　　金：国家自然科学基金(60972163);宁波市自然科学基金(2009A610090)

摘　　要：异常检测是一种流行的数据挖掘任务,但是轨迹数据的异常检测的研究比较少,而且存在的算法也较有局限性,因此J.-G Lee等人提出了TRAOD算法。该算法能够有效地检测出异常的轨迹,但是也存在着缺陷。它的复杂度和准确度比较难平衡,在参数的选取上也比较难,算法的运行时间较长。基于TRAOD的问题,提出一种基于R-tree的高效的异常轨迹检测算法R-TRAOD。该算法通过R-tree对轨迹点进行索引搜索其领域内的轨迹点,然后根据TRAOD算法对R-tree索引出来的轨迹点进行异常轨迹的检测,这样可以提高算法的运行速度。真实数据实验测试表明,该算法比最新的TRAOD异常轨迹挖掘算法效率要高。Outlier detection is a popular data mining task.However,there is a lack of serious study on outlier detection for trajectory data,and the existing algorithms also have the limitations.So J.-G Lee et al proposed TRAOD.TRAOD can effectively detect the abnormal trajectory,but it also has the defects.It is difficult to balance the accuracy and the complexity,the parameter selection is a little bit difficult too,the algorithm needs a long time to execute.Based on TRAOD＇s problems,this paper proposes the R-TRAOD,it is an efficient outlier detection algorithm based on R-tree trajectory.The algorithm indexes the trajectory points through R-tree for searching the trajectory points within the territory of their domain,then according to TRAOD it detects the abnormal trajectory against the trajectory points indexed by R-tree.In this way the operation speed of the algorithm can be improved.The test of real data experiments shows that this algorithm has higher efficiency than the latest TRAOD abnormal trajectory mining algorithm.

关 键 词：R-TREE 异常轨迹检测 TRAOD 

分 类 号：TP301.4[自动化与计算机技术—计算机系统结构]