决策树
决策树是一种自上而下，对样本数据进行分类的过程，由结点和有向边组成。结点分为内部结点和叶结点，其中每个内部结点表示一个特征或属性，叶结点表示类别。从顶部根结点开始，所有样本聚在一起。经过根结点的划分，样本被分到不同的子结点中。再根据子结点的特征进一步划分，直到所有样本都被归到某一个类别中。
从若干不同的决策树中选取最优的决策树是一个NP完全问题，在实际工作中，我们通常会采用启发式学习的方法去构建一颗满足启发式条件的决策树。常用的决策树算法有ID3,C4.5和CART，它们构建树所使用的启发式函数各是什么？
ID3——最大信息增益
对于样本集合D，类别数为K，数据集D的经验熵表示为H(D)=-∑(|Ck|/|D|)log2(|Ck|/|D|),其中Ck是样本集合D中属于D中属于第k类的样本子集，|Ck|表示该子集的元素个数，|D|表示样本集合的元素个数。
然后计算特征A对于数据集D的经验条件熵H(D|A)=∑(|Di|/|D|)H(Di)=∑(|Di|/|D|)(-∑(|Dik|/|Di|)log2(|Dik|/|Di|)),其中，Di表示D中特征A取第i个值的样本子集，Dik表示Di中属于第k类的样本子集。
信息增益就是二者只差，即g(D,A)=H(D)-H(D|A)
C4.5——最大信息增益比
特征A对于数据集D的信息增益比定义为gr(D,A) = g(D,A)/HA(D),其中，HA(D)=-∑(|Di|/|D|)log2(|Di|/|D|)，称为数据集D关于A的取值熵。
CART——最大基尼指数（Gini）
Gini描述的是数据的纯度，与信息熵类似。Gini（D）=1-∑(|Ck|/|D|)^2.
CART在每一次迭代中选择基尼指数最小的特征及其对应的切分点进行分类。它与ID3，C4.5不同的是，CART是一棵二叉数，采用二元切割法，每一步将数据按特征A的取值切成两份，分别进入左右子树。特征A的Gini指数定义为Gini(D|A)=∑(|Di|/|D|)Gini(Di)
通过对比三种决策树的构造准则，我们可以看出三者之间的差异。
首先，ID3是采用信息增益作为评价标准，信息增益反映的是给定条件以后不确定性减少的程度，特征取值越多就意味着确定性越高，也就是条件熵越小，信息增益越大。这在实际应用中存在很大的问题。C4.5实际上是对ID3进行优化，通过引入信息增益比一定程度桑对取值比较多的特征进行惩罚，避免ID3出现过拟合的特征，提升决策树的泛化能力。
其次，从样本类型的角度，ID3只能处理离散型变量，而C4.5和CART都可以处理连续类型的变量。C4.5处理连续型变量时，通过对数据排序之后找到类别不同的分割线作为切分点，根据切分点把连续属性转换为布尔型，从而将连续型变量转换多个取值区间的离散变量。而对于CART，由于其构建时每次都会对特征进行二值划分，因此可以很好地适用于连续变量。
从应用角度，ID3和C4.5只能用户分类任务，而CART既可以用于分类也可以用户回归。
另外，从实现细节、优化过程等角度来看，ID3对样本特征缺失值比较敏感，而C4.5和CART可以对缺失值进行不同方式的处理；ID3和C4.5可以在每个结点上产生出多叉分支，且每个特征在层级之间不会复用，而CART每个结点只会产生两个分支，最后会形成一个二叉树，每个特征可以被重复使用。ID3和C4.5通过剪枝来权衡数的准确性和泛化能力，而CART直接利用全部数据发现所有可能的数结构进行对比选择最优。
