1. 概述

前段时间搭好了一个多因子框架，从几十个因子里面挑出了5个表现比较好的因子，先进行了MLP的训练，但是因为因子数据太少，模型基本上没学习到什么东西，迭代一次，损失就不再下降了。于是决定采用随机森林模型来训练，这个系列将把自己学习模型过程中的经验分享出来，与大家一同交流。大家都知道，随机森林是由若干决策树组成的，所谓几十个臭皮匠，顶个诸葛亮。那么本文就先分享决策树模型，我们将从零开始实现完整的代码。

2.决策树

我们以下面这个例子为例，假如我们要租房，需要根据西区还是东区以及房间的数量来决定是否可以支付的起。

样本数据

Neighbourhood	# of rooms	Affordable (boolean)
West	3	Yes
West	5	Yes
West	2	Yes
East	3	Yes
East	4	Yes
East	6	No
East	5	No
East	2	Yes

如果要根据这些数据来构建一个决策树，应该是怎么样的呢？我们可以考虑下先选择根节点，这里有两个选择，一个是社区，另一个是房间数。那么我们应该选择哪个呢？
大家可以先考虑下，再往下看，也可以动手画一张试试看。

实际上决策树的算法中是两个都会选，然后选出Information Gain（信息增益） 最大的那个特征。我们先来看看什么是信息增益，以及信息增益计算要用到的熵（Entropy）。

信息增益（Information Gain）

信息增益是衡量某一特征对于分类任务的重要性，它反映了引入该特征后系统信息的不确定性（熵）的减少量。
信息增益（Information Gain）定义为在特征 ( A ) 的条件下，数据集 ( D ) 熵的减少量：

$IG(D, A) = H(D) - \sum_{v \in \text{Values}(A)} \frac{|D^v|}{|D|} \cdot H(D^v)$

其中：

( H(D) ) 表示数据集 ( D ) 的熵：

$H(D) = - \sum_{k=1}^K p_k \log_2 p_k$

( p_k ) 表示数据集中第 ( k ) 类的样本所占比例

我们以K=2的情况来说明，就是两种要么A要么B

从图中的曲线可以看出来，p在0.5的是最大，说明了熵值越大，数据越混乱

信息论角度

熵 = 不确定性 = 平均信息量
当两类样本数量相等时，预测最困难
需要最多的信息才能确定样本类别
这就是"最混乱"的状态

直观理解

想象一个盒子里有红球和蓝球：

情况	红球比例	熵值	混乱程度	预测难度
全红球	p ≈ 1	H ≈ 0	无混乱	很容易
5红5蓝	p = 0.5	H = 1	最混乱	最困难
全蓝球	p ≈ 0	H ≈ 0	无混乱	很容易

这就是为什么在决策树中，我们选择信息增益最大的特征来分割数据——它能最有效地减少混乱程度，提高分类的确定性。

公式看起来有点麻烦，实际上我们结合上面的实例，对着公式手算一遍之后，就都理解了。

原始数据集熵

总共8个样本：6个Yes，2个No
H(原始) = -(6/8)×log₂(6/8) - (2/8)×log₂(2/8) ≈ 0.811

按"社区"分割

West子集：4个样本，全是Yes → H(West) = 0
East子集：4个样本，2个Yes，2个No → H(East) = -(2/4)×log₂(2/4) - (2/4)×log₂(2/4) =1.0
加权平均熵 = (4/8)×0 + (4/8)×1.0 = 0.5
信息增益 = 0.811 - 0.5 = 0.311

数据集中，发现大于等于5个以上就出现NO的情况，那么我们用房间数<5来区分。

按"房间数<5"分割

<5房间：5个样本，4个Yes，1个No → H = 0.722
≥5房间：3个样本，2个Yes，1个No → H = 0.918
加权平均熵 = (5/8)×0.722 + (3/8)×0.918 ≈ 0.795
信息增益 = 0.811 - 0.795 = 0.016

决策树构建过程

