【机器学习】通俗的k-近邻算法算法解析和应用
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 算法按照距离最近的三部电影的类型，决定未知电影的类型，而这三部电影全是爱情片，因此我们判定未知电影是爱情片。
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-近邻（距离为矩阵差异值累加和），不理想。
上一个是用L1：曼哈顿距离，绝对值里两个样本相减, L2：计算欧氏距离
