每日算法 — 使用java实现孤立森林：随机特征分割与异常得分计算

引言

在海量数据中识别异常值（Outlier Detection）是数据挖掘和机器学习中的核心任务。从金融欺诈检测到工业设备故障预警，从网络安全入侵识别到医疗异常指标发现，异常检测的应用无处不在。

孤立森林（Isolation Forest）是Liu等人在2008年提出的异常检测算法，其核心思想与大多数密度估计方法截然不同：异常点由于与正常数据的分布特征不同，通常更容易被”孤立”。算法通过随机选择特征和分割值构建多棵二叉树，异常点在树中的平均路径长度显著短于正常点。本文将用Java完整实现孤立森林算法，包含随机树构建、路径长度计算、异常得分推导以及批量检测接口。

算法原理

核心思想

孤立森林基于一个直观但深刻的观察：异常点是”少数且不同”的，因此在随机分割过程中会被更快地区分开来。

路径长度与异常度的关系：
– 异常点 → 在随机树中更早被孤立 → 路径长度短
– 正常点 → 需要更多分割才能区分 → 路径长度长

关键概念

孤立树（iTree）：一棵二叉树，每个节点随机选择一个特征和分割值，将数据分为左右子树，直到节点中只剩一个样本或达到高度限制。

路径长度h(x)：样本x从根节点到达叶节点经过的边数。

异常得分s(x,n)：

s(x, n) = 2^(-E[h(x)] / c(n))

其中E[h(x)]是样本在多棵树中的平均路径长度，c(n)是给定样本数n时的平均路径长度期望。

• s接近1：异常点
• s接近0.5：正常点
• s远小于0.5：聚集的正常点

Java实现

项目结构

src/
├── IsolationForest.java    // 主算法类
├── IsolationTree.java      // 孤立树
├── TreeNode.java           // 树节点
└── Main.java               // 测试入口

TreeNode.java – 树节点

/**
 * 孤立树的节点
 * 包含分割特征索引、分割值、左右子树和当前节点样本数
 */
public class TreeNode {
    int splitFeature;       // 分割特征索引
    double splitValue;      // 分割阈值
    TreeNode left;          // 左子树（特征值 < 分割值）
    TreeNode right;         // 右子树（特征值 >= 分割值）
    int size;               // 当前节点包含的样本数
    boolean isExternal;     // 是否为外部节点（叶节点）

    public TreeNode() {
        this.isExternal = true;
        this.size = 0;
    }

    public TreeNode(int splitFeature, double splitValue, TreeNode left, TreeNode right, int size) {
        this.splitFeature = splitFeature;
        this.splitValue = splitValue;
        this.left = left;
        this.right = right;
        this.size = size;
        this.isExternal = false;
    }
}

IsolationTree.java – 孤立树

import java.util.*;

/**
 * 孤立树（iTree）
 * 通过递归随机分割构建的二叉树
 */
public class IsolationTree {
    private TreeNode root;
    private int heightLimit;    // 树高限制
    private Random random;

    public IsolationTree(int heightLimit, Random random) {
        this.heightLimit = heightLimit;
        this.random = random;
    }

    /**
     * 构建孤立树
     * @param data 样本子集
     * @param currentHeight 当前高度
     */
    public void fit(double[][] data, int currentHeight) {
        this.root = buildTree(data, currentHeight);
    }

    private TreeNode buildTree(double[][] data, int currentHeight) {
        int n = data.length;
        int numFeatures = data[0].length;

        // 终止条件：只剩一个样本、无样本、或达到高度限制
        if (n <= 1 || currentHeight >= heightLimit) {
            TreeNode node = new TreeNode();
            node.size = n;
            return node;
        }

        // 随机选择分割特征
        int splitFeature = random.nextInt(numFeatures);

        // 获取该特征的最小最大值
        double minVal = Double.MAX_VALUE, maxVal = -Double.MAX_VALUE;
        for (double[] sample : data) {
            minVal = Math.min(minVal, sample[splitFeature]);
            maxVal = Math.max(maxVal, sample[splitFeature]);
        }

        // 若该特征所有值相同，无法分割
        if (minVal == maxVal) {
            TreeNode node = new TreeNode();
            node.size = n;
            return node;
        }

        // 随机选择分割值（在[min, max]之间均匀采样）
        double splitValue = minVal + random.nextDouble() * (maxVal - minVal);

        // 分割数据
        List<double[]> leftData = new ArrayList<>();
        List<double[]> rightData = new ArrayList<>();
        for (double[] sample : data) {
            if (sample[splitFeature] < splitValue) {
                leftData.add(sample);
            } else {
                rightData.add(sample);
            }
        }

        // 递归构建子树
        TreeNode left = buildTree(leftData.toArray(new double[0][]), currentHeight + 1);
        TreeNode right = buildTree(rightData.toArray(new double[0][]), currentHeight + 1);

        return new TreeNode(splitFeature, splitValue, left, right, n);
    }

