机器学习——K近邻算法（KNN）及其python实现

参考视频与文献：

/video/BV1HX4y137TN/?spm_id_from=333.788&vd_source=77c874a500ef21df351103560dada737

统计学习方法（第二版）李航（编著）

k近邻法（k-nearest neighbor，k-NN）是一种基本分类与回归方法。k近邻法的输入为实例的特征向量，对应于特征空间的点；输出为实例的类别，可以取多类。k近邻法假设给定一个训练数据集，其中的实例类别已定。分类时，对新的实例，根据其k个最近邻的训练实例的类别，通过多数表决等方式进行预测。因此，k近邻法不具有显式的学习过程。k近邻法实际上利用训练数据集对特征向量空间进行划分，并作为其分类的“模型”。k值的选择、距离度量及分类决策规则是k近邻法的三个基本要素。

k值的选择会对k近邻法的结果产生重大影响。

如果选择较小的k值，就相当于用较小的邻域中的训练实例进行预测，“学习”的近似误差（approximation error)会减小，只有与输入实例较近的（相似的）训练实例才会对预测结果起作用。但缺点是“学习”的估计误差(estimation error)会增大，预测结果会对近邻的实例点非常敏感。如果邻近的实例点恰巧是噪声，预测就会出错。换句话说，k值的减小就意味着整体模型变得复杂，容易发生过拟合。

如果选择较大的k值，就相当于用较大邻域中的训练实例进行预测。其优点是可以减少学习的估计误差，但缺点是学习的近似误差会增大。这时与输入实例较远的（不相似的）训练实例也会对预测起作用，使预测发生错误。k值的增大就意味着整体的模型变得简单。

如果k=N，那么无论输入实例是什么，都将简单地预测它属于在训练实例中最多的类。这时，模型过于简单，完全忽略训练实例中的大量有用信息，是不可取的。

在应用中，k值一般取一个比较小的数值。通常采用交叉验证法来选取最优的k值。

此时K=3，待确定的样本寻找离它最近的三个样本

程序如下：

import numpy as npimport operator'''trainData - 训练集 N,DtestData - 测试 1,Dlabels - 训练集标签'''# k一般取奇数def knn(trainData, testData, labels, k):# 计算训练样本的行数rowSize = trainData.shape[0]# 计算训练样本和测试样本的差值diff = np.tile(testData, (rowSize, 1)) - trainData # 把测试样本复制N份，然后与训练样本相减# 计算差值的平方和sqrDiff = diff ** 2 # 计算欧氏距离sqrDiffSum = sqrDiff.sum(axis=1) # 沿着D的维度求和# 计算距离distances = sqrDiffSum ** 0.5# 对所得的距离从低到高进行排序sortDistance = distances.argsort() # 返回的输入数据的位置count = {}for i in range(k):vote = labels[sortDistance[i]]# print(vote)count[vote] = count.get(vote, 0) + 1# 对类别出现的频数从高到低进行排序sortCount = sorted(count.items(), key=operator.itemgetter(1), reverse=True)# 返回出现频数最高的类别return sortCount[0][0]file_data = 'iris.data'# 数据读取data = np.loadtxt(file_data,dtype = float, delimiter = ',',usecols=(0,1,2,3)) # 取出输入数据前4列lab = np.loadtxt(file_data,dtype = str, delimiter = ',',usecols=(4)) # 取出输入数据最后一列# 分为训练集和测试集和N = 150N_train = 100N_test = 50perm = np.random.permutation(N)index_train = perm[:N_train]index_test = perm[N_train:]data_train = data[index_train,:]lab_train = lab[index_train]data_test = data[index_test,:]lab_test = lab[index_test]# 参数设定k= 5n_right = 0for i in range(N_test):test = data_test[i,:]det = knn(data_train, test, lab_train, k)if det == lab_test[i]:n_right = n_right+1print('Sample %d lab_ture = %s lab_det = %s'%(i,lab_test[i],det))# 结果分析print('Accuracy = %.2f %%'%(n_right*100/N_test))

KNN算法的优势和劣势

了解KNN算法的优势和劣势，可以帮助我们在选择学习算法的时候做出更加明智的决定。那我们就来看看KNN算法都有哪些优势以及其缺陷所在！

KNN算法优点

简单易用，相比其他算法，KNN算是比较简洁明了的算法。即使没有很高的数学基础也能搞清楚它的原理。

模型训练时间快，上面说到KNN算法是惰性的，这里也就不再过多讲述。

预测效果好。

对异常值不敏感

KNN算法缺点

对内存要求较高，因为该算法存储了所有训练数据

预测阶段可能很慢

对不相关的功能和数据规模敏感

简单得说，当需要使用分类算法，且数据比较大的时候就可以尝试使用KNN算法进行分类了。