目录
- 评选算法
- 信息增益( ID3 算法选用的评估标准)
- 信息增益率( C4.5 算法选用的评估标准)
- 基尼系数( CART 算法选用的评估标准)
- 基尼增益
- 基尼增益率
评选算法
决策树学习的关键在于:如何选择最优划分属性。一般而言,随着划分过程的不断进行,我们自然希望决策树各分支结点所包含的样本尽可能属于同一类别,即结点的 “纯度” (purity) 越来越高。下面介绍几类较为主流的评选算法。
信息增益( ID3 算法选用的评估标准)
信息增益 𝑔(𝐷, 𝑋) :表示某特征 𝑋 使得数据集 𝐷 的不确定性减少程度,定义为集合 𝐷 的熵与在给定特征 𝑋 的条件下 𝐷 的条件熵 𝐻(𝐷 | 𝑋) 之差,即
g ( D , X ) = H ( D ) − H ( D ∣ X ) g(D,X)=H(D)−H(D|X) g(D,X)=H(D)−H(D∣X)
从该式可以看出,信息增益表达了样本数据在被分类后的专一性。因此,它可以作为选择当前最优特征的一个指标。
根据前面的计算结果,可知集合 𝐷 的熵 𝐻(𝐷) = 0.6931 ,特征 “天气”、“温度”、“风速”、“湿度” 的条件熵分别为 𝐻(D | X天气) = 0.3961 、𝐻(D | X温度) = 0.6931、𝐻(D | X风速) = 0.5983、𝐻(D | X湿度) = 0.6315。根据这些数据,可以算出全部特征在被用于分类时,各自的信息增益:
g ( D ∣ X 天气 ) = H ( D ) − H ( D ∣ X 天气 ) = 0.6931 − 0.3961 = 0.2970 g ( D ∣ X 温度 ) = H ( D ) − H ( D ∣ X 温度 ) = 0.6931 − 0.6931 = 0.0000 g ( D ∣ X 风速 ) = H ( D ) − H ( D ∣ X 风速 ) = 0.6931 − 0.5983 = 0.0948 g ( D ∣ X 湿度 ) = H ( D ) − H ( D ∣ X 湿度 ) = 0.6931 − 0.6315 = 0.0616 g(D|X天气)=H(D)−H(D∣X天气)=0.6931−0.3961=0.2970 \\ g(D|X温度)=H(D)−H(D∣X温度)=0.6931−0.6931=0.0000\\ g(D|X风速)=H(D)−H(D∣X风速)=0.6931−0.5983=0.0948\\ g(D|X湿度)=H(D)−H(D∣X湿度)=0.6931−0.6315=0.0616 g(D∣X天气)=H(D)−H(D∣X天气)=0.6931−0.3961=0.2970g(D∣X温度)=H(D)−H(D∣X温度)=0.6931−0.6931=0.0000g(D∣X风速)=H(D)−H(D∣X风速)=0.6931−0.5983=0.0948g(D∣X湿度)=H(D)−H(D∣X湿度)=0.6931−0.6315=0.0616
上面各特征求得的信息增益中,“天气” 特征对应的是最大的。也就是说,如果将 “天气” 作为决策树的第一个划分特征,系统整体的熵值将降低 0.297,是所有备选特征中效果最好的。因此,根据 “学校举办运动会的历史数据” 构建决策树时,根节点最好取 “天气” 特征。
接下来,在 “晴天” 中的数据将按上面的流程继续执行,直到构建好一棵完整的决策树(或达到指定条件)。不过此时,备选特征只剩下 “温度”、“风速” 和 “湿度” 3 项(往后,每当决策树的深度加 1 时,都会减少一个)。
信息增益率( C4.5 算法选用的评估标准)
以信息增益作为划分数据集的特征时,其偏向于选择取值较多的特征。比如,当在学校举办运动会的历史数据中加入一个新特征 “编号” 时,该特征将成为最优特征。因为给定 “编号” 就一定知道那天是否举行过运动会,因此 “编号” 的信息增益很高。
但实际我们知道,“编号” 对于类别的划分并没有实际意义。故此,引入信息增益率。
信息增益率 𝑔𝑅(𝐷, 𝑋) 定义为其信息增益 𝑔(𝐷, 𝑋) 与数据集 𝐷 在特征 𝑋 上值的熵 𝐻𝑋(𝐷) 之比,即:
g R ( D , X ) = g ( D , X ) H X ( D ) g_R(D,X)=\frac{g(D,X)}{H_X(D)} gR(D,X)=HX(D)g(D,X)
其中 H x ( D ) = − ∑ i = 1 k ∣ D i ∣ ∣ D ∣ log ∣ D i ∣ ∣ D ∣ Hx(D)=-\sum_{i=1}^k{\frac{|D_i|}{|D|}\text{log}\frac{|D_i|}{|D|}} Hx(D)=−∑i=1k∣D∣∣Di∣log∣D∣∣Di∣,k是特征 X 的取值类别个数。
从上式可以看出,信息增益率考虑了特征本身的熵(此时,当某特征取值类别较多时, g R ( D , X ) g_R(D, X) gR(D,X)式中的分母也会增大),从而降低了 “偏向取值较多的特征” 这一影响。根据该式,可得到基于各特征划分的信息增益率如下:
按天气划分:
按温度划分:
按风速划分:
按湿度划分:
从上面的结果可以看出,信息增益率能明显降低取值较多的特征偏好现象,从而更合理地评估各特征在划分数据集时取得的效果。因此,信息增益率是现阶段用得较多的一种算法。
基尼系数( CART 算法选用的评估标准)
从前面的讨论不难看出,无论是 ID3 还是 C4.5 ,都是基于信息论的熵模型出发而得,均涉及了大量对数运算。能不能简化模型同时又不至于完全丢失熵模型的优点呢?分类回归树(Classification and Regression Tree,CART)便是答案,它通过使用基尼系数来代替信息增益率,从而避免复杂的对数运算。基尼系数代表了模型的不纯度,基尼系数越小,则不纯度越低,特征越好。注:这一点和信息增益(率)恰好相反。
在分类问题中,假设有 k 个类别,且第 k 个类别的概率为 p k p_k pk,则基尼系数为:
G i n i ( p ) = ∑ i = 1 k p i ( 1 − p i ) = 1 − ∑ i = 1 k p i 2 Gini(p) =\sum_{i=1}^k{p_i(1-p_i)}=1-\sum_{i=1}^k{p_i^2} Gini(p)=i=1∑kpi(1−pi)=1−i=1∑kpi2
对于给定数据集D,假设有k个类别,且第k个类别的数量为 C k C_k Ck,则该数据集的基尼系数为:
G i n i ( D ) = ∑ i = 1 k ∣ C i ∣ ∣ D ∣ ( 1 − ∣ C i ∣ ∣ D ∣ ) = 1 − ∑ i = 1 k ( ∣ C i ∣ ∣ D ∣ ) 2 Gini(D)=\sum_{i=1}^k{\frac{|C_i|}{|D|}(1-\frac{|C_i|}{|D|})} =1-\sum_{i=1}^k{(\frac{|C_i|}{|D|})^2} Gini(D)=i=1∑k∣D∣∣Ci∣(1−∣D∣∣Ci∣)=1−i=1∑k(∣D∣∣Ci∣)2
从上式可以看出,基尼系数表征了样本集合里一个随机样本分类错误的平均概率。例如:
如果数据集D根据特征X的取值将其划分为 D 1 , D 2 , … , D m {D_1 , D_2 , … , D_m} D1,D2,…,Dm ,则在特征D的条件下,划分后的集合D的基尼系数为:
G i n i ( D , X ) = ∑ i = 1 k ∣ C i ∣ ∣ D ∣ G i n i ( D i ) Gini(D,X)=\sum_{i=1}^k{\frac{|C_i|}{|D|}}Gini(D_i) Gini(D,X)=i=1∑k∣D∣∣Ci∣Gini(Di)
由于基尼系数Gini(D)表示集合D的不确定性,则基尼系数Gini(D,X)表示 “基于指定特征X进行划分后,集合D的不确定性”。
该值越大,就表示数据集D的不确定性越大,也就说明以该特征进行划分越容易分乱。基于前面各特征对数据集的划分,可得到其对应的基尼系数为:
基尼增益
同信息增益一样,如果将数据集D的基尼系数减去数据集D根据特征X进行划分后得到的基尼系数就得到基尼增益(系数):
G ( D , X ) = G i n i ( D ) − G i n i ( D , X ) G(D,X) =Gini(D) -Gini(D,X) G(D,X)=Gini(D)−Gini(D,X)
显然,采用越好的特征进行划分,得到的基尼增益也越大。基于前面各特征对数据集的划分,可得到其对应的基尼增益。
步骤一:先算出初始数据集合D的基尼系数。
G ( D ) = 1 − ∑ i = 1 2 ( ∣ C i ∣ ∣ D ∣ ) 2 = 1 − ( ( 7 14 ) 2 + ( 7 14 ) 2 ) = 0.5000 G(D) =1-\sum_{i=1}^2{(\frac{|C_i|}{|D|})^2}=1-((\frac{7}{14})^2 +(\frac{7}{14})^2)=0.5000 G(D)=1−i=1∑2(∣D∣∣Ci∣)2=1−((147)2+(147)2)=0.5000
步骤二:计算基尼增益
可见,基尼增益在处理诸如 “编号” 这一类特征时,仍然会认为其是最优特征(此时,可采取类似信息增益率的方式,选用基尼增益率 )。但对常规特征而言,基尼增益的合理性还是较优的。
基尼增益率
基尼增益率 G R ( D , X ) G_R(D,X) GR(D,X)定义为其尼基增益G(D,X)与数据集D在特征X上的取值个数之比,即:
G R ( D , X ) = G ( D , X ) ∣ D X ∣ G_R(D,X) =\frac{G(D,X)}{|D_X|} GR(D,X)=∣DX∣G(D,X)
容易看出,基尼增益率考虑了特征本身的基尼系数(此时,当某特征取值类别较多时, G R ( D , X ) G_R(D,X) GR(D,X)式中的分母也会增大),从而降低了 “偏向取值较多的特征” 这一影响。根据该式,可得到基于各特征划分的基尼增益率如下:
从上面的结果可以看出,基尼增益率能明显降低取值较多的特征偏好现象,从而更合理地评估各特征在划分数据集时取得的效果。