决策树
特征选择
1、策略：选择信息增益/信息增益比最大的特征
2、熵与信息增益
（1）熵
- 熵
表示的是随机变量不确定性的度量
P
(
X
=
x
i
)
=
p
i
，
i
=
1
，
2
，
…
,
n
P(X= x_i) = p_i，i = 1，2，\dots,n
P(X=xi)=pi，i=1，2，…,n，为取有限个值的离散随机变量X的概率分布,随机变量X的熵:
H
(
X
)
=
−
∑
i
=
1
n
p
i
log
p
i
H(X) = - \sum_{i=1}^n p_i \log p_i
H(X)=−i=1∑npilogpi
熵越大，随机变量的不确定性越大:
0
≤
H
(
p
)
≤
log
n
0 \leq H(p) \leq \log n
0≤H(p)≤logn
- 条件熵
表示已知随机变量X的条件下随机变量Y的不确定性
随机变量（X，Y）的联合概率分布:
P
(
X
=
x
i
,
Y
=
y
i
)
=
p
i
j
i
=
1
，
2
，
…
,
n
j
=
i
=
1
，
2
，
…
,
m
\begin{aligned} &P(X= x_i,Y = y_i) = p_{ij}\\ &i = 1，2，\dots,n\\ &j = i = 1，2，\dots,m \end{aligned}
P(X=xi,Y=yi)=piji=1，2，…,nj=i=1，2，…,m
X给定的条件下Y的熵:
H
(
Y
∣
X
)
=
∑
i
=
1
n
p
i
H
(
Y
∣
X
=
x
i
)
H(Y|X) =\sum_{i=1}^n p_i H(Y | X = x_i)
H(Y∣X)=i=1∑npiH(Y∣X=xi)
熵和经验熵的求解：通过数据估计，尤其是极大似然估计求解
（2）信息增益
表示得知特征X的信息而使类Y的信息的不确定性减少的程度，特征A对训练数据D的信息增益，定义为集合D的经验熵与特征A给定条件下D的经验条件熵之差:
g
(
D
,
A
)
=
H
(
D
)
−
H
(
D
∣
A
)
g(D,A) = H(D) - H(D|A)
g(D,A)=H(D)−H(D∣A)
（3）信息增益比
信息增益规则倾向于选择取值较多的特征，信息增益比对这一问题进行矫正。特征A对训练数据集D的信息增益比定义为其信息增益与训练数据D关于特征A的值的熵之比：
g
R
(
D
,
A
)
=
g
(
D
,
A
)
H
A
(
D
)
其
中
：
H
A
(
D
)
=
−
∑
i
=
1
n
∣
D
i
∣
∣
D
∣
log
2
∣
D
i
∣
∣
D
∣
;
n
是
特
征
A
取
值
的
个
数
\begin{aligned} &g_R(D,A) = \frac{g(D,A)}{H_A(D)}\\ 其中：\\ &H_A(D) = -\sum_{i=1}^n \frac{|D_i|}{|D|} \log_2 \frac{|D_i|}{|D|};n是特征A取值的个数 \end{aligned}
其中：gR(D,A)=HA(D)g(D,A)HA(D)=−i=1∑n∣D∣∣Di∣log2∣D∣∣Di∣;n是特征A取值的个数
3、信息增益算法
输入：训练数据集$ D = { (x_1,y_1),(x_2,y_2),\dots,(x_N,y_N)}$；特征A
输出：特征A对训练数据D的信息增益 g ( D , A ) g(D,A) g(D,A)
步骤：
1
、
计
算
数
集
D
的
经
验
熵
H
(
D
)
:
H
(
X
)
=
−
∑
k
=
1
K
∣
C
k
∣
∣
D
∣
log
2
∣
C
k
∣
∣
D
∣
2
、
计
算
特
征
A
对
数
据
集
D
的
经
验
条
件
熵
H
(
D
,
A
)
:
H
(
D
∣
A
)
=
∑
i
=
1
n
∣
D
i
∣
∣
D
∣
H
(
D
i
)
=
−
∑
i
=
1
n
∣
D
i
∣
∣
D
∣
∑
k
=
1
K
∣
D
i
k
∣
∣
D
i
∣
log
2
∣
D
i
k
∣
∣
D
i
∣
3
、
计
算
信
息
增
益
g
(
D
,
A
)
:
g
(
D
,
A
)
=
H
(
D
)
−
H
(
D
∣
A
)
其
中
：
D
:
训
练
集
，
∣
D
∣
表
示
其
的
容
量
;
C
k
:
实
例
类
别
，
k
=
1
,
2
,
…
,
K
;
∣
C
k
∣
:
表
示
属
于
该
类
别
的
样
本
个
数
,
∑
k
=
1
K
｜
C
k
｜
=
｜
D
｜
A
:
样
本
特
征
，
有
n
个
不
同
的
取
值
{
a
1
,
a
2
,
…
,
a
n
}
;
D
i
:
根
据
A
的
取
值
将
D
划
分
成
n
个
子
集
,
i
=
1
,
2
,
…
,
n
;
∣
D
i
∣
:
表
示
D
i
的
样
本
个
数
,
∑
i
=
1
n
∣
D
i
∣
=
∣
D
∣
D
i
k
:
子
集
D
i
中
属
于
C
k
的
样
本
的
集
合
,
D
i
k
=
D
i
∩
C
k
;
∣
D
i
k
∣
:
为
其
样
本
个
数
\begin{aligned} &1、计算数集D的经验熵H(D):\\ &\quad\quad H(X) = - \sum_{k=1}^K \frac{|C_k|}{|D|} \log_2 \frac{|C_k|}{|D|}\\ &2、计算特征A对数据集D的经验条件熵H(D,A):\\ &\quad\quad H(D|A) = \sum_{i=1}^n \frac{|D_i|}{|D|}H(D_i)= -\sum_{i=1}^n \frac{|D_i|}{|D|}\sum_{k=1}^K \frac{|D_{ik}|}{|D_i|}\log_2 \frac{|D_{ik}|}{|D_i|}\\ &3、计算信息增益g(D,A):\\ &\quad\quad g(D,A) = H(D) - H(D|A)\\ \\ &\quad\quad其中：\\ &\quad\quad\quad\quad D:训练集，|D|表示其的容量;\\ &\quad\quad\quad\quad C_k:实例类别，k = 1,2,\dots,K;|C_k|:表示属于该类别的样本个数,\sum_{k=1}^K｜C_k｜ = ｜D｜\\ &\quad\quad\quad\quad A:样本特征，有n个不同的取值\{a_1,a_2,\dots,a_n \};\\ &\quad\quad\quad\quad D_i:根据A的取值将D划分成n个子集,i = 1,2,\dots,n;|D_i|:表示D_i的样本个数,\sum_{i=1}^n |D_i| = |D|\\ &\quad\quad\quad\quad D_{ik}:子集D_i中属于C_k的样本的集合,D_{ik} = D_i \cap C_k;|D_{ik}|:为其样本个数\\ \end{aligned}
1、计算数集D的经验熵H(D):H(X)=−k=1∑K∣D∣∣Ck∣log2∣D∣∣Ck∣2、计算特征A对数据集D的经验条件熵H(D,A):H(D∣A)=i=1∑n∣D∣∣Di∣H(Di)=−i=1∑n∣D∣∣Di∣k=1∑K∣Di∣∣Dik∣log2∣Di∣∣Dik∣3、计算信息增益g(D,A):g(D,A)=H(D)−H(D∣A)其中：D:训练集，∣D∣表示其的容量;Ck:实例类别，k=1,2,…,K;∣Ck∣:表示属于该类别的样本个数,k=1∑K｜Ck｜=｜D｜A:样本特征，有n个不同的取值{a1,a2,…,an};Di:根据A的取值将D划分成n个子集,i=1,2,…,n;∣Di∣:表示Di的样本个数,i=1∑n∣Di∣=∣D∣Dik:子集Di中属于Ck的样本的集合,Dik=Di∩Ck;∣Dik∣:为其样本个数
决策树生成
1、ID3
- 特点
- 基于信息增益进行特征选择
- 用极大似然估计法进行概率模型的选择
- 算法
输入：训练数据集：D；特征集A的阈值 ε \varepsilon ε
输出：决策树T
步骤：
1
、
若
D
中
所
有
实
例
均
属
于
同
一
类
C
k
，
则
T
为
单
结
点
树
，
并
将
C
k
作
为
该
结
点
的
类
标
记
，
返
回
T
;
2
、
若
A
=
ϕ
,
则
T
为
单
结
点
树
，
并
将
D
只
能
够
实
例
数
最
大
的
类
C
k
作
为
该
结
点
的
类
标
记
，
返
回
T
;
3
、
否
则
按
照
信
息
增
益
算
法
计
算
A
中
各
特
征
对
D
的
信
息
增
益
，
选
择
信
息
增
益
最
大
的
特
征
A
g
;
4
、
如
果
A
g
的
信
息
增
益
小
于
阈
值
ε
,
则
置
T
为
单
结
点
树
，
并
将
D
中
实
例
最
大
的
类
C
k
作
为
该
结
点
的
类
标
记
，
返
回
T
;
5
、
否
则
对
A
g
每
个
可
能
的
值
a
i
,
依
A
g
=
a
i
将
D
分
割
为
若
干
非
空
子
集
D
i
,
将
D
i
中
实
例
最
大
的
类
作
为
标
记
，
构
建
子
结
点
，
由
结
点
及
其
子
结
点
构
成
树
T
，
返
回
T
;
6
、
对
第
i
各
子
结
点
，
以
D
i
为
训
练
集
，
以
A
−
{
A
g
}
为
特
征
集
，
递
归
的
调
用
1
到
5
步
，
得
到
子
树
T
i
，
返
回
T
i
;
\begin{aligned} & 1、若D中所有实例均属于同一类C_k，则T为单结点树，并将C_k作为该结点的类标记，返回T; \\ & 2、若A=\phi,则T为单结点树，并将D只能够实例数最大的类C_k作为该结点的类标记，返回T; \\ & 3、否则按照信息增益算法计算A中各特征对D的信息增益，选择信息增益最大的特征A_g; \\ & 4、如果A_g的信息增益小于阈值\varepsilon,则置T为单结点树，并将D中实例最大的类C_k作为该结点的类标记，返回T;\\ & 5、否则对A_g每个可能的值a_i,依A_g= a_i将D分割为若干非空子集D_i,将D_i中实例最大的类作为标记，\\ & 构建子结点，由结点及其子结点构成树T，返回T;\\ & 6、对第i各子结点，以D_i为训练集，以A-\{A_g\}为特征集，递归的调用1到5步，得到子树T_i，返回T_i;\\ \end{aligned}
1、若D中所有实例均属于同一类Ck，则T为单结点树，并将Ck作为该结点的类标记，返回T;2、若A=ϕ,则T为单结点树，并将D只能够实例数最大的类Ck作为该结点的类标记，返回T;3、否则按照信息增益算法计算A中各特征对D的信息增益，选择信息增益最大的特征Ag;4、如果Ag的信息增益小于阈值ε,则置T为单结点树，并将D中实例最大的类Ck作为该结点的类标记，返回T;5、否则对Ag每个可能的值ai,依Ag=ai将D分割为若干非空子集Di,将Di中实例最大的类作为标记，构建子结点，由结点及其子结点构成树T，返回T;6、对第i各子结点，以Di为训练集，以A−{Ag}为特征集，递归的调用1到5步，得到子树Ti，返回Ti;
2、C4.5
- 特点
- 基于信息增益比进行特征选择
- 用极大似然估计法进行概率模型的选择
- 算法
1 、 若 D 中 所 有 实 例 均 属 于 同 一 类 C k ， 则 T 为 单 结 点 树 ， 并 将 C k 作 为 该 结 点 的 类 标 记 ， 返 回 T ; 2 、 若 A = ϕ , 则 T 为 单 结 点 树 ， 并 将 D 只 能 够 实 例 数 最 大 的 类 C k 作 为 该 结 点 的 类 标 记 ， 返 回 T ; 3 、 否 则 按 照 信 息 增 益 比 算 法 计 算 A 中 各 特 征 对 D 的 信 息 增 益 比 ， 选 择 信 息 增 益 最 大 的 特 征 A g ; 4 、 如 果 A g 的 信 息 增 益 比 小 于 阈 值 ε , 则 置 T 为 单 结 点 树 ， 并 将 D 中 实 例 最 大 的 类 C k 作 为 该 结 点 的 类 标 记 ， 返 回 T ; 5 、 否 则 对 A g 每 个 可 能 的 值 a i , 依 A g = a i 将 D 分 割 为 若 干 非 空 子 集 D i , 将 D i 中 实 例 最 大 的 类 作 为 标 记 ， 构 建 子 结 点 ， 由 结 点 及 其 子 结 点 构 成 树 T ， 返 回 T ; 6 、 对 第 i 各 子 结 点 ， 以 D i 为 训 练 集 ， 以 A − { A g } 为 特 征 集 ， 递 归 的 调 用 1 到 5 步 ， 得 到 子 树 T i ， 返 回 T i ; \begin{aligned} &1、若D中所有实例均属于同一类C_k，则T为单结点树，并将C_k作为该结点的类标记，返回T;\\ &2、若A=\phi,则T为单结点树，并将D只能够实例数最大的类C_k作为该结点的类标记，返回T;\\ &3、否则按照信息增益比算法计算A中各特征对D的信息增益比，选择信息增益最大的特征A_g;\\ &4、如果A_g的信息增益比小于阈值\varepsilon,则置T为单结点树，并将D中实例最大的类C_k作为该结点的类标记，返回T;\\ &5、否则对A_g每个可能的值a_i,依A_g= a_i将D分割为若干非空子集D_i,将D_i中实例最大的类作为标记，\\&构建子结点，由结点及其子结点构成树T，返回T;\\ &6、对第i各子结点，以D_i为训练集，以A-\{A_g\}为特征集，递归的调用1到5步，得到子树T_i，返回T_i;\\ \end{aligned} 1、若D中所有实例均属于同一类Ck，则T为单结点树，并将Ck作为该结点的类标记，返回T;2、若A=ϕ,则T为单结点树，并将D只能够实例数最大的类Ck作为该结点的类标记，返回T;3、否则按照信息增益比算法计算A中各特征对D的信息增益比，选择信息增益最大的特征Ag;4、如果Ag的信息增益比小于阈值ε,则置T为单结点树，并将D中实例最大的类Ck作为该结点的类标记，返回T;5、否则对Ag每个可能的值ai,依Ag=ai将D分割为若干非空子集Di,将Di中实例最大的类作为标记，构建子结点，由结点及其子结点构成树T，返回T;6、对第i各子结点，以Di为训练集，以A−{Ag}为特征集，递归的调用1到5步，得到子树Ti，返回Ti;
决策树剪枝
1、策略
利用损失函数最小化原则进行剪枝，即利用正则化的极大似然估计进行模型选择
- 决策树的损失函数
C α ( T ) = C ( T ) + α ∣ T ∣ 其 中 ： C ( T ) = ∑ t = 1 ∣ T ∣ N t H t ( T ) = − ∑ t = 1 ∣ T ∣ ∑ k = 1 K N t k log N t k N t H t ( T ) = − ∑ k N t k N t log N t k N t ∣ T ∣ : 树 T 的 叶 结 点 的 个 数 , t : 树 T 的 叶 结 点 ， 该 结 点 有 N t 各 样 本 点 ， 表 示 模 型 复 杂 度 N t k : 第 k 类 的 样 本 点 个 数 ; H t ( T ) : 为 叶 结 点 t 上 的 经 验 熵 ; α : 参 数 ， α ≥ 0 , 控 制 模 型 复 杂 度 和 拟 合 程 度 之 间 的 影 响 \begin{aligned} &C_\alpha(T) = C(T) + \alpha|T|\\ 其中：\\ &C(T) =\sum_{t=1}^{|T|} N_tH_t(T) =-\sum_{t=1}^{|T|} \sum_{k=1}^{K} N_{tk}\log \frac{N_{tk}}{N_t}\\ &H_t(T) = -\sum_{k} \frac{N_{tk}}{N_t}\log \frac{N_{tk}}{N_t}\\ &|T|:树T的叶结点的个数,t:树T的叶结点，该结点有N_t各样本点，表示模型复杂度\\ &N_{tk}:第k类的样本点个数;H_t(T):为叶结点t上的经验熵;\\ &\alpha:参数，\alpha \geq 0,控制模型复杂度和拟合程度之间的影响\\ \end{aligned} 其中：Cα(T)=C(T)+α∣T∣C(T)=t=1∑∣T∣NtHt(T)=−t=1∑∣T∣k=1∑KNtklogNtNtkHt(T)=−k∑NtNtklogNtNtk∣T∣:树T的叶结点的个数,t:树T的叶结点，该结点有Nt各样本点，表示模型复杂度Ntk:第k类的样本点个数;Ht(T):为叶结点t上的经验熵;α:参数，α≥0,控制模型复杂度和拟合程度之间的影响
2、算法
-
训练数据集： D = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , … , ( x N , y N ) } D = \{ (x_1,y_1),(x_2,y_2),\dots,(x_N,y_N)\} D={(x1,y1),(x2,y2),…,(xN,yN)}
-
输入：生成算法产生的整棵子树T，参数 α \alpha α
-
输出：修剪后的子树 T α T_\alpha Tα
-
步骤
1 、 计 算 经 验 熵 ： 计 算 每 个 结 点 的 经 验 熵 。 2 、 递 归 的 向 上 回 缩 : 递 归 的 从 树 的 叶 结 点 向 上 回 缩 ; 设 一 组 叶 结 点 回 缩 到 其 副 结 点 之 前 与 之 后 的 整 棵 树 的 分 别 是 T B 和 T A ; T B 和 T A 对 应 的 损 失 函 数 值 分 别 是 C α ( T B ) 与 C α ( T A ) ， 如 果 C α ( T A ) ≤ C α ( T B ) ; 则 进 行 剪 枝 ， 即 将 父 结 点 变 为 新 的 叶 结 点 。 3 、 回 到 步 骤 2 : 直 至 不 能 继 续 为 止 ， 得 到 损 失 函 数 最 小 的 子 树 。 \begin{aligned} &1、计算经验熵：\\ & \quad\quad计算每个结点的经验熵。\\ &2、递归的向上回缩:\\ &\quad\quad递归的从树的叶结点向上回缩;\\ &\quad\quad设一组叶结点回缩到其副结点之前与之后的整棵树的分别是T_B和T_A;\\ &\quad\quad T_B和T_A对应的损失函数值分别是C_\alpha(T_B)与C_\alpha(T_A)，如果C_\alpha(T_A) \leq C_\alpha(T_B);\\ &\quad\quad则进行剪枝，即将父结点变为新的叶结点。\\ &3、回到步骤2:\\ &\quad\quad直至不能继续为止，得到损失函数最小的子树。\\ \end{aligned} 1、计算经验熵：计算每个结点的经验熵。2、递归的向上回缩:递归的从树的叶结点向上回缩;设一组叶结点回缩到其副结点之前与之后的整棵树的分别是TB和TA;TB和TA对应的损失函数值分别是Cα(TB)与Cα(TA)，如果Cα(TA)≤Cα(TB);则进行剪枝，即将父结点变为新的叶结点。3、回到步骤2:直至不能继续为止，得到损失函数最小的子树。
决策树的具体实现：CART树
CART（classification and regression tree），分类与回归树。
-
其基本假设是：
- 决策树是二叉树
- 内部结点特征的取值为“是”和“否”
- 左分枝取值是“是”
- 右分枝取值是“否”
-
实现：
递归的二分每个特征，将输入空间划分为有限个单元，并在这些单元上确定预测的概率分布，即输入给定的条件下输出的条件概率分布
- 决策树的生成
- 基于训练数据生成尽量大的决策树
- 决策树的剪枝
- 用验证数据集对已生成的决策树进行剪枝并选择最优子树
- 这时用损失函数最小作为剪枝的标准
- 决策树的生成
1、CART最小二乘回归树的生成
在训练数据集所在的输入空间中，递归的将每个区域划分成两个子区域并决定每个子区域上的输出值，构建二叉决策树
（1）策略
基于平方误差最小化准则
（2）算法
-
输入：训练数据集D
-
输出：回归树 f ( x ) f(x) f(x)
-
步骤：
1 、 选 择 最 优 切 分 变 量 j 与 切 分 点 s ， 求 解 : min j , s [ min c 1 ∑ x i ∈ R 1 ( j , s ) ( y i − c 1 ) 2 + min c 2 ∑ x i ∈ R 2 ( j , s ) ( y i − c 2 ) 2 ] 遍 历 变 量 j ， 对 固 定 的 切 分 变 量 j 扫 描 切 分 点 s ， 选 择 上 式 达 到 最 小 值 的 对 ( j , s ) 2 、 用 选 定 的 对 ( j , s ) 划 分 区 域 并 决 定 相 应 的 输 出 值 ： R 1 ( j , s ) = { x ∣ x ( j ) ≤ s } , R 2 ( j ， s ) = { x ∣ x ( j ) > s } c ^ m = 1 N m ∑ x i ∈ R m ( j ， s ) y i ， x ∈ R m , m = 1 , 2 3 、 继 续 对 两 个 子 区 域 调 用 步 骤 1 和 2 ， 直 到 满 足 停 止 条 件 4 、 将 输 入 空 间 划 分 成 M 个 区 域 ， 生 成 决 策 树 : M 个 子 区 域 ： R 1 , R 2 , … , R M 决 策 树 : f ( x ) = ∑ m = 1 M c ^ m I ( x ∈ R m ) \begin{aligned} &1、选择最优切分变量j与切分点s，求解:\\ & \quad\quad\quad\quad \min_{j,s} [\min_{c_1} \sum_{x_i \in R_1(j,s)} (y_i-c_1)^{2} + \min_{c_2} \sum_{x_i \in R_2(j,s)} (y_i - c_2)^{2} ] \\ &遍历变量j，对固定的切分变量j扫描切分点s，选择上式达到最小值的对(j,s)\\ &2、用选定的对(j,s)划分区域并决定相应的输出值：\\ &\quad\quad\quad\quad R_1(j,s) = \{x|x^{(j)} \leq s\},R_2(j，s) = \{x|x^{(j)} > s\}\\ &\quad\quad\quad\quad \hat{c}_m = \frac{1}{N_m} \sum_{x_i \in R_m(j，s)} y_i，x \in R_m,m = 1,2\\ &3、继续对两个子区域调用步骤1和2，直到满足停止条件\\ &4、将输入空间划分成M个区域，生成决策树:\\ &\quad\quad\quad\quad M个子区域：R_1,R_2,\dots,R_M\\ &\quad\quad\quad\quad 决策树:f(x) = \sum_{m=1}^M \hat{c}_m I(x \in R_m) \end{aligned} 1、选择最优切分变量j与切分点s，求解:j,smin[c1minxi∈R1(j,s)∑(yi−c1)2+c2minxi∈R2(j,s)∑(yi−c2)2]遍历变量j，对固定的切分变量j扫描切分点s，选择上式达到最小值的对(j,s)2、用选定的对(j,s)划分区域并决定相应的输出值：R1(j,s)={x∣x(j)≤s},R2(j，s)={x∣x(j)>s}c^m=Nm1xi∈Rm(j，s)∑yi，x∈Rm,m=1,23、继续对两个子区域调用步骤1和2，直到满足停止条件4、将输入空间划分成M个区域，生成决策树:M个子区域：R1,R2,…,RM决策树:f(x)=m=1∑Mc^mI(x∈Rm)
2、CART分类树的生成
在训练数据集所在的输入空间中，递归的将每个区域划分成两个子区域并决定每个子区域上的输出值，构建二叉决策树
（1）策略
基于基尼指数最小化准则选择最优特征，同时决定该特征的最优二值切分点
- 基尼指数
分类问题中，假设有K个类，样本点属于第k类的概率为P_k，概率分布的基尼指数：
G
i
n
i
(
p
)
=
∑
k
=
1
K
p
k
(
1
−
p
k
)
=
1
−
∑
k
=
1
K
p
k
2
Gini(p) = \sum_{k=1}^K p_k (1-p_k) = 1-\sum_{k=1}^K p_k^2
Gini(p)=k=1∑Kpk(1−pk)=1−k=1∑Kpk2
二分类问题中的基尼指数:
G
i
n
i
(
p
)
=
2
p
(
1
−
p
)
Gini(p ) = 2p(1-p)
Gini(p)=2p(1−p)
给定的样本集合D的基尼指数:
G
i
n
i
(
D
)
=
1
−
∑
k
=
1
K
(
∣
C
k
∣
∣
D
∣
)
2
Gini(D) = 1- \sum_{k=1}^K (\frac{|C_k|}{|D|})^2
Gini(D)=1−k=1∑K(∣D∣∣Ck∣)2
C
k
C_k
Ck:D中属于
k
k
k类的样本子集，K是类的个数
给定特征A的条件下D的基尼指数:
G
i
n
i
(
D
,
A
)
=
∣
D
1
∣
∣
D
∣
G
i
n
i
(
D
1
)
+
∣
D
2
∣
∣
D
∣
G
i
n
i
(
D
2
)
D
1
=
{
(
x
,
y
)
∈
D
∣
A
(
x
)
=
a
}
,
D
2
=
D
−
D
1
\begin{aligned} &Gini(D,A) = \frac{|D_1|}{|D|}Gini(D_1) + \frac{|D_2|}{|D|}Gini(D_2)\\ &D_1 = \{(x,y) \in D|A(x) = a\},D_2=D-D_1 \end{aligned}
Gini(D,A)=∣D∣∣D1∣Gini(D1)+∣D∣∣D2∣Gini(D2)D1={(x,y)∈D∣A(x)=a},D2=D−D1
基尼指数值越大，样本集合的不确定性越大，这一点与熵相似
- 基尼指数/熵之半/分类误差率之间的关系
（2）算法
-
输入：训练数据集D，停止的条件
-
输出：CART决策树
-
步骤：
1 、 计 算 现 有 特 征 对 数 据 集 的 基 尼 指 数 G i n i ( D , A ) = ∣ D 1 ∣ ∣ D ∣ G i n i ( D 1 ) + ∣ D 2 ∣ ∣ D ∣ G i n i ( D 2 ) D 1 = { ( x , y ) ∈ D ∣ A ( x ) = a } , D 2 = D − D 1 2 、 选 择 基 尼 指 数 最 小 的 特 征 和 切 分 点 ， 将 特 征 空 间 切 分 成 两 个 子 区 域 / 子 结 点 ， 并 将 对 应 的 训 练 数 据 集 分 配 到 对 应 空 间 。 R 1 ( j , s ) = { x ∣ x ( j ) ≤ s } , R 2 ( j , s ) = { x ∣ x ( j ) > s } c ^ m = 1 N m ∑ x i ∈ R m ( j , s ) y i , x ∈ R m , m = 1 , 2 3 、 对 两 个 子 结 点 递 归 的 调 用 步 骤 1 和 2 ， 直 到 满 足 停 止 条 件 : 子 结 点 中 个 的 样 本 个 数 小 于 指 定 阈 值 样 本 集 的 基 尼 指 数 小 于 指 定 阈 值 4 、 生 成 决 策 树 \begin{aligned} &1、计算现有特征对数据集的基尼指数 \\ &\quad\quad\quad\quad Gini(D,A) = \frac{|D_1|}{|D|}Gini(D_1) + \frac{|D_2|}{|D|}Gini(D_2)\\ &\quad\quad\quad\quad D_1 = \{(x,y) \in D|A(x) = a\},D_2=D-D_1\\ &2、选择基尼指数最小的特征和切分点，将特征空间切分成两个子区域/子结点，\\ &并将对应的训练数据集分配到对应空间。\\ &\quad\quad\quad\quad R_1(j,s) = \{x|x^{(j)} \leq s\},R_2(j,s) = \{x|x^{(j)} > s\}\\ &\quad\quad\quad\quad \hat{c}_m = \frac{1}{N_m} \sum_{x_i \in R_m(j,s)} y_i,x \in R_m,m = 1,2\\ &3、对两个子结点递归的调用步骤1和2，直到满足停止条件:\\ &\quad\quad\quad\quad 子结点中个的样本个数小于指定阈值\\ &\quad\quad\quad\quad 样本集的基尼指数小于指定阈值\\ &4、生成决策树\\ \end{aligned} 1、计算现有特征对数据集的基尼指数Gini(D,A)=∣D∣∣D1∣Gini(D1)+∣D∣∣D2∣Gini(D2)D1={(x,y)∈D∣A(x)=a},D2=D−D12、选择基尼指数最小的特征和切分点，将特征空间切分成两个子区域/子结点，并将对应的训练数据集分配到对应空间。R1(j,s)={x∣x(j)≤s},R2(j,s)={x∣x(j)>s}c^m=Nm1xi∈Rm(j,s)∑yi,x∈Rm,m=1,23、对两个子结点递归的调用步骤1和2，直到满足停止条件:子结点中个的样本个数小于指定阈值样本集的基尼指数小于指定阈值4、生成决策树
3、CART树剪枝
（1）实现
从“完全生长”的决策树的底端剪去一些子树，使决策树变小，从而对未知数据集有更准确的预测。
1
、
获
得
一
个
子
树
序
列
:
从
生
成
算
法
产
生
的
决
策
树
底
端
开
始
不
断
的
剪
枝
直
到
根
结
点
。
根
据
损
失
函
数
计
算
公
式
：
C
α
(
T
)
=
C
(
T
)
+
α
∣
T
∣
计
算
下
列
子
树
的
损
失
函
数
：
1
)
计
算
以
生
成
的
C
A
R
T
树
的
任
意
内
部
结
点
t
为
单
结
点
树
的
损
失
函
数
：
C
α
(
t
)
=
C
(
t
)
+
α
2
)
计
算
以
t
为
根
结
点
的
子
树
的
T
t
的
损
失
函
数
：
C
α
(
T
t
)
=
C
(
T
t
)
+
α
∣
T
t
∣
3
)
计
算
使
损
失
函
C
α
(
T
t
)
=
C
α
(
t
)
数
相
等
的
参
数
α
:
g
(
t
)
=
α
=
C
(
t
)
−
C
(
T
t
)
∣
T
t
∣
−
1
4
)
在
T
0
中
剪
去
g
(
t
)
最
小
的
子
树
T
t
，
将
得
到
的
子
树
记
做
T
1
5
)
同
时
将
最
小
的
g
(
t
)
设
为
α
1
,
T
1
为
[
α
1
,
α
2
）
区
间
上
的
最
优
子
树
6
)
如
此
剪
下
去
，
直
到
得
到
根
结
点
，
在
此
过
程
中
不
断
的
增
大
α
的
值
，
产
生
新
的
区
间
。
2
、
选
择
最
优
子
树
:
通
过
交
叉
验
证
法
在
独
立
的
验
证
数
据
集
上
对
子
树
进
行
测
试
获
得
1
)
利
用
验
证
集
测
试
子
树
T
0
,
T
1
,
…
,
T
n
的
平
方
误
差
或
者
基
尼
指
数
2
)
选
择
平
方
误
差
或
基
尼
指
数
最
小
的
子
树
作
为
最
优
子
树
T
k
3
)
最
优
子
树
T
k
对
应
的
参
数
α
作
为
最
优
决
策
树
参
数
α
k
4
)
基
于
T
k
和
α
k
的
决
策
树
T
α
是
最
优
决
策
树
\begin{aligned} &1、获得一个子树序列:\\ &\quad\quad\quad\quad 从生成算法产生的决策树底端开始不断的剪枝直到根结点。\\ &\quad\quad\quad\quad 根据损失函数计算公式：C_\alpha(T) = C(T) +\alpha|T|计算下列子树的损失函数：\\ &\quad\quad\quad\quad 1)计算以生成的CART树的任意内部结点t为单结点树的损失函数：C_\alpha(t) = C(t) + \alpha\\ &\quad\quad\quad\quad 2)计算以t为根结点的子树的T_t的损失函数：C_\alpha(T_t) = C(T_t) + \alpha|T_t|\\ &\quad\quad\quad\quad 3)计算使损失函C_\alpha(T_t) = C_\alpha(t)数相等的参数\alpha: g(t) = \alpha = \frac{C(t)-C(T_t)}{|T_t| - 1}\\ &\quad\quad\quad\quad 4)在T_0中剪去g(t)最小的子树T_t，将得到的子树记做T_1\\ &\quad\quad\quad\quad 5)同时将最小的g(t)设为\alpha_1,T_1为[\alpha_1,\alpha_2）区间上的最优子树\\ &\quad\quad\quad\quad 6)如此剪下去，直到得到根结点，在此过程中不断的增大\alpha的值，产生新的区间。\\ \\ &2、选择最优子树:\\ &\quad\quad\quad\quad 通过交叉验证法在独立的验证数据集上对子树进行测试获得\\ &\quad\quad\quad\quad 1)利用验证集测试子树T_0,T_1,\dots,T_n的平方误差或者基尼指数\\ &\quad\quad\quad\quad 2)选择平方误差或基尼指数最小的子树作为最优子树T_k\\ &\quad\quad\quad\quad 3)最优子树T_k对应的参数\alpha作为最优决策树参数\alpha_k\\ &\quad\quad\quad\quad 4)基于T_k和\alpha_k的决策树T_\alpha是最优决策树 \end{aligned}
1、获得一个子树序列:从生成算法产生的决策树底端开始不断的剪枝直到根结点。根据损失函数计算公式：Cα(T)=C(T)+α∣T∣计算下列子树的损失函数：1)计算以生成的CART树的任意内部结点t为单结点树的损失函数：Cα(t)=C(t)+α2)计算以t为根结点的子树的Tt的损失函数：Cα(Tt)=C(Tt)+α∣Tt∣3)计算使损失函Cα(Tt)=Cα(t)数相等的参数α:g(t)=α=∣Tt∣−1C(t)−C(Tt)4)在T0中剪去g(t)最小的子树Tt，将得到的子树记做T15)同时将最小的g(t)设为α1,T1为[α1,α2）区间上的最优子树6)如此剪下去，直到得到根结点，在此过程中不断的增大α的值，产生新的区间。2、选择最优子树:通过交叉验证法在独立的验证数据集上对子树进行测试获得1)利用验证集测试子树T0,T1,…,Tn的平方误差或者基尼指数2)选择平方误差或基尼指数最小的子树作为最优子树Tk3)最优子树Tk对应的参数α作为最优决策树参数αk4)基于Tk和αk的决策树Tα是最优决策树
（2）算法
- 输入:CRAT算法生成的决策树 T 0 T_0 T0
- 输出：最优决策树 T α T_\alpha Tα
- 步骤：
1 、 设 k = 0 , T = T 0 2 、 设 α = + ∞ 3 、 自 下 而 上 的 对 各 内 部 结 点 t 计 算 下 列 值 ： g ( t ) = C ( t ) − C ( T t ) ∣ T t ∣ − 1 , 以 t 为 根 结 点 的 子 树 叶 结 点 的 个 数 ： ∣ T t ∣ ， 对 训 练 数 据 的 预 测 误 差 ： C ( T t ) , 参 数 ： α = min ( α , g ( t ) ) 4 、 对 g ( t ) = α 的 内 部 结 点 进 行 剪 枝 ， 并 对 叶 结 点 t 以 多 数 表 决 法 决 定 其 类 ， 得 到 树 T 5 、 设 k = k + 1 , α k = α , T k = T 6 、 如 果 T k 不 是 由 根 结 点 及 两 个 叶 结 点 构 成 的 树 ， 则 回 到 步 骤 2 ， 否 则 令 T k = T n 7 、 采 用 交 叉 验 证 法 在 子 树 序 列 T 0 , T 1 , … , T n 中 选 择 最 优 子 树 T α \begin{aligned} &1、设k=0,T = T_0\\ &2、设\alpha = +\infty\\ &3、自下而上的对各内部结点t计算下列值：\\ &\quad\quad\quad\quad g(t) = \frac{C(t)-C(T_t)}{|T_t| -1},\\ &\quad\quad\quad\quad 以t为根结点的子树叶结点的个数：|T_t|，\\ &\quad\quad\quad\quad 对训练数据的预测误差：C(T_t) ,\\ &\quad\quad\quad\quad 参数：\alpha=\min(\alpha,g(t))\\ &4、对g(t) = \alpha的内部结点进行剪枝，并对叶结点t以多数表决法决定其类，得到树T\\ &5、设k = k+1 ,\alpha_k = \alpha,T_k = T\\ &6、如果T_k不是由根结点及两个叶结点构成的树，则回到步骤2，否则令T_k = T_n\\ &7、采用交叉验证法在子树序列T_0,T_1,\dots,T_n中选择最优子树T_\alpha\\ \end{aligned} 1、设k=0,T=T02、设α=+∞3、自下而上的对各内部结点t计算下列值：g(t)=∣Tt∣−1C(t)−C(Tt),以t为根结点的子树叶结点的个数：∣Tt∣，对训练数据的预测误差：C(Tt),参数：α=min(α,g(t))4、对g(t)=α的内部结点进行剪枝，并对叶结点t以多数表决法决定其类，得到树T5、设k=k+1,αk=α,Tk=T6、如果Tk不是由根结点及两个叶结点构成的树，则回到步骤2，否则令Tk=Tn7、采用交叉验证法在子树序列T0,T1,…,Tn中选择最优子树Tα