文档介绍：第2页
K近邻分类的算法实现
K近邻（KNN）法的输入为实例的特征向量，对应于特征空间的点；输入为实例的类别，可以取多类。K近邻法假设给定一个训练数据集，其中的实例类别已定。分类时，对新的实例，根据其k个最近邻的训练实例的类别，通过测它属于在训练实例中最多的类。这时，模型过于简单，完全忽略训练实例中的大量有用信息，是不可取的。
分类决策规则
K近邻法中的分类决策规则往往是多数表决，即由输入实例的k个邻近的训练实例中的多数类决定输入实例的类。
多数表决规则有如下解释：如果分类的损失函数为0-1损失函数，分类函数为
广RnT{C1,c2，，ck}
那么误分类的概率是
P(Y丰f(X))=1-P(Y=f(X))
对给定的实例xw%,其最近邻的k个训练实例点构成集合Nk(x)。如果涵
盖N(x)的区域的类别是cj那么误分类概率是
工I(y丰c)二1-工I(y二c)
kijkij
xwN(x)xwN(x)
iKiK
工I(y=c)
要使误分类概率最小即经验风险最小，就要使xi叫(X)1j最大，所以多数iK
第6页
表决规则等价于经验风险最小化。
K近邻算法
输入：训练数据集
T二｛(X1,y"X2,y2)，…，(XN，yN)｝
其中，X"匚Rn为实例的特征向量，yiGy二｛C1,C2,…Ck｝为实例的类别，i=l,2,...,N;实例特征向量X；输出：实例x所属的类y。
⑴根据给定的距离度量，在训练集T中找出与x最邻近的k个点，涵盖这k个点的x邻域记作NK(x)；
⑵在Nk(x)中根据分类决策规则(如多数表决)决定x的类别y：y二argmax工I(y二c),i=1,2,…N;j=1,2,…,K
—叫(x)ij
该式中，I为指示函数，即当yi=Cj时I为1,否则I为0。
当k取1的特殊情况时，k近邻算法即为最近邻算法。对于输入的实例点或是特征向量x，其分类由其最邻近的点的分类决定。
第7页
第三章数据模拟和实例分析
用MATLAB随机生成150组数据，类别为三类，编程如下#程序1：
A1=rand(50,2);
holdonplot(A1(:,1),A1(:,2),'.')
A2=rand(50,2)+;
holdonplot(A2(:,1),A2(:,2),'.')
holdonA3=rand(50,2)+;
plot(A3(:,1),A3(:,2),'.')
再用k近邻分类算法对这150组数据进行分类，取k=15近邻，程序如下
#程序2：
clearall
clc
y=importdata('C:\Users\adm\Desktop\');
p=y(:,2:3);
p=p';
Add=zeros(150,1);
第8页
Add(1:50,:)=ones(50,1);
Add(51:100,:)=2*ones(50,1);
Add(101:150,:)=3*ones(50,1);
figure(1),plot(y(:,1),Add,'g.');
holdon
gridon;
count=0;
fori=1:3
forj=1:50
fork=1:150
distance(k)=mse(p(:,k)-p(:,(i-l)*50+j));%保存每个向量与所有训
练样本之间的距离
end
[dlindex1]=sort(distance);%对距离distance向量进行从小到大的排序num=[000];
form=1:20%考察num，存放的是排序后distance前20个属于每一类别的个数
ifindex1(m)<=50
num(1)=num(1)+1;
elseifindex1(m)<=100
num(2)=num(2)+1;
else
num(3)=num(3)+1;
end
end
[d2class]=max(num);%属于哪类的个数最多，就属于哪类，class即就是该向量所属的类别
ifi==class
count=count+1;
end
A((i-1)*50+j)=class;%存放判断的结果
end
end
count
rate=count/150
第9页
figure(2),plot(y(:,l),A,'r.');gridon;%画图分类
程序运行后得到count=l43rate=
图一模拟数据原始分类