1. 為什么KNN值得單獨拿出來寫一篇筆記很多人第一次接觸cs231n作業(yè)1的時候注意力都被后面的兩層神經(jīng)網(wǎng)絡或者圖像特征部分吸引走了覺得KNN這個算法太簡單sklearn調(diào)個包就完事了。但我實際做下來發(fā)現(xiàn)KNN這部分恰恰是整個作業(yè)1里最能幫你建立向量化思維和距離度量直覺的模塊。它看起來簡單但當你真的要從零實現(xiàn)一個不依賴任何循環(huán)的向量化版本時坑一個接一個。這篇筆記面向的是正在做或者準備做cs231n作業(yè)1的讀者也適合任何想真正搞懂KNN底層實現(xiàn)細節(jié)的人。我會把KNN在CIFAR-10上的完整流程拆開講——從數(shù)據(jù)加載、距離矩陣計算、交叉驗證調(diào)參到最終的可視化驗證。重點不是告訴你調(diào)這個函數(shù)就行而是把每一步為什么這么做、參數(shù)怎么選、踩過什么坑都講清楚。KNN的核心思想其實一句話就能說清給定一張測試圖片找到訓練集中跟它最像的K張圖片然后讓這K張圖片投票決定測試圖片的類別。但最像怎么定義、K張怎么選、投票怎么投每一個環(huán)節(jié)都有講究。下面我按實際做作業(yè)的順序一步步展開。2. 數(shù)據(jù)準備與預處理的關(guān)鍵細節(jié)2.1 CIFAR-10數(shù)據(jù)集的加載與結(jié)構(gòu)理解cs231n作業(yè)1用的是CIFAR-10數(shù)據(jù)集包含60000張32x32的彩色圖片分10個類別每個類別6000張。官方給的數(shù)據(jù)格式是pickle文件加載之后你會得到一個字典里面有幾個關(guān)鍵的keydata、labels、batch_label。data的形狀是N×3072這里的3072就是32×32×3展開成一維的結(jié)果。這里第一個容易困惑的點是為什么是3072而不是32×32×3分開存因為后續(xù)計算距離的時候我們需要把每張圖片當成一個3072維的向量來處理。展開成一維之后兩張圖片之間的歐氏距離就是這3072個維度上差值的平方和開根號。這個展開順序是RGB通道分別展平的也就是說前1024個數(shù)是R通道中間1024個是G通道最后1024個是B通道。你在做可視化的時候必須按這個順序reshape回去否則顏色會亂掉。加載數(shù)據(jù)的代碼大概長這樣import pickle import numpy as np def load_cifar10_batch(filepath): with open(filepath, rb) as f: datadict pickle.load(f, encodingbytes) X datadict[bdata] Y datadict[blabels] X X.reshape(10000, 3, 32, 32).transpose(0, 2, 3, 1).astype(float) Y np.array(Y) return X, Y注意這里有個transpose(0, 2, 3, 1)的操作把原來的(N, C, H, W)轉(zhuǎn)成(N, H, W, C)。為什么要轉(zhuǎn)因為后面可視化的時候用matplotlib顯示圖片它期望的格式是(H, W, C)。如果你不轉(zhuǎn)顯示出來的圖片顏色通道就錯位了。2.2 數(shù)據(jù)劃分與采樣策略作業(yè)要求把50000張訓練集再拆出一部分做驗證集。標準做法是取最后5000張作為驗證集前45000張作為訓練集。但實際調(diào)試的時候我強烈建議你先從訓練集里采樣一個很小的子集來跑通流程比如只取500張訓練、100張測試。原因很簡單KNN的計算量隨訓練集大小線性增長你如果一上來就用45000張跑光是距離矩陣計算就能讓你等好幾分鐘調(diào)參的時候根本受不了。采樣的時候要注意類別平衡。CIFAR-10每個類別的樣本數(shù)是一樣的如果你隨機采樣導致某些類別樣本過少驗證準確率會波動很大。我一般用每個類別取相同數(shù)量的方式來做子采樣這樣得到的準確率更有參考價值。還有一個細節(jié)數(shù)據(jù)要不要歸一化對于KNN來說如果你用的是歐氏距離特征的尺度會直接影響距離計算。CIFAR-10的像素值范圍是0到255不同通道之間的尺度差異不大所以歸一化不是必須的。但如果你后面要跟其他特征拼接比如HOG特征那就必須做標準化否則量綱大的特征會主導距離計算。我在做作業(yè)1的時候試過歸一化和不歸一化在純像素上差別不大準確率波動在1%以內(nèi)。3. 距離計算的兩種實現(xiàn)與性能對比3.1 雙循環(huán)版本的實現(xiàn)與理解KNN最核心的計算就是測試樣本和訓練樣本之間的距離矩陣。假設訓練集有N張圖測試集有M張圖那距離矩陣的維度就是M×N。最直觀的實現(xiàn)是兩層循環(huán)def compute_distances_two_loops(X_train, X_test): num_test X_test.shape[0] num_train X_train.shape[0] dists np.zeros((num_test, num_train)) for i in range(num_test): for j in range(num_train): diff X_test[i] - X_train[j] dists[i, j] np.sqrt(np.sum(diff ** 2)) return dists這個版本最好理解就是老老實實算每對圖片之間的歐氏距離。但它的性能極差在45000×5000的規(guī)模下Python的雙層循環(huán)大概要跑好幾分鐘。不過它的價值在于你可以用它來驗證后面向量化版本的正確性。我每次寫完向量化版本都會先用小規(guī)模數(shù)據(jù)跟雙循環(huán)版本對比一下確保結(jié)果一致。這里有個小坑np.sqrt(np.sum(diff ** 2))和np.linalg.norm(diff)是等價的但后者在某些numpy版本上會慢一點點。另外如果你不需要開根號比如只比較距離大小可以省掉sqrt因為平方距離的排序和距離的排序是一樣的。但在KNN里我們需要真實的距離值來做閾值判斷所以還是得開。3.2 單循環(huán)版本的優(yōu)化思路單循環(huán)版本的核心思路是每次處理一張測試圖片但把跟所有訓練圖片的距離計算向量化。def compute_distances_one_loop(X_train, X_test): num_test X_test.shape[0] num_train X_train.shape[0] dists np.zeros((num_test, num_train)) for i in range(num_test): diff X_train - X_test[i] dists[i, :] np.sqrt(np.sum(diff ** 2, axis1)) return dists這里的關(guān)鍵是X_train - X_test[i]利用了numpy的廣播機制得到一個(N, 3072)的矩陣然后沿axis1求和得到N個距離值。這個版本比雙循環(huán)快了幾十倍因為內(nèi)層循環(huán)被numpy的底層C實現(xiàn)替代了。但要注意內(nèi)存問題當N45000的時候X_train - X_test[i]會臨時創(chuàng)建一個45000×3072的矩陣大概占500MB內(nèi)存。如果你的機器內(nèi)存不夠這個操作可能會觸發(fā)swap反而變慢。我一般會確保至少有8GB可用內(nèi)存再跑這個版本。3.3 完全向量化版本的數(shù)學推導完全向量化版本是作業(yè)1里最精華的部分也是面試?？嫉狞c。核心公式是$$||a - b||^2 ||a||^2 ||b||^2 - 2a \cdot b$$把測試集矩陣記為$X_{test}$M×D訓練集矩陣記為$X_{train}$N×D那么距離矩陣的平方可以寫成$$D^2 \text{sum}(X_{test}^2, \text{axis}1)[:, \text{None}] \text{sum}(X_{train}^2, \text{axis}1)[\text{None}, :] - 2 X_{test} X_{train}^T$$對應的代碼def compute_distances_no_loops(X_train, X_test): train_sq np.sum(X_train ** 2, axis1) test_sq np.sum(X_test ** 2, axis1) cross X_test.dot(X_train.T) dists np.sqrt(test_sq[:, None] train_sq[None, :] - 2 * cross) return dists這個版本跑45000×5000的距離矩陣只需要幾秒鐘。但有一個隱藏的坑由于浮點數(shù)精度問題test_sq[:, None] train_sq[None, :] - 2 * cross可能會算出很小的負數(shù)比如-1e-12然后sqrt就會產(chǎn)生nan。解決辦法是在sqrt之前加一個clipdists np.sqrt(np.maximum(dists, 0))這個坑我在第一次做的時候踩得很慘距離矩陣里出現(xiàn)了一堆nan導致后續(xù)預測全部出錯排查了半天才發(fā)現(xiàn)是數(shù)值精度問題。3.4 三種實現(xiàn)的性能對比我在同一臺機器上8核CPU16GB內(nèi)存用5000張訓練、500張測試的數(shù)據(jù)跑了三種實現(xiàn)結(jié)果如下實現(xiàn)方式耗時相對加速比內(nèi)存占用雙循環(huán)約45秒1x低單循環(huán)約1.2秒約37x中完全向量化約0.08秒約560x高這個對比很直觀地說明了向量化的重要性。但要注意完全向量化版本在訓練集特別大的時候比如全量45000張內(nèi)存占用會很高因為要同時存儲M×N的距離矩陣。如果內(nèi)存吃緊可以考慮分塊計算每次只算一部分測試樣本的距離。4. 交叉驗證調(diào)參與預測邏輯4.1 K值選擇的交叉驗證流程KNN里最重要的超參數(shù)就是K。K太小模型對噪聲敏感容易過擬合K太大決策邊界過于平滑容易欠擬合。作業(yè)要求用交叉驗證來選K具體做法是把訓練集分成5折每次用4折訓練、1折驗證取平均準確率最高的K。def cross_validate(X_train, y_train, k_choices, num_folds5): fold_size X_train.shape[0] // num_folds k_to_accuracies {k: [] for k in k_choices} for fold in range(num_folds): val_start fold * fold_size val_end (fold 1) * fold_size X_val X_train[val_start:val_end] y_val y_train[val_start:val_end] X_tr np.concatenate([X_train[:val_start], X_train[val_end:]]) y_tr np.concatenate([y_train[:val_start], y_train[val_end:]]) dists compute_distances_no_loops(X_tr, X_val) for k in k_choices: y_pred predict_labels(dists, y_tr, kk) acc np.mean(y_pred y_val) k_to_accuracies[k].append(acc) return k_to_accuracies這里有個實操細節(jié)交叉驗證的時候每次都要重新計算距離矩陣因為訓練集變了。如果你用全量數(shù)據(jù)算一次距離矩陣然后復用那是不對的因為驗證集的樣本在訓練時不應該被看到。我一開始為了省時間想復用距離矩陣后來發(fā)現(xiàn)準確率偏高才意識到這個問題。K的候選值一般取[1, 3, 5, 8, 10, 12, 15, 20, 50, 100]。在CIFAR-10上我實測下來K10左右通常表現(xiàn)最好準確率大概在28%到30%之間。這個數(shù)字看起來很低但要知道CIFAR-10有10個類別隨機猜的準確率是10%KNN能到28%已經(jīng)說明像素層面的相似性確實包含了一些判別信息。4.2 預測函數(shù)的實現(xiàn)與投票機制預測函數(shù)的邏輯是對每個測試樣本找到距離最近的K個訓練樣本然后看這K個樣本里哪個類別最多就預測為哪個類別。def predict_labels(dists, y_train, k1): num_test dists.shape[0] y_pred np.zeros(num_test) for i in range(num_test): closest_y y_train[np.argsort(dists[i])[:k]] y_pred[i] np.argmax(np.bincount(closest_y)) return y_pred這里有幾個細節(jié)值得說。np.argsort返回的是排序后的索引取前K個就得到了最近的K個訓練樣本的索引。np.bincount統(tǒng)計每個類別出現(xiàn)的次數(shù)np.argmax取最多的那個。但np.bincount要求輸入是非負整數(shù)如果你的標簽是浮點數(shù)得先轉(zhuǎn)成int。還有一個投票平局的問題如果K個鄰居里兩個類別的票數(shù)一樣多np.argmax會返回索引較小的那個。這在實踐中影響不大但如果你追求嚴謹可以隨機選一個或者按距離加權(quán)投票。距離加權(quán)投票的思路是距離越近的鄰居話語權(quán)越大權(quán)重可以取距離的倒數(shù)。我試過加權(quán)投票在CIFAR-10上準確率提升了不到0.5%但計算量增加了一些所以作業(yè)里用簡單投票就夠了。4.3 準確率評估與結(jié)果解讀最終在測試集上的準確率用K10大概能到28%左右。這個結(jié)果說明兩個問題第一原始像素層面的KNN確實能捕捉到一些類別間的差異比如汽車和船的像素分布差異比較大第二KNN的天花板很低因為像素距離并不能很好地反映語義相似性一張稍微平移過的貓的圖片在像素空間里可能跟另一張貓的圖片距離很遠。作業(yè)里還要求可視化一些錯誤分類的案例。我看了之后發(fā)現(xiàn)很多錯誤是因為背景干擾。比如一張馬的圖片背景是大片綠色草地KNN可能會把它分到鹿或者青蛙類別因為綠色像素占比很高。這也解釋了為什么后面要引入顏色直方圖或者HOG特征來提升KNN的表現(xiàn)。5. 實操中踩過的坑與排查技巧5.1 距離矩陣出現(xiàn)nan的排查前面提到過完全向量化版本因為浮點精度問題可能產(chǎn)生nan。排查方法很簡單在sqrt之前檢查是否有負數(shù)。dists_sq test_sq[:, None] train_sq[None, :] - 2 * cross print(np.min(dists_sq)) # 如果輸出是負數(shù)說明有精度問題解決辦法就是加np.maximum(dists_sq, 0)。這個坑的隱蔽性在于它只在某些數(shù)據(jù)上出現(xiàn)而且nan會傳播到后續(xù)所有計算導致準確率變成0或者報錯。我建議在寫完向量化版本后先用小數(shù)據(jù)跑一遍檢查距離矩陣里有沒有nan。5.2 內(nèi)存不足與分塊計算當訓練集是全量45000張、測試集是5000張的時候距離矩陣是5000×45000每個元素是float64大概占1.8GB內(nèi)存。加上中間變量峰值內(nèi)存可能超過4GB。如果你的機器內(nèi)存不夠可以分塊計算def compute_distances_chunked(X_train, X_test, chunk_size500): num_test X_test.shape[0] num_train X_train.shape[0] dists np.zeros((num_test, num_train)) train_sq np.sum(X_train ** 2, axis1) for start in range(0, num_test, chunk_size): end min(start chunk_size, num_test) X_chunk X_test[start:end] test_sq np.sum(X_chunk ** 2, axis1) cross X_chunk.dot(X_train.T) dists[start:end] np.sqrt(np.maximum( test_sq[:, None] train_sq[None, :] - 2 * cross, 0)) return dists這樣每次只處理500張測試圖片內(nèi)存占用降到原來的十分之一。代價是稍微慢一點因為循環(huán)次數(shù)增加了但總體還是比單循環(huán)快很多。5.3 交叉驗證中的常見錯誤交叉驗證最容易犯的錯誤是數(shù)據(jù)泄露。比如你在劃分折之前就對整個訓練集做了歸一化那驗證集的信息就泄露到了訓練過程中。正確的做法是先劃分折然后在每折內(nèi)部單獨做歸一化用訓練折的均值和方差去標準化驗證折。另一個錯誤是K值選擇時的過擬合。如果你用測試集來選K那選出來的K在測試集上表現(xiàn)很好但這不是真實的泛化性能。作業(yè)里明確要求用驗證集選K最后再用測試集評估一次。我見過有人直接用測試集調(diào)參然后報告測試準確率這是不嚴謹?shù)摹?.4 常見問題速查表問題現(xiàn)象可能原因解決方法距離矩陣出現(xiàn)nan浮點精度導致負數(shù)開根號sqrt前加np.maximum(dists, 0)準確率異常低接近10%距離計算錯誤或標簽錯位用雙循環(huán)版本對比驗證內(nèi)存溢出距離矩陣太大分塊計算或減小數(shù)據(jù)集交叉驗證準確率波動大折數(shù)太少或數(shù)據(jù)不平衡增加折數(shù)或分層采樣預測結(jié)果全為同一類K值過大或距離矩陣全零檢查K值和距離計算運行速度極慢用了雙循環(huán)或單循環(huán)改用完全向量化版本6. 從KNN延伸出的思考與后續(xù)優(yōu)化方向KNN在CIFAR-10上的準確率雖然不高但它是一個很好的基線。我在做完KNN之后嘗試了幾個改進方向這里分享一下實際效果。第一個方向是換距離度量。歐氏距離對像素的絕對差異敏感如果圖片整體亮度有偏移距離就會很大。換成余弦距離或者曼哈頓距離在某些類別上會有提升。我試過曼哈頓距離準確率大概提升了1%左右但計算量增加了因為曼哈頓距離不能像歐氏距離那樣用矩陣乘法加速。第二個方向是降維。3072維的像素空間里很多維度是冗余的。用PCA降到100維左右KNN的準確率基本不變但速度快了很多。這個思路在后面做特征工程的時候很有用因為HOG特征維度更高降維能顯著減少計算量。第三個方向是特征工程。作業(yè)1后面會要求你實現(xiàn)HOG特征把HOG特征拼到像素特征上KNN的準確率能提升到40%左右。這說明KNN的性能瓶頸不在分類器本身而在特征的表征能力。同樣的KNN換一組更好的特征效果就能大幅提升。我在實際做作業(yè)的過程中最大的體會是不要因為KNN簡單就跳過它。它涉及的向量化計算、距離度量、交叉驗證、超參數(shù)調(diào)優(yōu)都是后面更復雜模型的基礎。你把KNN這部分吃透了后面寫兩層神經(jīng)網(wǎng)絡的時候很多代碼結(jié)構(gòu)和調(diào)試思路都是相通的。最后分享一個小技巧在調(diào)試KNN的時候先用100張訓練、20張測試的小數(shù)據(jù)跑通全流程確認準確率合理比如K1時訓練集上應該接近100%然后再逐步擴大數(shù)據(jù)量。這樣能快速定位問題是出在算法邏輯還是數(shù)據(jù)規(guī)模上。我一開始直接上全量數(shù)據(jù)結(jié)果跑了十分鐘才出結(jié)果發(fā)現(xiàn)準確率不對又得重新跑浪費了很多時間。小數(shù)據(jù)快速迭代大數(shù)據(jù)最終驗證這個節(jié)奏在做任何機器學習作業(yè)的時候都適用。