4.1算法逻辑
从逻辑角度，一堆if else语句的组合
从几何角度，根据某种准则划分特征空间
最终目的：将样本越分越纯
树形结构中每个内部节点表示一个属性上的判断，每个分支代表一个判断结果的输出，最后每个叶节点代表一种分类结果。
4.2划分选择
（1）熵
信息论中，熵(entropy）是随机变量不确定性的度量，也就是熵越大，则随机变量的不确定性越大。设X是一个取有限个值得离散随机变量，其概率分布为：
则随机变量X的熵定义为：
（2）条件熵
设有随机变量（X, Y），其联合概率分布为：
条件熵H(Y|X)表示在已知随机变量X的条件下，随机变量Y的不确定性。随机变量X给定的条件下随机变量Y的条件熵H(Y|X)，定义为X给定条件下Y的条件概率分布的熵对X的数学期望：
(3)ID3
ID3：以信息增益为准则来选择最优划分属性
信息增益的计算要基于信息熵（度量样本集合纯度的指标）
因此，假设于数据集D上建立决策树，数据有K个类别
缺陷：假设每个记录有一个属性“ID”，若按照ID来进行分割的话，由于ID是唯一的，因此在这一个属性上，能够取得的特征值等于样本的数目，也就是说ID的特征值很多。那么无论以哪个ID为划分，叶子结点的值只会有一个，纯度很大，得到的信息增益会很大，但这样划分出来的决策树是没意义的。由此可见，ID3决策树偏向于取值较多的属性进行分割，存在一定的偏好。为减小这一影响，有学者提出C4.5的分类算法
(4)C4.5
基于信息增益率准则选择最优分割属性的算法
信息增益比率通过引入一个被称作分裂信息(Split information)的项来惩罚取值较多的属性
C4.5决策树先从候选划分属性中找出信息增益高于平均水平的属性，在从中选择增益率最高的。
(5)CART
以基尼系数为准则选择最优划分属性，可以应用于分类和回归
基尼值：从样本集合D中随机抽取两个样本，其标记类别不一致的概率。因此，基尼值越小，碰到异类的概率就越小，纯度自然就越高。
属性a的基尼指数定义为：
