1
00:00:16,770 --> 00:00:19,360
大家好！我现在坐这里，在新西兰。

2
00:00:19,360 --> 00:00:21,440
新西兰在我后面的地球仪上。

3
00:00:21,440 --> 00:00:24,700
这里是新西兰，在世界的顶端，被大海环绕。

4
00:00:24,700 --> 00:00:27,540
但是，以前我不在这里。

5
00:00:27,540 --> 00:00:30,790
我20年前来到这里。

6
00:00:30,790 --> 00:00:35,790
在地图上，这里当然是新西兰，Google地图把北半球放在上面

7
00:00:35,790 --> 00:00:37,480
你用的那个应该也是这样。

8
00:00:37,480 --> 00:00:42,430
我从工作多年的 Calgary大学来到这里。

9
00:00:42,430 --> 00:00:45,540
我以前是 Calgary大学计算机科学的系主任。

10
00:00:45,540 --> 00:00:50,860
但是，最初，我来自Belfast，北爱尔兰，就在（大不列颠）联合王国的这里。

11
00:00:50,860 --> 00:00:55,410
所以，我的口音实际是北爱尔兰口音而不是新西兰口音。

12
00:00:55,410 --> 00:00:59,010
这不是新西兰口音。

13
00:00:59,010 --> 00:01:03,440
在第三部分的最后一节课，我们要介绍的是另一种机器学习的

14
00:01:03,440 --> 00:01:08,330
方法，叫做最邻近（nearest neighbor）或者基于实例的（instance-based）机器学习方法。

15
00:01:08,330 --> 00:01:15,330
当人们谈论机械式学习，他们只谈论记住的东西，

16
00:01:15,360 --> 00:01:17,550
而没有真正的思考。

17
00:01:17,550 --> 00:01:20,110
这是最简单的学习。

18
00:01:20,110 --> 00:01:23,030
nearest neighbor就是一种机械式学习。

19
00:01:23,030 --> 00:01:28,750
它只记忆训练实例，然后，为了给新的实例分类，寻找

20
00:01:28,750 --> 00:01:33,520
训练数据集中与新实例最相似的的实例。

21
00:01:33,520 --> 00:01:36,530
这里的知识表现为实例的集合。

22
00:01:36,530 --> 00:01:38,680
这是一种懒惰学习。

23
00:01:38,680 --> 00:01:42,610
学习者在预测之前不用做任何事情。

24
00:01:42,610 --> 00:01:46,970
令人费解的是，它也被称为基于实例的（instance-based）学习。

25
00:01:46,970 --> 00:01:52,100
nearest neighbor learning和instance-based learning是一样的。

26
00:01:52,100 --> 00:01:56,390
这是一张二维的实例空间示意图。

27
00:01:56,390 --> 00:02:02,330
蓝色的点和白色的点代表两种不同的类别，例如，yes和no。

28
00:02:02,330 --> 00:02:06,330
然后，我们有一个未知分类的点，一个红色的点。

29
00:02:06,330 --> 00:02:07,800
我们想知道它的分类。

30
00:02:07,800 --> 00:02:12,820
所以，我们简单地去找每个分类中最接近的实例，比较哪个更近。

31
00:02:12,820 --> 00:02:15,050
在这里，是这个蓝色的点。

32
00:02:15,050 --> 00:02:19,280
所以，我们将这个红色的点归为蓝色的点所在的分类。

33
00:02:19,280 --> 00:02:25,450
如果你想想看，在两个点之间划一条辅助线。

34
00:02:25,450 --> 00:02:32,410
这里是一条直线，最近的两个点的连线的中垂线。

35
00:02:32,410 --> 00:02:36,570
nearest neighbor 方法产生一个线性的决策边界。

36
00:02:36,570 --> 00:02:39,470
实际上，要比这复杂一点。

37
00:02:39,470 --> 00:02:46,700
它产生一个分段的线性的决策边界，有时是由一组短小的线性线段

38
00:02:46,700 --> 00:02:48,690
组成的决策边界。

39
00:02:50,840 --> 00:02:54,860
当然，关键是如何理解“最相似的”。

40
00:02:54,860 --> 00:03:00,480
我们需要一个相似性函数，通常，人们用常规的距离函数，

41
00:03:00,480 --> 00:03:07,920
欧氏距离（Euclidean distance），即属性值的差异的平方和。

42
00:03:07,920 --> 00:03:11,480
实际上，是平方和的平方根，但是我们只是比较

43
00:03:11,480 --> 00:03:14,220
两个实例，我们不需要开平方。

44
00:03:15,130 --> 00:03:20,510
或者，你可以使用曼哈顿距离（Manhattan 或 city block distance），

45
00:03:20,510 --> 00:03:22,290
即属性值之间的绝对差值总和。

46
00:03:23,410 --> 00:03:26,830
当然，我这里说的是数值属性。

47
00:03:26,830 --> 00:03:33,290
如果是名词类属性，我们需要定义不同的属性值之间的差异。

48
00:03:34,050 --> 00:03:38,210
通常，人们认为属性值不同的距离是1，

49
00:03:38,210 --> 00:03:39,960
属性值相同的距离是0。

50
00:03:39,960 --> 00:03:44,820
对于nearest neighbor learning，这也许是一个归一化属性的好主意，

51
00:03:44,820 --> 00:03:49,780
这样距离都在0和1之间，距离就不会被

52
00:03:49,780 --> 00:03:54,270
一些比例巨大的属性扭曲。

53
00:03:54,270 --> 00:03:57,070
怎样处理噪音实例。

54
00:03:57,070 --> 00:04:04,000
如果我们有一个有噪音的数据集，我们偶尔会找到一个

55
00:04:04,000 --> 00:04:06,850
分类错误的训练实例作为测试实例最邻近的实例。

