【机器学习】决策树——连续值处理

本文为自我总结。

本文的内容有两个部分，第一部分是阐述ID3算法在选择特征分裂时对数值型特征的处理，第二部分是CART回归树在选择特征分裂时对数值型特征的处理。

总的来说，两者均是通过设定候选划分点集进行二分（离散化），然后按照信息增益最大准则或平方误差最小准则选择最优划分点。

一、ID3连续值处理

直接用例子计算说明。

例：(牛客题库)根据信息增益，选择最优特征进行划分

这里a3是连续特征。

step1：升序排列不同取值的a3特征的值。

step2：得到划分点候选集。

step3：分别计算所有划分点的信息增益。
数据集D的信息熵为：

划分点为2.0的条件熵为：

划分点为2.0的信息增益为：

划分点为3.5的条件熵为：

划分点为3.5的信息增益为：

划分点为4.5的条件熵为：

划分点为4.5的信息增益为：

划分点为5.5的条件熵为：

划分点为5.5的信息增益为：

划分点为6.5的条件熵为：

划分点为6.5的信息增益为：

划分点为7.5的条件熵为：

划分点为7.5的信息增益为：

step4：找出使得信息增益最大的划分点作为该连续特征的信息增益。

至此，我们求得了连续特征a3的信息增益。
接下来我们只要求得a1，a2的信息增益，并且根据信息增益最大准则，就可以选出最优分裂特征。
类别特征a1的条件熵为：

类别特征a1的信息增益为：

类别特征a2的条件熵为：

类别特征a2的信息增益为：

因此，选择最优的特征a1进行划分。

• 注1：ID3算法并没有限制树为二叉树，但是从这里看，只要连续特征选择二分法进行划分，得出的就是二叉分枝。
• 注2：而类别特征的取值个数将决定分枝数，即K种取值的类别特征则分为K叉。这里的a1和a2取值为T和F，因此恰巧是二叉分枝。
• 注3：特别注意，ID3的注1，是与CART回归树的区别所在；ID3的注2，是与CART分类树的区别所在。
• 注4：C4.5的处理方式和ID3一致，仅仅是采用了信息增益比最大化准则不同。

二、CART连续值处理

1.CART回归树连续值处理
回归树是根据平方误差和最小准则，选择最优的 进行二叉划分。
一般来说，回归问题的特征都是数值特征，此时就是将样本集划分为两部分，分别是：

所以，本质上也是二分法。

• 注1：对于取值种数为2的类别特征，正好可以划分为两个不同的集合；
• 注2：对于取值种数大于2的类别特征，由于CART是二叉树，因此按以下进行划分：
  

2.CART分类树连续值处理
一般地，处理方法和回归树一致。