k最近邻算法实验报告

《k最近邻算法实验报告》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、k-最近邻算法实现题目学生姓名学生学号专业班级指导教师2015-1-2实验二k-最近邻算法实现一、实验目的1.加强对k-最近邻算法的理解；2.锻炼分析问题、解决问题并动手实践的能力。二、实验要求使用一种你熟悉的程序设计语言，如C++或java，给定最近邻数k和描述每个元组的属性数n，实现k-最近邻分类算法，至少在两种不同的数据集上比较算法的性能三、实验环境Win7旗舰版+VisualStudio2010语言：C++四、算法描述KNN(kNearestNeighbors)算法乂叫k最临近方法。假设每一个类包含多个样本数据，而且每个数据都有一个唯一的类标记表示这些样本是属于哪一个分类,K

2、NN就是计算每个样本数据到待分类数据的距离。如果一个样本在特征空间屮的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样木也属于这个类别。该方法在定类决策上只依据最邻近的一个或者几个样木的类别来决定待分样本所属的类别。KNN方法虽然从原理上也依赖于极限定理，但在类别决策时，只与极少量的相邻样本有关。因此，采用这种方法可以较好地避免样本的不平衡问题。另外，由于KNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待实验二k-最近邻算法实现一、实验目的1.加强对k-最近邻算法的理解；2.锻炼分析问题、解决问题并动手

3、实践的能力。二、实验要求使用一种你熟悉的程序设计语言，如C++或java，给定最近邻数k和描述每个元组的属性数n，实现k-最近邻分类算法，至少在两种不同的数据集上比较算法的性能三、实验环境Win7旗舰版+VisualStudio2010语言：C++四、算法描述KNN(kNearestNeighbors)算法乂叫k最临近方法。假设每一个类包含多个样本数据，而且每个数据都有一个唯一的类标记表示这些样本是属于哪一个分类,KNN就是计算每个样本数据到待分类数据的距离。如果一个样本在特征空间屮的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样木也属于这个类别。该方法在定类

4、决策上只依据最邻近的一个或者几个样木的类别来决定待分样本所属的类别。KNN方法虽然从原理上也依赖于极限定理，但在类别决策时，只与极少量的相邻样本有关。因此，采用这种方法可以较好地避免样本的不平衡问题。另外，由于KNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，KNN方法较其他方法更为适合。该方法的不足之处是计算量较大，因为对每一个待分类的文本都要计算它到全体已知样本的距离，才能求得它的K个最近邻点。0前常用的解决方法是事先对己知样本点进行剪辑，事先去除对分类作用不大的样木。该算法比较适用于样木容量比较大的类域的

5、自动分类，而那些样本容量较小的类域采用这种算法比较容易产生误分。1、算法思路K-最临近分类方法存放所有的训练样本，在接受待分类的新样本之前不需构造模型，并且直到新的(未标记的)样本需要分类时冰建立分类。K-最临近分类基于类比学习，其训练样本由N维数值属性描述，每个样本代表N维空间的一个点。这样，所冇训练样本都存放在N维模式空间中。给定一个未知样本，k-最临近分类法搜索模式空间，找出最接近未知样木的K个训练样木。这K个训练样本是未知样本的K个“近邻”。“临近性”乂称为和异度(Dissimilarity),由欧几里徳距离定义，其中两个点X(xl,x2,-,xn)和Y(yl，y2,…，yn

6、)的欧几里德距离是：7)=水'-y,)2+Cy2-y2)2+…+、xn-/J2未知样本被分配到K个最临近者中最公共的类。在最简单的情况下，也就是当K=1时，未知样本被指定到模式空间屮与之最临近的训练样本的类。2、算法步骤step.1…初始化距离为最大值；step.2…计算未知样本和每个训练样本的距离dist;step.3---得到目前K个最临近样本屮的最大距离maxdist；step.4---如果dist小于maxdist，则将该训练样本作为K-最近邻样本；step.5…重复步骤2、3、4,直到未知样木和所有训练样木的距离都算完；step.6---统计K-最近邻样本中每个类标号出现的

7、次数：step.7---选择出现频率最大的类标号作为未知样本的类标号。3、算法伪代码搜索k个近邻的算法：kNN(A[nl,k)输入：A[n]为N个训练样木在空间中的坐标(通过文件输入)，k为近邻数输出：x所属的类别取A[l]〜A[k]作为x的初始近邻，计算与测试样本x间的欧式距离d(x，A[ip，i=l，2,.....，k;按d(x,A[i])升序排序，计算最远样本与x间的距离D

8、j=l,2,…",k};for(i=k+l;i<