决策树的一些基础概念（根节点，内部结点，叶子结点等），结合数据结构的二叉树/非二叉树其实很好理解。
纯度
这个好像还是第一次看到。决策树在选择最优的划分属性时，希望分支节点包含尽可能多的同一类别的样本，这个就是指结点的“纯度”尽可能高。
划分方法对比
ID3（信息增益）
使用信息熵来度量样本集合的纯度；
-
信息熵定义：
image1.png
-
信息增益：
image2.png
信息增益越大，代表着使用此属性a划分的子集不确定性越小，而“纯度”越大。
- 缺点：对可取值较多的属性有偏好。
C4.5（增益率）
为了减少ID3（信息增益）算法的偏好问题，C4.5算法提出了用增益率来选择最优划分属性。
-
增益率定义：
2018-07-30 决策树学习记录
- 缺点：对可取值较少的属性有偏好。
注意：C4.5使用时，先从候选的划分属性中选出信息增益高与平均水平的属性，再从中选择增益率最高的。
CART（基尼指数）
数据集D的纯度可用基尼值度量：
2018-07-30 决策树学习记录
Gini(D)反映了从D中随机抽取两个样本，类别标记不一致的概率。因此，Gini(D)越小，代表着D的纯度越高。
属性a的基尼指数定义：
2018-07-30 决策树学习记录
因此，在候选属性中选择哪个使得划分后，基尼指数最小的属性作为划分属性。
网友评论