k近邻法(k-nearest neighbor, k-NN)是1967年由Cover T和Hart P提出的一种基本分类与回归方法。它的工作原理是：存在一个样本数据集合，也称作为训练样本集，并且样本集中每个数据都存在标签，即我们知道样本集中每一个数据与所属分类的对应关系。输入没有标签的新数据后，将新的数据的每个特征与样本集中数据对应的特征进行比较，然后算法提取样本最相似数据(最近邻)的分类标签。一般来说，我们只选择样本数据集中前k个最相似的数据，这就是k-近邻算法中k的出处，通常k是不大于20的整数。最后，选择k个最相似数据中出现次数最多的分类，作为新数据的分类。
k近邻算法
输入：训练数据集
其中， 为实例的特征向量，
为实例的类别，
;实例特征向量
;
输出：实例所属的类
.
(1)根据给定的距离度量，在训练集中找出与
最邻近的
个点，涵盖这
个点的
的邻域记作
;
(2)在中根据分类决策规则（如多数表决）决定
的类别
:
在上式中，为指示函数，即当
时，
为1，否则
为0.
k近邻模型由三个基本要素组成：距离度量，k值选择，分类决策规则
距离度量
距离选择有很多种，常用的距离函数有：
1、明考斯基距离
2、曼哈顿距离
3、Cityblock 距离
4、欧几里德距离(欧氏距离)
5、Canberra 距离
...
目前使用最多的距离计算公式为欧式距离，也是常用的向量距离计算方法。
欧式距离
计算两个物体直接的距离/相似度
K近邻模型的特征空间一般是n维实数向量空间 。使用的距离是欧氏距离，但也可以是其它距离。设特征空间
X是n维实数向量空间
，
,
的
距离定义为
这里。当
时称为欧氏距离，即
当时，称为曼哈顿距离，即
当时，它是各个坐标距离的最大值.
关于k取值
k对算法影响：
k值得选择会对k近邻算法的结果产生重大影响。
如果选择的k值较小，就相当于用较小的的邻域中的训练实例进行预测。此时预测的结果会对近邻的实例点非常敏感。
如果选择较大的k值，就相当于在较大的邻域中训练实例进行预测。此时，与输入实例较远的训练实例也会对预测起作用，使预测发生错误。
在使用k-NN算法的时候,k值一般会选择偶数，如1，3，5，7，9...。选择奇数是为了防止平手。K取1容易出现过拟合。
通过交叉验证选择合适的k，通常我们把它归类为“调参”。
交叉验证
把训练数据进一步分为训练数据(Training Data)和验证集合(Validation Data)。选择在验证数据里最好的超参数组合。
例：
K折交叉验证（K-fold Cross Validation），把训练数据分为K部分，一部分作为验证数据，另外(K-1)部分作为训练数据。
交叉验证中需要注意的点：
- 千万不要用测试数据来调参；
- 数据量越少，可以适当增加折数。
特征的缩放
- 线性归一化(Min-max Normalization)
- 标准差标准化(Z-score Normalization)
coding time
from sklearn import datasets
from collections import Counter
from sklearn.model_selection import train_test_split
import numpy as np
def euc_dis(instance1, instance2):
"""
计算两个样本直接的欧氏距离
"""
dist = np.sqrt(sum((instance1 - instance2)**2))
return dist
def knn_classify(X,y, testinstance, k):
dists = [euc_dis(x, testinstance) for x in X]
kneighbors = np.argsort(dists)[:k] # 排序，截取前K
count = Counter(y[kneighbors]) # 计算数量
return count.most_common()[0][0] # 返回出现最多的label
# 导入iris数据
iris = datasets.load_iris()
X = iris.data
y = iris.target
X_train, X_test, y_train, y_test = train_test_split(X, y, random_state=2003)
# 结果预测
predict = [knn_classify(X_train, y_train, data, 3) for data in X_test]
correct = np.count_nonzero((predict==y_test)==True) # 预测正确数量
print('Accuracy is : %.3f' % (correct/len(X_test))) # 正确率
sklearn k近邻算法
k-NN最大的作用是可以随时间序列计算，即样本不能一次性获取只能随着时间一个一个得到的时候，k-NN能发挥它的价值。至于其他的特点，它能做的，很多方法都能做；其他能做的它却做不了。
......
- 参考文献
1、李航，统计学习方法，清华大学出版社，2012
