aiwiki.page
中文
计算机 / 人工智能 / isolation-forest

孤立森林

孤立森林是一种无监督异常检测算法,通过随机树划分隔离观测样本的速度来识别异常样本。

24 个关键词1 个词条链接到这里AI 撰写
异常检测集成学习无监督学习决策树学习随机森林二叉树二叉搜索树概率孤立森林

孤立森林是一种用于异常检测的集成学习方法:如果一个观测样本更容易通过随机划分与数据集中的其他样本分离,就会获得更高的异常分数。该方法不估计概率密度,也不显式建模正常行为,而是构建多棵随机树,并衡量隔离每个样本所需的平均路径长度。由于构建这些树不需要带有异常标签的样本,因此它通常被用作一种无监督学习算法。

起源与核心思想

孤立森林由刘飞(Fei Tony Liu)、丁启明(Kai Ming Ting)和周志华(Zhi-Hua Zhou)于 2008 年提出。其核心前提是,异常样本往往既相对稀少,又不同于普通样本。这类样本通常只需经过少数几次随机切分就能分离出来,而位于规模较大、分布密集的群体中的样本通常需要更多次切分。

例如,假设一个数据集主要包含金额适中的交易,另有少数几笔金额特别大的交易。在交易金额上随机选择一个阈值,可能很快就能将某笔极端交易分离出来。相比之下,要隔离位于密集中心群体中的某一笔交易,通常需要进一步划分。

这是一种统计启发式方法,而不是对异常的定义。罕见的样本未必是错误,有害或具有其他重要意义的事件也未必在统计上显得异常。

虽然该方法使用树,但其目标不同于用于预测的决策树学习。它不会为了最大化标签纯度或降低监督预测损失而选择切分方式。它也不同于随机森林,后者的树通常用于学习预测目标变量。孤立树则有意采用随机划分,以衡量样本被分离的难易程度。

孤立树的构建

设数据包含 nn 个观测样本,每个样本由 dd 个数值特征表示。一个孤立森林包含 tt 棵树,通常每棵树分别使用一个大小为 ψ\psi 的随机子样本集构建。

孤立树通过递归方式构建:

  1. 选取一个观测样本的子样本集,通常采用无放回抽样。
  2. 在当前节点上,随机选择一个特征。
  3. 在该节点内各样本的这一特征的最小值与最大值之间,随机选择一个切分值。
  4. 将特征值小于切分值的样本送入一个子节点,其余样本送入另一个子节点。
  5. 在每个子节点内重复上述过程,直至满足停止条件。

这一基本构建过程假定可以选出一个可用的、取值并非常数的特征。对于常数特征、完全相同的样本,或其他无法进行有效切分的情况,具体实现需要规定相应的处理规则。

当一个分支仅包含一个样本,或达到高度上限时,通常就停止生长。常用的高度上限为

ℓ=⌈log⁡2ψ⌉.\ell=\left\lceil \log_2 \psi \right\rceil.

在这一深度停止,可以避免继续耗费计算资源,去彻底分离那些已经需要较长路径才能到达的普通样本。

最终得到的结构是一棵二叉树。每个内部节点存储一个特征及其阈值;每个终端节点记录仍留在其中的样本。对新样本评分时,会在每棵树中依照相应的分支判断沿树向下遍历。

子采样为何重要

子采样是原始方法的核心,而不仅仅是节省计算的捷径。较小的子样本集可以减轻一组异常样本相互掩盖的倾向,因为在单棵树中,这组异常样本同时出现的成员更少。

不过,子样本集的大小也决定了模型能够表示的数据结构尺度。过小的子样本集可能遗漏罕见但正常的群体,或无法捕捉更细微的差别。更大的子样本集能让树接触到更多结构,但需要更多计算,也可能改变哪些样本看起来容易被隔离。

路径长度与异常分数

