CS31n学习笔记<二>k-NN与线性分类器

2018-08-20

字数统计: 1.7k字 | 阅读时长: 6分

× 文章目录

1. 1、前言
2. 2、K-NN
3. 3、线性分类器

1、前言

　　任务：图像分类问题，就是对于输入的图像数据，根据已有的分类标签集合，选出合适的标签对齐进行分类标记，属于监督学习的范畴。虽然该问题对人来说非常简单，但却是计算机视觉领域的核心问题，计算机视觉领域中很多看似不同的问题（比如物体检测和分割），都可以被归结为图像分类问题。
　　难点：对于计算机来说，一张图像是由[Hight,Width,Channel]组成的张量(Tensor)，张量中的元素为像素值大小，大小在0-255之间的整型，其中0表示全黑，255表示全白。因此图像分类的目标就是：把这些上百万的数字变成一个简单的标签(label)。可想而知，计算机视觉算法所应对的困难与挑战有多大。

　　1). 视角变化（Viewpoint variation）
　　2). 大小变化（Scale variation）
　　3). 形变（Deformation）
　　4). 遮挡（Occlusion）
　　5). 光照条件（Illumination conditions）
　　6). 背景干扰（Background clutter）
　　7). 类内差异（Intra-class variation）
　　算法及流程：要应对如此多的变化，采用单一的规则是不可能解决图像分类的问题。那我们不如给计算机“看”大量各种各样猫的照片，然后让计算机自己学习并识别。这种基于大量已标注数据，通过计算机学习来完成某种任务的方法，称为：数据驱动方法。其完整流程包含：输入训练集（已标注数据），学习分类器或者模型，评价分类器质量（验证集）。

2、K-NN

　　K-NN没有显式训练过程，给定一个训练集，对于新输入的测试数据，在训练集中找到与该实例最近邻的K个实例，其中类别数最多的类为该实例的预测标签。
　　K-NN三要素：距离度量、K值选择以及分类决策。

2.1 距离度量

　　如何定义两个实例(图像)间的距离？是一种可选择的超参数。
　　L1 distance（曼哈顿距离）： $d_1(I_1,I_2) = \sum_{p}|I_1^p-I_2^p|$
　　L2 distance（欧氏距离）： $d_2(I_1,I_2) = \sqrt{\sum_{p}|I_1^p-I_2^p|^2}$
　　Lp distance（闵可夫斯基距离）： $d_p(I_1,I_2) = (\sum_{p}|I_1^p-I_2^p|^p)^\frac{1}{p}$
　　$L_\infty$ distance（切比雪夫距离）： $d_\infty(I_1,I_2) = \max_{p}|I_1^p-I_2^p|$
　　马氏距离： $d(\vec x,\vec y)=\sqrt{(\vec x-\vec y)^TS^{-1}(\vec x-\vec y)}$
　　余弦距离： $d(\vec x,\vec y)=1 - \frac{\vec x .\vec y}{|\vec x||\vec y|}$
　　汉明距离：字符串x变成y所需要的最小的替换次数
　　数据集：CIFAR-10 10类 50000训练图片，10000测试图片
　　衡量两张图片的相似度，对于图像的L1距离计算：
　　　　
　　选择L1距离的K-NN代码如下：

import numpy as np

class NearestNeighbor(object):
  def __init__(self):
    pass

  def train(self, X, y):
    """ X is N x D where each row is an example. Y is 1-dimension of size N """
    # the nearest neighbor classifier simply remembers all the training data
    self.Xtr = X
    self.ytr = y

  def predict(self, X):
    """ X is N x D where each row is an example we wish to predict label for """
    num_test = X.shape[0]
    # lets make sure that the output type matches the input type
    Ypred = np.zeros(num_test, dtype = self.ytr.dtype)

    # loop over all test rows
    for i in xrange(num_test):
      # find the nearest training image to the i'th test image
      # using the L1 distance (sum of absolute value differences)
      distances = np.sum(np.abs(self.Xtr - X[i,:]), axis = 1)
      min_index = np.argmin(distances) # get the index with smallest distance
      Ypred[i] = self.ytr[min_index] # predict the label of the nearest example

    return Ypred

2.2 k值的选择

　　另一个超参数(人为设定的参数)，k值选择会对算法结果产生非常大的影响。
　　如果k值较小，相当于用较小的领域中的训练实例进行预测，“学习”的近似误差会减小，只有与输入实例较近的训练实例才会对预测结果起作用。但缺点是估计误差会增大，即预测结果对近邻点实例非常敏感，若近邻实例为噪声就会导致错误的预测结果。极端地，若k=1，预测结果为最近领点所属类别。
　　如果k值较大，相当于用较大的领域中的训练实例进行预测，优点在于“学习”的估计误差会减小，但缺点是近似误差会增大，这时与输入实例较远的（不相似的）训练实例也会起作用。极端地，若k=N，模型过于简单，完全忽略了训练集中有用的信息，无论输入实例是什么，预测结果均为训练集中类别最多的类。
　　那么K值如何选择呢？简单的，尝试各种不同的参数，选择效果最好的。但是，如果只是在测试集评价效果最好是不可取的。一是因为测试集为最终模型泛化性能的评价而存在的；二是因为很可能会在测试集上过拟合了，无法在其他新数据达到很好泛化结果。
　　因此，常采用留一法或k折交叉验证法（5折/10折居多）来选取k值。

2.3 分类决策

　　常采用多数表决法，等价于经验风险最小化。

2.4 缺点　　

　　1). 速度慢，K-NN测试速度随着训练集规模线性增长，CNN相反：训练时间长，测试时间短（固定的计算）。
　　2). 复杂度高，如何降低最近邻分类器的计算复杂度也是研究的热门，在预处理阶段建立kd树或使用k-means聚类等，加速在数据集中查找最近邻的效率。近似最近邻算法（Approximate Nearest Neighbor (ANN) algorithms）如(FLANN)，牺牲了一定的最近邻精度来换取空间/时间复杂度的降低。
　　3). 不适用于维数大、容量大的数据，最近邻分类器在某些情况下可能会是一种好的选择，特别是数据维度比较低、数据量较小的时候，但是对于图像分类问题来说它基本不适合。原因之一是图像是高维物体（包含很多像素），在高维空间中进行距离运算通常不可靠。

3、线性分类器

　　相比于K-NN，线性分类器是基于参数化方法得到分类结果。
　　
　　$score = f(x, W) = Wx+b$　Ｘ为输入图像3072个输入神经元[3072, 1]，Ｗ为权重[10, 3072]（学习的参数）$score$[10, 1]为预测得分。b[10, 1]为偏置。
　　具体计算例子：
　　
　　将在CIFAIR数据集训练得到的W可视化，10类的特征权重如下图：
　　
　　a）马头和汽车存在左右方向，可看出对应参数出现两个头的情况。
　　问题：
　　a）对于线分类器，最难分类的数据样本是哪些？
　　实质为不同位置的颜色带权混合，因此针对不同位置、不同纹理难识别。