1
00:00:17,199 --> 00:00:24,199
大家好！ 这是课程3.4。我们来继续学习简单的分类器，

2
00:00:24,230 --> 00:00:29,219
生成决策树的分类器。

3
00:00:29,219 --> 00:00:33,269
我们来看J48。

4
00:00:33,269 --> 00:00:35,920
我们已经多次使用了这个分类器。

5
00:00:35,920 --> 00:00:38,399
让我们来学习它的工作原理。

6
00:00:38,399 --> 00:00:45,399
J48基于从上到下的策略，递归的分治策略。

7
00:00:46,479 --> 00:00:51,680
选择某个属性放置在根节点，为每一个可能的属性值

8
00:00:51,680 --> 00:00:57,960
产生一个分支，将实例分成多个子集，

9
00:00:57,960 --> 00:01:01,589
每个子集对应一个根节点的分支。

10
00:01:01,589 --> 00:01:06,210
然后在每个分支上递归地重复这个过程，我们只能使用到达这个分支的实例，

11
00:01:06,210 --> 00:01:12,180
来为节点选择属性。

12
00:01:12,180 --> 00:01:19,180
当所有实例有相同的分类时，停止。

13
00:01:19,439 --> 00:01:26,439
这里的技巧，或者问题是，如何选择根节点的属性。

14
00:01:29,490 --> 00:01:36,119
我们来看天气数据，可以看到，展望（outlook）被作为根节点。

15
00:01:37,140 --> 00:01:42,899
这里有四种可能性：、展望（outlook), 刮风(windy)、湿度(humidity)和温度(temperature)。

16
00:01:42,899 --> 00:01:46,819
这些是在每个属性分裂的结果。

17
00:01:48,000 --> 00:01:53,819
我们希望看到的是纯分裂，即分裂为纯节点。

18
00:01:54,709 --> 00:02:00,709
我们希望找到一个属性，它的一个节点全是yes，

19
00:02:00,709 --> 00:02:04,749
另一个节点全是no，或许第三个节点

20
00:02:04,749 --> 00:02:05,779
又全是yes。

21
00:02:05,779 --> 00:02:06,990
这能是最好的情况。

22
00:02:06,990 --> 00:02:12,340
我们不想要yes和no的混合，因为混合的节点需要

23
00:02:12,340 --> 00:02:14,740
再次分裂。

24
00:02:14,740 --> 00:02:17,040
可以看到以展望（outlook）分裂会整齐。

25
00:02:17,040 --> 00:02:24,040
其中一个分支有两个yes和三个no，分支overcast上全是yes，

26
00:02:24,209 --> 00:02:29,950
分支rainy上有三个yes和两个no。

27
00:02:29,950 --> 00:02:35,120
我们如何通过量化来确定能产生最纯子节点的属性？

28
00:02:35,120 --> 00:02:42,120
我们需要计算纯度。

29
00:02:42,269 --> 00:02:51,110
目标是得到最小的决策树，而自上而下的树归纳法用到了一些启发式的方法。

30
00:02:51,110 --> 00:02:58,110
最著名的产生纯节点的启发法是以信息论为基础的启发法。

31
00:03:00,269 --> 00:03:04,030
我们这里不讲解信息论，那会是另一门网络课程，

32
00:03:04,030 --> 00:03:06,939
很有趣的一门。

33
00:03:06,939 --> 00:03:12,909
信息论的创始人是Claude Shannon，美国数学家，

34
00:03:12,909 --> 00:03:14,880
12年前逝世。

35
00:03:14,880 --> 00:03:16,439
他是一个了不起的人，

36
00:03:16,439 --> 00:03:17,680
做了很多了不起的事情。

37
00:03:17,680 --> 00:03:23,000
我认为，其中之一是他能在80多岁

38
00:03:23,000 --> 00:03:26,799
边骑独轮车边杂耍。

39
00:03:26,799 --> 00:03:29,829
非常厉害。

40
00:03:29,829 --> 00:03:35,519
他提出了信息论，量化了信息熵，信息熵以bits

41
00:03:35,519 --> 00:03:37,019
来测量信息。

