二叉决策树

从哈基米开始

决策树(Decision Tree)是一种预测分类模型，我们从一个例子讲起。假设我们有若干小动物的外貌特征样本，比如耳朵的形状、面部形状、有无胡须等。这些特征量 $x$ 对应其动物种类： $y=1$ 表示是哈基米， $y=0$ 表示不是哈基米。

我们可以根据这些特征建立一个树结构，即决策树结构。它代表的是对象属性与对象值之间的一种映射关系。这个树结构的成分如下

分支节点：决策节点，根据属性值确定接下来沿左分支或右分支
叶子节点：表示某个对象
从根节点到叶子结点：决策过程

决策树就好比一个问答游戏，根据问题回答的不同逐渐缩小搜索范围，最终确定一个对象。对于一个给定的训练集，我们可以构造不同结构、不同大小的决策树。这可以理解为提问问题的先后顺序不同，而其预测表现可能有所差异。

[{"url":"/img/mlearning/m7f1.png","alt":"同一训练集的不同决策树","title":""}]

因此，决策树算法就是要训练并找到一个最有效的决策树预测结构。构建一个决策树通常有以下几个关键步骤，他们共同决定了该决策树的模型表现。

如何在每个分支节点上选择合适的特征量，以对样本进行分割或划分
何时停止对样本的分割
如何设置决策树的大小、深度

本部分先以二叉树形式的决策树讲起，即对于每个特征量 $x_i\in\{0,1\}$ 。

信息熵

一组样本的信息熵(Entropy)可以表示其基尼不纯度(Gini Impurity)，是表示数据集分类混杂程度的指标。当数据完全属于单一类别时信息熵为0，多类别均匀分布时信息熵最大。对于一个 $K$ 类别集 $X$ ，其信息熵定义为

$H(X)=-\sum_{i=1}^Kp_i\log_2(p_i),\quad p_i=P(y=i),(x,y)\in X$

特别地，对于一个二分类问题的训练集，设 $p_1=P(X=1)$ 为正类占比，那么有信息熵函数

$H(p_1)=-p_1\log_2(p_1)-(1-p_1)\log_2(1-p_1)$

对 $H(x)$ 求导有

$H'(x)=\log_2\frac{1-x}{x}$

当 $x=0.5$ 时 $H'(x)=0$ ，不难证明此时 $H(x)$ 取极大值。这也代表两种类别均匀分布，因此不纯度最大。当 $x=0,1$ 时 $H(x)=0$ ，这代表两种类只存在一种，因此不纯度最小。

我们在选取某一节点的对应特征时，应该尽可能的让两个分支的分类结果都尽可能纯，这样能减少分割次数，同时增加准确性。换言之，我们应尽可能使得其信息熵更小。因此可以引入数学方法，通过计算信息熵确定一个节点对应的最佳特征。

信息增益

信息熵是针对某个集定义的，不能凭此判断整个分类系统的优劣。作记号规定

$D$ ：某个分支节点
$x_D$ ：分支节点 $D$ 上被用于分割样本的特征
$L,R$ ：分支节点 $D$ 分割后左、右分支的样本集
$w_L,w_R$ ： $L,R$ 中样本数量占 $D$ 原样本数量的比例，且 $w_L+w_R=1$

分支节点 $D$ 对特征 $A$ 的信息增益(Information Gain)定义为

$IG(D,x_D)=H(D)-\Big(w_LH(L)+w_RH(R)\Big)$

信息增益表示了分支节点 $D$ 对应特征 $x_D$ 时数据纯度的提升程度。下图主观的给出了三种不同的分割效果，可以直观看出最左侧的决策方法是最优的，并且其信息增益最大。

[{"url":"/img/mlearning/m7f2.png","alt":"不同决策方式的信息增益","title":""}]

ID3算法

基于前面的内容，我们可以总结构造一个较优决策树的方法，称之为ID3算法或C4.5算法

