【机器学习】通俗的k-近邻算法算法解析和应用

【机器学习】通俗的k-近邻算法算法解析和应用

文章目录 1 概述 2 KNN 场景 3 KNN 原理 4 实例：改进约会网站的配对效果 5 算法总结 6 KNN算法的优缺点 7 图像分类应用 1 概述

k-近邻（kNN, k-NearestNeighbor）算法是一种基本分类与回归方法，我们这里只讨论分类问题中的 k-近邻算法。

一句话总结: 近朱者赤近墨者黑！

k 近邻算法的输入为实例的特征向量，对应于特征空间的点；输出为实例的类别，可以取多类。k 近邻算法假设给定一个训练数据集，其中的实例类别已定。分类时，对新的实例，根据其 k 个最近邻的训练实例的类别，通过多数表决等方式进行预测。因此，k近邻算法不具有显式的学习过程。

k 近邻算法实际上利用训练数据集对特征向量空间进行划分，并作为其分类的“模型”。 k值的选择、距离度量以及分类决策规则是k近邻算法的三个基本要素。

2 KNN 场景

电影可以按照题材分类，那么如何区分 动作片 和 爱情片 呢？

动作片: 打斗次数更多 爱情片: 亲吻次数更多 基于电影中的亲吻、打斗出现的次数，使用 k-近邻算法构造程序，就可以自动划分电影的题材类型。

现在根据上面我们得到的样本集中所有电影与未知电影的距离，按照距离递增排序，可以找到 k 个距离最近的电影。 假定 k=3，则三个最靠近的电影依次是， Hes Not Really into Dudes 、 Beautiful Woman 和 California Man。 knn 算法按照距离最近的三部电影的类型，决定未知电影的类型，而这三部电影全是爱情片，因此我们判定未知电影是爱情片。

3 KNN 原理

KNN 工作原理 假设有一个带有标签的样本数据集（训练样本集），其中包含每条数据与所属分类的对应关系。 输入没有标签的新数据后，将新数据的每个特征与样本集中数据对应的特征进行比较。 计算新数据与样本数据集中每条数据的距离。 对求得的所有距离进行排序（从小到大，越小表示越相似）。 取前 k （k 一般小于等于 20 ）个样本数据对应的分类标签。 求 k 个数据中出现次数最多的分类标签作为新数据的分类。 KNN 通俗理解 给定一个训练数据集，对新的输入实例，在训练数据集中找到与该实例最邻近的 k 个实例，这 k 个实例的多数属于某个类，就把该输入实例分为这个类。

KNN 开发流程 收集数据: 任何方法 准备数据: 距离计算所需要的数值，最好是结构化的数据格式 分析数据: 任何方法 训练算法: 此步骤不适用于 k-近邻算法 测试算法: 计算错误率 使用算法: 输入样本数据和结构化的输出结果，然后运行 k-近邻算法判断输入数据分类属于哪个分类，最后对计算出的分类执行后续处理 KNN 算法特点

优点: 精度高、对异常值不敏感、无数据输入假定 缺点: 计算复杂度高、空间复杂度高 适用数据范围: 数值型和标称型 4 实例：改进约会网站的配对效果

题目描述：海伦喜欢在在线约会网站寻找适合自己的对象，但是她不是喜欢每一个人。她发现交往过三种类型的人：

1.不喜欢的人

2.魅力一般的人

3.极具魅力的人

所以需要对网站的对象归入恰当的分类。她周一到周五喜欢魅力一般的人，而周末则更喜欢极具魅力的人。所以需要根据数据来分类

准备数据： 数据在文本datingTestSet.txt中，每个样本占据一行，总共1000行，每个样本有3个特征：

每年获得的飞行常客里程数 玩视频游戏所消耗的时间 每周消费的冰淇淋的公升

那么这些数据从文本读取后需要改写成分类器可以接受的格式。输出为样本矩阵和类标签向量

