《机器学习by周志华》学习笔记-决策树-03

1、连续值处理

到目前为止，我们在决策树01、02中仅讨论了基于离散属性来生成决策树，而现实任务中常会遇到连续属性，所以在本章的学习中，我们将会讨论如何在决策树学习中使用连续属性。

1.1、概念

取值范围是连续的实数值或者整数值的属性就是「连续属性」，与离散属性相对立。

这种属性通常可以用一个区间来描述，比如身高、体重、温度等。连续属性的取值通常是在一个连续的范围内变化的，因此它们的值可以是任何一个范围内的实数值或者整数值，而不是一组离散的取值。

1.2、背景

由于连续属性的可取值数目不再有限，因此不能直接根据「连续属性」的可取值来对节点进行划分，此时，想要生成决策树，就需要使用「连续属性离散化」技术解决。

连续属性离散化技术：

①概念：是「数据变换」的一种方式，用于生成决策树。

②方法：连续属性离散化-CSDN博客

无监督离散化
等宽法
灯频法
K-means聚类分析
...
有监督离散化

本文采用了二分法（bi-partition）对连续属性进行处理，这正是C4.5决策树算法中采用的机制。

1.3、方法

给定样本集D和连续属性a，假设a在D上出现了n个不同的取值，将这些值从小到大进行排序，记为集合Ai，可表示为：

$A_{i}=\left \{ a_{1} ,a_{2} ,...,a_{n} \right \}$

基于划分点t（ $a_{1}\leq t\leq a_{n}$ ），可将D分为子集 $D_{t}^{-}$ 和 $D_{t}^{+}$ ，其中：

$D_{t}^{-}=[a_{1},t]$

$D_{t}^{+}=(t,a_{n}]$

对于连续属性a相邻取值 $a_{i}$ 和 $a_{i+1}$ 来说，t在区间 $[a_{i},a_{i+1})$ 中任意取值所产生的划分结果相同，因此对连续属性a，我们可以考察a1～a(n-1)取值的候选划分点的集合Ta：

$T_{a}=\left \{ t_{1},t_{2},...,t_{n-1} \right \}=\left \{ \frac{a_{i}+a_{i+1}}{2} \right \}(1\leq i\leq n-1)$

然后，我们将按照离散属性一样来考察这n-1个划分点，选择最优的划分点来对样本集合进行划分：

$Gain(D,A_{i})=\underset{t\in T_{a}}{max}Gain(D,A_{i},t)$ $=\underset{t\in T_{a}}{Ent(D)}-\sum_{\lambda \in (-,+)}^{}\frac{|D_{t}^{\lambda }|}{|D|}Ent(D_{t}^{\lambda })$

其中 $Gain(D,A_{i},t)$ 是样本D给予划分点t二分之后的「信息增益」，则需要我们求出「信息增益」最大的划分点 $t_{i}$ 。

1.4、案例

给定西瓜数据集D如下表：

表1：西瓜数据集——离散属性&连续属性

编号色泽(A1) 根蒂(A2) 敲声(A3) 纹理(A4) 脐部(A5) 触感(A6) 密度(A7) 含糖率(A8) 是否好瓜(Y)
x1 青绿 $A_{1}^{1}$ 蜷缩 $A_{2}^{1}$ 浑浊 $A_{3}^{1}$ 清晰 $A_{4}^{1}$ 凹陷 $A_{5}^{1}$ 硬滑 $A_{6}^{1}$ 0.697 0.460 是Y1
x2 乌黑 $A_{1}^{2}$ 蜷缩 $A_{2}^{1}$ 沉闷 $A_{3}^{2}$ 清晰 $A_{4}^{1}$ 凹陷 $A_{5}^{1}$ 硬滑 $A_{6}^{1}$ 0.774 0.376 是Y1
x3 乌黑 $A_{1}^{2}$ 蜷缩 $A_{2}^{1}$ 浑浊 $A_{3}^{1}$ 清晰 $A_{4}^{1}$ 凹陷 $A_{5}^{1}$ 硬滑 $A_{6}^{1}$ 0.634 0.264 是Y1
x4 青绿 $A_{1}^{1}$ 蜷缩 $A_{2}^{1}$ 沉闷 $A_{3}^{2}$ 清晰 $A_{4}^{1}$ 凹陷 $A_{5}^{1}$ 硬滑 $A_{6}^{1}$ 0.608 0.318 是Y1
x5 浅白 $A_{1}^{3}$ 蜷缩 $A_{2}^{1}$ 浑浊 $A_{3}^{1}$ 清晰 $A_{4}^{1}$ 凹陷 $A_{5}^{1}$ 硬滑 $A_{6}^{1}$ 0.556 0.215 是Y1
x6 青绿 $A_{1}^{1}$ 稍蜷 $A_{2}^{2}$ 浑浊 $A_{3}^{1}$ 清晰 $A_{4}^{1}$ 稍凹 $A_{5}^{2}$ 软粘 $A_{6}^{2}$ 0.403 0.237 是Y1
x7 乌黑 $A_{1}^{2}$ 稍蜷 $A_{2}^{2}$ 浑浊 $A_{3}^{1}$ 稍糊 $A_{4}^{2}$ 稍凹 $A_{5}^{2}$ 软粘 $A_{6}^{2}$ 0.481 0.149 是Y1
x8 乌黑 $A_{1}^{2}$ 稍蜷 $A_{2}^{2}$ 浑浊 $A_{3}^{1}$ 清晰 $A_{4}^{1}$ 稍凹 $A_{5}^{2}$ 硬滑 $A_{6}^{1}$ 0.437 0.211 是Y1
x9 乌黑 $A_{1}^{2}$ 稍蜷 $A_{2}^{2}$ 沉闷 $A_{3}^{2}$ 稍糊 $A_{4}^{2}$ 稍凹 $A_{5}^{2}$ 硬滑 $A_{6}^{1}$ 0.666 0.091 否Y2
x10 青绿 $A_{1}^{1}$ 硬挺 $A_{2}^{3}$ 清脆 $A_{3}^{3}$ 清晰 $A_{4}^{1}$ 平坦 $A_{5}^{3}$ 软粘 $A_{6}^{2}$ 0.243 0.267 否Y2
x11 浅白 $A_{1}^{3}$ 硬挺 $A_{2}^{3}$ 清脆 $A_{3}^{3}$ 模糊 $A_{4}^{3}$ 平坦 $A_{5}^{3}$ 硬滑 $A_{6}^{1}$ 0.245 0.057 否Y2
x12 浅白 $A_{1}^{3}$ 蜷缩 $A_{2}^{1}$ 浑浊 $A_{3}^{1}$ 模糊 $A_{4}^{3}$ 平坦 $A_{5}^{3}$ 软粘 $A_{6}^{2}$ 0.343 0.099 否Y2
x13 青绿 $A_{1}^{1}$ 稍蜷 $A_{2}^{2}$ 浑浊 $A_{3}^{1}$ 稍糊 $A_{4}^{2}$ 凹陷 $A_{5}^{1}$ 硬滑 $A_{6}^{1}$ 0.639 0.161 否Y2
x14 浅白 $A_{1}^{3}$ 稍蜷 $A_{2}^{2}$ 沉闷 $A_{3}^{2}$ 稍糊 $A_{4}^{2}$ 凹陷 $A_{5}^{1}$ 硬滑 $A_{6}^{1}$ 0.657 0.198 否Y2