张　慧，侯开虎，周　洲

（昆明理工大学，机电工程学院，云南 昆明　650000）

0　引言

K-近邻（K-Nearest Neighbor，KNN）算法机器学习中解决分类问题的常用方法之一，KNN算法最早是由Cover和Hart在20世纪六十年代提出，在理论上算比较成熟的分类方法。KNN算法的分类原理是通过与分类对象最近的训练样本k来实现分类k一般选择大于 3的任意数，样本之间的空间距离一般采用 Euclidean 距离的计量方式，所要分类的对象以k个样本为依据分类[1]。KNN算法省去了需要预先建立模型的步骤，与其他的机器学习算法相比具有简单高效、不需要进行训练等优点，在分类问题上被广泛使用[2-5]。但传统的KNN算法依然存在很多的不足：在计算时储存参与计算的每一个样本，耗费了极大的储存空间[6]；KNN的计算原理决定了待分类样本要与每一个样本进行距离的计算，其计算量大；由于样本的分配不均衡问题，可能造成分类结果失准[7]；需要通过计算不同的 k值的预测能力来选择不同的k值，算法对不同k值的响应较灵敏，一般使用较小的k值，因此，在进行KNN算法前要确定一个确定k的值，多数情况下是由经验选择[8]。

为了解决KNN算法存在的问题，对KNN算法的优化一直是许多学者关注的问题，主要从两个角度进行优化，原始KNN算法得出的k个最近样本中是以少数服从多数的思想确定被分类样本的类别，就会存在一些干扰样本导致了分类的不精确，所以优化 KNN算法的第一个角度是对所给样本进行剪枝，樊存佳等人[9]采用改进了的 K-Medoids聚类算法对分类中贡献度低但影响分类结果的样本进行裁剪，定义了度函数对测试文本的最近邻文本进行有差别的处理，以此提高了KNN算法的计算速度和分类准确度，但这种方法有可能会过度裁剪；……