：從距離矩陣到交叉驗證全流程)
簡介面向模式識別、機器學習課程學習者與 Matlab 編程入門者的 KNN 實踐材料圍繞 KNN 分類原理與代碼實現(xiàn)展開可用于課堂作業(yè)、課程設計及分類實驗復現(xiàn)。壓縮包共 3 個文件均為 .m 腳本或函數(shù)文件整體約 3KB輕量且便于在 Matlab 中直接閱讀、運行和修改內(nèi)容覆蓋數(shù)據(jù)預處理、距離計算、K 值選擇、最近鄰篩選與類別投票等關(guān)鍵環(huán)節(jié)。材料結(jié)合“第六章 KNN 編程作業(yè)”的示例與說明并涉及剪輯近鄰法通過閾值篩選鄰居以降低噪聲干擾的思路方便讀者對照理解算法流程、調(diào)試代碼并完成自己的分類任務。已有 4444 人學習下載適合作為 KNN 入門實踐與作業(yè)參考的輕量資料。1. 從一張分不開的散點圖說起KNN 為什么總排在模式識別課的第一位模式識別這門課的第一個上機任務十有八九是甩給你一份帶標簽的數(shù)據(jù)讓你用 KNN 算法跑個分類 baseline。數(shù)據(jù)發(fā)下來Matlab 一開很多人第一反應是敲一行fitcknn交差——能出準確率但被追問一句「距離怎么算的、k 怎么定的、平票怎么處理」當場卡殼。這套 Matlab 實現(xiàn)就是為這個場景準備的。它不依賴任何工具箱從距離矩陣、近鄰選取、投票規(guī)則到交叉驗證選 k一層層拆開寫總共不到兩百行。跑通之后距離函數(shù)、投票權(quán)重、k 的搜索網(wǎng)格都可以隨手替換把它當后續(xù)實驗的底座用。適合正在做課設、想搞清楚每一行在算什么的人也適合已經(jīng)會用工具箱、但想掀開蓋子看看齒輪怎么咬合的人。2. 工程骨架一份能直接跑的 KNN Matlab 實現(xiàn)由哪幾個文件組成2.1 目錄結(jié)構(gòu)與每個文件的職責先把文件拆開。見過太多把 KNN 塞進一個main.m里寫到四百行的作業(yè)后面想換一種距離度量得在三處地方同時改改漏一處就跑出個莫名其妙的結(jié)果排查起來純屬玄學。按職責切分的版本大概長這樣knn_lab/ ├── main.m % 入口腳本: 造數(shù)據(jù) → 切分 → 歸一化 → 選k → 預測 → 評估 ├── make_demo_data.m % 生成帶標簽的合成數(shù)據(jù), 用來打通流程 ├── split_dataset.m % 分層切分, 固定隨機種子保證可復現(xiàn) ├── normalize_zscore.m % z-score 歸一化, 統(tǒng)計量只從訓練集算 ├── knn_distance.m % 距離矩陣, 度量方式在這里替換 ├── knn_classify.m % 核心分類器: 取近鄰 投票 ├── cross_validate_k.m % K 折交叉驗證掃 k 網(wǎng)格 ├── evaluate_model.m % 混淆矩陣與逐類召回率 └── data/ └── features.csv % 換成自己的數(shù)據(jù)放這里文件職責是否依賴工具箱main.m串起全流程的入口腳本否split_dataset.m按類別分層切分訓練/測試集否normalize_zscore.m特征標準化返回 mu/sigma 供推理復用否knn_distance.m計算 M×N 距離矩陣支持歐氏/余弦否knn_classify.m近鄰選取、加權(quán)投票、平票處理否cross_validate_k.mK 折交叉驗證輸出準確率曲線否evaluate_model.m手寫混淆矩陣算 P/R/F1否這樣拆的好處很直接換距離度量只動knn_distance.m一個文件換投票策略只動knn_classify.m里那七八行兩邊互不干擾。做消融實驗的時候改動面越小越不容易翻車。2.2 運行環(huán)境與最小依賴整套代碼只用到 Matlab 的基礎(chǔ)語法。R2016b 之后支持隱式擴展M×1和1×N相加自動廣播成M×Nvecnorm從 R2017b 開始才有所以我把距離計算寫成sum(X.^2, 2)的形式老版本也能跑。rng、sort、unique、sub2ind全是基礎(chǔ)函數(shù)不需要額外裝任何東西。需要說明的是knnsearch和fitcknn這兩個函數(shù)——它們屬于 Statistics and Machine Learning Toolbox。第 4 章會拿來做提速對比但那不是必需品手寫版本單獨就能跑完整條鏈路。如果你所在的環(huán)境沒有這個工具箱跳過對比實驗即可。入口腳本main.m按「數(shù)據(jù) → 切分 → 歸一化 → 選參 → 預測 → 評估」六步串起來每一步落一個函數(shù)調(diào)用%% main.m —— KNN 全流程入口 clear; clc; % 1) 造一份三類二維數(shù)據(jù), 換成自己的 csv 只改這一行 [X, y] make_demo_data(300, 3, 42); % 2) 分層切分 7:3, 種子固定 [XTrain, yTrain, XTest, yTest] split_dataset(X, y, 0.3, 42); % 3) 歸一化: mu/sigma 只從訓練集統(tǒng)計, 測試集直接套用 [ZTrain, ZTest, mu, sigma] normalize_zscore(XTrain, XTest); % 4) 五折交叉驗證掃 k 網(wǎng)格 kList 1:2:21; [bestK, accCurve] cross_validate_k(XTrain, yTrain, kList, 5, 7); fprintf(best k %d, cv acc %.4f\n, bestK, max(accCurve)); % 5) 用最優(yōu) k 預測, 開啟距離加權(quán) t0 tic; [yPred, score] knn_classify(ZTrain, yTrain, ZTest, bestK, ... struct(weighted, true, metric, euclidean)); fprintf(predict %d samples in %.1f ms\n, numel(yTest), toc(t0) * 1000); % 6) 評估 stats evaluate_model(yTest, yPred); fprintf(test accuracy %.4f\n, stats.accuracy); disp(stats.cm);make_demo_data負責在二維平面上撒幾團高斯分布的點類中心均勻鋪在半徑 4 的圓上噪聲取單位方差。它的價值不在于數(shù)據(jù)有多真實而在于「答案已知」——三團點分得開任何分類器的準確率都應該在 0.95 以上如果跑出來只有 0.6那一定是鏈路里某個環(huán)節(jié)出了問題而不是數(shù)據(jù)太難。做算法調(diào)試時一組答案已知的合成數(shù)據(jù)比真實數(shù)據(jù)好用十倍。function [X, y] make_demo_data(nPerClass, nClass, seed) %MAKE_DEMO_DATA 生成若干二維高斯簇, 用于快速驗證鏈路是否打通 rng(seed); theta linspace(0, 2*pi, nClass 1); theta(end) []; centers 4 * [cos(theta), sin(theta)]; % 類中心均勻鋪在半徑 4 的圓上 X zeros(nPerClass * nClass, 2); y zeros(nPerClass * nClass, 1); for c 1:nClass rows (c-1) * nPerClass (1:nPerClass); X(rows, :) centers(c, :) randn(nPerClass, 2); % 單位方差噪聲 y(rows) c; end end參數(shù)里nPerClass控制每類樣本量nClass控制類別數(shù)seed交給rng保證同一份數(shù)據(jù)多次生成結(jié)果一致。噪聲標準差固定為 1如果想讓問題變難把它改成 2 或者 3類之間就開始重疊這時候 k 的取值和加權(quán)策略的影響才會明顯體現(xiàn)出來。2.3 數(shù)據(jù)格式約定特征矩陣與標簽向量怎么排KNN 的實現(xiàn)里最容易埋雷的地方不是算法是數(shù)據(jù)格式。約定只有一條X是N×D的 double 矩陣行是樣本、列是特征y是N×1的整數(shù)向量取值必須是1..C的連續(xù)正整數(shù)。后面投票時用score(:, c)按類號索引標簽一旦出現(xiàn) 0 或者跳號比如 1、3、7score 矩陣的列就對不上了。真實數(shù)據(jù)多半從 csv 進來讀完先做一次標簽重編號T readtable(data/features.csv); X table2array(T(:, 1:end-1)); % 前 D 列是特征 rawLabel T{:, end}; % 最后一列是標簽, 可能是字符串或數(shù)值 % unique 的第三個輸出就是 1..C 的重編號, 字符串/數(shù)值通吃 [~, ~, y] unique(rawLabel); y y(:); % 強制列向量 X double(X); % 防止某些列被讀成整型導致除法截斷unique的第三個返回值是索引映射比如原始標簽是{cat,dog,cat}重編號后變成[1;2;1]類別名通過unique的第一個輸出保留下來評估時想顯示原名再映射回去就行。double(X)那句看著多余實際上很關(guān)鍵readtable讀整數(shù)列時會給int64類型后面算X - mu時整型除法的截斷會讓歸一化徹底失效報錯還特別隱蔽。切分函數(shù)用分層策略保證每個類在測試集里都有代表function [XTrain, yTrain, XTest, yTest] split_dataset(X, y, testRatio, seed) %SPLIT_DATASET 按類別分層切分, 避免小類在測試集里缺席 if nargin 4, seed 42; end rng(seed); classes unique(y); idxTrain false(numel(y), 1); for c 1:numel(classes) idx find(y classes(c)); idx idx(randperm(numel(idx))); % 類內(nèi)打亂 nTest max(1, round(numel(idx) * testRatio)); % 每類至少留 1 個 idxTrain(idx(nTest1:end)) true; % 剩下的進訓練集 end XTrain X(idxTrain, :); yTrain y(idxTrain); XTest X(~idxTrain, :); yTest y(~idxTrain); endtestRatio一般取 0.2 到 0.3樣本量小于 500 時建議走交叉驗證而不是單次切分否則測試集太小準確率的方差能大到讓你懷疑人生。max(1, ...)這個保底是為了防止某個類只有三五個樣本時測試集里一個都沒有那樣混淆矩陣會缺行后面算召回率直接除零。3. 核心鏈路拆解從歐氏距離矩陣到多數(shù)投票的每一步3.1 距離矩陣一次矩陣乘法頂?shù)魞芍匮h(huán)KNN 的計算量全在距離上。最直觀的寫法是兩層for循環(huán)測試樣本一個、訓練樣本一個逐個算歐氏距離1000×2000的數(shù)據(jù)在 Matlab 里能跑上十幾秒。向量化的做法是把平方歐氏距離展開$$|a-b|^2 |a|^2 |b|^2 - 2a^\top b$$右邊第一項是測試集每行的模長平方第二項是訓練集每行的模長平方第三項是一次矩陣乘法XTest * XTrain。三個都是高度優(yōu)化的 BLAS 調(diào)用寫出來就是十幾行function D2 knn_distance(XTrain, XTest, metric) %KNN_DISTANCE 計算測試集到訓練集的平方距離矩陣 % D2(i,j) 第 i 個測試樣本到第 j 個訓練樣本的距離 if nargin 3, metric euclidean; end switch lower(metric) case euclidean aa sum(XTest.^2, 2); % M×1, 測試集樣本模長平方 bb sum(XTrain.^2, 2); % 1×N, 訓練集樣本模長平方 D2 aa bb - 2 * (XTest * XTrain); % 隱式擴展成 M×N D2(D2 0) 0; % 浮點相減可能出 -1e-16 case cosine Xn XTest ./ sqrt(sum(XTest.^2, 2)); Yn XTrain ./ sqrt(sum(XTrain.^2, 2)); D2 1 - Xn * Yn; % 余弦距離, 范圍 [0, 2] otherwise error(unsupported metric: %s, metric); end endD2(D2 0) 0這一行不是潔癖。兩個幾乎相同的向量做減法浮點誤差會讓結(jié)果出現(xiàn)-1e-16這種負數(shù)后面sqrt一下直接變成復數(shù)報錯信息還指向別處非常難查。截斷到 0 成本極低但沒有它我至少浪費過一個下午。metric參數(shù)是給二次開發(fā)留的口子。改成cosine之后注意weighted加權(quán)投票邏輯里的1/(deps)依然成立只是物理含義從「距離倒數(shù)」變成了「相似度倒數(shù)」語義上要自己心里有數(shù)。這塊第 6 章會再展開。3.2 取前 K 個近鄰全排序、局部選擇與索引復用拿到 M×N 的距離矩陣之后要對每一行找出最小的 K 個。最省事的寫法是sort(D2, 2, ascend)拿到排序后的距離和對應的原始列下標取前 K 列就行。全排序每行是 $O(N\log N)$而我們只需要前 K 個理論上有更快的選擇算法。Matlab 從 R2017b 開始提供mink做的是部分選擇K 遠小于 N 時比sort快不少K min(k, size(XTrain, 1)); % k 不能超過訓練樣本總數(shù) if exist(mink, file) [dK, idx] mink(D2, K, 2); % R2017b: 每行取最小的 K 個, 返回距離和下標 else [~, idx] sort(D2, 2, ascend); % 老版本回退到全排序 idx idx(:, 1:K); dK D2(sub2ind(size(D2), repmat((1:size(D2,1)), 1, K), idx)); endmink的第二個參數(shù)是取多少個第三個參數(shù)2表示沿列方向也就是每行內(nèi)部取。idx拿到的是 M×K 的下標矩陣每一行是這 M 個測試樣本各自的 K 個最近訓練樣本的列號這個矩陣后面投票時要用兩次——一次取標簽一次取距離。sub2ind那行是把二維下標轉(zhuǎn)成線性下標用于從原始的D2里把對應的距離撈出來。它等價于用循環(huán)寫for i1:M, dK(i,:) D2(i, idx(i,:)); end但省掉了解釋器開銷。數(shù)據(jù)量上萬以后這種細節(jié)的差距是能感覺到的。3.3 多數(shù)投票score 矩陣怎么建加權(quán)與平票怎么處理核心分類器把前面兩步拼起來再加一個投票環(huán)節(jié)。思路是給每個測試樣本建一個長度 C 的得分向量K 個鄰居里屬于第 c 類的有幾個第 c 位就加幾分最后取maxfunction [yPred, score] knn_classify(XTrain, yTrain, XTest, k, opts) %KNN_CLASSIFY 向量化 KNN 分類器 % XTrain/yTrain: 訓練特征與標簽(標簽須為 1..C 連續(xù)整數(shù)) % XTest: 測試特征(用訓練集的 mu/sigma 歸一化過) % k : 近鄰個數(shù) % opts : .weighted(默認 false) / .metric(默認 euclidean) if nargin 5, opts struct(); end if ~isfield(opts, weighted), opts.weighted false; end if ~isfield(opts, metric), opts.metric euclidean; end nTest size(XTest, 1); nClass max(yTrain); % 標簽必須是 1..C K min(k, size(XTrain, 1)); D2 knn_distance(XTrain, XTest, opts.metric); % M×N [~, idx] sort(D2, 2, ascend); idx idx(:, 1:K); % M×K 近鄰下標 rows repmat((1:nTest), 1, K); dK D2(sub2ind(size(D2), rows, idx)); % M×K 近鄰距離 yNb yTrain(idx); % M×K 近鄰標簽 if opts.weighted W 1 ./ (dK 1e-12); % 距離越小, 投票權(quán)重越大 else W ones(nTest, K); end score zeros(nTest, nClass); for c 1:nClass score(:, c) sum(W .* (yNb c), 2); % 逐類累加票數(shù) end [maxScore, yPred] max(score, [], 2); tie sum(score maxScore, 2) 1; % 平票的行 if any(tie) yPred(tie) yTrain(idx(tie, 1)); % 平票退化成 1-NN end endyTrain(idx)這一句依賴yTrain是列向量idx是矩陣Matlab 會返回同形狀的矩陣省掉一層循環(huán)。后面的yNb c是逐元素比較sum(..., 2)按行求和整個投票過程沒有顯式的樣本循環(huán)。平票是必須處理的分支。K 取偶數(shù)時比如 k4兩類各 2 票平票是必然發(fā)生的max默認返回第一個最大值的下標這就等于「類別號小的贏」純屬實現(xiàn)細節(jié)帶來的偏見跟算法本身沒關(guān)系。我一般讓平票退化成 1-NN取距離最近的那個鄰居的標簽——這比按類別號拍腦袋合理得多。1e-12的 eps 是為了防除零歸一化之后訓練集和測試集里可能出現(xiàn)完全相同的樣本距離為 0倒數(shù)變成Inf乘上 0 票會變成NaN整個 score 就廢了。3.4 K 折交叉驗證k 的候選網(wǎng)格怎么掃歸一化為什么必須放進折內(nèi)k 是這套算法唯一真正需要調(diào)的超參數(shù)靠拍腦袋定下來不合適。做法是劃一個候選網(wǎng)格1、3、5…21每一折在訓練部分上歸一化、訓練、在驗證部分上打分取平均準確率最高的那個function [bestK, accCurve] cross_validate_k(X, y, kList, nFold, seed) %CROSS_VALIDATE_K K 折交叉驗證掃 k 網(wǎng)格 if nargin 5, seed 7; end rng(seed); n size(X, 1); perm randperm(n); foldId zeros(n, 1); foldId(perm) mod(0:n-1, nFold) 1; % 盡量均分到各折 accCurve zeros(numel(kList), 1); for ki 1:numel(kList) k kList(ki); acc zeros(nFold, 1); for f 1:nFold te foldId f; tr ~te; % 關(guān)鍵: 歸一化放在折內(nèi), 統(tǒng)計量只來自當前折的訓練部分 [Ztr, Zte] normalize_zscore(X(tr, :), X(te, :)); yp knn_classify(Ztr, y(tr), Zte, k); acc(f) mean(yp y(te)); end accCurve(ki) mean(acc); end [~, iBest] max(accCurve); bestK kList(iBest); endfoldId(perm) mod(0:n-1, nFold) 1這行是均分技巧先把樣本隨機打亂再按位置輪流發(fā)到各折樣本數(shù)不能被折數(shù)整除時誤差也只有 1比按固定塊切分靠譜。nFold一般取 5 或 10樣本量很小時可以用留一法nFold n但代價是訓練次數(shù)等于樣本數(shù)。歸一化寫在折內(nèi)這件事值得單獨強調(diào)。如果先在全體數(shù)據(jù)上算mu/sigma再做交叉驗證驗證折的信息已經(jīng)通過統(tǒng)計量泄漏進了訓練過程交叉驗證的準確率會系統(tǒng)性偏高通常高出一兩個點看起來不明顯但足以讓你選錯 k。這種錯誤的可怕之處在于它不會報錯也不會崩只是讓你拿到的數(shù)字不再可信。accCurve順手返回出來畫條曲線看看拐點比只看最小值更有信息量。3.5 評估混淆矩陣、逐類召回率與手寫累加confusionmat屬于工具箱函數(shù)為了保持零依賴這里手寫累加function stats evaluate_model(yTrue, yPred) %EVALUATE_MODEL 混淆矩陣與逐類指標, 不依賴工具箱 C max([yTrue(:); yPred(:)]); cm zeros(C, C); for i 1:numel(yTrue) cm(yTrue(i), yPred(i)) cm(yTrue(i), yPred(i)) 1; end tp diag(cm); stats.cm cm; stats.accuracy sum(tp) / sum(cm(:)); stats.recall tp ./ max(sum(cm, 2), 1); % 行和 真實類樣本數(shù) stats.precision (tp ./ max(sum(cm, 1), 1)); % 列和 預測類樣本數(shù) stats.f1 2 * stats.precision .* stats.recall ... ./ max(stats.precision stats.recall, eps); endcm(i,j)表示真實類別是 i、被預測成 j 的樣本數(shù)對角線是分對的。行方向求和得到每個真實類的樣本總數(shù)用來算召回率列方向求和得到每個預測類的樣本總數(shù)用來算精確率。max(..., 1)是為了防止某個類在測試集里完全缺席時除零算出來是 0 而不是NaN至少不會污染后面的平均值。只看總體準確率在類別不平衡時會騙人。三類數(shù)據(jù)里有一類占了 90%全判成這一類也能拿到 0.9 的準確率。把stats.recall打出來逐類看哪個類被打成了篩子一目了然比盯一個標量數(shù)字有用得多。4. 性能與精度調(diào)優(yōu)讓手寫 KNN 從玩具代碼變成實驗工具4.1 復雜度賬本訓練是假的預測才是真的貴KNN 是懶惰學習的典型訓練階段什么也不做就是把數(shù)據(jù)存起來復雜度 O(1)所有開銷堆在預測階段每個測試樣本要和全部 N 個訓練樣本算距離總復雜度 $O(M \cdot N \cdot D)$。這個不對稱性意味著「訓練快」根本不是優(yōu)點真正要盯的是預測耗時和內(nèi)存。內(nèi)存這一側(cè)更隱蔽。M×N 的距離矩陣是 double 類型每個元素 8 字節(jié)M5000, N20000就是 800MB稍微再大一點直接 out of memory。而這個矩陣只用來取前 K 個最小值絕大部分內(nèi)容算完就扔占著內(nèi)存純屬浪費。4.2 分塊計算把 M×N 矩陣拆成若干條帶解決辦法是按測試樣本分塊一次只算一塊的距離矩陣算完取完近鄰就釋放function yPred knn_predict_chunked(XTrain, yTrain, XTest, k, blockSize) %KNN_PREDICT_CHUNKED 分塊預測, 把 M×N 距離矩陣壓到 blockSize×N if nargin 5, blockSize 1000; end nTest size(XTest, 1); yPred zeros(nTest, 1); for s 1:blockSize:nTest e min(s blockSize - 1, nTest); yPred(s:e) knn_classify(XTrain, yTrain, XTest(s:e, :), k); end endblockSize是唯一要調(diào)的參數(shù)取值取決于訓練集大小和可用內(nèi)存。經(jīng)驗公式是讓blockSize * N * 8控制在內(nèi)存的三分之一以內(nèi)N20000 時blockSize 取 1000 大概占 160MB很安全N100000 時就得降到 200 以下。分塊之后總計算量不變但峰值內(nèi)存降了一個數(shù)量級而且因為矩陣變小了緩存命中率反而更高實測常常比分塊前還快一點。4.3 parfor 與 knnsearch兩條提速路線怎么選再往上提速有兩條路。第一條是并行把分塊循環(huán)換成parfor前提是已經(jīng)裝了 Parallel Computing Toolbox 并且開了并行池parfor s 1:blockSize:nTest e min(s blockSize - 1, nTest); yPred(s:e) knn_classify(XTrain, yTrain, XTest(s:e, :), k); end注意parfor里不能有跨迭代的共享狀態(tài)yPred用切片方式賦值是合法的但循環(huán)內(nèi)不能再rng或者寫全局變量。加速比取決于核數(shù)4 核大概能到 2.5 到 3 倍核再多收益遞減——瓶頸會轉(zhuǎn)移到內(nèi)存帶寬上。第二條路是直接調(diào)用工具箱的knnsearch% 需要 Statistics and Machine Learning Toolbox [idx, d] knnsearch(XTrain, XTest, K, k, NSMethod, kdtree); yNb yTrain(idx); % 后面接同樣的投票邏輯NSMethod有兩個取值exhaustive是暴力搜索kdtree建 KD 樹。KD 樹在低維D 小于 10 左右時優(yōu)勢明顯建樹一次、查詢多次維度一高就退化得厲害「維數(shù)災難」在 KNN 里體現(xiàn)得特別直接D 到 50 以上時 KD 樹可能比暴力搜索還慢因為這個剪枝結(jié)構(gòu)在高維空間里幾乎失效。方案適用場景內(nèi)存峰值依賴相對耗時雙重循環(huán)只用來對拍驗證正確性最低無最慢向量化全量N×M 小于 1e7高無快分塊向量化大數(shù)據(jù)集常規(guī)方案可控無快分塊 parfor多核機器、離線實驗可控并行工具箱更快knnsearch kdtree低維、多次查詢低統(tǒng)計工具箱低維最快表里的「相對耗時」是定性排序具體倍數(shù)跟機器、維度、數(shù)據(jù)分布都有關(guān)系別照抄。想拿到自己環(huán)境下的真實數(shù)字寫個 benchmark 循環(huán)for r 1:5跑五遍取中位數(shù)比看任何表格都靠譜。4.4 精度側(cè)的三個旋鈕k、權(quán)重、歸一化性能之外真正影響準確率的是三個東西按影響從大到小排。第一個是歸一化。這條幾乎每次都會踩因為不歸一化代碼照樣跑只是準確率悄悄掉下去。量綱差異大的時候尤其致命一個特征范圍是 0 到 255另一個是 0 到 1歐氏距離完全被前者主導后一個特征等于沒參與計算。z-score 之后每個維度方差為 1貢獻才均衡。第二個是 k。k 太小模型方差大一個噪聲點就能翻轉(zhuǎn)結(jié)果k 太大偏差大類邊界被抹平。實踐中從k1掃到ksqrt(N)附近看交叉驗證曲線的最低點。奇數(shù)優(yōu)先能天然規(guī)避兩類平票不過多類問題下平票依然可能第 3 章那段平票處理不能省。第三個是加權(quán)投票。weightedtrue之后近鄰的票數(shù)按距離倒數(shù)加權(quán)靠近邊界的樣本受影響更大通常在類重疊較多的數(shù)據(jù)上能漲一到兩個點。代價是對噪聲更敏感——一個離群點如果恰好離測試樣本很近它的權(quán)重會非常大一個頂十個。數(shù)據(jù)洗干凈之前別急著開這個開關(guān)。5. 避坑記錄Matlab 里跑 KNN 最容易翻車的 5 個地方5.1 現(xiàn)象準確率一直卡在隨機猜的水平原因九成是沒做歸一化或者歸一化的統(tǒng)計量用錯了數(shù)據(jù)。前者讓大方差維度獨占距離后者更隱蔽——在全體數(shù)據(jù)上算mu/sigma再切分測試集的信息泄漏進了訓練過程。還有一種少見但同樣致命的情況csv 里的整數(shù)列被讀成int64X - mu時整型除法直接截斷歸一化等于沒做。解決normalize_zscore只接受訓練集和測試集兩個輸入mu和sigma從訓練集算、保存下來推理時復用同一組。讀數(shù)據(jù)后強制X double(X)。驗證方法很土但有效歸一化之后mean(ZTrain)應該接近全零向量std(ZTrain)接近全一向量打出來看一眼。5.2 現(xiàn)象score(:, c)報下標越界或者預測結(jié)果只有一類原因標簽不是從 1 開始的連續(xù)整數(shù)。原始標簽可能是 0/1/2也可能是字符串元胞數(shù)組直接塞進knn_classify里nClass max(yTrain)算出來的類數(shù)對不上score的列數(shù)和實際類別錯位。解決入口處統(tǒng)一重編號。[~, ~, y] unique(rawLabel)這一句對字符串、數(shù)值、categorical 全都管用輸出保證是1..C的連續(xù)整數(shù)。同時檢查一下y是不是列向量——readtable取出來的可能是行yTrain(idx)的形狀會跟著錯報錯信息指向別處查半天。5.3 現(xiàn)象調(diào)大 k 之后準確率斷崖式下跌某一類被徹底吞掉原因k 超過了某個小類的樣本數(shù)。比如某類只有 5 個訓練樣本k 取 15這 15 個鄰居里屬于該類的頂多 5 票其他類隨便湊湊就壓過去了。類別不平衡時這個問題會放大多數(shù)類的票數(shù)天然占優(yōu)。解決K min(k, size(XTrain,1))只是防越本文還有配套的精品資源點擊獲取 手寫Matlab KNN實現(xiàn)：從距離矩陣到交叉驗證全流程
簡介面向模式識別、機器學習課程學習者與 Matlab 編程入門者的 KNN 實踐材料圍繞 KNN 分類原理與代碼實現(xiàn)展開可用于課堂作業(yè)、課程設計及分類實驗復現(xiàn)。壓縮包共 3 個文件均為 .m 腳本或函數(shù)文件整體約 3KB輕量且便于在 Matlab 中直接閱讀、運行和修改內(nèi)容覆蓋數(shù)據(jù)預處理、距離計算、K 值選擇、最近鄰篩選與類別投票等關(guān)鍵環(huán)節(jié)。材料結(jié)合“第六章 KNN 編程作業(yè)”的示例與說明并涉及剪輯近鄰法通過閾值篩選鄰居以降低噪聲干擾的思路方便讀者對照理解算法流程、調(diào)試代碼并完成自己的分類任務。已有 4444 人學習下載適合作為 KNN 入門實踐與作業(yè)參考的輕量資料。1. 從一張分不開的散點圖說起KNN 為什么總排在模式識別課的第一位模式識別這門課的第一個上機任務十有八九是甩給你一份帶標簽的數(shù)據(jù)讓你用 KNN 算法跑個分類 baseline。數(shù)據(jù)發(fā)下來Matlab 一開很多人第一反應是敲一行fitcknn交差——能出準確率但被追問一句「距離怎么算的、k 怎么定的、平票怎么處理」當場卡殼。這套 Matlab 實現(xiàn)就是為這個場景準備的。它不依賴任何工具箱從距離矩陣、近鄰選取、投票規(guī)則到交叉驗證選 k一層層拆開寫總共不到兩百行。跑通之后距離函數(shù)、投票權(quán)重、k 的搜索網(wǎng)格都可以隨手替換把它當后續(xù)實驗的底座用。適合正在做課設、想搞清楚每一行在算什么的人也適合已經(jīng)會用工具箱、但想掀開蓋子看看齒輪怎么咬合的人。2. 工程骨架一份能直接跑的 KNN Matlab 實現(xiàn)由哪幾個文件組成2.1 目錄結(jié)構(gòu)與每個文件的職責先把文件拆開。見過太多把 KNN 塞進一個main.m里寫到四百行的作業(yè)后面想換一種距離度量得在三處地方同時改改漏一處就跑出個莫名其妙的結(jié)果排查起來純屬玄學。按職責切分的版本大概長這樣knn_lab/ ├── main.m % 入口腳本: 造數(shù)據(jù) → 切分 → 歸一化 → 選k → 預測 → 評估 ├── make_demo_data.m % 生成帶標簽的合成數(shù)據(jù), 用來打通流程 ├── split_dataset.m % 分層切分, 固定隨機種子保證可復現(xiàn) ├── normalize_zscore.m % z-score 歸一化, 統(tǒng)計量只從訓練集算 ├── knn_distance.m % 距離矩陣, 度量方式在這里替換 ├── knn_classify.m % 核心分類器: 取近鄰 投票 ├── cross_validate_k.m % K 折交叉驗證掃 k 網(wǎng)格 ├── evaluate_model.m % 混淆矩陣與逐類召回率 └── data/ └── features.csv % 換成自己的數(shù)據(jù)放這里文件職責是否依賴工具箱main.m串起全流程的入口腳本否split_dataset.m按類別分層切分訓練/測試集否normalize_zscore.m特征標準化返回 mu/sigma 供推理復用否knn_distance.m計算 M×N 距離矩陣支持歐氏/余弦否knn_classify.m近鄰選取、加權(quán)投票、平票處理否cross_validate_k.mK 折交叉驗證輸出準確率曲線否evaluate_model.m手寫混淆矩陣算 P/R/F1否這樣拆的好處很直接換距離度量只動knn_distance.m一個文件換投票策略只動knn_classify.m里那七八行兩邊互不干擾。做消融實驗的時候改動面越小越不容易翻車。2.2 運行環(huán)境與最小依賴整套代碼只用到 Matlab 的基礎(chǔ)語法。R2016b 之后支持隱式擴展M×1和1×N相加自動廣播成M×Nvecnorm從 R2017b 開始才有所以我把距離計算寫成sum(X.^2, 2)的形式老版本也能跑。rng、sort、unique、sub2ind全是基礎(chǔ)函數(shù)不需要額外裝任何東西。需要說明的是knnsearch和fitcknn這兩個函數(shù)——它們屬于 Statistics and Machine Learning Toolbox。第 4 章會拿來做提速對比但那不是必需品手寫版本單獨就能跑完整條鏈路。如果你所在的環(huán)境沒有這個工具箱跳過對比實驗即可。入口腳本main.m按「數(shù)據(jù) → 切分 → 歸一化 → 選參 → 預測 → 評估」六步串起來每一步落一個函數(shù)調(diào)用%% main.m —— KNN 全流程入口 clear; clc; % 1) 造一份三類二維數(shù)據(jù), 換成自己的 csv 只改這一行 [X, y] make_demo_data(300, 3, 42); % 2) 分層切分 7:3, 種子固定 [XTrain, yTrain, XTest, yTest] split_dataset(X, y, 0.3, 42); % 3) 歸一化: mu/sigma 只從訓練集統(tǒng)計, 測試集直接套用 [ZTrain, ZTest, mu, sigma] normalize_zscore(XTrain, XTest); % 4) 五折交叉驗證掃 k 網(wǎng)格 kList 1:2:21; [bestK, accCurve] cross_validate_k(XTrain, yTrain, kList, 5, 7); fprintf(best k %d, cv acc %.4f\n, bestK, max(accCurve)); % 5) 用最優(yōu) k 預測, 開啟距離加權(quán) t0 tic; [yPred, score] knn_classify(ZTrain, yTrain, ZTest, bestK, ... struct(weighted, true, metric, euclidean)); fprintf(predict %d samples in %.1f ms\n, numel(yTest), toc(t0) * 1000); % 6) 評估 stats evaluate_model(yTest, yPred); fprintf(test accuracy %.4f\n, stats.accuracy); disp(stats.cm);make_demo_data負責在二維平面上撒幾團高斯分布的點類中心均勻鋪在半徑 4 的圓上噪聲取單位方差。它的價值不在于數(shù)據(jù)有多真實而在于「答案已知」——三團點分得開任何分類器的準確率都應該在 0.95 以上如果跑出來只有 0.6那一定是鏈路里某個環(huán)節(jié)出了問題而不是數(shù)據(jù)太難。做算法調(diào)試時一組答案已知的合成數(shù)據(jù)比真實數(shù)據(jù)好用十倍。function [X, y] make_demo_data(nPerClass, nClass, seed) %MAKE_DEMO_DATA 生成若干二維高斯簇, 用于快速驗證鏈路是否打通 rng(seed); theta linspace(0, 2*pi, nClass 1); theta(end) []; centers 4 * [cos(theta), sin(theta)]; % 類中心均勻鋪在半徑 4 的圓上 X zeros(nPerClass * nClass, 2); y zeros(nPerClass * nClass, 1); for c 1:nClass rows (c-1) * nPerClass (1:nPerClass); X(rows, :) centers(c, :) randn(nPerClass, 2); % 單位方差噪聲 y(rows) c; end end參數(shù)里nPerClass控制每類樣本量nClass控制類別數(shù)seed交給rng保證同一份數(shù)據(jù)多次生成結(jié)果一致。噪聲標準差固定為 1如果想讓問題變難把它改成 2 或者 3類之間就開始重疊這時候 k 的取值和加權(quán)策略的影響才會明顯體現(xiàn)出來。2.3 數(shù)據(jù)格式約定特征矩陣與標簽向量怎么排KNN 的實現(xiàn)里最容易埋雷的地方不是算法是數(shù)據(jù)格式。約定只有一條X是N×D的 double 矩陣行是樣本、列是特征y是N×1的整數(shù)向量取值必須是1..C的連續(xù)正整數(shù)。后面投票時用score(:, c)按類號索引標簽一旦出現(xiàn) 0 或者跳號比如 1、3、7score 矩陣的列就對不上了。真實數(shù)據(jù)多半從 csv 進來讀完先做一次標簽重編號T readtable(data/features.csv); X table2array(T(:, 1:end-1)); % 前 D 列是特征 rawLabel T{:, end}; % 最后一列是標簽, 可能是字符串或數(shù)值 % unique 的第三個輸出就是 1..C 的重編號, 字符串/數(shù)值通吃 [~, ~, y] unique(rawLabel); y y(:); % 強制列向量 X double(X); % 防止某些列被讀成整型導致除法截斷unique的第三個返回值是索引映射比如原始標簽是{cat,dog,cat}重編號后變成[1;2;1]類別名通過unique的第一個輸出保留下來評估時想顯示原名再映射回去就行。double(X)那句看著多余實際上很關(guān)鍵readtable讀整數(shù)列時會給int64類型后面算X - mu時整型除法的截斷會讓歸一化徹底失效報錯還特別隱蔽。切分函數(shù)用分層策略保證每個類在測試集里都有代表function [XTrain, yTrain, XTest, yTest] split_dataset(X, y, testRatio, seed) %SPLIT_DATASET 按類別分層切分, 避免小類在測試集里缺席 if nargin 4, seed 42; end rng(seed); classes unique(y); idxTrain false(numel(y), 1); for c 1:numel(classes) idx find(y classes(c)); idx idx(randperm(numel(idx))); % 類內(nèi)打亂 nTest max(1, round(numel(idx) * testRatio)); % 每類至少留 1 個 idxTrain(idx(nTest1:end)) true; % 剩下的進訓練集 end XTrain X(idxTrain, :); yTrain y(idxTrain); XTest X(~idxTrain, :); yTest y(~idxTrain); endtestRatio一般取 0.2 到 0.3樣本量小于 500 時建議走交叉驗證而不是單次切分否則測試集太小準確率的方差能大到讓你懷疑人生。max(1, ...)這個保底是為了防止某個類只有三五個樣本時測試集里一個都沒有那樣混淆矩陣會缺行后面算召回率直接除零。3. 核心鏈路拆解從歐氏距離矩陣到多數(shù)投票的每一步3.1 距離矩陣一次矩陣乘法頂?shù)魞芍匮h(huán)KNN 的計算量全在距離上。最直觀的寫法是兩層for循環(huán)測試樣本一個、訓練樣本一個逐個算歐氏距離1000×2000的數(shù)據(jù)在 Matlab 里能跑上十幾秒。向量化的做法是把平方歐氏距離展開$$|a-b|^2 |a|^2 |b|^2 - 2a^\top b$$右邊第一項是測試集每行的模長平方第二項是訓練集每行的模長平方第三項是一次矩陣乘法XTest * XTrain。三個都是高度優(yōu)化的 BLAS 調(diào)用寫出來就是十幾行function D2 knn_distance(XTrain, XTest, metric) %KNN_DISTANCE 計算測試集到訓練集的平方距離矩陣 % D2(i,j) 第 i 個測試樣本到第 j 個訓練樣本的距離 if nargin 3, metric euclidean; end switch lower(metric) case euclidean aa sum(XTest.^2, 2); % M×1, 測試集樣本模長平方 bb sum(XTrain.^2, 2); % 1×N, 訓練集樣本模長平方 D2 aa bb - 2 * (XTest * XTrain); % 隱式擴展成 M×N D2(D2 0) 0; % 浮點相減可能出 -1e-16 case cosine Xn XTest ./ sqrt(sum(XTest.^2, 2)); Yn XTrain ./ sqrt(sum(XTrain.^2, 2)); D2 1 - Xn * Yn; % 余弦距離, 范圍 [0, 2] otherwise error(unsupported metric: %s, metric); end endD2(D2 0) 0這一行不是潔癖。兩個幾乎相同的向量做減法浮點誤差會讓結(jié)果出現(xiàn)-1e-16這種負數(shù)后面sqrt一下直接變成復數(shù)報錯信息還指向別處非常難查。截斷到 0 成本極低但沒有它我至少浪費過一個下午。metric參數(shù)是給二次開發(fā)留的口子。改成cosine之后注意weighted加權(quán)投票邏輯里的1/(deps)依然成立只是物理含義從「距離倒數(shù)」變成了「相似度倒數(shù)」語義上要自己心里有數(shù)。這塊第 6 章會再展開。3.2 取前 K 個近鄰全排序、局部選擇與索引復用拿到 M×N 的距離矩陣之后要對每一行找出最小的 K 個。最省事的寫法是sort(D2, 2, ascend)拿到排序后的距離和對應的原始列下標取前 K 列就行。全排序每行是 $O(N\log N)$而我們只需要前 K 個理論上有更快的選擇算法。Matlab 從 R2017b 開始提供mink做的是部分選擇K 遠小于 N 時比sort快不少K min(k, size(XTrain, 1)); % k 不能超過訓練樣本總數(shù) if exist(mink, file) [dK, idx] mink(D2, K, 2); % R2017b: 每行取最小的 K 個, 返回距離和下標 else [~, idx] sort(D2, 2, ascend); % 老版本回退到全排序 idx idx(:, 1:K); dK D2(sub2ind(size(D2), repmat((1:size(D2,1)), 1, K), idx)); endmink的第二個參數(shù)是取多少個第三個參數(shù)2表示沿列方向也就是每行內(nèi)部取。idx拿到的是 M×K 的下標矩陣每一行是這 M 個測試樣本各自的 K 個最近訓練樣本的列號這個矩陣后面投票時要用兩次——一次取標簽一次取距離。sub2ind那行是把二維下標轉(zhuǎn)成線性下標用于從原始的D2里把對應的距離撈出來。它等價于用循環(huán)寫for i1:M, dK(i,:) D2(i, idx(i,:)); end但省掉了解釋器開銷。數(shù)據(jù)量上萬以后這種細節(jié)的差距是能感覺到的。3.3 多數(shù)投票score 矩陣怎么建加權(quán)與平票怎么處理核心分類器把前面兩步拼起來再加一個投票環(huán)節(jié)。思路是給每個測試樣本建一個長度 C 的得分向量K 個鄰居里屬于第 c 類的有幾個第 c 位就加幾分最后取maxfunction [yPred, score] knn_classify(XTrain, yTrain, XTest, k, opts) %KNN_CLASSIFY 向量化 KNN 分類器 % XTrain/yTrain: 訓練特征與標簽(標簽須為 1..C 連續(xù)整數(shù)) % XTest: 測試特征(用訓練集的 mu/sigma 歸一化過) % k : 近鄰個數(shù) % opts : .weighted(默認 false) / .metric(默認 euclidean) if nargin 5, opts struct(); end if ~isfield(opts, weighted), opts.weighted false; end if ~isfield(opts, metric), opts.metric euclidean; end nTest size(XTest, 1); nClass max(yTrain); % 標簽必須是 1..C K min(k, size(XTrain, 1)); D2 knn_distance(XTrain, XTest, opts.metric); % M×N [~, idx] sort(D2, 2, ascend); idx idx(:, 1:K); % M×K 近鄰下標 rows repmat((1:nTest), 1, K); dK D2(sub2ind(size(D2), rows, idx)); % M×K 近鄰距離 yNb yTrain(idx); % M×K 近鄰標簽 if opts.weighted W 1 ./ (dK 1e-12); % 距離越小, 投票權(quán)重越大 else W ones(nTest, K); end score zeros(nTest, nClass); for c 1:nClass score(:, c) sum(W .* (yNb c), 2); % 逐類累加票數(shù) end [maxScore, yPred] max(score, [], 2); tie sum(score maxScore, 2) 1; % 平票的行 if any(tie) yPred(tie) yTrain(idx(tie, 1)); % 平票退化成 1-NN end endyTrain(idx)這一句依賴yTrain是列向量idx是矩陣Matlab 會返回同形狀的矩陣省掉一層循環(huán)。后面的yNb c是逐元素比較sum(..., 2)按行求和整個投票過程沒有顯式的樣本循環(huán)。平票是必須處理的分支。K 取偶數(shù)時比如 k4兩類各 2 票平票是必然發(fā)生的max默認返回第一個最大值的下標這就等于「類別號小的贏」純屬實現(xiàn)細節(jié)帶來的偏見跟算法本身沒關(guān)系。我一般讓平票退化成 1-NN取距離最近的那個鄰居的標簽——這比按類別號拍腦袋合理得多。1e-12的 eps 是為了防除零歸一化之后訓練集和測試集里可能出現(xiàn)完全相同的樣本距離為 0倒數(shù)變成Inf乘上 0 票會變成NaN整個 score 就廢了。3.4 K 折交叉驗證k 的候選網(wǎng)格怎么掃歸一化為什么必須放進折內(nèi)k 是這套算法唯一真正需要調(diào)的超參數(shù)靠拍腦袋定下來不合適。做法是劃一個候選網(wǎng)格1、3、5…21每一折在訓練部分上歸一化、訓練、在驗證部分上打分取平均準確率最高的那個function [bestK, accCurve] cross_validate_k(X, y, kList, nFold, seed) %CROSS_VALIDATE_K K 折交叉驗證掃 k 網(wǎng)格 if nargin 5, seed 7; end rng(seed); n size(X, 1); perm randperm(n); foldId zeros(n, 1); foldId(perm) mod(0:n-1, nFold) 1; % 盡量均分到各折 accCurve zeros(numel(kList), 1); for ki 1:numel(kList) k kList(ki); acc zeros(nFold, 1); for f 1:nFold te foldId f; tr ~te; % 關(guān)鍵: 歸一化放在折內(nèi), 統(tǒng)計量只來自當前折的訓練部分 [Ztr, Zte] normalize_zscore(X(tr, :), X(te, :)); yp knn_classify(Ztr, y(tr), Zte, k); acc(f) mean(yp y(te)); end accCurve(ki) mean(acc); end [~, iBest] max(accCurve); bestK kList(iBest); endfoldId(perm) mod(0:n-1, nFold) 1這行是均分技巧先把樣本隨機打亂再按位置輪流發(fā)到各折樣本數(shù)不能被折數(shù)整除時誤差也只有 1比按固定塊切分靠譜。nFold一般取 5 或 10樣本量很小時可以用留一法nFold n但代價是訓練次數(shù)等于樣本數(shù)。歸一化寫在折內(nèi)這件事值得單獨強調(diào)。如果先在全體數(shù)據(jù)上算mu/sigma再做交叉驗證驗證折的信息已經(jīng)通過統(tǒng)計量泄漏進了訓練過程交叉驗證的準確率會系統(tǒng)性偏高通常高出一兩個點看起來不明顯但足以讓你選錯 k。這種錯誤的可怕之處在于它不會報錯也不會崩只是讓你拿到的數(shù)字不再可信。accCurve順手返回出來畫條曲線看看拐點比只看最小值更有信息量。3.5 評估混淆矩陣、逐類召回率與手寫累加confusionmat屬于工具箱函數(shù)為了保持零依賴這里手寫累加function stats evaluate_model(yTrue, yPred) %EVALUATE_MODEL 混淆矩陣與逐類指標, 不依賴工具箱 C max([yTrue(:); yPred(:)]); cm zeros(C, C); for i 1:numel(yTrue) cm(yTrue(i), yPred(i)) cm(yTrue(i), yPred(i)) 1; end tp diag(cm); stats.cm cm; stats.accuracy sum(tp) / sum(cm(:)); stats.recall tp ./ max(sum(cm, 2), 1); % 行和 真實類樣本數(shù) stats.precision (tp ./ max(sum(cm, 1), 1)); % 列和 預測類樣本數(shù) stats.f1 2 * stats.precision .* stats.recall ... ./ max(stats.precision stats.recall, eps); endcm(i,j)表示真實類別是 i、被預測成 j 的樣本數(shù)對角線是分對的。行方向求和得到每個真實類的樣本總數(shù)用來算召回率列方向求和得到每個預測類的樣本總數(shù)用來算精確率。max(..., 1)是為了防止某個類在測試集里完全缺席時除零算出來是 0 而不是NaN至少不會污染后面的平均值。只看總體準確率在類別不平衡時會騙人。三類數(shù)據(jù)里有一類占了 90%全判成這一類也能拿到 0.9 的準確率。把stats.recall打出來逐類看哪個類被打成了篩子一目了然比盯一個標量數(shù)字有用得多。4. 性能與精度調(diào)優(yōu)讓手寫 KNN 從玩具代碼變成實驗工具4.1 復雜度賬本訓練是假的預測才是真的貴KNN 是懶惰學習的典型訓練階段什么也不做就是把數(shù)據(jù)存起來復雜度 O(1)所有開銷堆在預測階段每個測試樣本要和全部 N 個訓練樣本算距離總復雜度 $O(M \cdot N \cdot D)$。這個不對稱性意味著「訓練快」根本不是優(yōu)點真正要盯的是預測耗時和內(nèi)存。內(nèi)存這一側(cè)更隱蔽。M×N 的距離矩陣是 double 類型每個元素 8 字節(jié)M5000, N20000就是 800MB稍微再大一點直接 out of memory。而這個矩陣只用來取前 K 個最小值絕大部分內(nèi)容算完就扔占著內(nèi)存純屬浪費。4.2 分塊計算把 M×N 矩陣拆成若干條帶解決辦法是按測試樣本分塊一次只算一塊的距離矩陣算完取完近鄰就釋放function yPred knn_predict_chunked(XTrain, yTrain, XTest, k, blockSize) %KNN_PREDICT_CHUNKED 分塊預測, 把 M×N 距離矩陣壓到 blockSize×N if nargin 5, blockSize 1000; end nTest size(XTest, 1); yPred zeros(nTest, 1); for s 1:blockSize:nTest e min(s blockSize - 1, nTest); yPred(s:e) knn_classify(XTrain, yTrain, XTest(s:e, :), k); end endblockSize是唯一要調(diào)的參數(shù)取值取決于訓練集大小和可用內(nèi)存。經(jīng)驗公式是讓blockSize * N * 8控制在內(nèi)存的三分之一以內(nèi)N20000 時blockSize 取 1000 大概占 160MB很安全N100000 時就得降到 200 以下。分塊之后總計算量不變但峰值內(nèi)存降了一個數(shù)量級而且因為矩陣變小了緩存命中率反而更高實測常常比分塊前還快一點。4.3 parfor 與 knnsearch兩條提速路線怎么選再往上提速有兩條路。第一條是并行把分塊循環(huán)換成parfor前提是已經(jīng)裝了 Parallel Computing Toolbox 并且開了并行池parfor s 1:blockSize:nTest e min(s blockSize - 1, nTest); yPred(s:e) knn_classify(XTrain, yTrain, XTest(s:e, :), k); end注意parfor里不能有跨迭代的共享狀態(tài)yPred用切片方式賦值是合法的但循環(huán)內(nèi)不能再rng或者寫全局變量。加速比取決于核數(shù)4 核大概能到 2.5 到 3 倍核再多收益遞減——瓶頸會轉(zhuǎn)移到內(nèi)存帶寬上。第二條路是直接調(diào)用工具箱的knnsearch% 需要 Statistics and Machine Learning Toolbox [idx, d] knnsearch(XTrain, XTest, K, k, NSMethod, kdtree); yNb yTrain(idx); % 后面接同樣的投票邏輯NSMethod有兩個取值exhaustive是暴力搜索kdtree建 KD 樹。KD 樹在低維D 小于 10 左右時優(yōu)勢明顯建樹一次、查詢多次維度一高就退化得厲害「維數(shù)災難」在 KNN 里體現(xiàn)得特別直接D 到 50 以上時 KD 樹可能比暴力搜索還慢因為這個剪枝結(jié)構(gòu)在高維空間里幾乎失效。方案適用場景內(nèi)存峰值依賴相對耗時雙重循環(huán)只用來對拍驗證正確性最低無最慢向量化全量N×M 小于 1e7高無快分塊向量化大數(shù)據(jù)集常規(guī)方案可控無快分塊 parfor多核機器、離線實驗可控并行工具箱更快knnsearch kdtree低維、多次查詢低統(tǒng)計工具箱低維最快表里的「相對耗時」是定性排序具體倍數(shù)跟機器、維度、數(shù)據(jù)分布都有關(guān)系別照抄。想拿到自己環(huán)境下的真實數(shù)字寫個 benchmark 循環(huán)for r 1:5跑五遍取中位數(shù)比看任何表格都靠譜。4.4 精度側(cè)的三個旋鈕k、權(quán)重、歸一化性能之外真正影響準確率的是三個東西按影響從大到小排。第一個是歸一化。這條幾乎每次都會踩因為不歸一化代碼照樣跑只是準確率悄悄掉下去。量綱差異大的時候尤其致命一個特征范圍是 0 到 255另一個是 0 到 1歐氏距離完全被前者主導后一個特征等于沒參與計算。z-score 之后每個維度方差為 1貢獻才均衡。第二個是 k。k 太小模型方差大一個噪聲點就能翻轉(zhuǎn)結(jié)果k 太大偏差大類邊界被抹平。實踐中從k1掃到ksqrt(N)附近看交叉驗證曲線的最低點。奇數(shù)優(yōu)先能天然規(guī)避兩類平票不過多類問題下平票依然可能第 3 章那段平票處理不能省。第三個是加權(quán)投票。weightedtrue之后近鄰的票數(shù)按距離倒數(shù)加權(quán)靠近邊界的樣本受影響更大通常在類重疊較多的數(shù)據(jù)上能漲一到兩個點。代價是對噪聲更敏感——一個離群點如果恰好離測試樣本很近它的權(quán)重會非常大一個頂十個。數(shù)據(jù)洗干凈之前別急著開這個開關(guān)。5. 避坑記錄Matlab 里跑 KNN 最容易翻車的 5 個地方5.1 現(xiàn)象準確率一直卡在隨機猜的水平原因九成是沒做歸一化或者歸一化的統(tǒng)計量用錯了數(shù)據(jù)。前者讓大方差維度獨占距離后者更隱蔽——在全體數(shù)據(jù)上算mu/sigma再切分測試集的信息泄漏進了訓練過程。還有一種少見但同樣致命的情況csv 里的整數(shù)列被讀成int64X - mu時整型除法直接截斷歸一化等于沒做。解決normalize_zscore只接受訓練集和測試集兩個輸入mu和sigma從訓練集算、保存下來推理時復用同一組。讀數(shù)據(jù)后強制X double(X)。驗證方法很土但有效歸一化之后mean(ZTrain)應該接近全零向量std(ZTrain)接近全一向量打出來看一眼。5.2 現(xiàn)象score(:, c)報下標越界或者預測結(jié)果只有一類原因標簽不是從 1 開始的連續(xù)整數(shù)。原始標簽可能是 0/1/2也可能是字符串元胞數(shù)組直接塞進knn_classify里nClass max(yTrain)算出來的類數(shù)對不上score的列數(shù)和實際類別錯位。解決入口處統(tǒng)一重編號。[~, ~, y] unique(rawLabel)這一句對字符串、數(shù)值、categorical 全都管用輸出保證是1..C的連續(xù)整數(shù)。同時檢查一下y是不是列向量——readtable取出來的可能是行yTrain(idx)的形狀會跟著錯報錯信息指向別處查半天。5.3 現(xiàn)象調(diào)大 k 之后準確率斷崖式下跌某一類被徹底吞掉原因k 超過了某個小類的樣本數(shù)。比如某類只有 5 個訓練樣本k 取 15這 15 個鄰居里屬于該類的頂多 5 票其他類隨便湊湊就壓過去了。類別不平衡時這個問題會放大多數(shù)類的票數(shù)天然占優(yōu)。解決K min(k, size(XTrain,1))只是防越本文還有配套的精品資源點擊獲取