相关概念
随机变量X的熵定义为：
因为随机变量X的熵与X的取值没关系，只取决于X的分布，所以也可以记作$H(p)$。如果对数以2为底，此时熵的单位是比特；如果对数以e为底，此时熵的单位是奈特。
条件熵：
信息增益：特征A对训练数据集D的信息增益$g(D,A)$，定义为集合D的经验熵$H(D)$与特征A给定条件下D的经验条件熵$H(D|A)$之差，即
熵$H(D)$与条件熵$H(D|A)$之差也称为互信息。设训练数据集为D，$|D|$表示为样本容量；设有K个类，$|C_k|$表示属于第k类的样本个数；设特征A的取值有n个，根据特征A的取值可以将D划分为n个不同的子集$D_1,D_2,…,D_n$，$|D_i|$为子集$D_i$中的样本个数；记子集$D_i$中属于第k类的样本集合为$D_{ik}$，信息增益可以通过如下公式计算：
信息增益比：以信息增益作为划分训练数据集的特征，存在偏向于选择取值较多的特征的问题，使用信息增益比可以对这一问题进行校正，信息增益比通过如下公式计算：
基尼指数：分类问题中，假设有K个类，样本点属于第k类的概率为$p_k$，则概率分布p的基尼指数可以定义为：
对于二类分类问题，若样本点属于第一个类的概率是p，则该概率分布的基尼指数为：
对于给定的样本集合D，其基尼指数为：
如果样本集合D根据特征A是否取某一可能值a被分割成$D_1$和$D_2$两部分，则在特征A的条件下，集合D的基尼指数为：
（$Gini(D,A)$的计算方式与条件熵$H(D,A)$有点类似）
代码实现
决策树的生成方式采用递归的方式，对于初始数据集D，计算所有特征对数据集D的信息增益（或信息增益比），选择信息增益最大（或信息增益比最大）的特征，根据该特征的取值对数据集进行划分（可能不止两个子节点），然后对划分的数据集递归使用这种生成算法。使用信息增益作为特征选择指标的算法叫ID3算法；使用信息增益比作为特征选择指标的算法叫做C4.5算法；ID3算法不能直接处理连续型特征，C4.5对其进行了改进，对于连续型特征，采用分桶的方式处理成离散型特征；CART算法与ID3和C4.5类似，但只生成二叉树，而且可以处理回归问题，回归时的拟合误差采用均方误差。
在实现之前需要考虑写的决策树具有什么样的功能，按照哪种算法来实现。查阅sklearn的决策树官方文档发现，sklearn里实现的是优化过的CART算法，并且无法处理离散型特征。为了便于实现，本文实现的决策树算法生成的是一棵二叉分类树，并且只能处理连续型特征，采用信息增益作为分裂的准则，每次分裂通过遍历所有特征的所有分裂点来选择最优的分裂特征，并且通过控制树的最大深度、最小信息增益量来控制过拟合。决策树的每一个内部节点需要保存该节点分列时用的哪一个特征以及分裂值，还需要保存孩子节点的指针，如果是叶子节点，需要保存当前叶子节点对应的标签（叶子 标签的计算采用投票法，即当前叶子节点的样本中出现次数最多的标签）。做预测时，只要根据输入的样本从树的根节点走到叶子节点即可。
代码的框架大致如下：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53class TreeNode:
def __init__(self, feature_idx=None, threshold=None, target=None,
target_proba=None, left_child=None, right_child=None):
self.feature_idx = feature_idx # 用于分裂的特征编号
self.threshold = threshold # 用于分裂的特征值
self.left_child = left_child # 左子树
self.right_child = right_child # 右子树
self.target = target # 如果是叶子节点，则保存对应的label
self.target_proba = target_proba # 如果是叶子节点，则保存每一个label的概率
class DecisionTree:
def __init__(self, min_samples_split=2, min_info_gain=1e-7, max_depth=float("inf")):
self.root = None
self.min_samples_split = min_samples_split
self.min_info_gain = min_info_gain
self.max_depth = max_depth
def _entropy(self, y):
"""计算信息熵"""
pass
def _info_gain(self, y, y1, y2):
"""计算信息增益"""
pass
def _leaf_calculation(self, y):
"""计算叶子节点对应的标签、对应标签的概率"""
pass
def _data_split(self, X, feature_idx, threshold):
"""将数据集根据第feature_idx个特征分成两部分：该特征值小于等于threshold的分为一部分，剩下的为另一部分"""
pass
def _build_tree(self, X, y, current_depth=0):
"""构建决策树"""
pass
def _search_tree(self, x, proba=False, tree=None):
"""搜索树"""
pass
def fit(self, X, y):
"""训练决策树"""
pass
def predict(self, X):
"""预测"""
pass
def predict_proba(self, X):
"""预测概率"""
pass
用sklearn自带的iris数据集测试实现的决策树算法，accuracy可以达到0.96。1
2
3
4
5
6
7
8
9
10data = datasets.load_iris()
X, y = data.data, data.target
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2)
model = DecisionTree()
model.fit(X_train, y_train)
y_pred = model.predict(X_test)
accuracy = accuracy_score(y_test, y_pred)
print(f'Accuracy = {accuracy}')
完整代码在这里。
总结
本文实现了可以处理连续型特征的二叉分类树，采用信息增益作为分裂时特征选择的标准。还有许多有趣的问题可以考虑，例如加上离散特征的处理、增加回归树的实现等。还可以基于当前的实现的决策树来实现随机森林算法，因为随机森林包含多棵基本决策树，每棵基本决策树都对输入样本进行采样，并且使用特征集的某个子集来进行分裂，最后的结果由所有基本决策树的结果来共同决定（投票、平均等）。