K最临近分类算法.docx
K最临近分类算法数据挖掘实验报告 K-最临近分类算法 学号：311062202 姓名：汪文娟 一、 数据源说明 1.数据理解 选择第二包数据Iris Data Set，共有150组数据,考虑到训练数据集的随机性和多样性，选择rowNo模3不等于0的100组作为训练数据集，剩下的50组做测试数据集。 。 b) 噪声数据：本文暂没考虑。 二、 K-最临近分类算法 KNN(k Nearest Neighbors)算法又叫k最临近方法，假设每一个类包含多个样本数据，而且每个数据都有一个唯一的类标记表示这些样本是属于哪一个分类， KNN就是计算每个样本数据到待分类数据的距离，如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。 KNN方法虽然从原理上也依赖于极限定理，但在类别决策时，只与极少量的相邻样本有关。因此，采用这种方法可以较好地避免样本的不平衡问题。另外，由于KNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，KNN方法较其他方法更为适合。 该方法的不足之处是计算量较大，因为对每一个待分类的文本都要计算它到全体已知样本的距离，才能求得它的K个最近邻点。目前常用的解决方法是事先对已知样本点进行剪辑，事先去除对分类作用不大的样本。该算法比较适用于样本容量比较大的类域的自动分类，而那些样本容量较小的类域采用这种算法比较容易产生误分。 算法思路： K-最临近分类方法存放所有的训练样本，在接受待分类的新样本之前不需构造模型，并且直到新的样本需要分类时才建立分类。K-最临近分类基于类比学习，其训练样本由N维数值属性描述，每个样本代表N维空间的一个点。这样，所有训练样本都存放在N维模式空间中。给定一个未知样本，k-最临近分类法搜索模式空间，找出最接近未知样本的K个训练样本。这K个训练样本是未知样本的K个“近邻”。“临近性”又称为相异度，由欧几里德距离定义，其中两个点 X和Y的欧几里德距离是： D(x,y)=(x1-y1)2+(x2-y2)2+.+(xn-yn)2 未知样本被分配到K个最临近者中最公共的类。在最简单的情况下，也就是当K=1时，未知样本被指定到模式空间中与之最临近的训练样本的类。 算法步骤： step.1-初始化距离为最大值 step.2-计算未知样本和每个训练样本的距离dist step.3-得到目前K个最临近样本中的最大距离maxdist step.4-如果dist小于maxdist，则将该训练样本作为K-最近邻样本 step.5-重复步骤2、3、4，直到未知样本和所有训练样本的距离都算完 step.6-统计K-最近邻样本中每个类标号出现的次数 step.7-选择出现频率最大的类标号作为未知样本的类标号 三、 算法源代码 / / / KNN.cpp K-最近邻分类算法 / / #include <stdlib.h> #include <stdio.h> #include <memory.h> #include <string.h> #include <iostream.h> #include <math.h> #include <fstream.h> / / / 宏定义 / / #define ATTR_NUM 4 /属性数目 #define MAX_SIZE_OF_TRAINING_SET 1000 /训练数据集的最大大小 #define MAX_SIZE_OF_TEST_SET 100 /测试数据集的最大大小 #define MAX_VALUE 10000.0 /属性最大值 #define K 7 /结构体 struct dataVector ; struct distanceStruct ; / / / 全局变量 / / struct dataVector gTrainingSetMAX_SIZE_OF_TRAINING_SET; /训练数据集 struct dataVector gTestSetMAX_SIZE_OF_TEST_SET; /测试数据集 struct distanceStruct gNearestDistanceK; /K个最近邻距离 int ID; /ID号 double distance; /距离 char classLabel15; /分类标号 int ID; /ID号 char classLabel15; /分类标号 double attributesATTR_NUM; /属性 int curTrainingSetSize=0; /训练数据集的大小 int curTestSetSize=0; /测试数据集的大小 / / / 求 vector1=(x1,x2,.,xn)和vector2=(y1,y2,.,yn)的欧几里德距离 / / double Distance(struct dataVector vector1,struct dataVector vector2) / / / 得到gNearestDistance中的最大距离，返回下标 / / int GetMaxDistance / / / 对未知样本Sample分类 / / char* Classify(struct dataVector Sample) double dist=0; int maxid=0,freqK,i,tmpfreq=1; char *curClassLable=gNearestDistance0.classLabel; memset(freq,1,sizeof(freq); /step.1-初始化距离为最大值 for(i=0;i<K;i+) int maxNo=0; for(int i=1;i<K;i+) if(gNearestDistancei.distance>gNearestDistancemaxNo.distance) maxNo = i; double dist,sum=0.0; for(int i=0;i<ATTR_NUM;i+) dist=sqrt(sum); return dist; sum+=(vector1.attributesi-vector2.attributesi)*(vector1.attributesi-vector2.attributesi); return maxNo; / / / 主函数 / /step.2-计算K-最近邻距离 for(i=0;i<curTrainingSetSize;i+) /step.3-统计每个类出现的次数 for(i=0;i<K;i+) /step.4-选择出现频率最大的类标号 for(i=0;i<K;i+) return curClassLable; if(freqi>tmpfreq) tmpfreq=freqi; curClassLable=gNearestDistancei.classLabel; for(int j=0;j<K;j+) if(i!=j)&&(strcmp(gNearestDistancei.classLabel,gNearestDistancej.classLabel)=0) freqi+=1; /step.2.1-计算未知样本和每个训练样本的距离 dist=Distance(gTrainingSeti,Sample); /step.2.2-得到gNearestDistance中的最大距离 maxid=GetMaxDistance; /step.2.3-如果距离小于gNearestDistance中的最大距离，则将该样本作为K-最近邻样本 if(dist<gNearestDistancemaxid.distance) gNearestDistancemaxid.ID=gTrainingSeti.ID; gNearestDistancemaxid.distance=dist; strcpy(gNearestDistancemaxid.classLabel,gTrainingSeti.classLabel); gNearestDistancei.distance=MAX_VALUE; / void main char c; int i,j, rowNo=0,TruePositive=0,FalsePositive=0; ifstream filein("iris.data"); FILE *fp; if(filein.fail)cout<<"Can't open data.txt"<<endl; return; /step.1-读文件 while(!filein.eof) rowNo+;/第一组数据rowNo=1 if(curTrainingSetSize>=MAX_SIZE_OF_TRAINING_SET) cout<<"The break ; training set has "<<MAX_SIZE_OF_TRAINING_SET<<" char *classLabel="" examples!"<<endl<<endl; /rowNo%3!=0的100组数据作为训练数据集 if(rowNo%3!=0) /剩下rowNo%3=0的50组做测试数据集 else if(rowNo%3=0) gTestSetcurTestSetSize.ID=rowNo; for(int i = 0;i < ATTR_NUM;i+) filein>>gTestSetcurTestSetSize.attributesi; filein>>c; gTrainingSetcurTrainingSetSize.ID=rowNo; for(int i = 0;i < ATTR_NUM;i+) filein>>gTrainingSetcurTrainingSetSize.attributesi; filein>>c; filein>>gTrainingSetcurTrainingSetSize.classLabel; curTrainingSetSize+; filein>>gTestSetcurTestSetSize.classLabel; curTestSetSize+; filein.close; /step.2-KNN算法进行分类，并将结果写到文件iris_OutPut.txt fp=fopen("iris_OutPut.txt","w+t"); /用KNN算法进行分类 fprintf(fp,"*程序说明 *n"); fprintf(fp,"* 采用KNN算法对iris.data分类。为了操作方便，对各组数据添加rowNo属性,第一组fprintf(fp,"* 共有150组数据,选择rowNo模3不等于0的100组作为训练数据集，剩下的50组做测fprintf(fp,"*fprintf(fp,"*for(i=0;i<curTestSetSize;i+) 第%d组数据实验结果rowNo=1!n"); 试数据集n"); *nn"); *nn"); fprintf(fp,"*n",i+1); cout<<classLabel<<"(正确类标号: " cout<<gTestSeti.classLabel<<")n" fprintf(fp,"rowNo: %3d t KNN classLabel =Classify(gTestSeti); cout<<"rowNo: " cout<<gTestSeti.ID<<" t" cout<<"KNN分类结果: " TruePositive+; if(strcmp(classLabel,gTestSeti.classLabel)=0)/相等时，分类正确 分类结果: %s ( 正确类标号: %s )n",gTestSeti.ID,classLabel,gTestSeti.classLabel); if(strcmp(classLabel,gTestSeti.classLabel)!=0)/不等时，分类错误 / fprintf(fp,"%d-最临近数据:n",K); for(j=0;j<K;j+) /cout<<" *分类错误*n" fprintf(fp," *分类错误*n"); cout<<gNearestDistancej.ID<<"t"<<gNearestDistancej.distance<<"t"<<gNearestDistancej.classLabel15<<endl; fprintf(fp,"*fprintf(fp,"TP(True fclose(fp); positive): 结果分析 fprintf(fp,"n"); fprintf(fp,"rowNo: %3d t Distance: %f tClassLable: %sn",gNearestDistancej.ID,gNearestDistancej.distance,gNearestDistancej.classLabel); FalsePositive=curTestSetSize-TruePositive; *n",i); %dnFP(False positive): %dnaccuracy: %fn",TruePositive,FalsePositive,double(TruePositive)/(curTestSetSize-1); return; 四、 详细描述该算法获得的模型 采用第二包数据Iris Data Set，共有150组数据,考虑到训练数据集的随机性和多样性，选择rowNo模3不等于0的100组作为训练数据集，剩下的50组做测试数据集。对未知样本进行分类，本文取k=7个最邻近数据。 以第19组为例进行说明，未知样本ROWNO为57，经过KNN算法分类，与之最临近的7组数据rowNo号分别为：52、86、128、139、92、64、71，其中类标号为Iris-versicolor的有5个，类标号为Iris-virginica的有2个，Iris-versicolor为最多，因此据此估计该组样本的类标号为Iris-versicolor。 50组测试样本运行结果如下： *程序说明* * 采用KNN算法对iris.data分类。为了操作方便，对各组数据添加rowNo属性,第一组rowNo=1! * 共有150组数据,选择rowNo模3不等于0的100组作为训练数据集，剩下的50组做测试数据集 * *实验结果* *第1组数据* rowNo: 3 7-最临近数据: rowNo: rowNo: rowNo: rowNo: rowNo: 43 Distance: 0.300000 ClassLable: Iris-setosa 2 Distance: 0.300000 ClassLable: Iris-setosa 4 Distance: 0.244949 ClassLable: Iris-setosa 13 Distance: 0.264575 ClassLable: Iris-setosa 7 Distance: 0.264575 ClassLable: Iris-setosa KNN分类结果: Iris-setosa ( 正确类标号: Iris-setosa ) rowNo: rowNo: *第2组数据* rowNo: 6 7-最临近数据: rowNo: rowNo: rowNo: rowNo: rowNo: rowNo: rowNo: *第3组数据* rowNo: 9 7-最临近数据: rowNo: rowNo: rowNo: rowNo: rowNo: rowNo: rowNo: *第4组数据* rowNo: 12 7-最临近数据: rowNo: rowNo: rowNo: rowNo: rowNo: rowNo: rowNo: *第5组数据* rowNo: 15 7-最临近数据: rowNo: rowNo: rowNo: rowNo: rowNo: 34 Distance: 0.412311 ClassLable: Iris-setosa 17 Distance: 0.469042 ClassLable: Iris-setosa 11 Distance: 0.583095 ClassLable: Iris-setosa 37 Distance: 0.591608 ClassLable: Iris-setosa 16 Distance: 0.547723 ClassLable: Iris-setosa KNN分类结果: Iris-setosa ( 正确类标号: Iris-setosa ) 31 Distance: 0.300000 ClassLable: Iris-setosa 25 Distance: 0.300000 ClassLable: Iris-setosa 40 Distance: 0.316228 ClassLable: Iris-setosa 50 Distance: 0.300000 ClassLable: Iris-setosa 7 Distance: 0.300000 ClassLable: Iris-setosa 8 Distance: 0.223607 ClassLable: Iris-setosa 10 Distance: 0.346410 ClassLable: Iris-setosa KNN分类结果: Iris-setosa ( 正确类标号: Iris-setosa ) 14 Distance: 0.346410 ClassLable: Iris-setosa 2 Distance: 0.509902 ClassLable: Iris-setosa 4 Distance: 0.300000 ClassLable: Iris-setosa 13 Distance: 0.424264 ClassLable: Iris-setosa 46 Distance: 0.424264 ClassLable: Iris-setosa 31 Distance: 0.489898 ClassLable: Iris-setosa 43 Distance: 0.316228 ClassLable: Iris-setosa KNN分类结果: Iris-setosa ( 正确类标号: Iris-setosa ) 22 Distance: 0.412311 ClassLable: Iris-setosa 47 Distance: 0.387298 ClassLable: Iris-setosa 11 Distance: 0.346410 ClassLable: Iris-setosa 49 Distance: 0.360555 ClassLable: Iris-setosa 19 Distance: 0.331662 ClassLable: Iris-setosa 20 Distance: 0.387298 ClassLable: Iris-setosa 17 Distance: 0.400000 ClassLable: Iris-setosa KNN分类结果: Iris-setosa ( 正确类标号: Iris-setosa ) 46 Distance: 0.264575 ClassLable: Iris-setosa 10 Distance: 0.316228 ClassLable: Iris-setosa rowNo: rowNo: *第6组数据* rowNo: 18 7-最临近数据: rowNo: rowNo: rowNo: rowNo: rowNo: rowNo: rowNo: *第7组数据* rowNo: 21 7-最临近数据: rowNo: rowNo: rowNo: rowNo: rowNo: rowNo: rowNo: *第8组数据* rowNo: 24 7-最临近数据: rowNo: rowNo: rowNo: rowNo: rowNo: rowNo: rowNo: *第9组数据* rowNo: 27 7-最临近数据: rowNo: rowNo: rowNo: rowNo: rowNo: 1 Distance: 0.316228 ClassLable: Iris-setosa 50 Distance: 0.300000 ClassLable: Iris-setosa 41 Distance: 0.331662 ClassLable: Iris-setosa 44 Distance: 0.223607 ClassLable: Iris-setosa 40 Distance: 0.244949 ClassLable: Iris-setosa KNN分类结果: Iris-setosa ( 正确类标号: Iris-setosa ) 40 Distance: 0.374166 ClassLable: Iris-setosa 26 Distance: 0.447214 ClassLable: Iris-setosa 44 Distance: 0.264575 ClassLable: Iris-setosa 28 Distance: 0.424264 ClassLable: Iris-setosa 32 Distance: 0.387298 ClassLable: Iris-setosa 8 Distance: 0.387298 ClassLable: Iris-setosa 50 Distance: 0.435890 ClassLable: Iris-setosa KNN分类结果: Iris-setosa ( 正确类标号: Iris-setosa ) 49 Distance: 0.374166 ClassLable: Iris-setosa 37 Distance: 0.424264 ClassLable: Iris-setosa 11 Distance: 0.360555 ClassLable: Iris-setosa 29 Distance: 0.360555 ClassLable: Iris-setosa 28 Distance: 0.300000 ClassLable: Iris-setosa 40 Distance: 0.360555 ClassLable: Iris-setosa 32 Distance: 0.282843 ClassLable: Iris-setosa KNN分类结果: Iris-setosa ( 正确类标号: Iris-setosa ) 1 Distance: 0.100000 ClassLable: Iris-setosa 40 Distance: 0.173205 ClassLable: Iris-setosa 29 Distance: 0.173205 ClassLable: Iris-setosa 5 Distance: 0.173205 ClassLable: Iris-setosa 41 Distance: 0.141421 ClassLable: Iris-setosa 8 Distance: 0.200000 ClassLable: Iris-setosa 28 Distance: 0.173205 ClassLable: Iris-setosa KNN分类结果: Iris-setosa ( 正确类标号: Iris-setosa ) 49 Distance: 0.655744 ClassLable: Iris-setosa 19 Distance: 0.556776 ClassLable: Iris-setosa r
