K最近邻与线性分类器（上）

图像分类

图像分类的基本任务就是将图片分类，那如何进行图片分类呢？图片是不可能直接当作输入传递给我们的机器学习任务的，一个通用的做法就是将图片转换成一张巨大的数字表单。这时候输入有了，那么就可以使用机器学习的算法从所有种类中，给这个表单选定一个标签。 图像分类的难题在于我们所说的语义鸿沟问题

我们人眼所看到的是一个完整的图像画面，但是计算机所看到的是一张巨大的数字表单，表单的数字反映的是亮度以及每个单点三基色的权值。图像分类难点就在于要去处理这个巨大的表单，然后根据其进行分类。 下面列出了一些其它方面的挑战：

• 视角变化：摄像机可以从多角度来拍摄物体。
• 光线变化 ：发光物体其它光线的影响
• 形变：很多东西的形状并非一成不变，会有很大变化。
• 遮挡：目标物体可能被挡住。有时候只有物体的一小部分（可以小到几个像素）是可见的。
• 背景干扰：物体可能混入背景之中，使之难以被辨认。
• 类内差异：一类物体的个体之间的外形差异很大，比如椅子。这一类物体有许多不同的对象，每个都有自己的外形。 数据驱动方法：怎么写一个识别猫的算法？随着网络的发展，在网络上可以找到许许多多猫的图片，就可以以此作为训练集，训练出识别猫的模型，当有新的图片时，我们就可以参考训练数据，给出答案。

NN

CIFAR-10数据集

该数据集共有60000张彩色图像，这些图像是32*32，分为10个类，每类6000张图。这里面有50000张用于训练，构成了5个训练批，每一批10000张图；另外10000用于测试，单独构成一批。

Nearest Neighbor算法

现在我们用CIFAR-10的50000张图片作训练集，训练模型，然后Nearest Neighbor算法用测试图片和训练集中每一张图片去比较，然后将它认为最近邻的一个样本的类别来决定待分样本所属的类别。 那最近邻是怎么判断的呢？最简单的方式就是曼哈顿距离算法，即L1距离算法，计算方式如下：

distance

下面就是使用L1距离的Nearest Neighbor分类器的实现套路：

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

其实我们可以看到，分类器的时间复杂度是和样本的大小有关系的，它是一个线性的减慢的过程。近邻算法分类器速度加快的方法，可以用一个近似近邻算法FLANN。 距离选择：计算向量间的距离有很多种方法，另一个常用的方法是L2距离，从几何学的角度，可以理解为它在计算两个向量间的欧式距离。

k-Nearest Neighbor分类器

为什么只用最相似的1张图片的标签来作为测试图像的标签呢？这不是很奇怪吗！是的，使用k-Nearest Neighbor分类器就能做得更好。它的思想很简单：与其只找最相近的那1个图片的标签，我们找最相似的k个图片的标签，然后让他们针对测试图片进行投票，最后把票数最高的标签作为对测试图片的预测。所以当k=1的时候，k-Nearest Neighbor分类器就是Nearest Neighbor分类器。从直观感受上就可以看到，更高的k值可以让分类的效果更平滑，使得分类器对于异常值更鲁棒。 设置参数

• Choose hyperparameters that work best on the data
• Split data into train and test, choose hyperparameters that work best on test data
• Split data into train, val, and test; choose hyperparameters on val and evaluate on test
• Cross-Validation: Split data into folds, try each fold as validation and average the results

knn处理图片分类的缺点

• 效率很低
• 像素上的距离度量难以表达图像信息

knn总结

• 在图像分类中，由被标注了分类标签的图像组成的集合，要求算法能预测没有标签的图像的分类标签，
• 距离评价方式和K是超参数
• 用交叉验证选择超参数，仅在测试集上运行一次。