K-最临近分类算法

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

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

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

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

5、样本是未知样本的K个“近邻”。“临近性”又称为相异度（Dissimilarity），由欧几里德距离定义，其中两个点 X（x1,x2,xn）和Y（y1,y2,yn）的欧几里德距离是：未知样本被分配到K个最临近者中最公共的类。在最简单的情况下，也就是当K=1时，未知样本被指定到模式空间中与之最临近的训练样本的类。（2）算法步骤：step.1-初始化距离为最大值step.2-计算未知样本和每个训练样本的距离diststep.3-得到目前K个最临近样本中的最大距离maxdiststep.4-如果dist小于maxdist，则将该训练样本作为K-最近邻样本step.5-重复步骤2、3、4，直到未知样本和

6、所有训练样本的距离都算完step.6-统计K-最近邻样本中每个类标号出现的次数step.7-选择出现频率最大的类标号作为未知样本的类标号三、 算法源代码/ KNN.cpp K-最近邻分类算法/#include #include #include #include #include #include #include / 宏定义/#define ATTR_NUM 4 /属性数目#define MAX_SIZE_OF_TRAINING_SET 1000 /训练数据集的最大大小#define MAX_SIZE_OF_TEST_SET 100 /测试数据集的最大大小#define MAX_VALUE

7、10000.0 /属性最大值#define K 7/结构体struct dataVector int ID; /ID号char classLabel15; /分类标号double attributesATTR_NUM; /属性;struct distanceStruct int ID; /ID号double distance; /距离char classLabel15; /分类标号;/ 全局变量/struct dataVector gTrainingSetMAX_SIZE_OF_TRAINING_SET; /训练数据集struct dataVector gTestSetMAX_SIZE_OF_

8、TEST_SET; /测试数据集struct distanceStruct gNearestDistanceK; /K个最近邻距离int curTrainingSetSize=0; /训练数据集的大小int curTestSetSize=0; /测试数据集的大小/ 求 vector1=(x1,x2,.,xn)和vector2=(y1,y2,.,yn)的欧几里德距离/double Distance(struct dataVector vector1,struct dataVector vector2)double dist,sum=0.0;for(int i=0;iATTR_NUM;i+)sum

