1、第六讲决策树简单的决策树模型人工智能发展到一定阶段的时候学者们就发现，这个智能不能靠我们人类完全告诉机器，因为这个世界上的知识和信息都是无止尽的，所以，我们需要让机器学会如何自己学习，于是就产生了机器学习这个研究方向，专门来研究如果让计算机通过数据来学习到知识。今天我们就来介绍一种非常经典的机器学习算法，叫做决策树算法。我们回想一下我们自己的学习过程，我们学一些知识的时候会有很多例题，但我们考试的时候，老师经常会出一些我们没有见过的题型。我们如果好好学习了这些例题的话，就能解出那些没有见过的题目。这是因为我们人类有归纳的能力。中国人把这个能力叫做融会贯通，举一反三等等。所以，我们也希望机器具有
2、这种能力，所以决策树算法就是一种典型的归纳学习。决策树（Decision tree）是一种典型的分类方法，首先对数据进行处理，利用归纳算法生成可读的规则和决策树，然后使用决策树对新数据进行分析。本质上决策树是通过一系列规则对数据进行分类的过程。我们来看一下决策树算法的定义，首先，我们说决策树算法是一种分类方法。这是我们这门课第一次提到分类这个概念，分类问题，这是人工智能里面一个非常重要的概念，我们之后会有一节课专门来讲分类问题的相关知识。在这里就不详细讲了，我们这里强调的是，决策树就是通过归纳，学习到的一种分类的能力。我们来看一个决策树的例子。简单的决策树的模型可以看出这副图很像一棵倒着的树，
3、这个棵树用来分类所有有着X、Y两种属性的数据，可以把这些数据分为三类。我们可以看到类1，类2，类3. 怎么分类的呢，我们从最上面开始，首先判断这个数据的X属性是否等于1，就是最上面那个圆圈，如果不是的话，就直接判断为类1，是的话呢，我们再判断这个数据的Y的大小，我们看到第二个圆圈，它往下有三个分支，说明它不是一个判断是否的问题，而是看Y的数值的范围，所以，如果YA时，分为类1，AYB时分为类2,BYC时，分为类3.这样说有点抽象，我们来看一个非常现实的例子。我们学校里面啊，有这么一类喜欢逃课的学生啊。我们看一下他们的上课的决策树。这个图就非常鲜明了，这些同学每天呆在宿舍里，去不去上课首先判断这
4、节课会不会点名，如果不会点名的话就不去了，非常的现实，如果点名了的话，他们就判断这个寝室到教室的距离，如果寝室到教室的距离在三分钟以下，那么就走着去。如果在需要多过三分钟，就跑着去，如果十分钟还到不了啊，就干脆不去了。这也是他们这个脑海中每天进行的一次分类，他们对于每天关于上不上课的信息主要考虑两个属性，一个是是否点名，一个是能否及时赶到，然后分类的结果，就有三种，一种是不去，一种是跑着去，一种是走着去。南开大一个老师啊，为了惩罚这些学生，在考卷前面加了这么一道选择题。我们还是回到这个决策树算法上来。我们下面来讲讲怎么样才能得到这样一颗决策树呢？就跟我们学习时，需要例题一样，我们需要给电脑一组
5、数据去训练它，大家应该发现了，这个决策树算法对训练数据有一定的要求，这些数据都应该有一些共同的属性并且每一个数据都有一个明确的分类。例如我们有这样一组数据，可以看到这组数据都有这些属性，年龄，收入，学生，信用等级，且都有一个分类，会买电脑，和不会买电脑。这些属性里面有些是数值的，比如年龄，有些是有几种等级，比如收入和信用等级，还有些是判断性质的，比如是否是学生。类别这里是两种，其实可以有很多种不同的分类。在这样一组数据的基础上，我们就能生成一棵决策树。生成决策树有什么好处呢？假如你问老师：“老师你什么时候心情比较好？”我说：“我在以下1000种情况下，心情比较好。第一种，天气晴朗，我头脑清晰，
6、在咖啡厅喝咖啡.第二种.哎哎，我还没说完，你别走.估计没听几条你就走人了，如果老师这样回答：”我只要身体健康，且睡眠充足的时候，就心情比较好。“明显后者比较有智能对不对。我们生成决策树，一方面对数据进行了整理和归纳，也就是说在数据中学习到了有用的规则，另一方面，我们能够通过决策树来对没有见过的数据进行分类。比如这个买电脑这组数据，年龄这个属性有三种情况，收入也有三种情况，学生两种，信用两种，总共啊，有3*3*2*2=36种情况，但我们只有14个数据，所以我们要通过这14个数据来得到一个对这36种情况的一个是否会买电脑的判断。决策树举例在充分了了解了这个决策树的重要性以后啊，我们来讲讲怎么从数据
7、中生成一个决策树。生成决策树有很多种方法，我们介绍一种最典型的，叫做ID3的算法。这个算法早在1975年就被提出来了。为了更加通俗的解释这个算法，我们再举一个例子。这里我们借鉴了一个非常流行的例子。Cs这个游戏大家应该都听说过吧，这是我们读中学的时候非常流行一个游戏，现在有这个穿越火线等都是属于这种系列的，我们统称为第一人称射击游戏。假设你在玩这个Cs的时候，有一个非常难缠的对手，我们管他叫小明吧，你和他玩了四局游戏以后，感觉他很厉害，所以想从他的游戏数据里面来分析他的这个战术行为来学习学习。我们看看有些什么游戏数据。 决策树举例 武器 |子弹数量 |血 |行为 机枪|多| 少 |战斗 机枪
8、|少 | 多 | 逃跑 手枪 |少 | 多 |战斗 手枪 |少 | 少 | 逃跑这是这个小明啊，他在玩CS的时候，什么时候打，什么时候跑的例子。这个数据中包含了3种考虑的因素，分别是武器种类，子弹数量，和血量。分类有两种行为，一种叫战斗，一种叫逃跑。总共有四条数据。我们先看这三个属性，武器种类，玩过的大家都知道，对于我们这个作战能力的影响非常的大，能不能迅速的解决敌人，主要就看你手上的武器，明显这个机枪肯定比手枪要强。然后是这个子弹数量，这也是一个关键因素，子弹充足的时候打起来肯定比较有信心，你枪再强，没子弹也只能先逃跑找个地方躲起来。最后这个血量也是很好理解的，没血了冲上去就是送人头对不对。
9、理解好这三个属性我们就要看看如果说我们通过ID3这个算法来分析这组数据，能够得到一个什么样的结果呢？首先我们先介绍一下信息熵这个概念。信息熵：是关于这组信息的有序度，也可以说是确定性的一个衡量值，我们通常用它来描述某个属性值的数据对于分类的重要性，如果这组数据越有序，那么它的熵就越低，反之就越高。这个有序就是有用，可以说这个属性对于做出分类是否给出了确定性的信息。比如说，你问一个人晚上出不去散步，他说月亮圆他出去，月亮不圆他也出去，那他给出的这两条信息啊，其实就是无序的，也就是非常不确定的。这个时候月亮圆和不圆的熵都很高，如果他说月亮圆他就出去，月亮不圆他就不出去，这两句话就非常明确了，这个时
10、候熵就很低。注意到我们说熵的时候可以是指的属性值，比如说月亮圆的熵很高，也可以是指的属性，比如说月亮这个属性的熵很高，这些都是可以计算出来的。我们觉得这组数据给出的信息非常的明确，比如，我们看到CS游戏那组数据中其实子弹的多少就是一个信息很明确的一组数据，当子弹多的时候这个玩家小明很明确的会去打一打试试看，实在打不过再跑嘛。这个时候我们说子弹多，这个属性值的熵很低，它为0，就是明确得不能再明确了。这个是怎么算出来的呢？它是由下面这个公式计算出来的。这里是一个求和公式，n是分类的个数。我们这里只有两种分类，逃跑和战斗，所以n=2。Sum是这个属性值的数据的总数，我们看到子弹多这个属性啊，只有1条
11、数据，所以sum=1，上面的di啊，是关于这个属性值的数据中在不同的分类中的数量。我们这里只有一条数据它是关于战斗的，所以d战斗=1， d逃跑=0。那么这就是子弹多的熵。那么子弹少的信息熵怎么算呢，同样的，套用公式， n=2，这个时候，由于关于子弹少有三条数据，所以sum=3，这三条数据里面啊，两条是逃跑，一条是战斗，所以d战斗=1， d逃跑=2。那么我们得到子弹多和子弹少的信息熵以后，就可以计算这个子弹这个属性的信息熵。属性的信息熵由一下公式来计算这里sum是所有数据的条数，我们这里都是4，n还是2，这里的di啊，是这个属性值的数据的个数。其实就是一个加权平均值，综合来计算这些属性值的信息熵
12、。所以对于子弹多这个属性值， d=1, 子弹少，d=3所以计算出来这就是这个属性的信息熵，我们同样的，可以计算出武器手枪，武器机枪的信息熵。我们首先来看这个武器的熵然后是这个血量同样我们首先要计算两个属性值的熵，它们分别是到这里，我们将三个属性的熵全都计算完了，我们之前说这个信息熵，表示的是一组数据的混乱程度，所以这个值，应该越小越好。但是我们衡量这三个属性主要用的是一个叫信息增益的参数，这个参数是通过我们整个属性的一个期待信息熵，我们叫它E（S），减去每个属性的信息熵来求得的。增益这个名词一听就感觉得到，这个值应该越大越好。这个期待信息熵怎么算呢?它和求这个属性熵一样，不过它是考虑的行为的比
13、例。比如这组数据中，有两个逃跑行为，两个战斗行为那么它的期待信息熵为如果这组数据啊，的行为全部都是逃跑，或者全部都是战斗，那么这组数据的信息熵就是在这个例子中，我们可以计算出，三个属性的信息增益分别是如果一个属性的信息增益量越大，这个属性作为一棵树的根节点就能使这棵树更简洁，我们就能把这个树写成最后我们来讲，如何根据我们的信息增益计算结果来生成决策树，这个决策树，我们先选择增益最高的作为最上面的根节点，就是我们的子弹数量，可以看到在子弹数量多的情况下，我们就可以直接的做出战斗行为的判断，然后再继续根据增益依次画出决策树。可以看到，决策树的根都是属性，叶子都是行为，连接根与根和叶子的是属性值。这里由于武器类型和血量的增益都是一样，所以可以有两种合理的画法，老师这里给出一种，这个决策树我们可以理解为，有子弹就上，没子弹的话，如果血量多就上，其他情况还是逃吧。如果我们要学习这名玩家的策略，碰到敌人时，就应该优先考虑子弹的数量，如果还有反应时间的话，我们再来考虑武器和血量。当然，我们这里还要讲一点就是，就算不计算信息增益，我们也能够构造出关于这组数据的决策树，比如我们一定要从血量作为根节点开始。
