CART决策树使用“基尼指数”(Gini index)来选择划分属性。
我们希望决策树的分支结点所包含的样本尽可能属于同一类别,即节点的纯度越来越高。
数据集D的纯度可用基尼值来度量:
![\color{red}{Gini(D)=\sum_{k=1}^{|y|}\sum_{k'\neq k}p_{k}p_{k'}=1-\sum_{k=1}^{|y|}p_{k}^2}](https://latex.csdn.net/eq?%5Ccolor%7Bred%7D%7BGini%28D%29%3D%5Csum_%7Bk%3D1%7D%5E%7B%7Cy%7C%7D%5Csum_%7Bk%27%5Cneq%20k%7Dp_%7Bk%7Dp_%7Bk%27%7D%3D1-%5Csum_%7Bk%3D1%7D%5E%7B%7Cy%7C%7Dp_%7Bk%7D%5E2%7D)
Gini(D)越小,则数据集D的纯度越高。
属性a的基尼指数定义为:
![{\color{Red} Gini\_index(D,a)=\sum_{v=1}^{V}\frac{|D^v|}{|D|}Gini(D^v)}](https://latex.csdn.net/eq?%7B%5Ccolor%7BRed%7D%20Gini%5C_index%28D%2Ca%29%3D%5Csum_%7Bv%3D1%7D%5E%7BV%7D%5Cfrac%7B%7CD%5Ev%7C%7D%7B%7CD%7C%7DGini%28D%5Ev%29%7D)
在候选属性集合A中,选择那个使得划分后基尼指数最小的属性作为最优划分属性,即
![{\color{Red} a_*=arg\ min\ Gini\_index(D,a)}](https://latex.csdn.net/eq?%7B%5Ccolor%7BRed%7D%20a_*%3Darg%5C%20min%5C%20Gini%5C_index%28D%2Ca%29%7D)
前面讲完了ID3、C4.5算法和CART决策树算法怎么选择最优划分属性,下面讲解决策树通用算法流程:
输入:训练集D={{x1,y1},{x2,y2},...,{xm,ym}}
属性集A={a1,a2,...,ad}
过程:函数TreeGenerate(D,A)
生成节点node;
if D中样本全属于同一类别C then
将node标记为C的叶节点;return
end if
if A≠
OR D中样本在A上取值相同 then
将node标记为叶节点,其类别标记为D中样本数最多的类;return
end if
从A中选择最优划分属性![a_*](https://latex.csdn.net/eq?a_*)
for
的每一个值
do
为node生成一个分支;令
表示D中在
上取值为
的样本子集;
if
为空 then
将分支节点标记为叶节点,其类别标记为D中样本最多的类;return
else
以TreeGenerate(
,A\{
}) 为分支节点
end if
end for
输出:以node为根节点的一颗决策树。
下一章讲解决策树的剪枝处理。