孤立森林是一种用于异常检测的集成学习方法:如果一个观测样本更容易通过随机划分与数据集中的其他样本分离,就会获得更高的异常分数。该方法不估计概率密度,也不显式建模正常行为,而是构建多棵随机树,并衡量隔离每个样本所需的平均路径长度。由于构建这些树不需要带有异常标签的样本,因此它通常被用作一种无监督学习算法。
起源与核心思想
孤立森林由刘飞(Fei Tony Liu)、丁启明(Kai Ming Ting)和周志华(Zhi-Hua Zhou)于 2008 年提出。其核心前提是,异常样本往往既相对稀少,又不同于普通样本。这类样本通常只需经过少数几次随机切分就能分离出来,而位于规模较大、分布密集的群体中的样本通常需要更多次切分。
例如,假设一个数据集主要包含金额适中的交易,另有少数几笔金额特别大的交易。在交易金额上随机选择一个阈值,可能很快就能将某笔极端交易分离出来。相比之下,要隔离位于密集中心群体中的某一笔交易,通常需要进一步划分。
这是一种统计启发式方法,而不是对异常的定义。罕见的样本未必是错误,有害或具有其他重要意义的事件也未必在统计上显得异常。
虽然该方法使用树,但其目标不同于用于预测的决策树学习。它不会为了最大化标签纯度或降低监督预测损失而选择切分方式。它也不同于随机森林,后者的树通常用于学习预测目标变量。孤立树则有意采用随机划分,以衡量样本被分离的难易程度。
孤立树的构建
设数据包含 个观测样本,每个样本由 个数值特征表示。一个孤立森林包含 棵树,通常每棵树分别使用一个大小为 的随机子样本集构建。
孤立树通过递归方式构建:
- 选取一个观测样本的子样本集,通常采用无放回抽样。
- 在当前节点上,随机选择一个特征。
- 在该节点内各样本的这一特征的最小值与最大值之间,随机选择一个切分值。
- 将特征值小于切分值的样本送入一个子节点,其余样本送入另一个子节点。
- 在每个子节点内重复上述过程,直至满足停止条件。
这一基本构建过程假定可以选出一个可用的、取值并非常数的特征。对于常数特征、完全相同的样本,或其他无法进行有效切分的情况,具体实现需要规定相应的处理规则。
当一个分支仅包含一个样本,或达到高度上限时,通常就停止生长。常用的高度上限为
在这一深度停止,可以避免继续耗费计算资源,去彻底分离那些已经需要较长路径才能到达的普通样本。
最终得到的结构是一棵二叉树。每个内部节点存储一个特征及其阈值;每个终端节点记录仍留在其中的样本。对新样本评分时,会在每棵树中依照相应的分支判断沿树向下遍历。
子采样为何重要
子采样是原始方法的核心,而不仅仅是节省计算的捷径。较小的子样本集可以减轻一组异常样本相互掩盖的倾向,因为在单棵树中,这组异常样本同时出现的成员更少。
不过,子样本集的大小也决定了模型能够表示的数据结构尺度。过小的子样本集可能遗漏罕见但正常的群体,或无法捕捉更细微的差别。更大的子样本集能让树接触到更多结构,但需要更多计算,也可能改变哪些样本看起来容易被隔离。
路径长度与异常分数
对于观测样本 ,其路径长度是从树的根节点到其所在终端节点所经过的边数。路径越短,表明该样本越容易被隔离。
如果树的生长提前停止,导致某个终端节点仍包含 个训练样本,通常会在已观测到的深度上,加上分离这些样本所需额外路径长度的估计值:
其中, 是终端节点的深度。
标准归一化采用在随机二叉搜索树中查找失败时的期望路径长度:
其中, 是第 个调和数。具体实现可以使用对数来近似计算调和数。
对于大小为 的子样本集,原始异常分数为
其中, 表示整个森林中经调整的路径长度的平均值。
该分数可作如下解读:
- **越接近 1:**该样本经过相对较少的划分就被隔离。
- **约为 0.5:**其平均路径长度接近归一化值 。
- **越接近 0:**其路径长度相对较长。
这些值表达的是相对隔离程度,而不是经过校准的、某个样本属于异常的概率。尤其是,分数为 0.8 并不意味着发生欺诈、故障或错误的概率为 80%。
软件库不一定采用这一确切的分数约定。有些库返回取负后的分数、经过平移的决策函数值,或二元预测结果。因此,分数朝哪个方向表示更异常,以及零值代表什么,都取决于所用接口。
拟合、评分与阈值
孤立森林将两项任务分开处理:构建基于隔离程度的排序,以及确定异常判定阈值的位置。
无标签拟合
树使用训练数据构建,不需要异常标签。训练集可以同时包含普通样本和异常样本,前提是其结构仍使异常样本相对容易被隔离。
同一个拟合好的森林既可以为训练样本评分,也可以为新样本评分。在新颖性检测场景中,训练数据旨在代表一个参考总体,新到来的样本则以该总体为参照进行评估。
阈值选择
连续分数不会自动决定哪些样本应被标记为异常。阈值可以根据选定的分数分位数、假定的异常比例,或在带标签样本上的表现来确定。
一个通常称为 contamination(污染比例)的参数用于指定假定的离群点比例。在常见实现中,它决定的是分数截断阈值,而不是让树学习异常的样貌。其确切作用取决于具体实现。
有标签可用时,可以使用验证集评估阈值,再用单独的测试集衡量各项选择确定后的性能。使用测试标签选择阈值会造成数据泄漏(机器学习)。
由于异常样本通常很少,整体分类准确率可能具有误导性。视应用而定,精确率、召回率和平均精度往往能提供更有价值的信息。
参数与计算特性
重要的超参数包括:
| 参数 | 主要作用 |
|---|---|
| 树的数量 | 增加树的数量通常会使平均路径长度更加稳定,但也会增加计算和内存开销。 |
| 子样本集大小 | 控制每棵树所表示的数据量,以及可检测结构的尺度。 |
| 最大深度 | 限制树的生长,并影响终端节点的路径长度修正。 |
| 特征子采样 | 在支持这一功能的实现中,限制每棵树可使用的特征。 |
| 随机种子 | 控制随机子样本集和随机切分的可复现性。 |
| 分数阈值或污染比例设置 | 将连续分数转换为异常标签。 |
在标准假设下,构建森林的近似时间复杂度为
为 个样本评分的近似开销为
这些表达式省略了特征处理开销和实现细节。不计数据集的存储,树结构的内存需求通常为 。
使用固定大小的子样本集,使抽样后的树构建过程基本不受完整数据集大小的影响,但读取数据、抽取样本以及为所有样本评分仍会产生开销。各棵树可以独立构建和评估,因此该方法适合并行计算。
特征表示与预处理
原始算法面向数值特征向量设计,其结果取决于这些向量的表示方式。
缩放与变换
与基于距离的方法不同,在理想化条件下,孤立森林对各个特征分别进行的正仿射变换具有不变性。如果对某个特征进行平移或乘以一个正常数,均匀采样的阈值也会相应变换,使划分的分布保持不变。因此,通常不必仅仅因为特征采用不同单位,就进行标准的特征缩放。
这种不变性并不适用于任意变换。对数变换会改变均匀采样阈值相对于样本的落点,从而可能改变所得分数。旋转特征空间也会改变轴对齐树的行为。
类别值与缺失值
对于类别值,需要使用能够显式处理它们的实现,或采用合适的数值表示。任意赋予整数编码会引入顺序关系;独热编码则会改变维数以及特定属性被选中的概率。
缺失值的处理同样取决于具体实现。插补、添加缺失指示变量或采用专门的切分规则,都可能改变模型将哪些情况视为异常。
无关特征与冗余特征
随机选择特征并不能消除无关信息。如果在高维数据集中,有信息量的特征只占很小一部分,许多切分就可能发生在无关变量上。重复或高度冗余的特征也会改变特定信息被选中的频率。因此,特征选择以及结合领域知识的特征工程,都可能显著影响异常排序。
局限性与变体
几何结构与轴对齐
标准孤立树每次只沿一个坐标进行切分,因此其划分与坐标轴对齐。这可能产生方向性伪影,并使结果对特征的方向敏感。如果一个样本的异常之处在于特征之间的关系,而各个特征本身都不极端,那么它可能很难被隔离。
扩展孤立森林通过采用随机朝向的超平面,而不只使用轴对齐的阈值切分,来应对这一问题。这能减少某些几何伪影,但既不能消除对数据表示的依赖,也不能保证在每个数据集上都取得更好的结果。
全局异常与局部异常
孤立森林并不是一种显式比较局部密度的方法。当正常群体的密度或规模差异很大时,它可能表现不佳:一个规模小但正常的簇可能很快被隔离,而密集区域内的异常点却可能需要多次划分。
基于局部邻域的方法针对的是另一种异常概念,因此可能产生明显不同的排序。
成群出现的异常
共同出现的异常样本可能形成一个看似正常群体的簇。这会产生掩蔽效应,即异常样本使彼此更难被检测到。反过来,异常群体附近的正常样本也可能被标记为异常,这种现象通常称为淹没效应。子采样可以缓解这些影响,但不能将其消除。
数据变化与时间结构
拟合好的森林表示的是构建时所用的数据。在发生分布偏移时,正常行为可能转移到旧模型认为异常的区域。
标准的批处理孤立森林也不直接建模序列顺序、季节性或时间依赖关系。在时间序列应用中,必须通过特征表示这些性质,或由更完整的建模流程处理。流式变体则会随着样本到来,调整抽样方式或更新树。
应用与解读
孤立森林用于识别异常交易、网络安全中的可疑网络活动、异常设备测量值,以及潜在的数据质量问题。其构建过程相对简单,拟合不需要标签,评分也易于扩展,因此是一种实用的通用异常排序方法。
仅凭异常分数,既不能解释某个样本为何异常,也不能证明有必要采取干预措施。树路径描述了模型如何划分数据,但并不构成因果解释。解读时,可以考察短路径涉及的特征,将被标记的样本与相关同类样本进行比较,或使用可解释人工智能中的方法。这些解释仍然只是对模型行为的描述,而不是对背后成因的证明。