决策树
引言
王妮梅今年 26 岁，单身，一天她妈妈要给她介绍男朋友，于是妈妈和女儿的一场对话如下：
妈妈：给你介绍一男的
女儿：帅吗？
妈妈：一般。
女儿：性格怎样？
妈妈：不好。
女儿：不见！
妈妈：妮梅！尼妹！
第二天，妈妈又找到一位男士
妈妈：给你介绍一男的
女儿：帅吗？
妈妈：还好。
女儿：收入高不？
妈妈：不高。
女儿：不见！
妈妈：妮梅！尼玛！
妮梅的两次决策过程就是通过性格 (好/坏)、长相 (美/丑) 和收入(高/低) 对和男人是否见面的结果分为两个类别：见/不见。如果把妮梅的决策过程用树来表示，见下图：
通过上图可知妮梅对男朋友的不见的要求是：长相一般性格一般；长相难看收入低。注意：上图底层两个红色叶子框里“不见”字眼，除此之外，上图还有三个绿色像叶子框里的“问号”。问号的意思就是目前还不知道妮梅的决策。假设她妈妈又和她进行三个对话：
妈妈：给你介绍一男的
女儿：帅吗？
妈妈：帅。
女儿：见！
妈妈：噢耶！
妈妈：给你介绍一男的
女儿：帅吗？
妈妈：还好。
女儿：性格好吗？
妈妈：好。
女儿：见！！
妈妈：噢耶！！
妈妈：给你介绍一男的
女儿：帅吗？
妈妈：不帅。
女儿：收入高不？
妈妈：高。
女儿：见！！！
妈妈：噢耶！！！
加上这三段对话，我们可以完整的把妮梅的决策过程用树来表示，见下图：
注意，上图的“问号”全部变成了“见”的字眼，而且树每一个分支都得到了一个明确答案，见或不见！妈妈以后拿着这颗树直接可以比较男方的信息然后介绍给妮梅了，根本无需再问她任何问题，除非妮梅有新的想法。例如，妮梅在得知男方长相难看收入高的情况后，还想在知道对方性格怎样，坏的话不约，好的话才约。在这种情况下，这颗树还要继续生长 (在第二章会考虑此情况)。
现在，我来问你：
你会加减乘除吗？
你会提问题吗？
你会提一些重要的问题吗？
你会问完之后删除繁冗的问题吗？
如果你的回答都是“会”，那么决策树这种找答案 (分类) 的机器学习算法对你实在是太简单了！终于有一篇不用做前戏的帖子了。
本帖目录如下
第一章 - 前戏王
第二章 - 理论皇
2.1 树的定义
2.2 树的数据
2.3 树的指标
2.4 树的生成
第三章 - 实践狼
3.1 多分类树
3.2 阈值选取
3.3 欠过拟合
3.4 树的修剪
3.5 数据缺失
3.6 其它指标
总结和下帖预告
第一章 - 前戏王
无！无！无！无！无！无！无！
第二章 - 理论皇
2.1 树的定义
决策树
决策树 (decision tree) 是一种描述对实例进行分类的树形结构，由结点 (node) 和有向边 (directed edge) 组成。结点有三种类型：
根结点 (root node)：表示树根
内结点 (internal node)：表示特征
叶结点 (leaf node)：表示类
决策树的是从根结点一层一层往叶结点走的，根结点在的位置叫做第 0 层，依次往下推。上一层的结点称为下一层结点的父结点 (parent node)，而下一层的结点称为上一层结点的子结点 (child node)。
用决策树分类，从根结点开始，对样例的某一个特征进行测试，根据测试结果，将样例分配到其子结点。此时，每一个子结点对应着该特征的一个取值。如此递推下去对样例测试再分配，直到达到叶结点而分到其类中。
所有关于决策树的定义和分类流程用下图展示：
上图黑色的多边形是根结点，粉色的菱形是内结点，而绿色红色的叶形是叶结点。注意天蓝色的矩形不是任何结点，他们只是每个内结点中特征的可能值。对照着上面定义和王妮梅那个具体例子来看：
你应该能分清楚各个图形要表达的东西了吧：
黑色多边形根结点
粉色菱形内结点：表示特征长相、性格、类
绿色红色叶结点：表示类，绿色正类“见”，红色反类“不见”
天蓝色矩形：表示特征值
长相：好看、一般、难看
性格：好、坏
收入：高、低
决策树桩
决策树桩 (decision stump) 就是只有一层的决策树。
由上图可知妮梅这棵决策树包含三个树桩。
2.2 树的数据
上面的决策树只有一个基本的树形，再从妮梅妈妈和妮梅五段对话的提炼出来五种分类结果 (你们可以从根数到叶子看是不是只有五条路径)。现在假如有 40 个像妮梅这样的女孩，她们各自的妈妈都有一个男士要介绍，问各自的女儿对长相、性格和收入之类的要求，得到女儿的回答，把数据交给情感大师斯蒂文来统计并生成相对应的决策树 (具体生成方法见下一章)。这 40 个女孩的数据和决策树如下：
数据
从上表里看出数据总共有 40 行，每一个数据有四列，前三列长相、性格和收入是特征，而最后一列“见吗？”是类别。为了便于看出，正类 22 个“是”用绿色高亮标示，反类 18 个“否”用红色高亮标示。
决策树
单从数据的类上看有 22 个是 18 个否，如果不做任何决策，正分类比为 22:18，因此在根结点附近记录 [22 18]。
斯蒂文一开始用的是长相特征按照好看、一般和难看对树进行分裂，当长相为
好看 (只看第一列是好看的行)，正分类比为 9:0，因此在内结点“好看”附近记录 [9 0]
一般 (只看第一列是一般的行)，正分类比为 9:4，因此在内结点“一般”附近记录 [9 4]
难看 (只看第一列是难看的行)，正分类比为 4:14，因此在内结点“难看”附近记录 [4 14]
当长相为一般时，斯蒂文用的性格特征按照好和坏对树进行分类，当性格为
好 (在第一列是一般时，只看第二列是好的行)，正分类比为 9:0，因此在内结点“好”附近记录 [9 0]
坏 (在第一列是一般时，只看第二列是坏的行)，正分类比为 0:4，因此在内结点“坏”附近记录 [0 4]
当长相为难看时，斯蒂文用的收入特征按照高和低对树进行分类，当收入为
高 (在第一列是难看时，只看第二列是高的行)，正分类比为 4:5，因此在内结点“高”附近记录 [4 5]
低 (在第一列是难看时，只看第二列是低的行)，正分类比为 0:9，因此在内结点“低”附近记录 [0 9]
接下来当收入为高时，按照上述同样的方法类推
决策树中每个结点对正类反类计数的过程，类似于计算条件概率，因为随着树越来越深，你知道的条件就越来越多，比如在知道对方长相一般和性格好的条件下见不见对方男士？但是在现在我们没有计算条件概率，姑且把这个过程叫做条件计数吧。
2.3 树的指标
后面将介绍树的分裂会遵循一些度量指标来选取最合适的特征来分裂，最常见的指标有分类误差率、信息增益、信息增益比和基尼指数等。本章现将最简单的分类误差率，下章再将其他指标。在介绍分类误差率之前需要了解多数法则。
多数规则
多数规则 (majority rules)，也成为多数投票规则 (majority voting rules)，是指一项决策须经半数以上人赞成，才能获得通过的一种投票规则。多数规则的实质，是少数服从多数。由于一致同意规则很高的决策成本，使得多数规则成本在实践中最为普遍运用的投票规则。对于 2.2 小节的图
如果在根结点树根就开始进行多数规则，正反类比为 22:18，很明显决策为正类，意思就是情感专家斯蒂文根据数据为所有 40 个女孩的建议是“见”男方！
往下细分，如果在内结点长相进行多数规则，当长相
好看，正反类比为 9:0，决策为正类，见男方
一般，正反类比为 9:4，决策为正类，见男方
难看，正反类比为 4:14，决策为反类，不见男方
再往下细分，按照上述多数规则可得到所有结点上的决策
按照多数规则得到的决策树图如下：
分类误差率
分类误差率 (misclassification error, ME) 就是分类器错误分类的样本数与总样本数之比。在决策树应用中，在一个结点，通常会计算分裂前和分裂后的分类误差率，如果前者比后者高，那么应该分裂，反之不应该分裂。
下图计算了树桩 1 在分裂前和分裂后的分类误差率：
在第零层树，根据多数规则，根结点的预测的是 40 正类，因为真实样例总共有 22 正类 18 反类，那么有 18 个预测错误，因此分类误差为 18/40 等于 0.45。
对着数据表，在第一层树，根据多数规则，当长相
好看，预测正类，真实样例总共有 9 正类 0 反类，有 0 个预测错误
一般，预测正类，真实样例总共有 9 正类 4 反类，有 4 个预测错误
难看，预测反类，真实样例总共有 4 正类 14 反类，有 4 个预测错误
在三个特征值下加起来一共有 8 个预测错误，因此分类误差为 8/40 等于 0.2。
2.3 树的生成
构造决策树的关键步骤是分裂属性。所谓分裂属性就是在某个结点处按照某一特征属性的不同值构造不同的分支，其目标是让各个分裂子集尽可能地“纯”。尽可能“纯”就是尽量让一个分裂子集中待分类项属于同一类别。
第一步：从树根开始，决定一个特征开始分裂树，用的度量标准是分类误差率。
具体过程如上图，在本例中只有三个特征，长相、性格和收入。以此用它们来分裂树，根据上面数据表里的数据，记下每个特征的特征值 (比如性格特征对应着好和坏，收入特征对应着高和低) 对应的正类 (见) 和反类 (不见) 的个数，再利用多数规则计算出分类误差率。由上述结果可知，按长相分时的分类误差率为 0.2，最低，因此一开始从树根应该用“长相”这个特征来分裂。此时的决策树长下图展示这个样子。
第二步：分裂之后检查每个特征值对应的分支，如果某个分支里所有样例都属于一类，那么停止分裂；如果不属于则继续分裂。
按照上图发现当长相“好看”时，所有决策都是“见” (9比0)，因此对于这个分支无需再继续分裂；但是当长相“一般”或“难看”时，决策结果还有分歧，还可以继续分裂。用什么特征来分裂，还是按着第一步的过程，选一个分类误差最小的但没有用过的特征 (这点很重要，防止一直用重复特征会使得树太过于复杂) 来分裂。省去具体计算 (有兴趣的同学可以自己计算)，分裂完后的决策树长下图展示这个样子。
第三步：递推生成完整的决策树，遵循以下两条停止条件 (stopping condition)：
条件 1 – 某个分支里所有样例都属于一类，停止分裂
条件 2 – 特征已经用完了，停止分裂
由上图知只有当长相“难看”和收入“高”时，决策结果还有分歧，因此还可以继续分裂，但是只能用这条分支之前没有用过的特征 – 性格 – 来分裂。(注：没有用过的特征不是指着在整颗树里没有用过，而是特指在某条分支上没有用过)
当树不能再继续分裂了，意味着每条分支都有叶结点。在每片叶子上用多数规则给出决策，也就是见或不见。最终决策树长下图展示这个样子。
根据 40 个训练数据生成决策树之后，我们可以用它来做预测。例如，出现了一个新男士，他的个人条件是长相难看，收入高，性格好，那么从根往叶将上面决策树穿越一遍 (橙色高亮)，得出的结论是见！！！如下图所示
第三章 - 实践狼
3.1 多分类树
上一章的例子是个二分类决策树，女孩只有两种决策，见男士，不见男士。假如一位男士长得丑收入低性格暴力，那么女孩绝逼不见！那么这是可能有三种决策：见、不见、绝逼不见去死吧！这个例子可能不是很适当，再看一个例子，银行根据借贷人信息决定这笔贷款是否应该借出去。这时银行可能会对借贷人划分三种类别：安全、危险、垃圾！这个时候怎么玩转决策树呢？处理方式一模一样，除了两类变多类，下面还是用女孩见男士的例子来解释，数据如下：
和二类决策树分裂规则一样，在一开始选一个有最小分类误差率的特征来分裂，这个特征还是“长相”，如下图所示：
3.4 阈值选取
本例中特征“收入”的值是离散值，高或低，这概念有点模糊，多高算高多低算低啊？现实中，特别是在问卷调查中，收入这栏填的都是10万、20万、50万这种连续值。如下图所示：
假设我们对收入的出现的每个连续值来分裂，得到的树会长成下面这样子。
这样划分有两个很严重的问题：
绝大多数结点只包含一个数据，要么正类要么反类，这是典型的过拟合现象
注意中间两个结点显示着矛盾的决策，见 24 万收入的男士，却不见 24.5 万收入的男士
当连续值划分的太细，我们对决策树的预测真的没什么信心。一个改进方法是找一个阈值 (threshold) 来进行分裂，比如对上例，25 万是个不错的分界点，小于 25 万归结成收入低，大于等于 25 万归结成收入高。如下图所示：
现在你可能会问，为什么选择 25 万当做阈值？问得好，下面就来给出阈值的算法。如下图，将所有收入连续值按升序标注在轴上，同时也记下每个收入值对应的类别，见或不见。显然，阈值选在图中 A 点和 B 点中间任一点，得到的分类误差率都一样！
因此我们的做法是
对每两个相邻的点，算出它们的中间值 (N 个点就有 N-1 个中间值)
把每个中间值当成阈值，计算出相对应的分类误差率
找到最小的分类误差率，并将其对应的中间值当成阈值
如下图所示：
3.4 欠过拟合
和所有机器学习方法一样，决策树也可能发生欠拟合或过拟合的现象。如下例，黑色加号代表正类，桃红色减号代表反类。
其中 x[1] 和 x[2] 是两个连续值特征。下图展示了一层树和两层树的全貌。
和离散特征不同，连续特征可以在一条分支上多次选择不同的阈值来进行分裂。你可以想象不停的细分连续值，那么决策树可以完美分类任何训练集，但是也严重的过拟合了训练数据而降低了其泛化能力。
下图类比了决策树和对率分类模型，其中
一层决策树和一次多项式对率分类欠拟合了数据，训练集上的误差都比较大
十层决策树和六次多项式对率分类过拟合了数据，训练集上的误差为零，但模型泛化能力弱
三层决策树和二次多项式对率分类好拟合了数据，模型棒棒哒
对于欠拟合模型，我们增加模型复杂度 (增加决策树的层数，增加对率模型多项式次数)；对于过拟合模型，我们降低模型复杂度 (修剪决策树，正规化对率模型)。下小节就细谈如何修剪树来防止它过拟合。
3.4 树的修剪
修剪 (pruning) 是决策树防止“过拟合”的主要手段。在决策树生成过程中，为了尽可能的正确分类训练集，结点划分将不断重复而可能造成分支过多。这样的后果就是这棵树把训练集学的太好了，从而把训练集所有特点当作所有数据具有的一般性质，这样模型的泛化 (generalization) 能力就会下降。因此可通过主动去掉一些分支来降低过拟合的风险，可以用两种思路：
未雨绸缪的思路：从根到叶的方向，在树生成中，预修剪 (pre-pruning) 分支以防树变得复杂
亡羊补牢的思路：从叶到根的方法，在树生成后，后修剪 (post-pruning) 分支致使树变得简单
预修剪
预修剪是指在决策树生成过程中，对每个结点在划分前先进行估计，一旦遇到以下三个提前停止条件 (early stopping condition)，就应该将当前结点标记为叶结点。
提前停止条件 1：当树的深度超过一个特定值 (最大树深)
回顾上一节的“十层决策树”，当你无限次用不同的阈值里分裂节点，得到的决策树可以完美分类所训练集，但是对新的测试集分类性能一定很差因为过拟合了。为了防止过拟合，我们会限制树的深度。做法是用验证集 (当数据很多时) 和交叉验证集 (当数据不多时)。具体细节见模型选择和评估一贴。
用验证集选择最大树的深度流程如下：
按 80% 和 20% 划分训练集和验证集
用训练集构建不同深度的树，并在验证集上计算分类误差率
选一个分类误差率最小的的对应的深度作为最大树深
用交叉验证集 (5折) 选择最大树的深度流程如下：
将整个数据集大概平均分成 5 份
对于每一个模型 (不同深度的树)，从第一份到最后一份，将选中那份数据集当作验证集，剩余的四份一起当作训练集
用训练集构建不同深度的树
在验证集上计算分类误差率
求出 5 个分类误差率的均值作为交叉分类误差率。
选一个交叉分类误差率最小的的对应的深度作为最大树深
提前停止条件 2：当继续分裂不能减小分类误差率
假设从树根用特征长相分裂后的树桩如下，当长相难看时，有 5 个正类和 16 反类，很显然还可以继续分裂下去。接下来我们计算不划分、用性格划分和用收入划分后的分类误差率，发现都是 0.24 (见下图)。既然不分裂和继续分裂的分类误差率都一样，那么我们选择简单的 (简单点，简单点，修剪的方式简单点)，应该提早停止分裂而直接作决策。
有的时候，当你简化树的决心更大时，你可能会选择一个 r 值，比如 5%，进而规定"只要继续分裂生成的分类误差率没有减少 r ，那么停止分裂”。
提前停止条件 3：当内结点包含的数据个数小于一个特定值
当结点里数据太少，我们就会提早停止分裂，如下图所示，当长相一般只对应这 3 个数据，这时候应该直接作决策而不是再往下分裂。
具体这个特定值要根据数据总数决定，通常实践中选 10 到 100 之间任何一个数。
后修剪
预修剪使得决策树的很多分支都没有展开，不仅降低了过拟合的风险，还减少了决策树的训练时间。但另一方面，有些分支过早停止但其实后续分裂区有可能导致性能显著提高。这样看来，预修剪有可能给决策树带来欠拟合的风险，这个时候后修剪的作用就来了。
后修剪的核心理念是先训练好决策树，即便复杂，再从叶往根开始简化，如果一个树桩可以用一个叶结点替代，那就替代而简化树！在后修剪过程中，我们需要平衡模型的分类能力和树的复杂度，前者可用误差分类率来量化，而后者可用树叶的个数来量化。其代价函数为
C(T)= ME(T) + λ∙L(T)
其中
T = 当前的树
C(T) = 代价函数
ME(T) = 分类误差率
L(T) = 叶结点的个数
λ = 参数
当 λ 等于 0 时，后修剪就只比较分类误差率而不考虑叶结点的个数；当 λ 等于无穷时，后修剪最终生成单单一个树根，因为多一个叶结点的代价太大了。下图描述了后修剪的过程
假设参数 λ 是 0.3，从最低层树桩开始 (上图红色椭圆框)，如果不修剪，整棵树有 6 片叶子，C(T) 为 0.25+ 6 ∙ 0.3 等于 0.43；如果修剪 (用一片叶子替代这个树桩)，那么修后的树 (见下图) 有 5 片叶子，C(T) 为 0.26+ 5 ∙ 0.3 等于 0.41。修剪后的 C(T) 小于修剪前的 C(T)，那么这个树桩应该要被修剪掉！注意，虽然修剪后的分类误差率大了一些，但是叶结点也少了，权衡这两点还是应该修剪。
接下来，对剩下三个内结点“性格”，“收入”和“长相”重复以上修剪过程。
后修剪决策树通常比预修剪决策树保留了更多的分支，因此前者的欠拟合风险很小，而泛化性能往往优于后者。但后修剪过程是在生成完整决策树之后进行的，并且要从叶往根对书中所有内结点逐一检测，因此其时间开销比预修剪决策树要大得多。
3.5 数据缺失
目前决策是的生成和修剪都是基于完整的数据。但是在实际情况中数据缺失是一种很普遍的现象，可能训练数据某一个特征值缺失，也可能测试数据的某一个特征值缺失。下图显示着一个缺失部分数据的训练集 (两个性格特征下和一个收入特征下的数据缺失)
下图显示着一个缺失收入特征值的测试数据 (当我们要预测是否见下一个男士时，如果该男士没有提供他的收入，怎么办)
一般来说，缺失数据的处理方式有三种：
删除 (delete)
推算 (impute)
归类 (categorize)
删除
删除数据是最简单也是最无脑的一种做法，其方式有两种，删除行 (数据点)，或者删除列 (特征)。如下图所示：
删除数据的优缺点有：
优点
操作简单
可以用在任何模型比如决策树、线性回归和对率分类等等
缺点
删除的数据可能包含着重要信息
不知道删除行好还是删除列好
对缺失数据的测试集没用
推算
根据特征值是分类型 (categorical) 变量或数值类 (numerical) 变量，推算的方式有两种：
用众数来推算分类型缺失数据
用平均数来推算数值型缺失数据
特征“性格”的特征值是个分类型变量，因此计数未缺失数据得到 2 个好和 7 个坏，根据众数原则应该将缺失数据用“坏”来填充。特征“收入”的特征值是个数值型变量，根据平均数原则算出未缺失数据的均值 20.4 万来填充。
推算数据的优缺点有：
优点
操作简单
可以用在任何模型比如决策树、线性回归和对率分类等等
对缺失数据的测试集有用，运用同样的规则 (众数分类型变量，平均数数值型变量)
缺点
可能会造成系统型误差
对于系统性误差有个真实案例，在华盛顿的银行里申请贷款，根据当地法律，申请人是不允许填年龄的。如果把整个美国申请人资料合在一起，很明显发现所有来自华盛顿的数据缺失年龄那一栏。假如按照“平均数数值型变量”这个规则算出均值是 41 岁，那么把所有华盛顿申请者的年龄填为 41 岁是极其不合理的。
归类
归类的核心思想是把“缺失 (unknown)”也当作是一种特征值，如下图：
当缺失收入特征值时，一开始我们无法利用决策树来做出决策。现在只需把“收入缺失”和“收入低”归纳成同一类，就很容易做出决策 – 不见！
同理，我们可以把“缺失”分类到每个特征上，一方它们都有可能有缺失的特征值。现在我们的决策树长成以下的样子。
上图一个有趣的地方时在把“缺失”归类给特征性格时，有时把它和“好”放一起，有时把它和“坏”放一起。接下来就来解释其原因。换一个问题问：是否有一个规则来决定“缺失”放在哪一特征值？有！和上一章用的规则一样，选用最小分类误差率，具体过程见下图。
归类数据的优缺点有：
优点
比起删除/推算数据，预测更准
对缺失数据的训练集和测试集都有用
缺点
需要修改算法，虽然对决策树不难
3.6 其它指标
上一章用的分类误差率指标来分裂特征，其它常见的还有信息增益、信息增益比和基尼指数。了解它们之前需要知道熵和条件熵的概念。
熵
在信息论 (information theory) 中，熵 (entropy) 是表示随机变量 Y 不确定性的度量。假设 Y 是一个离散随机变量，其概率分布为
P(yi) = pi, i = 1,2, …, n
那么 Y 的熵定义为
在上式中，如果某个 pi 等于0，定义 0ln0 = 0。有定义可知，熵只跟 Y 的分布有关因为 H 是个概率的函数，而和 Y 的值无关。当随机变量 Y 只取两个值时 (概率为 p 和 1-p)，其熵为
H(Y) = – plnp – (1-p)ln(1-p)
熵 H 随概率 p 变化的函数如下图所示，当 p 等于 0 或 1 时，H 为 0，说明随机变量 Y 完全是确定的，当 p 等于 0.5 时，H 为 ln2 取值最大，Y 不确定性最大。
条件熵
假设离散随机变量 X 和 Y 的联合概率分布为
P(yi, xj) = pij, i = 1,2, …, n, j = 1,2,…,m
条件熵 (conditional entropy)，用符号 H(Y|X) 表示在已知随机变量 X 的条件下随机变量 Y 的不确定性。那么 Y (类别) 关于 X (特征) 的条件熵定义为
其中
pj = P(xj)
m 是特征值的个数
n 是类别的个数
信息增益
信息增益 (information gain) 表示在得知特征 X 的信息之后的对类 Y 的信息的不确定性减少的程度。数学定义为
G(Y|X)= H(Y) – H(Y|X)
决策树应用信息增益准则来选择特征。给定类别 Y 和特征 X1, X2, …, Xm
熵 H(Y) 表示对 Y 进行分类的不确定性
条件熵 H(Y|Xj) 表示在特征 Xj 给定的条件下对 Y 进行分类的不确定性
那么他们的差就是信息增益，表示由于特征 Xj 而使得 Y 的分类的不确定性减少的程度。显然，对于 Y 来说，信息增益依赖于特征，不同的特征往往具有不同的信息增益，而信息增益大的特征具有更强的分类能力。
信息增益比
信息增益的大小是相对于数据集而言的，对不同训练集，这个指标没有一致的意义。在熵大时 (对于特征值数目多的特征 Xj) 信息增益大，反之，熵小时(对于特征值数目少的特征 Xj) 信息增益小。类比绝对值和相对值的关系，引进一个概念叫做信息增益比。
信息增益比 (information gain ratio) 就是信息增益和熵的比值，起到了将信息增益标准化的作用。数学定义为
在本章决策树例子中，Y 只有“是/否”两类。因此 n = 2。而上面熵和条件熵公式可以简写为
对着数据表，40 样例有 22 正类 18 反类，因此概率为 22/40 和 18/40，熵为
当长相
好看，有 9 个样例，占总数比 9/40。在这 9 个中，有 9 正类 0 反类，因此条件概率为 9/9 和 0/9
一般，有 13 个样例，占总数比 13/40。在这 13 个中，有 9 正类 4 反类，因此条件概率为 9/13 和 4/13
难看，有 18 个样例，占总数比 18/40。在这 18 个中，有 4 正类 14 反类，因此条件概率为 4/18 和 14/18
因此在得知特征“长相”后的条件熵、信息增益和信息增益比分别为
所有以上计算过程更直观的解释在下图
基尼指数
分类问题中，假设中 K 个类别，样例属于第 k 类得概率为 pk, 则概率分布的基尼指数 (Gini index) 定义为
对于二分类问题，若第一类的概率为 p，那么另一类概率为 1-p，套用上面公式，基尼指数可简化成
Gini(p)= 2p(1-p)
树的其它种类
在上一章讨论的决策树的分裂标准用的是分类误差率度量指标，业界用的更多的三种度量指标是
信息增益，对应的树或算法叫做第 3 代迭代二叉树 (Iterative Dichotomiser 3, ID3)
信息增益比，对应的树或算法叫做第 4.5 代分类树 (Classifier 4.5, C4.5)
基尼指数，对应的树或算法叫做回归分类树 (Classification and Regression Tree, CART)
ID3, C4.5 和 CART 这些树名或者算法名字听起来很高大上，实际上树的生成方法和上章将的一样，都是从根结点开始递推生成，只不过用信息增益、信息增益比和基尼指数不断的选取局部最优的特征。
总结和下帖预告
决策树的生成过程非常直观，容易被人理解，它不依赖领域知识，而仅仅使用一种选择分裂准则来递推运用。该准则是将数据“最好”的划分成不同的类。这个“最好”通常用以下四种度量指标 (quality metric) 来量化
分类误差率
信息增益
信息增益比
基尼指数
有时候林子 (树) 大了，什么鸟都有，决策树太过于茂密 (复杂) 时一定要修剪防止过拟合模型。这个过程决策树的修剪过程，它包括预修剪和后修剪，前者是“未雨绸缪以防复杂”，而后者是“亡羊补牢进而简化”。
即便这样，决策树还不是完美的，比如一开始“最好”的分裂生成的树可能没有一开始不是“最好”分裂生成的树性能好。因此大多情况下，我们不会在每个树层上过于专注在“最好”分裂，而且将树多样化 (并行多样化，顺序多样化) 在集合起来。
下一贴讲集成学习 (ensemble learning)，主要通过构建并结合多个学习器来完成学习任务，在保证准确度的同时也提升了模型防止过拟合的能力。两大类集成学习方法是：
自助聚合法 (bootstrap aggregation, bagging)
提升法 (boosting)
以决策树为知识背景，我们会详细介绍并行类的 bagging 和顺序类的 boosting 家族里最常见的具体方法，分别是随机森林 (random forest) 和渐步提升 (adaptive boost, adaBoost)。Stay Tuned!