K-最临近分类算法分析

1、数据挖掘实验报告K.最临近分类算法学号：311062202姓名：汪文娟一、数据源说明1.数据理解选择第二包数据Iris Data Set,共有150组数据，考虑到训练数据集的随机性和多样性,（1）每组数据有5个属性，分别是:选择rowNo模3不等于0的100组作为训练数据集，剩下的50组做测试数据集。1. sepal length in cm2. sepal wrowNoth in cm3. petal length in cm4. petal wrowNoth in cm5. class ：-Iris Setosa-Iris Versicolour-Iris Virginica（2）为了操作

2、方便，对各组数据添加rowN。属性，且第一组rowNo=K2.数据清理现实世界的数据一般是不完整的、有噪声的和不一致的。数据清理例程试图填充缺失的 值，光滑噪声并识别离群点，并纠正数据中的不一致。a）缺失值：当数据中存在缺失值是，忽略该元组（注意：本文选用的第二组数据Iris Data Set 的 Missing Attribute Values: None）。b）噪声数据：本文暂没考虑。二、K .最临近分类算法KNN（k Nearest Neighbors）算法又叫k最临近方法，假设每一个类包含多个样本数据， 而且每个数据都有一个唯一的类标记表示这些样本是属于哪一个分类，KNN就是计算每个

3、样本数据到待分类数据的距离，如果一个样本在特征空间中的k个最相似（即特征空间 中最邻近）的样本中的大多数属于某一个类别，则该样本也属于这个类别。该方法在 定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。 KNN方法虽然从原理上也依赖于极限定理，但在类别决策时，只与极少量的相邻样本 有关。因此，采用这种方法可以较好地避免样本的不平衡问题。另外，由于KNN方法 主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对 于类域的交叉或重叠较多的待分样本集来说，KNN方法较其他方法更为适合。该方 法的不足之处是计算量较大，因为对每一个待分类的文本都要计算它到全

4、体已知样本 的距离，才能求得它的K个最近邻点。目前常用的解决方法是事先对已知样本点进行 剪辑，事先去除对分类作用不大的样本。该算法比较适用于样本容量比较大的类域的 自动分类，而那些样本容量较小的类域采用这种算法比较容易产生误分。(1)算法思路：K-最临近分类方法存放所有的训练样本，在接受待分类的新样本之前不需构造模 型，并且直到新的(未标记的)样本需要分类时才建立分类。K-最临近分类基于类比 学习，其训练样本由N维数值属性描述，每个样本代表N维空间的一个点。这样，所 有训练样本都存放在N维模式空间中。给定一个未知样本，k-最临近分类法搜索模式 空间，找出最接近未知样本的K个训练样本。这K个训练

5、样本是未知样本的K个“近 邻”。“临近性”又称为相异度(Dissimilarity),由欧几里德距离定义，其中两个点 X (xu x:, Xa)和Y (y“y：,yC的欧几里德距离是：O(X，y) = J(内一必)2 +*2 - 力)2 + +区 一)未知样本被分配到K个最临近者中最公共的类。在最简单的情况下，也就是当K=1 时，未知样本被指定到模式空间中与之最临近的训练样本的类。(2)算法步骤：step. 1 初始化距离为最大值step. 2-计算未知样本和每个训练样本的距离diststep. 3-得到目前K个最临近样本中的最大距离maxdiststep. 4如果dist小于maxdist,

6、则将该训练样本作为K-最近邻样本step. 5-重复步骤2、3、4,直到未知样本和所有训练样本的距离都算完step. 6-统计K-最近邻样本中每个类标号出现的次数step. 7-选择出现频率最大的类标号作为未知样本的类标号三、算法源代码/ KNN.cppK 最近邻分类算法/#include <stdlib.h>#include <stdio.h>#include <memor)r.h>#include <string.h>#include <iostream.h>#include <math.h>include <f

7、slream.h>/ 宏定义/属性数目训练数据集的最大大小测试数据集的最大大小属性最大值#define ATTR.NUM 4#define MAX_SIZE_OF_TRAINING_SET 1000#define MAX_SIZE_OF_TEST_SET100#define MAX.VALUE 10000.0#define K 7结构体struct dataVector (int ID:/ID 号char classLabel15|:分类标号double attributesATTR_NUM: 属性 ；struct distanceStruct (/ID 号距离分类标号int ID:do

