本文为《机器学习》(周志华) 的读书笔记
- 参考 南瓜书
目录
基本流程
- 顾名思义，决策树是基于树结构来进行决策的; 叶结点对应于决策结果，其他每个结点则对应于一个属性测试; 每个结点包含的样本集合根据属性测试的结果被划分到子结点中; 根结点包含样本全集. 从根结点到每个叶结点的路径对应了一个判定测试序列
- 决策树学习的基本流程遵循"分而治之" (divide-and-conquer) 策略 (递归过程). 在决策树基本算法中，有三种情形会导致递归返回:
- (1) 当前结点包含的样本全属于同一类别，无需划分;
- (2) 当前属性集为空，或是所有样本在所有属性上取值相同，无法划分; 此时我们把当前结点标记为叶结点，并将其类别设定为该结点所含样本最多的类别 (利用当前结点的后验分布 → \rightarrow → 假设 x x x 为样本类别， θ \theta θ 为该结点样本满足的属性，该结点的类别即为 max x P ( x ∣ θ ) \mathop{\max}\limits_xP(x|\theta) xmaxP(x∣θ))
- (3) 当前结点包含的样本集合为空，不能划分. 这种情况下，我们同样把当前结点标记为叶结点，但将其类别设定为其父结点所含样本最多的类别 (把父结点的样本分布作为当前结点的先验分布)
划分选择
即选择最优划分属性
- 一般而言，随着划分过程不断进行，我们希望决策树的分支结点所包含的样本尽可能属于同一类别，即结点的"纯度" (purity) 越来越高.
信息增益 (information gain) (ID3)
信息熵 (information entropy)
- “信息熵” 是度量样本集合纯度最常用的一种指标. 假定当前样本集合
D
D
D 中第
k
k
k 类样本所占的比例为
p
k
p_k
pk (
k
=
1
,
2
,
.
.
.
,
∣
Y
∣
k = 1, 2,. . . , |\mathcal Y|
k=1,2,...,∣Y∣) ，则
D
D
D 的信息熵定义为
约定: 若 p = 0 p=0 p=0. 则 p log 2 p = 0 p\log_2p =0 plog2p=0 ( lim x → 0 x log 2 x = 0 \mathop{\lim}\limits_{x\rightarrow0}x\log_2x=0 x→0limxlog2x=0)
- 若令
∣
Y
∣
=
n
|\mathcal Y|= n
∣Y∣=n,
p
k
=
x
k
p_k = x_k
pk=xk，那么信息熵
E
n
t
(
D
)
Ent(D)
Ent(D) 就可以看作一个
n
n
n 元实值函数，也即
其中， 0 ≤ x k ≤ 1 0 ≤ x_k ≤ 1 0≤xk≤1, ∑ k = 1 n x k = 1 \sum^n_{k=1} x_k = 1 ∑k=1nxk=1，下面考虑求该多元函数的最值
- 首先我们先来求最大值，如果不考虑约束
0
≤
x
k
≤
1
0 ≤ x_k ≤ 1
0≤xk≤1，仅考虑
∑
k
=
1
n
x
k
=
1
\sum^n_{k=1} x_k = 1
∑k=1nxk=1 的话，对
f
(
x
1
,
.
.
.
,
x
n
)
f(x_1, ..., x_n)
f(x1,...,xn) 求最大值等价于如下最小化问题
显然，在 0 ≤ x k ≤ 1 0 ≤ x_k ≤ 1 0≤xk≤1 时，此问题为凸优化问题，而对于凸优化问题来说，能令其拉格朗日函数的一阶偏导数等于 0 的点即为最优解。根据拉格朗日乘子法可知，该优化问题的拉格朗日函数为
其中， λ λ λ 为拉格朗日乘子。对 L ( x 1 , . . . , x n , λ ) L(x_1, ..., x_n, λ) L(x1,...,xn,λ) 分别关于 x 1 , . . . , x n , λ x_1, ..., x_n, λ x1,...,xn,λ 求一阶偏导数，并令偏导数等于 0 可得
整理一下可得
由以上两个方程可以解得
满足约束 0 ≤ x k ≤ 1 0 ≤ x_k ≤ 1 0≤xk≤1; 将其代入 f ( x 1 , . . . , x n ) f(x_1, ..., x_n) f(x1,...,xn) 中可得最大值
- 求完最大值后下面我们再来求最小值，如果不考虑约束
∑
k
=
1
n
x
k
=
1
\sum^n_{k=1} x_k = 1
∑k=1nxk=1，仅考虑
0
≤
x
k
≤
1
0 ≤ x_k ≤ 1
0≤xk≤1 的话，
f
(
x
1
,
.
.
.
,
x
n
)
f(x_1, ..., x_n)
f(x1,...,xn) 可以看做是
n
n
n 个互不相关的一元函数的加和，也即
其中， g ( x k ) = − x k l o g 2 x k g(x_k) = −x_k log_2 x_k g(xk)=−xklog2xk, 0 ≤ x k ≤ 1 0 ≤ x_k ≤ 1 0≤xk≤1。那么当 g ( x 1 ) , g ( x 2 ) , . . . , g ( x n g(x_1), g(x_2), ..., g(x_n g(x1),g(x2),...,g(xn) 分别取到其最小值时， f ( x 1 , . . . , x n ) f(x_1, ..., x_n) f(x1,...,xn) 也就取到了最小值。所以接下来考虑求 g ( x 1 ) g(x_1) g(x1) 的最小值
所以 g ( x 1 ) g(x_1) g(x1) 是一个在其定义域范围内开口向下的凹函数，那么其最小值必然在边界取，于是分别取 x 1 = 0 x_1 = 0 x1=0 和 x 1 = 1 x_1 = 1 x1=1，代入 g ( x 1 ) g(x_1) g(x1) 可得
所以， g ( x 1 ) g(x_1) g(x1) 的最小值为 0，同理可得 g ( x 2 ) , . . . , g ( x n ) g(x_2), ..., g(x_n) g(x2),...,g(xn) 的最小值也为0，那么 f ( x 1 , . . . , x n ) f(x_1, ..., x_n) f(x1,...,xn) 的最小值此时也为 0。下面若考虑约束 ∑ k = 1 n x k = 1 \sum^n_{k=1} x_k = 1 ∑k=1nxk=1，那么 f ( x 1 , . . . , x n ) f(x_1, ..., x_n) f(x1,...,xn) 的最小值一定大于等于 0。如果令某个 x k = 1 x_k = 1 xk=1，那么根据约束 ∑ k = 1 n x k = 1 \sum^n_{k=1} x_k = 1 ∑k=1nxk=1 可知 x 1 = x 2 = . . . = x k − 1 = x k + 1 = . . . = x n = 0 x_1 = x_2 = ... = x_{k−1} = x_{k+1} = ... = x_n = 0 x1=x2=...=xk−1=xk+1=...=xn=0，将其代入 f ( x 1 , . . . , x n ) f(x_1, ..., x_n) f(x1,...,xn) 可得
因此 f ( x 1 , . . . , x n ) f(x_1, ..., x_n) f(x1,...,xn) 的最小值一定为 0
- 首先我们先来求最大值，如果不考虑约束
0
≤
x
k
≤
1
0 ≤ x_k ≤ 1
0≤xk≤1，仅考虑
∑
k
=
1
n
x
k
=
1
\sum^n_{k=1} x_k = 1
∑k=1nxk=1 的话，对
f
(
x
1
,
.
.
.
,
x
n
)
f(x_1, ..., x_n)
f(x1,...,xn) 求最大值等价于如下最小化问题
- 综上可知，当 f ( x 1 , . . . , x n ) f(x_1, ..., x_n) f(x1,...,xn) 取到最大值时： x 1 = x 2 = . . . = x n = 1 n x_1 = x_2 = ... = x_n =\frac{1}{n} x1=x2=...=xn=n1，此时样本集合纯度最低；当 f ( x 1 , . . . , x n ) f(x_1, ..., x_n) f(x1,...,xn) 取到最小值时： x k = 1 , x 1 = x 2 = . . . = x k − 1 = x k + 1 = . . . = x n = 0 x_k = 1, x_1 = x_2 = ... = x_{k−1} = x_{k+1} = ... = x_n = 0 xk=1,x1=x2=...=xk−1=xk+1=...=xn=0，此时样本集合纯度最高
条件熵
-
条件熵表示的是在已知一个随机变量的条件下，另一个随机变量的不确定性
- 具体地，假设有随机变量
X
X
X 和
Y
Y
Y，那么在已知
X
X
X 的条件下，随机变量
Y
Y
Y 的条件熵为
其中， p i = P ( X = x i ) p_i = P(X = x_i) pi=P(X=xi)
- 具体地，假设有随机变量
X
X
X 和
Y
Y
Y，那么在已知
X
X
X 的条件下，随机变量
Y
Y
Y 的条件熵为
互信息
-
互信息定义为信息熵和条件熵的差，它表示的是已知一个随机变量的信息后使得另一个随机变量的不确定性减少的程度
- 具体地，假设有随机变量
X
X
X 和
Y
Y
Y，那么在已知
X
X
X 的信息后，
Y
Y
Y 的不确定性减少的程度为
- 具体地，假设有随机变量
X
X
X 和
Y
Y
Y，那么在已知
X
X
X 的信息后，
Y
Y
Y 的不确定性减少的程度为
信息增益 (information gain)
- 假定离散属性
a
a
a 有
V
V
V 个可能的取值
{
a
1
,
.
.
.
,
a
V
}
\{a_1,...,a^V\}
{a1,...,aV}，若使用
a
a
a 来对样本集
D
D
D 进行划分，则会产生
V
V
V 个分支结点, 其中第
v
v
v 个分支结点包含了
D
D
D 中所有在属性
a
a
a 上取值为
a
V
a^V
aV 的样本, 记为
D
V
D^V
DV. 我们可根据式 (4.1) 计算出
D
V
D^V
DV 的信息熵, 再考虑到不同的分支结点所包含的样本数不同, 给分支结点赋予权重
∣
D
V
∣
/
∣
D
∣
|D^V|/|D|
∣DV∣/∣D∣，于是可计算出用属性
a
a
a 对样本集
D
D
D 进行划分所获得的"信息增益"
- 在信息论中信息增益也称为互信息。所以在这里，这个公式可以理解为在属性 a a a 的取值已知后数据集 D D D 中类别 k k k 的不确定性减小的程度。若根据某个属性计算得到的信息增益越大，则说明在知道其取值后样本集的不确定性减小的程度越大，也即为“纯度提升”越大
利用信息增益来进行决策树的划分属性选择
a ∗ = arg max a ∈ A Gain ( D , a ) a_{*}=\underset{a \in A}{\arg \max } \operatorname{Gain}(D, a) a∗=a∈AargmaxGain(D,a)
著名的 ID3 决策树学习算法就是以信息增益为准则来选择划分属性 (ID3 名字中的 ID 是 Iterative Dichotomiser (迭代二分器) 的简称)
例
- 以表 4.1 中的西瓜数据集 2.0 为例，该数据集包含 17 个训练样例，用以学习一棵能预测没剖开的是不是好瓜的决策树. 显然，
∣
Y
∣
=
2
|\mathcal Y| = 2
∣Y∣=2. 在决策树学习开始时，根结点包含
D
D
D 中的所有样例，其中正例占
p
1
=
8
17
p_1 =\frac{8}{17}
p1=178，反例占
9
17
\frac{9}{17}
179. 于是，根据式 (4.1) 可计算出根结点的信息熵为
- 然后，我们要计算出当前属性集合 {色泽，根蒂，敲声，纹理，脐部，触感} 中每个属性的信息增益. 以属性"色泽"为例，它有 3 个可能的取值: {青绿，乌黑，浅白}. 若使用该属性对
D
D
D 进行划分，则可得到 3 个子集，分别记为:
D
1
D^1
D1(色泽=青绿)，
D
2
D^2
D2 (色泽=乌黑)，
D
3
D^3
D3 (色泽=浅白).
- 子集
D
1
D^1
D1 包含编号为 {1, 4, 6, 10, 13, 17} 的 6 个样例，其中正例占
p
1
=
3
6
p_1=\frac{3}{6}
p1=63，反例占
p
2
=
3
6
p_2=\frac{3}{6}
p2=63; 则
- 同理
- 子集
D
1
D^1
D1 包含编号为 {1, 4, 6, 10, 13, 17} 的 6 个样例，其中正例占
p
1
=
3
6
p_1=\frac{3}{6}
p1=63，反例占
p
2
=
3
6
p_2=\frac{3}{6}
p2=63; 则
- 于是，属性"色泽"的信息增益为
- 类似的，我们可计算出其他属性的信息增益:
- 显然，属性"纹理"的信息增益最大，于是它被选为划分属性
- 然后，决策树学习算法将对每个分支结点做进一步划分， 最终得到的
决策树如图 4.4 所示.
增益率 (gain ratio) (C4.5)
- 在上面的介绍中，我们有意忽略了表 4.1 中的 “编号” 这一列. 若把 “编号” 也作为一个候选划分属性，则根据式件均可计算出它的信息增益为 0.998，远大于其他候选划分属性
- 这很容易理解: "编号"将产生 17 个分支，每个分支结点仅包含一个样本，这些分支结点的纯度己达最大. 然而，这样的决策树显然不具有泛化能力，无法对新样本进行有效预测
- 实际上，信息增益准则对可取值数目较多的属性有所偏好，为减少这种偏好可能带来的不利影响，著名的 C4.5 决策树算法不直接使用信息增益，而是使用"增益率"来选择最优划分属性. 采用与式 (4.2) 相同的符号表示，增益率定义为
其中
称为属性 a a a 的"固有值" (intrinsic value). 属性 a a a 的可能取值数目越多(即 V V V 越大)，则 I V ( a ) IV(a) IV(a) 的值通常会越大.
- 例如，对表 4.1 的西瓜数据集 2.0，有 I V ( 触 感 ) = 0.874 IV(触感) = 0.874 IV(触感)=0.874 ( V = 2 V = 2 V=2), I V ( 色 泽 ) = 1.580 IV(色泽) = 1.580 IV(色泽)=1.580 ( V = 3 V = 3 V=3), I V ( 编 号 ) = 4.088 IV(编号) = 4.088 IV(编号)=4.088 ( V = 17 V = 17 V=17).
- 需注意的是，增益率准则对可取值数目较少的属性有所偏好. 因此， C4.5 算法并不是直接选择增益率最大的候选划分属性，而是使用了一个启发式: 先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的.
基尼指数 (Gini index) (CART)
CART: Classification and Regression; 分类和回归任务都可用
- 数据集
D
D
D 的纯度可用基尼值来度量:
- 直观来说， G i n i ( D ) Gini(D) Gini(D) 反映了从数据集 D D D 中随机抽取两个样本，其类别标记不一致的概率. 因此， G i n i ( D ) Gini(D) Gini(D) 越小，则数据集 D D D 的纯度越高.
- 属性
a
a
a 的基尼指数定义为
- 于是，我们在候选属性集合 A A A 中，选择那个使得划分后基尼指数最小的属性作为最优划分属性，即 a ∗ = arg min a ∈ A Gini_index ( D , a ) . a_{*}=\underset{a \in A}{\arg \min } \text{ Gini\_index} (D, a) \text { . } a∗=a∈Aargmin Gini_index(D,a) .
CART 分类树的构造算法
由于 CART 分类树是一棵二叉树，因此 CART 不直接按照式 (4.6) 进行划分
- (1) 对每个属性
a
a
a 的每个可能取值
v
v
v，将数据集
D
D
D 分为
a
=
v
a = v
a=v 和
a
≠
v
a \neq v
a=v 两部分来计算基尼指数，即
Gini_index ( D , a ) = ∣ D a = v ∣ ∣ D ∣ Gini ( D a = v ) + ∣ D a ≠ v ∣ ∣ D ∣ Gini ( D a ≠ v ) \text { Gini\_index }(D, a)=\frac{\left|D^{a=v}\right|}{|D|} \operatorname{Gini}\left(D^{a=v}\right)+\frac{\left|D^{a \neq v}\right|}{|D|} \operatorname{Gini}\left(D^{a \neq v}\right) Gini_index (D,a)=∣D∣∣Da=v∣Gini(Da=v)+∣D∣∣∣Da=v∣∣Gini(Da=v) - (2) 选择基尼指数最小的属性及其对应取值作为最优划分属性和最优划分点
- (3) 重复以上两步，直至满足停止条件
CART 回归树的构造算法
- to be continued… (Pumpkin book)
剪枝处理 (pruning)
- 在决策树学习中，为了尽可能正确分类训练样本，结点划分过程将不断重复，有时会造成决策树分支过多，导致过拟合. 因此，可通过主动去掉一些分支来降低过拟合的风险
基本策略
- “预剪枝” (prepruning): 在决策树生成过程中，对每个结点在划分前先进行估计，若当前结点的划分不能带来决策树泛化性能提升，则停止划分并将当前结点标记为叶结点
- “后剪枝” (postpruning): 先从训练集生成一棵完整的决策树，然后自底向上地对非叶结点进行考察，若将该结点对应的子树替换为叶结点能带来决策树泛化性能提升，则将该子树替换为叶结点
下面用留出法来判断决策树泛化性能是否提升，即预留一部分数据用作"验证集"以进行性能评估；同时假定采用信息增益准则来进行划分属性选择
预剪枝 (prepruning)
- 基于信息增益准则，我们会选取属性"脐部"来对训练集进行划分，并产生 3 个分支，如图 4.6 所示. 然而，是否应该进行这个划分呢? 预剪枝要对划分前后的泛化性能进行估计
- 在划分之前，所有样例集中在根结点. 若不进行划分，则该结点将被标记为叶结点，其类别标记为训练样例数最多的类别 (当样例最多的类不唯一时，可任选其中一类)，假设我们将这个叶结点标记为 “好瓜”. 用验证集对这个单结点决策树进行评估, 则编号为 {4, 5, 8} 的样例被分类正确, 另外 4 个样例分类错误，于是，验证集精度为 3 7 = 42.9 % \frac{3}{7}=42.9\% 73=42.9%
- 在用属性"脐部"划分之后, 图 4.6 中的结点 ②、③、④ 分别包含编号为 {1, 2, 3, 14} 、{6, 7, 15, 17} 、{10, 16} 的训练样例，因此这 3 个结点分别被标记为叶结点"好瓜"、“好瓜”、“坏瓜”. 此时，验证集中编号为 {4, 5, 8, 11, 12} 的样例被分类正确，验证集精度为 5 7 = 71.4 % > 42.9 % \frac{5}{7}= 71.4\% > 42.9\% 75=71.4%>42.9%. 于是，用"脐部"进行划分得以确定.
- 同理，结点 ②③ 在划分后均不能提升验证集精度，于是，预剪枝策略禁止结点 ②③ 被划分. 对结点 ④， 其所含训练样例己属于同一类，不再进行划分.
- 于是， 基于预剪枝策略从表 4.2 数据所生成的决策树如图 4.6 所示，其验证集精度为 71. 4%. 这是一棵仅有一层划分的决策树，亦称"决策树桩" (decision stump).
- 对比图 4.6 和图 4.5 可看出，预剪枝使得决策树的很多分支都没有"展开", 这不仅降低了过拟合风险，还显著减少了决策树的训练及测试时间开销
- 但另一方面，有些分支的当前划分虽不能提升泛化性能、甚至可能导致泛化性能暂时下降，但在其基础上进行的后续划分却有可能导致性能显著提高; 预剪枝基于"贪心"本质禁止这些分支展开，给预剪枝决策树带来了欠拟含的风险
后剪枝 (postpruning)
- 后剪枝先从训练集生成一棵完整决策树. 例如基于表 4.2 的数据我们得到如图 4.5 所示的决策树. 该决策树的验证集精度为 42.9%
- 后剪枝首先考察图 4.5 中的结点 ⑥. 若将其领衔的分支剪除，则相当于把 ⑤ 替换为叶结点. 替换后的叶结点包含编号为 {7, 15} 的训练样本，于是该叶结点的类别标记为"好瓜"，此时决策树的验证集精度提高至 57.1%. 于是，后剪枝策略决定剪枝. 同理，依次考察结点 ⑤③②①，最终对 ② 进行剪枝. 最终?基于后剪枝策略从表 4.2 数据所生成的决策树如图 4.7 所示，其验证集精度为 71. 4%.
- 对比图 4.7 和图 4.6 可看出, 后剪枝决策树通常比预剪枝决策树保留了更多的分支. 一般情形下, 后剪枝决策树的欠拟合风险很小，泛化性能往往优于预剪枝决策树.
- 但后剪枝过程是在生成完全决策树之后进行的, 并且要自底向上地对树中的所有非叶结点进行逐一考察，因此其训练时间开销比未剪枝决策树和预剪枝决策树都要大得多
连续与缺失值
连续值处理: 二分法
- 下面讨论如何在决策树学习中使用连续属性
→
\rightarrow
→ 连续属性离散化
- 最简单的策略是采用二分法 (bi-partition) 对连续属性进行处理，这正是 C4.5 决策树算法中采用的机制
- 给定样本集 D D D 和连续属性 a a a, 基于划分点 t t t 可将 D D D 分为子集 D t − D_t^- Dt− 和 D t + D_t^+ Dt+, 其中 D t − D_t^- Dt− 包含那些在属性 a a a 上取值不大于 t t t 的样本，而 D t + D_t^+ Dt+ 则包含那些在属性 a a a 上取值大于 t t t 的样本
- 假定
a
a
a 在
D
D
D 上出现了
n
n
n 个不同的取值，将这些值从小到大进行排序，记为
{
a
1
,
a
2
,
.
.
.
,
a
n
}
\{a^1,a^2,...,a^n\}
{a1,a2,...,an}，显然，对相邻的属性取值
a
i
a^i
ai 与
a
i
+
1
a^{i+1}
ai+1 来说，
t
t
t 在区间
[
a
i
,
a
i
+
1
)
[a^i,a^{i+1})
[ai,ai+1) 中取任意值所产生的划分结果相同. 因此，对连续属性
a
a
a, 我们可考察包含
n
−
1
n-1
n−1 个元素的候选划分点集合
- 例如，对于“密度”这个连续属性，已观测到的可能取值为 {0.243, 0.245, 0.343, 0.360, 0.403, 0.437, 0.481, 0.556, 0.593, 0.608, 0.634, 0.639, 0.657, 0.666, 0.697, 0.719, 0.774} 共 17 个值，根据公式（4.7）可知，此时
i
i
i 依次取 1 到16，那么“密度”这个属性的候选划分点集合为
- 例如，对于“密度”这个连续属性，已观测到的可能取值为 {0.243, 0.245, 0.343, 0.360, 0.403, 0.437, 0.481, 0.556, 0.593, 0.608, 0.634, 0.639, 0.657, 0.666, 0.697, 0.719, 0.774} 共 17 个值，根据公式（4.7）可知，此时
i
i
i 依次取 1 到16，那么“密度”这个属性的候选划分点集合为
- 于是，我们可对式 (4.2) 稍加改造以得到用连续属性
a
a
a 进行划分时可得到的最大信息增益：
- 由式 (4.8) 可计算出属性“密度” 的信息增益为 0.262, 对应于划分点 0.381 (
0.360
+
0.403
2
\frac{0.360+0.403}{2}
20.360+0.403). 最终生成如图 4.8 所示的决策树
- 由式 (4.8) 可计算出属性“密度” 的信息增益为 0.262, 对应于划分点 0.381 (
0.360
+
0.403
2
\frac{0.360+0.403}{2}
20.360+0.403). 最终生成如图 4.8 所示的决策树
- 需注意的是，与离散属性不同，若当前结点划分属性为连续属性，该属性还可作为其后代结点的划分属性，只是划分点选取的范围变小了
- 例如在父结点上使用了 “密度 ≤ 0.381 \leq0.381 ≤0.381" , 不会禁止在子结点上使用"密度 ≤ 0.294 \leq0.294 ≤0.294"
缺失值处理
- 现实任务中常会遇到不完整样本，即样本的某些属性值缺失. 如果简单地放弃不完整样本，仅使用无缺失值的样本来进行学习，显然是对数据信息极大的浪费
- 例如，表 4.4 西瓜数据集 2.0 出现缺失值的版本，如果放弃不完整样本，则仅有编号 {4, 7, 14, 16} 的 4 个样本能被使用. 显然，有必要考虑利用有缺失属性值的训练样例来进行学习
- 例如，表 4.4 西瓜数据集 2.0 出现缺失值的版本，如果放弃不完整样本，则仅有编号 {4, 7, 14, 16} 的 4 个样本能被使用. 显然，有必要考虑利用有缺失属性值的训练样例来进行学习
(1) 如何在属性值缺失的情况下进行划分属性选择?
- 给定训练集 D D D 和属性 a a a，令 D ~ \tilde D D~ 表示 D D D 中在属性 a a a 上没有缺失值的样本子集. 对问题 (1)，显然我们仅可根据 D ~ \tilde D D~ 来判断属性 a a a 的优劣. 假定属性 a a a 有 V V V 个可取值 { a 1 , … , a V } \{a^1,…,a^V\} {a1,…,aV}，令 D ~ v \tilde D^v D~v 表示 D ~ \tilde D D~ 中在属性 a a a 上取值为 a v a^v av 的样本子集， D ~ k \tilde D_k D~k 表示 D ~ \tilde D D~ 中属于第 k k k 类 ( k = 1 , 2 , . . . , ∣ Y ∣ k = 1, 2, .. . ,|\mathcal Y| k=1,2,...,∣Y∣) 的样本子集
- 假定我们为每个样本
x
\boldsymbol x
x 赋予一个权重
w
x
w_\boldsymbol x
wx (在决策树学习开始阶段，设置根结点中各样本的权重初始化为 1) 并定义
- 直观地看，对属性 a a a， ρ ρ ρ 表示无缺失值样本所占的比例; p ~ k \tilde p_k p~k 表示无缺失值样本中第 k k k 类所占的比例; r ~ v \tilde r_v r~v 则表示无缺失值样本中在属性 a a a 上取值 a v a^v av 的样本所占的比例
- 基于上述定义，我们可将信息增益的计算式 (4.2) 推广为
其中
其实就是在 D ~ \tilde D D~ 上计算信息增益，然后乘上一个权重 ρ \rho ρ 得到最终的信息增益，这个权重使结果考虑了缺失值的影响。如果某个属性缺失值很多，最后得到的信息增益也会较小
(2) 给定划分属性，若样本在该属性上的值缺失，如何对样本进行划分?
- 若样本 x \boldsymbol x x 在划分属性 a a a 上的取值己知，则将 x \boldsymbol x x 划入与其取值对应的子结点，且样本权值在子结点中保持为 w x w_\boldsymbol x wx.
- 若样本
x
\boldsymbol x
x 在划分属性
a
a
a 上的取值未知，则将
x
\boldsymbol x
x 同时划入所有子结点, 且样本权值在与属性值
a
v
a^v
av 对应的子结点中调整为
r
~
v
⋅
w
x
\tilde r_v\cdot w_\boldsymbol x
r~v⋅wx
- 直观地看，这就是让同一个样本以不同的概率划入到不同的子结点中去.
C4.5 算法使用了上述解决方案
多变量决策树 (multivariate decision tree)
- 若我们把每个属性视为坐标空间中的一个坐标轴，则 d d d 个属性描述的样本就对应了 d d d 维空间中的一个数据点，对样本分类则意味着在这个坐标空间中寻找不同类样本之间的分类边界
-
决策树所形成的分类边界有一个明显的特点: 轴平行 (axis-parallel) ，即它的分类边界由若干个与坐标轴平行的分段组成. 如图 4.10, 4.11 所示，分类边界的每一段都是与坐标轴平行的. 这样的分类边界使得学习结果有较好的可解释性，因为每一段划分都直接对应了某个属性取值
- 但在学习任务的真实分类边界比较复杂时，必须使用很多段划分才能获得较好的近似. 如图 4.12 所示;此时的决策树会相当复杂，由于要进行大量的属性测试，预测时间开销会很大.
- 若能使用斜的划分边界，如图 4.12 中红色线段所示，则决策树模型将大为简化. “多变量决策树” 就是能实现这样的"斜划分"甚至更复杂划分的决策树.
- 以实现斜划分的多变量决策树为例，在此类决策树中，非叶结点不再是仅对某个属性，而是对属性的线性组合进行测试; 换言之，每个非叶结点是一个形如
∑
i
=
1
d
w
i
a
i
=
t
\sum_{i=1}^dw_ia_i=t
∑i=1dwiai=t 的线性分类器，其中
w
i
w_i
wi 是属性
a
i
a_i
ai 的权重，
w
i
w_i
wi 和
t
t
t 可在该结点所含的样本集和属性集上学得. 于是，多变量决策树在学习过程中，会试图建立一个合适的线性分类器
- 以实现斜划分的多变量决策树为例，在此类决策树中，非叶结点不再是仅对某个属性，而是对属性的线性组合进行测试; 换言之，每个非叶结点是一个形如
∑
i
=
1
d
w
i
a
i
=
t
\sum_{i=1}^dw_ia_i=t
∑i=1dwiai=t 的线性分类器，其中
w
i
w_i
wi 是属性
a
i
a_i
ai 的权重，
w
i
w_i
wi 和
t
t
t 可在该结点所含的样本集和属性集上学得. 于是，多变量决策树在学习过程中，会试图建立一个合适的线性分类器