一、引言

        在机器学习领域，K最近邻（K-Nearest Neighbors，KNN）算法以其简单直观的特性，成为了很多初学者入门的第一课。今天，我将手把手教你如何使用C++实现一个完整的KNN分类器，不仅理解算法原理，还能掌握实际的编程技巧。

        什么是KNN算法？

        KNN是一种基于实例的学习算法，它的核心思想可以用一句俗语概括："近朱者赤，近墨者黑"。简单来说，一个样本的类别可以由它最接近的k个邻居的类别来决定。

        算法工作原理：

1. 距离计算：计算测试样本与所有训练样本的距离

2. 寻找邻居：选择距离最近的k个训练样本

3. 投票决策：根据这k个邻居的类别进行投票，票数最多的类别即为预测结果

二、C++实现核心代码

        下面让我们一步步实现KNN分类器的核心部分。

2.1 类定义与基础结构：

class KNNClassifier {
private:
    std::vector<std::vector<double>> trainFeatures; // 存储训练特征
    std::vector<int> trainLabels;                   // 存储训练标签
    int k;                                          // K值参数

public:
    // 构造函数，初始化K值
    KNNClassifier(int k) : k(k) {}
    
    // 训练方法：存储训练数据
    void fit(const std::vector<std::vector<double>>& features, 
             const std::vector<int>& labels) {
        trainFeatures = features;
        trainLabels = labels;
    }
};

2.2 距离计算：算法的核心

        距离度量是KNN算法的关键，我们使用最常用的欧氏距离：

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 += pow(a[i] - b[i], 2);  // 计算平方差
    }
    return sqrt(sum);  // 开方得到欧氏距离
}

性能提示：在实际应用中，我们可以省略开方运算，因为距离的大小关系不变，这样可以提升计算速度。

2.3 预测逻辑：实现KNN精髓

int predict(const std::vector<double>& sample) {
    // 存储所有训练样本与测试样本的距离及其索引
    std::vector<std::pair<double, int>> distances;
    
    // 计算测试样本与每个训练样本的距离
    for (size_t i = 0; i < trainFeatures.size(); ++i) {
        double dist = euclideanDistance(sample, trainFeatures[i]);
        distances.push_back({dist, i});  // 保存距离和对应的训练样本索引
    }
    
    // 按距离从小到大排序
    std::sort(distances.begin(), distances.end());
    
    // 统计前k个最近邻居的类别投票
    std::map<int, int> voteCount;
    for (int i = 0; i < k; ++i) {
        int neighborIndex = distances[i].second;
        int label = trainLabels[neighborIndex];
        voteCount[label]++;  // 对应类别票数加1
    }
    
    // 找出票数最多的类别
    int predictedLabel = -1;
    int maxVotes = 0;
    for (const auto& vote : voteCount) {
        if (vote.second > maxVotes) {
            maxVotes = vote.second;
            predictedLabel = vote.first;
        }
    }
    
    return predictedLabel;
}

2.4 使用示例

        让我们看看如何使用这个KNN分类器：

// 创建K=3的KNN分类器
KNNClassifier knn(3);

// 准备训练数据：特征和标签
std::vector<std::vector<double>> trainFeatures = {
    {1.0, 2.0},  // 样本1
    {1.5, 1.8},  // 样本2
    {5.0, 8.0},  // 样本3
    {8.0, 8.0}   // 样本4
};
std::vector<int> trainLabels = {0, 0, 1, 1};  // 对应类别

// 训练模型
knn.fit(trainFeatures, trainLabels);

// 预测新样本
std::vector<double> testSample = {1.2, 2.0};
int result = knn.predict(testSample);
cout << "预测类别: " << result << endl;

三、重要注意事项

3.1 K值选择策略

        K值的选择对模型性能有重大影响：

• K值太小：模型过于复杂，容易过拟合
• K值太大：模型过于简单，可能欠拟合

        建议使用交叉验证来选择最优K值。

3.2 距离度量的选择

        根据数据类型选择合适的距离度量：

• 欧氏距离：适用于连续特征
• 曼哈顿距离：适用于高维数据
• 余弦相似度：适用于文本数据

四、面试手撕

        考虑到面试手撕一般写核心代码体现主要思路就行，下面给出一个稍微没那么严谨的作为参考。

#include <vector>
#include <algorithm>
#include <map>

// 假设数据格式：特征为vector<double>，标签为int
int knn(const std::vector<std::pair<std::vector<double>, int>>& train, 
        const std::vector<double>& test, int k) {
    
    // 1. 计算距离并绑定标签
    std::vector<std::pair<double, int>> dists; // (距离, 标签)
    for (const auto& sample : train) {  // C++11：通过sample访问pair成员
        const std::vector<double>& feat = sample.first;  // 特征
        int label = sample.second;                       // 标签
        
        double d = 0;
        for (size_t i = 0; i < feat.size(); ++i) {
            d += (feat[i] - test[i]) * (feat[i] - test[i]); // 欧氏距离平方
        }
        dists.emplace_back(d, label);
    }
    
    // 2. 按距离升序排序，取前k个
    std::sort(dists.begin(), dists.end());
    std::vector<int> topKLabels;
    for (int i = 0; i < k; ++i) {
        topKLabels.push_back(dists[i].second);
    }
    
    // 3. 投票选最多标签
    std::map<int, int> count;
    for (int l : topKLabels) {
        count[l]++;
    }
    int bestLabel = -1;
    int maxCnt = 0;
    // C++11：通过迭代器访问map键值对（替代结构化绑定）
    for (const auto& entry : count) {  // entry是pair<const int, int>
        int l = entry.first;           // 标签
        int c = entry.second;          // 计数
        if (c > maxCnt) {
            maxCnt = c;
            bestLabel = l;
        }
    }
    
    return bestLabel;
}