C++单刷《机器学习实战》——k-近邻算法

    数学系研二渣硕一枚，最早接触机器学习还是在研究生一年级的模式识别课程上，发现大部分机器学习的书籍都是采用Python语言，当然Python在数据分析和矩阵计算方面确实会有很大的优势，对于缺乏编程基础又想要快速入门的同学，Python确实是首选。而从本系列开始，我将主要用C++将《机器学习实战》这本书刷一遍，旨在加深对算法理解的同时提高编程能力，也希望能够为想入坑机器学习，同时又热爱C++的人提供一些参考。

    每一篇的开始会有一个简单的算法描述，不会将原书的Python的代码照搬过来，想了解具体的可以参考《机器学习实战》原著，CSDN上也有电子版可供下载。

        现学现卖，希望我能够坚持得下去。

算法概述：kNN算法采用测量不同特征值之间的距离方法进行分类。kNN算法在能够工作之前需要先获取大量样本数据进行训练，每一个样本数据事先都存在标签。输入没有标签的数据后，将新数据的每个特征与样本集中的特征进行比较，然后提取样本集中最相似数据的分类标签。一般来说，我们只选择样本数据集中前k个最相似的数据标签，这就是kNN算法中k的出处，通常k是不大于20的整数。最后，我们选择k个最相似数据中出现次数最多的分类，作为新数据的分类。

现在我们尝试一个简单的范例，对二维坐标系中的点进行分类，定义一个4×2二维数组group代表坐标系中4个点的坐标，相应的标签labels为一个字符串数组，labels索引对应group中每一行的索引。

double group[4][2] = { { 1.0, 1.1 }, { 1.0, 1.0 }, { 0, 0 }, { 0, 0.1 } };

string labels[4] = { "A", "A", "B", "B" };

在C++中，将样本集定义为一个结构体似乎是更为合理的选择，不过原书中都是矩阵计算，为描述方便，还是采用类似矩阵的数组。

在获得样本集后，需要采用kNN对无标签的数据进行分类，具体步骤如下：

（1）计算样本集中的点与当前点的距离；

（2）按照距离递增次序排序；

（3）选取与当前点距离最小k个点；

（4）确定前k个点所在类别的出现频率；

（5）返回前k个点出现频率最高的类别作为当前点的分类。

     相应的代码清单如下：

string classify(double* inX,double* dataSet,string labels[],int k,int size,int dataSetSize)

//kNN分类算法

//inX：未分类的输入数据，dataSet：样本集，labels：标签，k:k值，size：数据的特征数量，dataSetSize:样本集数量 

{

double sum = 0;

double* diff_array = new double[size];

double* diff_all = new double[dataSetSize];

int* sorted_index = new int[dataSetSize];

string label;

map<string, int> label_count;

for (int i = 0; i < dataSetSize; i++)

//计算当前点与各样本点的欧式距离，并存入数组diff_array

{

sum = 0;

for (int j = 0; j < size; j++)

{

diff_array[j] = *(inX + j) - *(dataSet + i*size + j);

sum += (diff_array[j] * diff_array[j]);

}

diff_all[i] = sqrt(sum);

}

//排序，并返回排序后的原数组索引

sortIndex(diff_all, sorted_index, dataSetSize);

for (int i = 0; i < k; i++)

//计算前k个索引对应标签的出现次数，存入关联容器label_count

{

label = labels[sorted_index[i]];

++label_count[label];

}

//找出出现次数最多的标签，返回

auto map_it = label_count.begin();

label = map_it->first;

int max_count = map_it->second;

for (; map_it != label_count.end(); map_it++)

{

if (max_count < map_it->second)

{

max_count = map_it->second;

label = map_it->first;

}

}

delete diff_array;

delete diff_all;

delete sorted_index;

return label;

}

以上程序使用欧氏距离公式，计算两个点xA和xB之间的距离：

计算当前点与所有样本点的距离后，将距离由小到大进行排序，找到最近的k个点，然后返回k个点中出现频率最高的标签，这是基本思路。

在对距离进行排序并按原数组的索引返回的时候出现了一些小麻烦，在python中只要一个命令就能解决的问题，我不知道在C++中是否有同样方便好用的排序函数，不过以提高编程能力为目标，我本人倒不介意重复造车轮子的过程，排序代码如下：

void sortIndex(double* data, int* sorted_index2, int n)

//排序，并返回排序后的原数组索引

//data：原始数组，sorted_index2：排序后的原数组索引，n：数组大小

{

int index = 0;

int* sorted_index = new int[n];

for (int i = 0; i < n; i++)

{

index = 0;

for (int j = 0; j < n; j++)

{

if (data[i] > data[j])

index++;

else if (data[i] == data[j] && i > j)

index++;

}

sorted_index[i] = index;

}

for (int i = 0; i < n; i++)

{

for (int j = 0; j < n; j++)

{

if (i == sorted_index[j])

sorted_index2[i] = j;

}

}

delete sorted_index;

}

代码完成后，在main函数中进行调用测试：

int main()

{

string result;

string line;

double point[2];

cout << "Please input the coodinate of the pixel" << endl;

while (getline(cin, line))

{

istringstream record(line);

record >> point[0];

record >> point[1];

result = classify(point, &group[0][0], labels, 3, 2, 4);

cout << "The result is: " << result << endl;

cout << "Please input the coodinate of the pixel" << endl;

}

return 0;

}

运行结果：

使用kNN算法改进约会网站的配对效果

海伦在使用约会网站寻找约会对象的过程中，经过总结可以把交往过的人分为三种类型：

不喜欢的人

魅力一般的人

极具魅力的人

海伦希望我们的算法可以帮助她将匹配对象分到确切的分类中，为此她收集了一批约会对象的用户数据，每一个约会对象包含3个特征：每年的飞行里程数

玩游戏所耗时间百分比

每周消费的冰淇淋公升数

每一条样本数据都已经做好了标签，样本数据如下：

为了应用已经实现的kNN算法帮助海伦进行分类，我们先要读取文本数据并转化为程序所需要的类型。然后应用以上的classify函数进行分类。

数据文件里共有1000条数据，选取前100条数据为测试集对算法进行测试，发现当k=3时，错误率为5%

利用全体数据作为样本集对当个数据进行分类：

查看完整代码：

http://blog.csdn.net/u014080185/article/details/60467308