决策树中的信息商与信息增益

熵（entropy）

熵是数据集合不确定性（amount of uncertainty）的度量方法。

• S，数据集。
  • 在分离数据集的迭代过程中，数据集会逐渐变小，分离出来的数据集都是原数据集的子集。
• X，数据集中的类别集合。
• p(x)，数据集S中类别为x的元素所占的百分比。

熵是度量信息分布的未知性数量的方法。熵值越小，表示信息的分布越趋于可知。 应用到数据集中，当熵 H(S) = 0 时，数据集被认为是完全分类了。

信息增益（information gain）

信息增益是度量数据集根据属性A分离前后的熵差，也即是表示数据集分离后的信息不确定性的减少量。

• H(S)，数据集S的熵。
• T，数据集S根据属性A分离后的子集的集合。
• p(t)，在子集 t 中的元素在数据集S中所有元素所占的比例。
• H(t)，子集 t 的熵