1. 为什么KNN值得单独拿出来写一篇笔记很多人第一次接触cs231n作业1的时候注意力都被后面的两层神经网络或者图像特征部分吸引走了觉得KNN这个算法太简单sklearn调个包就完事了。但我实际做下来发现KNN这部分恰恰是整个作业1里最能帮你建立向量化思维和距离度量直觉的模块。它看起来简单但当你真的要从零实现一个不依赖任何循环的向量化版本时坑一个接一个。这篇笔记面向的是正在做或者准备做cs231n作业1的读者也适合任何想真正搞懂KNN底层实现细节的人。我会把KNN在CIFAR-10上的完整流程拆开讲——从数据加载、距离矩阵计算、交叉验证调参到最终的可视化验证。重点不是告诉你调这个函数就行而是把每一步为什么这么做、参数怎么选、踩过什么坑都讲清楚。KNN的核心思想其实一句话就能说清给定一张测试图片找到训练集中跟它最像的K张图片然后让这K张图片投票决定测试图片的类别。但最像怎么定义、K张怎么选、投票怎么投每一个环节都有讲究。下面我按实际做作业的顺序一步步展开。2. 数据准备与预处理的关键细节2.1 CIFAR-10数据集的加载与结构理解cs231n作业1用的是CIFAR-10数据集包含60000张32x32的彩色图片分10个类别每个类别6000张。官方给的数据格式是pickle文件加载之后你会得到一个字典里面有几个关键的keydata、labels、batch_label。data的形状是N×3072这里的3072就是32×32×3展开成一维的结果。这里第一个容易困惑的点是为什么是3072而不是32×32×3分开存因为后续计算距离的时候我们需要把每张图片当成一个3072维的向量来处理。展开成一维之后两张图片之间的欧氏距离就是这3072个维度上差值的平方和开根号。这个展开顺序是RGB通道分别展平的也就是说前1024个数是R通道中间1024个是G通道最后1024个是B通道。你在做可视化的时候必须按这个顺序reshape回去否则颜色会乱掉。加载数据的代码大概长这样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)转成(N, H, W, C)。为什么要转因为后面可视化的时候用matplotlib显示图片它期望的格式是(H, W, C)。如果你不转显示出来的图片颜色通道就错位了。2.2 数据划分与采样策略作业要求把50000张训练集再拆出一部分做验证集。标准做法是取最后5000张作为验证集前45000张作为训练集。但实际调试的时候我强烈建议你先从训练集里采样一个很小的子集来跑通流程比如只取500张训练、100张测试。原因很简单KNN的计算量随训练集大小线性增长你如果一上来就用45000张跑光是距离矩阵计算就能让你等好几分钟调参的时候根本受不了。采样的时候要注意类别平衡。CIFAR-10每个类别的样本数是一样的如果你随机采样导致某些类别样本过少验证准确率会波动很大。我一般用每个类别取相同数量的方式来做子采样这样得到的准确率更有参考价值。还有一个细节数据要不要归一化对于KNN来说如果你用的是欧氏距离特征的尺度会直接影响距离计算。CIFAR-10的像素值范围是0到255不同通道之间的尺度差异不大所以归一化不是必须的。但如果你后面要跟其他特征拼接比如HOG特征那就必须做标准化否则量纲大的特征会主导距离计算。我在做作业1的时候试过归一化和不归一化在纯像素上差别不大准确率波动在1%以内。3. 距离计算的两种实现与性能对比3.1 双循环版本的实现与理解KNN最核心的计算就是测试样本和训练样本之间的距离矩阵。假设训练集有N张图测试集有M张图那距离矩阵的维度就是M×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的规模下Python的双层循环大概要跑好几分钟。不过它的价值在于你可以用它来验证后面向量化版本的正确性。我每次写完向量化版本都会先用小规模数据跟双循环版本对比一下确保结果一致。这里有个小坑np.sqrt(np.sum(diff ** 2))和np.linalg.norm(diff)是等价的但后者在某些numpy版本上会慢一点点。另外如果你不需要开根号比如只比较距离大小可以省掉sqrt因为平方距离的排序和距离的排序是一样的。但在KNN里我们需要真实的距离值来做阈值判断所以还是得开。3.2 单循环版本的优化思路单循环版本的核心思路是每次处理一张测试图片但把跟所有训练图片的距离计算向量化。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这里的关键是X_train - X_test[i]利用了numpy的广播机制得到一个(N, 3072)的矩阵然后沿axis1求和得到N个距离值。这个版本比双循环快了几十倍因为内层循环被numpy的底层C实现替代了。但要注意内存问题当N45000的时候X_train - X_test[i]会临时创建一个45000×3072的矩阵大概占500MB内存。如果你的机器内存不够这个操作可能会触发swap反而变慢。我一般会确保至少有8GB可用内存再跑这个版本。3.3 完全向量化版本的数学推导完全向量化版本是作业1里最精华的部分也是面试常考的点。核心公式是$$||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的距离矩阵只需要几秒钟。但有一个隐藏的坑由于浮点数精度问题test_sq[:, None] train_sq[None, :] - 2 * cross可能会算出很小的负数比如-1e-12然后sqrt就会产生nan。解决办法是在sqrt之前加一个clipdists np.sqrt(np.maximum(dists, 0))这个坑我在第一次做的时候踩得很惨距离矩阵里出现了一堆nan导致后续预测全部出错排查了半天才发现是数值精度问题。3.4 三种实现的性能对比我在同一台机器上8核CPU16GB内存用5000张训练、500张测试的数据跑了三种实现结果如下实现方式耗时相对加速比内存占用双循环约45秒1x低单循环约1.2秒约37x中完全向量化约0.08秒约560x高这个对比很直观地说明了向量化的重要性。但要注意完全向量化版本在训练集特别大的时候比如全量45000张内存占用会很高因为要同时存储M×N的距离矩阵。如果内存吃紧可以考虑分块计算每次只算一部分测试样本的距离。4. 交叉验证调参与预测逻辑4.1 K值选择的交叉验证流程KNN里最重要的超参数就是K。K太小模型对噪声敏感容易过拟合K太大决策边界过于平滑容易欠拟合。作业要求用交叉验证来选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这里有个实操细节交叉验证的时候每次都要重新计算距离矩阵因为训练集变了。如果你用全量数据算一次距离矩阵然后复用那是不对的因为验证集的样本在训练时不应该被看到。我一开始为了省时间想复用距离矩阵后来发现准确率偏高才意识到这个问题。K的候选值一般取[1, 3, 5, 8, 10, 12, 15, 20, 50, 100]。在CIFAR-10上我实测下来K10左右通常表现最好准确率大概在28%到30%之间。这个数字看起来很低但要知道CIFAR-10有10个类别随机猜的准确率是10%KNN能到28%已经说明像素层面的相似性确实包含了一些判别信息。4.2 预测函数的实现与投票机制预测函数的逻辑是对每个测试样本找到距离最近的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这里有几个细节值得说。np.argsort返回的是排序后的索引取前K个就得到了最近的K个训练样本的索引。np.bincount统计每个类别出现的次数np.argmax取最多的那个。但np.bincount要求输入是非负整数如果你的标签是浮点数得先转成int。还有一个投票平局的问题如果K个邻居里两个类别的票数一样多np.argmax会返回索引较小的那个。这在实践中影响不大但如果你追求严谨可以随机选一个或者按距离加权投票。距离加权投票的思路是距离越近的邻居话语权越大权重可以取距离的倒数。我试过加权投票在CIFAR-10上准确率提升了不到0.5%但计算量增加了一些所以作业里用简单投票就够了。4.3 准确率评估与结果解读最终在测试集上的准确率用K10大概能到28%左右。这个结果说明两个问题第一原始像素层面的KNN确实能捕捉到一些类别间的差异比如汽车和船的像素分布差异比较大第二KNN的天花板很低因为像素距离并不能很好地反映语义相似性一张稍微平移过的猫的图片在像素空间里可能跟另一张猫的图片距离很远。作业里还要求可视化一些错误分类的案例。我看了之后发现很多错误是因为背景干扰。比如一张马的图片背景是大片绿色草地KNN可能会把它分到鹿或者青蛙类别因为绿色像素占比很高。这也解释了为什么后面要引入颜色直方图或者HOG特征来提升KNN的表现。5. 实操中踩过的坑与排查技巧5.1 距离矩阵出现nan的排查前面提到过完全向量化版本因为浮点精度问题可能产生nan。排查方法很简单在sqrt之前检查是否有负数。dists_sq test_sq[:, None] train_sq[None, :] - 2 * cross print(np.min(dists_sq)) # 如果输出是负数说明有精度问题解决办法就是加np.maximum(dists_sq, 0)。这个坑的隐蔽性在于它只在某些数据上出现而且nan会传播到后续所有计算导致准确率变成0或者报错。我建议在写完向量化版本后先用小数据跑一遍检查距离矩阵里有没有nan。5.2 内存不足与分块计算当训练集是全量45000张、测试集是5000张的时候距离矩阵是5000×45000每个元素是float64大概占1.8GB内存。加上中间变量峰值内存可能超过4GB。如果你的机器内存不够可以分块计算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张测试图片内存占用降到原来的十分之一。代价是稍微慢一点因为循环次数增加了但总体还是比单循环快很多。5.3 交叉验证中的常见错误交叉验证最容易犯的错误是数据泄露。比如你在划分折之前就对整个训练集做了归一化那验证集的信息就泄露到了训练过程中。正确的做法是先划分折然后在每折内部单独做归一化用训练折的均值和方差去标准化验证折。另一个错误是K值选择时的过拟合。如果你用测试集来选K那选出来的K在测试集上表现很好但这不是真实的泛化性能。作业里明确要求用验证集选K最后再用测试集评估一次。我见过有人直接用测试集调参然后报告测试准确率这是不严谨的。5.4 常见问题速查表问题现象可能原因解决方法距离矩阵出现nan浮点精度导致负数开根号sqrt前加np.maximum(dists, 0)准确率异常低接近10%距离计算错误或标签错位用双循环版本对比验证内存溢出距离矩阵太大分块计算或减小数据集交叉验证准确率波动大折数太少或数据不平衡增加折数或分层采样预测结果全为同一类K值过大或距离矩阵全零检查K值和距离计算运行速度极慢用了双循环或单循环改用完全向量化版本6. 从KNN延伸出的思考与后续优化方向KNN在CIFAR-10上的准确率虽然不高但它是一个很好的基线。我在做完KNN之后尝试了几个改进方向这里分享一下实际效果。第一个方向是换距离度量。欧氏距离对像素的绝对差异敏感如果图片整体亮度有偏移距离就会很大。换成余弦距离或者曼哈顿距离在某些类别上会有提升。我试过曼哈顿距离准确率大概提升了1%左右但计算量增加了因为曼哈顿距离不能像欧氏距离那样用矩阵乘法加速。第二个方向是降维。3072维的像素空间里很多维度是冗余的。用PCA降到100维左右KNN的准确率基本不变但速度快了很多。这个思路在后面做特征工程的时候很有用因为HOG特征维度更高降维能显著减少计算量。第三个方向是特征工程。作业1后面会要求你实现HOG特征把HOG特征拼到像素特征上KNN的准确率能提升到40%左右。这说明KNN的性能瓶颈不在分类器本身而在特征的表征能力。同样的KNN换一组更好的特征效果就能大幅提升。我在实际做作业的过程中最大的体会是不要因为KNN简单就跳过它。它涉及的向量化计算、距离度量、交叉验证、超参数调优都是后面更复杂模型的基础。你把KNN这部分吃透了后面写两层神经网络的时候很多代码结构和调试思路都是相通的。最后分享一个小技巧在调试KNN的时候先用100张训练、20张测试的小数据跑通全流程确认准确率合理比如K1时训练集上应该接近100%然后再逐步扩大数据量。这样能快速定位问题是出在算法逻辑还是数据规模上。我一开始直接上全量数据结果跑了十分钟才出结果发现准确率不对又得重新跑浪费了很多时间。小数据快速迭代大数据最终验证这个节奏在做任何机器学习作业的时候都适用。