K近邻算法(KNN)的C++实现.docx

本文不对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文件中：0.0 1.1 A1.0 1.0 A2.0 1.0 B0.5 0.5 A2.5 0.5 B0.0 0.0 A1.0 0.0 A 2.0 0.0 B3.0 0.0 B0.0 -1.0 A1.0 -1.0 A2.0 -1.0 Bstep1：通过类的默认构造函数去初始化训练数据集dataSet和测试数据testData。step2：用get_distance()来计算测试数据testData和每一个训练数据dataSetindex的距离，用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：#include#include#include#include#include#include#include#includeusing namespace std;typedef char tLabel;typedef double tData;typedef pair PAIR;const int colLen = 2;const int rowLen = 12;ifstream fin;ofstream fout;class KNNprivate:tData dataSetrowLencolLen;tLabel labelsrowLen;tData testDatacolLen;int k;map map_index_dis;map map_label_freq;double get_distance(tData *d1,tData *d2);public:KNN(int k);void get_all_distance();void get_max_freq_label();struct CmpByValuebool operator() (const PAIR& lhs,const PAIR& rhs)return lhs.second k = k;fin.open(data.txt);if(!fin)coutcan not open the file data.txtendl;exit(1); /* input the dataSet */ for(int i=0;irowLen;i+)for(int j=0;jdataSetij;finlabelsi;coutplease input the test data :endl;/* inuput the test data */for(int i=0;itestDatai;/* * calculate the distance between test data and dataSeti */double KNN: get_distance(tData *d1,tData *d2)double sum = 0;for(int i=0;icolLen;i+)sum += pow( (d1i-d2i) , 2 );/coutthe sum is = sumendl;return sqrt(sum);/* * calculate all the distance between test data and each training data */void KNN: get_all_distance()double distance;int i;for(i=0;irowLen;i+)distance = get_distance(dataSeti,testData);/ = map_index_disi = distance;/traverse the map to print the index and distancemap:const_iterator it = map_index_dis.begin();while(it!=map_index_dis.end()coutindex = first distance = secondendl;it+;/* * check which label the test data belongs to to classify the test data */void KNN: get_max_freq_label()/transform the map_index_dis to vec_index_disvector vec_index_dis( map_index_dis.begin(),map_index_dis.end() );/sort the vec_index_dis by distance from low to high to get the nearest datasort(vec_index_dis.begin(),vec_index_dis.end(),CmpByValue();for(int i=0;ik;i+)coutthe index = vec_index_disi.first the distance = vec_index_disi.second the label = labelsvec_index_disi.first the coordinate ( dataSet vec_index_disi.first 0,dataSet vec_index_disi.first 1 )endl;/calculate the count of each labelmap_label_freq labels vec_index_disi.first +;map:const_iterator map_it = map_label_freq.begin();tLabel label;int max_freq = 0;/find the most frequent labelwhile( map_it != map_label_freq.end() )if( map_it-second max_freq )max_freq = map_it-second;label = map_it-first;map_it+;coutThe test data belongs to the label labelendl;int main()int k ;coutplease input the k value : k;KNN knn(k);knn.get_all_distance();knn.get_max_freq_label(); system(pause); return 0;我们来测试一下这个分类器(k=5)：testData(5.0,5.0):testData(-5.0,-5.0):testData(1.6,0.5):分类结果的正确性可以通过坐标系来判断，可以看出结果都是正确的。问题二：使用k-近邻算法改进约会网站的匹配效果情景如下：我的朋友海伦一直使用在线约会网站寻找合适自己的约会对象。尽管约会网站会推荐不同的人选，但她没有从中找到喜欢的人。经过一番总结，她发现曾交往过三种类型的人：不喜欢的人魅力一般的人极具魅力的人尽管发现了上述规律，但海伦依然无法将约会网站推荐的匹配对象归入恰当的分类。她觉得可以在周一到周五约会哪些魅力一般的人，而周末则更喜欢与那些极具魅力的人为伴。海伦希望我们的分类软件可以更好的帮助她将匹配对象划分到确切的分类中。此外海伦还收集了一些约会网站未曾记录的数据信息，她认为这些数据更有助于匹配对象的归类。海伦已经收集数据一段时间。她把这些数据存放在文本文件datingTestSet.txt（文件链接：/QUL6SxtiJFPfN）中，每个样本占据一行，总共有1000行。海伦的样本主要包含3中特征：每年获得的飞行常客里程数玩视频游戏所耗时间的百分比每周消费的冰淇淋公升数数据预处理：归一化数据我们可以看到，每年获取的飞行常客里程数对于计算结果的影响将远大于其他两个特征。而产生这种现象的唯一原因，仅仅是因为飞行常客书远大于其他特征值。但是这三种特征是同等重要的，因此作为三个等权重的特征之一，飞行常客数不应该如此严重地影响到计算结果。处理这种不同取值范围的特征值时，我们通常采用的方法是数值归一化，如将取值范围处理为0到1或者-1到1之间。公式为：newValue = (oldValue - min) / (max - min)其中min和max分别是数据集中的最小特征值和最大特征值。我们增加一个auto_norm_data函数来归一化数据。同事还要设计一个get_error_rate来计算分类的错误率，选总体数据的10%作为测试数据，90%作为训练数据，当然也可以自己设定百分比。其他的算法设计都与问题一类似。代码如下KNN_2.cc（k=7）：/* add the get_error_rate function */#include#include#include#include#include#include#include#includeusing namespace std;typedef string tLabel;typedef double tData;typedef pair PAIR;const int MaxColLen = 10;const int MaxRowLen = 10000;ifstream fin;ofstream fout;class KNNprivate:tData dataSetMaxRowLenMaxColLen;tLabel labelsMaxRowLen;tData testDataMaxColLen;int rowLen;int colLen;int k;int test_data_num;map map_index_dis;map map_label_freq;double get_distance(tData *d1,tData *d2);public:KNN(int k , int rowLen , int colLen , char *filename);void get_all_distance();tLabel get_max_freq_label();void auto_norm_data();void get_error_rate();struct CmpByValuebool operator() (const PAIR& lhs,const PAIR& rhs)return lhs.second rowLen = row;this-colLen = col;this-k = k;test_data_num = 0;fin.open(filename);fout.open(result.txt);if( !fin | !fout )coutcan not open the fileendl;exit(0);for(int i=0;irowLen;i+)for(int j=0;jdataSetij;foutdataSetijlabelsi;foutlabelsiendl;void KNN: get_error_rate()int i,j,count = 0;tLabel label;coutplease input the number of test data : test_data_num;for(i=0;itest_data_num;i+)for(j=0;jcolLen;j+)testDataj = dataSetij;get_all_distance();label = get_max_freq_label();if( label!=labelsi )count+;map_index_dis.clear();map_label_freq.clear();coutthe error rate is = (double)count/(double)test_data_numendl;double KNN: get_distance(tData *d1,tData *d2)double sum = 0;for(int i=0;icolLen;i+)sum += pow( (d1i-d2i) , 2 );/coutthe sum is = sumendl;return sqrt(sum);void KNN: get_all_distance()double distance;int i;for(i=test_data_num;irowLen;i+)distance = get_distance(dataSeti,testData);map_index_disi = distance;/map:const_iterator it = map_index_dis.begin();/while(it!=map_index_dis.end()/coutindex = first distance = secondendl;/it+;/tLabel KNN: get_max_freq_label()vector vec_index_dis( map_index_dis.begin(),map_index_dis.end() );sort(vec_index_dis.begin(),vec_index_dis.end(),CmpByValue();for(int i=0;ik;i+)coutthe index = vec_index_disi.first the distance = vec_index_disi.second the label = labels vec_index_disi.first the coordinate ( ;int j;for(j=0;jcolLen-1;j+)coutdataSet vec_index_disi.first j,;coutdataSet vec_index_disi.first j )endl;map_label_freq labels vec_index_disi.first +;map:const_iterator map_it = map_label_freq.begin();tLabel label;int max_freq = 0;while( map_it != map_label_freq.end() )if( map_it-second max_freq )max_freq = map_it-second;label = map_it-first;map_it+;coutThe test data belongs to the label labelendl;return label;void KNN:auto_norm_data()tData maxacolLen ;tData minacolLen ;tData rangecolLen ;int i,j;for(i=0;icolLen;i+)maxai = max(dataSet0i,dataSet1i);minai = min(dataSet0i,dataSet1i);for(i=2;irowLen;i+)for(j=0;jmaxaj )maxaj = dataSetij;else if( dataSetijminaj )minaj = dataSetij;for(i=0;icolLen;i+)rangei = maxai - minai ; /normalize the test data settestDatai = ( testDatai - minai )/rangei ;/normalize the training data setfor(i=0;irowLen;i+)for(j=0;jcolLen;j+)dataSetij = ( dataSetij - minaj )/rangej;int main(int argc , char* argv)int k,row,col;char *filename;if( argc!=5 )coutThe input should be like this : ./a.out k row col filenameendl;exit(1);k = atoi(argv1);row = atoi(argv2);col = atoi(argv3);filename = argv4;KNN knn(k,row,col,filename);knn.auto_norm_data();knn.get_error_rate();/knn.get_all_distance();/knn.get_max_freq_label();return 0;makefile:target:g+ KNN_2.cc ./a.out 7 1000 3 datingTestSet.txt结果：可以看到：在测试数据为10%和训练数据90%的比例下，可以看到错误率为4%，相对来讲还是很准确的。构建完整可用系统：已经通过使用数据对分类器进行了测试，现在可以使用分类器为海伦来对人进行分类。代码KNN_1.cc（k=7）：/* add the auto_norm_data */#include#include#include#include#include#include#include#includeusing namespace std;typedef string tLabel;typedef double tData;typedef pair PAIR;const int MaxColLen = 10;const int MaxRowLen = 10000;ifstream fin;ofstream fout;class KNNprivate:tData dataSetMaxRowLenMaxColLen;tLabel labelsMaxRowLen;tData testDataMaxColLen;int rowLen;int colLen;int k;map map_index_dis;map map_label_freq;double get_distance(tData *d1,tData *d2);public:KNN(int k , int rowLen , int colLen , char *filename);void get_all_distance();tLabel get_max_freq_label();void auto_norm_data();struct CmpByValuebool operator() (const PAIR& lhs,const PAIR& rhs)return lhs.second rowLen = row;this-colLen = col;this-k = k;fin.open(filename);fout.open(result.txt);if( !fin | !fout )coutcan not open the fileendl;exit(0);/input the training data setfor(int i=0;irowLen;i+)for(int j=0;jdataSetij;foutdataSetijlabelsi;foutlabelsiendl;/input the test datacouttestData0;couttestData1;couttestData2;double KNN: get_distance(tData *d1,tData *d2)double sum = 0;for(int i=0;icolLen;i+)sum += pow( (d1i-d2i) , 2 );return sqrt(sum);void KNN: get_all_distance()double distance;int i;for(i=0;irowLen;i+)distance = get_distance(dataSeti,testData);map_index_disi = distance;/map:const_iterator it = map_index_dis.begin();/while(it!=map_index_dis.end()/coutindex = first distance = secondendl;/it+;/tLabel KNN: get_max_freq_label()vector vec_index_dis( map_index_dis.begin(),map_index_dis.end() );sort(vec_index_dis.begin(),vec_index_dis.end(),CmpByValue();for(int i=0;ik;i+) /* coutthe index = vec_index_disi.first the distance = vec_index_disi.second the label = labels vec_index_disi.first the coordinate ( ;int j;for(j=0;jcolLen-1;j+)coutdataSet vec_index_disi.first j,;coutdataSet vec_index_disi.first j )endl; */map_label_freq labels vec_index_disi.first +;map:const_iterator map_it = map_label_freq.begin();tLabel label;int max_freq = 0;/*traverse the map_label_freq to get the most frequent label*/while( map_it != map_label_freq.end() )if( map_it-second max_freq )max_freq = map_it-second;label = map_it-f