决策树与随机森林

1. 决策树概述

决策树（Decision Tree）是一种树形结构的监督学习方法，可用于分类和回归任务。每个内部节点表示一个特征上的判断条件，每个叶节点表示一个类别（分类树）或一个连续值（回归树）。

1.1 决策树示例

                    天气?
                  /   |   \
               晴天  多云   雨天
               /       \       \
          湿度?      ✓出门   风力?
         /   \             /   \
       高    低         强    弱
       ✗      ✓          ✗     ✓

1.2 核心思想

决策树学习的本质是：从训练数据中归纳出一组分类规则，使得树的结构与数据的分布尽可能一致，同时具有良好的泛化能力。

1.3 决策树学习算法

常见的决策树学习算法包括：

算法	特征选择标准	支持任务
ID3	信息增益	分类
C4.5	信息增益比	分类
CART	基尼系数/均方误差	分类/回归

2. 特征选择

2.1 信息熵

信息熵是衡量随机变量不确定性的度量：

H (X) = - i = 1 \sum K p_{i} lo g p_{i}

当所有概率相等（ $p_{i} = 1/ K$ ）时，熵最大；当某一类概率为1时，熵为0。

2.2 条件熵

给定随机变量 $Y$ 后， $X$ 的条件熵：

H (X ∣ Y) = j \sum P (Y = y_{j}) H (X ∣ Y = y_{j})

2.3 信息增益

信息增益是得知特征 $Y$ 后，特征 $X$ 的不确定性减少量：

g (X, Y) = H (X) - H (X ∣ Y)

在ID3算法中，选择信息增益最大的特征进行分裂。

2.4 信息增益比

信息增益偏好取值多的特征，C4.5使用信息增益比进行修正：

g_{R} (X, Y) = \frac{g ( X , Y )}{H ( Y )}

2.5 基尼系数

CART算法使用基尼系数：

Gini (X) = 1 - k = 1 \sum K p_{k}^{2}

基尼系数表示从数据集中随机抽取两个样本，其类别不一致的概率。基尼系数越小，数据纯度越高。

Gini_index (D, a) = v = 1 \sum V \frac{∣ D ^{v} ∣}{∣ D ∣} \cdot Gini (D^{v})

3. ID3算法

3.1 算法流程

输入：训练数据集 D，特征集 A
输出：决策树 T

1. 若 D 中所有实例属于同一类 C，则 T 为单节点树
2. 若 A 为空，则 T 为单节点树，将 D 中实例数最多的类作为该节点的类标记
3. 否则，按算法选择最优特征 A_g：
   - 计算每个特征的信息增益
   - 选择信息增益最大的特征
4. 对 A_g 的每一个可能值 a_i：
   - 为 T 生成一个节点
   - 将 D 中 A_g = a_i 的子集 D_i 作为该节点的训练数据
5. 递归地对 D_i 调用步骤 1-4

3.2 示例

假设数据集 $D$ 包含两类，熵 $H (D) = 0.971$ 。

特征 $A$ 将数据分成两部分：

$D_{1}$ ： $H (D_{1}) = 0$ ，有3个样本
$D_{2}$ ： $H (D_{2}) = 0.971$ ，有7个样本

则条件熵：

H (D ∣ A) = \frac{3}{10} \cdot 0 + \frac{7}{10} \cdot 0.971 = 0.6797

信息增益：

g (D, A) = H (D) - H (D ∣ A) = 0.971 - 0.6797 = 0.2913

4. C4.5算法

C4.5是ID3的改进版本，主要改进：

使用信息增益比选择特征
可以处理连续特征（通过二分法）
可以处理缺失值
在树构建过程中进行剪枝

5. CART算法

5.1 CART分类树

CART（Classification and Regression Tree）使用二叉树结构，每个节点只产生两个子节点。

对于分类树，使用基尼系数选择最优特征和切分点。

5.2 CART回归树

对于回归树，使用平方误差作为损失函数：

j, s min c_{1} min x_{i} \in R_{1} (j, s) \sum (y_{i} - c_{1})^{2} + c_{2} min x_{i} \in R_{2} (j, s) \sum (y_{i} - c_{2})^{2}

其中：

$j$ 是特征索引
$s$ 是切分点
$R_{1} (j, s)$ 和 $R_{2} (j, s)$ 是根据 $(j, s)$ 划分的两个区域

6. 决策树剪枝

6.1 预剪枝

在决策树生成过程中，提前停止分裂。

优点：减少过拟合风险，减少训练时间
缺点：可能欠拟合

6.2 后剪枝

