第3章
图像分类之KNN算法
本章将讲解一种最简单的图像分类算法，即K-最近邻算法（K-NearestNeighbor，KNN）。KNN算法的思想非常简单，其涉及的数学原理知识也很简单。本章希望以KNN容易理解的算法逻辑与相对容易的Python实现方式帮助读者快速构建一个属于自己的图像分类器。
本章的要点具体如下。
- KNN的基本介绍。
- 机器学习中KNN的实现方式。
- KNN实现图像分类。
3.1 KNN的理论基础与实现
3.1.1 理论知识
KNN被翻译为最近邻算法，顾名思义，找到最近的k个邻居，在前k个最近样本（k近邻）中选择最近的占比最高的类别作为预测类别。如果觉得这句话不好理解，那么我们可以通过一个简单示例（如图3-1所示）来进一步说明。
绿色圆（待预测的）要被赋予哪个类，是红色三角形还是蓝色四方形？如果k=3（实线所表示的圆），由于红色三角形所占比例为2/3，大于蓝色四方形所占的比例1/3，那么绿色圆将被赋予红色三角形那个类。如果k=5（虚线所表示的圆），由于蓝色四方形的比例为3/5大于红色三角形所占的比例2/5，那么绿色圆被赋予蓝色四方形类。
通过上述这个例子，我们可以简单总结出KNN算法的计算逻辑。
1）给定测试对象，计算它与训练集中每个对象的距离。
2）圈定距离最近的k个训练对象，作为测试对象的邻居。
3）根据这k个近邻对象所属的类别，找到占比最高的那个类别作为测试对象的预测类别。
在KNN算法中，我们发现有两个方面的因素会影响KNN算法的准确度：一个是计算测试对象与训练集中各个对象的距离，另一个因素就是k的选择。
这里先着重讲一下距离度量，后面的小节中我们将着重讲述如何选择k（超参数调优）。对于距离度量，一般使用两种比较常见的距离公式计算距离：曼哈顿距离和欧式距离。
（1）曼哈顿距离（Manhattan distance）
假设先只考虑两个点，第一个点的坐标为(x1, y1)，第二个点的坐标为(x2, y2)，那么，它们之间的曼哈顿距离就是| x1-x2 | + | y1-y2 |。
（2）欧式距离（Euclidean Metric）
以空间为基准的两点之间的最短距离。还是假设只有两个点，第一个点的坐标为(x1, y1)，第二个点的坐标为(x2, y2)，那么它们之间的欧式距离就是。
3.1.2 KNN的算法实现
3.1.1节简单讲解了KNN的核心思想以及距离度量，为了方便读者理解，接下来我们使用Python实现KNN算法。
本书使用的开发环境（开发环境的安装已经在第2章中介绍过）是Pycharm和Anaconda。
首先，我们打开Pycharm，新建一个Python项目，创建演示数据集，输入如下代码：
import numpy as np
import matplotlib.pyplot as plt
##给出训练数据以及对应的类别
def createDataSet():
group = np.array([[1.0,2.0],[1.2,0.1],[0.1,1.4],[0.3,3.5],[1.1,1.0],[0.5,1.5]])
labels = np.array(['A','A','B','B','A','B'])
return group,labels
if __name__=='__main__':
group,labels = createDataSet()
plt.scatter(group[labels=='A',0],group[labels=='A',1],color = 'r', marker='*')
#对于类别为A的数据集我们使用红色六角形表示
plt.scatter(group[labels=='B',0],group[labels=='B',1],color = 'g', marker='+')
#对于类别为B的数据集我们使用绿色十字形表示
plt.show()下面，我们对这段代码做一个详细的介绍，createDataSet用于创建训练数据集及其对应的类别，group对应的是二维训练数据集，分别对应x轴和y轴的数据。labels对应的是训练集的标签（类别），比如，[1.0, 2.0]这个数据对应的类别是“A”。
我们使用Matplotlib绘制图形，使读者能够更加直观地查看训练集的分布，其中scatter方法是用来绘制散点图的。关于Matplotlib库的用法（如果读者还不是很熟悉的话）可以参阅Matplotlib的基本用法。训练集的图形化展示效果如图3-2所示，对于类别为A的数据集我们使用红色五角形表示，对于类别为B的数据集我们使用绿色十字形表示，观察后可以发现，绿色十字形比较靠近屏幕的左侧；红色五角形比较靠近屏幕的右侧。
通过Matplotlib，读者可以很直观地分辨出左边部分的数据更倾向于绿色十字点，而右边的数据则更倾向于红色五角形点。
接下来我们看一下如何使用Python（基于欧拉距离）实现一个属于我们自己的KNN分类器。示例代码如下：
def kNN_classify(k,dis,X_train,x_train,Y_test):
assert dis == 'E' or dis == 'M', 'dis must E or M，E代表欧式距离，M代表曼哈顿距离'
num_test = Y_test.shape[0] #测试样本的数量
labellist = []
'''
使用欧拉公式作为距离度量
'''
if (dis == 'E'):
for i in range(num_test):
#实现欧式距离公式
distances = np.sqrt(np.sum(((X_train - np.tile(Y_test[i], (X_train.shape[0], 1))) ** 2), axis=1))
nearest_k = np.argsort(distances) #距离由小到大进行排序，并返回index值
topK = nearest_k[:k] #选取前k个距离
classCount = {}
for i in topK: #统计每个类别的个数
classCount[x_train[i]] = classCount.get(x_train[i],0) + 1
sortedClassCount = sorted(classCount.items(),key=operator.itemgetter(1),reverse=True)
labellist.append(sortedClassCount[0][0])
return np.array(labellist)
#使用曼哈顿公式作为距离度量
#读者自行补充完成轮到你来：
尝试模仿上述代码，通过对曼哈顿距离的理解实现曼哈顿距离度量的Python版本。
下面我们来测试下KNN算法的效果，输入如下代码：
if __name__ == '__main__':
group, labels = createDataSet()
y_test_pred = kNN_classify(1, 'E', group, labels, np.array([[1.0,2.1],[0.4,2.0]]))
print(y_test_pred) #打印输出['A' 'B']，和我们的判断是相同的需要注意的是，我们在输入测试集的时候，需要将其转换为Numpy的矩阵，否则系统会提示传入的参数是list类型，没有shape的方法。
3.2 图像分类识别预备知识
3.2.1 图像分类
首先，我们来看一下什么是图像分类问题。所谓的图像分类问题就是将已有的固定的分类标签集合中最合适的标签分配给输入的图像。下面通过一个简单的小例子来解释下什么是图像分类模型，以图3-3所示的猫的图片为例，图像分类模型读取该图片，并生成该图片属于集合{cat, dog, hat, mug}中各个标签的概率。需要注意的是，对于计算机来说，图像是一个由数字组成的巨大的三维数组。在这个猫的例子中，图像的大小是宽248像素，高400像素，有3个颜色通道，分别是红、绿和蓝（简称RGB）。如此，该图像就包含了248×400×3=297 600个数字，每个数字都是处于范围0～255之间的整型，其中0表示黑，255表示白。我们的任务就是将上百万的数字解析成人类可以理解的标签，比如“猫”。
图像分类的任务就是预测一个给定的图像包含了哪个分类标签（或者给出属于一系列不同标签的可能性）。图像是三维数组，数组元素是取值范围从0～255的整数。数组的尺寸是宽度×高度×3，其中3代表的是红、绿、蓝3个颜色通道。
3.2.2 图像预处理
在开始使用算法进行图像识别之前，良好的数据预处理能够很快达到事半功倍的效果。图像预处理不仅可以使得原始图像符合某种既定规则以便于进行后续的处理，而且可以帮助去除图像中的噪声。在后续讲解神经网络的时候我们还会了解到，数据预处理还可以帮助减少后续的运算量以及加速收敛。常用的图像预处理操作包括归一化、灰度变换、滤波变换以及各种形态学变换等，随着深度学习技术的发展，一些预处理方式已经融合到深度学习模型中，由于本书的重点放在深度学习的讲解上，因此这里只重点讲一下归一化。
归一化可用于保证所有维度上的数据都在一个变化幅度上。比如，在预测房价的例子中，假设房价由面积s和卧室数b决定，面积s在0～200之间，卧室数b在0～5之间，进行归一化的一个实例就是s=s/200，b=b/5。
通常我们可以使用两种方法来实现归一化：一种是最值归一化，比如将最大值归一化成1，最小值归一化成-1；或者将最大值归一化成1，最小值归一化成0。另一种是均值方差归一化，一般是将均值归一化成0，方差归一化成1。我们可以通过图3-4来看一组数据归一化后的效果。
3.3 KNN实战
3.3.1 KNN实现MNIST数据分类
我们前面使用了两节的内容来讲述KNN算法的计算逻辑以及它的Python实现思路，本节将提供两个实战案例，带领大家逐步走进图像识别。
1. MNIST数据集
为了方便大家理解，本节选择的数据集是一个比较经典的数据集—MNIST。MNIST数据集来自美国国家标准与技术研究所（ National Institute of Standards and Technolo，NIST）。训练集由250个人手写的数字构成，其中50%是高中学生，50%是人口普查的工作人员。测试数据集也是同样比例的手写数字数据。MNIST数据集是一个很经典且很常用的数据集（类似于图像处理中的“Hello World！”）。为了降低学习难度，我们先从这个最简单的图像数据集开始。
我们先来看一下如何读取MNIST数据集。由于MNIST是一个基本的数据集，因此我们可以直接使用PyTorch框架进行数据的下载与读取，示例代码如下：
import torch
from torch.utils.data import DataLoader
import torchvision.datasets as dsets
import torchvision.transforms as transforms
batch_size = 100
# MNIST dataset
train_dataset = dsets.MNIST(root = '/ml/pymnist', #选择数据的根目录
train = True, #选择训练集
transform = None, #不考虑使用任何数据预处理
download = True) #从网络上下载图片
test_dataset = dsets.MNIST(root = '/ml/pymnist', #选择数据的根目录
train = False, #选择测试集
transform = None, #不考虑使用任何数据预处理
download = True) #从网络上下载图片
#加载数据
train_loader = torch.utils.data.DataLoader(dataset = train_dataset,
batch_size = batch_size,
shuffle = True) #将数据打乱
test_loader = torch.utils.data.DataLoader(dataset = test_dataset,
batch_size = batch_size,
shuffle = True)train_dataset与test_dataset可以返回训练集数据、训练集标签、测试集数据以及测试集标签，训练集数据以及测试集数据都是n×m维的矩阵，这里的n是样本数（行数），m是特征数（列数）。训练数据集包含60 000个样本，测试数据集包含10 000个样本。在MNIST数据集中，每张图片均由28×28个像素点构成，每个像素点使用一个灰度值表示。在这里，我们将28×28的像素展开为一个一维的行向量，这些行向量就是图片数组里的行（每行784个值，或者说每行就代表了一张图片）。训练集标签以及测试标签包含了相应的目标变量，也就是手写数字的类标签（整数0～9）。
print("train_data:", train_dataset.train_data.size())
print("train_labels:", train_dataset.train_labels.size())
print("test_data:", test_dataset.test_data.size())
print("test_labels:", test_dataset.test_labels.size())得到的结果如下：
train_data: torch.Size([60000, 28, 28])
train_labels: torch.Size([60000]) #训练集标签的长度
test_data: torch.Size([10000, 28, 28])
test_labels: torch.Size([10000]) #测试集标签的长度我们一般不会直接使用train_dataset与test_dataset，在训练一个算法的时候（比如，神经网络），最好是对一个batch的数据进行操作，同时还需要对数据进行shuffle和并行加速等。对此，PyTorch提供了DataLoader以帮助我们实现这些功能。我们后面用到的数据都是基于DataLoader提供的。
首先，我们先来了解下MNIST中的图片看起来到底是什么，先对它们进行可视化处理。通过Matplotlib的imshow函数进行绘制，代码如下：
import matplotlib.pyplot as plt
digit = train_loader.dataset.train_data[0] #取第一个图片的数据
plt.imshow(digit,cmap=plt.cm.binary)
plt.show()
print(train_loader.dataset.train_labels[0]) #输出对应的标签，结果为5标签的输出结果是5，图3-5所显示的数字也是5。
2. KNN实现MNIST数字分类
在真正使用Python实现KNN算法之前，我们先来剖析一下思想，这里我们以MNIST的60 000张图片作为训练集，我们希望对测试数据集的10 000张图片全部打上标签。KNN算法将会比较测试图片与训练集中每一张图片，然后将它认为最相似的那个训练集图片的标签赋给这张测试图片。
那么，具体应该如何比较这两张图片呢？在本例中，比较图片就是比较28×28的像素块。最简单的方法就是逐个像素进行比较，最后将差异值全部加起来，如图3-6所示。
以图3-6中的一个颜色通道为例来进行说明。两张图片使用L1距离来进行比较。逐个像素求差值，然后将所有差值加起来得到一个数值。如果两张图片一模一样，那么L1距离为0，但是如果两张图片差别很大，那么，L1的值将会非常大。
3.验证KNN在MNIST上的效果
在实现算法之后，我们需要验证MNIST数据集在KNN算法下的分类准确度，在“if name == '__main__'”下添加如下代码（不要忘记缩进）：
X_train = train_loader.dataset.train_data.numpy() #需要转为numpy矩阵
X_train = X_train.reshape(X_train.shape[0],28*28)#需要reshape之后才能放入knn分类器
y_train = train_loader.dataset.train_labels.numpy()
X_test = test_loader.dataset.test_data[:1000].numpy()
X_test = X_test.reshape(X_test.shape[0],28*28)
y_test = test_loader.dataset.test_labels[:1000].numpy()
num_test = y_test.shape[0]
y_test_pred = kNN_classify(5, 'M', X_train, y_train, X_test)
num_correct = np.sum(y_test_pred == y_test)
accuracy = float(num_correct) / num_test
print('Got %d / %d correct => accuracy: %f' % (num_correct, num_test, accuracy))最后，我们运行代码，由运行结果可以看到准确率只有Got 368 / 1000 correct => accuracy: 0.368000！这说明1000张图片中只有大约37张图片预测类别的结果是准确的。
先别气馁，我们之前不是刚说过可以使用数据预处理的技术吗？下面我们试一下如果在进行数据加载的时候尝试使用归一化，那么分类准确度是否会提高呢？我们稍微修改下代码,主要是在将X_train和X_test放入KNN分类器之前先调用centralized，进行归一化处理，示例代码如下：
X_train = train_loader.dataset.train_data.numpy()
mean_image = getXmean(X_train)
X_train = centralized(X_train,mean_image)
y_train = train_loader.dataset.train_labels.numpy()
X_test = test_loader.dataset.test_data[:1000].numpy()
X_test = centralized(X_test,mean_image)
y_test = test_loader.dataset.test_labels[:1000].numpy()
num_test = y_test.shape[0]
y_test_pred = kNN_classify(5, 'M', X_train, y_train, X_test)
num_correct = np.sum(y_test_pred == y_test)
accuracy = float(num_correct) / num_test
print('Got %d / %d correct => accuracy: %f' % (num_correct, num_test, accuracy))下面再来看下输出结果的准确率：Got 951 / 1000 correct => accuracy: 0.951000，95%算是不错的结果。
现在我们来看一看归一化后的图像是什么样子的，代码如下：
import matplotlib.pyplot as plt
mean_image = getXmean(X_train)
cdata = centralized(test_loader.dataset.test_data.numpy(),mean_image)
cdata = cdata.reshape(cdata.shape[0],28,28)
plt.imshow(cdata[0],cmap=plt.cm.binary)
plt.show()
print(test_loader.dataset.test_labels[0]) #输出的label为7效果如图3-7所示。
4. KNN代码整合
现在，我们再来回顾下KNN的算法实现，对于KNN算法来说，之前的实现代码虽然可用，但并不是按照面向对象的思路来编写的，在本例中，我们将之前的代码做一下改进。代码的实现思路是：我们可以创建一个fit方法来存储所有的图片以及与它们对应的标签。伪代码如下：
def fit(self,X_train,y_train):
return model再创建一个predict方法，以预测输入图片最有可能匹配的标签：
def predict(self,k, dis, X_test): #其中，k的选择范围为1~20，dis代表选择的是欧拉还是曼哈顿公式，X_test表示训练数据，函数返回的是预测的类别
return test_labels下面我们来完善下KNN算法的封装（基于面向对象的思想来实现）。我们将这个类命名为Knn（注意：这个类名的n是小写的）。
第一步，完善fit方法，fit方法主要是通过训练数据集来训练模型，在Knn类中，我们的实现思路是将训练集的数据与其对应的标签存储于内存中。代码如下：
def fit(self,X_train,y_train): #我们统一下命名规范，X_train代表的是训练数据集，而y_train代表的是对应训练集数据的标签
self.Xtr = X_train
self.ytr = y_train第二步，完善predict方法，predict方法可用于预测测试集的标签。具体的实现代码与之前的代码类似，只不过输入的参数只有k（代表的是k的选值），dis代表使用的是欧拉公式还是曼哈顿公式，X_test代表的是测试数据集；predict方法返回的是预测的标签集合。代码如下（只包含了欧氏距离的实现）：
def predict(self,k, dis, X_test):
assert dis == 'E' or dis == 'M', 'dis must E or M'
num_test = X_test.shape[0] #测试样本的数量
labellist = []
#使用欧拉公式作为距离度量
if (dis == 'E'):
for i in range(num_test):
distances = np.sqrt(np.sum(((self.Xtr - np.tile(X_test[i], (self.Xtr.shape[0], 1))) ** 2), axis=1))
nearest_k = np.argsort(distances)
topK = nearest_k[:k]
classCount = {}
for i in topK:
classCount[self.ytr[i]] = classCount.get(self.ytr[i], 0) + 1
sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)
labellist.append(sortedClassCount[0][0])
return np.array(labellist)最后，我们引入from ml.knn.demo.KnnClassify import Knn，使用MNIST数据集查看效果。
3.3.2 KNN实现Cifar10数据分类
3.3.1节中，我们讲解了什么是MNIST数据集，以及如何使用KNN算法进行图像分类，从分类的准确率来看，KNN算法的效果还是可以的。本节我们将进一步使用稍微复杂一些的Cifar10数据集进行实验。
1. Cifar10数据集
Cifar10是一个由彩色图像组成的分类的数据集（MNIST是黑白数据集），其中包含了飞机、汽车、鸟、猫、鹿、狗、青蛙、马、船、卡车10个类别（如图3-8所示），且每个类中包含了1000张图片。整个数据集中包含了60 000张32×32的彩色图片。该数据集被分成50 000和10 000两部分，50 000是training set，用来做训练；10 000是test set，用来做验证。
Cifar10官方数据源提供多种语言的数据集，如果你从官方数据源下载Cifar10的Python版的数据集，那么数据集的结构是这样的：
batches.meta
data_batch_1
data_batch_2
data_batch_3
data_batch_4
data_batch_5
test_batch
readme.htmlCifar10是按字典的方式进行组织的，每一个batch中包含的内容具体如下。
- data：图片的信息，组织成10 000×3072的大小，3072是将原来的3×32×32的图片序列化之后的大小，原来32×32的RGB图像按照R、G、B三个通道分别摆放成一个向量，所以恢复的时候会分别恢复出三个通道，在显示图像的时候需要merge一下。
- labels：对应于data里面的每一张图片所属的label。
- batch_label：当前所使用的batch的编号。
- filenames：数据集里面每一张图片所对应的文件名（这个不太重要）。
其中，batches.meta保存的是元数据，是一个字典结构，其所包含的内容具体如下。
- num_cases_per_batch：每一个batch的数据的数量是多少，这里是10 000。
-
label_names：标签的名称，在数据集中标签是按index分类的，相应的index的名字就在这里。
- num_vis：数据的维度，这里是3072。
我们依然使用PyTorch来读取Cifar10数据集，完整的代码具体如下：
import torch
from torch.utils.data import DataLoader
import torchvision.datasets as dsets
batch_size = 100
#Cifar10 dataset
train_dataset = dsets.CIFAR10(root = '/ml/pycifar', #选择数据的根目录
train = True, #选择训练集
download = True) #从网络上下载图片
test_dataset = dsets.CIFAR10(root = '/ml/pycifar', #选择数据的根目录
train = False, #选择测试集
download = True) #从网络上下载图片
#加载数据
train_loader = torch.utils.data.DataLoader(dataset = train_dataset,
batch_size = batch_size,
shuffle = True) #将数据打乱
test_loader = torch.utils.data.DataLoader(dataset = test_dataset,
batch_size = batch_size,
shuffle = True)下面来看下我们需要分类的图片是什么样的，代码如下：
classes = ('plane', 'car', 'bird', 'cat',
'deer', 'dog', 'frog', 'horse', 'ship', 'truck')
digit = train_loader.dataset.train_data[0]
import matplotlib.pyplot as plt
plt.imshow(digit,cmap=plt.cm.binary)
plt.show()
print(classes[train_loader.dataset.train_labels[0]]) #打印出是frogclasses是我们定义的类别，其对应的是Cifar中的10个类别。使用PyTorch读取的类别是index，所以我们还需要额外定义一个classes来指向具体的类别。最后我们看下图3-9的效果，由于只有32×32个像素，因此图3-9比较模糊。
2. KNN在Cifar10上的效果
之前章节中也已经提到过KNN分类算法，现在我们主要观察下KNN对于Cifar10数据集的分类效果，与之前MNIST数据集不同的是，X_train = train_loader.dataset.train_data，X_train的dtype是uint8而不是torch.uint8，所以不需要使用numpy()这个方法进行转换，示例代码如下：
def getXmean(X_train):
X_train = np.reshape(X_train, (X_train.shape[0], -1))
#将图片从二维展开为一维
mean_image = np.mean(X_train, axis=0)
#求出训练集中所有图片每个像素位置上的平均值
return mean_image
def centralized(X_test,mean_image):
X_test = np.reshape(X_test, (X_test.shape[0], -1)) #将图片从二维展开为一维
X_test = X_test.astype(np.float)
X_test -= mean_image #减去均值图像，实现零均值化
return X_test
X_train = train_loader.dataset.train_data
mean_image = getXmean(X_train)
X_train = centralized(X_train,mean_image)
y_train = train_loader.dataset.train_labels
X_test = test_loader.dataset.test_data[:100]
X_test = centralized(X_test,mean_image)
y_test = test_loader.dataset.test_labels[:100]
num_test = len(y_test)
y_test_pred = kNN_classify(6, 'M', X_train, y_train, X_test)#这里并没有使用封装好的类
num_correct = np.sum(y_test_pred == y_test)
accuracy = float(num_correct) / num_test
print('Got %d / %d correct => accuracy: %f' % (num_correct, num_test, accuracy))在上述代码中，我们使用了k=6，读者可以自行测试k的其他值或者更换距离度量，进一步观察预测的准确率。
3.4 模型参数调优
机器学习方法（深度学习是机器学习中的一种）往往涉及很多参数甚至超参数，因此实践过程中需要对这些参数进行适当地选择和调整。本节将以KNN为例介绍模型参数调整的一些方法。这里的方法不局限于图像识别，属于机器学习通用的方法。本节的知识既可以完善读者的机器学习知识体系，也可以帮助读者在未来的实践中更快、更好地找到适合自己模型和业务问题的参数。当然如果你比较急切地想了解图像识别、快速地动手实践以看到自己写出的图像识别代码，那么你可以先跳过这一节，实战时再回来翻看也不迟。
对于KNN算法来说，k就是需要调整的超参数。对于一般初学者来说，你可能会尝试不同的值，看哪个值表现最好就选哪个。有一种更专业的穷举调参方法称为GridSearch，即在所有候选的参数中，通过循环遍历，尝试每一种的可能性，表现最好的参数就是最终的结果。
那么选用哪些数据集进行调参呢，我们来具体分析一下。
方法一，选择整个数据集进行测试。这种方法有一个非常明显的问题，那就是设定k=1总是最好的，因为每个测试样本的位置总是与整个训练集中的自己最接近，如图3-10所示。
方法二，将整个数据集拆分成训练集和测试集，然后在测试集中选择合适的超参数。这里也会存在一个问题，那就是不清楚这样训练出来的算法模型对于接下来的新的测试数据的表现会如何，如图3-11所示。
方法三，将整个数据集拆分成训练集、验证集和测试集，然后在验证集中选择合适的超参数，最后在测试集上进行测试。这个方法相对来说比之前两种方法好很多，也是在实践中经常使用的方法，如图3-12所示。
方法四，使用交叉验证，将数据分成若干份，将其中的各份作为验证集之后给出平均准确率，最后将评估得到的合适的超参数在测试集中进行测试。这个方法更加严谨，但实践中常在较小的数据集上使用，在深度学习中很少使用，如图3-13所示。
我们现在针对方法四来做测试。
第一步，使用之前所写的KNN分类器，代码如下：
class Knn:
def __init__(self):
pass
def fit(self,X_train,y_train):
self.Xtr = X_train
self.ytr = y_train
def predict(self,k, dis, X_test):
assert dis == 'E' or dis == 'M', 'dis must E or M'
num_test = X_test.shape[0] #测试样本的数量
labellist = []
#使用欧拉公式作为距离度量
if (dis == 'E'):
for i in range(num_test):
distances = np.sqrt(np.sum(((self.Xtr - np.tile(X_test[i], (self.Xtr.shape[0], 1))) ** 2), axis=1))
nearest_k = np.argsort(distances)
topK = nearest_k[:k]
classCount = {}
for i in topK:
classCount[self.ytr[i]] = classCount.get(self.ytr[i], 0) + 1
sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)
labellist.append(sortedClassCount[0][0])
return np.array(labellist)
#使用曼哈顿公式作为距离度量
if (dis == 'M'):
for i in range(num_test):
#按照列的方向相加，其实就是行相加
distances = np.sum(np.abs(self.Xtr - np.tile(X_test[i], (self.Xtr.shape[0], 1))), axis=1)
nearest_k = np.argsort(distances)
topK = nearest_k[:k]
classCount = {}
for i in topK:
classCount[self.ytr[i]] = classCount.get(self.ytr[i], 0) + 1
sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)
labellist.append(sortedClassCount[0][0])
return np.array(labellist)第二步，准备测试数据与验证数据，值得注意的是，如果使用方法四，则在选择超参数阶段不需要使用到X_test和y_test的输出，代码如下：
X_train = train_loader.dataset.train_data
X_train = X_train.reshape(X_train.shape[0],-1)
mean_image = getXmean(X_train)
X_train = centralized(X_train,mean_image)
y_train = train_loader.dataset.train_labels
y_train = np.array(y_train)
X_test = test_loader.dataset.test_data
X_test = X_test.reshape(X_test.shape[0],-1)
X_test = centralized(X_test,mean_image)
y_test = test_loader.dataset.test_labels
y_test = np.array(y_test)
print(X_train.shape)
print(y_train.shape)
print(X_test.shape)
print(y_test.shape)第三步，将训练数据分成5个部分，每个部分轮流作为验证集，代码如下：
num_folds = 5
k_choices = [1, 3, 5, 8, 10, 12, 15, 20] #k的值一般选择1~20以内
num_training=X_train.shape[0]
X_train_folds = []
y_train_folds = []
indices = np.array_split(np.arange(num_training), indices_or_sections=num_folds) #把下标分成5个部分
for i in indices:
X_train_folds.append(X_train[i])
y_train_folds.append(y_train[i])
k_to_accuracies = {}
for k in k_choices:
#进行交叉验证
acc = []
for i in range(num_folds):
x = X_train_folds[0:i] + X_train_folds[i+1:] #训练集不包括验证集
x = np.concatenate(x, axis=0) #使用concatenate将4个
训练集拼在一起
y = y_train_folds[0:i] + y_train_folds[i+1:]
y = np.concatenate(y) #对label进行同样的操作
test_x = X_train_folds[i] #单独拿出验证集
test_y = y_train_folds[i]
classifier = Knn() #定义model
classifier.fit(x, y) #读入训练集
#dist = classifier.compute_distances_no_loops(test_x)
#计算距离矩阵
y_pred = classifier.predict(k,'M',test_x) #预测结果
accuracy = np.mean(y_pred == test_y) #计算准确率
acc.append(accuracy)
k_to_accuracies[k] = acc #计算交叉验证的平均准确率
#输出准确度
for k in sorted(k_to_accuracies):
for accuracy in k_to_accuracies[k]:
print('k = %d, accuracy = %f' % (k, accuracy))使用下面的代码图形化展示k的选取与准确度趋势：
# plot the raw observations
import matplotlib.pyplot as plt
for k in k_choices:
accuracies = k_to_accuracies[k]
plt.scatter([k] * len(accuracies), accuracies)
# plot the trend line with error bars that correspond to standard deviation
accuracies_mean = np.array([np.mean(v) for k,v in sorted(k_to_accuracies.items())])
accuracies_std = np.array([np.std(v) for k,v in sorted(k_to_accuracies.items())])
plt.errorbar(k_choices, accuracies_mean, yerr=accuracies_std)
plt.title('Cross-validation on k')
plt.xlabel('k')
plt.ylabel('Cross-validation accuracy')
plt.show()这样我们就能比较直观地了解哪个k比较合适，了解测试集的准确度，当然我们也可以更改下代码（选取欧拉公式来重新测试，看哪个距离度量比较好）。
特别需要注意的是，不能使用测试集来进行调优。当你在设计机器学习算法的时候，应该将测试集看作非常珍贵的资源，不到最后一步，绝不使用它。如果你使用测试集来调优，即使算法看起来效果不错，但真正的危险在于：在算法实际部署后，算法对测试集过拟合，也就是说在实际应用的时候，算法模型对于新的数据预测的准确率将会大大下降。从另一个角度来说，如果使用测试集来调优，那么实际上就是将测试集当作训练集，由测试集训练出来的算法再运行同样的测试集，性能看起来自然会很好，但其实是有一点自欺欺人了，实际部署起来，效果就会差很多。所以，到最终测试的时候再使用测试集，可以很好地近似度量你所设计的分类器的泛化性能。
3.5 本章小结
本章主要讲述了KNN在图像分类上的应用，虽然KNN在MNIST数据集中的表现还算可以，但是其在Cifar10数据集上的分类准确度就差强人意了。另外，虽然KNN算法的训练不需要花费时间（训练过程只是将训练集数据存储起来），但由于每个测试图像需要与所存储的全部训练图像进行比较，因此测试需要花费大量时间，这显然是一个很大的缺点，因为在实际应用中，我们对测试效率的关注要远远高于训练效率。
在实际的图像分类中基本上是不会使用KNN算法的。因为图像都是高维度数据（它们通常包含很多像素），这些高维数据想要表达的主要是语义信息，而不是某个具体像素间的距离差值（在图像中，具体某个像素的值和差值基本上并不会包含有用的信息）。如图3-14所示，右边三张图（遮挡、平移、颜色变换）与最左边原图的欧式距离是相等的。但由于KNN是机器学习中最简单的分类算法，而图像分类也是图像识别中最简单的问题，所以本章使用KNN来做图像分类，这是我们了解图像识别算法的第一步。