异常检测-流检测

之前提到的孤立森林是一种离线的数据挖掘挖掘|机器学习的方法。也就是说，孤立森林无法对实时的流数据进行检测。这里介绍一种使用 Half-Space Trees 构造的实时检测算法。Half-Space Trees 是一种构造方法和孤立森林极其相似的用于异常检测的模型，其理论是 Mass Estimation 。不熟悉的同学可以看:

具体的树和森林的构造方法就不在仔细讲。与孤立森林只有一点不同，孤立森林选择的划分点为随机的，而 Half-Space Trees 则是在用于划分的特征选取 (最大值+最小值)/2。这里主要讲一下其中在上面两篇文章中没有提到的概念以及如何进行事实检测。

时间窗

Fast Anomaly Detection for Streaming Data 文中直接用 window 来描述。这里为了好理解将其翻译为时间窗。在最开始阶段，使用 refer window 学习正常数据的质量特征(mass profile)。然后使用学得特征对流数据进行检测，而持续的流数据将放入一个 latest window 中。放入 latest window 中的数据也将对质量特征进行更新，当 latest window 中数据达到 window size，也就是一个 window 中容纳的最多样本的数目。就将 latest window 更新为 refer window。并将 refer window 学得质量特征更新为 latest window 学得的质量特征，如此反复。

质量特征

质量特征用来计算需要检测数据的异常得分，最开始由正常数据计算，随后在检测的过程中不断更新。质量特征的计算方法如下:

对于数据x，将x通过每一个棵树。如果x经历了节点 n :
if n in refer window:
	n.r ++
else if n in latest window:
	n.l ++

也就是说，对一个节点，如果有很多数据会进过这个节点，则这落在这个节点的数据就很多，而这个节点的正常度也就越高。反之则越低。

最终异常得分的公式为:
$$
n.r × 2^{n.k}
$$
至于这里为什么要乘上一个系数 $2^{n.k}$ 可以看看论文 Mass estimation 中有详细的推导。对每一个棵树的异常得分取平均就能得到最终的异常得分。

实时检测

结合上面说的，可以得实时检测的算法如下:

1. 构建 Half-Space Trees //构建方法与构建异常森林基本相同
2. 从训练样本中找到窗口大小的数据放入 refer window ，并构建质量特征
3. 将从流中获取的数据输入 Half-Space Trees 获取异常值，并构建关于 latest window 的质量特征
4. 如果 latest window 未满，则循环步骤3 否则进行步骤 5
5. 将每一棵树的 n.r 替换为 n.l 并将 n.l 设置为 0。使用 latest window 替换 refer window。并跳到步骤 3

从上面的算法可以看出，实时检测并没有对树的结构进行更新，只是交换了质量特征。因此性能非常好。

与孤立森林的区别

Half-Space Trees 在参数上与孤立森林有一点点差别:

Half-Space Trees 落在在某一个节点样本数量 < 0.1 $\cdot$ window size 会停止分裂。
Half-Space Trees 树的最大高度并没有设置为$log2(训练样本数量)$
Half-Space Trees 推荐使用 25 棵树集成一个森林。

参考

Tan S C, Kai M T, Liu T F. Fast Anomaly Detection for Streaming Data.[C]// IJCAI 2011, Proceedings of the, International Joint Conference on Artificial Intelligence, Barcelona, Catalonia, Spain, July. DBLP, 2011:1511-1516.