大家好！ 这是课程3.4。我们来继续学习简单的分类器，
生成决策树的分类器。
我们来看J48。
我们已经多次使用了这个分类器。
让我们来学习它的工作原理。
J48基于从上到下的策略，递归的分治策略。
选择某个属性放置在根节点，为每一个可能的属性值
产生一个分支，将实例分成多个子集，
每个子集对应一个根节点的分支。
然后在每个分支上递归地重复这个过程，我们只能使用到达这个分支的实例，
来为节点选择属性。
当所有实例有相同的分类时，停止。
这里的技巧，或者问题是，如何选择根节点的属性。
我们来看天气数据，可以看到，展望（outlook）被作为根节点。
这里有四种可能性：、展望（outlook), 刮风(windy)、湿度(humidity)和温度(temperature)。
这些是在每个属性分裂的结果。
我们希望看到的是纯分裂，即分裂为纯节点。
我们希望找到一个属性，它的一个节点全是yes，
另一个节点全是no，或许第三个节点
又全是yes。
这能是最好的情况。
我们不想要yes和no的混合，因为混合的节点需要
再次分裂。
可以看到以展望（outlook）分裂会整齐。
其中一个分支有两个yes和三个no，分支overcast上全是yes，
分支rainy上有三个yes和两个no。
我们如何通过量化来确定能产生最纯子节点的属性？
我们需要计算纯度。
目标是得到最小的决策树，而自上而下的树归纳法用到了一些启发式的方法。
最著名的产生纯节点的启发法是以信息论为基础的启发法。
我们这里不讲解信息论，那会是另一门网络课程，
很有趣的一门。
信息论的创始人是Claude Shannon，美国数学家，
12年前逝世。
他是一个了不起的人，
做了很多了不起的事情。
我认为，其中之一是他能在80多岁
边骑独轮车边杂耍。
非常厉害。
他提出了信息论，量化了信息熵，信息熵以bits
来测量信息。
这就是信息熵的公式：所有可能结果的p log p之和。
我们不会详细讲解这个公式。
公式中都是负号，因为当数字小于1，它对数为负数。
而可能性总是小于1。
最终，得到的信息熵会是正数。
我们只看信息增益。
知道一个属性的值会得到多少bits的信息增益？
分裂前的分布的信息熵减去
分裂后的分布的信息熵。
以天气数据为例。
这些是bits的值。
以展望分裂的信息增益是0.247bits。
你也许会觉得奇怪，这些值都是小数。通常
我们会见到1bit、8bit、32bit，但是信息论中你会看到小数的bits。
这些都是小数的bits。
这里我不再细讲。
可以看到，知道windy的值只有0.048bits的信息增益。
湿度（humidity）要好得多，温度（temperature）的又低到了0.029bits 。
我们要选择信息增益最多的属性，
即展望（outlook）属性。
在树顶端，根节点，以展望（outlook）属性分裂。
分裂了展望（outlook）属性后，我们需要看一下展望（outlook）的每一个分支，
它们分别对应着展望（outlook）的三个值，考虑下在每一分支上
的进一步分支。
在第一个分支，我们可以选择以温度（temperature）、刮风（windy）和湿度（humidity）分裂。
我们不会进一步以展望（outlook）分裂，因为我们知道它的
所有实例都是sunny。
我们对其他三个属性做同样的事情。
我们评估这一节点的温度（temperature）、刮风（windy）和湿度（humidity）的信息增益。
选择信息增益最多的属性。
湿度（humidity）的值为0.971bits。
可以看到，如果我们以湿度（humidity）分支，会得到纯节点：一个是3个no，
另一个是2个yes。
当得到这个结果，就不需要再次分裂了。
我们在寻找纯节点。
这就是决策树的原理。
分裂会一直持续到所有节点都是纯节点为止。
打开Weka，试一下名词性的天气数据。
当然，我们之前做过，但现在再来做一次。
不会花太长时间。
J48是数据挖掘算法的常用工具。
这是数据。
我们来选择J48。
树分类器。
运行后，我们得到一个决策树，和我们之前看到的树一样，
首先以outlook分裂：sunny，overcast和rainy。
然后，如果是sunny，以humidity分裂，节点有3个实例。
再以normal分裂，得到3个yes，如此进行下去。
我们可以通过点击菜单中Visualize the tree来看决策树。
这就是决策树。
这是这个节点上yes和no实例的数量。
针对这个决策树，我们做交叉验证。
第11次对整个数据集运行。
使用训练数据集，我们得到这些数据。
实际上，这里是纯节点。
有时你会得到两个数字： 3/2或3/1。
第一个数字表示这个节点的正确的实例数，这里是
实例no的数量。
如果3后面有数字，那表示实例yes的数量，
即这个节点不正确的实例的数量。
但在这个简单的数据集中没有第二个数字。
现在我们知道，J48是自上而下地归纳决策树，
这完全基于信息论，
是非常好的数据挖掘算法。
十年前，我会说这是最好的数据挖掘算法，但是
现在出现了一些更好的算法。
无论如何，J48可信度高，而且最重要的是，
它的决策树简单易懂。
J48的结果非常容易理解。
当应用数据挖掘时，这一点很重要。
你可以用很多标准来选择属性。
这里我们用了信息增益。
在现实中，不同标准的结果区别不会太大。
要在实际中使用这个算法，还需要做一些重要的
修改。
我只是讲解了最基本的法则。
实际上，J48还包含一些较为复杂的算法以保证在不同的情景下
顺利运行。
我们将在下节课将解。
书中章节4.3Divide-and-conquer:Constructing decision trees介绍了
基本的J48。
请做这节课的课后练习。
祝好运！下次见！