先生成完整的决策树，然后自底向上剪枝。

REP剪枝（Reduced Error Pruning）：

使用验证集评估每个节点
如果剪枝后验证集精度不下降，则剪枝

代价复杂度剪枝（CCP，CART使用）：

C_{α} (T) = C (T) + α ∣ T ∣

其中 $C (T)$ 是训练误差， $∣ T ∣$ 是叶节点数， $α$ 是惩罚参数。

7. 随机森林

7.1 集成学习思想

随机森林（Random Forest）是Bagging的扩展，通过构建多棵决策树并集成它们的预测结果来提高准确性和稳定性。

7.2 随机森林的两重随机性

Bagging：每棵树的训练数据是通过有放回抽样从原始数据集中抽取的
特征随机：每棵树在分裂时，只从随机选取的特征子集中选择最优特征

7.3 算法流程

输入：训练集 D，决策树个数 T，特征子集大小 m

对于 t = 1 到 T：
    1. 使用Bootstrap抽样从 D 中抽取训练集 D_t
    2. 使用 D_t 训练一棵决策树：
       - 在每个节点分裂时，随机选择 m 个特征
       - 从这 m 个特征中选择最优特征进行分裂
    3. 不进行剪枝（或只做少量剪枝）

输出：随机森林 {T_1, T_2, ..., T_T}

通常 $m = p$ （分类）或 $m = p /3$ （回归），其中 $p$ 是特征总数。

7.4 预测

分类：多数投票
$\overset{y}{^} = ar g c max t = 1 \sum T I (T_{t} (x) = c)$
回归：平均
$\overset{y}{^} = \frac{1}{T} t = 1 \sum T T_{t} (x)$

8. 代码实现

8.1 决策树实现

import numpy as np
from collections import Counter
 
class DecisionTree:
    def __init__(self, max_depth=10, min_samples_split=2, criterion='gini'):
        self.max_depth = max_depth
        self.min_samples_split = min_samples_split
        self.criterion = criterion
        self.tree = None
    
    def _gini(self, y):
        counts = Counter(y)
        probs = [count / len(y) for count in counts.values()]
        return 1 - sum(p ** 2 for p in probs)
    
    def _entropy(self, y):
        counts = Counter(y)
        probs = [count / len(y) for count in counts.values()]
        return -sum(p * np.log2(p) for p in probs if p > 0)
    
    def _best_split(self, X, y):
        best_gain = -1
        best_feat = None
        best_thresh = None
        
        criterion_func = self._gini if self.criterion == 'gini' else self._entropy
        current_impurity = criterion_func(y)
        
        for feat in range(X.shape[1]):
            thresholds = np.unique(X[:, feat])
            for thresh in thresholds:
                left_mask = X[:, feat] <= thresh
                right_mask = ~left_mask
                
                if sum(left_mask) == 0 or sum(right_mask) == 0:
                    continue
                
                left_impurity = criterion_func(y[left_mask])
                right_impurity = criterion_func(y[right_mask])
                
                n_left, n_right = sum(left_mask), sum(right_mask)
                gain = current_impurity - (n_left * left_impurity + n_right * right_impurity) / len(y)
                
                if gain > best_gain:
                    best_gain = gain
                    best_feat = feat
                    best_thresh = thresh
        
        return best_feat, best_thresh
    
    def _build_tree(self, X, y, depth=0):
        if len(np.unique(y)) == 1 or depth >= self.max_depth or len(y) < self.min_samples_split:
            return Counter(y).most_common(1)[0][0]
        
        feat, thresh = self._best_split(X, y)
        if feat is None:
            return Counter(y).most_common(1)[0][0]
        
        left_mask = X[:, feat] <= thresh
        right_mask = ~left_mask
        
        tree = {
            'feature': feat,
            'threshold': thresh,
            'left': self._build_tree(X[left_mask], y[left_mask], depth + 1),
            'right': self._build_tree(X[right_mask], y[right_mask], depth + 1)
        }
        return tree
    
    def fit(self, X, y):
        self.tree = self._build_tree(np.array(X), np.array(y))
    
    def _predict_sample(self, x, tree):
        if not isinstance(tree, dict):
            return tree
        if x[tree['feature']] <= tree['threshold']:
            return self._predict_sample(x, tree['left'])
        return self._predict_sample(x, tree['right'])
    
    def predict(self, X):
        return [self._predict_sample(x, self.tree) for x in X]

8.2 随机森林实现