8、uble distance:char classLabel15|;；/全局变量/struct dataVector gTrainingSet|MAX_SIZE_OF.TRAINING_SET: 训练数据集struct dataVector gTestSet|MAX_SIZE_OF_TEST_SET;测试数据集struct distanceStruct gNearestDistanceK|:/K 个最近邻距离int curTrainingSetSize=O:训练数据集的大小int curTestSetSize=O:测试数据集的大小/ / 求 vectorl=(xl.x2.xn)和 vector2

9、=(yl,y2,yn)的欧几里德距离 / double Dislance(struct dalaVector vectorLstruct dataVector vector?) (double dist.sum=0.0;for(int i=O;i<ATTR_NUM;i+) sum+=(vectorl.attnbutesi-vector2.altributes|il)*(vectorl.attnbutes|i-vector2.attributes|i|); ) dist=sqrt(suin)： return dist;)/ / 得到gNearestDistance中的最大距离，返回下标 /

10、 int GetMaxDistanceO (int maxNo=0： for(int i=l:i<K:i+) if(gNearestDisiance|i).distaiice>gNearestDistanceinaxNo.distance) maxNo = i;) retuni maxNo： )/ / 对未知样本Sample分类 / char* Classify(slruct dataVector Sample)double dist=O:int maxid=Oj'reqKxtmpfreq=lchar *curClassLable=gNearestDistance|O.cl

11、assLabel: memset( freq.l.sizeof( freq);/step. 1-初始化距离为最大值 for(i=O;i<K;i+)gNeareslDistancei.distance=MAX_ VALUE; )siep,2计算K-最近邻距离 fbr(i=O;i<curTrainingSetSize;i+) step.2.l-计算未知样本和每个训练样本的距离dist=Distance(gTrainingSet|i|.Sample);step.2.2得到 gNearestDislance 中的最大距离 maxid=GetMaxDistance();step23-如果距离

