练习集 D = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , … , ( x m , y m ) } D = \{(x_1, y_1), (x_2, y_2), \ldots, (x_m, y_m)\} D={(x1,y1),(x2,y2),…,(xm,ym)}
属性集 A = { a 1 , a 2 , … , a d } A = \{a_1, a_2, \ldots, a_d\} A={a1,a2,…,ad}
过程：函数 TreeGenerate ( D , A ) \text{TreeGenerate}(D, A) TreeGenerate(D,A)
天生结点 node \text{node} node；
if D D D 中样本全属于同一类别 C C C then
将 node \text{node} node 标志为 C C C 类叶结点；
return
end if
if A = ∅ A = \emptyset A=∅ OR D D D 中样本在 A A A 上取值相同 then
将 node \text{node} node 标志为叶结点，其类别标志为 D D D 中样本数最多的类；
return
end if
从 A A A 中选择最优划分属性 a ∗ a_{*} a∗；
for a ∗ a_{*} a∗ 的每一个值 a ∗ v a_{*}^v a∗v do
为 node \text{node} node 天生一个分支；
令 D v D_v Dv 表现 D D D 中在 a ∗ a_{*} a∗ 上取值为 a ∗ v a_{*}^v a∗v 的样本子集；
if D v D_v Dv 为空 then
将分支结点标志为叶结点，其类别标志为 D D D 中样本最多的类；
return
else
以 TreeGenerate ( D v , A ∖ { a ∗ } ) \text{TreeGenerate}(D_v, A \setminus \{a_{*}\}) TreeGenerate(Dv,A∖{a∗}) 为分支结点；
end if
end for
输出：以 node \text{node} node 为根结点的一棵决议树
4.2信息增益划分
信息熵 (Entropy)
信息熵是度量样本聚集"纯度"最常用的指标。 定义：
对于样本聚集 D D D，此中第 k k k 类样本所占比例为 p k p_k pk，信息熵定义为：
E n t ( D ) = − ∑ k = 1 ∣ Y ∣ p k log 2 p k Ent(D) = -\sum_{k=1}^{|\mathcal{Y}|} p_k \log_2 p_k Ent(D)=−k=1∑∣Y∣pklog2pk 约定：
若 p k = 0 p_k = 0 pk=0，则 p k log 2 p k = 0 p_k \log_2 p_k = 0 pklog2pk=0
E n t ( D ) Ent(D) Ent(D) 的最小值为 0 0 0（完全纯净），最大值为 log 2 ∣ Y ∣ \log_2 |\mathcal{Y}| log2∣Y∣（完全混乱）
定义：
对于离散属性 a a a 有 V V V 个取值 { a 1 , a 2 , … , a V } \{a^1, a^2, \ldots, a^V\} {a1,a2,…,aV}，其信息增益公式为：
Gain ( D , a ) = Ent ( D ) − ∑ v = 1 V ∣ D v ∣ ∣ D ∣ Ent ( D v ) \text{Gain}(D, a) = \text{Ent}(D) - \sum_{v=1}^V \frac{|D^v|}{|D|} \text{Ent}(D^v) Gain(D,a)=Ent(D)−v=1∑V∣D∣∣Dv∣Ent(Dv) 符号说明：
D v D^v Dv： D D D 中在属性 a a a 上取值为 a v a^v av 的样本子集
Ent ( D ) \text{Ent}(D) Ent(D)：划分前的信息熵（原始数据集纯度）
∑ v = 1 V ∣ D v ∣ ∣ D ∣ Ent ( D v ) \sum_{v=1}^V \frac{|D^v|}{|D|} \text{Ent}(D^v) ∑v=1V∣D∣∣Dv∣Ent(Dv)：划分后的加权信息熵
关键点：
∣ D v ∣ ∣ D ∣ \frac{|D^v|}{|D|} ∣D∣∣Dv∣ 是第 v v v 个分支的权重（样本越多，分支影响越大）
直接接纳信息增益作为属性划分尺度
信息增益越大，表现该属性划分带来的纯度提升越显著
4.3其他属性划分准则
信息增益的缺陷
对多值属性存在偏好：倾向于选择取值数目多的属性（如"编号"这类偶尔义属性）
示例：若将"编号"作为属性，因其唯一性会导致信息增益最大化，但现实无分类意义
增益率 (Gain Ratio)
定义：
Gain_ratio ( D , a ) = Gain ( D , a ) IV ( a ) \text{Gain\_ratio}(D,a) = \frac{\text{Gain}(D,a)}{\text{IV}(a)} Gain_ratio(D,a)=IV(a)Gain(D,a)
此中 固有值 (Intrinsic Value) 为：
IV ( a ) = − ∑ v = 1 V ∣ D v ∣ ∣ D ∣ log 2 ∣ D v ∣ ∣ D ∣ \text{IV}(a) = -\sum_{v=1}^{V} \frac{|D^v|}{|D|} \log_2 \frac{|D^v|}{|D|} IV(a)=−v=1∑V∣D∣∣Dv∣log2∣D∣∣Dv∣ 关键性子：
IV ( a ) \text{IV}(a) IV(a) 反映属性 a a a 的取值分散水平：
取值数目 V V V 越大， IV ( a ) \text{IV}(a) IV(a) 通常越大
作用：通过除以 IV ( a ) \text{IV}(a) IV(a) 处罚多值属性，缓解信息增益的偏好问题
数据集 D D D 的基尼值衡量从 D D D 中随机抽取两个样本其类别标志不同等的概率：
Gini ( D ) = ∑ k = 1 ∣ Y ∣ ∑ k ′ ≠ k p k p k ′ = 1 − ∑ k = 1 ∣ Y ∣ p k 2 \text{Gini}(D) = \sum_{k=1}^{|\mathcal{Y}|} \sum_{k' \neq k} p_k p_{k'} = 1 - \sum_{k=1}^{|\mathcal{Y}|} p_k^2 Gini(D)=k=1∑∣Y∣k′=k∑pkpk′=1−k=1∑∣Y∣pk2 性子：
Gini ( D ) \text{Gini}(D) Gini(D) 越小，数据集 D D D 的纯度越高
属性 a a a 的基尼指数定义为各子集基尼值的加权和：
Gini_index ( D , a ) = ∑ v = 1 V ∣ D v ∣ ∣ D ∣ Gini ( D v ) \text{Gini\_index}(D,a) = \sum_{v=1}^V \frac{|D^v|}{|D|} \text{Gini}(D^v) Gini_index(D,a)=v=1∑V∣D∣∣Dv∣Gini(Dv)
此中 D v D^v Dv 是 D D D 中属性 a a a 取值为 a v a^v av 的子集。 划分准则：
选择使划分后基尼指数最小的属性：
a ∗ = a r g m i n a ∈ A Gini_index ( D , a ) a_* = argmin_{a \in A} \text{Gini\_index}(D,a) a∗=argmina∈AGini_index(D,a)
应用：
CART算法（Classification and Regression Trees）接纳基尼指数作为属性划分尺度
对比信息增益/增益率：基尼指数盘算更高效，且对多值属性敏感度较低
示例：
若属性 a a a 将 D D D 划分为 D 1 D_1 D1 和 D 2 D_2 D2，则基尼指数为：
Gini_index ( D , a ) = ∣ D 1 ∣ ∣ D ∣ Gini ( D 1 ) + ∣ D 2 ∣ ∣ D ∣ Gini ( D 2 ) \text{Gini\_index}(D,a) = \frac{|D_1|}{|D|} \text{Gini}(D_1) + \frac{|D_2|}{|D|} \text{Gini}(D_2) Gini_index(D,a)=∣D∣∣D1∣Gini(D1)+∣D∣∣D2∣Gini(D2)
决议树泛化性能的关键因素
