内容
①kNN概述
② 距离测量
③数据归一化
④具体代码
⑤ 相关优化
⑥ 思考
①kNN概述
kNN算法的思想：就是在训练集中数据和标签已知的情况下，输入测试数据，将测试数据的特征与训练集中对应的特征进行相互比较，找到训练集中与之最为相似的前k个数据，则该测试数据对应的类别就是K个数据中出现次数最多的那个分类，其算法的描述为：
1）计算测试数据与各个训练数据之间的距离；
2）按照距离的递增关系进行排序；
3）选取距离最近的k个点；
4）确定前k个点所在类别的出现频率；
5）返回前k个点中出现频率最高的类别作为测试数据的预测分类。
② 距离测量
样本空间中两个点之间的距离度量表示的是两个样本点之间的相似程度：距离越小，表示相似程度越高；相反，距离越大，相似程度越低。在kNN算法中，常用的距离有三种，分别为曼哈顿距离、欧式距离和闵可夫斯基距离。
1）闵可夫斯基距离（Minkowski distance）
闵可夫斯基距离不是一个距离，而是一类距离的定义。其数学定义如下：
其中p可以随意取值，可以是负数，也可以是正数，或是无穷大。当p=1时，又叫做曼哈顿距离，当p=2时，又叫做欧式距离，当p=∞时，又叫做契比雪夫距离。
2）欧式距离
欧式距离其实就是空间中两点间的距离，是我们最常用的一种距离计算公式。因为计算是基于各维度特征的绝对数值，所以欧氏度量需要保证各维度指标在相同的刻度级别，比如对身高（cm）和体重（kg）两个单位不同的指标使用欧式距离可能使结果失效。所以在使用欧氏距离时，应该尽量将特征向量的每个分量归一化，以减少因为特征值的刻度级别不同所带来的干扰。
3）曼哈顿距离
想象你在曼哈顿要从一个十字路口开车到另外一个十字路口，驾驶距离是两点间的直线距离吗？显然不是，除非你能穿越大楼。实际驾驶距离就是这个“曼哈顿距离”。而这也是曼哈顿距离名称的来源，曼哈顿距离也称为城市街区距离(City Blockdistance)。具体选用哪种距离公式，我们也将其作为其中一种参数，在后面介绍另外一种调参方法的时候所提及。
③数据归一化
1）最值归一化：所有数据归一到0-1之间
2）均值方差归一化：把所有数据归一到均值0方差1的分布中
注意：当测试数据集被归一化时，训练数据集的均值和方差被减去并除以
④具体代码
# 用鸢尾花数据集演示数据归一化
import numpy as np
from sklearn import datasets
iris = datasets.load_iris()
X = iris.data
y = iris.target
# 创建测试集和训练集
from sklearn.model_selection import train_test_split
X_train, X_test, y_train, y_test = train_test_split(iris.data, iris.target, test_size=0.2, random_state=666)
# 对训练集归一化（均值方差归一化）
from sklearn.preprocessing import StandardScaler # 数据预处理包里加载数据归一化
standardScalar = StandardScaler()
standardScalar.fit(X_train) # 放入数据
X_train = standardScalar.transform(X_train) # 归一化处理
X_test_standard = standardScalar.transform(X_test)
# 使用归一化后的数据进行knn分类
from sklearn.neighbors import KNeighborsClassifier
knn_clf = KNeighborsClassifier(n_neighbors=3) # k取3
knn_clf.fit(X_train, y_train) # 传入归一化数据进行训练
print(knn_clf.score(X_test_standard, y_test)) # 分类准确度
输出结果：
⑤ 相关优化
1）最佳k值：
用循环求解
# 以鸢尾花数据集为例
import numpy as np
from sklearn import datasets
digits = datasets.load_digits()
X = digits.data
y = digits.target
from sklearn.model_selection import train_test_split
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=666)
from sklearn.neighbors import KNeighborsClassifier
# 循环解决
best_score = 0.0
best_k = -1
for k in range(1, 11):
knn_clf = KNeighborsClassifier(n_neighbors=k)
knn_clf.fit(X_train, y_train)
score = knn_clf.score(X_test, y_test)
if score > best_score:
best_k = k
best_score = score
print("best_k =", best_k)
print("best_score =", best_score)输出结果：
2）考虑距离权重（一般取距离的倒数，k=3）
如下图，如果是普通的kNN算法思路，获胜的应该是蓝色，但是如果考虑权重，红色获胜。
考虑距离权重可以很好地解决平票情况。
# 以鸢尾花数据集为例
import numpy as np
from sklearn import datasets
digits = datasets.load_digits()
X = digits.data
y = digits.target
from sklearn.model_selection import train_test_split
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=666)
from sklearn.neighbors import KNeighborsClassifier
# weights默认值是uniform（不考虑距离权重），distance（考虑距离权重）
best_score = 0.0
best_k = -1
best_method = ""
for method in ["uniform", "distance"]:
for k in range(1, 11):
knn_clf = KNeighborsClassifier(n_neighbors=k, weights=method)
knn_clf.fit(X_train, y_train)
score = knn_clf.score(X_test, y_test)
if score > best_score:
best_k = k
best_score = score
best_method = method
print("best_method =", best_method)
print("best_k =", best_k)
print("best_score =", best_score)输出结果：（这里最好的方法是不考虑距离权重）
⑥ 思考
1）缺点：
1.效率低下，如果训练集有m个样本，n个特征，则预测每一个新数据，需要O(m*n)。优化：使用树结构，KD-Tree，Ball-Tree（即使如此，效率还是很低）。
2.最终结果高度数据相关。
3.预测结果不具有可解释性。
4.维数灾难，随着维度的增加，看似相近的点之间距离越来越大。解决方法：降维。
2）优点：
1.天然的可以解决多分类问题。
2.思想简单，效果强大。
3.还可以解决回归问题。对于要预测的节点找到离他最近的几个节点，几个点的均值为预测值。
文章出处登录后可见！