def file2matrix(filename): fr = open(filename) arrayOlines = fr.readlines() numberOfLines = len(arrayOlines) returnMat = zeros((numberOfLines,3)) classLabelVector=[] index = 0 for line in arrayOLines: line = line.strip() #去回车 listFromLine = line.split(\t) #以\t分割 returnMat[index,:] = listFromLine[0:3] classLabelVector.append(int(listFromLine[-1])) index+=1 return returnMat,classLabelVector

其实python处理文本文件很容易。 reload(kNN)

datingDataMat,datingLabels = kNN.file2matrix(datingTestSet2.txt)

datingDataMat array([[ 4.09200000e+04, 8.32697600e+00, 9.53952000e-01], [ 1.44880000e+04, 7.15346900e+00, 1.67390400e+00], [ 2.60520000e+04, 1.44187100e+00, 8.05124000e-01], …, [ 2.65750000e+04, 1.06501020e+01, 8.66627000e-01], [ 4.81110000e+04, 9.13452800e+00, 7.28045000e-01], [ 4.37570000e+04, 7.88260100e+00, 1.33244600e+00]])

接下来需要分析数据，使用Matplotlib创建散点图

import matplotlib.pyplot as plt fig = plt.figure() ax = fig.add_subplot(111) ax.scatter(datingDataMat[:,1],datingDataMat[:,2]) #颜色以及尺寸标识了数据点属性类别 散点图使用datingDataMat矩阵的第二，第三列数据代表玩视频游戏所耗时间百分比，每周所消耗的冰淇凌公升数

由于没有样本分类的特征值。很难看到任何有用的数据模型信息。一般用采用色彩或其他记号标记不同分类

而展现的数据图如下： 但是如果标识了三个不同的样本分类区域，采用第1.2列效果会更直观

对数据进行归一化处理： 如果我们对数据样本直接进行计算距离。(0-67)^2 + (20000-32000)^2 + (1.1-0.1)^2数字最大属性对结果影响很大。

也就是说飞行常客对于结果的影响远远大于其他特征。但是我们应该认为这3个属性同等重要。所i有需要数值归一化我们可以将任意值转化到

0到1之间 newValue = (oldValue-min)/(max-min)

def autoNorm(dataSet): minVals = dataSet.min(0) maxVals = dataSet.max(0) ranges = maxVals – minVals normDataSet = zeros(shape(dataSet)) m = dataSet.shape[0] normDataSet = dataSet – tile(minVals,(m,1)) normDataSet = normDataSet/tile(ranges,(m,1)) return normDataSet,ranges,minVals

原来的数据为 array([[ 4.09200000e+04, 8.32697600e+00, 9.53952000e-01], [ 1.44880000e+04, 7.15346900e+00, 1.67390400e+00], [ 2.60520000e+04, 1.44187100e+00, 8.05124000e-01], …, [ 2.65750000e+04, 1.06501020e+01, 8.66627000e-01], [ 4.81110000e+04, 9.13452800e+00, 7.28045000e-01], [ 4.37570000e+04, 7.88260100e+00, 1.33244600e+00]]) 进过处理后的数据为

array([[ 0.44832535, 0.39805139, 0.56233353], [ 0.15873259, 0.34195467, 0.98724416], [ 0.28542943, 0.06892523, 0.47449629], …, [ 0.29115949, 0.50910294, 0.51079493], [ 0.52711097, 0.43665451, 0.4290048 ], [ 0.47940793, 0.3768091 , 0.78571804]]) 使用完成程序测试分类 机器学习的重要工作就是评估算法的正确率，通常按照上述的算法如果正确分类，那么可以使用这个软件来处理约会网站提供的约会名单了。

但是还需要测试当前分类器的性能，我们以测试错误率为主对这个程序测试程序如下：

def datingClassTest(): hoRation = 0.10 datingDataMat,datingLabels = file2matrix(E:\pythonProject\ML\datingTestSet2.txt) normMat,ranges,minVals = autoNorm(datingDataMat) m = normMat.shape[0] numTestVecs = int(m*hoRation) errorCount = 0.0 for i in range(numTestVecs): classifierResult = classify0(normMat[i,:],normMat[numTestVecs:m,:],datingLabels[numTestVecs:m],3) print (“the classifier came back with %d,the real answer is %d” %(classifierResult,datingLabels[i])) if(classifierResult!=datingLabels[i]):errorCount+=1.0 print “the total error rate is %f” % (errorCount/float(numTestVecs)) 5 算法总结