计算每个特征的信息增益
选择信息增益最大的特征作为分割点
递归地对子节点重复这个过程

在这个例子中，"社区"特征的信息增益（0.311）> "房间数"特征的信息增益（0.016），所以**"社区"被选为根节点的分割特征**。

信息增益对比

分割特征	信息增益	选择结果
社区位置	0.311	✅ 被选择
房间数<5	0.016	❌ 未选择

得到的决策树，如图中所示：

每一层都按同样的方法进行，直到达到我们期望的结束条件。
对于小数据集，可以期望节点完全纯净，即（熵 = 0）。而对于大数据集，则需要设置最大层数，以防止过拟合的现象。

介绍完理论部分，我们接下来就开始实战代码吧，手写一遍估计对模型的理解会更深刻。

3.代码示例

节点类

class Node:
    def __init__(self, feature=None, threshold=None, left=None, right=None, *, value=None):
        self.feature = feature  # Index of the feature to split on
        self.threshold = threshold  # Value to split the feature on
        self.left = left  # Left child node
        self.right = right  # Right child node
        self.value = value
        
    def is_leaf_node(self):
        return self.value is not None

is_leaf 用来判断是是叶节点，对于非叶节点，Value是None

🍃 什么是 `value`？

在决策树中，value 通常代表预测结果：
- 分类问题：value 表示类别标签，如 $0$ 或 $1$
- 回归问题：value 是某一组样本的均值、中位数或其他聚合值

只有叶子节点（Leaf Node）才持有 value，用于预测。

🧠 非叶子节点为什么没有 `value`？

非叶子节点的职责是划分数据，而不是直接给出预测。

它们保存的是：

分裂特征编号 $\text{feature}$
分裂阈值 $\text{threshold}$
左子树、右子树引用

因此，它们不需要 value。
我们结合下面的例子简单说明：

 feature_0 < 2.5
   /        \
[value=3.2] feature_1 < 1.1
		/       \
	[value=4.0] [value=5.1]

根节点根据 feature_0 做分裂，无 value

左子节点满足条件，直接预测 $3.2$

右子节点继续用 feature_1 分裂

最终叶子节点分别预测 $4.0$ 和 $5.1$

接下来就是实现DecisionTree的类，主要是实现树的构造，非常巧妙，跟着视频手写了一遍，感觉很受用，后面尝试脱离视频多写几遍，相信对模型的理解会更加深刻。

完整的代码如下：

from collections import Counter

import numpy as np


class Node:
    def __init__(self, feature=None, threshold=None, left=None, right=None, *, value=None):
        self.feature = feature  # Index of the feature to split on
        self.threshold = threshold  # Value to split the feature on
        self.left = left  # Left child node
        self.right = right  # Right child node
        self.value = value  # Class label for leaf nodes

    def is_leaf_node(self):
        return self.value is not None


