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 再见!