第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.html Cifar10是按字典的方式進行組織的，每一個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]]) #列印出是frog classes是我們定義的類别，其對應的是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來做圖像分類，這是我們了解圖像識别算法的第一步。