异常检测是一个比较经典的方向，这类算法目的是识别出系统的异常数据点，其细分还有一些子方向，变点监测用于识别序列中的突变点，异常序列监测，这类算法经常在轨迹中使用比较广泛，如何快速发现轨迹中的飘逸轨迹点序列。本文介绍的一个比较经典用于找到数据中的孤立点的算法，你可以直接用来识别训练数据中的孤立点和噪声点，也可以使用这个算法作为前置算法帮助过滤数据。废话不多说，现在就马上介绍一些这个算法。下面咱们单独看看异常监测这个方向的内容。
异常检测分为 离群点检测(outlier detection) 以及 奇异值检测(novelty detection) 两种。
离群点检测：适用于训练数据中包含异常值的情况，例如上述所提及的情况。离群点检测模型会尝试拟合训练数据最集中的区域，而忽略异常数据。
奇异值检测：适用于训练数据不受异常值的污染，目标是去检测新样本是否是异常值。 在这种情况下，异常值也被称为奇异点。
孤立森林
孤立森林 (Isolation Forest, iForest)是一个基于Ensemble的快速离群点检测方法，具有线性时间复杂度和高精准度，是符合大数据处理要求的State-of-the-art算法。由南京大学周志华教授等人于2008年首次提出，之后又于2012年提出了改进版本。适用于连续数据(Continuous numerical data)的异常检测，与其他异常检测算法通过距离、密度等量化指标来刻画样本间的疏离程度不同，孤立森林算法通过对样本点的孤立来检测异常值。具体来说，该算法利用一种名为孤立树iTree的二叉搜索树结构来孤立样本。由于异常值的数量较少且与大部分样本的疏离性，因此，异常值会被更早的孤立出来，也即异常值会距离iTree的根节点更近，而正常值则会距离根节点有更远的距离。
对于如何查找哪些点是否容易被孤立，iForest使用了一套非常高效的策略。假设我们用一个随机超平面来切割数据空间, 切一次可以生成两个子空间（想象拿刀切蛋糕一分为二）。之后我们再继续用一个随机超平面来切割每个子空间，循环下去，直到每子空间里面只有一个数据点为止。直观上来讲，我们可以发现那些密度很高的簇是可以被切很多次才会停止切割，但是那些密度很低的点很容易很早的就停到一个子空间了。
孤立森林建模过程
下面来看看这类模型的建模过程。
构建ITree
- 从训练数据中随机选择Ψ个点样本点作为样本子集，放入树的根节点。
- 随机指定一个维度（特征），在当前节点数据中随机产生一个切割点 p（切割点产生于当前节点数据中指定维度的最大值和最小值之间）。
- 以此切割点生成了一个超平面，然后将当前节点数据空间划分为2个子空间：把指定维度里小于 p 的数据放在当前节点的左子节点，把大于等于 p 的数据放在当前节点的右子节点。
- 在子节点中递归步骤(2)和(3)，不断构造新的子节点，直到子节点中只有一个数据（无法再继续切割）或子节点已到达限定高度。
循环(1)至(4)，直至生成 T 个孤立树iTree。
定义异常度
获得T个iTree之后，iForest训练就结束，然后我们可以用生成的iForest来评估测试数据了。对于每一个数据点xi，令其遍历每一颗孤立树iTree，计算点 xi 在森林中的平均高度h(xi) ，对所有点的平均高度做归一化处理。异常值分数的计算公式如下所示：
S(x,Ψ)=2−c(Ψ)E(h(x))
其中c(Ψ)如下定义。
c(Ψ)=
\begin{cases}
\begin{align}
2(H(Ψ-1))-\frac{2(Ψ-1)}{Ψ} ,Ψ>2\\
1 ,Ψ=2\\
0 \\
\end{align}
\end{cases}
𝐻(𝑖) 是调和数，可以通过 ln(i) + 0.5772156649（欧拉常数）来估算。分值越小表示数据越为异常。
- iForest具有线性时间复杂度。因为是Ensemble的方法，所以可以用在含有海量数据的数据集上面。通常树的数量越多，算法越稳定。由于每棵树都是互相独立生成的，因此可以部署在大规模分布式系统上来加速运算。
- Forest不适用于特别高维的数据。由于每次切数据空间都是随机选取一个维度，建完树后仍然有大量的维度信息没有被使用，导致算法可靠性降低。高维空间还可能存在大量噪音维度或无关维度(irrelevant attributes)，影响树的构建。对这类数据，建议使用子空间异常检测(Subspace Anomaly Detection)技术。
- iForest仅对Global Anomaly敏感，即全局稀疏点敏感，不擅长处理局部的相对稀疏点(Local Anomaly)