一、KNN算法基本思想

K近邻算法，即KNN算法，可用于分类。该算法的基本思想非常简单：给定带标签的训练样本集，对于测试样本，根据事先设定的距离度量计算测试样本与每一个训练样本的距离，选出K个距离最近的训练样本，然后基于投票的方式将测试样本标记为k个训练样本中出现次数最多的类别。

KNN算法在训练阶段不产生模型，仅仅是将样本保存起来，训练的时间开销为零，是懒惰学习的典型代表。

二、KNN算法调优策略

• 距离度量的选择

选择合适的距离度量很重要，常用的距离有欧式距离、曼哈顿距离等。此后会有详细的距离度量的文章。

• k的选择

k的选择非常重要。以下图为例，不同的k，分类结果会有显著的差别。

以二分类为例，图中蓝色加号代表正类，紫色减号代表负类，橙色三角形是待判样本。取k=3时，待判样本被标记为正类，取k=11时，待判样本被标识为负类，取k=15时，待判样本被标记为正类。

一般情况下，我们可将样本分为训练集和测试集，多尝试几组k值，通过测试样本的分类效果来确定合适的k值。

• 样本不平横问题

考虑如下情况。

以上图为例，针对这种样本不平衡的情况，很容易就会将测试样本标识为正类。我们可对负类样本进行重采用，对正类样本进行欠采样，其实本质就是调整样本权重。

三、优缺点分析

KNN算法简单有效，对数据的分布没有要求，训练阶段仅是保存数据，时间开销为零。由于KNN算法不产生模型，它在发现特征之间的关系上的能力有限，另外就是分类阶段很慢，因为该算法需要计算测试样本与每一个训练样本的距离，需要大量的内存，而且名义变量要额外处理。