1
00:00:17,320 --> 00:00:24,240
大家好！在上一课，我们学习了构建决策树的基本算法。

2
00:00:24,240 --> 00:00:29,450
为了得到一个具有工业强度的决策树归纳算法，我们需要添加一些

3
00:00:29,450 --> 00:00:32,870
更复杂的东西，尤其是修剪。

4
00:00:32,870 --> 00:00:37,949
我们这节课要谈论修剪决策树。

5
00:00:37,949 --> 00:00:41,600
这有一个给树剪枝的人，当提到修剪决策树时，

6
00:00:41,600 --> 00:00:43,110
你的脑海可以浮现出这个很形象的画面。

7
00:00:43,110 --> 00:00:47,460
我们寻找一些树的边缘的小细枝和小树叉，

8
00:00:47,460 --> 00:00:52,340
检查他们是否是有价值的，如果发现他们是多余的就剪除它。

9
00:00:52,340 --> 00:00:58,570
这样，我们可能得到一个在训练数据上表现差的决策树，但是也许

10
00:00:58,579 --> 00:01:02,680
在独立的测试数据上会表现的好。

11
00:01:02,680 --> 00:01:07,100
这就是我们想要的。

12
00:01:07,100 --> 00:01:08,350
这里又是天气数据。

13
00:01:08,350 --> 00:01:12,490
我很抱歉总是使用天气数据，但是这是一个我们熟悉的

14
00:01:12,490 --> 00:01:13,970
简单好用的例子。

15
00:01:13,970 --> 00:01:15,920
我已经在这里新增了一个新的属性。

16
00:01:15,920 --> 00:01:21,090
我把它叫做ID属性，这个属性对于每个实例都有不同的值。

17
00:01:21,090 --> 00:01:25,530
我已经赋给它们一个识别码：a，b，c，等等。

18
00:01:25,530 --> 00:01:29,119
让我们回想一下上节课学过的知识，

19
00:01:29,119 --> 00:01:34,170
当我们寻找最好的属性作为根节点，第一个决定，是怎样做的。

20
00:01:34,170 --> 00:01:39,759
我们分别计算每个属性的信息增益。

21
00:01:39,759 --> 00:01:43,630
如果选择ID属性，我们将获得许多信息。

22
00:01:43,630 --> 00:01:48,040
实际上，如果你用ID属性划分，

23
00:01:48,040 --> 00:01:49,049
你将得到我们想要的

24
00:01:49,049 --> 00:01:54,149
这是一个最大的信息增益，很明确地，我们将用

25
00:01:54,149 --> 00:01:58,590
ID属性在决策树的根节点划分实例。

26
00:01:58,590 --> 00:02:05,590
但是，这完全不能运用到新的天气实例上。

27
00:02:07,119 --> 00:02:12,790
为了解决这个问题，构建决策树后，决策树算法，

28
00:02:12,790 --> 00:02:15,230
会自动修剪决策树。

29
00:02:15,230 --> 00:02:22,230
你不会看到这个过程，这个过程在Weka中自动完成。

30
00:02:22,350 --> 00:02:28,419
我们如何修剪呢？这有一些简单的修剪技术，和一些较复杂的

31
00:02:28,419 --> 00:02:29,410
修建技术。

32
00:02:29,410 --> 00:02:36,410
一种非常简单的技术是：如果节点包含的实例非常少，就停止分裂。

33
00:02:37,079 --> 00:02:43,850
上节课，我说我们要一直分裂到每个节点只有

34
00:02:43,850 --> 00:02:46,130
一个分类。

35
00:02:46,130 --> 00:02:51,070
这恐怕不是一个好主意。如果一个节点只包含很少的几个实例，

36
00:02:51,070 --> 00:02:53,470
那么恐怕不值得再继续分裂这个节点了。

37
00:02:53,470 --> 00:02:56,160
实际上，这是J48的参数之一。

38
00:02:56,160 --> 00:03:02,690
打开Weka，选择J48，看下它的参数。

39
00:03:08,370 --> 00:03:12,480
这里有一个叫做minNumObj的参数。

40
00:03:12,480 --> 00:03:18,190
如果把鼠标移到这个参数上，可以看到"每个叶节点最少包含多少个实例"。

41
00:03:18,190 --> 00:03:22,669
默认值是2。

42
00:03:22,669 --> 00:03:26,560
下一步，我们创建一个详尽的决策树，然后从叶节点开始修剪。

43
00:03:26,560 --> 00:03:31,500
 这表明，先创建详尽的的树再反向修剪比

44
00:03:31,500 --> 00:03:35,040
在建树的过程中正向修剪要好。