    /**
     * 计算样本在树中的路径长度
     */
    public double pathLength(double[] sample) {
        return pathLength(sample, root, 0);
    }

    private double pathLength(double[] sample, TreeNode node, int currentPath) {
        if (node == null || node.isExternal) {
            // 外部节点：使用修正项
            return currentPath + c(node.size);
        }

        if (sample[node.splitFeature] < node.splitValue) {
            return pathLength(sample, node.left, currentPath + 1);
        } else {
            return pathLength(sample, node.right, currentPath + 1);
        }
    }

    /**
     * 平均路径长度期望的修正项
     * c(n) = 2H(n-1) - 2(n-1)/n，其中H为调和数
     */
    public static double c(int n) {
        if (n <= 1) return 0;
        if (n == 2) return 1;
        return 2 * (Math.log(n - 1) + 0.5772156649) - 2 * (n - 1.0) / n;
    }
}

IsolationForest.java – 孤立森林

import java.util.*;

/**
 * 孤立森林异常检测算法
 * 通过多棵孤立树的集成投票判断异常程度
 */
public class IsolationForest {
    private int numTrees;           // 树的数量
    private int subSampleSize;      // 每棵树的子采样大小
    private int heightLimit;        // 树高限制
    private List<IsolationTree> trees;  // 森林
    private Random random;

    public IsolationForest(int numTrees, int subSampleSize) {
        this.numTrees = numTrees;
        this.subSampleSize = subSampleSize;
        this.heightLimit = (int) Math.ceil(Math.log(subSampleSize) / Math.log(2));
        this.trees = new ArrayList<>();
        this.random = new Random(42);
    }

    /**
     * 训练孤立森林
     */
    public void fit(double[][] data) {
        int n = data.length;

        for (int i = 0; i < numTrees; i++) {
            // 子采样
            double[][] subSample = subSample(data, Math.min(subSampleSize, n));

            // 构建孤立树
            IsolationTree tree = new IsolationTree(heightLimit, random);
            tree.fit(subSample, 0);
            trees.add(tree);
        }
    }

    /**
     * 子采样
     */
    private double[][] subSample(double[][] data, int size) {
        int n = data.length;
        List<Integer> indices = new ArrayList<>();
        for (int i = 0; i < n; i++) indices.add(i);
        Collections.shuffle(indices, random);

        double[][] result = new double[size][];
        for (int i = 0; i < size; i++) {
            result[i] = data[indices.get(i)];
        }
        return result;
    }

    /**
     * 计算所有样本的异常得分
     */
    public double[] anomalyScores(double[][] data) {
        int n = data.length;
        double[] scores = new double[n];

        for (int i = 0; i < n; i++) {
            scores[i] = anomalyScore(data[i]);
        }

        return scores;
    }

    /**
     * 计算单个样本的异常得分
     * s(x, n) = 2^(-E[h(x)] / c(n))
     */
    public double anomalyScore(double[] sample) {
        double avgPath = 0;
        for (IsolationTree tree : trees) {
            avgPath += tree.pathLength(sample);
        }
        avgPath /= numTrees;

        double cn = IsolationTree.c(subSampleSize);
        return Math.pow(2, -avgPath / cn);
    }

    /**
     * 预测异常标签（基于阈值）
     */
    public int[] predict(double[][] data, double threshold) {
        double[] scores = anomalyScores(data);
        int[] labels = new int[data.length];
        for (int i = 0; i < scores.length; i++) {
            labels[i] = scores[i] >= threshold ? 1 : 0;  // 1表示异常
        }
        return labels;
    }

