現(xiàn)：從距離矩陣到交叉驗(yàn)證全流程)
簡(jiǎn)介面向模式識(shí)別、機(jī)器學(xué)習(xí)課程學(xué)習(xí)者與 Matlab 編程入門者的 KNN 實(shí)踐材料圍繞 KNN 分類原理與代碼實(shí)現(xiàn)展開(kāi)可用于課堂作業(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è)”的示例與說(shuō)明并涉及剪輯近鄰法通過(guò)閾值篩選鄰居以降低噪聲干擾的思路方便讀者對(duì)照理解算法流程、調(diào)試代碼并完成自己的分類任務(wù)。已有 4444 人學(xué)習(xí)下載適合作為 KNN 入門實(shí)踐與作業(yè)參考的輕量資料。1. 從一張分不開(kāi)的散點(diǎn)圖說(shuō)起KNN 為什么總排在模式識(shí)別課的第一位模式識(shí)別這門課的第一個(gè)上機(jī)任務(wù)十有八九是甩給你一份帶標(biāo)簽的數(shù)據(jù)讓你用 KNN 算法跑個(gè)分類 baseline。數(shù)據(jù)發(fā)下來(lái)Matlab 一開(kāi)很多人第一反應(yīng)是敲一行fitcknn交差——能出準(zhǔn)確率但被追問(wèn)一句「距離怎么算的、k 怎么定的、平票怎么處理」當(dāng)場(chǎng)卡殼。這套 Matlab 實(shí)現(xiàn)就是為這個(gè)場(chǎng)景準(zhǔn)備的。它不依賴任何工具箱從距離矩陣、近鄰選取、投票規(guī)則到交叉驗(yàn)證選 k一層層拆開(kāi)寫總共不到兩百行。跑通之后距離函數(shù)、投票權(quán)重、k 的搜索網(wǎng)格都可以隨手替換把它當(dāng)后續(xù)實(shí)驗(yàn)的底座用。適合正在做課設(shè)、想搞清楚每一行在算什么的人也適合已經(jīng)會(huì)用工具箱、但想掀開(kāi)蓋子看看齒輪怎么咬合的人。2. 工程骨架一份能直接跑的 KNN Matlab 實(shí)現(xiàn)由哪幾個(gè)文件組成2.1 目錄結(jié)構(gòu)與每個(gè)文件的職責(zé)先把文件拆開(kāi)。見(jiàn)過(guò)太多把 KNN 塞進(jìn)一個(gè)main.m里寫到四百行的作業(yè)后面想換一種距離度量得在三處地方同時(shí)改改漏一處就跑出個(gè)莫名其妙的結(jié)果排查起來(lái)純屬玄學(xué)。按職責(zé)切分的版本大概長(zhǎng)這樣knn_lab/ ├── main.m % 入口腳本: 造數(shù)據(jù) → 切分 → 歸一化 → 選k → 預(yù)測(cè) → 評(píng)估 ├── make_demo_data.m % 生成帶標(biāo)簽的合成數(shù)據(jù), 用來(lái)打通流程 ├── 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ǔ)語(yǔ)法。R2016b 之后支持隱式擴(kuò)展M×1和1×N相加自動(dòng)廣播成M×Nvecnorm從 R2017b 開(kāi)始才有所以我把距離計(jì)算寫成sum(X.^2, 2)的形式老版本也能跑。rng、sort、unique、sub2ind全是基礎(chǔ)函數(shù)不需要額外裝任何東西。需要說(shuō)明的是knnsearch和fitcknn這兩個(gè)函數(shù)——它們屬于 Statistics and Machine Learning Toolbox。第 4 章會(huì)拿來(lái)做提速對(duì)比但那不是必需品手寫版本單獨(dú)就能跑完整條鏈路。如果你所在的環(huán)境沒(méi)有這個(gè)工具箱跳過(guò)對(duì)比實(shí)驗(yàn)即可。入口腳本main.m按「數(shù)據(jù) → 切分 → 歸一化 → 選參 → 預(yù)測(cè) → 評(píng)估」六步串起來(lái)每一步落一個(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è), 開(kāi)啟距離加權(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)分得開(kāi)任何分類器的準(zhǔn)確率都應(yīng)該在 0.95 以上如果跑出來(lái)只有 0.6那一定是鏈路里某個(gè)環(huán)節(jié)出了問(wèn)題而不是數(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如果想讓問(wèn)題變難把它改成 2 或者 3類之間就開(kāi)始重疊這時(shí)候 k 的取值和加權(quán)策略的影響才會(huì)明顯體現(xiàn)出來(lái)。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)來(lái)讀完先做一次標(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]類別名通過(guò)unique的第一個(gè)輸出保留下來(lái)評(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è)都沒(méi)有那樣混淆矩陣會(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 里能跑上十幾秒。向量化的做法是把平方歐氏距離展開(kāi)$$|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)用寫出來(lái)就是十幾行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 成本極低但沒(méi)有它我至少浪費(fèi)過(guò)一個(gè)下午。metric參數(shù)是給二次開(kāi)發(fā)留的口子。改成cosine之后注意weighted加權(quán)投票邏輯里的1/(deps)依然成立只是物理含義從「距離倒數(shù)」變成了「相似度倒數(shù)」語(yǔ)義上要自己心里有數(shù)。這塊第 6 章會(huì)再展開(kāi)。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 開(kāi)始提供mink做的是部分選擇K 遠(yuǎn)小于 N 時(shí)比sort快不少K min(k, size(XTrain, 1)); % k 不能超過(guò)訓(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)的距離撈出來(lái)。它等價(jià)于用循環(huán)寫for i1:M, dK(i,:) D2(i, idx(i,:)); end但省掉了解釋器開(kāi)銷。數(shù)據(jù)量上萬(wàn)以后這種細(xì)節(jié)的差距是能感覺(jué)到的。3.3 多數(shù)投票score 矩陣怎么建加權(quán)與平票怎么處理核心分類器把前面兩步拼起來(lái)再加一個(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 歸一化過(guò)) % 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è)投票過(guò)程沒(méi)有顯式的樣本循環(huán)。平票是必須處理的分支。K 取偶數(shù)時(shí)比如 k4兩類各 2 票平票是必然發(fā)生的max默認(rèn)返回第一個(gè)最大值的下標(biāo)這就等于「類別號(hào)小的贏」純屬實(shí)現(xiàn)細(xì)節(jié)帶來(lái)的偏見(jiàn)跟算法本身沒(méi)關(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ù)靠拍腦袋定下來(lái)不合適。做法是劃一個(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ì)量只來(lái)自當(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)通過(guò)統(tǒng)計(jì)量泄漏進(jìn)了訓(xùn)練過(guò)程交叉驗(yàn)證的準(zhǔn)確率會(huì)系統(tǒng)性偏高通常高出一兩個(gè)點(diǎn)看起來(lái)不明顯但足以讓你選錯(cuò) k。這種錯(cuò)誤的可怕之處在于它不會(huì)報(bào)錯(cuò)也不會(huì)崩只是讓你拿到的數(shù)字不再可信。accCurve順手返回出來(lái)畫條曲線看看拐點(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ù)用來(lái)算召回率列方向求和得到每個(gè)預(yù)測(cè)類的樣本總數(shù)用來(lái)算精確率。max(..., 1)是為了防止某個(gè)類在測(cè)試集里完全缺席時(shí)除零算出來(lái)是 0 而不是NaN至少不會(huì)污染后面的平均值。只看總體準(zhǔn)確率在類別不平衡時(shí)會(huì)騙人。三類數(shù)據(jù)里有一類占了 90%全判成這一類也能拿到 0.9 的準(zhǔn)確率。把stats.recall打出來(lái)逐類看哪個(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ù)存起來(lái)復(fù)雜度 O(1)所有開(kāi)銷堆在預(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è)矩陣只用來(lái)取前 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 并且開(kāi)了并行池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 樹(shù)。KD 樹(shù)在低維D 小于 10 左右時(shí)優(yōu)勢(shì)明顯建樹(shù)一次、查詢多次維度一高就退化得厲害「維數(shù)災(zāi)難」在 KNN 里體現(xiàn)得特別直接D 到 50 以上時(shí) KD 樹(shù)可能比暴力搜索還慢因?yàn)檫@個(gè)剪枝結(jié)構(gòu)在高維空間里幾乎失效。方案適用場(chǎng)景內(nèi)存峰值依賴相對(duì)耗時(shí)雙重循環(huán)只用來(lái)對(duì)拍驗(yàn)證正確性最低無(wú)最慢向量化全量N×M 小于 1e7高無(wú)快分塊向量化大數(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è)特征等于沒(méi)參與計(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ī)避兩類平票不過(guò)多類問(wèn)題下平票依然可能第 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ù)洗干凈之前別急著開(kāi)這個(gè)開(kāi)關(guān)。5. 避坑記錄Matlab 里跑 KNN 最容易翻車的 5 個(gè)地方5.1 現(xiàn)象準(zhǔn)確率一直卡在隨機(jī)猜的水平原因九成是沒(méi)做歸一化或者歸一化的統(tǒng)計(jì)量用錯(cuò)了數(shù)據(jù)。前者讓大方差維度獨(dú)占距離后者更隱蔽——在全體數(shù)據(jù)上算mu/sigma再切分測(cè)試集的信息泄漏進(jìn)了訓(xùn)練過(guò)程。還有一種少見(jiàn)但同樣致命的情況csv 里的整數(shù)列被讀成int64X - mu時(shí)整型除法直接截?cái)鄽w一化等于沒(méi)做。解決normalize_zscore只接受訓(xùn)練集和測(cè)試集兩個(gè)輸入mu和sigma從訓(xùn)練集算、保存下來(lái)推理時(shí)復(fù)用同一組。讀數(shù)據(jù)后強(qiáng)制X double(X)。驗(yàn)證方法很土但有效歸一化之后mean(ZTrain)應(yīng)該接近全零向量std(ZTrain)接近全一向量打出來(lái)看一眼。5.2 現(xiàn)象score(:, c)報(bào)下標(biāo)越界或者預(yù)測(cè)結(jié)果只有一類原因標(biāo)簽不是從 1 開(kāi)始的連續(xù)整數(shù)。原始標(biāo)簽可能是 0/1/2也可能是字符串元胞數(shù)組直接塞進(jìn)knn_classify里nClass max(yTrain)算出來(lái)的類數(shù)對(duì)不上score的列數(shù)和實(shí)際類別錯(cuò)位。解決入口處統(tǒng)一重編號(hào)。[~, ~, y] unique(rawLabel)這一句對(duì)字符串、數(shù)值、categorical 全都管用輸出保證是1..C的連續(xù)整數(shù)。同時(shí)檢查一下y是不是列向量——readtable取出來(lái)的可能是行yTrain(idx)的形狀會(huì)跟著錯(cuò)報(bào)錯(cuò)信息指向別處查半天。5.3 現(xiàn)象調(diào)大 k 之后準(zhǔn)確率斷崖式下跌某一類被徹底吞掉原因k 超過(guò)了某個(gè)小類的樣本數(shù)。比如某類只有 5 個(gè)訓(xùn)練樣本k 取 15這 15 個(gè)鄰居里屬于該類的頂多 5 票其他類隨便湊湊就壓過(guò)去了。類別不平衡時(shí)這個(gè)問(wèn)題會(huì)放大多數(shù)類的票數(shù)天然占優(yōu)。解決K min(k, size(XTrain,1))只是防越本文還有配套的精品資源點(diǎn)擊獲取 手寫Matlab KNN實(shí)現(xiàn)：從距離矩陣到交叉驗(yàn)證全流程
簡(jiǎn)介面向模式識(shí)別、機(jī)器學(xué)習(xí)課程學(xué)習(xí)者與 Matlab 編程入門者的 KNN 實(shí)踐材料圍繞 KNN 分類原理與代碼實(shí)現(xiàn)展開(kāi)可用于課堂作業(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è)”的示例與說(shuō)明并涉及剪輯近鄰法通過(guò)閾值篩選鄰居以降低噪聲干擾的思路方便讀者對(duì)照理解算法流程、調(diào)試代碼并完成自己的分類任務(wù)。已有 4444 人學(xué)習(xí)下載適合作為 KNN 入門實(shí)踐與作業(yè)參考的輕量資料。1. 從一張分不開(kāi)的散點(diǎn)圖說(shuō)起KNN 為什么總排在模式識(shí)別課的第一位模式識(shí)別這門課的第一個(gè)上機(jī)任務(wù)十有八九是甩給你一份帶標(biāo)簽的數(shù)據(jù)讓你用 KNN 算法跑個(gè)分類 baseline。數(shù)據(jù)發(fā)下來(lái)Matlab 一開(kāi)很多人第一反應(yīng)是敲一行fitcknn交差——能出準(zhǔn)確率但被追問(wèn)一句「距離怎么算的、k 怎么定的、平票怎么處理」當(dāng)場(chǎng)卡殼。這套 Matlab 實(shí)現(xiàn)就是為這個(gè)場(chǎng)景準(zhǔn)備的。它不依賴任何工具箱從距離矩陣、近鄰選取、投票規(guī)則到交叉驗(yàn)證選 k一層層拆開(kāi)寫總共不到兩百行。跑通之后距離函數(shù)、投票權(quán)重、k 的搜索網(wǎng)格都可以隨手替換把它當(dāng)后續(xù)實(shí)驗(yàn)的底座用。適合正在做課設(shè)、想搞清楚每一行在算什么的人也適合已經(jīng)會(huì)用工具箱、但想掀開(kāi)蓋子看看齒輪怎么咬合的人。2. 工程骨架一份能直接跑的 KNN Matlab 實(shí)現(xiàn)由哪幾個(gè)文件組成2.1 目錄結(jié)構(gòu)與每個(gè)文件的職責(zé)先把文件拆開(kāi)。見(jiàn)過(guò)太多把 KNN 塞進(jìn)一個(gè)main.m里寫到四百行的作業(yè)后面想換一種距離度量得在三處地方同時(shí)改改漏一處就跑出個(gè)莫名其妙的結(jié)果排查起來(lái)純屬玄學(xué)。按職責(zé)切分的版本大概長(zhǎng)這樣knn_lab/ ├── main.m % 入口腳本: 造數(shù)據(jù) → 切分 → 歸一化 → 選k → 預(yù)測(cè) → 評(píng)估 ├── make_demo_data.m % 生成帶標(biāo)簽的合成數(shù)據(jù), 用來(lái)打通流程 ├── 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ǔ)語(yǔ)法。R2016b 之后支持隱式擴(kuò)展M×1和1×N相加自動(dòng)廣播成M×Nvecnorm從 R2017b 開(kāi)始才有所以我把距離計(jì)算寫成sum(X.^2, 2)的形式老版本也能跑。rng、sort、unique、sub2ind全是基礎(chǔ)函數(shù)不需要額外裝任何東西。需要說(shuō)明的是knnsearch和fitcknn這兩個(gè)函數(shù)——它們屬于 Statistics and Machine Learning Toolbox。第 4 章會(huì)拿來(lái)做提速對(duì)比但那不是必需品手寫版本單獨(dú)就能跑完整條鏈路。如果你所在的環(huán)境沒(méi)有這個(gè)工具箱跳過(guò)對(duì)比實(shí)驗(yàn)即可。入口腳本main.m按「數(shù)據(jù) → 切分 → 歸一化 → 選參 → 預(yù)測(cè) → 評(píng)估」六步串起來(lái)每一步落一個(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è), 開(kāi)啟距離加權(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)分得開(kāi)任何分類器的準(zhǔn)確率都應(yīng)該在 0.95 以上如果跑出來(lái)只有 0.6那一定是鏈路里某個(gè)環(huán)節(jié)出了問(wèn)題而不是數(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如果想讓問(wèn)題變難把它改成 2 或者 3類之間就開(kāi)始重疊這時(shí)候 k 的取值和加權(quán)策略的影響才會(huì)明顯體現(xiàn)出來(lái)。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)來(lái)讀完先做一次標(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]類別名通過(guò)unique的第一個(gè)輸出保留下來(lái)評(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è)都沒(méi)有那樣混淆矩陣會(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 里能跑上十幾秒。向量化的做法是把平方歐氏距離展開(kāi)$$|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)用寫出來(lái)就是十幾行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 成本極低但沒(méi)有它我至少浪費(fèi)過(guò)一個(gè)下午。metric參數(shù)是給二次開(kāi)發(fā)留的口子。改成cosine之后注意weighted加權(quán)投票邏輯里的1/(deps)依然成立只是物理含義從「距離倒數(shù)」變成了「相似度倒數(shù)」語(yǔ)義上要自己心里有數(shù)。這塊第 6 章會(huì)再展開(kāi)。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 開(kāi)始提供mink做的是部分選擇K 遠(yuǎn)小于 N 時(shí)比sort快不少K min(k, size(XTrain, 1)); % k 不能超過(guò)訓(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)的距離撈出來(lái)。它等價(jià)于用循環(huán)寫for i1:M, dK(i,:) D2(i, idx(i,:)); end但省掉了解釋器開(kāi)銷。數(shù)據(jù)量上萬(wàn)以后這種細(xì)節(jié)的差距是能感覺(jué)到的。3.3 多數(shù)投票score 矩陣怎么建加權(quán)與平票怎么處理核心分類器把前面兩步拼起來(lái)再加一個(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 歸一化過(guò)) % 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è)投票過(guò)程沒(méi)有顯式的樣本循環(huán)。平票是必須處理的分支。K 取偶數(shù)時(shí)比如 k4兩類各 2 票平票是必然發(fā)生的max默認(rèn)返回第一個(gè)最大值的下標(biāo)這就等于「類別號(hào)小的贏」純屬實(shí)現(xiàn)細(xì)節(jié)帶來(lái)的偏見(jiàn)跟算法本身沒(méi)關(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ù)靠拍腦袋定下來(lái)不合適。做法是劃一個(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ì)量只來(lái)自當(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)通過(guò)統(tǒng)計(jì)量泄漏進(jìn)了訓(xùn)練過(guò)程交叉驗(yàn)證的準(zhǔn)確率會(huì)系統(tǒng)性偏高通常高出一兩個(gè)點(diǎn)看起來(lái)不明顯但足以讓你選錯(cuò) k。這種錯(cuò)誤的可怕之處在于它不會(huì)報(bào)錯(cuò)也不會(huì)崩只是讓你拿到的數(shù)字不再可信。accCurve順手返回出來(lái)畫條曲線看看拐點(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ù)用來(lái)算召回率列方向求和得到每個(gè)預(yù)測(cè)類的樣本總數(shù)用來(lái)算精確率。max(..., 1)是為了防止某個(gè)類在測(cè)試集里完全缺席時(shí)除零算出來(lái)是 0 而不是NaN至少不會(huì)污染后面的平均值。只看總體準(zhǔn)確率在類別不平衡時(shí)會(huì)騙人。三類數(shù)據(jù)里有一類占了 90%全判成這一類也能拿到 0.9 的準(zhǔn)確率。把stats.recall打出來(lái)逐類看哪個(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ù)存起來(lái)復(fù)雜度 O(1)所有開(kāi)銷堆在預(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è)矩陣只用來(lái)取前 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 并且開(kāi)了并行池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 樹(shù)。KD 樹(shù)在低維D 小于 10 左右時(shí)優(yōu)勢(shì)明顯建樹(shù)一次、查詢多次維度一高就退化得厲害「維數(shù)災(zāi)難」在 KNN 里體現(xiàn)得特別直接D 到 50 以上時(shí) KD 樹(shù)可能比暴力搜索還慢因?yàn)檫@個(gè)剪枝結(jié)構(gòu)在高維空間里幾乎失效。方案適用場(chǎng)景內(nèi)存峰值依賴相對(duì)耗時(shí)雙重循環(huán)只用來(lái)對(duì)拍驗(yàn)證正確性最低無(wú)最慢向量化全量N×M 小于 1e7高無(wú)快分塊向量化大數(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è)特征等于沒(méi)參與計(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ī)避兩類平票不過(guò)多類問(wèn)題下平票依然可能第 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ù)洗干凈之前別急著開(kāi)這個(gè)開(kāi)關(guān)。5. 避坑記錄Matlab 里跑 KNN 最容易翻車的 5 個(gè)地方5.1 現(xiàn)象準(zhǔn)確率一直卡在隨機(jī)猜的水平原因九成是沒(méi)做歸一化或者歸一化的統(tǒng)計(jì)量用錯(cuò)了數(shù)據(jù)。前者讓大方差維度獨(dú)占距離后者更隱蔽——在全體數(shù)據(jù)上算mu/sigma再切分測(cè)試集的信息泄漏進(jìn)了訓(xùn)練過(guò)程。還有一種少見(jiàn)但同樣致命的情況csv 里的整數(shù)列被讀成int64X - mu時(shí)整型除法直接截?cái)鄽w一化等于沒(méi)做。解決normalize_zscore只接受訓(xùn)練集和測(cè)試集兩個(gè)輸入mu和sigma從訓(xùn)練集算、保存下來(lái)推理時(shí)復(fù)用同一組。讀數(shù)據(jù)后強(qiáng)制X double(X)。驗(yàn)證方法很土但有效歸一化之后mean(ZTrain)應(yīng)該接近全零向量std(ZTrain)接近全一向量打出來(lái)看一眼。5.2 現(xiàn)象score(:, c)報(bào)下標(biāo)越界或者預(yù)測(cè)結(jié)果只有一類原因標(biāo)簽不是從 1 開(kāi)始的連續(xù)整數(shù)。原始標(biāo)簽可能是 0/1/2也可能是字符串元胞數(shù)組直接塞進(jìn)knn_classify里nClass max(yTrain)算出來(lái)的類數(shù)對(duì)不上score的列數(shù)和實(shí)際類別錯(cuò)位。解決入口處統(tǒng)一重編號(hào)。[~, ~, y] unique(rawLabel)這一句對(duì)字符串、數(shù)值、categorical 全都管用輸出保證是1..C的連續(xù)整數(shù)。同時(shí)檢查一下y是不是列向量——readtable取出來(lái)的可能是行yTrain(idx)的形狀會(huì)跟著錯(cuò)報(bào)錯(cuò)信息指向別處查半天。5.3 現(xiàn)象調(diào)大 k 之后準(zhǔn)確率斷崖式下跌某一類被徹底吞掉原因k 超過(guò)了某個(gè)小類的樣本數(shù)。比如某類只有 5 個(gè)訓(xùn)練樣本k 取 15這 15 個(gè)鄰居里屬于該類的頂多 5 票其他類隨便湊湊就壓過(guò)去了。類別不平衡時(shí)這個(gè)問(wèn)題會(huì)放大多數(shù)類的票數(shù)天然占優(yōu)。解決K min(k, size(XTrain,1))只是防越本文還有配套的精品資源點(diǎn)擊獲取