45
00:03:35,040 --> 00:03:37,880
我们将在每一个阶段进行统计测试。

46
00:03:37,880 --> 00:03:39,570
这是confidenceFactor参数。

47
00:03:39,570 --> 00:03:40,590
它在这里。

48
00:03:40,590 --> 00:03:42,979
默认值是0.25。

49
00:03:42,979 --> 00:03:48,190
“用于修剪的信心因数（较小的值导致更多的修剪]。”

50
00:03:48,190 --> 00:03:53,519
有时修剪一个内部节点并将它的子树提升

51
00:03:53,519 --> 00:03:57,269
一个层次。

52
00:03:57,269 --> 00:03:59,130
这叫做子树提升。

53
00:03:59,130 --> 00:04:01,220
就是这个参数。

54
00:04:01,220 --> 00:04:02,880
我们可以启用或者关闭它。

55
00:04:02,880 --> 00:04:09,570
“在修剪时，是否考虑子树提升操作。”提升子树实际上

56
00:04:09,570 --> 00:04:18,130
增加了算法的复杂度，所以关闭它可以缩短运行时间。

57
00:04:18,130 --> 00:04:21,479
子树提升是一个大问题。

58
00:04:21,479 --> 00:04:24,820
我不打算介绍子树提升的细节。

59
00:04:24,820 --> 00:04:29,009
修剪是一个混乱和复杂的主题，而且不是特别有启发性。

60
00:04:29,009 --> 00:04:33,229
实际上，我并不建议改变这里的这些参数。

61
00:04:33,229 --> 00:04:38,130
J48的默认值往往表现很好。

62
00:04:40,300 --> 00:04:45,700
当然，现在你知道了，需要修剪的真正原因是

63
00:04:45,700 --> 00:04:51,800
原始的未修剪的决策树过度拟合训练数据集。

64
00:04:51,800 --> 00:04:54,080
这是过度拟合的另一个例子。

65
00:04:54,080 --> 00:05:00,010
有时候，简化后的决策树会有更好的结果，并不仅仅是更小的，更易管理的

66
00:05:00,010 --> 00:05:03,030
决策树，也会得到更好的结果。

67
00:05:03,030 --> 00:05:05,530
载入diabetes数据集。

68
00:05:13,360 --> 00:05:20,440
选择J48，保留默认参数值，运行。

69
00:05:20,440 --> 00:05:28,480
交叉验证的准确率是73.8%。

70
00:05:28,480 --> 00:05:37,020
这个决策树一共39个节点，其中20个是叶节点。

71
00:05:37,020 --> 00:05:42,950
也就是19个内部节点和20个叶节点。

72
00:05:43,500 --> 00:05:45,320
让我们去掉修剪过程。

73
00:05:45,320 --> 00:05:47,260
J48默认修剪。

74
00:05:47,260 --> 00:05:48,940
关掉修剪过程。

75
00:05:48,940 --> 00:05:53,140
这里有一个unpruned的选项，默认值是false，意味修剪。

76
00:05:53,140 --> 00:05:59,850
改为true（即不再修剪）

77
00:05:59,850 --> 00:06:00,750
再次运行。

78
00:06:00,750 --> 00:06:07,750
现在我们得到的是一个略低的准确率，72.7%，低得并不多。

79
00:06:07,750 --> 00:06:13,760
我们得到了一个大得多的决策树——22个叶节点，一共43个节点。

80
00:06:13,760 --> 00:06:15,420
这是之前的两倍。

81
00:06:15,420 --> 00:06:19,280
我们得到了一个更大更难理解的准确率略低的

82
00:06:19,280 --> 00:06:20,460
决策树。

83
00:06:20,460 --> 00:06:25,490
这里，我们更喜欢修剪之后的决策树。

84
00:06:26,240 --> 00:06:30,580
我将用一组关于乳腺癌的数据给你演示另一个极端的例子。

85
00:06:30,580 --> 00:06:36,770
我想我们之前没有见过乳腺癌的数据。

86
00:06:36,770 --> 00:06:45,460
分类是no-recurrence-events和recurrence-events，属性有年龄（age）、绝经期 （menopause）、

87
00:06:45,460 --> 00:06:49,360
肿瘤大小（tumor size），等等。

88
00:06:49,360 --> 00:06:53,560
我们使用J48的默认配置。

89
00:06:53,560 --> 00:07:02,460
启用修剪（将unpruned设置为false）然后运行它。

90
00:07:04,000 --> 00:07:11,710
准确率是75.5%，并且生成了一个相当小的只有4个叶节点和2个内部节点的决策树。

91
00:07:11,710 --> 00:07:18,700
可以在这里查看决策树，或者可视化决策树。