56
00:04:06,850 --> 00:04:12,360
你可以通过使用k-nearest-neighbors避免这种情况。

57
00:04:12,360 --> 00:04:17,280
k可以是3或者5，你寻找最近的3到5个实例，

58
00:04:17,280 --> 00:04:22,030
其中的大多数属于某一个分类，则该实例也属于这个分类。

59
00:04:22,030 --> 00:04:24,540
这就是k-nearest-neighbor方法。

60
00:04:24,540 --> 00:04:31,650
在Weka中，这叫做IBk，这是一种懒惰学习法。

61
00:04:31,650 --> 00:04:38,000
让我们栽入glass数据集。

62
00:04:40,230 --> 00:04:46,490
切换到分类面板，选择懒惰分类器IBk。

63
00:04:48,430 --> 00:04:49,960
直接运行它。

64
00:04:49,960 --> 00:04:56,960
准确率是70.6%。

65
00:04:57,150 --> 00:04:59,650
模型并没有真正的显示出来，因为就没有模型。

66
00:04:59,650 --> 00:05:02,520
只有训练实例集。

67
00:05:03,440 --> 00:05:05,960
当然，我们用的是十折交叉验证。

68
00:05:05,960 --> 00:05:12,960
让我们改变k的值，这个kNN表示k的值。

69
00:05:15,070 --> 00:05:16,470
默认设置是1。

70
00:05:16,470 --> 00:05:23,470
（使用的临近的实例数）。我们将改为5，运行。

71
00:05:24,840 --> 00:05:31,380
k等于5时，我们得到了稍差一些的结果，67.8%。

72
00:05:32,120 --> 00:05:35,010
我认为这不是一个含有很多噪音的数据集。

73
00:05:35,010 --> 00:05:41,810
如果我们把k变为20，再次运行。

74
00:05:41,810 --> 00:05:44,840
我们得到65%的准确率，更加差一些。

75
00:05:45,440 --> 00:05:52,280
如果我们用一个充满噪音的数据集，我们会发现随着k刚开始增大时，

76
00:05:52,280 --> 00:05:53,490
准确率会提高。

77
00:05:53,490 --> 00:05:55,960
然后，（随着k增大）准确率总是会开始降低的。

78
00:05:55,960 --> 00:06:00,940
如果我们把k设为一个极值，接近整个数据集的大小，然后

79
00:06:00,940 --> 00:06:06,550
我们算出测试实例到所有训练实例的距离，并且求平均值

80
00:06:06,550 --> 00:06:10,090
我们大概会得到一个的接近基线的准确率。

81
00:06:10,090 --> 00:06:15,440
这里，如果我把k定到极大的值，例如100。

82
00:06:15,440 --> 00:06:22,150
找出最近的100个实例，求它们的类别的平均值。

83
00:06:22,150 --> 00:06:29,070
我们得到的准确率是35%，这个数，我想已经非常接近

84
00:06:29,070 --> 00:06:30,090
这个数据集的基线准确率了。

85
00:06:30,090 --> 00:06:36,710
让我们用ZeroR验证一下，基线准确率准确的是35%。

86
00:06:40,280 --> 00:06:42,000
nearest neighbor是一个很好的方法。

87
00:06:42,000 --> 00:06:44,090
通常都很准确。

88
00:06:44,090 --> 00:06:45,430
它可能有点慢。

89
00:06:45,430 --> 00:06:52,050
每一个预测都需要扫描整个训练数据集，

90
00:06:52,050 --> 00:06:56,690
因为我们需要计算未知的测试实例到所有训练实例的距离

91
00:06:56,690 --> 00:06:59,320
以便找到最邻近的实例。

92
00:06:59,320 --> 00:07:03,190
一些复杂的数据结构可以加速这个过程加速，所以，

93
00:07:03,190 --> 00:07:06,300
你不需要每次都扫描整个数据集。

94
00:07:06,300 --> 00:07:09,900
（IBk）假设所有的实例都是一样重要的。

95
00:07:09,900 --> 00:07:14,810
如果不是这样，你可以使用根据属性的重要性

96
00:07:14,810 --> 00:07:18,240
来选择或加权属性的方案。

97
00:07:18,240 --> 00:07:23,220
如果我们有噪音实例，那么我们采纳k个近邻实例中的占大多数的分类，

98
00:07:23,220 --> 00:07:27,370
或者我们根据实例的预测准确率给它们加权。

99
00:07:27,370 --> 00:07:32,850
再或者，我们可以试着找到每个分类别中可靠的原型，

100
00:07:32,850 --> 00:07:34,270
这是一个非常老的方法了。

101
00:07:34,270 --> 00:07:37,650
统计人员从二十世纪五十年代开始使用k-nearest-neighbor。

102
00:07:37,650 --> 00:07:41,210
这里有一个有趣的理论结果。

103
00:07:41,210 --> 00:07:49,090
如果训练实例的数量趋于无穷大，k也增大，以致于

104
00:07:49,090 --> 00:07:58,550
k/n接近0，但k也趋于无穷大，k-nearest-neighbor的错误率

105
00:07:58,550 --> 00:08:03,190
趋于这个数据集的理论最小错误率。

106
00:08:03,190 --> 00:08:08,800
这从理论上保证了，对于较大的训练数据集和较大的k值，

107
00:08:08,800 --> 00:08:12,800
使用nearest neighbor 方法，可以得到较好的分类结果。

108
00:08:12,800 --> 00:08:16,800
课本的第四章第七节介绍了基于实例的学习。

109
00:08:16,800 --> 00:08:19,830
这是第三部分的最后一课。

110
00:08:19,830 --> 00:08:23,300
请大家完成课后练习，我们第四部分见。

111
00:08:23,300 --> 00:08:25,030
再见！