【机器学习】通俗的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，则三个最靠近的电影依次是， He's 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))