冗余的代码

本章中将详细介绍一种工业界中极其实用的分类和异常检测算法，及在此基础上针对轨迹异常的离散化处理版本。这种称为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.计算局部轨迹距离，看是否有严重的超过正常距离的行为。