决策树算法既可以用于分类问题,又可以用于回归问题。针对分类问题,其目标在于根据属性对样本集合加以分支,使得各个分支所包含的样本集尽量只属于或者只包含一类。针对回归问题,其目标一般是使得各分支中所包含的样本目标函数(预测值跟真实值之间的偏差之和)最小化。
本文主要讨论决策树用于分类问题。二分类决策树算法是比较简单的一种决策树分类算法。决策树中比较关键的点就在于其中每个节点的分支策略,在某个节点进行分支时,如何分支,应该选择哪个特征执行分支时非常关键的。执行分支时,可以基于Gini系数或熵将某个节点分成两个子节点,分支目标是尽可能使得两个子节点中只包含两类中的其中一类,意即使得两个子节点都比较纯净。
子节点的基尼系数(也可以称作不纯度指标)计算公式如下:
由此可以得到父节点的基尼系数:
基于基尼系数分割决策树节点时,决策树的目标是使得基尼系数变小,即使得基尼增益越大越好。
对于二分类问题,熵的计算公式如下:
这里的p表示两个类别分别对应的概率。容易看出,如果某个节点中只有一个类,那么此时对应的熵为0。如果两个类别的样本各占一半,对应的熵会达到最大值。这是因为只有两个类别时,针对上面的函数,比较容易计算出使得熵达到最大的自变量的位置。
对于决策树中的节点来讲,熵越小越好,熵越小说明该节点所包含的样本比较纯,基本只包含一个类别的样本。熵越小,信息增益越大,决策树分类的目标就是使得信息增益最大。
对于多类问题,熵的计算公式可以由二类问题推广得到: