题目内容

KNN 算法的核心思想是，如果一个样本在特征空间中的 KK 个最相邻的样本中的大多数属于某一个类别，则该样本也属于这个类别，并具有这个类别上样本的特性。请按照下面的步理，实现 KNNKNN 算法。

KNNKNN 算法说明：

计算待分类点到其他样本点的距离；

通过距离进行排序，选择距离最小的 KK 个点；提取这 KK 个临近点的类别，根据少数服从多数的原则，将占比最多的那个标签赋值给待分类样本点的 labellabel 。

本题说明：

1、给定数据集中，默认每一类标签都存在数据，不存在某类型数量为 00 的场景；

2、为消除不同特征权重问题，给出数据均已做好归一化处理，并保留两位小数；

3、出现并列第一的情形时，取并列第一的样本中，最近邻居的标签返回；

4、距离函数定义为: dx,y=∑i=1n(xi−yi)2dx,y​=∑i=1n​(xi​−yi​)2​。

输入描述

第 11 行：kk mm nn ss ：kk 代表每次计算时选取的最近邻居个数(不大于 2020 )，mm 代表样本数量(不大于 200200 )，nn 代表样本维度(不包括标签，不大于 55 )，ss 代表类别个数(不于 55 )；

第 22 行：待分类样本

第 33 行~第 m+2m+2 行：mm 个样本，每一行 n+1n+1 列，最后一列为类别标签 labellabel

输出描述

输出待分类样本的类别标签及距离最小的 KK 个点中的该标签样本数量

样例1

输入

3 10 2 3
0.81 0.64
0.19 0.2 1.0
0.18 0.14 0.0
0.76 0.58 1.0
0.4 0.16 1.0
0.98 0.85 0.0
0.42 0.97 1.0
0.75 0.26 1.0
0.24 0.06 1.0
0.97 0.8 0.0
0.21 0.1 2.0

Copy

输出

0 2

Copy

说明

第 11 行输入说明输入了 m=10m=10 个样本，每个样本有 n=2n=2 个维度的数据(去除最后一列标签)，共有 s=3s=3 种类别

第 22 行输入待分类样本的 nn 维数据

从第 33 行到第 1212 行的前两列数据为输入的 m=10m=10 个样本，每个样本有 n=2n=2 个维度的数据+最后一列的标签数据

待分类样本 [0.81[0.81 0.64]0.64] 最近的前 k=3k=3 个邻居分别为：[0.76[0.76 0.58],[0.980.58],[0.98 0.85],[0.970.85],[0.97 0.8]0.8] ，分别有 22 个 00 号标签和 11 个 11 号标签 00 号标签占多，返回 00 以及标签 00 的样本数量 22

样例2

输入

6 10 2 4
0.78 0.63
0.57 0.07 1.0
0.5 0.13 1.0
0.83 0.07 3.0
0.27 0.87 3.0
0.81 0.44 2.0
0.21 0.73 3.0
0.45 0.91 1.0
0.12 0.22 2.0
0.25 0.48 0.0
0.54 0.87 1.0

Copy

输出

1 2

Copy

说明

本样例的距离最小的 66 个样本中，标签 11 和标签 33 出现次数都是 22 次，并列第一；虽然 [0.8[0.8 0.44]0.44] 距离样本最近，但其标签 22 不是出现最多的，排除在下一轮统计样本中此时需要从标签 11 和标签 33 中的样本中，选取距离最近的 [0.54[0.54 0.87]0.87] 的标签 11 作为返回值，并同时返回标签 11 的样本数量 22 。

我第一次做的时候感觉没那么难，第一次代码是这样写的

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <unordered_map>
using namespace std;
struct Sample
{

    //n维度的特征值
    vector<double>features;
    //标签类别
    int label;
};
struct Distance
{
    double distance;
    int label;
};
int main()
{
    //输入k（邻居） m（样本数量） n（样本维度） s（样本类别）
    int k,m,n,s;
    cin>>k>>m>>n>>s;
    //输入待分类样本
    vector<double> test_sample(n);
    for (int i=0;i<n;i++)
    {
        cin>>test_sample[i];
    }
    //输入已知样本
    vector<Sample>m_sample(m);
    for (int i=0;i<m;i++)
    {
        m_sample[i].features.resize(n);
        for (int j=0;j<n;j++)
        {
            cin>>m_sample[i].features[j];
        }
        cin>>m_sample[i].label;
    }
    //找k个邻居
        //计算距离并排序
    vector<Distance>all_distances;//(m);
    double distance=0;
    for (int i=0;i<m;i++)
    {
        distance=0;
        for (int j=0;j<n;j++)
        {
            // distance=(test_sample[j]-m_sample[i].features[j])*(test_sample[j]-m_sample[i].features[j]);
            // distance+=distance;
            double diff = test_sample[j] - m_sample[i].features[j];
            distance += diff * diff; // 累加平方差
        }
    all_distances.push_back({distance,m_sample[i].label});
    }
    sort(all_distances.begin(),all_distances.end(),[](Distance& a,Distance& b){return a.distance<b.distance;});
    //列出前k个的距离和类别
    vector<Distance>k_neighbor(all_distances.begin(),all_distances.begin()+k);//左闭右开
    map<int,int>label_cnt;//左边是label，右边是该label的计数
    //记录每个label的数量
    for (auto d :k_neighbor)
    {
        label_cnt[d.label]++;
    }
    //最多的label数量
    int max_cnt=0;
    for (auto m:label_cnt)
    {
        if (m.second>max_cnt)
        {
            max_cnt=m.second;
        }
    }
    //最多的label
    vector<double>maxcnt_label;
    for (auto m:label_cnt)
    {
        if (m.second==max_cnt)
        {
            maxcnt_label.push_back(m.first);
        }
    }
    //如果只有一个最大的label
    if (maxcnt_label.size()==1)
    {
        cout<<maxcnt_label[0]<<" "<<max_cnt<<endl;
    }
    else
    {
        for (auto k:k_neighbor)
        {
            if (find(maxcnt_label.begin(),maxcnt_label.end(),k.label)!=maxcnt_label.end())
            {
                cout<<k.label<<" "<<max_cnt<<endl;
                break;
            }
        }
    }
    return 0;
}

当然编写期间还有好多坑，比如

#include <algorithm>之后

struct Sample这个结构体的名字不能定义成sample，否则符号不明确有冲突

还有就是本人菜鸡，计算距离的时候

 distance=(test_sample[j]-m_sample[i].features[j])*(test_sample[j]-m_sample[i].features[j]);
 distance+=distance;

这样写导致每次循环distance都被重写加了等于没加

还有

vector<Distance>all_distances[m];

这样初始化导致后面push_back是在这m个元素后面push

但是所有小错误改完之后我发现输入一些数据还是有的过，有的过不了

比如题干中第一个例子，我想不明白，反复检查逻辑也没发现问题。后来我debug时发现计算距离时，前几个距离总是对的，后几个错的离谱，实在想不出招的情况下我灵机一动把label全部换成了double类型，因为输入是1.0，2.0这样的，改完一测全过了。

当使用cin >> m_sample[i].label读取1.0这样的浮点数时，

cin会读取到1，然后遇到小数点.就停止读取

所以1.0被截断为1，0.0被截断为0，

我原本以为没一点问题，但是事实证明它真的会影响后续读取