这道题要求实现一个 K 近邻分类器的判别模块。我们需要通过计算待分类样本与训练数据集中的样本之间的距离，找出 K 个距离最近的样本，按照这些样本的类别进行投票，最后预测出该样本的类别。

理论解析

K 近邻算法（KNN） 是一种非常简单的机器学习算法，通常用于分类问题。它的基本原理是：

  1. 距离度量：计算待分类样本与所有训练样本的距离。通常使用欧氏距离、曼哈顿距离等度量方式。这里题目明确要求使用“平方欧氏距离”，即计算欧氏距离的平方：

    其中， 是待分类的样本， 是训练样本， 是特征维度。

  2. 挑选 K 个最近的样本：找到与待分类样本距离最近的 K 个训练样本。对于每个训练样本，都计算距离，选择 K 个最小的。

  3. 投票决策：对这 K 个近邻的类别标签进行统计，选择出现次数最多的类别作为预测结果。如果有并列，则选择距离最近的那个类别。

  4. 输出预测标签与出现次数：最终输出预测的标签和该标签在前 K 个近邻中出现的次数。

题目解析

输入中包含了以下几个部分：

  1. k m n s：

    • k：最近邻的数量（最大 20），即我们要从训练数据中选择 K 个最接近待分类样本的样本。
    • m：训练样本的数量（最大 200）。
    • n：每个样本的特征维度（最大 5）。
    • s：类别数量（最大 5）。

  2. 待分类样本的特征：在第 2 行，给定了一个待分类样本的特征。

  3. 训练样本的特征与标签：从第 3 行开始到第 m+2 行，每行包含 n 个特征和一个类别标签（标签是浮动的）。

输出要求

  • 输出预测的标签和该标签在前 K 个近邻中的出现次数。

具体步骤

  1. 读取输入数据：首先读取待分类样本的特征，再读取训练样本的特征和标签。

  2. 计算待分类样本与每个训练样本的距离：使用“平方欧氏距离”来度量。

  3. 按距离排序：对训练样本按距离从小到大排序，选择前 K 个最小距离的样本。

  4. 统计标签的出现次数：统计 K 个最近邻中各个标签的出现次数，选择出现最多的标签。如果有并列，则选择距离最近的标签。

  5. 输出结果：输出预测的标签和其在前 K 个近邻中出现的次数。

代码实现示例

#include <bits/stdc++.h>
using namespace std;

// 结构体存储距离和索引
struct PairD {
    double d2;  // 平方欧氏距离
    int idx;    // 样本索引
    bool operator<(const PairD& o) const { return d2 < o.d2; }  // 按照距离排序
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // 读到 EOF，按空白分隔
    vector<string> tok;
    string s;
    while (cin >> s) tok.push_back(s);
    if (tok.empty()) return 0;

    size_t p = 0;

    int k = stoi(tok[p++]);  // 最近邻个数
    int m = stoi(tok[p++]);  // 样本数
    int n = stoi(tok[p++]);  // 特征维度
    int sc = stoi(tok[p++]); // 类别数，未直接使用

    // 读待分类样本
    vector<double> q(n);
    for (int i = 0; i < n; ++i) q[i] = stod(tok[p++]);

    // 读训练样本
    vector<vector<double>> X(m, vector<double>(n));
    vector<int> y(m);
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) X[i][j] = stod(tok[p++]);
        y[i] = (int)llround(stod(tok[p++]));  // 标签是浮点型，转换为整数
    }

    // 计算每个训练样本与待分类样本的平方欧氏距离
    vector<PairD> ds; ds.reserve(m);
    for (int i = 0; i < m; ++i) {
        double d2 = 0.0;
        for (int j = 0; j < n; ++j) {
            double diff = q[j] - X[i][j];
            d2 += diff * diff;
        }
        ds.push_back({d2, i});
    }
    
    // 排序，距离最近的样本排前
    sort(ds.begin(), ds.end());

    // 统计前 K 个近邻的标签频率
    int kk = min(k, m);
    unordered_map<int,int> freq;
    freq.reserve(kk * 2 + 1);
    for (int i = 0; i < kk; ++i) {
        int lab = y[ds[i].idx];
        ++freq[lab];
    }

    // 找出频率最高的标签
    int maxFreq = 0;
    for (auto &e : freq) maxFreq = max(maxFreq, e.second);

    // 记录频率相同的标签
    unordered_set<int> tie;
    for (auto &e : freq) if (e.second == maxFreq) tie.insert(e.first);

    // 如果有并列，选择距离最近的标签
    int ansLab = -1;
    for (int i = 0; i < kk; ++i) {
        int lab = y[ds[i].idx];
        if (tie.count(lab)) { ansLab = lab; break; }
    }

    cout << ansLab << " " << freq[ansLab] << "\n";
    return 0;
}

代码详解

  1. 输入数据的处理：

    • 通过 map(int, input().split()) 读取 k, m, n, s 以及待分类样本的特征。
    • 循环读取训练样本的特征和标签，将它们存储到 train_samples 中。

  2. 计算距离并排序：

    • 遍历每个训练样本，计算它与待分类样本之间的平方欧氏距离，将结果存储到 ds 中。
    • 然后按照距离对 ds 进行排序，选择前 K 个最近邻。

  3. 标签统计与投票：

    • 使用 freq 统计前 K 个近邻中各个标签的出现次数。
    • 找到出现次数最多的标签。如果有多个标签出现的次数相同，就按照距离排序，选择距离最近的标签。

  4. 输出结果：

    • 输出预测标签以及该标签在前 K 个近邻中的出现次数。

示例解释

示例 1

输入：

3 6 2 2
0.00 0.00
0.20 0.10 0.0
0.30 0.00 0.0
0.00 0.40 1.0
0.60 0.60 1.0
0.05 0.02 0.0
0.90 0.90 1.0

步骤：

  • 计算待分类样本 (0.00, 0.00) 与训练样本之间的距离。
  • 按照距离排序，选择最近的 3 个邻居，分别为 (0.05, 0.02, 0), (0.20, 0.10, 0), (0.30, 0.00, 0)。
  • 标签为 0 出现 3 次。

输出：

0 3

示例 2

输入：

4 6 2 3
1.00 1.00
0.95 0.95 2.0
1.10 1.00 2.0
0.90 1.10 1.0
0.80 0.90 1.0
2.00 2.00 3.0
1.30 1.40 1.0

步骤：

  • 计算待分类样本 (1.00, 1.00) 与训练样本之间的距离。
  • 按照距离排序，选择最近的 4 个邻居，分别为 (0.95, 0.95, 2), (1.10, 1.00, 2), (0.90, 1.10, 1), (0.80, 0.90, 1)。
  • 标签 1 和 2 各自出现 2 次。
  • 因为标签 2 出现的最近邻是 (0.95, 0.95, 2)，它距离最近，最终预测标签为 2。

输出：

2 2

总结

这道题的关键在于实现 K 近邻算法的基本步骤：计算距离、选择最近邻、进行投票，并处理并列情况。理解每一步的操作和如何实现它们对于解决问题至关重要。

难点

  • 对题意的理解，注意q的含义