KNN参考文献翻译.doc

KNN参考文献翻译.doc
Rote分类器（死记硬背分类器）是最简单和相当琐碎的分类器的一种，其中记忆整个 训练数据，并且执行分类当且仅当测试对象的属性完全匹配某一个训练对象的属性。这种方 法的一个明显的问题是，许多测试记录将不被归类，因为它们不完全符合某一个培训记录。 另一个问题出现，当两个或两个以上的培训记录具有相同的属性，但不同的类标签。
一个更复杂的方法，k-近邻（KNN）分类，发现最接近的测试对象中的训练集的一组k 类对象，和根据标签上的优势在这附近的一个特定的类的分配。这解决了上述问题，在许多 数据集，这是不太可能的，一个对象将完全匹配另一个，以及一个事实，即关于一个对象的 类的相互矛盾的信息可能由最靠近它的对象提供。关于这种方法有一些关键部分：（i ）被 标记的对象的集合被用于评估测试对象的类，（ii）距离或者相似性度量，可以被使用于计 算对象的接近程度（iii）该的k值，最近邻的数目，（iv）所使用的方法是用来确定基于类和 k个最近邻的距离的目标对象的类。在其最简单的形式，KNN涉及分配对象的其最近邻的类 或者多数其最近邻，但各种增强功能是可能的并且将在下面讨论。
更一般地，kNN是一种基于实例学习的特殊情况。这包括基于案例的关于处理符号数据 的推理。kNN方法也是一个例子关于懒惰学习技术，即，一种技术，它等待直到查询到达总 结出超出了训练数据。
虽然KNN分类是一个很容易理解和执行的分类技术，在许多情况下，它可以很好的执 行。特别是，一个由Cover和Hart总结的众所周知的结论显示，最近邻居规则的分类 错误的上界等于两倍在一定合理假设下的最优贝叶斯错误。此外，一般的kNN方法的误 差渐近贝叶斯错误并且可以用来近似它。
此外，由于它的简单性，kNN是一个容易修改为更复杂的分类问题。例如，kNN是特别 非常适合于多式联运类以及一个对象可以有许多类标签的应用程序。至此说明最后一点，为 了根据基因芯片表达谱上的基因的功能分配，一些研究人员发现，kNN的表现优于一个更 为复杂的分类方案——支持向量机（SVM）的方法。
本章的其余部分描述了基本的KNN算法，包括影响分类和计算性能的各种问题：指针 被利用于kNN的实现，并且还提供了使用Weka中机器学习包来执行最近邻分类的例子。简 要讨论了先进的技术以及本章包含了一些练习。


。给定一个训练集D和一个测试对象z(属 性值的一个向量值)，并具有一个未知的类标签，算法计算z和所有的训练对象之间的距离 (或相似性)，以确定其最近邻居的列表。然后，它通过考虑相邻对象的类的大多数一类分 配到z。在一个不确定的方式关系被打破，例如，通过随机或采取的最常见的一类的训练集。
基本KNN算法
输入：训练对象的集合D,测试对象z (这是一个属性值的向量)，以及用于标记对象的类的 集(L)
输出：公♦七,z的类
foreach 对象 y 仁 D do
|计算d(z, y),z和y之间的距离；
end
选择 N 1 D, the set (neighborhood) of k closest training objects for z;
Cz = argmax £心 = ckss(Cy)):| vgL '
whe