rrcf 🌲🌲🌲

由 Guha 等人 (2016) 提出的用于异常检测的 鲁棒随机切割森林算法 的实现。

S. Guha, N. Mishra, G. Roy, & O. Schrijvers，《基于鲁棒随机切割森林的流式数据异常检测》，载于第33届国际机器学习会议论文集，纽约，纽约州，2016年（第2712–2721页）。

关于

鲁棒随机切割森林（RRCF）算法是一种用于检测流式数据中离群点的集成方法。RRCF 具有许多竞争性异常检测算法所不具备的功能。具体而言，RRCF：

• 专为处理流式数据而设计。
• 在高维数据上表现良好。
• 减少无关维度的影响。
• 能够优雅地处理重复和近似重复的数据，这些数据可能会掩盖离群点的存在。
• 拥有一个具有明确统计意义的异常评分算法。

本仓库提供了 RRCF 算法及其核心数据结构的开源实现，旨在促进实验研究，并为 RRCF 算法的未来扩展提供支持。

文档

请在此处阅读文档 📖[链接]。

安装

使用 pip 通过 pypi 安装 rrcf：

$ pip install rrcf

目前仅支持 Python 3。

依赖项

安装和使用 rrcf 需要以下依赖项：

• numpy（>= 1.15）

运行文档中示例所需的以下可选依赖项：

• pandas（>= 0.23）
• scipy（>= 1.2）
• scikit-learn（>= 0.20）
• matplotlib（>= 3.0）

列出的版本号已经过测试并确认可用（但这并不排除较旧版本的可能性）。

鲁棒随机切割树

鲁棒随机切割树（RRCT）是一种二叉搜索树，可用于检测点集中的离群点。RRCT 可以从点集实例化。也可以向 RRCT 中添加或删除点。

创建树

import numpy as np
import rrcf

# 可以从点集（n x d）实例化一棵（鲁棒）随机切割树
X = np.random.randn(100, 2)
tree = rrcf.RCTree(X)

# 随机切割树也可以在没有点的情况下实例化
tree = rrcf.RCTree()

插入点

tree = rrcf.RCTree()

for i in range(6):
    x = np.random.randn(2)
    tree.insert_point(x, index=i)

─+
 ├───+
 │   ├───+
 │   │   ├──(0)
 │   │   └───+
 │   │       ├──(5)
 │   │       └──(4)
 │   └───+
 │       ├──(2)
 │       └──(3)
 └──(1)

删除点

tree.forget_point(2)

─+
 ├───+
 │   ├───+
 │   │   ├──(0)
 │   │   └───+
 │   │       ├──(5)
 │   │       └──(4)
 │   └──(3)
 └──(1)

异常评分

一个点是离群点的可能性由其协同位移（CoDisp）来衡量：如果加入一个新的点会显著改变模型复杂度（即位深），那么该点更有可能是离群点。

# 使用零均值、正态分布的数据初始化树
X = np.random.randn(100,2)
tree = rrcf.RCTree(X)

# 生成一个内点和一个离群点
inlier = np.array([0, 0])
outlier = np.array([4, 4])

# 插入树中
tree.insert_point(inlier, index='inlier')
tree.insert_point(outlier, index='outlier')

tree.codisp('inlier')
>>> 1.75

tree.codisp('outlier')
>>> 39.0

批量异常检测

此示例展示了如何使用鲁棒随机切割森林在批量环境中检测离群点。离群点对应于较大的 CoDisp 值。

import numpy as np
import pandas as pd
import rrcf

# 设置参数
np.random.seed(0)
n = 2010
d = 3
num_trees = 100
tree_size = 256

# 生成数据
X = np.zeros((n, d))
X[:1000,0] = 5
X[1000:2000,0] = -5
X += 0.01*np.random.randn(*X.shape)