12、小于gNearestDislance中的最大距离，则将该样本作为K保近邻样木 if(disi<gNeareslDistance|inaxid.distance) (gNearestDistance(maxid.ID=gTrainingSeti.ID:gNearestDistance|maxid.distance=dist:strcpy(gNearestDistance|maxid|.classLabel.gTrainingSet(i.classLabel): )/step. 3一统计每个类出现的次数for(i=0:i<K:i+) for(int j=O:j<K;j+) (if

13、(i!=j)&&(strcmp(gNearesiDistaiice|i.classLabel.gNearestDislance(j.classLabel)=O) freq|il+=l;siep.4一选择出现频率最大的类标号for(i=O;i<K;i+)if(freqil>lmpfreq)(linpfreq=freqi:curlassLable=gNearestDistance|i.classLabel:)return curClassLable;)/ 主函数/void main() (chare;char *classLabel="M:ini ij. ro

14、wNo=O.TruePositive=O.FalsePositive=0;ifstream filein("iris.dataM);FILE *fp:iftfilein.failOXcouKCan open data.txt H«endl： return:)“step. 1一读文件 while(!filein.eof() rowNo+，第一组数据 rowNo=lif(curTrainingSetSize>=MAX_SIZE_OF_TRAINING_SET) (couivv'The training set has H«MAX_SIZE_OF_TRAI

15、NING_SET«', exa!nples!M«endl«endl; break; ) /rowNo%3!=0的100组数据作为训练数据集 if(rowNo%3!=0) (gTrainingSet(curTrainingSetSize.ID=rowNo: for(inli = 0;i< ATTR_NUM:i+) filein»gTrainingSet|curTrainingSetSize|.atlributes|il; filein»c: ) filein»gTrainingSetcurTrainingSetSize.c

16、lassLabel;curTrainingSelSize+;)剩下rowNo%3=0的50组做测试数据集 else if(rowNo%3=0) (gTestSet|curTeslSetSize.ID=rowNo;for(inti = 0;i< ATTR_NUM:i+) filein»gTeslSel|curTeslSetSize.attributes(i: filein»c:filein»gTestSetcurTestSetSizel.classLabel: curTeslSetSize+:filein.closeO;siep.2KNN算法进行分类，并将结果

17、写到文件iris_OutPut.txt fp=fopen(Miris_Ou(Pui.txt,Hw+tH);用KNN算法进行分类fprinlftlp.*程fprinlf(fp：*采用KNN算法对iris.data分类。为了操作方便，对各组数据添加rowNo属性,第一组 rowNo=l!i)");fprinlfdp;*共有150组数据,选择rowNo模3不等于0的100组作为训练数据集，剩下的50组做测 试数据集n)fprinlidp.fprintftfp.fdr(i=O;i<curTestSetSize;i+)”*%dfprintf(fpJ* *classLabel =Class

18、ify(gTestSeti);的1©1甲(。匕§§11小1小£61川.(:匕$§1氏1)=0)相等时，分类正确TruePosilive+:cout«MrowNo:cout«gTestSet|i|.ID«Hcout«MKNN分类结果: coutvvclassLabekv%正确类标号:"；cout<vgTestSeUi.classLabelv<”)n"；fprintftfp/'rowNo:%3d t KNN 分类结果： %s (正确类标号：%s )ifgTestSet|

19、il.ID,classLabeLgTeslSet|i).classLabel);小皿1】甲(：屈§111)1田10$【51”.(：屈§11)!=0)不等时，分类错误 ( / cout«H分类错误叱41"；fprintf(fp.” 分类错误*n")； fprintf(fpj%d-最临近数据:n”,K);for(j=0;j<K:j+) ( /cout<<gNearestDistancej.ID«Mt,'«gNearestDistance(jl.distance«HiM«gNeares

20、lDistancej.classLabel|15«endl;fprintf(fp,MrowNo:%3dtDistance:%fVClassLable:%snM,gNeareslDistance(j.ID.gNeareslDistancej.distance.gNeareslDistancej.cIassLabel):) fprintf(fp/'n°); ) FaIsePositive=curTestSetSize-TruePositive; fprintf(W* 京 *结果分析*n” ) fprinlf(fp,HTP(Truepositive):%dnFP( Fal

21、sepositive): %dnaccuracy: %fn'TruePositive.FaIsePositive.double(TruePositive)/(curTestSetSize-l); fclose(fp); retum: )四、详细描述该算法获得的模型采用第二包数据Iris Data Set,共有150组数据，考虑到训练数据集的随机性和多样性， 选择rowNo模3不等于0的100组作为训练数据集，剩下的50组做测试数据集。对未知样本进行分类(括号里的正确类标号是读取的iris.data文件里的类标号，括号外的是计算所得)， 本文取k=7个最邻近数据。以第19组为例进行说明，

22、未知样本ROWNO为57,经过KNN算法分类，与之最临近的 7 组数据 rowNo 号分别为:52、86、128、139、92、64、71,其中类标号为 Iris-versicolor 的有5个，类标号为Iris-virginica的有2个，Iris-versicolor为最多，因此据此估计该组样本的类标号为 Iris-versicolor©50组测试样本运行结果如下：* *程序说 qjj * * *采用KNN算法对iris.data分类。为了操作方便,对各组数据添加rowNo属性.第一组rowNo=l!*共有150组数据.选择rowNo模3不等于0的100组作为训练数据集，剩下的5

23、0组做测试数据集 *京*实验结果*rowNo:3KNN 分类结果：Iris-setosa （正确类标号：Iris-setosa ）7.最临近数据：rowNo:43Distance:0.300000ClassLable:Iris-setosarowNo:Distance:0.300000ClassLable:Iris-setosarowNo:4Distance:0.244949ClassLable:Iris-setosarowNo:13Distance:0.264575ClassLable:Iris-setosarowNo:7Distance:0.264575ClassLable:Iris-se

24、tosa第1组数据*rowNo:46Distance: 0.264575 ClassLable:Iris-setosarowNo:10Distance: 0.316228 ClassLable:Iris-setosa*览 2 幺H 轨出*rowNo:6KNN 分类结果：Iris-setosa （正确类标号：Iris-setosa ）7.最临近数据：rowNo:22Distance:0.412311ClassLable:Iris-setosarowNo:47Distance:0.387298ClassLable:Iris-setosarowNo:11Distance:0346410ClassLa

25、ble:Iris-setosarowNo:49Distance:0360555ClassLable:Iris-setosarowNo:19Distance:0.331662ClassLable:Iris-setosarowNo:20Distance:0387298ClassLable:Iris-setosarowNo:17Distance:0.400000ClassLable:Iris-setosa*今*第 3 tEl(*rowNo:9KNN 分类结果：Iris-setosa（正确类标号：Iris-setosa ）7-最临近数据:rowNo:14Distance:0.346410ClassLa

26、ble:Iris-setosarowNo:2Distance:0.509902ClassLable:Iris-setosarowNo:4Distance:0.300000ClassLable:Iris-setosarowNo:13Distance:0.424264ClassLable:Iris-setosarowNo:46Distance:0.424264ClassLable:Iris-setosarowNo:31Distance:0.489898ClassLable:Iris-setosarowNo:43Distance:0316228ClassLable:Iris-setosa* 第 4*

27、 *rowNo:12KNN分类结果：Irisseiosa（正确类标号：Iris-setosa ）7-最临近数据：rowNo:31Distance:0.300000ClassLable:Iris-setosarowNo:25Distance:0.300000ClassLable:Iris-setosarowNo:40Distance:0.316228ClassLable:Iris-setosarowNo:50Distance:0.300000ClassLable:Iris-setosarowNo:7Distance:0.300000ClassLable:Iris-setosarowNo:8Dis

28、tance:0.223607ClassLable:Iris-setosarowNo:10Distance:0346410ClassLable:Iris-setosa*京*第 5 (*rowNo:15KNN 分类结果：Iris-setosa （正确类标号：Iris-setosa ）7-最临近数据：rowNo:34Distance:0.412311ClassLable:Iris-setosarowNo:17Distance:0.469042ClassLable:Iris-setosarowNo:11Distance:0.583095ClassLable:Iris-setosarowNo:37Dis

29、tance:0.591608ClassLable:Iris-setosarowNo:16Distance:0.547723ClassLable:Iris-setosarowNo:49Distance: 0.655744 ClassLable:Iris-setosarowNo:19Distance: 0.556776 ClassLable:Iris-setosa*rowNo:18KNN 分类结果：Iris-setosa （正确类标号：Iris-setosa ）7.最临近数据：rowNo:1Distance:0.100000ClassLable:Iris-setosarowNo:40Distanc

30、e:0.173205ClassLable:Iris-setosarowNo:29Distance:0.173205ClassLable:Iris-setosarowNo:5Distance:0.173205ClassLable:Iris-setosarowNo:41Distance:0.141421ClassLable:Iris-setosarowNo:8Distance:0.200000ClassLable:Iris-setosarowNo:28Distance:0.173205ClassLable:Iris-setosa第6组数据*4!*第 7 幺。*rowNo:21KNN 分类结果：Ir

31、is-seiosa （正确类标号：Iris-setosa ）7-最临近数据：rowNo:49Distance:0374166ClassLable:Iris-setosarowNo:37Distance:0.424264ClassLable:Iris-setosarowNo:11Distance:0360555ClassLable:Iris-setosarowNo:29Distance:0360555ClassLable:Iris-setosarowNo:28Distance:0.300000ClassLable:Iris-setosarowNo:40Distance:0360555ClassL

32、able:Iris-setosarowNo:32Distance:0.282843ClassLable:Iris-setosarowNo:24KNN分类结果：kisseiosa（正确类标号：Iris-setosa ）7-最临近数据：rowNo:40Distance:0374166ClassLable:Iris-setosarowNo:26Distance:0.447214ClassLable:Iris-setosarowNo:44Distance:0.264575ClassLable:Iris-setosarowNo:28Distance:0.424264ClassLable:Iris-set

33、osarowNo:32Distance:0387298ClassLable:Iris-setosarowNo:8Distance:0.387298ClassLable:Iris-setosarowNo:50Distance:0.435890ClassLable:Iris-setosa*第8组数据rowNo:27KNN 分类结果：Iris-setosa （正确类标号：Iris-setosa ）7-最临近数据：rowNo:1Distance:0316228ClassLable:Iris-setosarowNo:50Distance:0.300000ClassLable:Iris-setosarow

34、No:41Distance:0331662ClassLable:Iris-setosarowNo:44Distance:0.223607ClassLable:Iris-setosarowNo:40Distance:0.244949ClassLable:Iris-setosa*第9组数据rowNo:rowNo:28Distance: 0.223607 ClassLable: Iris-setosa*4( *4( *Distance: 0.316228 ClassLable: Iris-setosa*京*第Q 组数据*京*rowNo:30KNN 分类结果：Iris-setosa （正确类标号：Ir

35、is-setosa ）7.最临近数据：rowNo:31Distance:0.141421ClassLable:Iris-setosarowNo:38Distance:0.264575ClassLable:Iris-setosarowNo:4Distance:0.173205ClassLable:Iris-setosarowNo:13Distance:0316228ClassLable:Iris-setosarowNo:7Distance:0316228ClassLable:Iris-setosarowNo:35Distance:0.264575ClassLable:Iris-setosarow

36、No:10Distance:0.264575ClassLable:Iris-setosa第 11*rowNo:33KNN 分类结果：Iris-seiosa （正确类标号：Iris-setosa ）7-最临近数据：rowNo:34Distance:0.346410ClassLable:Iris-setosarowNo:22Distance:0.509902ClassLable:Iris-setosarowNo:11Distance:0.458258ClassLable:Iris-setosarowNo:49Distance:0.424264ClassLable:Iris-setosarowNo:

37、47Distance:0346410ClassLable:Iris-setosarowNo:20Distance:0374166ClassLable:Iris-setosarowNo:17Distance:0.458258ClassLable:Iris-setosa*第 12*rowNo:36KNN分类结果：Irisseiosa（正确类标号：Iris-setosa ）7-最临近数据：rowNo:38Distance:0.346410ClassLable:Iris-setosarowNo:2Distance:0.300000ClassLable:Iris-setosarowNo:41Distan

38、ce:0.331662ClassLable:Iris-setosarowNo:35Distance:0.346410ClassLable:Iris-setosarowNo:29Distance:0346410ClassLable:Iris-setosarowNo:50Distance:0.223607ClassLable:Iris-setosarowNo:10Distance:0346410ClassLable:Iris-setosa*东*第3 (*rowNo:39KNN分类结果：Iris-setosa （正确类标号：kisselosa ）7-最临近数据：rowNo:13Distance:0.

39、424264ClassLable:Iris-setosarowNo:46Distance:0.424264ClassLable:Iris-setosarowNo:4Distance:0.300000ClassLable:Iris-setosarowNo:14Distance:0.244949ClassLable:Iris-setosarowNo:7Distance:0.469042ClassLable:Iris-setosarowNo:31Distance: 0.509902 ClassLable:Iris-setosarowNo:43Distance: 0.200000 ClassLable

40、:Iris-setosa*京* *第14 组数据 * *rowNo:42KNN 分类结果：Iris-setosa （正确类标号：Iris-setosa ）7.最临近数据：rowNo:14Distance:0.781025ClassLable:Iris-setosarowNo:Distance:0.818535ClassLable:Iris-setosarowNo:4Distance:0.836660ClassLable:Iris-setosarowNo:13Distance:0.793725ClassLable:Iris-setosarowNo:31Distance:0.911043Class

41、Lable:Iris-setosarowNo:46Distance:0.768115ClassLable:Iris-setosarowNo:43Distance:0.911043ClassLable:Iris-setosa*今*第5 组数据*rowNo:45KNN分类结果：Irisseiosa （正确类标号：Iris-setosa ）7-最临近数据：rowNo:28Distance:0.547723ClassLable:Iris-setosarowNo:49Distance:0.500000ClassLable:Iris-setosarowNo:22Distance:0.412311Class

42、Lable:Iris-setosarowNo:47Distance:0360555ClassLable:Iris-setosarowNo:20Distance:0.412311ClassLable:Iris-setosarowNo:44Distance:0.479583ClassLable:Iris-setosarowNo:25Distance:0.538516ClassLable:Iris-setosa*第6*rowNo:48KNN分类结果：Irisseiosa（正确类标号：Iris-setosa ）7-最临近数据：rowNo:13Distance:0.300000ClassLable:Ir

43、is-setosarowNo:43Distance:0.223607ClassLable:Iris-setosarowNo:4Distance:0.141421ClassLable:Iris-setosarowNo:31Distance:0.300000ClassLable:Iris-setosarowNo:7Distance:0.223607ClassLable:Iris-setosarowNo:46Distance:0.300000ClassLable:Iris-setosarowNo:10Distance:0346410ClassLable:Iris-setosa* 京*第7* *row

44、No: 517.最临近数据:KNN 分类结果：Iris-versicolor （正确类标号：Iris-versicolor）rowNo:59Distance:0.519615ClassLable:Iris-versicolorrowNo:77Distance:0.458258ClassLable:Iris-versicolorrowNo:55Distance:0.655744ClassLable:Iris-versicolorrowNo:134Distance:0.905539ClassLable:Iris-virginicarowNo:53Distance:0.264575ClassLable:Iris-versicolorrowNo:76Distance: 0.538516 ClassLable: Iris-versicolorrowNo:52Distance: 0.640312ClassLable: Iris-versicolor*京*第8*