基于Random cut forest的流数据异常检测(rrcf, UPenn, Amazon, ICML'16)

Robost random cut forest (rrcf) 的优势:

  1. 针对流数据设计
  2. 可以处理高维数据
  3. 可以减少不相关维度的影响
  4. 考虑了重复数据(或接近重复的数据),减少对异常值的影响
  5. 异常评分的设计明确其潜在的统计意义

Robust random cut tree (RRCT)的构建

对于数据集\(S\), RRCT的构建方式是通过递归划分所有点集的方式,直到每一个点都孤立(isolated)。对于每一次的迭代,都要随机选择一个维度,该维度被选择的概率由其值域范围(最大-最小值)来决定,接下来对于该维度的划分位置也是从其值域内随机选择的。如果一个通过划分可以产生孤立点\(x\),那么针对\(x\)可以生成一个叶子节点,并从点集中删除\(x\)点。算法如下(注:\(S \setminus S_1\) 使集合的减法):

Robust random cut forest(RRCF) 就是多个RRCT的组成。那么如何保证RRCF的数据结构可以在一定程度上保证数据点之间的距离呢?

考虑RRCT的构建算法,我们让树上的每一个点的权重都对应维度和\(\sum_il_i\),任意两个点\(u,v\in S\),定义树距离(tree distance)为两个点最小共同祖先的权重,树距离最小值使曼哈顿距离(曼哈顿距离就是\(L_1\)距离)\(L_1(u,v)\), 期望最大值为\(O(dlog\frac{|S|}{L_1(u,v)}) * L_1(u,v)\)。 这个结果表明如果一个点离其邻居都很远(潜在异常点),那么它在RRCT上与其它点的期望距离也很远。

Robust random cut tree (RRCT)的修正

由于流式数据处理的要求,RRCT需要动态地修正,包括插入与删除,其主要目的是:

  1. 有效识别数据流上的异常
  2. 使模型可以适应数据的变化
  3. 创建一个异常评分的标准(异常被定义为在插入删除时使树结构显著改变的点)

RRCT节点删除

节点删除是从\(RRCF(S)\) 中找到一个树\(T\),然后移除一个点\(p\in S\),然后生成一个新的树\(T'\)符合\(RRCF(S-p)\)的分布,这可以通过删除对应\(p\)的叶子节点\(P\),然后将同级节点放在其祖父节点下

RRCT节点插入

与删除操作相反,插入操作主要有以下需要考虑的特点:

  1. 随机选择一个需要划分的维度并且检查划分是否将\(S\)\(p\)划分开
  2. 如果划分将\(p\)点分开,那么要创建一个新的\(p\)的父节点,该父节点的另一个子节点是\(T(S)\)
  3. 如果没有将\(p\)分开,那么要沿着当前已有的划分(例如,如果\(p_i\)小于划分值,那么就转到左子节点否则右节点)
  4. 然后回到第一步继续

异常评分

对于某个点\(x\)的异常评分,通过节点的插入与删除,来改变模型(树/森林)的复杂度来评分其异常。首先RRCT是一个二叉搜索树