9、+=(vector1.attributesi-vector2.attributesi)*(vector1.attributesi-vector2.attributesi);dist=sqrt(sum);return dist;/ 得到gNearestDistance中的最大距离，返回下标/int GetMaxDistance()int maxNo=0;for(int i=1;igNearestDistancemaxNo.distance)maxNo = i; return maxNo;/ 对未知样本Sample分类/char* Classify(struct dataVector Sample

10、)double dist=0;int maxid=0,freqK,i,tmpfreq=1;char *curClassLable=gNearestDistance0.classLabel;memset(freq,1,sizeof(freq);/step.1-初始化距离为最大值for(i=0;iK;i+)gNearestDistancei.distance=MAX_VALUE;/step.2-计算K-最近邻距离for(i=0;icurTrainingSetSize;i+)/step.2.1-计算未知样本和每个训练样本的距离dist=Distance(gTrainingSeti,Sample);/

11、step.2.2-得到gNearestDistance中的最大距离maxid=GetMaxDistance();/step.2.3-如果距离小于gNearestDistance中的最大距离，则将该样本作为K-最近邻样本if(distgNearestDistancemaxid.distance) gNearestDistancemaxid.ID=gTrainingSeti.ID;gNearestDistancemaxid.distance=dist;strcpy(gNearestDistancemaxid.classLabel,gTrainingSeti.classLabel);/step.3-

12、统计每个类出现的次数for(i=0;iK;i+) for(int j=0;jK;j+)if(i!=j)&(strcmp(gNearestDistancei.classLabel,gNearestDistancej.classLabel)=0)freqi+=1;/step.4-选择出现频率最大的类标号for(i=0;itmpfreq) tmpfreq=freqi; curClassLable=gNearestDistancei.classLabel;return curClassLable;/ 主函数/void main() char c; char *classLabel=;int i,j,

13、rowNo=0,TruePositive=0,FalsePositive=0;ifstream filein(iris.data);FILE *fp;if(filein.fail()coutCant open data.txt=MAX_SIZE_OF_TRAINING_SET) coutThe training set has MAX_SIZE_OF_TRAINING_SET examples!endlendl; break ;/rowNo%3!=0的100组数据作为训练数据集if(rowNo%3!=0)gTrainingSetcurTrainingSetSize.ID=rowNo;for(i

14、nt i = 0;i gTrainingSetcurTrainingSetSize.attributesi;fileinc;fileingTrainingSetcurTrainingSetSize.classLabel;curTrainingSetSize+;/剩下rowNo%3=0的50组做测试数据集else if(rowNo%3=0)gTestSetcurTestSetSize.ID=rowNo;for(int i = 0;i gTestSetcurTestSetSize.attributesi;fileinc;fileingTestSetcurTestSetSize.classLabel

15、;curTestSetSize+;filein.close();/step.2-KNN算法进行分类，并将结果写到文件iris_OutPut.txtfp=fopen(iris_OutPut.txt,w+t);/用KNN算法进行分类fprintf(fp,*程序说明*n);fprintf(fp,* 采用KNN算法对iris.data分类。为了操作方便，对各组数据添加rowNo属性,第一组rowNo=1!n);fprintf(fp,* 共有150组数据,选择rowNo模3不等于0的100组作为训练数据集，剩下的50组做测试数据集n);fprintf(fp,*nn);fprintf(fp,*实验结果*n

16、n);for(i=0;icurTestSetSize;i+) fprintf(fp,*第%d组数据*n,i+1);classLabel =Classify(gTestSeti); if(strcmp(classLabel,gTestSeti.classLabel)=0)/相等时，分类正确TruePositive+;coutrowNo:;coutgTestSeti.ID t;coutKNN分类结果: ; coutclassLabel(正确类标号: ;coutgTestSeti.classLabel)n;fprintf(fp,rowNo: %3d t KNN分类结果: %s ( 正确类标号: %s

17、 )n,gTestSeti.ID,classLabel,gTestSeti.classLabel);if(strcmp(classLabel,gTestSeti.classLabel)!=0)/不等时，分类错误/cout *分类错误*n;fprintf(fp, *分类错误*n);fprintf(fp,%d-最临近数据:n,K);for(j=0;jK;j+)/coutgNearestDistancej.IDtgNearestDistancej.distancetgNearestDistancej.classLabel15endl;fprintf(fp,rowNo: %3d t Distance:

18、 %f tClassLable: %sn,gNearestDistancej.ID,gNearestDistancej.distance,gNearestDistancej.classLabel);fprintf(fp,n); FalsePositive=curTestSetSize-TruePositive;fprintf(fp,*结果分析*n,i);fprintf(fp,TP(True positive): %dnFP(False positive): %dnaccuracy: %fn,TruePositive,FalsePositive,double(TruePositive)/(cur

19、TestSetSize-1);fclose(fp); return;四、 详细描述该算法获得的模型采用第二包数据Iris Data Set，共有150组数据,考虑到训练数据集的随机性和多样性，选择rowNo模3不等于0的100组作为训练数据集，剩下的50组做测试数据集。对未知样本进行分类（括号里的正确类标号是读取的iris.data文件里的类标号，括号外的是计算所得），本文取k=7个最邻近数据。以第19组为例进行说明，未知样本ROWNO为57，经过KNN算法分类，与之最临近的7组数据rowNo号分别为：52、86、128、139、92、64、71，其中类标号为Iris-versicolor的有

20、5个，类标号为Iris-virginica的有2个，Iris-versicolor为最多，因此据此估计该组样本的类标号为Iris-versicolor。50组测试样本运行结果如下：*程序说明* 采用KNN算法对iris.data分类。为了操作方便，对各组数据添加rowNo属性,第一组rowNo=1!* 共有150组数据,选择rowNo模3不等于0的100组作为训练数据集，剩下的50组做测试数据集*实验结果*第1组数据*rowNo: 3 KNN分类结果: Iris-setosa ( 正确类标号: Iris-setosa )7-最临近数据:rowNo: 43 Distance: 0.300000

21、ClassLable: Iris-setosarowNo: 2 Distance: 0.300000 ClassLable: Iris-setosarowNo: 4 Distance: 0.244949 ClassLable: Iris-setosarowNo: 13 Distance: 0.264575 ClassLable: Iris-setosarowNo: 7 Distance: 0.264575 ClassLable: Iris-setosarowNo: 46 Distance: 0.264575 ClassLable: Iris-setosarowNo: 10 Distance:

22、0.316228 ClassLable: Iris-setosa*第2组数据*rowNo: 6 KNN分类结果: Iris-setosa ( 正确类标号: Iris-setosa )7-最临近数据:rowNo: 22 Distance: 0.412311 ClassLable: Iris-setosarowNo: 47 Distance: 0.387298 ClassLable: Iris-setosarowNo: 11 Distance: 0.346410 ClassLable: Iris-setosarowNo: 49 Distance: 0.360555 ClassLable: Iris

23、-setosarowNo: 19 Distance: 0.331662 ClassLable: Iris-setosarowNo: 20 Distance: 0.387298 ClassLable: Iris-setosarowNo: 17 Distance: 0.400000 ClassLable: Iris-setosa*第3组数据*rowNo: 9 KNN分类结果: Iris-setosa ( 正确类标号: Iris-setosa )7-最临近数据:rowNo: 14 Distance: 0.346410 ClassLable: Iris-setosarowNo: 2 Distance:

24、 0.509902 ClassLable: Iris-setosarowNo: 4 Distance: 0.300000 ClassLable: Iris-setosarowNo: 13 Distance: 0.424264 ClassLable: Iris-setosarowNo: 46 Distance: 0.424264 ClassLable: Iris-setosarowNo: 31 Distance: 0.489898 ClassLable: Iris-setosarowNo: 43 Distance: 0.316228 ClassLable: Iris-setosa*第4组数据*r

25、owNo: 12 KNN分类结果: Iris-setosa ( 正确类标号: Iris-setosa )7-最临近数据:rowNo: 31 Distance: 0.300000 ClassLable: Iris-setosarowNo: 25 Distance: 0.300000 ClassLable: Iris-setosarowNo: 40 Distance: 0.316228 ClassLable: Iris-setosarowNo: 50 Distance: 0.300000 ClassLable: Iris-setosarowNo: 7 Distance: 0.300000 Clas

26、sLable: Iris-setosarowNo: 8 Distance: 0.223607 ClassLable: Iris-setosarowNo: 10 Distance: 0.346410 ClassLable: Iris-setosa*第5组数据*rowNo: 15 KNN分类结果: Iris-setosa ( 正确类标号: Iris-setosa )7-最临近数据:rowNo: 34 Distance: 0.412311 ClassLable: Iris-setosarowNo: 17 Distance: 0.469042 ClassLable: Iris-setosarowNo:

27、 11 Distance: 0.583095 ClassLable: Iris-setosarowNo: 37 Distance: 0.591608 ClassLable: Iris-setosarowNo: 16 Distance: 0.547723 ClassLable: Iris-setosarowNo: 49 Distance: 0.655744 ClassLable: Iris-setosarowNo: 19 Distance: 0.556776 ClassLable: Iris-setosa*第6组数据*rowNo: 18 KNN分类结果: Iris-setosa ( 正确类标号:

28、 Iris-setosa )7-最临近数据:rowNo: 1 Distance: 0.100000 ClassLable: Iris-setosarowNo: 40 Distance: 0.173205 ClassLable: Iris-setosarowNo: 29 Distance: 0.173205 ClassLable: Iris-setosarowNo: 5 Distance: 0.173205 ClassLable: Iris-setosarowNo: 41 Distance: 0.141421 ClassLable: Iris-setosarowNo: 8 Distance: 0

29、.200000 ClassLable: Iris-setosarowNo: 28 Distance: 0.173205 ClassLable: Iris-setosa*第7组数据*rowNo: 21 KNN分类结果: Iris-setosa ( 正确类标号: Iris-setosa )7-最临近数据:rowNo: 49 Distance: 0.374166 ClassLable: Iris-setosarowNo: 37 Distance: 0.424264 ClassLable: Iris-setosarowNo: 11 Distance: 0.360555 ClassLable: Iris

30、-setosarowNo: 29 Distance: 0.360555 ClassLable: Iris-setosarowNo: 28 Distance: 0.300000 ClassLable: Iris-setosarowNo: 40 Distance: 0.360555 ClassLable: Iris-setosarowNo: 32 Distance: 0.282843 ClassLable: Iris-setosa*第8组数据*rowNo: 24 KNN分类结果: Iris-setosa ( 正确类标号: Iris-setosa )7-最临近数据:rowNo: 40 Distanc

31、e: 0.374166 ClassLable: Iris-setosarowNo: 26 Distance: 0.447214 ClassLable: Iris-setosarowNo: 44 Distance: 0.264575 ClassLable: Iris-setosarowNo: 28 Distance: 0.424264 ClassLable: Iris-setosarowNo: 32 Distance: 0.387298 ClassLable: Iris-setosarowNo: 8 Distance: 0.387298 ClassLable: Iris-setosarowNo:

32、 50 Distance: 0.435890 ClassLable: Iris-setosa*第9组数据*rowNo: 27 KNN分类结果: Iris-setosa ( 正确类标号: Iris-setosa )7-最临近数据:rowNo: 1 Distance: 0.316228 ClassLable: Iris-setosarowNo: 50 Distance: 0.300000 ClassLable: Iris-setosarowNo: 41 Distance: 0.331662 ClassLable: Iris-setosarowNo: 44 Distance: 0.223607 Cl

33、assLable: Iris-setosarowNo: 40 Distance: 0.244949 ClassLable: Iris-setosarowNo: 8 Distance: 0.223607 ClassLable: Iris-setosarowNo: 28 Distance: 0.316228 ClassLable: Iris-setosa*第10组数据*rowNo: 30 KNN分类结果: Iris-setosa ( 正确类标号: Iris-setosa )7-最临近数据:rowNo: 31 Distance: 0.141421 ClassLable: Iris-setosarow

34、No: 38 Distance: 0.264575 ClassLable: Iris-setosarowNo: 4 Distance: 0.173205 ClassLable: Iris-setosarowNo: 13 Distance: 0.316228 ClassLable: Iris-setosarowNo: 7 Distance: 0.316228 ClassLable: Iris-setosarowNo: 35 Distance: 0.264575 ClassLable: Iris-setosarowNo: 10 Distance: 0.264575 ClassLable: Iris

35、-setosa*第11组数据*rowNo: 33 KNN分类结果: Iris-setosa ( 正确类标号: Iris-setosa )7-最临近数据:rowNo: 34 Distance: 0.346410 ClassLable: Iris-setosarowNo: 22 Distance: 0.509902 ClassLable: Iris-setosarowNo: 11 Distance: 0.458258 ClassLable: Iris-setosarowNo: 49 Distance: 0.424264 ClassLable: Iris-setosarowNo: 47 Distan

36、ce: 0.346410 ClassLable: Iris-setosarowNo: 20 Distance: 0.374166 ClassLable: Iris-setosarowNo: 17 Distance: 0.458258 ClassLable: Iris-setosa*第12组数据*rowNo: 36 KNN分类结果: Iris-setosa ( 正确类标号: Iris-setosa )7-最临近数据:rowNo: 38 Distance: 0.346410 ClassLable: Iris-setosarowNo: 2 Distance: 0.300000 ClassLable:

37、 Iris-setosarowNo: 41 Distance: 0.331662 ClassLable: Iris-setosarowNo: 35 Distance: 0.346410 ClassLable: Iris-setosarowNo: 29 Distance: 0.346410 ClassLable: Iris-setosarowNo: 50 Distance: 0.223607 ClassLable: Iris-setosarowNo: 10 Distance: 0.346410 ClassLable: Iris-setosa*第13组数据*rowNo: 39 KNN分类结果: I

38、ris-setosa ( 正确类标号: Iris-setosa )7-最临近数据:rowNo: 13 Distance: 0.424264 ClassLable: Iris-setosarowNo: 46 Distance: 0.424264 ClassLable: Iris-setosarowNo: 4 Distance: 0.300000 ClassLable: Iris-setosarowNo: 14 Distance: 0.244949 ClassLable: Iris-setosarowNo: 7 Distance: 0.469042 ClassLable: Iris-setosarowNo: 31 Distance: 0.5099