    /**
     * 获取最异常的top-k样本索引
     */
    public Integer[] topKAnomalies(double[][] data, int k) {
        double[] scores = anomalyScores(data);
        Integer[] indices = new Integer[data.length];
        for (int i = 0; i < indices.length; i++) indices[i] = i;

        Arrays.sort(indices, (a, b) -> Double.compare(scores[b], scores[a]));
        return Arrays.copyOf(indices, k);
    }
}

Main.java – 测试

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // 构造二维数据：大部分点聚集，少数点偏离
        int normalCount = 300;
        int anomalyCount = 20;
        double[][] data = new double[normalCount + anomalyCount][2];
        Random rand = new Random(42);

        // 正常点：围绕(0,0)的正态分布
        for (int i = 0; i < normalCount; i++) {
            data[i][0] = rand.nextGaussian();
            data[i][1] = rand.nextGaussian();
        }

        // 异常点：远离中心的点
        for (int i = normalCount; i < normalCount + anomalyCount; i++) {
            data[i][0] = 5 + rand.nextGaussian() * 0.5;
            data[i][1] = 5 + rand.nextGaussian() * 0.5;
        }

        // 训练孤立森林
        IsolationForest forest = new IsolationForest(100, 256);
        forest.fit(data);

        // 计算异常得分
        double[] scores = forest.anomalyScores(data);

        // 统计正常点和异常点的平均得分
        double normalAvg = 0, anomalyAvg = 0;
        for (int i = 0; i < normalCount; i++) normalAvg += scores[i];
        for (int i = normalCount; i < data.length; i++) anomalyAvg += scores[i];
        normalAvg /= normalCount;
        anomalyAvg /= anomalyCount;

        System.out.println("正常点平均异常得分: " + String.format("%.4f", normalAvg));
        System.out.println("异常点平均异常得分: " + String.format("%.4f", anomalyAvg));

        // Top-20异常检测
        Integer[] topAnomalies = forest.topKAnomalies(data, 20);
        int correct = 0;
        for (int idx : topAnomalies) {
            if (idx >= normalCount) correct++;
        }
        System.out.println("Top-20中真实异常数: " + correct + "/20");

        // 阈值预测
        int[] predictions = forest.predict(data, 0.6);
        int tp = 0, fp = 0, fn = 0;
        for (int i = 0; i < data.length; i++) {
            boolean isAnomaly = i >= normalCount;
            boolean predicted = predictions[i] == 1;
            if (isAnomaly && predicted) tp++;
            if (!isAnomaly && predicted) fp++;
            if (isAnomaly && !predicted) fn++;
        }
        System.out.println("\n阈值=0.6 分类结果:");
        System.out.println("TP=" + tp + ", FP=" + fp + ", FN=" + fn);
        System.out.println("精确率: " + String.format("%.2f%%", 100.0 * tp / (tp + fp)));
        System.out.println("召回率: " + String.format("%.2f%%", 100.0 * tp / (tp + fn)));
    }
}

运行结果

正常点平均异常得分: 0.4213
异常点平均异常得分: 0.8427
Top-20中真实异常数: 20/20

阈值=0.6 分类结果:
TP=20, FP=12, FN=0
精确率: 62.50%
召回率: 100.00%

复杂度分析

由于采用子采样（通常ψ=256），训练时间和空间复杂度与总样本数无关，可线性扩展至海量数据。

算法优势

• 线性时间复杂度：子采样使训练时间与数据量解耦
• 低内存占用：无需存储全部样本的统计信息
• 无需密度估计：避免了高维空间中的维度灾难
• 对高维数据友好：随机特征选择天然适应高维场景

应用场景

• 金融风控：识别信用卡欺诈交易和异常转账行为
• 工业物联网：监测传感器数据的异常波动，预测设备故障
• 网络安全：检测异常流量模式和入侵行为
• 医疗诊断：识别体检指标中的异常值，辅助疾病筛查

总结

孤立森林通过随机分割的巧妙设计，将异常检测问题转化为路径长度比较问题，避免了传统密度估计方法的计算瓶颈。本文提供的Java实现完整覆盖了从单棵树构建到多树集成的完整流程，子采样策略确保了算法在大规模数据上的高效性。读者可根据实际场景调整树的数量、子采样大小和判断阈值，以获得最佳的异常检测效果。