1.0 算法介绍
1.1 基本思想
kNN是最简单的机器算法之一，其基本原理通过对某个例的若干特征进行分析，进而对该个例的进行归类，通过对该类别的先验认知加深对个例的理解。简单举例，当我们去蛋糕店时，看到棕咖色的蛋糕一般情况下都会自动认为这个蛋糕是巧克力味道的，粉红色的蛋糕会认为是草莓味的，白色的蛋糕是奶油味的，等等。这里，每个蛋糕就是一个个例，特征就是颜色。由于对蛋糕味道的判断是基于先验认知（即记忆）进行推断的，因此kNN也叫memory based reasoning，MBR法。
1.2 应用场景
基于上述买蛋糕的场景可以发现，kNN一般用来对未知事物进行分类或者预测。而通过划分类别，有时也可以作为降维的一种手段。
1.3 算法原理
kNN的原理简言之就是“近朱者赤，近墨者黑”。通过比较个例与先验已知样本的紧密程度，进而对个例进行判断。简单理解就是看一个人邻近往来的是朱者多还是墨者多，如果朱者多则这个人可能也是个朱者，反之亦然。
kNN算法中，对于邻近的描述就是通过距离进行的，这里的距离一般默认为欧式空间距离。使用曼哈顿距离或其他自定义的距离形式完全取决于个人实际需求。
当然，要判断朱者多还是墨者多，应该给定一个具体的界限范围，否则有可能就计不清数量了。这个界限可以是限定数量，即距离最近的k个人，也可以是限定距离，即距离为r以内的所有人。
2.0 算法实现
2.1 伪码实现
Step 0：准备数据，包括但不限于检查数据（如分类or连续、量纲差异、量级差异、数据有效性/准确性、分布形式等），数据转换（如标准化、哑变量化等），分割数据为训练集和测试集等；
Step 1：模型训练。通过训练集建立样本特征与类别的映射关系；
Step 2：计算距离。计算测试集中的每个未分类个体与训练集中所有样本的距离；
Step 3：选择近邻。若以数量为限，选择与未分类个体最近的k个样本；若以距离为限，选择距未分类个体半径r以内的所有样本；
Step 4：类别统计。统计未分类个体的近邻类别，一般按照投票法进行，即取众数；若连续变量时则取平均数。
Step 5：分类判断。将近邻中频次最多的类别赋予个体。
2.2 python算法演示
（算法的手动实现就略过了，本质就是算距离和排序，这里直接演示调用sklearn实现）
2.2.1 按数量寻找近邻 KNeighborsClassifier
from sklearn import datasets
from sklearn.model_selection import train_test_split
from sklearn.neighbors import KNeighborsClassifier
from sklearn.neighbors import RadiusNeighborsClassifier
from sklearn.metrics import accuracy_score
from sklearn.preprocessing import StandardScaler
"""准备数据"""
cancers = datasets.load_breast_cancer() #导入数据集，sklearn自带数据集，此外还有iris，boston等数据集
X = cancers['data'] #特征值
y = cancers['target'] #类别标签
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.25, random_state=20) #
train_test_split将数据集随机分割为训练集和测试集，test_size为测试集比例，random_state为随机种子
kNC = KNeighborsClassifier(n_neighbors=5) #类的实例化，设置近邻数量，默认n_neighbors=5
kNC.fit(X_train, y_train) #模型训练
y_predict_kNC = kNC.predict(X_test) #模型预测：计算距离、筛选近邻、统计类别、预测类别
accuracy_score(y_test, y_predict_kNC) #结果评价，准确率0.9300699300699301，调整n_neighbors的值，可得不同结果
2.2.2 按半径寻找近邻 RadiusNeighborsClassifier
rNC = RadiusNeighborsClassifier(radius=10) #类的实例化，默认半径radius=1
rNC.fit(X_train, y_train) #模型训练
y_predict_rNC = rNC.predict(X_test) #模型预测
accuracy_score(y_test, y_predict_rNC)
上段代码中，到y_predict_rNC这一步会报出错误 ValueError: No neighbors found for test samples [0, 1, 2,...]，意思是测试集中的这些个例在半径r内没有找到近邻。因此需要放大radius。可使用NearestNeighbors查看测试个例与近邻的距离。
2.2.3 查看近邻信息 NearestNeighbors
from sklearn.neighbors import NearestNeighbors
NN = NearestNeighbors(n_neighbors=3).fit(X_test)
NN.kneighbors(X_train[:1]) #查看测试集中第一个个例的最近3个近邻
上段代码的最终返回结果为 (array([[10.34234317, 12.30153886, 12.46914998]]), array([[183, 335, 115]]))，其中包含了两个array。array([[10.34234317, 12.30153886, 12.46914998]]是三个近邻与个例的距离，array([[183, 335, 115]])是这三个近邻的索引号。可以发现最近的距离都在10以上，这就说明了2.2.2中以半径为10找不到近邻的原因。
事实上，这个样本中，个例间的距离离散程度比较大，比如X_train[115:116]这个个例与其最近近邻的距离都达到1100以上。此时如果要使用半径查找近邻则需要将radius设置在1100以上。而个例X_train[:1]与近邻的距离仅在12左右，说明数据整体是分布非常不均匀的，这种情况下用半径法可能难以达到较高的预测准确性，此时就要考虑使用其他分类方法或对数据进行标准化。（注:RadiusNeighborsClassifier(radius=1200)时，准确率为0.7552447552447552）
