关于KNN算法的理解及应用
K最近邻即KNN（k-Nearest Neighbor)分类算法是数据聚类中一种较为简单方便的方法。所谓K最近邻，假设每一类包含多个样本数据，而且没个数据有一个唯一的类标记表示这些样本是属于那一个分类，计算没个样本数据到待分类数据的距离，取和待分类数据最近的K个数据样本，那么这K个样本数据中哪个类别的样本数据占多数，则待分类数据就属于该类别。由此可见，KNN算法的核心思想是如果一个样本在特征空间中的K个最相邻的样本中的大多数属于某一个类别，则该样本也属于这个类别，并具有这个类别上样本的特性。该方法在确定分类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。由于kNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，KNN方法较为适合。
我们可以看两个简单的例子来了解一下KNN算法，如图附录1。列表中给出了七部曾经的风靡电影，可以看到该表统计了每部电影中的打斗次数及接吻次
数，并在最后一列对该电影进行了分类：动作电影抑或是爱情电影。通过观察可以发现，打斗次数多而接吻次数少的电影即被判别为动作电影，反之即为爱情电影，这符合正常的逻辑。对于第七部电影，电影名未知，但已知其中接吻及打斗次数，通过简单比较我们就可以判断出该电影属于动作电影。再看图附录2，图中的圆被决定属于哪个类，是三角形还是四方形？根据定义我们可以做简单的判断：当K=3时，由于三角形所占比例为2/3，故圆将被赋予三角形所在的类。当然我们也可以取K=5，此时四方形所占比例为3/5，故圆将被赋予四方形所在的类。
通过上述的两个例子我们可以总结下KNN算法的算法流程：1. 准备数据，对数据进行预处理；2. 选用合适的数据结构存储训练数据和测试元组；3. 设定参数，如K(K 值的确定目前没有很好的方法，一般采用先定一个初始值，然后根据实验测试的结果调整K 值}；4.维护一个大小为k的的按距离由大到小的优先级队列，用于存储最近邻训练元组。随机从训练元组中选取k个元组作为初始的最近邻元组，分别计算测试元组到这k个元组的距离，将训练元组标号和距离存入优先级队列；5. 遍历训练元组集，计算当前训练元组与测试元组的距离，将所得距离L 与优先级队列
中的最大距离Lmax；6. 进行比较。若L>=Lmax，则舍弃该元组，遍历下一个元组。若L < Lmax，删除优先级队列中最大距离的元组，将当前训练元组存入优先级队列；7. 遍历完毕，计算优先级队列中k 个元组的多数类，并将其作为测试元组的类别；8. 测试元组集测试完毕后计算误差率，继续设定不同的k值重新进行训练，最后取误差率最小的k 值。（详情代码及运行效果图见附录3）
通过对KNN算法的简单应用和流程分析，易知该方法易于实现无需训练。适合对稀有事件进行分类，且在多分类问题中表现的更为突出。但其不足也很明显：第一，当样本不平衡时，如一个类的样本容量很大，而其他类样本容量很小时，有可能导致当输入一个新样本时，该样本的K个邻居中大容量类的样本占多数。该算法只计算"最近的"邻居样本，某一类的样本数量很大，那么或者这类样本并不接近目标样本，或者这类样本很靠近目标样本。无论怎样，数量并不能影响运行结果。第二：计算量较大，对每一个待分类的文本都要计算它到全体已知样本的距离，才能求得它的K个最近邻点。
针对KNN算法的不足，一些关于它的改进算法也应运而生。比如分组快速搜索近邻法：将样本集按近
邻关系分解成组，给出每组质心的位置，以质心作为代表点，和未知样本计算距离，选出距离最近的一个或若干个组，再在组的范围内应用一般的KNN算法。还有剪辑近邻法：用现有样本集对其自身进行剪辑，将不同类别交界处的样本以适当方式筛选，可以实现既减少样本数又提高正确识别率的双重目的。它的基本思想是：将样本集K N分成两个互相独立的子集：test 集K T和reference集K R。首先对K T中每一个X i在K R中找到其最近邻的样本Y i(X i) 。如果Y i与X i不属于同一类别，则将X i从K T中删除，最后得到一个剪辑的样本集K TE（剪辑样本集），以取代原样本集，对待识别样本进行分类。这两种方法对KNN算法进行了一些简化和修改，在不同程度上简化了KNN算法，但对于如何客服基本KNN算法计算复杂的缺点一直没有得到很好的解决。
附录1：