从根节点开始创建决策树结构
对分支节点 $D$ 和所有当前可用特征 $x_i$ ，确定使得 $\max IG(D,x_i)$ 的特征 $x_D$
对 $D$ 中的当前样本依据特征 $x_D$ 进行分割，创建左、右分支和分支节点
对于每个分支，重复(2,3)步骤，直到以下几种情况之一发生，停止分割
- 某个节点的信息熵为0，即样本类别一致
- 当前节点深度超过了决策树的规定最大深度
- 该节点所有可能的信息增益值均小于规定阈值
- 该节点的样本数量小于阈值

创建决策树通常可使用递归(Recursion)的方法。定义一个以节点 $D$ 为根节点并基于当前信息 $S$ 创建决策树的函数 $DT(D,S)$ ，其左、右分支的首个分支节点也可以看做两个决策树的根节点。因此，可以递归调用函数 $DT(D_L,S_L)$ 和 $DT(D_R,S_R)$ 。

正因为使用递归方法，因此需要设置递归的最大深度，防止因递归深度过大而栈溢出。

决策树的优化

独热编码

对于前文的哈基米分类问题，我们假定了每个特征量都是二分类的，这显然是不现实的。现实中的分类问题亦是如此，一个特征量可能有许多不同的取值，而引入多分支结构很容易使得模型过拟合。

举例而言，假设存在特征量 $x$ 作为样本唯一对应的编号ID，那么ID3算法很可能会选择其作为用于分割的特征。这样虽然能保证划分纯度，但显然是毫无用处的。

一种过渡的解决方法是使用独热编码(One-Hot Encoding)，即对于一个 $k$ 类特征 $x(k>2)$ ，创建 $k$ 个新的二类特征 $x_1,x_2,\cdots,x_k$ 替代 $x$ 。

例如，把“动物耳朵的形状”作为一个特征量，其形状可能是圆形、椭圆形、三角形等等，那么我们就用以下数个新特征量代替原来的特征量即可

耳朵形状是否为圆形
耳朵形状是否为椭圆形
耳朵形状是否为三角形
(…)

这种思路和一对多分类问题是很相似的，其也可以用到神经网络上。

连续型特征量

在哈基米分类的问题中，如果引入一些连续型特征量，比如重量、体长等，我们就不能使用处理离散型特征量的方法。当决策树用某个连续型特征量进行分割时，我们选择一个阈值 $t$ ，使得大于该阈值的样本进入一个分支，小于等于该阈值的样本进入另一个分支。

选取阈值 $t$ 时，我们仍然遵循ID3算法的规定，尝试若干个阈值 $t_1,t_2,\cdots,t_{m-1}$ ，并选取使得分支节点的信息增益最大的阈值。一般而言，设 $m$ 个样本的某连续型特征量 $x$ 取值从小到大为 $x_{(1)},x_{(2)},\cdots,x_{(m)}$ ，习惯上取阈值分别为

$t_i=\frac{x_{(i+1)}-x_{(i)}}{2},\quad i=1,2,\cdots,m-1$

[{"url":"/img/mlearning/m7f3.png","alt":"阈值的选择","title":""}]

当然，如果能通过数学方法在全局找到一个使得信息增益最大的阈值 $t_0$ ，当然可以无脑讲起设为阈值。但在样本数量足够大时，使用上述离散型取值方法已经能足够了。

回归树

前面提到的决策树都用来处理离散型分类问题，本节来讨论处理连续型回归问题的一类树结构算法，称之为回归树(Regression Tree)，其可以视作决策树的推广模型。

在哈基米分类例子中，我们把预测输出“该动物是否为哈基米”改为“该动物的重量”，这就变成了一个回归问题。简单来说，我们可以在决策树模型的基础上做两点改动

把每个叶子节点的输出改为该节点训练结果的样本输出的平均值
修改分支节点的分割策略