简单来说: 通过距离度量来计算查询点（query point）与每个训练数据点的距离，然后选出与查询点（query point）相近的K个最邻点（K nearest neighbors），使用分类决策来选出对应的标签来作为该查询点的标签。

NN 三要素

K, K的取值 对查询点标签影响显著（效果拔群）。k值小的时候 近似误差小，估计误差大。 k值大 近似误差大，估计误差小。 如果选择较小的 k 值，就相当于用较小的邻域中的训练实例进行预测，“学习”的近似误差（approximation error）会减小，只有与输入实例较近的（相似的）训练实例才会对预测结果起作用。但缺点是“学习”的估计误差（estimation error）会增大，预测结果会对近邻的实例点非常敏感。如果邻近的实例点恰巧是噪声，预测就会出错。换句话说，k 值的减小就意味着整体模型变得复杂，容易发生过拟合。 如果选择较大的 k 值，就相当于用较大的邻域中的训练实例进行预测。其优点是可以减少学习的估计误差。但缺点是学习的近似误差会增大。这时与输入实例较远的（不相似的）训练实例也会对预测起作用，使预测发生错误。 k 值的增大就意味着整体的模型变得简单。 太大太小都不太好，可以用交叉验证（cross validation）来选取适合的k值。 近似误差和估计误差，请看这里: https://www.zhihu.com/question/60793482 距离度量 Metric/Distance Measure 距离度量 通常为 欧式距离（Euclidean distance），还可以是 Minkowski 距离 或者 曼哈顿距离。也可以是 地理空间中的一些距离公式。（更多细节可以参看 sklearn 中 valid_metric 部分） 分类决策 （decision rule） 分类决策 在 分类问题中 通常为通过少数服从多数 来选取票数最多的标签，在回归问题中通常为 K个最邻点的标签的平均值。 算法: （sklearn 上有三种）

Brute Force 暴力计算/线性扫描 KD Tree 使用二叉树根据数据维度来平分参数空间。 Ball Tree 使用一系列的超球体来平分训练数据集。 树结构的算法都有建树和查询两个过程。Brute Force 没有建树的过程。 算法特点: 优点: High Accuracy， No Assumption on data， not sensitive to outliers 缺点: 时间和空间复杂度 高 适用范围: continuous values and nominal values 相似同源产物: radius neighbors 根据制定的半径来找寻邻点 影响算法因素: N 数据集样本数量(number of samples)， D 数据维度 (number of features) 总消耗: Brute Force: O[DN^2] 此处考虑的是最蠢的方法: 把所有训练的点之间的距离都算一遍。当然有更快的实现方式, 比如 O(ND + kN) 和 O(NDK) , 最快的是 O[DN] 。感兴趣的可以阅读这个链接: k-NN computational complexity KD Tree: O[DN log(N)] Ball Tree: O[DN log(N)] 跟 KD Tree 处于相同的数量级，虽然建树时间会比 KD Tree 久一点，但是在高结构的数据，甚至是高纬度的数据中，查询速度有很大的提升。 查询所需消耗: Brute Force: O[DN] KD Tree: 当维度比较小的时候， 比如 D<20, O[Dlog(N)] 。相反，将会趋向于 O[DN] Ball Tree: O[Dlog(N)] 当数据集比较小的时候，比如 N<30的时候，Brute Force 更有优势。 Intrinsic Dimensionality(本征维数) 和 Sparsity（稀疏度） 数据的 intrinsic dimensionality 是指数据所在的流形的维数 d < D , 在参数空间可以是线性或非线性的。稀疏度指的是数据填充参数空间的程度(这与“稀疏”矩阵中使用的概念不同, 数据矩阵可能没有零项, 但是从这个意义上来讲,它的结构 仍然是 “稀疏” 的)。 Brute Force 的查询时间不受影响。 对于 KD Tree 和 Ball Tree的查询时间, 较小本征维数且更稀疏的数据集的查询时间更快。KD Tree 的改善由于通过坐标轴来平分参数空间的自身特性 没有Ball Tree 显著。 k的取值 (k 个邻点) Brute Force 的查询时间基本不受影响。 但是对于 KD Tree 和 Ball Tree , k越大，查询时间越慢。 k 在N的占比较大的时候，使用 Brute Force 比较好。 Number of Query Points （查询点数量， 即测试数据的数量） 查询点较少的时候用Brute Force。查询点较多的时候可以使用树结构算法。 关于 sklearn 中模型的一些额外干货: 如果KD Tree，Ball Tree 和Brute Force 应用场景傻傻分不清楚，可以直接使用 含有algorithm=auto的模组。 algorithm=auto 自动为您选择最优算法。 有 regressor 和 classifier 可以来选择。 metric/distance measure 可以选择。 另外距离 可以通过weight 来加权。 leaf size 对KD Tree 和 Ball Tree 的影响 建树时间: leaf size 比较大的时候，建树时间也就快点。 查询时间: leaf size 太大太小都不太好。如果leaf size 趋向于 N（训练数据的样本数量），算法其实就是 brute force了。如果leaf size 太小了，趋向于1，那查询的时候 遍历树的时间就会大大增加。leaf size 建议的数值是 30，也就是默认值。 内存: leaf size 变大，存树结构的内存变小。 Nearest Centroid Classifier 分类决策是哪个标签的质心与测试点最近，就选哪个标签。 该模型假设在所有维度中方差相同。 是一个很好的base line。 进阶版: Nearest Shrunken Centroid 可以通过shrink_threshold来设置。 作用: 可以移除某些影响分类的特征，例如移除噪音特征的影响。