class RandomForest:
    def __init__(self, n_trees=100, max_depth=10, min_samples_split=2, max_features='sqrt'):
        self.n_trees = n_trees
        self.max_depth = max_depth
        self.min_samples_split = min_samples_split
        self.max_features = max_features
        self.trees = []
    
    def _bootstrap_sample(self, X, y):
        n_samples = X.shape[0]
        indices = np.random.choice(n_samples, n_samples, replace=True)
        return X[indices], y[indices]
    
    def fit(self, X, y):
        X, y = np.array(X), np.array(y)
        n_features = X.shape[1]
        
        if self.max_features == 'sqrt':
            max_feat = int(np.sqrt(n_features))
        elif self.max_features == 'log2':
            max_feat = int(np.log2(n_features))
        else:
            max_feat = n_features
        
        self.trees = []
        for _ in range(self.n_trees):
            X_boot, y_boot = self._bootstrap_sample(X, y)
            
            # 随机选择特征子集
            feat_indices = np.random.choice(n_features, max_feat, replace=False)
            X_boot_subset = X_boot[:, feat_indices]
            
            tree = DecisionTree(max_depth=self.max_depth, 
                               min_samples_split=self.min_samples_split)
            tree.fit(X_boot_subset, y_boot)
            self.trees.append((tree, feat_indices))
    
    def predict(self, X):
        X = np.array(X)
        predictions = []
        for tree, feat_indices in self.trees:
            preds = tree.predict(X[:, feat_indices])
            predictions.append(preds)
        
        # 多数投票
        result = []
        for i in range(X.shape[0]):
            votes = [p[i] for p in predictions]
            result.append(Counter(votes).most_common(1)[0][0])
        return np.array(result)

8.3 使用sklearn

from sklearn.tree import DecisionTreeClassifier, plot_tree
from sklearn.ensemble import RandomForestClassifier
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from sklearn.metrics import accuracy_score, classification_report
 
# 加载数据
iris = load_iris()
X, y = iris.data, iris.target
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3, random_state=42)
 
# 决策树
dt = DecisionTreeClassifier(max_depth=5, criterion='gini')
dt.fit(X_train, y_train)
dt_pred = dt.predict(X_test)
print(f"Decision Tree Accuracy: {accuracy_score(y_test, dt_pred):.4f}")
 
# 随机森林
rf = RandomForestClassifier(n_estimators=100, max_depth=10, random_state=42)
rf.fit(X_train, y_train)
rf_pred = rf.predict(X_test)
print(f"Random Forest Accuracy: {accuracy_score(y_test, rf_pred):.4f}")
 
# 特征重要性
print("\nFeature Importances:")
for name, importance in zip(iris.feature_names, rf.feature_importances_):
    print(f"  {name}: {importance:.4f}")
 
# Out-of-Bag Score
rf_oob = RandomForestClassifier(n_estimators=100, oob_score=True, random_state=42)
rf_oob.fit(X_train, y_train)
print(f"\nOOB Score: {rf_oob.oob_score_:.4f}")

9. 随机森林的特有性质

9.1 Out-of-Bag (OOB) 误差

由于每棵树只使用了约63.2%的原始数据（约1 - 1/e），剩余的约36.8%样本可以作为验证集。

OOB Error = \frac{1}{N} i = 1 \sum N I (\overset{y}{^}_{i}^{OOB} \neq = y_{i})

9.2 特征重要性

随机森林可以计算特征重要性：

Importance (X_{j}) = \frac{1}{T} t = 1 \sum T impurity_reduction (X_{j}, T_{t})

基尼重要性（Mean Decrease in Gini）：

MDI_{j} = t \sum k \sum \frac{n _{k}^{(t)}}{n ^{(t)}} \cdot Gini (k)^{(t)} \cdot I (X_{j}^{(t)} = k)

9.3 泛化误差上界

随机森林的泛化误差上界为：

P E^{*} \leq \frac{ρ ˉ \cdot s ^{2}}{T}

其中 $\overset{ρ}{ˉ}$ 是树之间的平均相关性， $s$ 是单棵树的分类强度。

10. 优缺点分析

决策树

优点	缺点
简单直观，易解释	容易过拟合
可以处理非线性关系	对噪声敏感
不需要特征缩放	小的变化可能导致树结构大变化
可以处理混合特征	不稳定

随机森林

优点	缺点
减少过拟合	计算成本高
可以处理高维数据	比单棵决策树难解释
可以并行训练	在某些噪声大的问题上可能过拟合
不用特征缩放
可以估计不确定性

11. 应用场景

11.1 特征选择

随机森林的特征重要性可以用于特征选择，筛选出最重要的特征。

Metaphor

探索