对于第二点，由于预测结果是连续型的，因此我们不再使用信息熵、信息增益，而使用样本方差。对于样本集合 $X=\{x_1,x_2,\cdots,x_m\}$ ，其样本方差定义为

$s^2(X)=\frac{1}{m-1}\sum_{i=1}^{m}(x_i-\bar{x})^2$

因此，考虑某个分支节点 $D$ 对于特征 $x_D$ 的分割，其左右分支为 $L,R$ ，定义

$\text{Split}(D,x_D)=s^2(D)-\Big(w_Ls^2(L)+w_Rs^2(R)\Big)$

这个值越大，表明该分割使得方差降低程度越大，因此不纯度减少的更多，选择特征量的方式完全可以类比决策树。到此，回归树的构造方法就可以参考决策树的ID3构造方法了。

CART算法

一种更稳定的决策树算法是CART算法，其主要采用基尼不纯度而非信息熵衡量信息的纯度。对于一个 $K$ 类别集 $X$ ，其概率分布的基尼不纯度定义为

$\text{Gini}(X)=-\sum_{i=1}^Kp_i(1-p_i),\quad p_i=P(y=i),(x,y)\in X$

从基尼不纯度的计算式可以看出，它的计算更加方便，是信息熵公式泰勒展开后的近似式。此外，CART算法还采用了代价复杂度剪枝的技巧，增强了其预测能力，这里我们不深入讲述。

树集成

随机森林

由于树结构对于信息的改变十分敏感，因此一个分类问题对应的决策树可能有许多合理的结构形式，这些决策树构成一个随机森林(Random Forest)。这些决策树可能会给出不同的预测结果，而我们可以通过这些决策树输出的趋势或比例确定一个更可能的预测结果。

设原始训练集样本量为 $m$ ，一个随机森林有 $B$ 棵决策树。对于每一个决策树，我们采用有放回抽样的方法得到一个样本容量同样为 $m$ 的训练集。这一步称作自主采样(Bootstrap)，其不保证样本数据的不重复性。

为了使得这些决策树具有一定的随机性，对于每一个决策树的分支节点 $D$ ，我们从其可选的全部特征中随机选取一个子集，并从这个子集中寻找合适的特征量。这样可以保证每棵决策树在略有不同的数据和特征视角下进行训练，从而获得比单棵决策树更稳定、更强大的性能。

一般而言，若可选特征数为 $n$ ，则选择大小为 $k=[\sqrt{n}]$ 的特征子集。

当每棵决策树输出预测结果时，我们统计所有预测结果，并取票数最多的类别作为最终结果。这一步称作聚合(Aggregating)，而随机森林算法的整个过程包含了Bootstrap和Aggregating，因此合称其为Bagging算法。

XGBoost

另一种强大的集成树算法简称XGBoost(eXtreme Gradient Boosting)，其基于梯度提升树(Gradient Boosting Tree)实现，主要思想是对决策树预测效果不理想的样本加强训练，并且引入了正则项、并行计算等优化策略，是一种较为高效的集成树算法。

[{"url":"/img/mlearning/m7f4.png","alt":"XGBoost","title":""}]

代码实现

仍然以鸢尾花识别项目为例，决策树的Python代码可以通过库函数简单实现。

from sklearn import datasets
from sklearn.model_selection import train_test_split
from sklearn.tree import DecisionTreeClassifier
from sklearn.metrics import accuracy_score
from sklearn import tree

# 加载鸢尾花数据集
iris = datasets.load_iris()
X = iris.data
y = iris.target

# 数据集划分
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)

# 初始化模型
clf = DecisionTreeClassifier(criterion='entropy', max_depth=3)

# 训练模型
clf.fit(X_train, y_train)

# 预测
y_pred = clf.predict(X_test)

# 评估模型
accuracy = accuracy_score(y_test, y_pred)
print(f"模型准确率: {accuracy:.2f}")

# 可视化决策树
text_representation = tree.export_text(clf)
print("决策树结构：")
print(text_representation)