[C++与机器学习] k-近邻算法（K–nearest neighbors）

C++ with Machine Learning -K–nearest neighbors

我本想写C++与人工智能，但是转念一想，人工智能范围太大了，我根本介绍不完也没能力介绍完，所以还是取了他的子集。我想这应该是一个有关机器学习的系列文章，我会不定期更新文章，希望喜欢机器学习的朋友不宁赐教。

本系列特别之处是与一些实例相结合来系统的讲解有关机器学习的各种算法，由于能力和时间有限，不会向诸如Simon Haykin<<NEURAL NETWORKS>>等大块头详细的讲解某一个领域的所有算法与概念，我会有选择的讲解一些算法作为引导，如果要继续深入则推荐读者系统阅读相关书籍。

我相信认真看的每个人都能明白K近邻算法。

K–nearest neighbors,简称 KNN/kNN,用来处理分类和回归，它是最简单的Machine Learning Algorithm，所以以它为开端。这里考虑一个实例，有两个小组AB，A组为实践组，B组为理论组，A组的实践分平均为90，理论为30，B组实践分为20分，理论分为70分，现在有一个同学实践60分，理论60分，她到底属于哪个组？

就像上面的图片一样，不过我们可以使用欧氏距离[附录]计算出未知点与其他四个点的距离（相似度/相似值），然后把计算出来的值从小到大排序，选择K个值（这就是k的由来），这K个值都是选择最小的。

比如最后用欧氏距离计算出来的距离是

与1点的距离：5,

与2点的距离：5.3

与3点的距离：2.2

与4点的距离：7.12

我们就需要对上面排序，排成这样：

与3点的距离：2.2

与1点的距离：5,

与2点的距离：5.3

与4点的距离：7.12

这里假设K=3，就意味这我们需要选择前面三个数据，然后判断前面三个数据中A和B，3点是B类，1点是A类，2点是B类，这里显然B类多一些，所以未知数就是B类，到这里算法是想就解释了，很简单把，因为它是最简单的ML算法，下面就是C++的实现了

//A bad version about k-nearest neighbour algorithm,just a teaching sample.
#include <iostream>
#include <algorithm>
#include <map>
#include <math.h>

const int k=3;

std::ostream & operator<<(std::ostream& out, const std::pair<double,char>& p) {
  return out << p.first << "\t" << p.second;
}
//训练样本数据集
class simple_data{
public:
    simple_data(double x,double y,char classtype):
        type(classtype),datx(x),daty(y)
    {}
    inline double get_distance(double x0,double y0){
        return sqrt((pow(datx-x0,2)+pow(daty-y0,2)));//欧氏距离
    }
    char type;
private:
    double datx;
    double daty;
};


int main(){
    //构造<span style="font-family: Arial, Helvetica, sans-serif;">训练样本数据集，这样正常情况下应该从文本读入。为了方便就直接构造了</span>
    simple_data sd1(1.0,2.0,'A');
    simple_data sd2(2.0,3.0,'A');
    simple_data sd3(12.0,13.0,'B');
    simple_data sd4(8.0,9.0,'B');

    //读入需要分类的新数据，并计算它和所有点的距离
    double newdata[2]={1.0,1.0};
    std::map<double,char> mp;
    mp.insert(std::pair<double,char>(sd1.get_distance(newdata[0],newdata[1]),sd1.type));
    mp.insert(std::pair<double,char>(sd2.get_distance(newdata[0],newdata[1]),sd2.type));
    mp.insert(std::pair<double,char>(sd3.get_distance(newdata[0],newdata[1]),sd3.type));
    mp.insert(std::pair<double,char>(sd4.get_distance(newdata[0],newdata[1]),sd4.type));
    //得到相似度，并进行排序，最后输出
    unsigned int acout=0,bcout=0,i=0;
    std::cout<<"相似度："<<'\t'<<"类型:\n";
    for(std::map<double,char>::iterator iter = mp.begin();
         iter != mp.end();++iter)
    {
        i++;
        std::cout << *iter <<std::endl;
        if(i<k){
            if(mp[i]='A'){
                acout++;
            }else{
                bcout++;
            }
        }
    }
    if(acout>bcout)
        std::cout<<"未知类型数属于：A";
    else
        std::cout<<"未知类型数属于：B"

}

本系列的源码我会修改它们写成一个可供调用的API，方便对于机器学习有兴趣而对编程不太熟悉的朋友直接调用从而编写程序。

补充

如果要计算2个以上特征值需要注意的除了改变距离计算方法之外还要注意K值尽量不要太大，实际上这一rule也存在于两个特征值，K值的大小和和数据的精确度是影响计算的两个方面，又尤其是数据精确度，建议尽量三位小数内进行计算，因为最后我们的目的是分类不是精确计算。

附：

1)欧氏距离

最常见的两点之间或多点之间的距离表示法，又称之为欧几里得度量，它定义于欧几里得空间中，如点 x = (x1,...,xn) 和 y = (y1,...,yn) 之间的距离为：

二维平面上两点a(x1,y1)与b(x2,y2)间的欧氏距离 ：

本文由于只有两个特征值（就是XY）所以使用的，到底如何选择请根据实际情况而定，假如你需要分类的特征值除了理论分数实践分数之外还包括思想品德分数英语分数，显然就必须使用第一个公式.

2)曼哈顿距离（from http://blog.csdn.net/v_july_v/article/details/8203674/）

比较常见的一个距离计算，如A星寻路算法就使用的曼哈顿距离计算。

(1)二维平面两点a(x1,y1)与b(x2,y2)间的曼哈顿距离 

(2)两个n维向量a(x11,x12,…,x1n)与 b(x21,x22,…,x2n)间的曼哈顿距离 

原文：http://blog.csdn.net/racaljk/article/details/37882177