建设银行的网站是多少钱,龙江人社 pp,aspcms自适应网站,wordpress 显示图片啊决策树#xff08;理论#xff09; 目录一、何为决策树1、决策树的组成2、决策树的构建二、熵1、熵的作用2、熵的定义3、熵的计算4、条件熵的引入5、条件熵的计算三、划分选择1、信息增益#xff08; ID3 算法选用的评估标准#xff09;2、信息增益率#xff08; C4.5 算法…决策树理论 目录一、何为决策树1、决策树的组成2、决策树的构建二、熵1、熵的作用2、熵的定义3、熵的计算4、条件熵的引入5、条件熵的计算三、划分选择1、信息增益 ID3 算法选用的评估标准2、信息增益率 C4.5 算法选用的评估标准3、基尼系数 CART 算法选用的评估标准4、基尼增益5、基尼增益率四、决策树中的连续值处理五、决策树中的预剪枝处理正则化1、限制决策树的深度2、限制决策树中叶子结点的个数3、限制决策树中叶子结点包含的样本个数4、限制决策树的最低信息增益六、决策树中的后剪枝处理七、实战部分一、何为决策树 决策树Decision Tree是一种分类和回归方法是基于各种情况发生的所需条件构成决策树以实现期望最大化的一种图解法。由于这种决策分支画成图形很像一棵树的枝干故称决策树。它的运行机制非常通俗易懂因此被誉为机器学习中最“友好”的算法。下面通过一个简单的例子来阐述它的执行流程。假设根据大量数据含 3 个指标天气、温度、风速构建了一棵“可预测学校会不会举办运动会”的决策树如右图所示。
接下来当我们拿到某个数据时就能做出对应预测 在对任意数据进行预测时都需要从决策树的根结点开始一步步走到叶子结点执行决策的过程。如对上表中的第一条数据 [ 阴天寒冷强 ] 首先从根结点出发判断“天气”取值而该数据的“天气”属性取值为“阴天”从决策树可知此时可直接输出决策结果为“举行”。这时无论其他属性取值为什么都不需要再执行任何决策类似于“短路”现象。 1、决策树的组成
决策树由结点和有向边组成。结点有两种类型内部结点圆和叶结点矩形。其中内部结点表示一个特征属性叶结点表示一个类别。而有向边则对应其所属内部结点的可选项属性的取值范围。 在用决策树进行分类时首先从根结点出发对实例在该结点的对应属性进行测试接着会根据测试结果将实例分配到其子结点然后在子结点继续执行这一流程如此递归地对实例进行测试并分配直至到达叶结点最终该实例将被分类到叶结点所指示的结果中。
在决策树中若把每个内部结点视为一个条件每对结点之间的有向边视为一个选项则从根结点到叶结点的每一条路径都可以看做是一个规则而叶结点则对应着在指定规则下的结论。这样的规则具有互斥性和完备性从根结点到叶结点的每一条路径代表了一类实例并且这个实例只能在这条路径上。从这个角度来看决策树相当于是一个 if-then 的规则集合因此它具 有非常好的可解释性白盒模型这也是为什么说它是机器学习算法中最“友好”的一个原因。 2、决策树的构建
前面介绍了决策树的相关概念接下来讨论如何构建一棵决策树。
决策树的本质是从训练集中归纳出一套分类规则使其尽量符合以下要求
具有较好的泛化能力在 1 的基础上尽量不出现过拟合现象。
注意到一件事当目标数据的特征较多时构建的具有不同规则的决策树也相当庞大成长复杂度为 (!) 。如当仅考虑 5 个特征时就能构建出 5×4×3×2×1120 种。在这么多树中选择哪一棵才能达到最好的分类效果呢实际上这个问题的本质是应该将样本数据的特征按照怎样的顺序添加到一颗决策树的各级结点中这便是构建决策树所需要关注的问题核心。
如在前面的例子中为什么要先对“天气”进行划分然后再是“温度”和“风速”呢下图1可不可以先对“风速”进行划分然后再是“温度”和“天气”呢下图2 一种很直观的思路是如果按照某个特征对数据进行划分时它能最大程度地将原本混乱的结果尽可能划分为几个有序的大类则就应该先以这个特征为决策树中的根结点。接着不断重复这一过程直到整棵决策树被构建完成为止。
基于此引入信息论中的“熵”。 二、熵 1、熵的作用
熵Entropy)是表示随机变量不确定性的度量。说简单点就是物体内部的混乱程度。比如下边的两幅图中从 图1 到 图2 表示了熵增的过程。对于决策树的某个结点而言它在对样本数据进行分类后我们当然希望分类后的结果能使得整个样本集在各自的类别中尽可能有序即希望某个特征在被用于分类后能最大程度地降低样本数据的熵。 现在假设有这样一个待分类数据如下图所示若分类器 1 选择特征 1、分类器 2 选择特征 2 分别为根构建了一棵决策树其效果如下 则根据以上结果可以很直观地认为决策树 2 的分类效果优于决策树 1 。从熵的角度看决策树 2 在通过特征 2 进行分类后整个样本被划分为两个分别有序的类簇而决策树 1 在通过特征 1 进行分类后得到的分类结果依然混乱甚至有熵增的情况因此这个特征在现阶段被认为是无效特征。 2、熵的定义
故此可以这样认为构建决策树的实质是对特征进行层次选择而衡量特征选择的合理性指标则是熵。为便于说明下面先给出熵的定义设 是取值在有限范围内的一个离散随机变量其概率密度为
P(Xxi)pi,i1,2,…,nP(Xx_i)p_i \ , \ i1,2,…,n P(Xxi)pi , i1,2,…,n
下图展示了有关 _pi 与 kkk 的定义其中 是该集合中元素的类别数 则随机变量 的熵定义为
H(X)−∑i1kpilog piH(X)-\sum_{i1}^kp_i \ \text{log} \ p_i H(X)−i1∑kpi log pi
从该式的定义可以看出熵仅仅依赖于 的分布而与其取值无关所以也可以将 的熵记为 () 。 由于随机变量 的概率密度 ∈[0,1]_ ∈ [0, 1]pi∈[0,1] ,因此 log ∈(−∞,0]\text{log}\ _ ∈ (−∞, 0]log pi∈(−∞,0] 。此时若在 log \text{log}\ _log pi 前加上负号就有 −log ∈[0,∞)-\text{log}\ _ ∈ [0,∞)−log pi∈[0,∞) 。所以 H(X)−∑i1kpilog pi∈[0,∞)H(X)-\sum_{i1}^kp_i \ \text{log} \ p_i∈ [0,∞)H(X)−∑i1kpi log pi∈[0,∞) 。当某个集合含有多个类别时此时 较大 的数量过多且整体的 都会因 的过大而普遍较小从而使得 (X) 的值过大。这正好符合“熵值越大事物越混乱”的定义。 3、熵的计算
例如现在有两个集合 { 1,2 } { 1,2,3,4,5,6 } 若以这两个集合为取值空间则可分别计算其熵。 对于集合 先计算其分布列为 于是可得到其熵为
H(XA)−∑i12pilog pi−(12×log1212×log12)−log12log 2≈0.69\begin{aligned} H(X_A) -\sum_{i1}^2p_i \ \text{log} \ p_i \\ -(\frac12× \text{log} \frac12 \frac12× \text{log} \frac12) -\text{log} \frac12 \\ \text{log} \ 2 \\ ≈ 0.69 \\ \end{aligned} H(XA)−i1∑2pi log pi−(21×log2121×log21)−log21log 2≈0.69
对于集合 计算其分布列为 于是可得到其熵为
H(XB)−∑i16pilog pi−(16×log1616×log1616×log1616×log1616×log1616×log16)−log12log 2≈0.69\begin{aligned} H(X_B) -\sum_{i1}^6p_i \ \text{log} \ p_i \\ -(\frac16× \text{log} \frac16 \frac16× \text{log} \frac16 \frac16× \text{log} \frac16 \frac16× \text{log} \frac16 \frac16× \text{log} \frac16 \frac16× \text{log} \frac16) \\ -\text{log} \frac12 \\ \text{log} \ 2 \\ ≈ 0.69 \end{aligned} H(XB)−i1∑6pi log pi−(61×log6161×log6161×log6161×log6161×log6161×log61)−log21log 2≈0.69
结果显示 集合的熵值要低一些从两个集合的内容也能很轻易看出 集合只有两种类别相对稳定而 集合中的类别过多显得混乱。从另一个角度看若视集合 为“抛 1 次硬币的结果”视集合 为“掷 1 次骰子的结果”则显然掷骰子的不确定性比投硬币的不确定性要高。 取极端情况当集合中仅有一类元素时如 { 1,1,1,1,1,1 } 时此时其分布列为 其熵为
H(XB)−∑i11pilog pi−(1×log1)0\begin{aligned} H(X_B) -\sum_{i1}^1p_i \ \text{log} \ p_i \\ -(1 × \text{log} 1) \\ 0 \end{aligned} H(XB)−i1∑1pi log pi−(1×log1)0
取到最小值即表明当前集合状态不混乱非常有序。 4、条件熵的引入
根据熵的定义在构建决策树时我们可采用一种很简单的思路来进行“熵减”每当要选出一个内部结点时考虑样本中的所有“尚未被使用”特征并基于该特征的取值对样本数据进行划分。即有 对于每个特征都可以算出“该特征各项取值对运动会举办与否”的影响而衡量各特征谁最合适的准则即是熵。为此引入条件熵。首先看原始数据集 共14天的熵该数据的标签只有两个“举办”与“不举办”且各占一半故可算出该数据集的初始熵为
H(XB)−∑i12pilog pi−(12×log 1212×log 12)−log 12log2≈0.6931\begin{aligned} H(X_B) -\sum_{i1}^2p_i \ \text{log} \ p_i \\ -(\frac12 ×\text{log} \ \frac12 \frac12 ×\text{log} \ \frac12) \\ -\text{log} \ \frac12 \\ \text{log} 2 \\ ≈ 0.6931 \end{aligned} H(XB)−i1∑2pi log pi−(21×log 2121×log 21)−log 21log2≈0.6931
对于每个特征我们逐个分析先从“天气”开始 天气 “晴天” 时归类集合的熵为 H(XA)−∑i12pilog−(48×log 4848×log 48)−log 12≈0.6931H(X_A)-\sum_{i1}^2p_i \ \text{log}-(\frac48 ×\text{log} \ \frac48 \frac48 ×\text{log} \ \frac48) -\text{log} \ \frac12≈ 0.6931H(XA)−∑i12pi log−(84×log 8484×log 84)−log 21≈0.6931 天气 “阴天” 时归类集合的熵为 H(XB)−∑i12pilog−(1×log 10×log 0)0H(X_B)-\sum_{i1}^2p_i \ \text{log}-(1 ×\text{log} \ 1 0 ×\text{log} \ 0) 0H(XB)−∑i12pi log−(1×log 10×log 0)0天气 “雨天” 时归类集合的熵为 H(XC)−∑i12pilog−(0×log 01×log 1)0H(X_C)-\sum_{i1}^2p_i \ \text{log}-(0 ×\text{log} \ 0 1 ×\text{log} \ 1) 0H(XC)−∑i12pi log−(0×log 01×log 1)0。
从原始数据表可知“天气” 特征取值为 “晴天”、“阴天”、“雨天” 的概率分别为 814\frac{8}{14}148 、314\frac{3}{14}143 、 314\frac{3}{14}143因此若以 “天气” 特征为现阶段的内部节点用于划分的特征则整个系统的熵值为
814H(XA)314H(XB)314H(XC)814×0.6931314×0314×0≈0.3961\begin{aligned} \frac{8}{14} H(X_A) \frac{3}{14} H(X_B) \frac{3}{14} H(X_C) \\ \frac{8}{14} × 0.6931 \frac{3}{14} × 0 \frac{3}{14} × 0 \\ ≈ 0.3961 \end{aligned} 148H(XA)143H(XB)143H(XC)148×0.6931143×0143×0≈0.3961 5、条件熵的计算
在上面的计算中我们将“天气”特征展开以分别求解各取值对应集合的熵。实际上该式的计算正是在求条件熵。条件熵 ( | ) 表示在已知随机变量 的条件下随机变量 的不确定性。它的数学定义是若设随机变量 (, ) 其联合概率密度为
P(Xxi,Yyj)pij,i1,2,…,nP(Xx_i,Yy_j)p_{ij} \ , \ i1,2,…,n P(Xxi,Yyj)pij , i1,2,…,n
则定义条件熵 ( | ) 在给定 的条件下 的条件概率分布对 的数学期望即
(∣)∑i1kpiH(Y∣Xxi)( | )\sum_{i1}^k \ p_i \ H(Y|Xx_i) H(Y∣X)i1∑k pi H(Y∣Xxi)
其中 piP(Xxi),1,2,…,p_iP(Xx_i) \ , \ 1,2, … , piP(Xxi) , i1,2,…,k (表示指定集合中的元素类别) 。 按照这样的定义可算出其余各特征的条件熵分别为
特征取 “温度” 时 H(Y∣X温度)∑i13piH(Y∣Xxi)P(X炎热)H(Y∣X炎热)P(X正常)H(Y∣X正常)P(X寒冷)H(Y∣X寒冷)614×(−(36log 3636log 36))414×(−(24log 2424log 24))414×(−(24log 2424log 24))≈0.6931\begin{aligned} H(Y|X_{温度}) \sum_{i1}^3 \ p_i \ H(Y|Xx_i) \\ P(X {\sf {}} 炎热 {\sf {}})H(Y|X {\sf {}} 炎热 {\sf {}} ) P(X {\sf {}} 正常 {\sf {}})H(Y|X {\sf {}} 正常 {\sf {}} ) P(X {\sf {}} 寒冷 {\sf {}})H(Y|X {\sf {}} 寒冷 {\sf {}} ) \\ \frac{6}{14}× \left( - \left( \frac36 \ \text{log} \ \frac36 \frac36 \ \text{log} \ \frac36 \right) \right) \frac{4}{14}× \left( - \left( \frac24 \ \text{log} \ \frac24 \frac24 \ \text{log} \ \frac24 \right) \right) \frac{4}{14}× \left( - \left( \frac24 \ \text{log} \ \frac24 \frac24 \ \text{log} \ \frac24 \right) \right) \\ ≈ 0.6931 \end{aligned} H(Y∣X温度)i1∑3 pi H(Y∣Xxi)P(X炎热)H(Y∣X炎热)P(X正常)H(Y∣X正常)P(X寒冷)H(Y∣X寒冷)146×(−(63 log 6363 log 63))144×(−(42 log 4242 log 42))144×(−(42 log 4242 log 42))≈0.6931 特征取 “风速” 时 H(Y∣X风速)∑i12piH(Y∣Xxi)P(X强)H(Y∣X强)P(X弱)H(Y∣X弱)714×(−(27log 2757log 57))714×(−(57log 5727log 27))≈0.5983\begin{aligned} H(Y|X_{风速}) \sum_{i1}^2 \ p_i \ H(Y|Xx_i) \\ P(X {\sf {}} 强 {\sf {}})H(Y|X {\sf {}} 强 {\sf {}} ) P(X {\sf {}} 弱 {\sf {}})H(Y|X {\sf {}} 弱 {\sf {}} ) \\ \frac{7}{14}× \left( - \left( \frac27 \ \text{log} \ \frac27 \frac57 \ \text{log} \ \frac57 \right) \right) \frac{7}{14}× \left( - \left( \frac57 \ \text{log} \ \frac57 \frac27 \ \text{log} \ \frac27 \right) \right) \\ ≈ 0.5983 \end{aligned} H(Y∣X风速)i1∑2 pi H(Y∣Xxi)P(X强)H(Y∣X强)P(X弱)H(Y∣X弱)147×(−(72 log 7275 log 75))147×(−(75 log 7572 log 72))≈0.5983 特征取 “湿度” 时 H(Y∣X湿度)∑i13piH(Y∣Xxi)P(X干燥)H(Y∣X干燥)P(X正常)H(Y∣X正常)P(X潮湿)H(Y∣X潮湿)414×(−(24log 2424log 24))614×(−(46log 4626log 26))414×(−(14log 1434log 34))≈0.6315\begin{aligned} H(Y|X_{湿度}) \sum_{i1}^3 \ p_i \ H(Y|Xx_i) \\ P(X {\sf {}} 干燥 {\sf {}})H(Y|X {\sf {}} 干燥 {\sf {}} ) P(X {\sf {}} 正常 {\sf {}})H(Y|X {\sf {}} 正常 {\sf {}} ) P(X {\sf {}} 潮湿 {\sf {}})H(Y|X {\sf {}} 潮湿 {\sf {}} ) \\ \frac{4}{14}× \left( - \left( \frac24 \ \text{log} \ \frac24 \frac24 \ \text{log} \ \frac24 \right) \right) \frac{6}{14}× \left( - \left( \frac46 \ \text{log} \ \frac46 \frac26 \ \text{log} \ \frac26 \right) \right) \frac{4}{14}× \left( - \left( \frac14 \ \text{log} \ \frac14 \frac34 \ \text{log} \ \frac34 \right) \right) \\ ≈ 0.6315 \end{aligned} H(Y∣X湿度)i1∑3 pi H(Y∣Xxi)P(X干燥)H(Y∣X干燥)P(X正常)H(Y∣X正常)P(X潮湿)H(Y∣X潮湿)144×(−(42 log 4242 log 42))146×(−(64 log 6462 log 62))144×(−(41 log 4143 log 43))≈0.6315 三、划分选择
从前面的讨论可以知道决策树学习的关键在于如何选择最优划分属性。一般而言随着划分过程的不断进行我们自然希望决策树各分支结点所包含的样本尽可能属于同一类别即结点的 “纯度” (purity) 越来越高。下面介绍几类较为主流的评选算法。 1、信息增益 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 特征 “天气”、“温度”、“风速”、“湿度” 的条件熵分别为 ( | 天气) 0.3961 、( | 温度) 0.6931、( | 风速) 0.5983、( | 湿度) 0.6315。根据这些数据可以算出全部特征在被用于分类时各自的信息增益
g(∣天气)H(D)−H(D∣X天气)0.6931−0.39610.2970g(∣温度)H(D)−H(D∣X温度)0.6931−0.69310.0000g(∣风速)H(D)−H(D∣X风速)0.6931−0.59830.0948g(∣湿度)H(D)−H(D∣X湿度)0.6931−0.63150.0616g( | _{天气})H(D)-H(D|X_{天气}) 0.6931-0.3961 0.2970 \\ g( | _{温度})H(D)-H(D|X_{温度}) 0.6931-0.6931 0.0000 \\ g( | _{风速})H(D)-H(D|X_{风速}) 0.6931-0.5983 0.0948 \\ g( | _{湿度})H(D)-H(D|X_{湿度}) 0.6931-0.6315 0.0616 g(D∣X天气)H(D)−H(D∣X天气)0.6931−0.39610.2970g(D∣X温度)H(D)−H(D∣X温度)0.6931−0.69310.0000g(D∣X风速)H(D)−H(D∣X风速)0.6931−0.59830.0948g(D∣X湿度)H(D)−H(D∣X湿度)0.6931−0.63150.0616
上面各特征求得的信息增益中“天气” 特征对应的是最大的。也就是说如果将 “天气” 作为决策树的第一个划分特征系统整体的熵值将降低 0.297是所有备选特征中效果最好的。因此根据 “学校举办运动会的历史数据” 构建决策树时根节点最好取 “天气” 特征。
接下来在 “晴天” 中的数据将按上面的流程继续执行直到构建好一棵完整的决策树或达到指定条件。不过此时备选特征只剩下 “温度”、“风速” 和 “湿度” 3 项往后每当决策树的深度加 1 时都会减少一个。 2、信息增益率 C4.5 算法选用的评估标准
以信息增益作为划分数据集的特征时其偏向于选择取值较多的特征。比如当在学校举办运动会的历史数据中加入一个新特征 “编号” 时该特征将成为最优特征。因为给定 “编号” 就一定知道那天是否举行过运动会因此 “编号” 的信息增益很高。 按 “编号” 进行划分得到的决策树 其条件熵
H(D∣X编号)∑i114piH(D∣Xxi)(114×(1×log 1)114×(1×log 1)…114×(1×log 1))(00…0)0\begin{aligned} H(D|X_{编号})\sum_{i1}^{14} \ p_i \ H(D|Xx_i) \\ \left( \frac1{14}×(1× \text{log} \ 1) \frac1{14}×(1× \text{log} \ 1) … \frac1{14}×(1× \text{log} \ 1) \right) \\ (00…0) \\ 0 \end{aligned} H(D∣X编号)i1∑14 pi H(D∣Xxi)(141×(1×log 1)141×(1×log 1)…141×(1×log 1))(00…0)0
信息增益
g(∣编号)H(D)−H(D∣X编号)0.6931−00.6931g( | _{编号})H(D)-H(D|X_{编号}) 0.6931-0 0.6931 g(D∣X编号)H(D)−H(D∣X编号)0.6931−00.6931
但实际我们知道“编号” 对于类别的划分并没有实际意义。故此引入信息增益率。
信息增益率 (, ) 定义为其信息增益 (, ) 与数据集 在特征 上值的熵 () 之比即
gR(D,X)g(D,X)HX(D)g_R(D,X)\frac{g(D,X)}{H_X(D)} gR(D,X)HX(D)g(D,X)
其中 HX(D)−∑i1k∣Di∣∣D∣log∣Di∣∣D∣H_X(D)-\sum_{i1}^k \ \frac{|D_i|}{|D|}\text{log}\frac{|D_i|}{|D|}HX(D)−∑i1k ∣D∣∣Di∣log∣D∣∣Di∣ 是特征 的取值类别个数。从上式可以看出信息增益率考虑了特征本身的熵此时当某特征取值类别较多时(, ) 式中的分母也会增大从而降低了 “偏向取值较多的特征” 这一影响。根据该式可得到基于各特征划分的信息增益率如下
按编号划分H编号(D)−∑i114∣Di∣∣D∣log∣Di∣∣D∣−∑i114114log114log 14≈2.6390gR(D,X编号)g(D,X编号)H编号(D)0.69312.6390≈0.2574按天气划分H天气(D)−∑i13∣Di∣∣D∣log∣Di∣∣D∣−(814log814314log314314log314)≈0.9800gR(D,X天气)g(D,X天气)H天气(D)0.29700.9800≈0.3031按温度划分H温度(D)−∑i13∣Di∣∣D∣log∣Di∣∣D∣−(614log614414log414414log414)≈1.0790gR(D,X温度)g(D,X温度)H温度(D)01.0790≈0按风速划分H风速(D)−∑i12∣Di∣∣D∣log∣Di∣∣D∣−(714log714714log714)≈0.6931gR(D,X风速)g(D,X风速)H风速(D)0.09480.6931≈0.1368按湿度划分H湿度(D)−∑i13∣Di∣∣D∣log∣Di∣∣D∣−(414log414614log614414log414)≈1.0790gR(D,X湿度)g(D,X湿度)H湿度(D)0.06161.0790≈0.0571\begin{aligned} 按编号划分 \\ H_{编号}(D)-\sum_{i1}^{14} \ \frac{|D_i|}{|D|}\text{log}\frac{|D_i|}{|D|}-\sum_{i1}^{14} \ \frac{1}{14}\text{log}\frac{1}{14}\text{log} \ 14≈2.6390 \\ g_R(D,X_{编号})\frac{g(D,X_{编号})}{H_{编号}(D)}\frac{0.6931}{2.6390}≈0.2574 \\ \\ 按天气划分 \\ H_{天气}(D)-\sum_{i1}^{3} \ \frac{|D_i|}{|D|}\text{log}\frac{|D_i|}{|D|}-\left( \frac{8}{14}\text{log}\frac{8}{14} \frac{3}{14}\text{log}\frac{3}{14} \frac{3}{14}\text{log}\frac{3}{14} \right)≈0.9800 \\ g_R(D,X_{天气})\frac{g(D,X_{天气})}{H_{天气}(D)}\frac{0.2970}{0.9800}≈0.3031 \\ \\ 按温度划分 \\ H_{温度}(D)-\sum_{i1}^{3} \ \frac{|D_i|}{|D|}\text{log}\frac{|D_i|}{|D|}-\left( \frac{6}{14}\text{log}\frac{6}{14} \frac{4}{14}\text{log}\frac{4}{14} \frac{4}{14}\text{log}\frac{4}{14} \right)≈1.0790 \\ g_R(D,X_{温度})\frac{g(D,X_{温度})}{H_{温度}(D)}\frac{0}{1.0790}≈0 \\ \\ 按风速划分 \\ H_{风速}(D)-\sum_{i1}^{2} \ \frac{|D_i|}{|D|}\text{log}\frac{|D_i|}{|D|}-\left( \frac{7}{14}\text{log}\frac{7}{14} \frac{7}{14}\text{log}\frac{7}{14} \right)≈0.6931 \\ g_R(D,X_{风速})\frac{g(D,X_{风速})}{H_{风速}(D)}\frac{0.0948}{0.6931 }≈0.1368 \\ \\ 按湿度划分 \\ H_{湿度}(D)-\sum_{i1}^{3} \ \frac{|D_i|}{|D|}\text{log}\frac{|D_i|}{|D|}-\left( \frac{4}{14}\text{log}\frac{4}{14} \frac{6}{14}\text{log}\frac{6}{14} \frac{4}{14}\text{log}\frac{4}{14} \right)≈1.0790 \\ g_R(D,X_{湿度})\frac{g(D,X_{湿度})}{H_{湿度}(D)}\frac{0.0616}{1.0790 }≈0.0571 \\ \end{aligned} 按编号划分H编号(D)−i1∑14 ∣D∣∣Di∣log∣D∣∣Di∣−i1∑14 141log141log 14≈2.6390gR(D,X编号)H编号(D)g(D,X编号)2.63900.6931≈0.2574按天气划分H天气(D)−i1∑3 ∣D∣∣Di∣log∣D∣∣Di∣−(148log148143log143143log143)≈0.9800gR(D,X天气)H天气(D)g(D,X天气)0.98000.2970≈0.3031按温度划分H温度(D)−i1∑3 ∣D∣∣Di∣log∣D∣∣Di∣−(146log146144log144144log144)≈1.0790gR(D,X温度)H温度(D)g(D,X温度)1.07900≈0按风速划分H风速(D)−i1∑2 ∣D∣∣Di∣log∣D∣∣Di∣−(147log147147log147)≈0.6931gR(D,X风速)H风速(D)g(D,X风速)0.69310.0948≈0.1368按湿度划分H湿度(D)−i1∑3 ∣D∣∣Di∣log∣D∣∣Di∣−(144log144146log146144log144)≈1.0790gR(D,X湿度)H湿度(D)g(D,X湿度)1.07900.0616≈0.0571
从上面的结果可以看出信息增益率能明显降低取值较多的特征偏好现象从而更合理地评估各特征在划分数据集时取得的效果。因此信息增益率是现阶段用得较多的一种算法。 3、基尼系数 CART 算法选用的评估标准
从前面的讨论不难看出无论是 ID3 还是 C4.5 都是基于信息论的熵模型出发而得均涉及了大量对数运算。能不能简化模型同时又不至于完全丢失熵模型的优点呢分类回归树Classification and Regression TreeCART便是答案它通过使用基尼系数来代替信息增益率从而避免复杂的对数运算。基尼系数代表了模型的不纯度基尼系数越小则不纯度越低特征越好。注这一点和信息增益率恰好相反。
在分类问题中假设有 个类别且第 个类别的概率为 则基尼系数为
Gini(p)∑i1kpi(1−pi)1−∑i1kpi2Gini(p)\sum_{i1}^k \ p_i(1-p_i)1-\sum_{i1}^kp_i^2 Gini(p)i1∑k pi(1−pi)1−i1∑kpi2
对于给定数据集 假设有 个类别且第 个类别的数量为 则该数据集的基尼系数为
Gini(D)∑i1k∣Ci∣∣D∣(1−∣Ci∣∣D∣)1−∑i1k(∣Ci∣∣D∣)2Gini(D)\sum_{i1}^k \ \frac{|C_i|}{|D|} \left(1-\frac{|C_i|}{|D|} \right)1-\sum_{i1}^k{\left( \frac{|C_i|}{|D|} \right)}^2 Gini(D)i1∑k ∣D∣∣Ci∣(1−∣D∣∣Ci∣)1−i1∑k(∣D∣∣Ci∣)2
从上式可以看出基尼系数表征了样本集合里一个随机样本分类错误的平均概率。例如 如果数据集 根据特征 的取值将其划分为 {1,2, … ,m} 则在特征 的条件下划分后的集合 的基尼系数为
Gini(D,X)∑i1k∣Ci∣∣D∣Gini(Di)Gini(D,X)\sum_{i1}^k \ \frac{|C_i|}{|D|} Gini(D_i) Gini(D,X)i1∑k ∣D∣∣Ci∣Gini(Di)
由于基尼系数 () 表示集合 的不确定性则基尼系数 (, ) 表示 “基于指定特征 进行划分后集合 的不确定性”。该值越大就表示数据集 的不确定性越大也就说明以该特征 进行划分越容易分乱。基于前面各特征对数据集的划分可得到其对应的基尼系数为
Gini(D,X编号)∑i114∣Ci∣∣D∣Gini(Di)114(1−12)114(1−12)…114(1−12)0Gini(D,X天气)∑i13∣Ci∣∣D∣Gini(Di)814(1−((48)2(48)2))314(1−(33)2)314(1−(33)2)≈0.2857Gini(D,X温度)∑i13∣Ci∣∣D∣Gini(Di)614(1−((36)2(36)2))414(1−((24)2(24)2))414(1−((24)2(24)2))≈0.5000Gini(D,X风速)∑i12∣Ci∣∣D∣Gini(Di)714(1−((27)2(57)2))714(1−((57)2(27)2))≈0.4082Gini(D,X湿度)∑i13∣Ci∣∣D∣Gini(Di)414(1−((24)2(24)2))614(1−((46)2(26)2))414(1−((14)2(34)2))≈0.4405\begin{aligned} Gini(D,X_{编号})\sum_{i1}^{14} \ \frac{|C_i|}{|D|} Gini(D_i)\frac{1}{14}(1-1^2)\frac{1}{14}(1-1^2)…\frac{1}{14}(1-1^2)0 \\ Gini(D,X_{天气})\sum_{i1}^{3} \ \frac{|C_i|}{|D|} Gini(D_i)\frac{8}{14} \left(1- \left( \left(\frac48 \right)^2 \left(\frac48 \right)^2 \right) \right) \frac{3}{14} \left( 1- \left( \frac33 \right)^2 \right) \frac{3}{14} \left( 1- \left( \frac33 \right)^2 \right)≈0.2857 \\ Gini(D,X_{温度})\sum_{i1}^{3} \ \frac{|C_i|}{|D|} Gini(D_i)\frac{6}{14} \left(1- \left( \left(\frac36 \right)^2 \left(\frac36 \right)^2 \right) \right) \frac{4}{14} \left(1- \left( \left(\frac24 \right)^2 \left(\frac24 \right)^2 \right) \right) \frac{4}{14} \left(1- \left( \left(\frac24 \right)^2 \left(\frac24 \right)^2 \right) \right)≈0.5000 \\ Gini(D,X_{风速})\sum_{i1}^{2} \ \frac{|C_i|}{|D|} Gini(D_i)\frac{7}{14} \left(1- \left( \left(\frac27 \right)^2 \left(\frac57 \right)^2 \right) \right) \frac{7}{14} \left(1- \left( \left(\frac57 \right)^2 \left(\frac27 \right)^2 \right) \right)≈0.4082 \\ Gini(D,X_{湿度})\sum_{i1}^{3} \ \frac{|C_i|}{|D|} Gini(D_i)\frac{4}{14} \left(1- \left( \left(\frac24 \right)^2 \left(\frac24 \right)^2 \right) \right) \frac{6}{14} \left(1- \left( \left(\frac46 \right)^2 \left(\frac26 \right)^2 \right) \right) \frac{4}{14} \left(1- \left( \left(\frac14 \right)^2 \left(\frac34 \right)^2 \right) \right)≈0.4405 \\ \end{aligned} Gini(D,X编号)i1∑14 ∣D∣∣Ci∣Gini(Di)141(1−12)141(1−12)…141(1−12)0Gini(D,X天气)i1∑3 ∣D∣∣Ci∣Gini(Di)148(1−((84)2(84)2))143(1−(33)2)143(1−(33)2)≈0.2857Gini(D,X温度)i1∑3 ∣D∣∣Ci∣Gini(Di)146(1−((63)2(63)2))144(1−((42)2(42)2))144(1−((42)2(42)2))≈0.5000Gini(D,X风速)i1∑2 ∣D∣∣Ci∣Gini(Di)147(1−((72)2(75)2))147(1−((75)2(72)2))≈0.4082Gini(D,X湿度)i1∑3 ∣D∣∣Ci∣Gini(Di)144(1−((42)2(42)2))146(1−((64)2(62)2))144(1−((41)2(43)2))≈0.4405 4、基尼增益
同信息增益一样如果将数据集 的基尼系数减去数据集 根据特征 进行划分后得到的基尼系数
G(D,X)Gini(D)−Gini(D,X)G(D,X)Gini(D)-Gini(D,X) G(D,X)Gini(D)−Gini(D,X)
就得到基尼增益系数。显然采用越好的特征进行划分得到的基尼增益也越大。基于前面各特征对数据集的划分可得到其对应的基尼增益。
步骤一先算出初始数据集合 D 的基尼系数。
Gini(D)1−∑i12(∣Ci∣∣D∣)21−((714)2(714)2)0.5000Gini(D)1-\sum_{i1}^2 \left( \frac{|C_i|}{|D|} \right)^21- \left( \left(\frac{7}{14} \right)^2 \left(\frac{7}{14} \right)^2 \right)0.5000Gini(D)1−∑i12(∣D∣∣Ci∣)21−((147)2(147)2)0.5000
步骤二计算基尼系数计算基尼增益率。
G(D,X编号)Gini(D)−Gini(D,X编号)0.5000−00.5000G(D,X天气)Gini(D)−Gini(D,X天气)0.5000−0.28570.2143G(D,X温度)Gini(D)−Gini(D,X温度)0.5000−0.50000G(D,X风速)Gini(D)−Gini(D,X风速)0.5000−0.40820.0918G(D,X湿度)Gini(D)−Gini(D,X湿度)0.5000−0.44050.0595\begin{aligned} G(D,X_{编号})Gini(D)-Gini(D,X_{编号})0.5000-00.5000 \\ G(D,X_{天气})Gini(D)-Gini(D,X_{天气})0.5000-0.28570.2143 \\ G(D,X_{温度})Gini(D)-Gini(D,X_{温度})0.5000-0.50000\\ G(D,X_{风速})Gini(D)-Gini(D,X_{风速})0.5000-0.40820.0918 \\ G(D,X_{湿度})Gini(D)-Gini(D,X_{湿度})0.5000-0.44050.0595 \\ \end{aligned} G(D,X编号)Gini(D)−Gini(D,X编号)0.5000−00.5000G(D,X天气)Gini(D)−Gini(D,X天气)0.5000−0.28570.2143G(D,X温度)Gini(D)−Gini(D,X温度)0.5000−0.50000G(D,X风速)Gini(D)−Gini(D,X风速)0.5000−0.40820.0918G(D,X湿度)Gini(D)−Gini(D,X湿度)0.5000−0.44050.0595
可见基尼增益在处理诸如 “编号” 这一类特征时仍然会认为其是最优特征此时可采取类似信息增益率的方式选用基尼增益率 。但对常规特征而言其评估的合理性还是较优的。 5、基尼增益率
基尼增益率 (, ) 定义为其尼基增益 (, ) 与数据集 在特征 上的取值个数之比即
GR(D,X)G(D,X)∣DX∣G_R(D,X)\frac{G(D,X)}{|D_X|} GR(D,X)∣DX∣G(D,X)
容易看出基尼增益率考虑了特征本身的基尼系数此时当某特征取值类别较多时 (, ) 式中的分母也会增大从而降低了 “偏向取值较多的特征” 这一影响。根据该式可得到基于各特征划分的基尼增益率如下
GR(D,X编号)G(D,X编号)∣D编号∣0.500014≈0.0357GR(D,X天气)G(D,X天气)∣D天气∣0.21433≈0.7143GR(D,X温度)G(D,X温度)∣D温度∣030GR(D,X风速)G(D,X风速)∣D风速∣0.09483≈0.0316GR(D,X湿度)G(D,X湿度)∣D湿度∣0.06162≈0.0308\begin{aligned} G_R(D,X_{编号})\frac{G(D,X_{编号})}{|D_{编号}|}\frac{0.5000}{14}≈0.0357 \\ G_R(D,X_{天气})\frac{G(D,X_{天气})}{|D_{天气}|}\frac{0.2143}{3}≈0.7143 \\ G_R(D,X_{温度})\frac{G(D,X_{温度})}{|D_{温度}|}\frac{0}{3}0 \\ G_R(D,X_{风速})\frac{G(D,X_{风速})}{|D_{风速}|}\frac{0.0948}{3}≈0.0316 \\ G_R(D,X_{湿度})\frac{G(D,X_{湿度})}{|D_{湿度}|}\frac{0.0616}{2}≈0.0308 \\ \end{aligned} GR(D,X编号)∣D编号∣G(D,X编号)140.5000≈0.0357GR(D,X天气)∣D天气∣G(D,X天气)30.2143≈0.7143GR(D,X温度)∣D温度∣G(D,X温度)300GR(D,X风速)∣D风速∣G(D,X风速)30.0948≈0.0316GR(D,X湿度)∣D湿度∣G(D,X湿度)20.0616≈0.0308
从上面的结果可以看出基尼增益率能明显降低取值较多的特征偏好现象从而更合理地评估各特征在划分数据集时取得的效果。 四、决策树中的连续值处理
在前面的数据集中各项特征以及标签均为离散型数据但有时处理的数据对象可能会含有连续性数值为了解决这一问题我们可以对数据进行离散化处理。此时可把连续取值的数据值域划分为多个区间并将每个区间视为该特征的一个取值如此就完成了从连续性数据到离散性数据的转变。例如当 “学校举办运动会的历史数据” 为下表时我们可根据这些数据并结合相关知识将温度特征的取值作以下划分 将 “温度” 属性进行分区处理 对于一些尚无明确划分标准的特征如下面是一组无具体含义的数据
626572868996102116118120125169187211218626572868996102116118120125169187211218 626572868996102116118120125169187211218
我们要如何将这些数据进行离散化呢一种较为直接的方式是对原数据进行排序再取任意相邻值的中位点作为划分点例如可以 65 和 72 的中位点φaiai126572268.5\varphi\frac{a_ia_{i1}}{2}\frac{6572}{2}68.5φ2aiai12657268.5进行划分。对数据进行离散化处理是希望划分之后的数据集更加纯净所以这里依然可以用信息熵来作为对划分的度量并选取划分效果最好的点作为划分点。
对于长度为 nnn 的数据其备选中位点有 n−1n-1n−1 个
φ{aiai12,1≤i≤n−1}\varphi\left\{ \frac{a_ia_{i1}}{2} , 1≤i≤n-1 \right\} φ{2aiai1,1≤i≤n−1}
我们需要算出这 n−1n-1n−1 个备选中位点划分出的数据集的信息熵信息熵最小的就是最优划分点。
在评估决策树执行分类或回归任务的效果时其方式也有所不同。对于分类任务可用熵或基尼系数对于回归任务则需要用方差来衡量最终落到某个叶子节点中的数值之间的差异方差越小则说明数据之间的差异越小越应该被归类到一类。注决策树在执行回归任务时其最终反馈的结果应当取某个叶子结点中所有数的均值。 五、决策树中的预剪枝处理正则化
对于决策树而言当你不断向下划分以构建一棵足够大的决策树时直到所有叶子结点熵值均为 0理论上就能将近乎所有数据全部区分开。所以决策树的过拟合风险非常大。为此需要对其进行剪枝处理。
常用的剪枝策略主要有两个
预剪枝构建决策树的同时进行剪枝处理更常用后剪枝构建决策树后再进行剪枝处理。
预剪枝策略可以通过限制树的深度、叶子结点个数、叶子结点含样本数以及信息增量来完成。 1、限制决策树的深度
下图展示了通过限制树的深度以防止决策树出现过拟合风险的情况。 2、限制决策树中叶子结点的个数
下图展示了通过限制决策树中叶子结点的个数以防止决策树出现过拟合风险的情况。 3、限制决策树中叶子结点包含的样本个数
下图展示了通过限制决策树中叶子结点包含的样本个数以防止决策树出现过拟合风险的情况。 4、限制决策树的最低信息增益
下图展示了通过限制决策树中叶子结点包含的样本个数以防止决策树出现过拟合风险的情况。 六、决策树中的后剪枝处理
后剪枝的实现依赖如下衡量标准
LαGini(T)×∣T∣α∣Tleaf∣L_\alphaGini(T)×|T|\alpha|T_{leaf}| LαGini(T)×∣T∣α∣Tleaf∣
其中 () 表示最终损失希望决策树的最终损失越小越好() 表示当前结点的熵或基尼系数 || 表示当前结点包含的数据样本个数 表示当前结点被划分后产生的叶子结点个数显然叶子节点越多损失越大 是由用户指定的偏好系数 越大代表我们对 “划分出更多的子结点” 的惩罚越大即越不偏好于决策树的过分划分因此有助于控制模型过拟合反之 越小表示我们对 “划分出更多的子结点” 的惩罚越小即更希望决策树能在训练集上得到较好的结果而不在意过拟合风险。
下面以一幅图像来展示后剪枝处理的算法原理 七、实战部分
博主正在尽力研究中… END
