决策树的一些基础概念（根节点，内部结点，叶子结点等），结合数据结构的二叉树/非二叉树其实很好理解。

纯度

这个好像还是第一次看到。决策树在选择最优的划分属性时，希望分支节点包含尽可能多的同一类别的样本，这个就是指结点的“纯度”尽可能高。

划分方法对比

ID3（信息增益）

使用信息熵来度量样本集合的纯度；

• 信息熵定义：

  
  
  image1.png

• 信息增益：

  
  
  image2.png

信息增益越大，代表着使用此属性a划分的子集不确定性越小，而“纯度”越大。

• 缺点：对可取值较多的属性有偏好。

C4.5（增益率）

为了减少ID3（信息增益）算法的偏好问题，C4.5算法提出了用增益率来选择最优划分属性。

• 增益率定义：

  
  
  图片发自简书App

• 缺点：对可取值较少的属性有偏好。

注意：C4.5使用时，先从候选的划分属性中选出信息增益高与平均水平的属性，再从中选择增益率最高的。

CART（基尼指数）

数据集D的纯度可用基尼值度量：

图片发自简书App

Gini(D)反映了从D中随机抽取两个样本，类别标记不一致的概率。因此，Gini(D)越小，代表着D的纯度越高。
属性a的基尼指数定义：

图片发自简书App

因此，在候选属性中选择哪个使得划分后，基尼指数最小的属性作为划分属性。