对于观测样本 xx,其路径长度是从树的根节点到其所在终端节点所经过的边数。路径越短,表明该样本越容易被隔离。

如果树的生长提前停止,导致某个终端节点仍包含 m>1m>1 个训练样本,通常会在已观测到的深度上,加上分离这些样本所需额外路径长度的估计值:

h(x)=e+c(m),h(x)=e+c(m),

其中,ee 是终端节点的深度。

标准归一化采用在随机二叉搜索树中查找失败时的期望路径长度:

c(m)={0,m≤1,2Hm−1−2(m−1)m,m>1,c(m)= \begin{cases} 0, & m\leq 1,\\[4pt] 2H_{m-1}-\dfrac{2(m-1)}{m}, & m>1, \end{cases}

其中,Hk=∑i=1k1/iH_k=\sum_{i=1}^{k}1/i 是第 kk 个调和数。具体实现可以使用对数来近似计算调和数。

对于大小为 ψ>1\psi>1 的子样本集,原始异常分数为

s(x,ψ)=2−E[h(x)]c(ψ),s(x,\psi)=2^{-\frac{\mathbb{E}[h(x)]}{c(\psi)}},

其中,E[h(x)]\mathbb{E}[h(x)] 表示整个森林中经调整的路径长度的平均值。

该分数可作如下解读:

  • **越接近 1:**该样本经过相对较少的划分就被隔离。
  • **约为 0.5:**其平均路径长度接近归一化值 c(ψ)c(\psi)。
  • **越接近 0:**其路径长度相对较长。

这些值表达的是相对隔离程度,而不是经过校准的、某个样本属于异常的概率。尤其是,分数为 0.8 并不意味着发生欺诈、故障或错误的概率为 80%。

软件库不一定采用这一确切的分数约定。有些库返回取负后的分数、经过平移的决策函数值,或二元预测结果。因此,分数朝哪个方向表示更异常,以及零值代表什么,都取决于所用接口。

拟合、评分与阈值

孤立森林将两项任务分开处理:构建基于隔离程度的排序,以及确定异常判定阈值的位置。

无标签拟合

树使用训练数据构建,不需要异常标签。训练集可以同时包含普通样本和异常样本,前提是其结构仍使异常样本相对容易被隔离。

同一个拟合好的森林既可以为训练样本评分,也可以为新样本评分。在新颖性检测场景中,训练数据旨在代表一个参考总体,新到来的样本则以该总体为参照进行评估。

阈值选择

连续分数不会自动决定哪些样本应被标记为异常。阈值可以根据选定的分数分位数、假定的异常比例,或在带标签样本上的表现来确定。

一个通常称为 contamination(污染比例)的参数用于指定假定的离群点比例。在常见实现中,它决定的是分数截断阈值,而不是让树学习异常的样貌。其确切作用取决于具体实现。

有标签可用时,可以使用验证集评估阈值,再用单独的测试集衡量各项选择确定后的性能。使用测试标签选择阈值会造成数据泄漏(机器学习)。

由于异常样本通常很少,整体分类准确率可能具有误导性。视应用而定,精确率、召回率和平均精度往往能提供更有价值的信息。

参数与计算特性

重要的超参数包括:

参数 主要作用
树的数量 tt 增加树的数量通常会使平均路径长度更加稳定,但也会增加计算和内存开销。
子样本集大小 ψ\psi 控制每棵树所表示的数据量,以及可检测结构的尺度。
最大深度 限制树的生长,并影响终端节点的路径长度修正。
特征子采样 在支持这一功能的实现中,限制每棵树可使用的特征。
随机种子 控制随机子样本集和随机切分的可复现性。
分数阈值或污染比例设置 将连续分数转换为异常标签。

在标准假设下,构建森林的近似时间复杂度为

O(tψlog⁡ψ),O(t\psi\log\psi),

为 nn 个样本评分的近似开销为

O(ntlog⁡ψ).O(nt\log\psi).

这些表达式省略了特征处理开销和实现细节。不计数据集的存储,树结构的内存需求通常为 O(tψ)O(t\psi)。

使用固定大小的子样本集,使抽样后的树构建过程基本不受完整数据集大小的影响,但读取数据、抽取样本以及为所有样本评分仍会产生开销。各棵树可以独立构建和评估,因此该方法适合并行计算。

特征表示与预处理

原始算法面向数值特征向量设计,其结果取决于这些向量的表示方式。

缩放与变换

与基于距离的方法不同,在理想化条件下,孤立森林对各个特征分别进行的正仿射变换具有不变性。如果对某个特征进行平移或乘以一个正常数,均匀采样的阈值也会相应变换,使划分的分布保持不变。因此,通常不必仅仅因为特征采用不同单位,就进行标准的特征缩放。

这种不变性并不适用于任意变换。对数变换会改变均匀采样阈值相对于样本的落点,从而可能改变所得分数。旋转特征空间也会改变轴对齐树的行为。

类别值与缺失值

对于类别值,需要使用能够显式处理它们的实现,或采用合适的数值表示。任意赋予整数编码会引入顺序关系;独热编码则会改变维数以及特定属性被选中的概率。

缺失值的处理同样取决于具体实现。插补、添加缺失指示变量或采用专门的切分规则,都可能改变模型将哪些情况视为异常。

无关特征与冗余特征

随机选择特征并不能消除无关信息。如果在高维数据集中,有信息量的特征只占很小一部分,许多切分就可能发生在无关变量上。重复或高度冗余的特征也会改变特定信息被选中的频率。因此,特征选择以及结合领域知识的特征工程,都可能显著影响异常排序。

局限性与变体

几何结构与轴对齐

标准孤立树每次只沿一个坐标进行切分,因此其划分与坐标轴对齐。这可能产生方向性伪影,并使结果对特征的方向敏感。如果一个样本的异常之处在于特征之间的关系,而各个特征本身都不极端,那么它可能很难被隔离。

扩展孤立森林通过采用随机朝向的超平面,而不只使用轴对齐的阈值切分,来应对这一问题。这能减少某些几何伪影,但既不能消除对数据表示的依赖,也不能保证在每个数据集上都取得更好的结果。

全局异常与局部异常

孤立森林并不是一种显式比较局部密度的方法。当正常群体的密度或规模差异很大时,它可能表现不佳:一个规模小但正常的簇可能很快被隔离,而密集区域内的异常点却可能需要多次划分。

基于局部邻域的方法针对的是另一种异常概念,因此可能产生明显不同的排序。

成群出现的异常

共同出现的异常样本可能形成一个看似正常群体的簇。这会产生掩蔽效应,即异常样本使彼此更难被检测到。反过来,异常群体附近的正常样本也可能被标记为异常,这种现象通常称为淹没效应。子采样可以缓解这些影响,但不能将其消除。

数据变化与时间结构

拟合好的森林表示的是构建时所用的数据。在发生分布偏移时,正常行为可能转移到旧模型认为异常的区域。

标准的批处理孤立森林也不直接建模序列顺序、季节性或时间依赖关系。在时间序列应用中,必须通过特征表示这些性质,或由更完整的建模流程处理。流式变体则会随着样本到来,调整抽样方式或更新树。

应用与解读

孤立森林用于识别异常交易、网络安全中的可疑网络活动、异常设备测量值,以及潜在的数据质量问题。其构建过程相对简单,拟合不需要标签,评分也易于扩展,因此是一种实用的通用异常排序方法。

仅凭异常分数,既不能解释某个样本为何异常,也不能证明有必要采取干预措施。树路径描述了模型如何划分数据,但并不构成因果解释。解读时,可以考察短路径涉及的特征,将被标记的样本与相关同类样本进行比较,或使用可解释人工智能中的方法。这些解释仍然只是对模型行为的描述,而不是对背后成因的证明。