# 构建森林
forest = []
while len(forest) < num_trees:
    # 从点集中均匀随机选择子集
    ixs = np.random.choice(n, size=(n // tree_size, tree_size),
                           replace=False)
    # 将采样的树添加到森林中
    trees = [rrcf.RCTree(X[ix], index_labels=ix) for ix in ixs]
    forest.extend(trees)

# 计算平均 CoDisp
avg_codisp = pd.Series(0.0, index=np.arange(n))
index = np.zeros(n)
for tree in forest:
    codisp = pd.Series({leaf : tree.codisp(leaf) for leaf in tree.leaves})
    avg_codisp[codisp.index] += codisp
    np.add.at(index, codisp.index.values, 1)
avg_codisp /= index

流式异常检测

此示例展示了如何使用该算法检测流式时间序列数据中的异常。

import numpy as np
import rrcf

# 生成数据
n = 730
A = 50
center = 100
phi = 30
T = 2*np.pi/100
t = np.arange(n)
sin = A*np.sin(T*t-phi*T) + center
sin[235:255] = 80

# 设置树的参数
num_trees = 40
shingle_size = 4
tree_size = 256

# 创建一个空树的森林
forest = []
for _ in range(num_trees):
    tree = rrcf.RCTree()
    forest.append(tree)
    
# 使用“shingle”生成器创建滚动窗口
points = rrcf.shingle(sin, size=shingle_size)

# 创建一个字典存储每个点的异常评分
avg_codisp = {}

# 对于每一个 shingle...
for index, point in enumerate(points):
    # 对于森林中的每一棵树...
    for tree in forest:
        # 如果树的叶子数量超过允许的最大值，则移除最老的叶子（FIFO）
        if len(tree.leaves) > tree_size:
            tree.forget_point(index - tree_size)
        # 将新点插入树中
        tree.insert_point(point, index=index)
        # 计算新点的 CoDisp，并取所有树的平均值
        if not index in avg_codisp:
            avg_codisp[index] = 0
        avg_codisp[index] += tree.codisp(index) / num_trees

获取特征重要性

此示例展示了如何在计算 CoDisp 时，利用切割维度来估计特征的重要性。

import numpy as np
import pandas as pd
import rrcf

# 设置参数
np.random.seed(0)
n = 2010
d = 3
num_trees = 100
tree_size = 256

# 生成数据
X = np.zeros((n, d))
X[:1000,0] = 5
X[1000:2000,0] = -5
X += 0.01*np.random.randn(*X.shape)

# 构建森林
forest = []
while len(forest) < num_trees:
    # 从点集中均匀随机选择子集
    ixs = np.random.choice(n, size=(n // tree_size, tree_size),
                           replace=False)
    # 将采样的树加入森林
    trees = [rrcf.RCTree(X[ix], index_labels=ix) for ix in ixs]
    forest.extend(trees)


# 计算每个点在切割维度上的平均CoDisp
dim_codisp = np.zeros([n,d],dtype=float)
index = np.zeros(n)
for tree in forest:
    for leaf in tree.leaves:
        codisp,cutdim = tree.codisp_with_cut_dimension(leaf)
        
        dim_codisp[leaf,cutdim] += codisp 

        index[leaf] += 1

avg_codisp = dim_codisp.sum(axis=1)/index

# 根据CoDisp异常阈值计算各特征的平均值
feature_importance_anomaly = np.mean(dim_codisp[avg_codisp>50,:],axis=0)
# 创建包含特征重要性的数据框
df_feature_importance = pd.DataFrame(feature_importance_anomaly,columns=['feature_importance'])
df_feature_importance

贡献说明

我们欢迎对 rrcf 仓库的贡献。如需贡献，请向 dev 分支提交一个 拉取请求。

贡献类型

以下是一些建议的贡献类型：

• 修复 bug
• 改进文档
• 提升性能
• 扩展算法功能

请查看问题跟踪器，了解是否有需要帮助的具体问题。如果您在使用 rrcf 时遇到问题，或有扩展功能的想法，欢迎随时提交问题。

贡献者指南

在向代码库贡献时，请遵循以下指南：

• 确保所有新增的方法、函数或类都包含文档字符串。文档字符串应包括代码描述、输入参数和输出结果的说明。建议提供示例用法（可参考现有方法）。
• 为任何新代码编写单元测试，并确保所有测试都能通过且无警告。请确保整体代码覆盖率不低于80%。

运行单元测试

要运行单元测试，首先确保已安装 pytest 和 pytest-cov：

$ pip install pytest pytest-cov

然后导航到仓库的根目录并运行：

$ pytest --cov=rrcf/

引用说明

如果您在论文或其他出版物中使用了本代码库并希望引用它，请使用 Journal of Open Source Software 文章。

M. Bartos, A. Mullapudi, & S. Troutman, rrcf: Implementation of the Robust Random Cut Forest algorithm for anomaly detection on streams, in: Journal of Open Source Software, The Open Journal, 第4卷第35期. 2019

@article{bartos_2019_rrcf,
  title={{rrcf: Implementation of the Robust Random Cut Forest algorithm for anomaly detection on streams}},
  authors={Matthew Bartos and Abhiram Mullapudi and Sara Troutman},
  journal={{The Journal of Open Source Software}},
  volume={4},
  number={35},
  pages={1336},
  year={2019}
}

rrcf 快速上手指南

rrcf 是 鲁棒随机切割森林 (Robust Random Cut Forest) 算法的 Python 实现，专为流式数据中的异常检测设计。它擅长处理高维数据，能有效识别离群点并降低无关维度的影响。

环境准备

在开始之前，请确保您的开发环境满足以下要求：

• 操作系统：Linux, macOS 或 Windows
• Python 版本：仅支持 Python 3 (推荐 3.6+)
• 核心依赖：
  • numpy (>= 1.15)
• 可选依赖（运行示例代码时需要）：
  • pandas, scipy, scikit-learn, matplotlib

安装步骤

使用 pip 即可快速安装。国内用户建议使用清华或阿里镜像源以加速下载。

标准安装：

pip install rrcf

使用国内镜像源加速安装（推荐）：

pip install rrcf -i https://pypi.tuna.tsinghua.edu.cn/simple

基本使用

以下是使用 rrcf 进行异常检测的最简示例。该算法通过计算 共谋位移 (CoDisp) 来衡量点的异常程度：CoDisp 值越高，该点越可能是异常点。

1. 构建树并插入数据

import numpy as np
import rrcf

# 生成一些符合正态分布的正常数据 (100 个点，2 维)
X = np.random.randn(100, 2)

# 初始化随机切割树
tree = rrcf.RCTree(X)

# 定义一个正常点和一个异常点
inlier = np.array([0, 0])   # 靠近中心，应为正常
outlier = np.array([4, 4])  # 远离中心，应为异常

# 将点插入树中
tree.insert_point(inlier, index='inlier')
tree.insert_point(outlier, index='outlier')

2. 计算异常分数 (CoDisp)

# 获取正常点的异常分数
score_inlier = tree.codisp('inlier')
print(f"Inlier CoDisp: {score_inlier}")
# 输出示例：1.75 (数值较小)

# 获取异常点的异常分数
score_outlier = tree.codisp('outlier')
print(f"Outlier CoDisp: {score_outlier}")
# 输出示例：39.0 (数值显著较大)

3. 简单判断逻辑

在实际应用中，您可以设定一个阈值来判断新数据是否为异常：

threshold = 10.0  # 根据实际数据分布调整阈值

if score_outlier > threshold:
    print("检测到异常点！")
else:
    print("数据正常。")

提示：对于生产环境中的流式数据或批量数据，通常建议构建由多棵树组成的“森林” (Robust Random Cut Forest) 并取平均 CoDisp 值，以获得更稳定的检测结果。详细用法可参考官方文档。