机器学习day9-决策树

决策树

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

决策树常用的启发函数

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

ID3-最大信息增益

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

C4.5-最大信息增益比

特征A对于数据集D的信息增益比定义：
$g_{R}(D,A)=\frac{g(D,A)}{H_A(D)}$
其中
$H_A(D)=-\sum_{i=1}^n\frac{|D_i|}{|D|}log_2\frac{|D_i|}{|D|}$
$H_A(D)$ 称为数据集D关于A的取值熵。

CART-最大基尼指数(Gini)

Gini描述的是数据的纯度，与信息熵含义类似
$Gini(D)=1-\sum_{k=1}^{n}(\frac{|C_k|}{|D|})^2$
CART每次迭代时选择基尼指数最小的特征及其对应的切分点进行分类。CART是二叉树，每一步数据按照特征A的取值切成两份，分别进入左右子树。特征A的Gini指数定义：
$Gini(D|A)=\sum_{i=1}^n\frac{|D_i|}{|D|}Gini(D_i)$

三种启发函数

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