92
00:07:22,440 --> 00:07:27,680
这里，我们得到这个简单的决策结构，它很容易理解并且

93
00:07:27,680 --> 00:07:30,490
表现出色，拥有75%的准确度。

94
00:07:30,490 --> 00:07:35,740
我们将要关掉修剪过程。

95
00:07:35,740 --> 00:07:39,930
将unpruned设置为true，再次运行。

96
00:07:41,700 --> 00:07:49,910
首先，我们得到了一个坏得多的结果，69.6%

97
00:07:49,910 --> 00:07:51,870
比我们之前得到的75.5%差多了。

98
00:07:51,870 --> 00:07:58,870
更重要的是，我们得到的是一个有152个叶节点，共179个节点的巨大的决策树。

99
00:07:59,510 --> 00:08:00,460
这真大。

100
00:08:00,460 --> 00:08:04,720
如果可视化这个决策树，很可能我们不能看到具体的内容。

101
00:08:04,720 --> 00:08:09,530
我可以试着调整决策树的大小以适应我的屏幕，

102
00:08:12,360 --> 00:08:14,860
但是，这里还是不可能看到具体有什么。

103
00:08:14,860 --> 00:08:21,860
事实上，如果我们看树的文本描述，会发现它极其复杂。

104
00:08:22,880 --> 00:08:24,949
这是不好的。

105
00:08:24,949 --> 00:08:27,810
这里，创建未修剪的树是一个非常坏的选择。

106
00:08:27,810 --> 00:08:34,810
我们得到一棵巨大的树，它比一个简单得多的决策结构要差许多。

107
00:08:35,930 --> 00:08:42,919
J48默认进行修剪，一般情况下，你应该让它用

108
00:08:42,919 --> 00:08:44,079
默认的参数值修剪。

109
00:08:44,079 --> 00:08:46,940
这是我的建议。

110
00:08:48,870 --> 00:08:52,920
我们谈论J48，或者，换句话说，C4.5。

111
00:08:52,920 --> 00:08:59,589
记得在Lesson 1.4，我们提到Ross Quinlan的C4.5的发展。

112
00:08:59,589 --> 00:09:05,240
在屏幕的底部有一张澳大利亚计算机学家Ross Quinlan的照片。

113
00:09:05,240 --> 00:09:11,500
J48用Java实现了Ross的C4.5，

114
00:09:11,500 --> 00:09:14,100
两者的本质是一样的。

115
00:09:14,100 --> 00:09:15,690
这是非常受欢迎的方法。

116
00:09:15,690 --> 00:09:17,520
简单而实用。

117
00:09:17,520 --> 00:09:21,900
决策树很有吸引力，因为你可以看到它们，可以看到它们的决策结构，

118
00:09:21,900 --> 00:09:24,740
看到哪些对于你的数据是重要的。

119
00:09:25,850 --> 00:09:31,740
有许多不同的修剪方法，它们的主要作用是

120
00:09:31,790 --> 00:09:32,410
改变树的大小。

121
00:09:32,410 --> 00:09:36,360
修剪方法对准确率的影响很小，通常使准确率下降。

122
00:09:36,360 --> 00:09:42,650
修剪方法经常会大大简化决策树，就像我们刚刚看到的乳腺癌的例子。

123
00:09:42,650 --> 00:09:47,670
修剪实际上是防止过拟合的一个通用的技术，它可以应用于

124
00:09:47,670 --> 00:09:52,540
树之外的其他结构，如决策规则。

125
00:09:52,540 --> 00:09:56,940
关于决策树，我们还可以介绍很多。

126
00:09:56,940 --> 00:10:01,730
例如，我们以前经常谈论的单变量决策树

127
00:10:01,730 --> 00:10:04,450
即，每个节点只有一个测试。

128
00:10:04,450 --> 00:10:08,550
你可以想像一个多变量的树，那里是一个复合试验。

129
00:10:08,550 --> 00:10:14,110
节点的测试可能是“如果这个属性是什么并且另一个属性是什么”。

130
00:10:14,110 --> 00:10:19,370
你可以想像由更复杂的算法生成的更复杂的决策树。

131
00:10:19,370 --> 00:10:26,370
一般来说，C4.5/J48是一个常见的有效的数据挖掘算法。

132
00:10:27,740 --> 00:10:32,310
课本中有更多关于决策树的内容。

133
00:10:32,310 --> 00:10:37,610
第六章第一节是关于修剪的，并且提供了我在这里简述过的

134
00:10:37,610 --> 00:10:43,310
修剪方法的数学背景。

135
00:10:43,310 --> 00:10:46,240
做下练习，我们下节课见。

136
00:10:46,240 --> 00:10:47,900
再见！