走进决策树
决策树是广泛用于分类和回归任务的模型。本质上，它从一层层的 if/else 问题中进行学习，并得出结论。
说到决策树，那么最容易想到的就是在程序语言中的条件判断语句，if and else 可谓是是决策树的本质。
下面通过两个案例对其进行本质的剖析：
案例一
想象一下，你想要区分下面这四种动物：熊、鹰、企鹅和海豚。你的目标是通过提出尽可能少的 if/else 问题来得到正确答案。你可能首先会问：这种动物有没有羽毛，这个问题会将可能的动物减少到只有两种。如果答案是“有”，你可以问下一个问题，帮你区分鹰和企鹅。例如，你可以问这种动物会不会飞。如果这种动物没有羽毛，那么可能是海豚或熊，所以你需要问一个问题来区分这两种动物——比如问这种动物有没有鳍。
在这张图中，树的每个结点代表一个问题或一个包含答案的终结点（也叫叶结点）。树的边将问题的答案与将问的下一个问题连接起来。用机器学习的语言来说就是，为了区分四类动物（鹰、企鹅、海豚和熊），我们利用三个特征（“有没有羽毛”“会不会飞”和“有没有鳍”）来构建一个模型。我们可以利用监督学习从数据中学习模型，而无需人为构建模型。
案例二
理想总是很美好，但是现实确实很骨感。随着中国人口比例失衡，很多适龄青年都会面对一个严峻的考验，那就是“择偶”，正所谓“你在桥上看风景，看风景的人在看你”，那么多少人在进行另一半的寻找的时候，会考虑什么因素呢？下面看一张决策树的现象图：
你是否也是上述的标准呢？
灵魂的树
在编程中， if-else所依赖的判断条件是由程序员来填写，但在机器学习里，我们能做的只有两件事，第一件事是选择模型，第二件事是往模型“嘴”里塞数据，剩下的就只能坐在一旁干着急。上面这棵可以决策的树得依靠我们把判别条件填进去，它要想成为真正的决策树，就得学会怎样挑选判别条件。这是决策树算法的灵魂，也是接下来需要重点探讨的问题。
第一个要紧问题就是：判别条件从何而来呢？分类问题的数据集由许多样本构成，而每个样本数据又会有多个特征维度，譬如学生资料数据集的样本就可能包含姓名、年龄、班级、学号等特征维度，它们本身也是一个集合，我们称为特征维度集。数据样本的特征维度都可能与最终的类别存在某种关联关系，决策树的判别条件正是从这个特征维度集里产生的。
部分教材认为只有真正有助于分类的才能叫特征，原始数据里面的这些记录项目只能称为属性（Attribute），而把特征维度集称为属性集，所以在这些教材中，决策树是从称为树形集的集合中选择判别条件。这里为了保持本书用语的连贯性，我们仍然称之为“特征维度”。当然，这只是用语习惯上的不同，在算法原理上是没有任何区别的。
决策树的选择机制
活经验告诉我们：挑重要的问题先问。决策树也确实是按这个思路来选择决策条件的。思考这个问题，可以从“怎样才算是好的决策条件”开始。决策树最终是要解决分类问题，那么最理想的情况当然是选好决策条件后，一个if-else就正好把数据集按正类和负类分成两个部分。
不过，现实通常没有“一刀切”这么理想，总会有一些不识时务的样本“跑”到不属于自己的类别里，我们退而求其次，希望分类结果中这些不识时务的杂质越少越好，也就是分类结果越纯越好。
依照这个目标，决策树引入了“纯度”的概念，集合中归属同一类别的样本越多，我们就说这个集合的纯度越高。每一次使用if-else进行判别，二元分类问题的数据集都会被分成两个子集，那么怎么评价分类的效果呢？可以通过子集的纯度。子集纯度越高，说明杂质越少，分类效果就越好。
节点纯度的度量规则
使用决策树这套框架的分类算法有很多，其中最著名的决策树算法一共有三种，分别是ID3、C4.5和CART，这三种决策树算法分别采用了信息增益、增益率和基尼指数这三种不同的指标作为决策条件的选择依据。
虽然三种决策树算法分别选择了三种不同的数学指标，但这些指标都有一个共同的目的：提高分支下的节点纯度（Purity）。
决策树算法中使用了大量二叉树进行判别，在一次判别后，最理想的情况就是二叉树的一个分支纯粹是正类，另一个分支纯粹是负类，这样就意味着完整和准确地完成了一次分类。但大多数的判别结果都没有这么理性，所以一个分支下会既包含正类又包含负类，不过我们希望看到的是一个分支包含的样本尽可能地都属于同一个类，也就是希望这个分支下面的样本类别越纯越好，所以用了“纯度”来进行描述。纯度有三点需要记住：
当一个分支下的所有样本都属于同一个类时，纯度达到最高值。
当一个分支下样本所属的类别一半是正类一半是负类时，纯度取得最低值。
纯度考察的是同一个类的占比，并不在乎该类究竟是正类还是负类，譬如某个分支下无论是正类占70%，还是负类占70%，纯度的度量值都是一样的。
纯度的度量方法
我们的任务就是要找到一种满足纯度达到最大值和最小值条件的纯度度量函数，它既要满足这三点需求，又要能作为量化方法。
现在让我们把这三点要求作成图像（可视化的图像有助于更直观地理解），同时，如果我们能够找到一款函数符合这个图像，就等于找到了符合条件的函数。我们约定所作图像的横轴表示某个类的占比，纵轴表示纯度值，首先来分析极值点的位置。
根据第一点要求，某个类占比分别达到最大值和最小值时，纯度达到最高值。最大值好理解，为什么最小值也能令纯度达到最高？可以反过来想，这个类取得最小值时，另一个类就取得了最大值，所以纯度也就最高。根据分析，我们知道了纯度将在横坐标的头尾两个位置达到最大值。
根据第二点要求，纯度的最小值出现在某个类占比为50%的时候。换句话说，当横坐标为0.5时，纯度取得最低值。
现在可以作出图像了。根据上述分析的纯度最高值和最低值随类占比的变化情况，我们用一条平滑的曲线连接起这三个点，则所作出来的图像应该类似一条微笑曲线
不过我们在机器学习中更喜欢计算的是“损失值”，那么对纯度度量函数的要求正好与纯度函数的要求相反，因为纯度值越低意味着损失值越高，反之则越低。所以纯度度量函数所作出来的图像正好相反
决策树算法背景介绍
最早的决策树算法是由Hunt等人于1966年提出的CLS。后来的决策树算法基本都是基于Hunt算法框架的改进。
当前最有影响力的决策树算法是Quinlan于1986年提出的ID3和1993年提出的C4.5（现在已经进化到C5.0），以及BFOS（Breiman、Friedman、Olshen、Stone）四位学者于1984年提出的CART算法。
追溯其原理，决策树的算法原理就是如此的清晰 ，建立决策树的关键，即在当前状态下选择哪个属性作为分类依据
信息(Information)和信息的量化
假设：X为某随机变量，xi表示X的某个取值，p(xi) 指当X=xi的概率，I(X=xi)表示X=xi的信息量
该函数满足: 当一个事件发生的概率越大(确定性越大), 它所携带的信息量就越小, 反之, 当一个事件发生的概率越小(确定性越小), 它所携带的信息量就越大。
1. 当小概率事件发生时, 我们才会感觉’信息量大’
2. 当大概率事件发生时, 我们会感觉’理所应当’, ‘信息量小-正常操作’
也就是越容易发生的事件，那么它所携带的信息量就越小，因为不需要去寻找这些多因素
信息熵(Information Entropy)
熵(Entropy): 事件不确定性的度量
信息熵: 实质上就是对事件的不确定性程度的度量，也可以理解为一个事件集的平均信息量
例如：已知小明及格的概率为0.2, 不及格的概率为0.8, 那么小明成绩的不确定性如何度量呢?
H(小明成绩)=−0.2∗(log20.2)+(−0.8∗(log20.8))=0.7219
这就是信息熵的公式，那么假如小明的及格的概率是：0.5，不及格的概率也是：0.5，那么它的信息熵就是：1
条件熵(Conditional Entropy)
条件熵：是为解释信息增益而引入的概念，即在给定条件X的情况下Y的信息熵。以下是公式定义：
这是一个典型的二分类问题：是否为鱼
信息熵：H(是否为鱼)=-P(是鱼)*log2P(是鱼)-P(不是鱼)*log2P(不是鱼)=-2/5*log22/5-3/5*log23/5=0.971
条件熵：H(是否为鱼|是否用鳃呼吸)=P(用鳃呼吸)*H(是否为鱼|用鳃呼吸)+P(不用鳃呼吸)*H(是否为鱼|不用鳃呼吸)=3/5*(-2/3*log22/3-1/3*log21/3)+2/5(0-1log21)=0.551
H(是否为鱼|是否有鳍)=P(有鳍)*H(是否为鱼|有鳍)+P(没有鳍)*H(是否为鱼|没有鳍)=4/5*(-1/2*log21/2-1/2*log21/2)+1/5(0-1log21)=0.8
信息增益(Information Gain，ID3算法使用)
信息增益: 事件中某一影响因素的不确定性度量对事件信息不确定性减少的程度，即得知特征X的信息而使得类Y的信息不确定性减少的程度。
如果H(D)为集合D的信息熵，H(D|A)为集合D在特征A下的条件熵，则信息增益可表述为如下数学公式:
即集合D的信息熵H(D)与D在特征A下的条件熵H(D|A)之差
ID3算法中选取最优分裂属性的策略
首先计算未分裂前当前集合D的信息熵H(D)
然后计算当前集合D对所包含的所有属性A的条件熵H(D|A)
然后计算每个属性的信息增益IG(D|A):
IG (D|A)=H(D)−H(D|A)
选取信息增益最大的属性AIG=max作为决策树进行分裂的属性
信息增益总结
优点：
1）考虑了特征出现与不出现的两种情况，比较全面。
2）使用了所有样例的统计属性，减小了对噪声的敏感度。
3）容易理解，计算简单。
缺点：
1）信息增益考察的是特征对整个系统的贡献，没有到具体的类别上，所以一般只能用来做全局的特征选择，而没法针对单个类别做特征选择
2）算法天生偏向选择分支多的属性，容易导致过拟合(overfitting)
极端的例子：如果ID被当成一个属性，那么ID属性的信息增益会最大。因为按照ID划分数据集合可以得到最纯的子集，即每一个ID所在样例都会归属于单一类别，故其条件熵为0。
信息增益率: 因为信息增益会倾向于取值最多的属性，会导致过拟合问题，所以需要引入一个惩罚参数，即数据集D以特征A作为随机变量的信息熵的倒数：
存在与信息增益相反的缺点，即偏向于取值最少的属性，因为属性A取值越少，H(A)也越小，导致IGA(D|A)越大。
基尼指数(Gini Index,CART算法使用)
基尼指数: 是一种与信息熵类似的做特征选择的指标，可以用来表征数据的不纯度。其计算公式为：
1、Pk表示选中的样本属于k类别的概率，不属于K类别的概率则为(1− Pk)
2、样本集合中有K个类别，一个随机选中的样本可以属于这k个类别中的任意一个，因而对类别就加和
3、当为二分类时，Gini(p)=2p(1−p)
基尼指数解读
基尼指数越小表示集合中被选中的样本被分错的概率越小，也就是说集合的纯度越高，反之集合越不纯。即:基尼指数（基尼不纯度）= 样本被选中的概率 * 样本被分错的概率
样本集合D的Gini指数：假设集合中有K个类别，则：
基于特征A划分样本集合D之后的基尼指数：
