决策树

决策树自上而下，对样本数据进行树形分类的过程。决策树由结点和有向边组成。结点又分内部结点和叶结点。每个内部结点表示一个特征或属性，叶子结点表示类别。
从顶部开始，所有样本聚在一起，经过根结点的划分，样本分入不同的子结点，再根据子结点的特征进一步划分，直到所有的样本被归入到一个类别。
决策树是最基础且常见的监督学习模型，可以用于处理分类问题和回归问题。
决策树的生成包括：特征选择，树的构造，树的剪枝三个过程。

决策树常用的启发函数

常用的决策树算法有：ID3，C4.5和CART，那么它们的启发式函数是什么？

ID3-最大信息增益

对于样本集合D，类别数为K，数据集D的经验熵表示：

其中，是样本集合D中属于第k类的样本子集，表示该子集的元素个数，|D|表示样本集合的样本个数。
然后计算某特征A对于数据集D的经验条件熵H(D|A)：
其中，表示D中特征A取第i个值得样本子集，表示中属于dik类的样本子集。
因此，信息增益g(D,A)可以表示为二者之差，
信息增益最大，一般是最后具体划分类别的结点。

C4.5-最大信息增益比

特征A对于数据集D的信息增益比定义：

其中
称为数据集D关于A的取值熵。

CART-最大基尼指数(Gini)

Gini描述的是数据的纯度，与信息熵含义类似
CART每次迭代时选择基尼指数最小的特征及其对应的切分点进行分类。CART是二叉树，每一步数据按照特征A的取值切成两份，分别进入左右子树。特征A的Gini指数定义：

三种启发函数

ID3使用信息增益作为评价标准。C4.5基于ID3进行了优化，引入了信息增益比，对取值较多的特征进行惩罚，避免了一定程度的过拟合。提高决策树的泛化能力。
ID3应用于离散变量，C4.5和CART都可以用于连续变量。
ID3和C4.5用于分类任务，CART，Classification and Regression Tree，分类回归树用于回归和分类问题。
最后，ID3对于样本特征缺失值比较敏感，CART和C4.5会自己处理，C4.5通过剪枝，CART则是直接利用全部数据发现所有可能的树结构进行对比。