机器学习:决策树学习之最佳划分的度量问题(一)

从决策树学习基本算法的步骤可以看出，决策树学习的关键是如何选择最佳属性划分。一般而言，随着长树过程的不断进行，通常希望决策树的分支结点所包含的样本越来越归属于同一类别，即结点的“不纯度”越来越低。因此，为了确定按某个属性划分的结果，我们需要比较划分前（父亲结点）和划分后（所有儿子结点）不纯度的降低程度，降低越多，划分的效果就越好。

若记不纯度的降低程度为△，则用来确定划分效果的度量标准可以用下面的公式来定义：

其中，I（parent）是父亲结点的不纯度度量，k是划分属性取值的个数。N是父亲结点上样本的总数，N（j）是第j个儿子结点上样本的数目，I（j）是第j个儿子结点的不纯度度量。

接下来的问题是，给定任意结点t，如何来定义它的不纯度度量，令p（i）为结点t中第i类样本所占有的比例，则结点t的不纯度度量主要包括：

由此，就可以得到以下3种选择最佳划分的度量标准：

需要注意的是，这里的熵减最大度量标准就是信息增益最大度量标准，记为：△info

信息增益标准存在一个内在的偏置，它偏好选择具有较多属性值的属性，为减少这种偏好可能带来的不利影响，著名的C4.5决策树算法不直接使用信息增益，而是使用“增益率”来选择最佳划分属性。

增益率度量就是在信息增益度量中引入一个被称为“分裂信息”的项作分母来惩罚具有较多属性值的属性：

其中，SplitInfo是划分属性的分裂信息。

属性的分裂信息SplitInfo度量了属性划分数据的广度和均匀性：

其中，p（j）是当前结点中划分属性第j个属性值所占有样本的比例。

分裂信息实际上就是当前结点关于划分属性各值的熵，它可以阻碍选择属性值均匀的属性。