class DecisionTree:

    def __init__(self, min_samples_split=2, max_depth=100, n_features=None):
        """ 初始化决策树
        :param min_samples_split: 最小样本分割数
        :param max_depth: 最大树深度
        :param n_features: 特征数量
        """
        self.min_samples_split = min_samples_split
        self.max_depth = max_depth
        self.n_features = n_features
        self.root = None

    def fit(self, X, y):
        """ 训练决策树模型
        :param X: 特征矩阵
        :param y: 标签向量
        """
        self.n_features = X.shape[1] if self.n_features is None else min(X.shape[1], self.n_features)
        self.root = self._grow_tree(X, y)

    def _grow_tree(self, X, y, depth=0):
        """ 递归构建决策树
        :param X: 特征矩阵
        :param y: 标签向量
        """
        n_samples, n_feats = X.shape
        n_labels = len(np.unique(y))
        # check the stopping criteria
        if (depth >= self.max_depth or n_labels == 1 or n_samples < self.min_samples_split):
            leaf_value = self.most_common_label(y)
            return Node(value=leaf_value)
        # 从 n_feats 个特征中，随机选择 self.n_features 个特征索引（不重复），存到 feat_idxs 中。
        feat_idxs = np.random.choice(n_feats, self.n_features, replace=False)
        # find the best split
        best_feature, best_threshold = self._best_split(X, y, feat_idxs)
        # create child nodes
        left_idx, right_idx = self._split(X[:, best_feature], best_threshold)
        left = self._grow_tree(X[left_idx, :], y[left_idx], depth + 1)
        right = self._grow_tree(X[right_idx, :], y[right_idx], depth + 1)
        return Node(feature=best_feature, threshold=best_threshold, left=left, right=right)

    def _best_split(self, X, y, feat_idxs):
        best_gain = -1
        split_idx, split_threshold = None, None

        for feat_idx in feat_idxs:
            X_column = X[:, feat_idx]  # 从特征矩阵 X 中，提取第 feat_idx 列（即某一个特征），作为一个向量 X_column
            thresholds = np.unique(X_column)

            for thr in thresholds:
                gain = self._information_gain(X_column, y, thr)

                if gain > best_gain:
                    best_gain = gain
                    split_idx = feat_idx
                    split_threshold = thr

            return split_idx, split_threshold

    def _information_gain(self, X_column, y, threshold):
        parent_entropy = self._entropy(y)

        # create children
        left_idx, right_idx = self._split(X_column, threshold)

        if len(left_idx) == 0 or len(right_idx) == 0:
            return 0

        # calculate the weighted average of the entropy of the children
        n = len(y)
        n_l, n_r = len(left_idx), len(right_idx)
        e_l, e_r = self._entropy(y[left_idx]), self._entropy(y[right_idx])
        child_entropy = (n_l / n) * e_l + (n_r / n) * e_r

        # calculate the information gain
        gain = parent_entropy - child_entropy
        return gain

    def _split(self, X_column, threshold):
        left_idx = np.argwhere(X_column <= threshold).flatten()
        right_idx = np.argwhere(X_column > threshold).flatten()
        return left_idx, right_idx

    def _entropy(self, y):
        hist = np.bincount(y)  # 即使某些整数值（如 0）没有出现在 y 中，np.bincount() 也会把它们补上
        # y = np.array([0, 1, 1, 2, 2, 2])
        # hist = np.bincount(y) [1 2 3] 0:1 time,1:2 times,2:3 times
        ps = hist / len(y)
        return -np.sum([p * np.log2(p) for p in ps if p > 0])

    def most_common_label(self, y):
        """ 返回最常见的标签 """
        counter = Counter(y)
        value = counter.most_common(1)[0][0]
        return value

    def predict(self, X):
        return np.array([self._traverse_tree(x, self.root) for x in X])

    def _traverse_tree(self, x, node):
        """ 遍历树，找到叶节点 """
        if node.is_leaf_node():
            return node.value
        feature_value = x[node.feature]
        if feature_value <= node.threshold:
            return self._traverse_tree(x, node.left)
        else:
            return self._traverse_tree(x, node.right)

测试代码，代码中用的数据集是乳腺癌诊断数据集（Breast Cancer Wisconsin Dataset），用于二分类任务。

from sklearn import datasets
from sklearn.model_selection import train_test_split
import numpy as np

from ml.learn.decision_tree import DecisionTree

data = datasets.load_breast_cancer()
X, y = data.data, data.target

X_train, X_test, y_train, y_test = train_test_split(
    X, y, test_size=0.2, random_state=1234
)

clf = DecisionTree(max_depth=10)
clf.fit(X_train, y_train)
predictions = clf.predict(X_test)


def accuracy(y_test, y_pred):
    return np.sum(y_test == y_pred) / len(y_test)


acc = accuracy(y_test, predictions)
print(acc)

输出的acc=0.9035087719298246准确度还可以。

4.结语

要真正理解一个机器学习模型，最好的办法就是自己手写一个出来，这样才能明白模型的底层原理，而且当遇到需要调优的时候，也知道从哪些地方下手，跟大家一起共勉，下一期，将分享如何从零开始构建随机森林模型。下次见！