k近邻法

k近邻法

    k近邻法（k nearest neighbor algorithm，k-NN）是机器学习中最基本的分类算法，在训练数据集中找到k个最近邻的实例，类别由这k个近邻中占最多的实例的类别来决定，当k=1时，即类别为最近邻的实例的类别。

    如上图所示（引自wiki），当k=3时，此时红色的个数为2，则绿色的输入实例的类别为红色的三角形，当k=5时，此时蓝色的个数为3，输入实例的类别为蓝色的四边形。
    在分类过程中，k值通常是人为预先定义的常值，从上图可以看出，k值的选取对会对结果有很多的影响。大的k值可以减小噪声对分类的影响，但是和实例较远的实类会对判决起作用，通常采用交叉验证的方式来选取最优的k值。

    通常实类间的距离通常采用欧氏距离，这主要面向的是连续的特征变量，对于文本分类问题，可以采用汉明距离（Hamming distance），定义为两个字符串对应位置的不同字符的个数。对距离的度量很多，往往按照应用来决定。
    k近邻法的最简单的实现就是线性扫描，当训练集的数据很大，特征的维度很高的时候，计算量就会过于巨大，可以通过建立k-d tree进行快速搜索k近邻。

继续阅读

http://blog.csdn.net/hust_core/article/details/7628177

http://www.cnblogs.com/eyeszjwang/articles/2429382.html

http://www.cnblogs.com/eyeszjwang/articles/2432465.html