先计算样本的总体信息熵：
再计算属性的信息增益及信息增益率：
选择增益率大的来进行划分
用python代码实现：
from sklearn.preprocessing import LabelEncoder, OneHotEncoder
from sklearn.externals.six import StringIO
from sklearn import tree
import pandas as pd
import numpy as np
import pydotplus
import sys
df = pd.read_excel("input.xlsx")
if __name__ == '__main__':
with open("input.xlsx", 'r') as fr:
loan = np.array(df).tolist()
loan_target = [] #提取每组数据的类别，保存在列表里
for each in loan:
loan_target.append(each[-1])
loanLabels = ['age', 'worK', 'house', 'Credit conditions'] #特征标签
loan_list = [] #保存loan数据的临时列表
loan_dict = {} #保存loan数据的字典，用于生成pandas
for each_label in loanLabels: #提取信息，生成字典
for each in loan:
loan_list.append(each[loanLabels.index(each_label)])
loan_dict[each_label] = loan_list
loan_list = []
# print(loan_dict) #每个特征的情况
loan_pd = pd.DataFrame(loan_dict) #生成pandas.DataFrame
# print(loan_pd) #打印pandas.DataFrame
le = LabelEncoder() #创建LabelEncoder()对象，用于序列化
for col in loan_pd.columns: #序列化
loan_pd[col] = le.fit_transform(loan_pd[col])
# print(loan_pd) #打印编码信息
clf = tree.DecisionTreeClassifier(max_depth = 4) #创建DecisionTreeClassifier()类
clf = clf.fit(loan_pd.values.tolist(), loan_target) #使用数据，构建决策树
dot_data = StringIO()
tree.export_graphviz(clf, out_file = dot_data, #绘制决策树
feature_names = loan_pd.keys(),
class_names = clf.classes_,
filled=True, rounded=True,
special_characters=True)
graph = pydotplus.graph_from_dot_data(dot_data.getvalue())
graph.write_pdf("tree.pdf") #保存绘制好的决策树，以PDF的形式存储。
#预测
df2 = pd.read_excel("预测数据.xlsx")
table = np.array(df2).tolist()
print(clf.predict(table))
结果为：['no' 'yes' 'yes' 'yes' 'no' 'no' 'yes' 'yes' 'yes' 'yes' 'yes' 'yes' 'yes' 'yes' 'no']
1.基本流程
性质：决策树是基于树形结构来进行决策的，一颗决策树包含一个根结点、若干个内部结点和若干个叶节点。叶结点对应决策结果、其他结点对应属性测试
目的：产生一棵泛化能力强，即处理未见示例能力强的决策树
基本流程：遵循简单且直观的“分而治之”策略
2.划分选择
结点的纯度：决策树的分支结点所包含的样本尽可能属于同一类别，即结点的纯度越来越高,划分指标：信息增益、增益率、基尼指数.
（1）信息增益
信息熵：度量样本集合纯度最常用的一种指标。Ent(D)的值越小，则D的纯度越高
熵代表一个系统中蕴含多少信息量，信息量越大表明一个系统不确定性就越大，就存在越多的可能性。当样本中某类样本均匀分布时，这时信息熵最大，纯度最小；假设样本中只有一类样本，此时信息熵最小，纯度最大。
信息增益：即样本数越多的分支结点的影响越大。信息增益越大，则意味着使用属性a来进行划分所获得的“纯度提升”越大。我们可用信息增益来进行决策树的划分属性选择
偏好：对可取值数目较多的属性有所偏好
算法例子：ID3决策树
eg：利用信息增益画出决策树
该数据集包含17个训练样例，其中正例占8份，反例占9份，可计算出根结点的信息熵：
再按属性色泽来进行划分，求出三个根结点不同颜色的信息熵：
然后根据公式计算色泽的信息增益：
按以上步骤计算出其他属性的信息增益，选择数值最大的作为划分属性，生成的决策树如下：
（2）增益率
基于信息增益的缺点，C4.5 算法不直接使用信息增益，而是使用一种叫增益率的方法来选择最优特征进行划分。从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的
IV(a)称为属性a的固有值，是特征 a 的熵，属性a的可能取值数目越多（即V越大），则IV(a)的值通常会越大
偏好：对可取值数目较少的属性有所偏好
算法例子：C4.5决策树
（3）基尼系数
假定当前样本集合 D 中第 k 类样本所占的比例为 pk，数据集D的纯度可用基尼值来度量。Gini(D)越小，则数据集D的纯度越高
属性a的基尼指数定义为：
偏好：在候选属性集合A中，选择那个使得划分后基尼指数最小的属性作为最优划分属性
算法例子：CART决策树
3.剪枝处理
目的：剪枝是决策树学习算法对付“过拟合”的主要手段，通过主动去掉一些分支来降低过拟合的风险
基本策略：
(1).预剪枝--对每个结点在划分前先进行估计，若当前结点不能提升泛化性能，则停止划分
优点：a.降低过拟合风险；b.显著减少决策树的训练时间开销和测试时间开销
决策树桩：一棵仅有一层划分的决策树
(2).后剪枝--在训练集生成的决策树中自底向上对非叶结点进行考察，若该结点对应的子树替换叶结点能提升泛化性能，则用该子树代替叶结点。
优点：a.欠拟合风险小；b.泛化性能往往优于预剪枝决策树
缺点：训练时间开销比未剪枝决策树和预剪枝决策树都要多
4.连续值与缺失值
(1)连续值处理：
采用二分法对连续属性进行处理，二分法是C4.5决策树算法中采用的机制，其中Gain(D,a,t)是样本D基于划分点t二分后的信息增益。我们可选择使Gain(D,a,t)最大化的划分点
注意：与离散属性不同，若当前结点划分属性为连续属性，该属性还可作为其后代结点的划分属性
(2)缺失值处理
问题：
1.如何在属性值缺失的情况下进行划分属性选择？
2.给定划分属性，若样本在该属性上的值缺失，如何对样本进行划分
对于问题1的解决方案：我们可根据样本在属性a上没有缺失值的样本子集来判断属性a的优劣
对于问题2的解决方案：若样本x在划分属性a上的取值已知，则将x划入与其取值对应的子结点，且样本权值在于结点中保持为wx。否则，让同一个样本以不同的概率划入到不同的结点中去
5.多变量决策树
特点：轴平行，即它的分类边界由若干个与坐标轴平行的分段组成。使得学习结果有较好的可解释性
缺点：要进行大量的属性测试，预测时间开销会很大
决策树对复杂分类边界的分段近似，使用斜的划分边界则决策树模型将大大简化
多变量决策树--斜决策树：把轴平行的划分边界改为斜划分