6 KNN算法的优缺点

KNN算法的优点：算法简单易于实现，而且通过对K的选择可具备丢噪音数据的健壮性，我们来举一个例子，下图中鼠标未知是什么类型的样本？其实我们一看就应该认为它是红三角的，因为它距离红三角比较近，但是这有一个问题就是，假如我们设置K=1，那么此时的未知样本就被认为是蓝方块。这就是蓝色方块噪音对我们的影响。所以我们可以通过增加K，来达到去除噪音的作用，我们可以设置K=4，那么算法就会认为未知样本是红三角了，这就是增加K达到去噪的作用，这是KNN算法的优点。

未知未知样本是什么？KNN算法的缺点：首先算法需要大量的空间存储，算法复杂性高，需要将未知实例和所有的已知实例进行比较，当一类样本数量过大占主导地位的时候，K也设为很大的时候，新的未知实例容易被数量大的样本主导，但有可能这个未知实例并不接近这个最多的样本类别，它可能更接近其它类别，但这个问题也是可以解决的，为了解决这个问题，根据样本设置权重，比如权重为1/d(d为距离)，距离越近权重越大。

7 图像分类应用

如何计算： 结果：利用K-近邻（距离为矩阵差异值累加和），不理想。

import numpy as np class NearestNeighbor(object): def __init__(self): pass def train(self, X, y): #X是NXD的数组，其中每一行代表一个样本，Y是N行的一维数组，对应X的标签 # 最近邻分类器就是简单的记住所有的数据 self.Xtr = X self.ytr = y def predict(self, X): #X是NXD的数组，其中每一行代表一个图片样本 #看一下测试数据有多少行 num_test = X.shape[0] # 确认输出的结果类型符合输入的类型 Ypred = np.zeros(num_test, dtype = self.ytr.dtype) # 循环每一行，也就是每一个样本 for i in xrange(num_test): # 找到和第i个测试图片距离最近的训练图片 # 计算他们的L1距离 distances = np.sum(np.abs(self.Xtr – X[i,:]), axis = 1) min_index = np.argmin(distances) # 拿到最小那个距离的索引 Ypred[i] = self.ytr[min_index] # 预测样本的标签，其实就是跟他最近的训练数据样本的标签 return Ypred

上一个是用L1：曼哈顿距离，绝对值里两个样本相减, L2：计算欧氏距离

distances = np.sqrt(np.sum(np.square(self.Xtr – X[i,:]), axis = 1))