机器学习十大算法8：kNN概要

1、第八章k NN3336万-最近邻居迈克尔斯坦贝克和庞内容8.1简介(1518.2算法描述(1528 .2 .1高级描述(1528 .2 .2问题(1538 .2 .3软件实施(1558.3示例(1558.4高级主题(1578.5练习(158确认(159参考文献(1598.1介绍最简单且相当简单的分类器之一是死记硬背分类器，它存储整个训练数据，并且仅当测试对象的属性与其中一个训练对象的属性完全匹配时才执行分类。这种方法的一个明显问题是，许多测试记录不会被分类，因为它们与任何培训记录都不完全匹配。当两个或多个训练记录具有相同的属性但不同的类别标签时，会出现另一个问题。一种更复杂的方法，k-最近邻(

2、k NnClassi10，11，21，在训练集中找出一组最接近测试对象的k个对象，并根据该邻域中特定类的优势来分配标签。这解决了在许多数据集中，一个对象不太可能与另一个完全匹配的问题，以及关于一个对象的类的冲突信息可能由最接近它的对象提供的事实。这种方法有几个关键要素：(用于评估测试对象类别的一组标记对象，1(可用于计算的距离或相似性度量这不一定是整个训练集。151152kNN3336万-最近邻居物体的接近度(三)k的值，最近邻居的数量，以及用于基于k个最近邻居的类别和距离来确定目标物体的类别的方法。在其最简单的形式中k神经网络可以包括给一个对象分配其最近邻居的类或其大多数最近邻居的类，但是各

3、种增强是可能的，并且将在下面讨论。更一般地说k神经网络是基于实例学习的一个特例1.这包括基于案例的推理3，它处理符号数据k .神经网络方法也是一种惰性学习技术的例子，也就是说，这种技术一直等到查询到达时才进行扩展，超出了训练数据的范围。尽管k神经网络分类是一种易于理解和实现的分类技术，但它在许多情况下表现良好。特别是，封面和Hart6的一个众所周知的结果表明，在某些合理的假设下，最近邻规则的分类误差2被最佳贝叶斯误差3的两倍所限制。此外，广义k神经网络方法的误差渐近地接近于贝叶斯误差，并可用于逼近它。此外，由于它的简单性k神经网络很容易修改为更复杂的分类问题。例如k神经网络特别适用于多模态类4

4、以及一个对象可以有许多类标签的应用。为了说明最后一点，对于基于微阵列表达谱的基因功能分配，一些研究人员发现k神经网络优于支持向量机（支持向量机)，后者是一种更复杂的分类方案17.本章的其余部分描述了基本的k神经网络算法，包括影响分类和计算性能的各种问题。给出了k神经网络实现的指针，并提供了使用新西兰黑秧鸡机器学习包执行最近邻分类的示例。本章简要讨论了高级技术，并以几个练习结束8.2 .算法描述8 .2 .1高级描述算法8.1提供了最近邻分类方法的高级摘要。给定一个训练集D和一个测试对象z，测试对象z是属性值的向量，并且具有未知的类标签，算法计算距离（或相似性2分类器的分类错误是它错误分类的实例

5、的百分比。3贝叶斯误差是贝叶斯分类器的分类误差，即知道数据相对于类的潜在概率分布，并将每个数据点分配给该点概率密度最高的类的分类器。有关更多详细信息，请参见9.4对于多模式类，特定类标签的对象集中在数据空间的几个不同区域，而不仅仅是一个。用统计学术语来说，该类的概率密度函数不像高斯函数那样只有一个凸起，而是有多个峰值。8.2算法描述153算法8.1基本k神经网络算法输入：D，训练对象的集合，测试对象z，它是属性值和用于标记对象的类的集合输出3336 c zL，该类z为每个对象y D做|计算d (z，y，z和y之间的距离；目标选择D北部该集合为z的k个最近训练对象的邻域；c z=argmax v LyN输入(v=类(c y );其中，我(是一个指示函数，如果其参数为真，则返回值1，否则返回0 .在z和所有训练对象之间，确定其最近邻列表。然后，它通过获取大多数相邻对象的类来给z赋值。领带以不明确的方式被打破，例如，随机地或通过参加训练集中最频繁的课程。该算法的存储复杂度为O (n，其中n是训练对象的数量。时间复杂度也是O (n，因为需要计算目标和每