1 介绍
决策树（Decision Tree）是机器学习中比较经典的算法之一，也属于有监督学习中的一员。与线性模型（逻辑回归、神经网络等）不同的是，它的学习过程不是为每个特征学习一个权重，而是根据某种决策不断的对数据集进行分裂，使得到的子数据集上的标签越来越纯净，最终得到的模型就是一个树形结构，故其名曰决策树。
2 原理
决策树算法的效果好，可用于分类，也可用于回归 (比如CART树) 。决策树有多种，这里我介绍三种最经典的决策树：ID3、C4.5、C5.0。这三种树的唯一区别就是在节点划分时决策的选择上有所不同。
2.1 ID3
公式详解：
进入正题之前先了解一下什么是信息熵 (香农熵) ，前面说了决策树是不断的对数据集进行划分，使子数据集的标签越来越纯净，那么纯净度该如何度量呢？
(D表示数据集样本数量，Ck表示数据集中类别为k的样本数量，K为数据集的类别数)
上述公式即可对一个数据集D的纯净度进行度量，统计各类标签所占总样本的比例即可得到。H(D)越小，表示数据集D的标签纯度越高。
了解了信息熵之后，再来看一下什么是信息增益。信息增益显然就是两个信息熵之间的差距，具体来说，信息增益等于未划分时数据集的信息熵，减去划分之后所有子数据集的信息熵之和。
( Gain(D,A)表示用特征A划分得到的信息增益，H(D)表示未划分时D的信息熵，H(D|A)表示用特征A划分得到的所有子数据集的信息熵之和 )
 ( Di 表示划分之后得到的子数据集数量，H(D |
A) 就是各个子数据集信息熵 H(Di) 的加权求和,权重为子样本数占全部样本的比例 ) |
ID3算法： 决策树每次对数据集进行划分需要选择最优的划分特征，ID3就是对每个特征进行遍历，然后计算按此特征划分后得到的信息增益，选择增益最大的特征进行数据集的划分。然后再对每个子数据集进行同样的划分操作。
算法缺点： 1 ID3信息增益准则对可取值数目较多的特征有所偏好，比如ID类特征的信息增益可接近于1； 2 只能用于处理离散分布的特征，不能处理连续值与缺失值； 3 只能用于分类。
2.2 C4.5
为了克服ID3倾向于取值数目较多的特征的缺陷，C4.5在信息增益的基础上添加了分母项，引入了信息增益率，计算公式如下：
分母项Ha会对取值数目较多的特征进行惩罚，特征取值数目越多，Ha越大，信息增益率就越小。所以很好的解决了ID3的缺点1。信息增益率同信息增益，都是越大越好。
[注]：信息增益率虽然解决了倾向于取值较大的特征，但是又引入了倾向于取值较少特征的缺陷，所以其选择特征时不是直接选取信息增益率最大的特征，而是先从候选特征中找到信息增益高于平均值的特征，再从中选择使增益率最高的作为最优划分特征。
优点： 1 改进ID3倾向于选择取值较多的特征的缺点； 2 可处理连续值与缺失值。 缺点： 1 跟ID3一样只能用于分类； 2 计算量较大，计算信息熵有大量的对数运算，以及选取最优特征时，对连续值的排序等。
2.3 C5.0 (CART)
C5.0又称为CART(分类回归树)，C5.0抛弃了用信息熵来衡量数据集的纯净度，使用了一种更简单的计算方式，称为基尼系数，其公式如下：
Gini(D)表示从D中随机抽取两个样本，这两个样本的标签不一样的概率。概率越小，表示同类的样本数越多，数据集D越纯净，这性质与信息熵越大样本越纯净相反。
C5.0不再是考量划分前后信息熵的差距，而是基尼系数的差距。C5.0的计算过程没有引入log对数计算，所以它的计算复杂度要优于ID3与C4.5。
优点： 1 使用 Gini 系数来度量样本纯净度，减少了大量的对数运算； 2 可同时用于分类与回归； 缺点： 1 同ID3都倾向于多取值特征
3 总结
4 代码实现
该代码为ID3的实现： (修改节点划分函数NodeSplit中增益gain的计算，即可扩展成C4.5与C5.0)
import numpy as np
import pandas as pd
class DecisionTree:
def __init__(self):
pass
#信息熵的计算
def getEnt(self, data):
labels = data.iloc[:, -1] #取标签列，默认最后一列为样本标签
ent = 0 #信息熵初始化0
p = labels.value_counts().values/len(labels) #每一类标签数量/总样本数，列表p存储每类标签所占比例
ent -= p*np.log2(p) #列表ent为每类标签的信息熵
return np.sum(ent) #对所以类标签求和得到整个样本信息熵
#遍历寻找最优划分特征
def NodeSplit(self, data):
beforeEnt = self.getEnt(data) #划分前data的信息熵
bestFeature = -1 #最优划分特征的下标
bestGain = 0 #记录最大信息增益
for i in range(data.shape[1]-1):#遍历每个特征，除了标签
val = data.iloc[:, i].value_counts().index
ents = 0
for v in val: #遍历特征i的所有取值
childData = data[data.iloc[:, i] == v] #取特征i的取值为v的部分样本
ents += (len(childData)/len(data)) * self.getEnt(childData) #计算子样本的信息熵(累加)
gain = beforeEnt - ents #划分前后的信息增益
if(gain>bestGain):
bestGain = gain #更新最大增益
bestFeature = i #记录最优划分特征下标
return bestFeature
#根据找到的最优划分特征，对数据集进行划分
def DataSplit(self, data, feature, value): #划分出特征feature下取值为value的样本
col = data.columns[feature] #根据下标取列名
childData = data.loc[data[col]==value, :]
childData = childData.drop(col, axis=1) #最优划分的特征使用一次后需删除
return childData
#递归生成 Decision Tree
def getTree(self, data):
columns = list(data.columns) #数据集所有的列
labels = data.iloc[:, -1].value_counts() #获取最后一列标签
#递归结束条件：
#1、样本标签全部为一类
#2、样本只剩下一个特征
if labels[0]==len(data) or len(columns)==1:
return labels.index[0] #返回标签
bestFeature = self.NodeSplit(data) #计算当前数据集最佳划分特征的索引
col = columns[bestFeature] #获取索引取对应的特征名
myTree = {col: {}} #采用字典嵌套的方式存储树信息
del columns[bestFeature] #使用后删除最优划分特征
for val in set(data[col]): #遍历特征col的每个特征值，对每一个值递归建树
childData = self.DataSplit(data, bestFeature, val) #取每个值对应的子样本
myTree[col][val] = self.getTree(childData) #对子样本进行建树,并保存在嵌套字典中
return myTree
修改NodeSplit中gain的计算，扩展成C4.5的代码如下：(C5.0比较简单，可自行实现)
# 替换NodeSplit()中的for循环即可，添加分母项 H
for i in range(data.shape[1]-1):#遍历每个特征，除了标签
val = data.iloc[:, i].value_counts().index
ents = 0
H = 0
for v in val: #遍历特征i的所有取值
childData = data[data.iloc[:, i] == v] #取特征i的取值为v的部分样本
ents += (len(childData)/len(data)) * self.getEnt(childData) #计算子样本的信息熵(累加)
p = len(childData)/len(data)
H -= p*np.log2(p)
gain = beforeEnt - ents #划分前后的信息增益
gain = gain/H
使用测试：
dict = {'a': [1, 1, 1, 0, 0],
'b': [1, 1, 0, 1, 1],
'c': [0, 1, 0, 1, 2],
'd': [1, 2, 1, 0, 1],
'label': ['yes', 'yes', 'no', 'no', 'no']}
Data = pd.DataFrame(dict)
print(DecisionTree().getTree(Data))
# 生成的tree如下：
# {'a': {0: 'no', 1: {'b': {0: 'no', 1: 'yes'}}}}
如有问题，欢迎与我联系。 如果您对机器学习其他算法感兴趣，可参考我的知乎
