《K近邻算法优化设计策略》-工学论文，计算机论文-论文范文参考-科学狗论文网

标题

K近邻算法优化设计策略

范文

李驰段雨梅

摘要：K近邻算法作为一种简单有效且易于实现的机器学习算法被广泛应用于模式识别的各领域。为了提高该算法的准确度和执行效率，需要在算法设计的多个环节上进行策略的优化。针对提高该算法的准确度，首先探讨了K值的选择问题，然后对几种距离度量的方法进行了分析比较，最后对分类决策规则问题进行了阐述。针对提高算法的执行效率，从样本数筛选、维度降低和搜索空间优化三个方面进行了分析，从而降低了该算法的计算复杂度。

关键词：K近邻;K值选择;距离度量;分类决策规则;Kd树

中图分类号：TP18 文献标识码：A

文章编号：1009-3044（2019）31-0200-03

K近邻算法是机器学习中经典而简单的算法，它既可以用于分类，也可以用于回归，甚至在异常点检测问题（one-class）上也可以使用。该算法依赖周围有限个近鄰样本，而不是通过判别类域的方法来预测待测点的类别，所以针对类与类交叉严重或者不同类别重叠较多的情况较其他分类法有一定的优势。该算法的实现步骤是：首先计算已知类别数据集中的每个点与待测点之间的距离，然后选取其中距离值最小的K个点，最后统计出这K个点中出现频率最高的类别就是待测点的类别。K近邻算法虽然简单，但是要让它真正有效的运行，必须要在设计的多个环节上进行策略的优化，本文对此进行分析和讨论。

1K值的选择

K近邻算法中K值的确定对算法的准确性影响是很大的。但是这个值的选择是比较困难的，直观认为既不能太小也不能太大。

K值如果太小，虽然会让学习的近似误差变小，但是同时会使得学习的估计误差变大。这样使得预测结果直接只受近邻的少数几个实例点的影响，而如果它们又恰巧是噪声点，则预测出错的可能性就增大了。太小的K值会导致整体模型变得复杂，容易发生过拟合。一个极端的情况是K等于1，如图1虚线小圆圈所示，离问号处最近点的类别是圆形（很明显，它是一个噪点），于是我们就错误的将问号处的点划归为圆形类别，而直观告诉我们，其实它更应该属于三角形类别。

另一方面，K值如果太大，虽然会让学习的估计误差变小，但是同时会使得学习的近似误差变大。K值太大，固然使得考虑的实例点增多，但是也会让一些离预测点很远，没什么相关陛的实例点来参与到预测决策中，而且有时靠着数量众多还起到了比较大的决策作用，这显然是不太合理的。太大的K值会导致整体模型变得简单，容易发生欠拟合。一个极端的情况就是K等于N（N为样本点的总数），如图1虚线大圆圈所示，无论问号点在哪个位置，也无论其他点如何分布，最终我们都简单地认为它属于所有样本点中类别最多的那个类，即这里的圆形类，显然这是不合适的。

既然K值既不能太小也不能太大，那应该如何选择。很显然，我们希望得到如图1中实线中圆圈所示对应的K等于9的值。解决方式一种是使用交叉验证。交叉验证是一种常用的模型选择方法，它的基本思想就是通过多次反复将数据集分为一部分训练集，另一部分为测试集，然后尝试在这些训练集中取不同的K值，测试集中观察它们的误差，最后选出最小误差对应的K值。常用的交叉验证法有简单交叉验证、L折交叉验证和留一交叉验证。另一种解决思路就是尝试使用一些智能算法，例如遗传算法等，将预测误差率设置为目标函数，不断地迭代推演K值，找出使得目标函数值最小的K值。

2距离的度量

2.1传统的距离度量

2.2余弦距离度量

除了以上这类定义距离的方式之外，在有些领域的K近邻分类算法中采用一种称为余弦定理的度量方式来定义距离更为合适。例如在使用K近邻算法对新闻进行分类时，我们可以将某篇新闻中对应的TF-IDF值f即新闻中出现该关键词的频数占总数的百分比）使用特征向量表示出来。如果两篇新闻的内容很相似，则它们必然在很多维度上的TF-IDF值相似，从而我们可以通过比较这两篇新闻对应的特征向量的夹角来考察它们的相似度。样本数为r，维度为n，第i个样本和第i个样本夹角余弦公式如下：

这个值在0到1之间，值越大，夹角越小，说明越相似。

另外，传统的K近邻算法在计算距离的时候，不同维度的重要性考虑是一样的，但是有些时候应该是有重有轻的。例如在新闻分类中，实词要比虚词的重要性高很多，名词可能又比动词的重要性高一点。同样一个词出现在新闻标题或者段首就比出现在段中的重要性要高。可以考虑在每个维度上追加一个口作为权重系数，将公式3修改为如下公式：相应的公式1和2也可以做同样的处理。

2.3核函数距离度量

还有一种将核函数运用到距离度量的方法，其基本思想是将线性不可分的低维度特征向量映射到线性可分的高维度特征向量空间中，映射函数为ψ（x），则核函数KK（xi，yj）=ψ（xi）·ψ（xj）。常用的核函数有高斯核、多项核和线性核。相应的，距离公式变为如下：

在样本数据集的分布呈现非高斯分布和非椭圆分布时，使用核函数的距离度量，在分类精度上往往优于传统的距离度量，尤其在one-class异常检测问题上。

2.4归一化处理

最后，在计算距离的时候还要考虑一个归一化问题。当一个实例的不同维度的数值由于量纲单位不同或者特征不同导致大小范围差异很大。如果不做归一化处理，则可能出现某个维度的数值因为很小，其变化信息就会淹没在另一个维度的大数值中几乎不起作用。常见的归一化处理有以下几种：

