1、什么是KNN

k近邻法（k-nearest neighbor, kNN）是一种基本分类与回归方法，其基本做法是：给定测试实例，基于某种距离度量找出训练集中与其最靠近的k个实例点，然后基于这k个最近邻的信息来进行预测。

通常，在分类任务中可使用“投票法”，即选择这k个实例中出现最多的标记类别作为预测结果；在回归任务中可使用“平均法”，即将这k个实例的实值输出标记的平均值作为预测结果；还可基于距离远近进行加权平均或加权投票，距离越近的实例权重越大。

k近邻法不具有显式的学习过程，事实上，它是懒惰学习（lazy learning）的著名代表，此类学习技术在训练阶段仅仅是把样本保存起来，训练时间开销为零，待收到测试样本后再进行处理。

本文只讨论分类问题中的k近邻法，下一篇文章将会介绍KNN分类的实际案例。

2、KNN的算思想

KNN（k-NearestNeighbor）又被称为近邻算法，它的核心思想是：物以类聚，人以群分

假设一个未知样本数据x需要归类，总共有ABC三个类别，那么离x距离最近的有k个邻居，这k个邻居里有k1个邻居属于A类，k2个邻居属于B类，k3个邻居属于C类，如果k1>k2>k3，那么x就属于A类，也就是说x的类别完全由邻居来推断出来。

所以我们可以总结出其算法步骤为：

计算测试对象到训练集中每个对象的距离按照距离的远近排序选取与当前测试对象最近的k的训练对象，作为该测试对象的邻居统计这k个邻居的类别频率k个邻居里频率最高的类别，即为测试对象的类别

我们可以简化为：找邻居 + 投票决定

3、KNN的优点与缺点

优点

非常简单的分类算法没有之一，人性化，易于理解，易于实现适合处理多分类问题，比如推荐用户

缺点

属于懒惰算法，时间复杂度较高，因为需要计算未知样本到所有已知样本的距离样本平衡度依赖高，当出现极端情况样本不平衡时，分类绝对会出现偏差可解释性差，无法给出类似决策树那样的规则4、KNN的应用范围

由KNN的自身属性所决定的，基于现有类别计算距离投票选择，所以不能发现新的类别，但对于固定类别，KNN的简单易用的特性就完全的显示出来了，在某些分类上，比SVM，决策树等有着并不逊色的性能。在进行固定类别分类的时候，模型选择的时可以以KNN作为基础标准进行模型选择，说不定会有意外的惊喜。目前KNN应用比较成熟的方向主要有，内容的推荐，文本的识别等。

5、KNN参数详解

KNN算法在实际应用时，最主要的参数主要有三个：距离算法的选择、K值的选择、投票时的权重计算

5.1距离算法的选择

目前主流的距离计算的算法主要有以下几种：

欧式距离：是应用最多的距离计算算法曼哈顿距离：应用相对较少，可在交叉验证中选择查看余弦距离：两个向量之间的夹角大小，主要用来计算文本相似性

5.2K值的选择

K值指的是，在进行分类投票时，选择多少距离最小的类别进行投票，K值的大小会对分类器的结果产生直接的影响，这个可以通过交叉验证确定最佳K值。

5.3投票时的权重计算

k近邻默认的投票方法是分类决策规则往往是多数表决，即由输入实例的k个邻近的训练实例中的多数类，决定输入实例的类。即在取出的K个分类中，出现最多的分类及分类的结果。

同时也可采用对K个临近的记录不同的距离进行加权，距离近的权重高，距离远的权重低来进行投票。常用的距离加权函数为高斯函数。