引言
在机器学习领域，单一决策树容易过拟合且对数据扰动敏感。随机森林（Random Forest）由Breiman于2001年提出，通过Bagging（Bootstrap Aggregating）策略集成多棵决策树，既保留了决策树易解释的优点，又显著提升了模型的泛化能力和稳定性。随机森林在分类、回归和特征选择等任务中表现优异，是数据科学竞赛和工业应用中的常用算法。
算法原理
1. Bagging策略
- 从原始数据集中有放回地随机抽取N个样本（Bootstrap采样）
- 对每份采样数据训练一棵决策树
- 最终预测时，分类任务采用投票法，回归任务采用平均法
2. 随机性来源
- 样本随机：Bootstrap采样使每棵树看到不同的训练样本
- 特征随机：每个节点分裂时，仅从随机选取的m个特征中选择最优分裂特征
3. Out-of-Bag评估
由于Bootstrap采样约有36.8%的数据不会被抽到（(1-1/n)^n ≈ 1/e），这些Out-of-Bag（OOB）样本可用于无偏估计模型性能，无需额外划分验证集。
Java实现
import java.util.*;
/**
* 随机森林分类器实现
* 基于CART决策树的Bagging集成
*/
public class RandomForest {
/**
* 数据样本
*/
static class Sample {
double[] features;
int label;
Sample(double[] features, int label) {
this.features = features;
this.label = label;
}
}
/**
* 决策树节点
*/
static class TreeNode {
int featureIndex; // 分裂特征索引（-1表示叶子节点）
double threshold; // 分裂阈值
int predictedLabel; // 叶子节点的预测标签
TreeNode left, right; // 左右子树
boolean isLeaf() { return featureIndex == -1; }
}
private int numTrees; // 树的数量
private int maxDepth; // 最大深度
private int minSamplesSplit; // 节点最小分裂样本数
private int numFeatures; // 每棵树随机选取的特征数
private List<TreeNode> trees; // 森林中的所有树
private List<List<Sample>> bootstrapSamples; // 每棵树的训练样本
private List<Set<Integer>> oobIndices; // 每棵树的OOB样本索引
private int numClasses; // 类别数
public RandomForest(int numTrees, int maxDepth, int minSamplesSplit, int numFeatures) {
this.numTrees = numTrees;
this.maxDepth = maxDepth;
this.minSamplesSplit = minSamplesSplit;
this.numFeatures = numFeatures;
this.trees = new ArrayList<>();
this.bootstrapSamples = new ArrayList<>();
this.oobIndices = new ArrayList<>();
}
/**
* 计算Gini不纯度
*/
double giniImpurity(List<Sample> samples) {
if (samples.isEmpty()) return 0;
Map<Integer, Integer> counts = new HashMap<>();
for (Sample s : samples) {
counts.merge(s.label, 1, Integer::sum);
}
double impurity = 1.0;
for (int count : counts.values()) {
double p = (double) count / samples.size();
impurity -= p * p;
}
return impurity;
}
/**
* 寻找最优分裂
*/
Object[] findBestSplit(List<Sample> samples, int[] featureIndices) {
double bestGain = -1;
int bestFeature = -1;
double bestThreshold = 0;
double parentImpurity = giniImpurity(samples);
for (int fi : featureIndices) {
// 获取该特征的所有唯一值作为候选阈值
Set<Double> values = new HashSet<>();
for (Sample s : samples) values.add(s.features[fi]);
for (double threshold : values) {
List<Sample> left = new ArrayList<>();
List<Sample> right = new ArrayList<>();
for (Sample s : samples) {
if (s.features[fi] <= threshold) left.add(s);
else right.add(s);
}
if (left.isEmpty() || right.isEmpty()) continue;
double gain = parentImpurity
- (double) left.size() / samples.size() * giniImpurity(left)
- (double) right.size() / samples.size() * giniImpurity(right);
if (gain > bestGain) {
bestGain = gain;
bestFeature = fi;
bestThreshold = threshold;
}
}
}
return new Object[]{bestGain, bestFeature, bestThreshold};
}
/**
* 构建决策树（CART）
*/
TreeNode buildTree(List<Sample> samples, int depth, int[] featureIndices) {
// 终止条件
if (depth >= maxDepth || samples.size() < minSamplesSplit) {
return createLeaf(samples);
}
// 检查是否所有样本标签相同
boolean sameLabel = true;
int firstLabel = samples.get(0).label;
for (Sample s : samples) {
if (s.label != firstLabel) { sameLabel = false; break; }
}
if (sameLabel) return createLeaf(samples);
// 寻找最优分裂
Object[] splitResult = findBestSplit(samples, featureIndices);
double gain = (Double) splitResult[0];
int feature = (Integer) splitResult[1];
double threshold = (Double) splitResult[2];
if (gain <= 0) return createLeaf(samples);
// 分裂样本
List<Sample> left = new ArrayList<>();
List<Sample> right = new ArrayList<>();
for (Sample s : samples) {
if (s.features[feature] <= threshold) left.add(s);
else right.add(s);
}
TreeNode node = new TreeNode();
node.featureIndex = feature;
node.threshold = threshold;
node.left = buildTree(left, depth + 1, featureIndices);
node.right = buildTree(right, depth + 1, featureIndices);
return node;
}
/**
* 创建叶子节点
*/
TreeNode createLeaf(List<Sample> samples) {
TreeNode leaf = new TreeNode();
leaf.featureIndex = -1;
// 投票选出最多标签
Map<Integer, Integer> counts = new HashMap<>();
for (Sample s : samples) {
counts.merge(s.label, 1, Integer::sum);
}
int maxCount = 0;
for (Map.Entry<Integer, Integer> entry : counts.entrySet()) {
if (entry.getValue() > maxCount) {
maxCount = entry.getValue();
leaf.predictedLabel = entry.getKey();
}
}
return leaf;
}
/**
* Bootstrap采样
*/
List<Sample> bootstrapSample(List<Sample> data, Set<Integer> oobIdx) {
List<Sample> sample = new ArrayList<>();
Set<Integer> selected = new HashSet<>();
Random rand = new Random();
for (int i = 0; i < data.size(); i++) {
int idx = rand.nextInt(data.size());
sample.add(data.get(idx));
selected.add(idx);
}
// OOB样本索引
for (int i = 0; i < data.size(); i++) {
if (!selected.contains(i)) oobIdx.add(i);
}
return sample;
}
/**
* 训练随机森林
*/
public void fit(List<Sample> data, int numTotalFeatures, int numClasses) {
this.numClasses = numClasses;
Random rand = new Random();
for (int t = 0; t < numTrees; t++) {
// Bootstrap采样
Set<Integer> oobIdx = new HashSet<>();
List<Sample> sample = bootstrapSample(data, oobIdx);
bootstrapSamples.add(sample);
oobIndices.add(oobIdx);
// 随机选取特征子集
int[] allFeatures = new int[numTotalFeatures];
for (int i = 0; i < numTotalFeatures; i++) allFeatures[i] = i;
// Fisher-Yates shuffle前numFeatures个
for (int i = numTotalFeatures - 1; i > 0; i--) {
int j = rand.nextInt(i + 1);
int tmp = allFeatures[i];
allFeatures[i] = allFeatures[j];
allFeatures[j] = tmp;
}
int[] featureSubset = Arrays.copyOf(allFeatures, numFeatures);
// 构建决策树
TreeNode tree = buildTree(sample, 0, featureSubset);
trees.add(tree);
}
}
/**
* 单棵树预测
*/
int predictOne(TreeNode node, double[] features) {
while (!node.isLeaf()) {
if (features[node.featureIndex] <= node.threshold) {
node = node.left;
} else {
node = node.right;
}
}
return node.predictedLabel;
}
/**
* 森林预测（投票）
*/
public int predict(double[] features) {
Map<Integer, Integer> votes = new HashMap<>();
for (TreeNode tree : trees) {
int pred = predictOne(tree, features);
votes.merge(pred, 1, Integer::sum);
}
int bestLabel = -1;
int maxVotes = -1;
for (Map.Entry<Integer, Integer> entry : votes.entrySet()) {
if (entry.getValue() > maxVotes) {
maxVotes = entry.getValue();
bestLabel = entry.getKey();
}
}
return bestLabel;
}
/**
* 预测概率分布
*/
public double[] predictProba(double[] features) {
double[] probs = new double[numClasses];
for (TreeNode tree : trees) {
int pred = predictOne(tree, features);
probs[pred]++;
}
for (int i = 0; i < numClasses; i++) {
probs[i] /= numTrees;
}
return probs;
}
/**
* OOB准确率评估
*/
public double oobScore(List<Sample> data) {
int correct = 0;
int total = 0;
for (int i = 0; i < data.size(); i++) {
// 收集预测该样本的所有树的预测结果
Map<Integer, Integer> votes = new HashMap<>();
for (int t = 0; t < numTrees; t++) {
if (oobIndices.get(t).contains(i)) {
int pred = predictOne(trees.get(t), data.get(i).features);
votes.merge(pred, 1, Integer::sum);
}
}
if (!votes.isEmpty()) {
int bestLabel = -1;
int maxVotes = -1;
for (Map.Entry<Integer, Integer> entry : votes.entrySet()) {
if (entry.getValue() > maxVotes) {
maxVotes = entry.getValue();
bestLabel = entry.getKey();
}
}
if (bestLabel == data.get(i).label) correct++;
total++;
}
}
return total == 0 ? 0 : (double) correct / total;
}
/**
* 特征重要性（基于Gini减少量）
*/
public double[] featureImportance(int numFeatures) {
double[] importance = new double[numFeatures];
// 简化版：统计每棵树中各特征的使用次数
for (TreeNode tree : trees) {
countFeatures(tree, importance);
}
// 归一化
double sum = 0;
for (double v : importance) sum += v;
if (sum > 0) {
for (int i = 0; i < numFeatures; i++) {
importance[i] /= sum;
}
}
return importance;
}
void countFeatures(TreeNode node, double[] importance) {
if (node == null || node.isLeaf()) return;
importance[node.featureIndex]++;
countFeatures(node.left, importance);
countFeatures(node.right, importance);
}
public static void main(String[] args) {
// 测试案例：二维平面上的二分类问题（XOR的变种）
List<Sample> data = new ArrayList<>();
Random rand = new Random(42);
// 类别0：中心(2,2)附近的点
for (int i = 0; i < 100; i++) {
data.add(new Sample(new double[]{
2 + rand.nextGaussian() * 0.5,
2 + rand.nextGaussian() * 0.5
}, 0));
}
// 类别1：中心(5,5)附近的点
for (int i = 0; i < 100; i++) {
data.add(new Sample(new double[]{
5 + rand.nextGaussian() * 0.5,
5 + rand.nextGaussian() * 0.5
}, 1));
}
// 训练随机森林
RandomForest rf = new RandomForest(50, 10, 5, 2);
rf.fit(data, 2, 2);
// OOB评估
double oobAccuracy = rf.oobScore(data);
System.out.println("OOB准确率：" + String.format("%.4f", oobAccuracy));
// 测试预测
int[] testLabels = {0, 1, 0, 1};
double[][] testFeatures = {
{2.0, 2.0},
{5.0, 5.0},
{1.8, 2.2},
{5.2, 4.8}
};
System.out.println("预测结果：");
for (int i = 0; i < testFeatures.length; i++) {
int pred = rf.predict(testFeatures[i]);
double[] proba = rf.predictProba(testFeatures[i]);
System.out.println(" 真实=" + testLabels[i] + ", 预测=" + pred
+ ", 概率=[" + String.format("%.3f", proba[0]) + ", "
+ String.format("%.3f", proba[1]) + "]");
}
// 特征重要性
double[] imp = rf.featureImportance(2);
System.out.println("特征重要性：" + String.format("%.3f", imp[0]) + ", " + String.format("%.3f", imp[1]));
}
}
复杂度分析
| 阶段 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 训练（单棵树） | O(m × n log n) | O(n) |
| 训练（T棵树） | O(T × m × n log n) | O(T × n) |
| 预测（单棵树） | O(log n) | O(1) |
| 预测（森林） | O(T × log n) | O(1) |
其中n为样本数，m为特征数，T为树的数量。
调参建议
- numTrees：通常100-500棵，更多树提升稳定性但增加计算量
- maxDepth：控制过拟合，通常10-30
- numFeatures：分类任务取√m，回归任务取m/3
- minSamplesSplit：节点最小分裂样本数，越大越不容易过拟合
应用场景
- 金融风控：信用评分、欺诈检测
- 医疗健康：疾病诊断、基因表达分类
- 电商推荐：用户行为预测、商品分类
- 自然语言处理：文本分类、情感分析
总结
随机森林通过Bagging和特征随机化，有效降低了决策树的方差，同时保持了较低的偏差。其OOB评估机制提供了便捷的性能估计方式，而特征重要性分析则有助于理解模型决策过程。作为一种”开箱即用”的算法，随机森林是机器学习实践中的可靠选择。
