作者：数据取经团 - JQstyle
本期将为大家带来决策树算法的介绍和实现，在机器学习领域、决策树为代表的一系列算法是不可忽视的一部分。当前在实际应用中较为主流的几种算法，如随机森林（RF）、梯度迭代决策树（GBDT）和XGBoost等，均是以决策树作为基础模型。
决策树简单介绍
决策树是一种基本的分类和回归方法，在本章中主要介绍的是运用于分类问题的决策树。决策树的基本模型结构是树形结构（可以为二叉树也可以非二叉树），包含了一系列节点和向边。节点按照所处于的位置和输出内容，可以分为内部节点和叶节点（居于底部）。
在决策树的分类流程中，从最顶部的根节点开始从输入数据的各个变量中的某一特征进行测试，根据测试结果，将实力分配到其下属的一个子节点中，在到达叶节点之前，该过程将会持续递归，知道输出叶节点的类别结果。决策树的基本结构如下图：
可以看出，每一条从根节点到叶节点的路径对应的是一条规则，即记录在各个对应字段上应满足的若干条件，这些规则有一个重要的性质：互斥且完备。
决策树的训练（ID3算法为例）
变量选择的指标介绍
决策树算法每次对一个内部节点的特征选择中，会根据某种方法确定最优特征，使得当前节点对各个数据子集有一个最好的分类过程。从根节点开始，不断进行特征选择的递归，直到满足某些条件（如当前数据子集已经基本可以被正确分类、节点深度达到阈值等），那么将构建叶节点，将当前的子集划分到对应的叶节点输出类别中。
对于每次内部节点的最佳特征选择的方法，比较常用的是基于信息增益指标大小来确定。为了计算目标变量和各特征字段的信息增益，首先引出信息熵的概念，信息熵指的是对一个变量的不确定性的度量，对于一个有限取值的离散型随机变量X，其每个可能的取值x都对应一个概率值p，那么信息熵的计算公式如下：
当信息熵的值越大，则该变量的不确定性越高（蕴含信息越丰富）。而对于两个变量X和Y，已知联合概率分布的情况下，定义给定条件X下的Y的条件概率分布熵（条件熵）的计算公式为：
显然，条件熵指的是在变量X的条件下，Y的不确定性的度量。最后，给出某个特征X对训练数据集目标Y的信息增益g(Y|X)的计算公式：
信息增益的含义可以理解为基于特征X下使得目标Y的分类不确定性的减少程度。在构建决策树的特征选择中，会选择当前数据集目标信息增益最大的特征作为分类依据，使得Y的不确定性显著降低。
ID3算法流程
ID3算法是最为基本的决策树训练方法之一。简单来说，就是从根节点开始，根据每次计算各个变量信息增益的大小，选择该指标最大的特征作为当前内部节点的分类依据，对于其子节点，递归进行，直到满足停止条件。具体如下：
对于输入的训练集：目标Y和特征集合A
输出决策树模型T
（1）若当前节点下所有的Y均属于同一类型Ck（或者属于Ck的比例超过某一阈值），则此时该节点为叶节点，输出类别Ck；
（2）当没有可以选择的特征，A=∅，则输出当前Y中实例数最多的Ck；
（3）开始计算A中各个特征对目标Y的信息增益，选择信息增益最大的特征X；
（4）若X的信息增益低于某个阈值，则依旧输出最多的实例Ck；
（5）否则，对X的每一个可能值x，将对应的数据集划分为若干子节点；
（6）对每一个子节点，递归执行上述步骤。
剪枝的介绍
决策树算法的性质决定了，当特征信息了足够的情况下，可以实现对训练集精确的拟合（理论上特征足够多的决策树可以实现对训练集的完美分类），但随着决策树的深度的增加，模型越加复杂，在对其他数据集的预测上，效果可能就会有所下降，即模型的泛华能力不够，产生过拟合问题。
对于此类问题的解决方式是剪枝。即去掉一些决策树的分支来降低过拟合问题。剪枝处理可以分为“预剪枝”和“后剪枝”。“预剪枝”指的是在决策树的训练过程中，在每个节点划分前就进行估计，若当前节点的划分不能带来泛化能力的提升，则停止节点划分并产生叶节点。
后剪枝指的是从训练以后得到的完整决策树，自底向上对内部节点进行考察，若将当前内部节点替换为叶节点可以使得泛化能力提升，则将改子树替换为叶节点。
为了测度当前模型的泛化能力，决策树训练之前会考虑将数据集划分出一部分作为“验证集”，这部分数据不参与模型训练，而是用于对模型预测效果的考察。
决策树的特点
作为一种常用的基础方法，决策树的优点非常明显。第一、决策树便于理解，相比于其它算法，通过生成的规则，在业务上具有良好的可解释性；第二、常成熟的决策树算法可以同时处理连续性和离散型数据，也可以很好地避免缺失值等影响；第三、决策树对数据量的要求不大；第四、决策树能够处理多输出问题；第五、在运算速度上，单决策树所花的时间相对较短。
决策树的缺陷在于：首先、常规的单一决策树模型容易陷入过拟合（可用剪枝等手段改善），泛化能力有限；其次、随着数据维度的增长，决策树的效率和预测效果会受到显著影响，及决策树不适合高维数据建模；再次、当决策树的规则中产生异或和复用的情况时，会影响对模型的理解。最后、单一决策树模型并不稳定，容易受到异常值的影响。当样本分布不均衡时，决策树的分类容易偏向多数类样本。
ID3决策树的简单实现
接下来，我们尝试用Python实现简单的ID3决策树算法。本次测试的数据集依旧为马疝病的生存预测数据，首先加载数据集
import numpy as np
import pandas as pd
horse = pd.read_table('/Users/jq_tongdun/Desktop/tech_learning/horseColicTraining.txt',
sep='\t',names=['x' + str(i) for i in range(21)]+['y'])
horse_t = pd.read_table('/Users/jq_tongdun/Desktop/tech_learning/horseColicTest.txt',
sep='\t',names=['x' + str(i) for i in range(21)]+['y'])因为ID3决策树无法直接处理连续型字段，我们需要对该数据集的数值型变量进行分箱，定义分箱函数，以1/3和2/3分位数为端点，将这些变量分为3箱。
#分箱器
def bin_get(x,your_bins):
new_x = x.copy()
for i in range(your_bins.shape[0]):
if i==0:
new_x[x<=your_bins[i]]=0
if i>0:
new_x[(x>your_bins[i-1])&(x<=your_bins[i])]=i
if i==your_bins.shape[0]-1:
new_x[x>your_bins[i]]=(i+1)
return new_x
#分箱:将horse数据集的每个数值型字段等分为三箱用于之后的ID3算法建模
horse_bin = horse.copy()
horse_t_bin = horse_t.copy()for i in range(horse.shape[1]-1):
if len(set(horse_bin.ix[:,i])) > 3:
horse_bin.iloc[:,i] = bin_get(horse.ix[:,i],
np.array(horse.ix[:,i].quantile([1/3.,1/6.])))
horse_t_bin.iloc[:,i] = bin_get(horse_t.ix[:,i],
np.array(horse.ix[:,i].quantile([1/3.,1/6.])))
horse_bin = np.array(horse_bin)
horse_t_bin = np.array(horse_t_bin)分箱结束后，将数据集转化为numpy矩阵，并且区分特征集X合目标Y：
#训练集和测试集
horse_train_x = np.array(horse.ix[:,range(21)])
horse_train_y = np.array(horse.ix[:,21])
horse_test_x = np.array(horse_t.ix[:,range(21)])
horse_test_y = np.array(horse_t.ix[:,21])
horse_bin_train = horse_bin[:,range(21)]
horse_bin_test = horse_t_bin[:,range(21)]然后开始设计ID3决策树模型,首先定义ID3类和信息增益的函数：
#ID3算法
class desicion_tree: #信息熵
import numpy as np
ID3_tree_model = {}
def inf_ent(self,x):#信息熵
inf_ent = 0
for type in set(x):
pi = float(sum(x==type))/x.shape[0]
inf_ent -= pi*np.log2(pi)
return (inf_ent)
def con_ent(self,y,x): #条件熵
con_ent = 0
for type in set(x):
yt = y[x==type]
pi = float(sum(x==type))/x.shape[0]
con_ent += pi*self.inf_ent(yt)
return(con_ent)
def inf_gain(self,y,x): #信息增益
inf_gain = self.inf_ent(y)-self.con_ent(y,x)
return(inf_gain)接下来定义模型的训练函数，在这里我们将停止条件设定为：当前节点的众数类别比例超过了某个阈值或者当前节点的记录数低于某个阈值，则停止并生成叶节点。
def des_ID3(self,x,y,x_name,stop_p=0.95,inf_min=0.1,thre_num=5): #ID3递归建模函数
ID3_tree = {}
max_rate = 0
y_res = 0
for tp in set(y):
if sum(y==tp)/float(y.shape[0]) > max_rate:
max_rate = sum(y==tp)/float(y.shape[0])
y_res = tp
if len(y) <= thre_num: #停止条件，当前叶节点Y记录数低于阈值时
return(y_res)
if max_rate >= stop_p : #停止条件，当前叶节点Y的众数比例超过阈值时
return(y_res)
inf_gain = np.zeros(x.shape[1])
for i in range(x.shape[1]): #计算各个特征对Y信息增益
inf_gain[i] = self.inf_gain(y,x[:,i])
sel_name = x_name[inf_gain == inf_gain.max()][0] #选择最大的信息增益的特征
x_name_new = x_name[inf_gain != inf_gain.max()]
for tp in set(x[:,inf_gain == inf_gain.max()][:,0]): #对选定特征的每一个取值下的子节点进行递归
y_new = y[x[:,inf_gain == inf_gain.max()][:,0]==tp]
x_new = x[x[:,inf_gain == inf_gain.max()][:,0]==tp,:]
x_new = x_new[:,inf_gain != inf_gain.max()]
ID3_tree[(sel_name, tp)] = self.des_ID3(x_new,y_new,x_name_new,stop_p=stop_p,inf_min=inf_min,thre_num=thre_num)
return(ID3_tree)
def des_ID3_fit(self,x,y,x_name,stop_p=0.95,inf_min=0.1,thre_num=5): #ID3最终使用的建模函数
self.ID3_tree_model = self.des_ID3(x,y,x_name,stop_p=stop_p,inf_min=inf_min,thre_num=thre_num)
return(self.ID3_tree_model)生成的决策树以一个字典的形式呈现，然后，定义模型的预测函数：
def ID3_predict_rec(self,x,x_name,model):
name = x_name[x_name == model.keys()[0][0]][0]
model = model[(name,x[x_name == model.keys()[0][0]][0])]
if isinstance(model,dict):
return(self.ID3_predict_rec(x,x_name,model=model))
else:
return(model)
def ID3_predict_line(self,x,x_name): #单条记录的预测函数
result = self.ID3_predict_rec(x,x_name,self.ID3_tree_model)
return(result)
def ID3_predict(self,x,x_name): #数据集预测函数
if self.ID3_tree_model == {}:
print("the model need to be trained")
else:
y_pre = np.zeros(x.shape[0])
for i in range(x.shape[0]):
y_pre[i] = self.ID3_predict_line(x[i,:],x_name)
return(y_pre)到此，对ID3决策树模型的设计就完成了，我们首先建立一个简单的数据集合，来进行测试。
example_x_name = np.array(["Age","Job","House","Credit"])
example_x = np.array([["youth","youth","youth","youth","youth","middle","middle",
"middle","middle","middle","old","old","old","old","old"],
['no','no','yes','yes','no','no','no','yes','no','no','no',
'no','yes','yes','no'],
['no','no','no','yes','no','no','no','yes','yes','yes',
'yes','yes','no','no','no'],
['common','good','good','common','common','common','good',
'good','very good','very good','very good','good','good',
'very good','common']]).T
example_y = np.array([0,0,1,1,0,0,0,1,1,1,1,1,1,1,0])该数据集包含了4个字段（年龄、工作、住房和信用），变量Y衡量是否为该记录的客户发放贷款（1为是，2为否）。建立模型，并且输出决策树结构：
#ID3算法测试
ID3_model=desicion_tree()
ID3_model.des_ID3_fit(x=example_x,y=example_y,x_name=example_x_name) #训练模型
ID3_model.ID3_tree_model #查看ID3决策树结果
ID3_model.ID3_predict(example_x,example_x_name) #对数据集的类别预测(回带)
从输出的模型结果可以看出，模型中包含了两个变量，三条规则。即：1、有住房的客户可以获得贷款；2、没有住房但是有工作的客户也可以获得贷款；3既没有住房、又没有工作的客户将被拒绝。
接下来，我们对分箱以后的马疝病数据集进行测试，并且给出对测试集的预测准确度。
#利用ID31对分箱以后的horse数据集进行测试
horse_name = np.array(['X%s' %i for i in range(21) ]) #为X字段命名
ID3_horse=desicion_tree()
ID3_horse.des_ID3_fit(x=horse_bin_train,y=horse_train_y,x_name=horse_name,stop_p=0.8,thre_num=10) #训练模型
sum(ID3_horse.ID3_predict(x=horse_bin_test,x_name=horse_name)==horse_test_y)/float(len(horse_test_y)) #测试准确度建立的决策时对测试集的预测准确度可以达到73%以上，分类效果尚可。
ID3决策树模型较为简单，缺陷也很明显，在实际中通常会采用该算法的改进版本C4.5(最新的C5.0)算法，这些算法具有同时处理离散和连续变量，采用信息增益率来代替信息增益进行特征选择以及剪枝上的优化以提高泛化能力等优势。
拓展：CART决策树
CART是一种二叉树决策树模型，顾名思义，这种决策树的每个内部节点的特征只有两条向边连接两个子节点，取值分别为是和否，这样的决策树等价于递归二分每个特征。
基尼指数的特征选择
CART分类决策树中，目标Y存在K个类别时，其概率的基尼指数定义为：
当Y只有两个类别时，第一个类别的概率为p，公式可以简化为：
而特征X(被二分)对于Y的基尼指数定义如下：
当基尼指数越大，则说明变量的不确定性越大（与熵指标类似），对于连续型变量，CART决策树会尝试每个变量中所有记录值作为二分变量切分点，选择基尼系数最小的点切分变量，并对比所有变量当前切分后的基尼系数，确定最优特征。
CART决策树流程
下面给出CART分类决策树的建模流程
输入:训练数据集各个字段A和目标字段Y，停止计算的条件。
输出：CART决策树模型
(1)判断当前节点是否满足停止条件，若满足则生成叶节点；
(2)对当前节点，计算A中线有特征对该数据集的基尼指数，对于任一特征X，对其可能的每个取值x，根据样本点X=x测试为是或否将数据集分割为两部分，计算X=x时候Y的基尼指数；
(3)在所有特征A以及他们的可能切分点x中，选择基尼指数最小的特征和对应的且分店作为最有特征和最优切分点。对应地，此节点根据切分以后的最优特征生成两个子节点；
(4)递归上述步骤，直到停止而生成模型。
对于CART决策树的实现，为节约篇幅，参见本文的附件代码。
CART决策树的测试
运用python实现了CART决策树，该模型可以直接用于数值型变量进行建模而不需要预先进行分箱。因此，直接采用马疝病生存预测的数据集进行测试：
#基于之前的horse数据集测试
cart_model=cart_tree() #实例化
cart_model.cart_tree_fit(horse_train_x[:,:2],horse_train_y,horse_name,thre_num=5) #模型训练
cart_model.cart_tree #查看决策树的内容
cart_model_pre = cart_model.cart_predict(horse_test_x,horse_name) #预测
sum(cart_model_pre == horse_test_y)/float(len(horse_test_y)) #准确度
从输出的模型的预测准确度可以看出，CART模型在分类预测中也可以取得较好的效果。
Sklearn库建立CART决策树
机器学习库Sklearn中已经包含了很多决策树类的算法，其中tree.DecisionTreeClassifier函数包含了一系列决策树的建模参数，如特征选择的依据，最大数的深度（即垂直方向上内部节点数），每个内部节点的最小样本数等。在默认情况下，该函数采用基尼系数作为变量选择的依据，即为CART决策树模型。利用该函数进行建模测试：
#采用sklearn模块构建cart决策树
from sklearn import tree
clf_cart =tree.DecisionTreeClassifier(criterion='gini',max_depth = 5,min_samples_leaf=5) #实例化，区分一个内部节点需要的最少的样本数为10，一个叶节点最小样本数为5
clf_cart.fit(horse_train_x,horse_train_y) #模型训练
clf_cart_pre = clf_cart.predict(horse_test_x) #预测
sum(clf_cart_pre == horse_test_y)/float(len(horse_test_y)) #准确度在模型中，我们设定最大树深为5，每个叶节点最小样本数为5，可以实现70%以上的预测准确度。（值得注意的是，这一棵决策树的复杂度要低于先前笔者自行编写的决策树模型，而当复杂度越高的时候，决策树就越有可能会陷入过拟合的问题）
绘制决策树
对于输出的sklearn决策树模型，我们可以将其绘制出来以更加形象地进行展示，在此过程中我们需要安装graphviz工具和相应的库。代码如下：
import pydotplus
from sklearn.tree import export_graphviz
from IPython.display import Image
with open(r"/Users/jq_tongdun/Desktop/tree.dot",'w') as f: #保存决策树模型
f = export_graphviz(clf_cart, feature_names = horse_name, out_file = f)
graph = pydotplus.graphviz.graph_from_dot_file(r"/Users/jq_tongdun/Desktop/tree.dot")
#graph.write_pdf(r"/Users/jq_tongdun/Desktop/tree.pdf") #创建PDF存储决策树图
Image(graph.create_png()) #直接绘制绘制出的决策树部分结果如下图：
