这篇博客用来简要介绍决策树算法（DecisionTree）
决策树是机器学习中常用的一种算法，它即可用于解决分类问题，也可用于解决回归问题，在这篇博客我们只介绍分类决策树。
决策树顾名思义是一种树形结构，而我们的任务就是想办法构建出这样一颗树用它来进行分类。
在开始介绍决策树的构建之前，首先介绍几个相关概念，信息熵、条件熵以及信息增益：
信息熵：
我个人的理解，信息熵就是用来衡量一个随机变量取值的不确定性的一个指标，信息熵越大则不确定性越大，信息熵越小则不确定性也就越小。
假设一个随机变量的概率分布如下：
| |
.... | |||
| .... |
则随机变量X的信息熵的计算公式如下：
通常情况下对数以2为底或以（自然对数）为底，并且我们规定如果
则定义
。
一个服从两点分布的随机变量的信息熵图像如下图所示：
可以看出当概率时，信息熵最大，随机变量的不确定性也就最大，从直观的角度这也很容易理解，即如果随机变量属于两个值的概率都相等，那我们很难确定它属于哪一个值，反之如果不相等，则我们将猜测随机变量属于概率大的哪一个值。
条件熵：
设二维随机变量的概率分布为：
我们将随机变量给定条件下随机变量
的条件熵表示为
，表示在已知随机变量
的情况下随机变量
的不确定性，其定义如下：
实际上就是给定的条件下随机变量
的熵对于
的期望值。
信息增益：
信息增益表示为，其含义为给定
的能够使随机变量
的确定性增加的程度。
计算方式如下：
这个很好理解，当我们知道某些信息时肯定是要比什么都不知道的时候更能确定某个随机变量的取值，除非这些信息是无效信息，否则肯定会带来确定性的增加，即信息增益。
接下来我们就来探究决策树的构建过程：
决策树由节点和有向边所构成，节点分为叶子节点和内部节点两部分，通常情况下，节点分支都为二叉的，如下图所示：
图中圆形为内部节点，方块为叶子节点。
我们以案例驱动的方式来解释决策树是如何构建出来的，其过程分为两步，特征选择以及决策树的生成。
首先我们给定一张数据表，数据表中记录的是一些贷款信息，如下图所示：
| ID | 年龄 | 有工作 | 有房子 | 信贷情况 | 类别 |
| 1 | 青年 | 否 | 否 | 一般 | 否 |
| 2 | 青年 | 否 | 否 | 好 | 否 |
| 3 | 青年 | 是 | 否 | 好 | 是 |
| 4 | 青年 | 是 | 是 | 一般 | 是 |
| 5 | 青年 | 否 | 否 | 一般 | 否 |
| 6 | 中年 | 否 | 否 | 一般 | 否 |
| 7 | 中年 | 否 | 否 | 好 | 否 |
| 8 | 中年 | 是 | 是 | 好 | 是 |
| 9 | 中年 | 否 | 是 | 非常好 | 是 |
| 10 | 中年 | 否 | 是 | 非常好 | 是 |
| 11 | 老年 | 否 | 是 | 非常好 | 是 |
| 12 | 老年 | 否 | 是 | 好 | 是 |
| 13 | 老年 | 是 | 否 | 好 | 是 |
| 14 | 老年 | 是 | 否 | 非常好 | 是 |
| 15 | 老年 | 否 | 否 | 一般 | 否 |
我们的任务就是构建一颗决策树来进行判断是否同意某个人的贷款申请。
我们用随机变量来表示类别（0表示否，1表示是），
表示年龄（0表示青年，1表示中年，2表示老年），
是否有工作（0表示否，1表示是），
表示是否有房子（0表示否，1表示是），
表示信贷情况（0表示一般，1表示好，2表示非常好）
根节点包含的样本：所有样本
根节点信息熵：
根节点各个特征的条件熵：
计算信息增益：
因此可以确定，当分支特征为（是否有房子）时带来的信息增益越大，因此根节点的分支特征选择为是否有房子，分为左右两支，左子节点中的数据集为没有房子的样本，右子节点的数据集为有房子，之后以此类推便构建出了决策树模型。
综上，每个节点的分支过程可以分为以下几步：
1.确定当前节点的信息熵以及各个特征的条件熵
2.计算各个特征的信息增益
3.确定当前节点的分支特征
那么，我们如何决定什么时候停止分支呢？我们可以这样设置，当某个节点的信息熵小于某个阈值时我们就停止对这个节点的分支操作，那么此节点也就成为了叶子节点。
最终我们需要确定每个叶子结点的类别，即叶子结点中的样本集中，占比最大的那一个类别便是当前叶子节点的类别，当新来一个样本我们只需要按照决策树从顶层向下逐步判断，看样本最终落入那个叶子结点，所落入的叶子结点的类别便是当前样本的预测类别。
至此决策树的基本原理已经介绍完毕，要说明的是，以上介绍的只是决策树当中的ID3算法，在ID3算法提出之后，相继又提出了C4.5算法和CART，与ID3算法不同的是，C4.5算法采用的特征选择指标是信息增益率而不是信息增益，其他原理同ID3相同。实际上信息增益率的计算方法也相当简单，就是信息增益与特征的熵的比值；而CART（Class and Regression Tree）从名字看出来即可做分类又可做回归，与ID3不同的是，作为分类树时，其选择划分节点的特征的依据是基尼系数，选择使得划分后数据集基尼系数最小的那个特征作为节点的划分的特征。如果是构建回归树，则划分节点的特征的选择是依据划分后子节点的方差，我们尽可能选择使得方差最小的划分特征，我们往往使用启发式的方式来搜索划分特征以及划分特征的值，即依次遍历各个维度的特征，当遍历到当前维度特征时，依次遍历当前特征的所有值作为划分值从而选出使得子节点方差最小的划分特征以及特征的值。
以下为本人使用Python编写的决策树的相关程序：
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
import numpy as np
from sklearn.metrics import accuracy_score
class DecesionTree(object):
def __init__(self, stop_entropy, deepth):
"""
:param stop_entropy: 终止分裂的最小熵值
:param deepth: 决策树最大深度
"""
self.stop_entropy = stop_entropy
self.deepth = deepth
data = load_iris()
x = data["data"]
y = data["target"]
self.x_train, self.x_test, self.y_train, self.y_test = train_test_split(x, y, random_state=2, test_size=0.3)
self.tree = {}
for layer in range(deepth):
self.tree[layer] = [None] * 2 ** layer
attr_max_values = np.max(self.x_train, axis=0)
attr_min_values = np.min(self.x_train, axis=0)
# self.split_values用来记录每一维特征的所有可能的分割值， self.split[i]表示第i维特征的所有可能的分割值
self.split_values = []
for min_value, max_value in zip(attr_min_values, attr_max_values):
self.split_values.append(np.linspace(min_value, max_value, 102, endpoint=True)[1:-1])
def generate_tree(self):
for layer in range(self.deepth):
# 遍历是第几层节点
# node_num用于标记当前层节点的个数
node_num = 2 ** layer
for node_index in range(1, node_num + 1):
# 先确定当前节点的数据集，标记
node = Node()
if layer == 0:
# 如果是第0层，则当前节点node的数据集就是训练集
node.data_set = self.x_train
node.labels = self.y_train
else:
# 如果不是0层，则需要根据父节点来获取当前节点的数据集
# previous_index为生成当前节点的上一层父节点的索引
previous_index = int(np.ceil(node_index / 2)) - 1
previous_node = self.tree[layer - 1][previous_index]
if (previous_node is None) or (previous_node.attr_split is None):
# 判断如果父节点为叶子节点则跳过当前节点的构造
continue
attr_split = previous_node.attr_split
split_value = previous_node.split_value
data_set = previous_node.data_set
labels = previous_node.labels
if node_index % 2 != 0:
# 上一层节点的左分支（小于分割值）
data_index = data_set[:, attr_split] < split_value
node.data_set = data_set[data_index]
node.labels = labels[data_index]
else:
# 上一层节点的右分支（大于等于分割值）
data_index = data_set[:, attr_split] >= split_value
node.data_set = data_set[data_index]
node.labels = labels[data_index]
# 确定当前节点数据集后，计算当前节点信息熵，确定是否进行分割，如果小于停止分割信息熵，则不分割，否则分割
current_node_entropy = self.calc_entropy(node.labels)
if current_node_entropy < self.stop_entropy:
# 小于停止分割信息熵则不对当前节点的attr_split以及split_value赋值，当前节点成为叶子节点
self.tree[layer][node_index - 1] = node
continue
else:
# 确定当前节点的分割特征以及分割特征的值
courrent_entropy_gain = 0
current_attr_split = None
current_split_value = None
for attr_split_index in range(4):
# 遍历四个维度的特征
for split_value in self.split_values[attr_split_index]:
entropy_gain = self.calc_entropy_gain(attr_split_index, split_value, node.data_set, node.labels)
if entropy_gain >= courrent_entropy_gain:
courrent_entropy_gain = entropy_gain
current_attr_split = attr_split_index
current_split_value = split_value
node.attr_split = current_attr_split
node.split_value = current_split_value
self.tree[layer][node_index - 1] = node
values = list(self.tree.values())
for value in values:
if np.all(np.logical_not(np.array(value, np.bool))):
index_ = values.index(value)
break
else:
index_ = self.deepth
nodes = self.tree[index_ - 1]
for node in nodes:
if isinstance(node, Node):
node.attr_split = None
node.split_value = None
def calc_entropy(self, labels):
"""
:param labels: 要计算熵值的数据集的标记
:return: 数据集的熵值
"""
# 计算信息熵
label_unique = np.unique(labels)
labels_list = list(labels)
p_list = []
for label in label_unique:
p_list.append(labels_list.count(label) / len(labels_list))
entropy = 0
for p in p_list:
entropy -= p * np.log2(p)
return entropy
def calc_condition_entropy(self, attr_split, split_value, data_set, labels):
"""
:param attr_split: 用来分割数据集的特征
:param split_value: 用来分割数据集的特征的值
:param data_set: 被分割的数据集
:param labels: 被分割的数据集标记
:return: 条件熵, 大于分割特征特征值的数据集和标记以及小于分割特征特征值的数据集和标记
"""
# 计算小于分割值的数据集的熵
smaller_index = data_set[:, attr_split] < split_value
smaller_data_set = data_set[smaller_index]
smaller_label = labels[smaller_index]
smaller_entropy = self.calc_entropy(smaller_label)
# 计算大于分割值的数据集的熵
bigger_index = data_set[:, attr_split] >= split_value
bigger_data_set = data_set[bigger_index]
bigger_label = labels[bigger_index]
bigger_entropy = self.calc_entropy(bigger_label)
# 两部分熵加权求和得到条件熵
p_smaller = len(smaller_label) / len(labels)
p_bigger = len(bigger_label) / len(labels)
condition_entropy = p_smaller * smaller_entropy + p_bigger * bigger_entropy
return condition_entropy, bigger_data_set, bigger_label, smaller_data_set, smaller_label
def calc_entropy_gain(self, attr_split, split_value, data_set, labels):
entropy = self.calc_entropy(labels)
condition_entropy = self.calc_condition_entropy(attr_split, split_value, data_set, labels)[0]
entropy_gain = entropy - condition_entropy
return entropy_gain
def leaf_node_label(self):
# 确定叶子节点的类别
nodes = []
nodes_list = self.tree.values()
for nd in nodes_list:
nodes.extend(nd)
while True:
if None in nodes:
nodes.remove(None)
else:
break
for node in nodes:
if not node.split_value:
labels = np.unique(node.labels)
p = []
for label in labels:
p.append(list(node.labels).count(label) / len(node.labels))
node.predict_label = labels[p.index(max(p))]
def test(self):
self.y_test_pred = []
for test_sample in self.x_test:
current_nodes = [self.tree[0][0]]
for layer in range(1, self.deepth):
current_attr_split = current_nodes[-1].attr_split
current_split_value = current_nodes[-1].split_value
# 寻找下一个子节点
if test_sample[current_attr_split] < current_split_value:
current_node = self.tree[layer][self.tree[layer - 1].index(current_nodes[-1]) * 2]
else:
current_node = self.tree[layer][self.tree[layer - 1].index(current_nodes[-1]) * 2 + 1]
current_nodes.append(current_node)
if not current_node.split_value:
# 如果已经到叶节点就不在继续
break
y_pred = current_nodes[-1].predict_label
self.y_test_pred.append(y_pred)
print("鸢尾花数据测试集预测结果：")
print("测试集预测类别：", self.y_test_pred)
print("测试集真实类别：", list(self.y_test))
print("预测准确率：%.2f%s" % (100 * accuracy_score(self.y_test, self.y_test_pred), "%"))
class Node(object):
def __init__(self):
# self.data_set为当前节点的样本
self.data_set = None
# self.labels为当前节点的样本对应的标记
self.labels = None
# self.attr_split为用来分割当前节点的特征是哪一维
self.attr_split = None
# self.split_value为分割当前节点特征的分割值是多少
self.split_value = None
# 如果当前节点为叶子节点，则self.predict_label代表当前叶节点的类别
self.predict_label = None
def main():
tree = DecesionTree(0.2, 3)
tree.generate_tree()
tree.leaf_node_label()
tree.test()
if __name__ == "__main__":
main()