一、算法简介
先抛出问题：针对如下一个简单样本数据，即根据贷款者的年龄、是否有工作、是否有房、信贷情况，及贷款申请是否通过，如何建立分类决策树？
决策树构建通常包含三个流程：特征选择、树的生成、树的剪枝。
1 特征选择
通俗地说，一个申请者贷款通过与否先看哪个因素，再看哪个因素，本例中是先看贷款情况还是工作情况？也就是选择哪个特征作为根节点，然后在剩余的特征中选择第二层节点，以此类推，直到所有特征都被选择完毕。
决策树学习中特征选择的算法有ID3/C4.5、CART。ID3/C4.5其实原理是一致的，ID3是基于信息增益，C4.5基于信息增益比，C4.5是在ID3的基础上产生的，二者都是由熵计算而来；CART则是基于基尼系数。
计算特征的信息增益(信息增益=经验熵-经验条件熵）：
之所以称为经验熵和经验条件熵，是因为熵和条件熵的概率由极大似然估计而得。样本中的熵为：
特征A1对样本D的经验熵：
所以A1的信息增益为0.971-0.888=0.083，以此计算其他几个特征的信息增益分别为0.324、0.420、0.363，0.420对应的特征为是否有房，以ID3算法得到树的根节点为“是否有房”。
假如采用C4.5算法，则多一步骤，计算信息增益比。假如采用CART算法，还会是“是否有房”作为根节点吗？
ID3算法选择特征要求信息增益越大越好，而CART算法要求基尼系数越小越好。其次还有一点不同之处：CART算法假设决策树是二叉树，即每个节点只有两个分支，所以对于年龄和信贷情况有三个分支的需要选择基尼系数最小的分支为最优切分点。
Ck是D中第k类的样本子集。
特征A1对样本D的基尼系数：
A1=1，2，3分别对应青年，中年，老年。根据基尼系数最小原则，以青年或老年作为最佳分割点均可，且A1的基尼指数为0.44，以此方法分别计算其他特征的基尼系数分别为：
由此看出，A3(是否有房)的系数最小，则CART算法选择的根节点也是“是否有房”，与ID3算法的结果一致。
2 树的生成
那么如果有房，下一个节点是什么，没房下一个节点是什么？首先将是否有房划分两个子样本分别为D1(有房）和D2(无房），D1中所有的类别为是，即有房贷款申请则通过，所以直接到叶节点“是”；D2则需要从剩余的特征中选择一个节点作为下一个节点，D2中有3个是6个否，所以D2的熵为：
特征A1对样本D2的经验熵:
所以A1在D2样本集的信息增益为0.918-0.667=0.251，以此计算其他几个特征的信息增益分别为0.918、0.474，0.918对应的特征为是否有工作。以ID3算法得到树的第二层节点为叶节点“是”和“是否有工作”。在有工作中的样本中贷款都通过，在无工作的样本中贷款都没通过，树生成结束。假如没有到达叶节点，再对剩余两个特征计算经验熵，直到树生成完毕。
3 数的剪枝
剪枝的目的是防止过度拟合，也就是在训练样本中能够准确无误，但是对于测试数据表现能力很差。一般分为先剪枝和后剪枝，先剪枝是在树还没生成之前，限定节点个数、树的高度、给定增益的阀值等；后剪枝是树生成之后，根据测试数据的错误率等方法减掉节点。
二、Python实践
假如有以下简单样本，根据天气、是否周末、是否促销三个因素，用决策树预测销量高低。
假如样本比较理想，没有脏数据及缺失值等，省去数据清洗的步骤。
以上代码模型已建立好，并用测试集检测模型预测能力，结果如下（模型计算有小数四舍五入）：
对结果进行解读：
TP-将正预测为真，FN-将正预测为假，FP-将反预测为真，TN-将反预测为假。
accuracy(精确度)=TP/(TP+FP)=5/(5+3)=0.625
precision(准确率)=TP+TN/(TP+FP+FN+TN)=(5+1)/9=0.667
recall(召回率)=TP/(TP+FN)=5/(5+0)=1
f1_score(精确率和召回率的调和均值)=2*TP/(2TP+FP+FN)=2*5/(2*5+3+0)=0.769
#召回率：分类器中判定为真的正例占总正例的比率。f1_score：准确率和召回率呈负相关，一个高，一个就低，用调和均值作为综合指标评估模型。
从计算结果来看，模型对实际销售量高的样本预测很准确，但总是高估实际销售量低的样本。
漏洞之处望指正！
