KNN (K-Nearest Neighbors) 概述

近邻算法 KNN 是常用的监督型算法，可用于分类或者回归。预测新样本的标签的时候，根据样本邻域内的 K 个训练数据的标签来决定新样本属于哪个类。值得注意的是，KNN 的名称与聚类算法 K-means 听上去类似，但两者是完全不同类型的算法：KNN 是监督型算法，K-means 是非监督型聚类算法。

同时，近邻算法是非参数算法，即，算法对样本数据本身不做假设，模型的结果是由数据本身来决定的。与之相对应的是参数算法，例如回归模型，我们预先需要假定回归模型的类型，例如线性回归，对象是回归等。这些假定是由参数决定的。

近邻算法不需要对数据进行大量的训练，因此算法执行的速度是很快的。

近邻算法的三大要素是：K值，点之间距离的定义，分类决策规则。

主要优点有：

算法简单易懂，不依赖于高深的数学知识。训练速度快。对异常值不敏感。

主要缺点：

因为算法存储所有数据的信息，占用内存较大。对参数 K 敏感。KNN 算法描述

近邻算法用于分类时，选择新样本邻域内与其特征值最接近的 K 个样本，选择最多的类别数作为新样本的类别。其中邻域的选取依赖于距离度量的定义。

近邻算法用于回归时，选取邻域内 K 个样本的平均值作为新样本的回归预测值。

距离的度量有很多种，常用的有欧氏距离:

d(x,y)=(x1−y1)2+...+(xn−yn)2−−−−−−−−−−−−−−−−−−−−−−√=∑i=1n(xi−yi)2−−−−−−−−−−√

曼哈顿距离：

d(x,y)=|x1−y1|+...+|xn−yn|=∑i=1n|xi−yi|

闵可夫斯基距离(Minkowski Distance):

d(x,y)=[(|x1−y1|)p+...+(|xn−yn|)p]1p=[∑i=1n(|xi−yi|)p]1p,p≥1

关于 K 的选择，没有固定的算法。

选择较小的 K 值，训练数据的误差较小，但对于测试数据容易过度拟合，因为选择的邻域较小，同时模型的泛化能力较差。

选择较大的 K 值，模型变得简单，返化能力强，但同时训练数据的误差增大。因为邻域变大，距离预测样本较远的样本也会对预测结果有影响。

在实际应用中，我们常使用交叉验证来确定最佳的 K 值。即将数据拆分为训练数据和验证数据，逐步增大 K 的值，并计算验证数据的方差。一般情况下，随着 K 值得增加，验证数据得方差呈 V 形，验证数据方差随着 K 的增加首先减小，而后突破临界值以后反而会上升。这个临界值就是最佳的 K 值。

KNN 算法复杂度

理论上，对于每个新样本，我们需要计算遍历所有样本，计算他们的特征值到新样本特征值的距离，从而找到在新样本领域内的样本。这个算法 (brute force) 虽然简单，但是当样本特征值数量巨大的情况下，算法的效率很低。

常用的解决方法是 KD 树算法，和球树算法。

KNN 用于数据的降维处理

KNN 的概念被用于数据的降维处理。基于 KNN 概念的 Uniform Manifold Approximation and Projection (UMAP) 是一种数据降维方法，尽量保持了局部和全局的样本数据结构，相对于其他降维方法运行时间较短。

UMAP 使用梯度法 stochastic gradient descent 优化结果。它首先计算高维空间中点和点之间的距离，将他们映射到低维空间，并且计算低维空间中点之间的距离。然后利用 stochastic gradient descent 最小化距离之间的差别。算法的具体细节参见文章：

KNN 程序实现：scikit

Nearest Neighbor 广泛用于监督型(分类问题和回归问题)和非监督型模型中，应用实例包括手写字体识别，卫星图像识别等。下面以 scikit-learn 为例讲述KNN在分类问题中的应用。

scikit-learn 中的 Nearest Neighbor 分类模型有两类：

KNeighborsClassifier： 基于新样本周围的k个点的信息，这里k 是用户给定的常数。这是最常用的模型。

RadiusNeighborsClassifier：基于新样本周围半径为r 的范围内的点，这里r 是用户给定的常数。

当样本分布不均匀时，RadiusNeighborsClassifier 是更好的选择，给定半径r，新样本周围在给定半径r 的范围内的点数随样本密度分布而变化。另外，新样本的标签可以是周围选定样本标签的平均，也可以是随距离而变化的加权平均。

在 scikit-learn 中的模型调用同样分为四步：

第一步，建立一个模型框架，并设置所需的参数。

# Construct model; the paramters are set as default values;>>> model = KNeighborsClassifier(n_neighbors = 3, weight='uniform', algorithm='auto', metric='minkowski')

第二步，用建立好的模型框架拟合训练数据。模型将会选择最优的参数。

# Fit the model to the data;>>> model.fit(X_train,y_train)

第三步，用建立好的模型框架拟合训练数据。模型将会选择最优的参数。

# Use the model to predict the labels of test data;>>> y_pred_lr = model.predict(X_test)

第四步，计算模型的性能指标。

# Check the performance of model by using training data;>>> model.score(X_train,y_train)