K-近邻算法以及图像分类应用

以下均为自己看视频做的笔记，自用，侵删！

K最近邻(k-Nearest Neighbor，KNN)分类算法，该方法的思路是：如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。

K-近邻算法步骤：

对于未知类别属性数据集中的点：

1. 计算已知类别数据集中的点与当前点的距离
2. 按照距离依次排序
3. 选取与当前点距离最小的K个点
4. 确定前K个点所在类别的出现概率
5. 返回前K个点出现频率最高的类别作为当前点预测分类。

概述：

• KNN 算法本身简单有效，它是一种 lazy-learning 算法。
• 分类器不需要使用训练集进行训练，训练时间复杂度为0。
• KNN 分类的计算复杂度和训练集中的文档数目成正比，也就是说，如果训练集中文档总数为 n，那么 KNN 的分类时间复杂度为O(n)。

K 值的选择，距离度量和分类决策规则是该算法的三个基本要素。

问题 该算法在分类时有个主要的不足是，当样本不平衡时，如一个类的样本容量很大，而其他类样本容量很小时，有可能导致当输入一个新样本时，该样本的 K 个邻居中大容量类的样本占多数。

解决 不同的样本给予不同权重项

如何计算：

结果 利用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))

超参数的选取

问题：

1.对于距离如何设定？

2.对于K近邻的K该如何选择？

3.如果有的话，其它的超参数该怎么设定呢？

测试集非常宝贵，只能最终的时候才能使用（所有模型的参数都确定下来之后）。（不能每次训练完之后，用测试集来调一下参数）

# 假设我们之前有 Xtr_rows, Ytr, Xte_rows, Yte 这几份数据
#  Xtr_rows 是 50,000 x 3072 的矩阵
Xval_rows = Xtr_rows[:1000, :] # 抽取前1000张作为评估集
Yval = Ytr[:1000]
Xtr_rows = Xtr_rows[1000:, :] # 其余的4900张作为训练集
Ytr = Ytr[1000:]

# 找到在评估集上表现做好的超参数
validation_accuracies = []
for k in [1, 3, 5, 10, 20, 50, 100]:

  # 使用确定的k值作用在评估集上
  nn = NearestNeighbor()
  nn.train(Xtr_rows, Ytr)
  # 这里假设我们有一个最近邻的类，可以把k值作为输入
  Yval_predict = nn.predict(Xval_rows, k = k)
  acc = np.mean(Yval_predict == Yval)
  print 'accuracy: %f' % (acc,)

  # 记录在评估集上每个k对应的准确率
  validation_accuracies.append((k, acc))
           

交差验证

（将训练集再分成两部分：一部分当作训练集，另一部分当作验证集，测试集最后用！），通过5次迭代的结果求平均，交差验证可以消除一些偏高或偏低的结果。

不同交差验证次数，得到的结果：

背景主导：

因为背景的作用，导致图像分类的不准确，所以我们不能用K-近邻来完成图像分类。因为不同的变化和原图具有相同的L2距离。

使用K-近邻：

1. 选取超参数调优的正确方法是：将原始训练集分为 训练集和 验证集 ，我们在验证集上尝试不同的超参数，最后保留表现最好那个。
2. 如果训练数据量不够： 使用交叉验证 交叉验证方法，它能帮助我们在选取最优超参数的时候减少噪音。
3. 一旦找到最优的超参数： 就让算法以该参数在测试集跑且只跑一次，并根据测试结果评价算法。
4. 最近邻分类器能够在CIFAR-10上得到将近40%的准确率。该算法简单易实现，但需要存储所有训练数据，并且在测试的时候过于耗费计算能力。
5. 最后，我们知道了仅仅使用L1和L2范数来进行像素比较是不够的，图像更多的是按照背景和颜色被分类，而不是语义主体分身。

使用注意：

1. 预处理你的数据：对你数据中的 特征进行归一化（normalize），让其具有 零平均值（zero mean）和 单位方差（unit variance）。
2. 如果数据是高维数据，考虑使用降维方法，比如PCA。
3. 将数据随机分入训练集和验证集。按照一般规律，70%-90% 数据作为训练集。
4. 在验证集上调优，尝试足够多的k值，尝试L1和L2两种范数计算方式。

本文参考：https://www.cnblogs.com/douzujun/p/9035923.html