基于Rtree的高效异常轨迹检测算法.pdfVIP

第２８卷第１０期　　　 计算机应用与软件 Ｖｏｌ２８Ｎｏ．１０ ２０１１年１０月　　 ＣｏｍｐｕｔｅｒＡｐｐｌｉｃａｔｉｏｎｓａｎｄＳｏｆｔｗａｒｅ Ｏｃｔ．２０１１ 基于Ｒｔｒｅｅ的高效异常轨迹检测算法 １，２ ２ ２ １ ２ 陈锦阳 　刘良旭 　宋加涛 　王让定 　管　博 １（宁波大学信息科学与工程学院　浙江宁波３１５２１１） ２（宁波工程学院电子与信息工程学院　浙江宁波３１５０１６） 摘　要　　异常检测是一种流行的数据挖掘任务，但是轨迹数据的异常检测的研究比较少，而且存在的算法也较有局限性，因此Ｊ． ＧＬｅｅ等人提出了ＴＲＡＯＤ算法。该算法能够有效地检测出异常的轨迹，但是也存在着缺陷。它的复杂度和准确度比较难平衡，在 参数的选取上也比较难，算法的运行时间较长。基于ＴＲＡＯＤ的问题，提出一种基于Ｒｔｒｅｅ的高效的异常轨迹检测算法ＲＴＲＡＯＤ。 该算法通过Ｒｔｒｅｅ对轨迹点进行索引有哪些信誉好的足球投注网站其领域内的轨迹点，然后根据ＴＲＡＯＤ算法对Ｒｔｒｅｅ索引出来的轨迹点进行异常轨迹的检 测，这样可以提高算法的运行速度。真实数据实验测试表明，该算法比必威体育精装版的ＴＲＡＯＤ异常轨迹挖掘算法效率要高。 关键词　　Ｒｔｒｅｅ　异常轨迹检测　ＴＲＡＯＤ 中图分类号　ＴＰ３０１．４　　　　文献标识码　Ａ ＥＦＦＩＣＩＥＮＴＯＵＴＬＩＥＲＤＥＴＥＣＴＩＯＮＡＬＧＯＲＩＴＨＭＦＯＲＴＲＡＪＥＣＴＯＲＹ ＢＡＳＥＤＯＮＲＴＲＥＥ １，２ ２ ２ １ ２ ＣｈｅｎＪｉｎｙａｎｇ 　ＬｉｕＬｉａｎｇｘｕ　ＳｏｎｇＪｉａｔａｏ　ＷａｎｇＲａｎｇｄｉｎｇ　ＧｕａｎＢｏ １（ＣｏｌｌｅｇｅｏｆＩｎｆｏｒｍａｔｉｏｎＳｃｉｅｎｃｅａｎｄＥｎｇｉｎｅｅｒｉｎｇ，ＮｉｎｇｂｏＵｎｉｖｅｒｓｉｔｙ，Ｎｉｎｇｂｏ３１５２１１，Ｚｈｅｊｉａｎｇ，Ｃｈｉｎａ） ２（ＳｃｈｏｏｌｏｆＥｌｅｃｔｒｏｎｉｃａｎｄＩｎｆｏｒｍａｔｉｏｎ，ＮｉｎｇｂｏＵｎｉｖｅｒｓｉｔｙｏｆＴｅｃｈｎｏｌｏｇｙ，Ｎｉｎｇｂｏ３１５０１６，Ｚｈｅｊｉａｎｇ，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ　　Ｏｕｔｌｉｅｒｄｅｔｅｃｔｉｏｎｉｓａｐｏｐｕｌａｒｄａｔａｍｉｎｉｎｇｔａｓｋ．Ｈｏｗｅｖｅｒ，ｔｈｅｒｅｉｓａｌａｃｋｏｆｓｅｒｉｏｕｓｓｔｕｄｙｏｎｏｕｔｌｉｅｒｄｅｔｅｃｔｉｏｎｆｏｒｔｒａｊｅｃｔｏｒｙｄａｔａ， ａｎｄｔｈｅｅｘｉｓｔｉｎｇａｌｇｏｒｉｔｈｍｓａｌｓｏｈａｖｅｔｈｅｌｉｍｉｔａｔｉｏｎｓ．ＳｏＪ．ＧＬｅｅｅｔａｌｐｒｏｐｏｓｅｄＴＲＡＯＤ．ＴＲＡＯＤｃａｎｅｆｆｅｃｔｉｖｅｌｙｄｅｔｅｃｔｔｈｅａｂｎｏｒｍａｌ ｔｒａｊｅｃｔｏｒｙ，ｂｕｔｉｔａｌｓｏｈａｓｔｈｅｄｅｆｅｃｔｓ．Ｉｔｉｓｄｉｆｆｉｃｕｌｔｔｏｂａｌａｎｃｅｔｈｅａｃｃｕｒａｃｙａｎｄｔｈｅｃｏｍｐｌｅｘｉｔｙ，ｔｈｅｐａｒａｍｅｔｅｒｓｅｌｅｃｔｉｏｎｉｓａｌｉｔｔｌｅｂｉｔｄｉｆｆｉｃｕｌｔ ｔｏｏ，ｔｈｅａｌｇｏｒｉｔｈｍｎｅｅｄｓａｌｏｎｇｔｉｍｅｔｏｅｘｅｃｕｔｅ．ＢａｓｅｄｏｎＴＲＡＯＤ’ｓｐｒｏｂｌｅｍｓ，ｔｈｉｓｐａｐｅｒｐｒｏｐｏｓｅｓｔｈｅＲＴＲＡＯＤ，ｉｔｉｓａｎｅｆｆｉｃｉｅｎｔｏｕｔｌｉｅｒ ｄｅｔｅｃｔｉｏｎａｌｇｏｒｉｔｈｍｂａｓｅｄｏｎＲｔｒｅｅｔｒａｊｅｃｔｏｒｙ．ＴｈｅａｌｇｏｒｉｔｈｍｉｎｄｅｘｅｓｔｈｅｔｒａｊｅｃｔｏｒｙｐｏｉｎｔｓｔｈｒｏｕｇｈＲｔｒｅｅｆｏｒｓｅａｒｃｈｉｎｇｔｈｅｔｒａｊｅｃｔｏｒｙｐｏｉｎｔｓ ｗｉｔｈｉｎｔｈｅｔｅｒｒｉｔｏｒｙｏｆｔｈｅｉｒｄｏｍａｉｎ，ｔｈｅｎａｃｃｏｒｄｉｎｇｔｏＴＲＡＯＤｉｔｄｅｔｅｃｔｓｔｈｅａｂｎｏｒｍａｌｔｒａｊｅｃｔｏｒｙａｇａｉｎｓｔｔｈｅｔｒ