【机器学习实战之一】：C++实现K

本文不对KNN算法做过多的理论上的解释，主要是针对问题，进行算法的设计和代码的注解。

KNN算法：

优点：精度高、对异常值不敏感、无数据输入假定。

缺点：计算复杂度高、空间复杂度高。

适用数据范围：数值型和标称性。

工作原理：存在一个样本数据集合，也称作训练样本集，并且样本集中每个数据都存在标签，即我们知道样本集中每一个数据与所属分类的对应关系。输入没有标签的新数据后，将新数据的每个特征与样本集中数据对应的特征进行比较，然后算法提取样本集中特征最相似数据（最近邻）的分类标签。一般来说，我们只选择样本数据及中前ｋ个最相似的数据，这就是k-近邻算法中k的出处，通常k选择不大于20的整数。最后，选择k个最相似数据中出现次数最多的分类，作为新数据的分类。

K-近邻算法的一般流程：

（1）收集数据：可以使用任何方法

（2）准备数据：距离计算所需要的数值，最好是结构化的数据格式

（3）分析数据：可以使用任何方法

（4）训练算法：此步骤不适用k-邻近算法

（5）测试算法：计算错误率

（6）使用算法：首先需要输入样本数据和结构化的输出结果，然后运行k-近邻算法判定输入数据分别属于哪个分类，最后应用对计算出的分类执行后续的处理。

问题一：现在我们假设一个场景，就是要为坐标上的点进行分类，如下图所示：

上图一共12个左边点，每个坐标点都有相应的坐标(x,y)以及它所属的类别A/B，那么现在需要做的就是给定一个点坐标(x1,y1)，判断它属于的类别A或者B。

所有的坐标点在data.txt文件中：

step2：用get_distance()来计算测试数据testData和每一个训练数据dataSet[index]的距离，用map_index_dis来保存键值对,其中index代表第几个训练数据，distance代表第index个训练数据和测试数据的距离。

step3：将map_index_dis按照value值（即distance值）从小到大的顺序排序，然后取前k个最小的value值，用map_label_freq来记录每一个类标签出现的频率。

step4：遍历map_label_freq中的value值，返回value最大的那个key值，就是测试数据属于的类。

看一下代码KNN_0.cc：