k最近邻算法实验报告.pdf

《k最近邻算法实验报告.pdf》由会员分享，可在线阅读，更多相关《k最近邻算法实验报告.pdf（9页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、以家为家，以乡为乡，以国为国，以天下为天下。管子牧民天行健，君子以自强不息。地势坤，君子以厚德载物。易经 题 目 k-最近邻算法实现 学生姓名 学生学号 专业班级 指导教师 2015-1-2 志不强者智不达，言不信者行不果。墨翟古之立大事者，不惟有超世之才，亦必有坚忍不拔之志。苏轼 实验二 k-最近邻算法实现 一、实验目的 1.加强对 k-最近邻算法的理解；2.锻炼分析问题、解决问题并动手实践的能力。二、实验要求 使用一种你熟悉的程序设计语言，如 C+或 Java，给定最近邻数 k 和描述每个元组的属性数 n，实现 k-最近邻分类算法，至少在两种不同的数据集上比较算法的性能。三、实验环境 Wi

2、n7 旗舰版+Visual Studio 2010 语言：C+四、算法描述 KNN(k Nearest Neighbors)算法又叫 k 最临近方法。假设每一个类包含多个样本数据，而且每个数据都有一个唯一的类标记表示这些样本是属于哪一个分类，KNN 就是计算每个样本数据到待分类数据的距离。如果一个样本在特征空间中的 k 个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。KNN 方法虽然从原理上也依赖于极限定理，但在类别决策时，只与极少量的相邻样本有关。因此，采用这种方法可以较好地

3、避免样本的不平衡问题。另外，由于 KNN 方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待人人好公，则天下太平；人人营私，则天下大乱。刘鹗良辰美景奈何天，便赏心乐事谁家院。则为你如花美眷，似水流年。汤显祖 分样本集来说，KNN 方法较其他方法更为适合。该方法的不足之处是计算量较大，因为对每一个待分类的文本都要计算它到全体已知样本的距离，才能求得它的 K个最近邻点。目前常用的解决方法是事先对已知样本点进行剪辑，事先去除对分类作用不大的样本。该算法比较适用于样本容量比较大的类域的自动分类，而那些样本容量较小的类域采用这种算法比较容易产生误分。

4、1、算法思路 K-最临近分类方法存放所有的训练样本，在接受待分类的新样本之前不需构造模型，并且直到新的（未标记的）样本需要分类时才建立分类。K-最临近分类基于类比学习，其训练样本由 N 维数值属性描述，每个样本代表 N 维空间的一个点。这样，所有训练样本都存放在 N 维模式空间中。给定一个未知样本，k-最临近分类法搜索模式空间，找出最接近未知样本的 K 个训练样本。这 K 个训练样本是未知样本的 K 个“近邻”。“临近性”又称为相异度（Dissimilarity），由欧几里德距离定义，其中两个点 X（x1,x2,xn）和 Y（y1,y2,yn）的欧几里德距离是：2222211)()()(),(

5、nnyxyxyxyxD 未知样本被分配到 K 个最临近者中最公共的类。在最简单的情况下，也就是当 K=1 时，未知样本被指定到模式空间中与之最临近的训练样本的类。2、算法步骤 初始化距离为最大值；计算未知样本和每个训练样本的距离dist；得到目前 K 个最临近样本中的最大距离maxdist；如果 dist 小于 maxdist，则将该训练样本作为K-最近邻样本；重复步骤 2、3、4，直到未知样本和所有训练样本的距离都算完；统计 K-最近邻样本中每个类标号出现的次数；选择出现频率最大的类标号作为未知样本的类标号。吾日三省乎吾身。为人谋而不忠乎？与朋友交而不信乎？传不习乎？论语常将有日思无日，莫待

6、无时思有时。增广贤文 3、算法伪代码 搜索 k 个近邻的算法：kNN(An,k)输入：An为 N 个训练样本在空间中的坐标（通过文件输入），k 为近邻数 输出：x 所属的类别 取 A1Ak作为 x 的初始近邻，计算与测试样本 x 间的欧式距离 d（x,Ai）,i=1,2,.,k；按 d（x，Ai）升序排序，计算最远样本与 x 间的距离D-maxd(x,aj)|j=1,2,.,k;for(i=k+1;i=n;i+)计算ai与 x 间的距离d(x,Ai);if(d(x,Ai)D then 用 Ai代替最远样本 按 照 d(x,Ai)升 序 排 序，计 算 最 远 样 本 与x间 的 距 离D-ma

7、xd(x,Aj)|j=1,.,i;计算前 k 个样本 Ai),i=1,2,.,k 所属类别的概率，具有最大概率的类别即为样本 x 的类。五、数据结构 代码结构如图所示，方法描述如下：KNN：KNN 类构造函数，用于读取数据集；get_all_distance:KNN类公有函数，计算要分类的点到所有点的距离；get_distance:KNN类私有函数，计算两点间的距离；吾日三省乎吾身。为人谋而不忠乎？与朋友交而不信乎？传不习乎？论语好学近乎知，力行近乎仁，知耻近乎勇。中庸 get_max_freq_label:KNN 类公有函数，在 k 个数据里，获取最近 k 个数据的分类最多的标签，将测试数据

8、归位该类。类图如上图所示，KNN 类的成员变量描述如下：dataSet：tData 型二维数组，用于训练的数据集；k：int 型，从 k 个最近的元素中，找类标号对应的数目的最大值，归类；labels：tLable 型一维数组，类标签；map_index_dist：map型，记录测试点到各点的距离；map_label_freq：map型，记录 k 个邻居类，各类的个数。六、程序截图 百川东到海，何时复西归？少壮不尽力，老大徒伤悲。汉乐府长歌行吾日三省乎吾身。为人谋而不忠乎？与朋友交而不信乎？传不习乎？论语 七、实验总结 八、附件 1.程序源码#include#include#include#i

9、nclude#include using namespace std;typedef char tLabel;typedef double tData;typedef pair PAIR;const int colLen=2;const int rowLen=10;ifstream fin;class KNN private:tData dataSetrowLencolLen;tLabel labelsrowLen;int k;map map_index_dis;map map_label_freq;double get_distance(tData*d1,tData*d2);public:K

10、NN(int k);void get_all_distance(tData*testData);void get_max_freq_label();struct CmpByValue bool operator()(const PAIR&lhs,const PAIR&rhs)return k=k;();if(!fin)coutcan not open the file endl;exit(1);/*input the dataSet*/for(int i=0;irowLen;i+)for(int j=0;jdataSetij;finlabelsi;/*calculate the distanc

11、e 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);irst 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;irst +;

12、勿以恶小而为之，勿以善小而不为。刘备其身正，不令而行；其身不正，虽令不从。论语 map:const_iterator map_it=();tLabel label;int max_freq=0;/find the most frequent label while(map_it!=()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()tData testDatacolLen;int k;coutplease input the k value:k;KNN knn(k);coutplease input the test data:endl;for(int i=0;itestDatai;(testData);();system(pause);return 0;2.数据集 常将有日思无日，莫待无时思有时。增广贤文宠辱不惊，看庭前花开花落；去留无意，望天上云卷云舒。洪应明