machine learning / 机器学习

K最临近分类器(K-Nearest Neighbor Classifier)

K最临近分类器(K-Nearest Neighbor Classifier)

当我们在处理图像分类问题时,有很多种方法,这里介绍一种最简单且便于理解的算法:K最临近分类器。

首先我先介绍一下最临近分类器(Nearest Neighbor Classifier)。

 

Nearest Neighbor Classifier:

假设我采用CIFAR-10图像分类数据集进行分类训练,这个训练集有10种分类和60000张32x32像素的彩色图片,每个图片被标记为其中1种类别。

IMG_256

我选择其中50000张图片用于训练,10000张图片用于测试。

Nearest Neighbor Classifier从测试集中选择一张图片作为测试图片,然后遍历训练集中的所有图片与测试图片进行比较计算,将计算结果中与测试图片最相近的训练图片所对应的类别标记为测试图片的类别。

那么这个比较计算的算法是怎么设计的?

L1距离:每张图片的宽和高是32像素、有RGB三个颜色通道,因此一张图片的数据维度是32x32x3,那么该算法将两张需要比较的图片表现为向量模式\[{{I}_{1}}\]和\[{{I}_{2}}\]。则有:

\[{{d}_{1}}({{I}_{1}},{{I}_{2}})=\sum\limits_{p}{\left| I_{1}^{p}-I_{2}^{p} \right|}\]

用一张图来更形象的说明上面这个公式的计算过程(以单颜色通道为例)

计算结果越小说明两张图相似度越高,计算结果越大说明两张图相似度越低。

 

代码实现:

 

 

# Xtr训练集的全部图片数据为(50000,32,32,3)

# Ytr训练集标记(50000,1)

Xtr, Ytr, Xte, Yte = load_CIFAR10('data/cifar10/') # 加载CIFAR10数据

# 扁平化所有图片到一维,即(32,32,3)这三个维度变成一个维度

Xtr_rows = Xtr.reshape(Xtr.shape[0], 32 * 32 * 3) # Xtr大小为50000 x 3072

Xte_rows = Xte.reshape(Xte.shape[0], 32 * 32 * 3) # Xte大小为10000 x 3072

nn = NearestNeighbor() # 创建一个最邻近分类器

nn.train(Xtr_rows, Ytr) # 训练分类器

Yte_predict = nn.predict(Xte_rows) # 预测测试集中图片的标记

# 输出分类器的准确度。Yte_predict == Yte会输出[True,False,False…]这样的结构,np.mean会统计结果为True的比例。

print 'accuracy: %f' % ( np.mean(Yte_predict == Yte) )

 

最邻近分类器实现:

import numpy as np

 

class NearestNeighbor(object):

  def __init__(self):

    pass

 

  def train(self, X, y):

    # X维度N x D。Y维度 1 x N。

    self.Xtr = X

    self.ytr = y

 

  def predict(self, X):

    num_test = X.shape[0]

    # 初始化输出对象

    Ypred = np.zeros(num_test, dtype = self.ytr.dtype)

 

    # 遍历测试集

    for i in xrange(num_test):

      # L1距离。训练集的所有行与测试集的第i行减法操作。

      distances = np.sum(np.abs(self.Xtr - X[i,:]), axis = 1)

   # 获取最短距离对应的行数

      min_index = np.argmin(distances) 

   # 获取对应的标记

      Ypred[i] = self.ytr[min_index] 

return Ypred

 

L2距离:

在最邻近算法中,除了L1距离算法以外,还有一些其他的算法,比如比较常用的L2算法:

\[{{d}_{2}}({{I}_{1}},{{I}_{2}})=\sqrt{\sum\limits_{p}{{{(I_{1}^{p}-I_{2}^{p})}^{2}}}}\]

代码实现:

distances = np.sqrt(np.sum(np.square(self.Xtr - X[i,:]), axis = 1))

注意np.sqrt在实际应用中是不需要的,因为开方是个单调函数,开方最小的项必然也就是不开方最小的项。少执行一步计算可以提高算法效率。

 

L1 VS L2:

假设有如下两组数据A=[1,0,0,0],B=[0.25,0.25,0.25,0.25]。去掉距离算法中的减法部分。

如果采用L1算法那么L1_A=L1_B

如果采用L2算法那么L2_A=1 L2_B=SQRT(0.0625+0.0625+0.0625+0.0625)=0.25,XB的L2小于L1,那么在最小化过程中,系统会更倾向于B。

同时我们可以发现,A中的0较多,意味着A的稀疏性较高,会直接把一些数据忽略掉(也许这些被忽略的数据实际有意义),而采用L2算法可以降低数据的稀疏性,让尽可能多的数据发挥作用,可以更好的防止过拟合的情况出现。

L1、L2的先验分布图(L1蓝色、L2红色):

图上我们可以看出L1对极端值更能容忍,而且倾向于稀疏。L2则没有。

 

K-Nearest Neighbor Classifier:

K-Nearest Neighbor Classifier表示从训练集中找到距离最近的k个图片,然后让它们投票,选出得票率最高的标记。当k=1时,即为Nearest Neighbor Classifier。