KNN KNN原理： K最近邻（KNN）算法核心思想是如果一个样本在特征空间中的k个最临近的样本中的大多数属于某一个类别，则该样本也属于这个类别。K通常是不大于20的整数。 最重要的三点就是：k值的选取，距离度量的方式和分类决策规则。 规则：分类决策规则一般使用多数表决法。即如果一个样本在特征空间中的k个最相似（即特征空间中最邻近）的样本中的大多数属于某一个类别，则该样本也属于这个类别 过程： 输入训练集数据和标签，输入测试数据； 计算测试数据与各个训练数据之间的距离； 按照距离的递增关系进行排序，选取距离最小的K个点； 确定前K个点所在类别的出现频率，返回前K个点中出现频率最高的类别作为测试数据的预测分类。
算法步骤： 1初始化距离为最大值 2计算未知样本和每个训练样本的距离dist 3得到目前K个最近邻样本中最大距离maxdist 4如果dist小于maxdist,则将该训练样本作为K-最近邻样本 5重复步骤2，3，4，直到未知样本和所有训练样本的距离都算完 6统计K个最近邻样本中每个类别出现的次数 7选择出现频率最大的类别作为未知样本的类别；
#include<stdio.h> #include<math.h> #include<stdlib.h> #define K 3 //近邻数k typedef float type; //动态创建二维数组 type **createarray(int n,int m) { int i; type **array; array=(type **)malloc(n*sizeof(type )); array[0]=(type )malloc(nmsizeof(type)); for(i=1;i<n;i++) array[i]=array[i-1]+m; return array; } //读取文本中数据，要求首行格式为 N=数据量,D=维数 void loaddata(int *n,int *d,type ***array,type ***karray) { int i,j; FILE *fp; if((fp=fopen(“C:\Users\杨素素\Desktop\data.txt”,“r”))NULL) fprintf(stderr,“can not open data.txt!\n”); if(fscanf(fp,“N=%d,D=%d”,n,d)!=2) fprintf(stderr,“reading error!\n”); *array=createarray(*n,*d); *karray=createarray(2,K); for(i=0;i<*n;i++) for(j=0;j<*d;j++) fscanf(fp,"%f",&(*array)[i][j]); //读取数据 for(i=0;i<2;i++) for(j=0;j<K;j++) (*karray)[i][j]=9999.0; //默认的最大值 if(fclose(fp)) fprintf(stderr,“can not close data.txt”); } //计算欧氏距离 type computedistance(int n,type *avector,type *bvector) { int i; type dist=0.0; for(i=0;i<n;i++) dist+=pow(avector[i]-bvector[i],2); return sqrt(dist); } //冒泡排序 void bublesort(int n,type **a,int choice) { int i,j; type k; for(j=0;j<n;j++) for(i=0;i<n-j-1;i++){ if(0choice){ if(a[0][i]>a[0][i+1]){ k=a[0][i]; a[0][i]=a[0][i+1]; a[0][i+1]=k; k=a[1][i]; a[1][i]=a[1][i+1]; a[1][i+1]=k; } } else if(1==choice){ if(a[1][i]>a[1][i+1]){ k=a[0][i]; a[0][i]=a[0][i+1]; a[0][i+1]=k; k=a[1][i]; a[1][i]=a[1][i+1]; a[1][i+1]=k; } } } } //统计有序表中的元素个数 type orderedlist(int n,type *list) { int i,count=1,maxcount=1; type value; for(i=0;i<(n-1);i++) { if(list[i]!=list[i+1]) { if(count>maxcount){ maxcount=count; value=list[i]; count=1; } } else count++; } if(count>maxcount){ maxcount=count; value=list[n-1]; } return value; } int main() { int i,j,k; int D,N; //维度，数据量 type **array=NULL; //数据数组 type **karray=NULL; // K近邻点的距离及其标签 type *testdata; //测试数据 type dist,maxdist; loaddata(&N,&D,&array,&karray); testdata=(type *)malloc((D-1)*sizeof(type)); printf(“输入待分类数（ %d 个）:\n”,D-1); for(i=0;i<(D-1);i++) scanf("%f",&testdata[i]); while(1){ for(i=0;i<K;i++){ if(K>N) exit(-1); karray[0][i]=computedistance(D-1,testdata,array[i]); karray[1][i]=array[i][D-1]; } bublesort(K,karray,0); maxdist=karray[0][K-1]; //初始化k近邻数组的距离最大值 for(i=K;i<N;i++){ dist=computedistance(D-1,testdata,array[i]); if(dist<maxdist) for(j=0;j<K;j++){ if(dist<karray[0][j]){ for(k=K-1;k>j;k–){ //j后元素复制到后一位，为插入做准备 karray[0][k]=karray[0][k-1]; karray[1][k]=karray[1][k-1]; } karray[0][j]=dist; //插入到j位置 karray[1][j]=array[i][D-1]; break; //不比较karray后续元素 } } maxdist=karray[0][K-1]; } bublesort(K,karray,1); printf("\n标签: %.0f\n",orderedlist(K,karray[1])); printf(“输入待分类的数据（%d个） :\n”,D-1); for(i=0;i<(D-1);i++) scanf("%f",&testdata[i]); } return 0; }
本来先开始用的是C语言，因为对matlab不是那么熟悉，但是发现不能用鸢尾花数据，所以又做了matlab。
load fisheriris x=meas(:,3:4);%载入鸢尾花数据%
gscatter(x(:,1),x(:,2),species) legend(‘Location’,‘best’)%展示数据的分布情况% %引入新的查询点，在图上把该点标出% newpoint=[5 1.45]; line(newpoint(1),newpoint(2),‘marker’,‘x’,‘color’,‘k’,… ‘markersize’,10,‘linewidth’,2) %建立基于KD-Tree的最近零搜索模型，查询目标点附近10个最近邻的点。 md1 = KDTreeSearcher(x)
md1 =
KDTreeSearcher (具有属性):
BucketSize: 50 Distance: 'euclidean' DistParameter: [] X: [150x2 double][n,d]=knnsearch(md1,newpoint,‘k’,10); line(x(n,1),x(n,2),‘color’,[.5 .5 .5],‘marker’,‘o’,… ‘linestyle’,‘none’,‘markersize’,10) %查看最近邻的10个数据% x(n,:)
ans =
5.0000 1.5000 4.9000 1.5000 4.9000 1.5000 5.1000 1.5000 5.1000 1.6000 4.8000 1.4000 5.0000 1.7000 4.7000 1.4000 4.7000 1.4000 4.7000 1.5000tabulate(species(n))%输出分类结果 % Value Count Percent % virginica 2 20.00% % versicolor 8 80.00% %百分之80为versicolor类型，20%为virginica
使用matlab时没有计算欧式距离，采用的是k-d树来完成的最近邻点搜索。其实刚开始也不懂这个树是什么，也是查了资料才有所了解。相比于算出他们之间的欧氏距离再来比较大小来判断最近的距离要简单一点。
