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