42
00:03:37,019 --> 00:03:44,019
这就是信息熵的公式：所有可能结果的p log p之和。

43
00:03:44,659 --> 00:03:47,299
我们不会详细讲解这个公式。

44
00:03:47,299 --> 00:03:51,299
公式中都是负号，因为当数字小于1，它对数为负数。

45
00:03:51,299 --> 00:03:53,930
而可能性总是小于1。

46
00:03:53,930 --> 00:03:56,709
最终，得到的信息熵会是正数。

47
00:03:57,460 --> 00:03:59,939
我们只看信息增益。

48
00:03:59,939 --> 00:04:07,170
知道一个属性的值会得到多少bits的信息增益？

49
00:04:07,170 --> 00:04:12,180
分裂前的分布的信息熵减去

50
00:04:12,180 --> 00:04:14,359
分裂后的分布的信息熵。

51
00:04:14,359 --> 00:04:17,480
以天气数据为例。

52
00:04:18,440 --> 00:04:19,620
这些是bits的值。

53
00:04:19,620 --> 00:04:24,150
以展望分裂的信息增益是0.247bits。

54
00:04:24,150 --> 00:04:28,750
你也许会觉得奇怪，这些值都是小数。通常

55
00:04:28,750 --> 00:04:34,690
我们会见到1bit、8bit、32bit，但是信息论中你会看到小数的bits。

56
00:04:34,690 --> 00:04:36,330
这些都是小数的bits。

57
00:04:36,330 --> 00:04:38,820
这里我不再细讲。

58
00:04:38,820 --> 00:04:46,310
可以看到，知道windy的值只有0.048bits的信息增益。

59
00:04:46,310 --> 00:04:53,310
湿度（humidity）要好得多，温度（temperature）的又低到了0.029bits 。

60
00:04:53,310 --> 00:04:58,630
我们要选择信息增益最多的属性，

61
00:04:58,630 --> 00:05:00,460
即展望（outlook）属性。

62
00:05:00,460 --> 00:05:05,610
在树顶端，根节点，以展望（outlook）属性分裂。

63
00:05:05,610 --> 00:05:11,000
分裂了展望（outlook）属性后，我们需要看一下展望（outlook）的每一个分支，

64
00:05:11,000 --> 00:05:16,250
它们分别对应着展望（outlook）的三个值，考虑下在每一分支上

65
00:05:16,250 --> 00:05:17,600
的进一步分支。

66
00:05:17,600 --> 00:05:22,710
在第一个分支，我们可以选择以温度（temperature）、刮风（windy）和湿度（humidity）分裂。

67
00:05:22,710 --> 00:05:25,980
我们不会进一步以展望（outlook）分裂，因为我们知道它的

68
00:05:25,980 --> 00:05:30,020
所有实例都是sunny。

69
00:05:30,020 --> 00:05:32,950
我们对其他三个属性做同样的事情。

70
00:05:32,950 --> 00:05:38,750
我们评估这一节点的温度（temperature）、刮风（windy）和湿度（humidity）的信息增益。

71
00:05:38,750 --> 00:05:39,640
选择信息增益最多的属性。

72
00:05:39,640 --> 00:05:44,230
湿度（humidity）的值为0.971bits。

73
00:05:44,230 --> 00:05:50,710
可以看到，如果我们以湿度（humidity）分支，会得到纯节点：一个是3个no，

74
00:05:50,710 --> 00:05:52,010
另一个是2个yes。

75
00:05:52,010 --> 00:05:54,120
当得到这个结果，就不需要再次分裂了。

76
00:05:54,850 --> 00:06:00,800
我们在寻找纯节点。

77
00:06:00,800 --> 00:06:01,520
这就是决策树的原理。

78
00:06:01,520 --> 00:06:05,990
分裂会一直持续到所有节点都是纯节点为止。

79
00:06:05,990 --> 00:06:11,860
打开Weka，试一下名词性的天气数据。

80
00:06:11,860 --> 00:06:15,520
当然，我们之前做过，但现在再来做一次。

81
00:06:15,520 --> 00:06:17,650
不会花太长时间。