3分类决策规则

3.1传统分类决策规则

这样，决定待测点的分类就不仅仅是考虑哪个类的数量多了，还要综合考虑它们离待测点的距离因素。采用加权法之后，如图2的情况，待测点的类别很可能就属于圆形了。因为尽管虚线圆圈内圆形数量不占优势，但加权考虑距离后胜出。

4计算复杂度的解决

K近邻算法是一种惰性算法，该算法不会提前训练样本，而是等到要进行预测时才进行数据计算。因为每次预测时要计算待预测样本和每一个训练样本的距离，而且要对距离进行排序找到最近的K个样本。当训练样本数大、特征向量维数很高时计算复杂度高，对内存和系统资源的开销比较大，从而导致算法效率不高。为此，我们要从样本数筛选、维度降低和搜索空间优化三个方面来考虑解决方案。

4.1样本数筛选

当样本数量很多时，为了减少计算量，我们可以对样本进行挑选。简单的挑选原则就是选择有代表性的，保证不同类别的样本数量比较均衡。但这些原则比较主观随意，很难操作。具有可操作性的减少训练样本数量的方法有剪辑法和压缩法两种。剪辑法的思路是去掉那些会造成错误分类的样本或者被其他类别样本包围着的样本;而压缩法的思路是考虑到处于决策边界附近的样本比远离决策边界的样本對分类起的作用更大，从而将远离决策边界的样本去掉。文献【11】给出了一种筛选样本数的方法，具体做法如下：首先确定一个来自类1的样本点xio然后找出离点xi1，最近的且属于类2的样本点xi1，即xi1=NN（xio），如此交替迭代，有xi，j+1=NN（xij），直到两个样本彼此互为最近邻就终止迭代。这些交替来自两类的最近邻序列就构成了样本xio的最近邻链。最后设置一个阈值，只保留每条最近邻链中的最后一条或者几条链中的样本点，其余样本点都去掉，从而得到一个较小的训练样本集。

4.2维度降低

有些业务领域例如图像处理或者文本处理会涉及很高的维度，如果不做降维处理而直接使用K近邻算法会使得计算的空间复杂度和时间复杂度急剧上升，占用大量的计算机内存和CPU运行时间，甚至导致计算不可行。所以，对于使用K近邻算法的高维数据通常都要进行降维处理。

降维的方式通常有两种，一种叫作特征选择，即从m个特征中直接去除掉一些不太相关的或者冗余的特征，最后保留n个特征的方法。这里n

特征提取的方法很多，主要有主成分分析PCA（PrincipalComponent Analysis），独立成分分析、线型判别分析等。最常用的是PCA，它是通过对原始变量的相关矩阵或协方差矩阵内部结构的研究，将多个变量转换为少数几个综合变量即主成分的降维方法。具体算法思想是数据从原来的坐标转换到了新的坐标系，第一个新坐标轴的选择是原始数据中方差最大的方向，第二个新坐标轴的选择和第一个坐标轴正交且具有最大方差的方向，如此重复直到找到第n个新坐标轴。n值可以通过设定累加方差达到了总方差的一个很大比例，例如90%来确定。通常n远远小于m，所以PCA方法可以通过损失很少的信息来换取维度的大幅度降低。PCA的具体算法步骤往往要用到线性代数中计算协方差矩阵的特征值和特征向量来完成。

4.3搜索空间优化

传统的K近邻算法采用线性扫描，即当要预测分类时需要实时的计算待测点和每一个训练样本点的距离，才能得到距离最近的前K个点，一旦数据量大计算非常耗时。为了提高搜索效率，有一些优化搜索空间的方法可以提高搜索效率。

比较常用的有Kd树（K-dimensionaltree）。Kd树的思想类似与索引、二分法查找的思想，它把整个多维空间划分为特定的几个部分，将搜索锁定到部分特定空间内，从而减少搜索范围和次数，节省搜索时间。它首先需要构建一个二叉树，将所有的训练样本点均衡的分布到这个树上。虽然构造这个二叉树也要一些时间，但这是在实时预测之前就已经完成的工作，不占用预测时间。然后在正式预测时就开始搜索，不同于线型扫描的全数遍历，它一开始从根节点搜索，通过与节点的坐标值比较决定其继续往左还是往右分支继续查找，直到叶节点。这时得到的叶结点只能算“当前最近点”，需要继续“回溯”到父节点及其另外一个分支去查找是否有更近的点，这个过程一直“回溯”到根节点才结束，最后得到的“当前最近点”才是真正的最近点。通过这种搜索法使得时间复杂度从传统线性扫描的O（N）降低到了O（logN），大大提高了效率。Kd树更适合解决样本数很多的情况，而对维度很高的情况解决效率并不高。

另一种常用的搜索法叫ball树，不像Kd树依赖坐标轴划分矩形空间，ball树通过球体来进行空间分割。相较Kd树，它的主要优势是在处理数据集分布不均匀，维度很高的问题时效率仍然很高，同时还支持距离度量使用核函数的情况。

5总结

K近邻算法借鉴了空间分类思想，通过将特征值映射到多维空间，再根据不同数据的类别属性来判断待测样本和哪一类最相似。算法虽然很简单，但是在一些细节的设计上还是有很多环节需要注意。本文从K值选择、距离度量、分类决策规则和计算复杂度解决等多个方面对该算法进行了剖析。

随便看

科学优质学术资源、百科知识分享平台，免费提供知识科普、生活经验分享、中外学术论文、各类范文、学术文献、教学资料、学术期刊、会议、报纸、杂志、工具书等各类资源检索、在线阅读和软件app下载服务。