【小白啃书】统计学习方法（李航第二版）代码实现 （C++） 之 2.K近邻（1）

本文仅梳理总结自己在学习过程中的一些理解和思路，水平有限，理解粗鄙浅薄且不一定正确。文章所有观点均不保证绝对正确，请酌情参考。如果各位朋友发现任何错误请及时告诉我，大家一起讨论共同提高。
（不要问我为什么用C++写机器学习，问就是导师要求的）
希望我不鸽，咕咕

相关内容
0.导入数据
1.感知机

K近邻

写在前面（可以不看）

上一篇刚刚说过面向对象的思维不强的问题，写本次的程序的时候就切切实实地深受其害了。上课的时候老师曾经做过这样一个比方，一个对象就仿佛一个完整的人，有鼻子有眼睛有手，能说话能吃饭能跳舞。面向对象的方法要求我们在代码中，饭吃进嘴里，嘴连着喉管，把饭送进肠胃，而不是直接打开这个人的肠胃把食物塞进去，吃个饭都要拎着肠子到处乱跑。这次的代码让我切实地体会到了这种“拎着肠子满街乱跑”的感觉，无法拆分成独立的函数，更将某些部分无法移植到其他代码中使用，整个代码像一团乱码搅在一起竟然也实现了功能，就也还挺“鹅妹子嘤”的。
在本文中，我会把原本的代码贴上来，而在KNN（2）中则会放上修改过后的代码，以便让大家直观地感受一些两者之间的区别，也许会对大家更好地理解“面向对象”这一概念有些许帮助。

算法原理

网上总结太多了，书上也讲的详细，不多赘述。简而言之就是：

• 我离哪个（或k个）样本最近，我的标签就跟谁一样

当距离最近的k个样本标签不同的时候，通常选择少数服从多数的方法确定最后的标签。

训练

很显然，K近邻算法中不涉及训练，k为超参数，需要不断实验寻找效果最好的k值（所谓调参）

判断标签值

步骤如下

• 计算与每个样本的的距离
• 按距离排序
• 统计与待定样本点最近的K个样本的标签数量
• 最多的标签即视为待定样本点的标签

计算距离

计算距离使用的为欧氏距离，其计算公式为

d = sqrt( (x1-x2)²+(y1-y2)² )

for (auto iter : Sample_feature){for (int i = 0; i < feature_num; i++){dis += pow((it_test.first[i] - iter.second[i]), 2);}dis = sqrt(dis);distance.insert(map<int, double>::value_type(iter.first, dis));}

这段代码中用到的pow（平方）函数和sqrt（开方）函数需要包括头文件cmath

#include<cmath>

根据距离排序

map一般会默认按照键值进行排序，而我们这里需要的确是按照值的大小进行排序，以便筛选出距离代求的样本点最近的Ｋ个样本。直接对map的value进行相对来说复杂，一般常用的方法是将map放入vector中，利用vector的sort函数进行排序。
将map中的内容放入vector

for (map<int, double>::iterator it = distance.begin(); it != distance.end(); it++){vec_distance.push_back(pair<int, double>(it->first, it->second));}

sort函数的参数有三个，sort(begin, end, storFun)，分别为排序的起始位，终止位和排序方式。第三个参数缺省时默认从大到小排列，其他特殊的排序方式需要单独构建排序函数进行说明。我们这里的排序方式为按照vector的second项进行排序。

bool storFun(pair<int, double> a, pair<int, double> b)
{return a.second < b.second;
}

在此基础上，排序只需要一行代码就可以实现

		sort(vec_distance.begin(), vec_distance.end(), storFun); //从大到小排序

统计标签数量

遍历前ｋ项并统计其标签。特别的，map可以通过键值直接索引，当所查找的键值在map中不存在时还会自动增加此键值，这就给我们的统计带来了方便。我们不需要先得知总共出现了哪些标签值，只需要一行代码就可以完成标签的计数。

			map_label_freq[label]++;

当程序读取到标签值时，会将map中对应的计数结果（value）加一，若map中没有这个标签，则会添加这个标签为新的键值。

将标签赋给待分类样本

通过遍历计数结果map来找到出现次数最多的标签，完成样本的分类。

for (auto it_map : map_label_freq){if (it_map.second>max_freq){max_freq = it_map.second;label = it_map.first;}}

调用这个函数

可以看到，我并没有写输出结果的代码（因为想偷懒），所以在KNN函数的最后我打了一个断点以便查看运行结果。

因为前面讲过的原因，整个代码中除了读取数据只有KNN一个功能函数，各种数据纠缠在一起，极度混乱：＜

运行结果

最后的数字１为分类的正确率（虽然数据集是我自己写的在学习过程中这个数字并没有什么意义）

一些说明

为了方便大家看这个代码有多屎，我把这个代码完整复制在这里，如果对这一部分不感兴趣这篇文章阅读到这里就结束了。
结构更加清晰的程序我会在（２）中继续贴出来（如果我写得出来的话）

typedef string TLabel;
typedef double TFeature;
ifstream fin;
ofstream fout;bool storFun(pair<int, double> a, pair<int, double> b){……}int data_read(map<vector<TFeature>, TLabel> &Sample, string data_add, int &sample_num){……}void Sample_data_read(map<int, vector<TFeature>> &Sample_feature, map<int, TLabel>&Sample_label, map<vector<TFeature>, TLabel> &Sample, string data_add, int &sample_num){……}void KNN(int k)
{string data_add = ("F:\\learning ML\\KNN\\data.txt");string test_add = ("F:\\learning ML\\KNN\\test.txt");int feature_num = 0;int sample_num = 0;int test_sample_num = 0;double accuracy = 0;map<vector<TFeature>, TLabel> Sample;map<vector<TFeature>, TLabel> Test_Sample;map<int, vector<TFeature>> Sample_feature;map<int, TLabel>Sample_label;Sample_data_read(Sample_feature, Sample_label, Sample, data_add, sample_num);feature_num = data_read(Test_Sample, test_add, test_sample_num);//计算距离for (auto it_test : Test_Sample){double dis = 0;int index = 0;map<int, double> distance;vector<pair<int, double>> vec_distance;map<TLabel, int> map_label_freq;vector<pair<TLabel, int>>vec_label_freq;for (auto iter : Sample_feature){for (int i = 0; i < feature_num; i++){dis += pow((it_test.first[i] - iter.second[i]), 2);}dis = sqrt(dis);distance.insert(map<int, double>::value_type(iter.first, dis));}for (map<int, double>::iterator it = distance.begin(); it != distance.end(); it++){vec_distance.push_back(pair<int, double>(it->first, it->second));}sort(vec_distance.begin(), vec_distance.end(), storFun); //从大到小排序TLabel label;//统计分类for (int i = 0; i < k; i++){index = vec_distance[i].first;label = Sample_label[index];map_label_freq[label]++;}int max_freq = 0;for (auto it_map : map_label_freq){if (it_map.second>max_freq){max_freq = it_map.second;label = it_map.first;}}cout << "The test data belongs to the " << label << " label" << endl;if (label == it_test.second){accuracy++;}}accuracy = accuracy / test_sample_num;cout << accuracy << endl;system("pause");
}int main()
{int k;cout << "please input the k value : " << endl;cin >> k;KNN(k);}

源码和用到的数据集我打包放在KNN（１）

最后，错误及有待改进之处，希望各位大佬不吝赐教。