CH10 分类|10.2决策树归纳《白话大数据与机器学习》-学习
文章原创,最近更新：2018-06-22
1.什么叫决策树归纳?
2.样本的收集
3.信息增益
4.连续型变量
1.什么叫决策树归纳?
决策树也是一种常用的方式，这种方式几乎是人们可以无师自通的。在平时做决定的时候常常也会有一些原则尺度可以用一棵树来表示，下面举两个小例子。
案例1
假如一个男生安排休息日的活动时思路如图所示。
安排活动的思路
按照优先程度:
- 如果能约会就去看电影，
- 若不能，如果能约到球友就去打球，
- 若不能，如果能约到饭友就去下馆子
- 若不能，如果有好片子就自己看
- 若不能，如果有好玩的游戏就自己玩，
- 若不能，这些都没有那就在家睡觉。
这其实就是一个比较典型的决策树，一个样本，如某一天具体的客观情况，从树根（树是倒着从上往下长的，但也可以画成从下往上、从左往右、从右往左，不影响逻辑的表达）开始一步一步最后落入决策结果。
案例2
再如某大龄女青年在相亲网站进行海选，因为资源太多而自己精力有限，所以肯定是要进行相亲决策的，如图所示。
相亲决策
- 年龄35以上直接拉黑，年龄35以下可以考虑见面。
- 年收入20万元以上的，属于比较有能力的高质量男性，其他条件可以适当放宽。
- 如果学历为硕士以上，身高不够175cm也可以；如果学历为本科及以下，那么身高必须在175cm以上。
- 如果年收入20万元以下，要看是不是“潜力股”，或者颜值是否够高。
- 如果学历为硕士以上，不够180cm身高也可以；如果学历为本科及以下，那么身高必须在180cm以上。
本例同样是根据样本——对该大龄女青年打招呼的男性的情况从树根开始走决策树，最后决定是相亲还是不相亲。当然实际生活中相亲的条件还是很复杂的，尤其还要靠“眼缘”这种超级难量化的东西，哪是这么一张图这两三个条件就全都表达清楚。
决策树归纳和上述过程看上去有些相反，是一个“自底向上”的认识过程。解释如下:
- 第一棵决策树是根据某人长期以来进行休息日行为决策的条件和结果从大量样本中总结而来的，而不是由他自己经过深思熟虑进行总结和口述；
- 第二棵决策树也不是某人自己直接口述而来的，而是她在网站上进行不断地互动和相亲，通过计算机学习归纳总结出来的。
这种归纳总结的过程比从陈述而来的过程可能更为客观和准确——所谓察其言不如观其行。
2.样本的收集
可以想象，相亲网站的运营人员也没有可能去跟她做一个访谈来了解到她对相亲决策过程的描述，怎么办？如果能够拿到她相亲结果的反馈，如跟谁见过面等反馈，就很容易归纳出她的策略了。
假设相亲信息表如表所示。
假设拿到真实的12个样本，由于网站ID这种信息对大龄女青年们做出相亲决策没有什么影响，所以直接忽略，下面来看后面的数据项。
所示的相亲决策树图以年龄与35岁相比作为树根。试想一下，其他的数据项能不能做树根？另外，是不是一定要用大于或小于35岁作为树根分裂的条件呢，不能是34岁或者36岁吗？不是存在一种比较科学或者客观的方法能够找到这个描述最简洁的方式呢？这里需要用到一个重要的概念，即信息增益。
3.信息增益
在介绍信息增益之前先要介绍信息熵，在第6章中提到过信息熵的概念和计算方法。信息熵是用来描述信息混乱程度或者说确定程度的一个值。混乱程度越高，熵越大；混乱程度越低，熵越小。
整个样本集合的熵如下：
这又是一个加和结果，具体表述如下:
- m的数量就是最后分类（决策）的种类，这个例子里m就是2——要么见面要么不见面。
- pi指的实际是这个决策项产生的概率。本例中有两个决策项，一个是N（不相亲），概率为5/12，一个是Y（相亲），概率为7/12，这个概率就是从拿到的完整的相亲记录里得到的结论了。
通过以上数据,熵为
这个熵也有另外一个叫法，即期望信息。从熵的定义来看，不难看出，熵越大说明信息混乱程度越高，做切割时越复杂，要切割若干次才能完成；熵越小说明信息混乱程度越低，做切割时越容易，切割次数也就越少。究竟用哪个字段做树根能够使得消除信息混杂的能力最强。
假设用某一个字段A来划分，在这种划分规则下的熵为
式中具体的表述如下:
- InfoA是指要求的熵
- 右侧从1到v做加和，其中v表示一共划分为多少组，A字段有3个枚举值，表示划分成3组，如例子中“学历”字段就有3个枚举值，那么用“学历”字段划分就是v=3的情况。
- Pj表示这种分组产生的概率，也可以认为是一种权重，即3种学历各自占的比例，这里大专是2/12，本科是5/12，硕士是5/12。
- Info（Aj）是在当前分组状态下的期望信息值。
具体来看看用“学历”字段做分割的情况下，熵有什么变化。把上面的公式展开：
信息增益如下：
这就是用“学历”字段作为根的信息增益。如果希望挑选到的是增益最大的那种方式，那么还需要试试其他字段是否有更大的信息增益。
4.连续型变量
试试用“年龄”字段看是否能取得最大的信息增益，但是“年龄”字段比较麻烦，它是一个连续型的字段，不像上述“学历”字段，就是3个枚举值。这种方法通常是在这个字段上找一个最佳的分裂点，然后一刀切下去，让它的信息增益最大。
在一个连续的字段上可以尝试用如下做法。先把这个字段中的值做一个排序，从小到大。年龄：25、25、28、28、29、30、33、34、35、36、40、46。
这一刀可以在任意两个数字之间切下去，切分点就是这两个数字加和再平均，如25和25之间就是25，30和33之间就是31.5。要用与用“学历”字段分割类似的方法去做切割。如果有n个数字，那么就有n-1种切法，究竟哪种好只能一个一个地试。但是也可以选择中位点，然后一个一个往两边去试。
如果猜测这个字段值大小确实对最终决策有比较大的影响，如确实年龄是一个很重要的问题，大于某个值就直接淘汰了，小于某个值就有很大机会，那么从中位点往两边试，第一次第v个点（中位点），第二次v-1个点，第三次v+1个点，第四次v-2个点，第五次v+2个点，以此类推。每一次切割都会产生一个信息熵，一共v-1个信息熵，当发现某一个点m比它左右两边的m-1和m+1点的信息熵都要小时，就认为找到了这个点。但是这个前提条件太强了，要求确实存在一个分水岭式的分割点。需要老老实实把这n-1种方式都计算一次找到这个信息熵最小的点吧。
最后归纳总结一下构造整棵树时的思路，应该是遵循下面这样的方式：
- 第一步，找到信息增益最大的字段A和信息增益最大的切分点v（不管是连续类型还是枚举类型）。
- 第二步，决定根节点的字段A和切分点v。
- 第三步，把字段A从所有待选的字段列表中拿走，再从第一步开始找。注意这时相当于决策已经走了一步了，如果在根节点上已经分裂成两个分支，那么每一个分支各自又形成一个完整的决策树的选择过程，注意不同点。
不同的是：可选的字段不一样了，因为A字段被去掉了；此外，在这个分支上的样本也比原来少了，因为两个分支分割了整个样本，使得一个部分分支只拥有样本的一部分。
缺点:
缺点是这个归纳出来的树可能会非常复杂，分支和层次极多，这样在可视化上也有问题，在实际用新样本来做分类时也会感觉操作麻烦。
拓外:
还可以用“减枝法”进行树的修剪，有“前减枝”和“后剪枝”两种方法。
- “前剪枝”就是提前终止树的构造，如只用了2个字段，两层树就已经构造完整个树了，保持了树的精简性。
- “后剪枝”就是等树完全构造完，如建模一共使用7个字段，全都用上，这样就形成了一个7层的树，如果一个分支下分类已经比较“纯粹”了，就没必要再通过其他条件分支来进行细化，那么整个枝可以直接减掉变成一个叶。
剪枝这个动作其实是在分类精度上和算法繁琐的程度上做了一个妥协，这种思路几乎贯穿所有的分类算法的始终。
