1、模型原理
（一）原理
1、原理：是一种常用的监督学习方法，给定测试样本，基于某种距离度量找出训练集中与其最靠近的k个训练样本，然后基于这k个“邻居”的信息来进行预测。也有无监督的最近邻，暂不讨论。
2、判定方法主要有两种：
（1）在分类任务中的可使用“投票法”，即选择这k个样本中出现最多的类别标记作为预测结果；
（2）在回归任务中可使用“平均法”，即将这k个样本的标记平均值作为预测结果。
（3）还可以根据距离远近，对样本进行加权，实现加权平均或加权投票。
（二）注意点：
1、距离度量方法不同，找到的“近邻”也可能有显著区别，进而导致分类结果不同。通常是用欧式距离，即平方和开根号。
2、k在其中是一个相当重要的参数，k取值不同时，分类结果会有显著不同。
3、
（三）相关概念
1、“维度灾难”，如果样本的属性维度过多，在这种高维情况下，会出现数据样本稀疏（不密集，太过分散），距离计算困难等问题，这是所有机器学习方法共同面对的问题，被称为维度灾难。
2、由于这种情况，就需要进行降维。在低维空间中保持样本点间的距离不变，最简单的是对原始的高维空间进行线性变换，主成分分析就是最常见的一种线性降维方法。
有时，需要非线性映射才能找到恰当的低维嵌入，就会采用比如“核技巧”等非线性降维方法。
这里引申出来了“主成分分析”方法，可以在下面做补充。
（四）Python实现步骤
（1）计算已知类别数据集中的每个点依次执行以下操作；
（2）按照距离递增次序排序（越来越大）；
（3）选取与当前点距离最小的k个点；
（4）确定前k个点所在类别的出现频率；
（5）返回前k个点出现频率最高的类别作为当前点的预测分类
最近邻算法，是基于输入样本的，它和其他算法不一样，最近邻不会试图去构造一个泛化的模型（即，它的思路不是去拟合出一个含有各种参数的函数，然后把新的数据带入就可以得到新的结果），而只是去简单的使用输入训练集的所有数据，通过测算距离，来实现分类或回归。
分为KNN分类（KNeighborsClassifier）和KNN（KNeighborsRegressor）回归两种，一种是预测属性（离散值），一种是预测数值（连续值）。
与它对应的还有，通过设置半径R来进行分类和回归的，RadiusNeighborsClassifier和RadiusNeighborsRegressor。当用户确定了一个半径之后，这些在半径之内的点都会被考虑。
当我们需要训练的数据不那么规范的时候RadiusNeighborsClassifier （RN）会是一个更好的选择，对于一些高维空间，RN的效率会受到影响，这也是一种“维度之殇”了吧。
2、Python3中sklearn-KNN的代码实现
第一，sklearn中的KNN包源代码（未查到，以后补充）
第二，sklearn中的KNN包，有几个可调参数，及每个参数代表的意义
KNeighborsClassifier( n_neighbors=5, weights=’uniform’, algorithm=’auto’, leaf_size=30, p=2, metric=’minkowski’, metric_params=None, n_jobs=1, **kwargs )
n_neighbors，即选择k值，较大的k值可以容忍较多的噪声，但是会使得分类的结果变的不那么精确；但样本不平衡时，一个类样本容量很大，其他样本容量很小，导致输入新样本时，该样本邻近中大样本占多数，因此可以采取权值的方法（和样本距离小的邻近权值大）来改进，减少k值选择对结果的影响；可以通过循环来尝试不同的k值的效果。
weights，即权重设置，‘uniform’和‘distance’，对每个点赋予同样的权重，或者根据距离远近，赋予不同的权重（距离越远权重越小）。
algorithm，即搜索最近邻算法的选择，包括ball_tree、kd_tree、brute和auto。
brute代表Brute Force算法，就是一个最原始（蛮力）邻居搜索做法，Brute Force在寻找邻居时，会把输入的点同所有样本中的点做一个距离计算，然后再排序选择最近的点。
kd_tree代表KD树算法，为了解决BF算法效率低下的问题，人们提出了很多树形结构的算法，树形结构的主要贡献在于，它们一般通过事先的合理组织，降低了我们搜索中的开销，也就是使用树形结构的算法，我们在搜索时可以不用每个样本都去计算距离了，这无疑降低了很多的开销。在不太高的维度（小于20）下，KD树的效果是很不错的，不过当维度走向更高时，KD树的效率也会随之下降，这也呼应了我们之前提到的“维度之殇”的问题。
ball_tree代表Ball Tree算法，KD-Tree是为了解决Brute Force的效率问题，那么Ball-Tree也就是为了解决KD-Tree在高维情况下的效率不佳的另一个做法了，Ball树在构建的时候，比起KD树要复杂许多，不过在最后的搜索过程中，其表现就会非常好。
三者的选取：样本≤30，用BF；样本较大，但维度≤20，用KD_tree；维度更多的，用ball tree。
参考：知乎回答：KDtree和Ball Tree的区别
默认值是auto，在auto下，将会从你给定的测试数据当中选择最终性能最好的哪一个算法。leaf_size，设置一个数值，什么时候切换到BF暴力求解，默认是30。
metric ，用于树的距离度量。默认'minkowski与P = 2（即欧氏度量）。
第三，KNN的基本操作
from sklearn.neighbors import KNeighborsClassifier
knn ＝ KNeighborsClassifier(n_neighbors=6) #设置knn中的参数，并赋予某变量
knn.fit(x,y) #导入训练集，进行模型训练，x是数据，y是标签
y_pred = knn.predict(X_new) #带入新样本进行分类预测
如何判断准确率？那只能是把有标签的数据划分为训练集、测试集，然后看它预测的准确率。
from sklearn.model_selection import train_test_split #调用了sklearn中进行测试集和训练集分类的函数
X_train,X_test,y_train,y_test = train_test_split(X,y,test_size=0.2,random_state=42,stratify=y)
knn.score(X_test,y_test) # .score，就是测试准确度用的
具体的用法如下：
fit(x,y) #导入数据
get_params([deep]) #获取此估算器的参数
kneighbors([X, n_neighbors, return_distance]) #找到一个点的n个邻居，并返回距离值
kneighbors_graph([X, n_neighbors, mode]) # 计算X中的点的k-邻居的（加权）图
predict(X) #预测提供的数据的分类标签
predict_proba(X) #返回测试数据X的概率估计。
score(X, y[, sample_weight]) #返回给定测试数据上的平均精确度
set_params(**params) #设置此估算器的参数
取不同k值时，计算准确度
#取不同k值的效率图：
#创建一个数组储存训练和测试数据的精确度
neighbors = np.arange(1, 9)
train_accuracy = np.empty(len(neighbors))
test_accuracy = np.empty(len(neighbors))
# 循环对k进行赋值
for i, k in enumerate(neighbors):
# Setup a k-NN Classifier with k neighbors: knn
knn = KNeighborsClassifier(n_neighbors=k)
# Fit the classifier to the training data
knn.fit(X_train,y_train)
#计算训练集的准确度
train_accuracy[i] = knn.score(X_train, y_train)
#计算测试集的准确度
test_accuracy[i] = knn.score(X_test, y_test)
用一个循环对
一个简单的小例子
import numpy as np
from sklearn import neighbors
knn = neighbors.KNeighborsClassifier() #取得knn分类器
data = np.array([[3,104],[2,100],[1,81],[101,10],[99,5],[98,2]]) #data对应着打斗次数和接吻次数
labels = np.array([1,1,1,2,2,2]) #labels则是对应Romance和Action
knn.fit(data,labels) #导入数据进行训练
print(knn.predict([18,90]))
一点注意
拿《机器学习实战》中第二章KNN部分的约会网站数据进行了测试，发现虽然直接用的是结果类别标签数据‘largeDoses’、‘smallDoses’、‘didntLike’，未进行类别变量的转换，但在模型预测时，可以正确执行预测，结果直接为‘didntLike’等。
3、参考资料
刘建平博客中关于KNN的部分：
K近邻法(KNN)原理小结
scikit-learn K近邻法类库使用小结
以及ML：Scikit-Learn 学习笔记--- Nearest Neighbors 最近邻 1-3篇
参考的两篇帖子，NumPy 和 sklearn入门,以及 ML神器：sklearn的快速使用。
里面提到的几个点很好，比如为什么不用Python自带的数组list，而使用Numpy的array。
比如，sklearn中各个算法有统一的API接口，各个算法的一般实现流程是：
step1. 数据加载和预处理
step2. 定义分类器, 比如： lr_model = LogisticRegression()
step3. 使用训练集训练模型 ： lr_model.fit(X,Y)
step4. 使用训练好的模型进行预测： y_pred = lr_model.predict(X_test)
step5. 对模型进行性能评估：lr_model.score(X_test, y_test)
引申问题
1、计算样本间的差异有多大，也就是样本间距离。涉及到如何衡量距离。
2、排序问题，最经典的算法问题了。
这应该都有专门的代码。
