@haoqiang 2018-01-22T04:53:40.000000Z 字数 1117 阅读 70

决策树

机器学习

算法	支持模型	树结构	特征选择	连续值处理	缺失值处理	剪枝
ID3	分类	多叉树	信息增益	不支持	不支持	不支持
C4.5	分类	多叉树	信息增益比	支持	支持	支持
CART	分类，回归	二叉树	基尼系数，均方差	支持	支持	支持

ID3

思想
计算出每个特征的信息的信息增益，选择信息增益最大的特征来建立决策树的当前节点。

信息增益
特征 $A$ 对训练数据集 $D$ 的信息增益(互信息) $g(D,A)$ ，定义为集合 $D$ 的经验熵 $H(D)$ 与特征 $A$ 给定条件下 $D$ 的经验条件熵 $H(D|A)$ 之差，即

g (D, A) = H (D) - H (D | A)

$g(D,A)=H(D)-H(D|A)$

ID3算法的不足
1. 没有考虑连续特征，如长度，密度。
2. 取值比较多的特征比取值少的特征信息增益大。

思想
计算出每个特征的信息的信息增益比，选择信息增益比最大的特征来建立决策树的当前节点。

信息增益比
信息增益比是信息增益和特征熵的比值：

g R (D, A) = g ( D , A ) H A ( D )

$g_R(D,A)=\frac{g(D,A)}{H_A(D)}$

算法
计算所有特征的信息增益比，选择最大的作为最佳特征；若某一特征是连续的，计算每个切分点的二分类信息增益比，选择最大的作为该特征的最佳切分点。

使用基尼系数来代替信息增益比，每次仅仅对某个特征的值进行二分。

基尼系数代表了模型的不纯度，基尼系数越小，则不纯度越低，特征越好。在分类问题中，假设有 $K$ 个类别，第 $k$ 个类别的概率为 $p_k$ ，则基尼系数的表达式为：

G i n i (p) = \sum k = 1 K p k (1 - p k) = 1 - \sum k = 1 K p 2 k

$Gini(p) = \sum\limits_{k=1}^{K}p_k(1-p_k) = 1- \sum\limits_{k=1}^{K}p_k^2$

二分类问题，基尼系数的表达式为：

G i n i (p) = 2 p (1 - p)

$Gini(p) = 2p(1-p)$

特别的，对于样本 $D$ ，如果根据特征 $A$ 的某个值 $a$ ，把 $D$ 分成 $D_1$ 和 $D_2$ 两部分，则在特征 $A$ 的条件下， $D$ 的基尼系数表达式为：

G i n i (D, A) = | D 1 | | D | G i n i (D 1) + | D 2 | | D | G i n i (D 2)

$Gini(D,A) = \frac{|D_1|}{|D|}Gini(D_1) + \frac{|D_2|}{|D|}Gini(D_2)$

计算所有特征的基尼系数，选择最小的作为最佳特征；若某一特征有多个切分点，计算每个切分点的二分类基尼系数，选择最小的作为该特征的最佳切分点。