作者： [寒小陽](http://blog.csdn.net/han_xiaoyang?viewmode=contents) 時間：2015年11月。 出處：[http://blog.csdn.net/han_xiaoyang/article/details/49949535](http://blog.csdn.net/han_xiaoyang/article/details/49949535) 聲明：版權所有，轉載請注明出處，謝謝 ### 1. 圖像分類問題 這是人每天自然而然會做的事情，普通到大部分時候，我們都感知不到我們在完成一個個這樣的任務。早晨起床洗漱，你要看看洗漱臺一堆東西中哪個是杯子，哪個是你的牙刷；吃早餐的時候你要分辨食物和碗碟… 抽象一下，對于一張輸入的圖片，要判定它屬于給定的一些**標簽/類別**中的哪一個。看似很簡單的一個問題，這么多年卻一直是計算機視覺的一個核心問題，應用場景也很多。它的重要性還體現在，其實其他的一些計算機視覺的問題(比如說物體定位和識別、圖像內容分割等)都可以基于它去完成。 咱們舉個例子從機器學習的角度描述一下這個問題^_^ 計算機拿到一張圖片(如下圖所示)，然后需要給出它對應{貓，狗，帽子，杯子}4類的概率。人類是灰常牛逼的生物，我們一瞥就知道這貨是貓。然而對計算機而言，他們是沒辦法像人一樣『看』到整張圖片的。對它而言，這是一個3維的大矩陣，包含248*400個像素點，每個像素點又有紅綠藍(RGB)3個顏色通道的值，每個值在0(黑)-255(白)之間，計算機就需要根據這248 * 400 * 3=297600個數值去判定這貨是『貓』  #### 1.1 圖像識別的難點 圖像識別看似很直接。但實際上包含很多挑戰，人類可是經過數億年的進化才獲得如此強大的大腦，對于各種物體有著精準的視覺理解力。總體而言，我們想『教』會計算機去認識一類圖，會有下面這樣一些困難： - **視角不同**，每個事物旋轉或者側視最后的構圖都完全不同 - **尺寸大小不統一**，相同內容的圖片也可大可小 - **變形**，很多東西處于特殊的情形下，會有特殊的擺放和形狀 - **光影等干擾/幻象** - **背景干擾** - **同類內的差異(比如椅子有靠椅/吧椅/餐椅/躺椅…)**  #### 1.2 識別的途徑 首先，大家想想就知道，這個算法并不像『對一個數組排序』或者『求有向圖的最短路徑』，我們沒辦法提前制定一個流程和規則去解決。定義『貓』這種動物本身就是一件很難的事情了，更不要說去定義一只貓在圖像上的固定表現形式。所以我們寄希望于機器學習，使用`『Data-driven approach/數據驅動法』`來做做嘗試。簡單說來，就是對于每個類別，我們都找一定量的圖片數據，『喂』給計算機，讓它自己去『學習和總結』每一類的圖片的特點。對了，這個過程和小盆友學習新鮮事物是一樣一樣的。『喂』給計算機學習的圖片數據就和下圖的貓/狗/杯子/帽子一樣：  #### 1.3 機器學習解決圖像分類的流程/Pipeline 整體的流程和普通機器學習完全一致，簡單說來，也就下面三步： - **輸入**：我們的給定K個類別的N張圖片，作為計算機學習的訓練集 - **學習**：讓計算機逐張圖片地『觀察』和『學習』 - **評估**：就像我們上學學了東西要考試檢測一樣，我們也得考考計算機學得如何，于是我們給定一些計算機不知道類別的圖片讓它判別，然后再比對我們已知的正確答案。 ### 2. 最近鄰分類器(Nearest Neighbor Classifier) 先從簡單的方法開始說，先提一提**最近鄰分類器/Nearest Neighbor Classifier**，不過事先申明，它和深度學習中的卷積神經網/Convolutional Neural Networks其實一點關系都沒有，我們只是從基礎到前沿一點一點推進，最近鄰是圖像識別一個相對簡單和基礎的實現方式。 #### 2.1 CIFAR-10 [CIFAR-10](http://www.cs.toronto.edu/~kriz/cifar.html)是一個非常常用的圖像分類數據集。數據集包含60000張32*32像素的小圖片，每張圖片都有一個類別標注(總共有10類)，分成了50000張的訓練集和10000張的測試集。如下是一些圖片示例：  上圖中左邊是十個類別和對應的一些示例圖片，右邊是給定一張圖片后，根據像素距離計算出來的，最近的10張圖片。 #### 2.2 基于最近鄰的簡單圖像類別判定 假如現在用CIFAR-10數據集做訓練集，判斷一張未知的圖片屬于CIFAR-10中的哪一類，應該怎么做呢。一個很直觀的想法就是，既然我們現在有每個像素點的值，那我們就根據輸入圖片的這些值，計算和訓練集中的圖片距離，找最近的圖片的類別，作為它的類別，不就行了嗎。 恩，想法很直接哈，這就是『最近鄰』的思想。偷偷說一句，這種直接的做法在圖像識別中，其實效果并不是特別好。比如上圖是按照這個思想找的最近鄰，其實只有3個圖片的最近鄰是正確的類目。 即使這樣，作為最基礎的方法，我們還是來實現一下吧。我們需要一個圖像距離評定準則，比如最簡單的方式就是，比對兩個圖像像素向量之間的l1距離(也叫曼哈頓距離/cityblock距離)，公式如下： d1(I1,I2)=∑p∣∣Ip1?Ip2∣∣ 其實就是計算了所有像素點之間的差值，然后做了加法，直觀的理解如下圖：  我們先把數據集讀進內存： ~~~ #! /usr/bin/env python #coding=utf-8 import os import sys import numpy as np def load_CIFAR_batch(filename): """ cifar-10數據集是分batch存儲的，這是載入單個batch @參數 filename: cifar文件名 @r返回值: X, Y: cifar batch中的 data 和 labels """ with open(filename, 'r') as f: datadict=pickle.load(f) X=datadict['data'] Y=datadict['labels'] X=X.reshape(10000, 3, 32, 32).transpose(0,2,3,1).astype("float") Y=np.array(Y) return X, Y def load_CIFAR10(ROOT): """ 讀取載入整個 CIFAR-10 數據集 @參數 ROOT: 根目錄名 @return: X_train, Y_train: 訓練集 data 和 labels X_test, Y_test: 測試集 data 和 labels """ xs=[] ys=[] for b in range(1,6): f=os.path.join(ROOT, "data_batch_%d" % (b, )) X, Y=load_CIFAR_batch(f) xs.append(X) ys.append(Y) X_train=np.concatenate(xs) Y_train=np.concatenate(ys) del X, Y X_test, Y_test=load_CIFAR_batch(os.path.join(ROOT, "test_batch")) return X_train, Y_train, X_test, Y_test # 載入訓練和測試數據集 X_train, Y_train, X_test, Y_test = load_CIFAR10('data/cifar10/') # 把32*32*3的多維數組展平 Xtr_rows = X_train.reshape(X_train.shape[0], 32 * 32 * 3) # Xtr_rows : 50000 x 3072 Xte_rows = X_test.reshape(X_test.shape[0], 32 * 32 * 3) # Xte_rows : 10000 x 3072 ~~~ 下面我們實現最近鄰的思路： ~~~ class NearestNeighbor: def __init__(self): pass def train(self, X, y): """ 這個地方的訓練其實就是把所有的已有圖片讀取進來 -_-|| """ # the nearest neighbor classifier simply remembers all the training data 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距離，并找到最近的圖片 distances = np.sum(np.abs(self.Xtr - X[i,:]), axis = 1) min_index = np.argmin(distances) # 取最近圖片的下標 Ypred[i] = self.ytr[min_index] # 記錄下label return Ypred nn = NearestNeighbor() # 初始化一個最近鄰對象 nn.train(Xtr_rows, Y_train) # 訓練...其實就是讀取訓練集 Yte_predict = nn.predict(Xte_rows) # 預測 # 比對標準答案，計算準確率 print 'accuracy: %f' % ( np.mean(Yte_predict == Y_test) ) ~~~ 最近鄰的思想在CIFAR上得到的準確度為**38.6%**，我們知道10各類別，我們隨機猜測的話準確率差不多是1/10=10%，所以說還是有識別效果的，但是顯然這距離人的識別準確率(94%)實在是低太多了，不那么實用。 #### 2.3 關于最近鄰的距離準則 我們這里用的距離準則是l1距離，實際上除掉l1距離，我們還有很多其他的距離準則。 - 比如說l2距離(也就是大家熟知的歐氏距離)的計算準則如下： d2(I1,I2)=∑p(Ip1?Ip2)2￣￣￣￣￣￣￣￣￣￣￣￣￣￣√ - 比如余弦距離計算準則如下： 1?I1?I2||I1||?||I2|| 更多的距離準則可以參見[scipy相關計算頁面](http://docs.scipy.org/doc/scipy-0.16.0/reference/generated/scipy.spatial.distance.pdist.html). ### 3. K最近鄰分類器(K Nearest Neighbor Classifier) 這是對最近鄰的思想的一個調整。其實我們在使用最近鄰分類器分類，掃描CIFAR訓練集的時候，會發現，有時候不一定距離最近的和當前圖片是同類，但是最近的一些里有很多和當前圖片是同類。所以我們自然而然想到，把最近鄰擴展為最近的N個臨近點，然后統計一下這些點的類目分布，取最多的那個類目作為自己的類別。 恩，這就是KNN的思想。 KNN其實是一種特別常用的分類算法。但是有個問題，我們的K值應該取多少呢。換句話說，我們找多少鄰居來投票，比較靠譜呢？ #### 3.1 交叉驗證與參數選擇 在現在的場景下，假如我們確定使用KNN來完成圖片類別識別問題。我們發現有一些參數是肯定會影響最后的識別結果的，比如： - 距離的選擇(l1,l2,cos等等) - 近鄰個數K的取值。 每組參數下其實都能產生一個新的model，所以這可以視為一個模型選擇/model selection問題。而對于模型選擇問題，最常用的辦法就是在[交叉驗證](https://en.wikipedia.org/wiki/Cross-validation_%28statistics%29)集上實驗。 數據總量就那么多，如果我們在test data上做模型參數選擇，又用它做效果評估，顯然不是那么合理（因為我們的模型參數很有可能是在test data上過擬合的，不能很公正地評估結果）。所以我們通常會把訓練數據分為兩個部分，一大部分作為訓練用，另外一部分就是所謂的cross validation數據集，用來進行模型參數選擇的。比如說我們有50000訓練圖片，我們可以把它分為49000的訓練集和1000的交叉驗證集。 ~~~ # 假定已經有Xtr_rows, Ytr, Xte_rows, Yte了，其中Xtr_rows為50000*3072 矩陣 Xval_rows = Xtr_rows[:1000, :] # 構建1000的交叉驗證集 Yval = Ytr[:1000] Xtr_rows = Xtr_rows[1000:, :] # 保留49000的訓練集 Ytr = Ytr[1000:] # 設置一些k值，用于試驗 validation_accuracies = [] for k in [1, 3, 5, 7, 10, 20, 50, 100]: # 初始化對象 nn = NearestNeighbor() nn.train(Xtr_rows, Ytr) # 修改一下predict函數，接受 k 作為參數 Yval_predict = nn.predict(Xval_rows, k = k) acc = np.mean(Yval_predict == Yval) print 'accuracy: %f' % (acc,) # 輸出結果 validation_accuracies.append((k, acc)) ~~~ 這里提一個在很多地方會看到的概念，叫做k-fold cross-validation，意思其實就是把原始數據分成k份，輪流使用其中k-1份作為訓練數據，而剩余的1份作為交叉驗證數據(因此其實對于k-fold cross-validation我們會得到k個accuracy)。以下是5-fold cross-validation的一個示例：  以下是我們使用5-fold cross-validation，取不同的k值時，得到的accuracy曲線(補充一下，因為是5-fold cross-validation，所以在每個k值上有5個取值，我們取其均值作為此時的準確度)  可以看出大概在k=7左右有最佳的準確度。 #### 3.2 最近鄰方法的優缺點 K最近鄰的優點大家都看出來了，思路非常簡單清晰，而且完全不需要訓練…不過也正因為如此，最后的predict過程非常耗時，因為要和全部訓練集中的圖片比對一遍。 實際應用中，我們其實更加關心實施predict所消耗的時間，如果有一個圖像識別app返回結果要半小時一小時，你一定第一時間把它卸了。我們反倒不那么在乎訓練時長，訓練時間長一點沒關系，只要最后應用的時候識別速度快效果好，就很贊。后面會提到的深度神經網絡就是這樣，深度神經網絡解決圖像問題時訓練是一個很耗時間的過程，但是識別的過程非常快。 另外，不得不多說一句的是，優化計算K最近鄰時間問題，實際上依舊到現在都是一個非常熱門的問題。**Approximate Nearest Neighbor (ANN)**算法是犧牲掉一小部分的準確度，而提高很大程度的速度，能比較快地找到近似的K最近鄰，現在已經有很多這樣的庫，比如說[FLANN](http://www.cs.ubc.ca/research/flann/). 最后，我們用一張圖來說明一下，用圖片像素級別的距離來實現圖像類別識別，有其不足之處，我們用一個叫做[t-SNE](http://lvdmaaten.github.io/tsne/)的技術把CIFAR-10的所有圖片按兩個維度平鋪出來，靠得越近的圖片表示其像素級別的距離越接近。然而我們瞄一眼，發現，其實靠得最近的并不一定是同類別的。  其實觀察一下，你就會發現，像素級別接近的圖片，在整張圖的顏色分布上，有很大的共性，然而在圖像內容上，有時候也只能無奈地呵呵嗒，畢竟顏色分布相同的不同物體也是非常多的。