82
00:06:18,140 --> 00:06:22,640
J48是数据挖掘算法的常用工具。

83
00:06:22,640 --> 00:06:23,910
这是数据。

84
00:06:23,910 --> 00:06:26,430
我们来选择J48。

85
00:06:26,430 --> 00:06:28,500
树分类器。

86
00:06:29,840 --> 00:06:38,110
运行后，我们得到一个决策树，和我们之前看到的树一样，

87
00:06:38,110 --> 00:06:42,150
首先以outlook分裂：sunny，overcast和rainy。

88
00:06:42,150 --> 00:06:47,360
然后，如果是sunny，以humidity分裂，节点有3个实例。

89
00:06:47,360 --> 00:06:51,610
再以normal分裂，得到3个yes，如此进行下去。

90
00:06:51,610 --> 00:06:58,610
我们可以通过点击菜单中Visualize the tree来看决策树。

91
00:06:58,990 --> 00:07:03,060
这就是决策树。

92
00:07:03,060 --> 00:07:08,140
这是这个节点上yes和no实例的数量。

93
00:07:08,140 --> 00:07:12,900
针对这个决策树，我们做交叉验证。

94
00:07:12,900 --> 00:07:16,250
第11次对整个数据集运行。

95
00:07:16,250 --> 00:07:19,750
使用训练数据集，我们得到这些数据。

96
00:07:19,750 --> 00:07:24,520
实际上，这里是纯节点。

97
00:07:24,520 --> 00:07:29,950
有时你会得到两个数字： 3/2或3/1。

98
00:07:29,950 --> 00:07:35,670
第一个数字表示这个节点的正确的实例数，这里是

99
00:07:35,670 --> 00:07:36,980
实例no的数量。

100
00:07:36,980 --> 00:07:41,090
如果3后面有数字，那表示实例yes的数量，

101
00:07:41,090 --> 00:07:43,460
即这个节点不正确的实例的数量。

102
00:07:43,460 --> 00:07:47,850
但在这个简单的数据集中没有第二个数字。

103
00:07:50,740 --> 00:07:55,560
现在我们知道，J48是自上而下地归纳决策树，

104
00:07:56,490 --> 00:07:59,360
这完全基于信息论，

105
00:07:59,360 --> 00:08:02,230
是非常好的数据挖掘算法。

106
00:08:02,230 --> 00:08:08,590
十年前，我会说这是最好的数据挖掘算法，但是

107
00:08:08,590 --> 00:08:11,280
现在出现了一些更好的算法。

108
00:08:11,280 --> 00:08:18,200
无论如何，J48可信度高，而且最重要的是，

109
00:08:18,200 --> 00:08:20,980
它的决策树简单易懂。

110
00:08:20,980 --> 00:08:23,850
J48的结果非常容易理解。

111
00:08:23,850 --> 00:08:28,090
当应用数据挖掘时，这一点很重要。

112
00:08:28,090 --> 00:08:31,430
你可以用很多标准来选择属性。

113
00:08:31,430 --> 00:08:33,459
这里我们用了信息增益。

114
00:08:33,459 --> 00:08:38,000
在现实中，不同标准的结果区别不会太大。

115
00:08:38,000 --> 00:08:42,269
要在实际中使用这个算法，还需要做一些重要的

116
00:08:42,269 --> 00:08:42,820
修改。

117
00:08:42,820 --> 00:08:45,310
我只是讲解了最基本的法则。

118
00:08:45,310 --> 00:08:51,590
实际上，J48还包含一些较为复杂的算法以保证在不同的情景下

119
00:08:51,590 --> 00:08:52,300
顺利运行。

120
00:08:52,300 --> 00:08:56,370
我们将在下节课将解。

121
00:08:56,370 --> 00:09:02,580
书中章节4.3Divide-and-conquer:Constructing decision trees介绍了

122
00:09:02,580 --> 00:09:05,360
基本的J48。

123
00:09:06,100 --> 00:09:09,590
请做这节课的课后练习。

124
00:09:09,590 --> 00:09:12,220
祝好运！下次见！