65、C++项目实战：K近邻算法实现
K近邻算法，说白了就是“近朱者赤，近墨者黑”。
你想想看，要判断一个新样本属于哪一类，最简单的方法是什么？看看它周围最近的几个邻居都是什么类别，然后投票决定。这就是KNN的核心思想。
我个人习惯把KNN叫做“懒人算法”——因为它训练阶段啥也不干，就是把数据存起来。真正干活是在预测的时候。嗯，这里要注意，这种“懒惰”既是优点也是缺点，后面我会细说。
算法原理与核心要素
KNN算法有三个核心要素，我当年刚接触时总觉得很简单，直到在项目中踩了坑才真正理解它们的重要性。
KNN三要素：
- K值选择：邻居的数量。K太小容易过拟合，K太大又会让边界变得模糊。
- 距离度量：怎么算“近”？最常用的是欧氏距离，但曼哈顿距离、余弦相似度也各有适用场景。
- 决策规则：多数投票是最简单的，但也可以加权投票——离得近的邻居话语权更大。
我曾经在一个图像分类项目里用过KNN，当时K值设成了1，结果测试集上准确率惨不忍睹。后来改成K=5，效果立马好了不少。所以K值的选择，真的不是拍脑袋就能定的。
距离计算：欧氏距离与曼哈顿距离
距离度量是KNN的基石。我给大家列一下最常见的两种：
| 距离类型 | 公式 | 适用场景 |
|---|---|---|
| 欧氏距离 | d = √(Σ(xi - yi)²) | 连续数值特征，各维度量纲一致 |
| 曼哈顿距离 | d = Σ|xi - yi| | 高维数据，或特征为离散值 |
为什么会有两种？其实很好理解。欧氏距离是直线距离，曼哈顿距离是沿着坐标轴走的距离。你想想看，在城市里从一个路口到另一个路口，你只能沿着街道走，这就是曼哈顿距离。
我的经验：如果特征维度很高（比如超过100维），欧氏距离的效果会急剧下降。这时候我建议试试曼哈顿距离，或者先做降维处理。
K值选择与交叉验证
K值怎么选？我见过有人直接拍脑袋定K=3，结果模型泛化能力很差。正确的做法是用交叉验证。
具体来说，就是把训练数据分成几份，轮流拿一份做验证，剩下的训练。然后试不同的K值，看哪个K在验证集上表现最好。
避坑指南：我曾经在一个项目里直接用了K=训练样本数，结果模型永远预测为多数类。后来才意识到，K值不能太大，一般不超过样本数的平方根。另外，K值最好选奇数，避免平票的情况。
C++实现：从零搭建KNN分类器
好了，理论说完了，咱们直接上代码。我习惯把KNN封装成一个类，这样用起来方便。
#include <vector>
#include <cmath>
#include <algorithm>
#include <map>
class KNN {
private:
std::vector<std::vector<double>> trainData;
std::vector<int> trainLabels;
int k;
double euclideanDistance(const std::vector<double>& a,
const std::vector<double>& b) {
double sum = 0.0;
for (size_t i = 0; i < a.size(); ++i) {
sum += (a[i] - b[i]) * (a[i] - b[i]);
}
return std::sqrt(sum);
}
public:
KNN(int kValue) : k(kValue) {}
void fit(const std::vector<std::vector<double>>& X,
const std::vector<int>& y) {
trainData = X;
trainLabels = y;
}
int predict(const std::vector<double>& sample) {
// 计算所有距离
std::vector<std::pair<double, int>> distances;
for (size_t i = 0; i < trainData.size(); ++i) {
double dist = euclideanDistance(sample, trainData[i]);
distances.push_back({dist, trainLabels[i]});
}
// 排序取前K个
std::sort(distances.begin(), distances.end());
std::map<int, int> voteCount;
for (int i = 0; i < k; ++i) {
voteCount[distances[i].second]++;
}
// 投票决定类别
int bestLabel = -1;
int maxVotes = 0;
for (auto& pair : voteCount) {
if (pair.second > maxVotes) {
maxVotes = pair.second;
bestLabel = pair.first;
}
}
return bestLabel;
}
};这段代码看着简单，但有几个细节我提醒一下：
- 距离计算用了欧氏距离，如果你想换曼哈顿距离，改一下那个函数就行
- 排序用的是std::sort，默认升序，正好取前K个最小的距离
- 投票用了std::map，自动按类别统计票数
特征归一化：容易被忽略的一步
我刚开始用KNN时犯过一个错误——没做特征归一化。结果某个特征的数值范围特别大（比如年龄0-100），另一个特征范围特别小（比如收入0-1万），距离计算完全被大数值特征主导了。
解决办法很简单：把所有特征缩放到同一个范围，比如[0,1]或[-1,1]。
void normalize(std::vector<std::vector<double>>& data) {
if (data.empty()) return;
size_t dim = data[0].size();
for (size_t j = 0; j < dim; ++j) {
double minVal = data[0][j], maxVal = data[0][j];
for (size_t i = 0; i < data.size(); ++i) {
minVal = std::min(minVal, data[i][j]);
maxVal = std::max(maxVal, data[i][j]);
}
double range = maxVal - minVal;
if (range == 0) continue;
for (size_t i = 0; i < data.size(); ++i) {
data[i][j] = (data[i][j] - minVal) / range;
}
}
}小技巧：归一化参数（min和max）要从训练集计算，然后应用到测试集上。千万别把测试集和训练集混在一起算归一化，那样会数据泄露，导致评估结果虚高。
KNN的优缺点与适用场景
说实话，KNN不是万能的。我整理了一下它的优缺点：
| 优点 | 缺点 |
|---|---|
| 原理简单，容易理解 | 预测速度慢（要算所有距离） |
| 无需训练过程 | 对特征尺度敏感 |
| 适合多分类问题 | 维度灾难（高维数据效果差） |
| 可以处理非线性边界 | 需要大量内存存储数据 |
你想想看，如果你的数据集有100万条，每次预测都要算100万个距离，那速度肯定慢得让人抓狂。所以KNN更适合中小规模的数据集，或者作为基线模型来对比。
核心逻辑流程图
下面这张图展示了KNN从训练到预测的完整流程，我画出来方便大家理解：
性能优化：KD树与近似搜索
前面说了，KNN的预测速度是个瓶颈。怎么优化？我常用的方法有两个：
- KD树：把数据组织成树形结构，搜索时只遍历部分节点，不用算所有距离。适合低维数据（维度<20）。
- 近似最近邻：不找绝对最近的K个，而是找“差不多最近”的。速度能快几个数量级，适合海量数据。
我记得在一个推荐系统项目里，数据量有50万条，直接用暴力搜索每次预测要花0.5秒。换成KD树后，降到了5毫秒。用户体验直接上了一个台阶。
总结一下：KNN虽然简单，但用好了威力不小。关键是要处理好K值选择、特征归一化和距离度量这三个点。如果你刚开始学机器学习，我建议从KNN入手——它直观、好理解，而且能帮你建立对分类问题的直觉。
好了，K近邻算法就讲到这里。代码我已经贴出来了，建议你亲手跑一跑，改改K值，看看效果怎么变。实践出真知嘛。