posts - 13, comments - 0, trackbacks - 0, articles - 0
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

GPS轨迹挖掘-绕路分析(3)

Posted on 2020-03-13 15:20 杜仲当归 阅读(437) 评论(0)  编辑 收藏 引用
本章中将详细介绍一种工业界中极其实用的分类和异常检测算法,及在此基础上针对轨迹异常的离散化处理版本。这种称为iForest的方法比起基于距离、密度的方法更为巧妙,它直接刻画数据的“疏离”(isolation)程度。

4.iBAT

关于iForest算法本身可以阅读这篇blog:https://blog.csdn.net/Super_Json/article/details/84944707
简单的说,iForest是一种针对多维数据的随机决策树,通过随机选取某个维度将数据按值分成两棵子树,类似BST(划分出大的数据和小的数据),然后子树按相同规则递归划分,直到无法划分为止,此时所有的子树中的数据归于一类。

而iBAT就是一种建立在轨迹网格化基础上的决策树。用作者的话来说,轨迹可以分为两种,一种是正常的,一种是异常的,正常的轨迹“多且近似”,异常的轨迹“少且特殊”, 后者是我们要求的答案。相对于正常轨迹的复杂化和难以处理,异常轨迹比较容易被孤立,因此决策树用于解决异常轨迹有特别的好处。

iBAT的算法如下:
1.随机选某个网格
2.把轨迹集合按有无此网格分为两棵树
3.递归处理子树
4.得到完整的决策树
5.按iForest算法决定异常数据

在实际应用中,发现iBAT存在几个缺点:
1.需要选出OD对下的所有轨迹集合,在实际使用时往往某些异常轨迹OD对比较少,难以在统计上成立。当然,这个缺点对于所有的异常检测算法都或多或少存在。
2.本质上还是全局算法,缺乏对部分轨迹绕路的精确判断,如果轨迹绕路只是局部的(但在距离上很明显),由于大部分数据和正常轨迹相同,此时可能落在决策树的底层。
3.决策树的高层(即异常数据)也可能由于一个异常点的存在,首先选取了该异常点存在的网格,从而发生误判。

因此后面也有许多工作对iBAT提出了优化,其中几个思路都很清晰:
1.对异常数据和正常数据进行相似度判定,离正常数据相似度太低的才是异常数据。
2.计算局部轨迹距离,看是否有严重的超过正常距离的行为。

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理