论文部分内容阅读
【摘要】
决策树和基于规则的分类器是积极学习方法例子，消极学习的一个例子rote分类器，它记住整个训练数据，仅当测试实例的属性和某个训练样例完全配对时才进行分类。该方法的一个明显缺点是有些测试记录不能被分类，因为没有任何训练样例与它们匹配。使该方法更为灵活的一个途径是找出和测试样例的属性相对接近的所有训练样例，这些训练样例称为最近邻，可以用来确定测试样例的类标号，下面来进一步研究这个备受关注，同时又灵活有意义的消极学习方法例子——k-最近邻分类器，它是分类器算法中最通俗易懂的一种。
【关键字】
k-最近邻分类器 算法 MATLAB
一、算法思想与原理
最近分类器把每一个样例看作d维空间上的一个数据点，其中d是属性个数。给定一个测试样例，我们使用任意一种邻近性度量，计算该测试样例与训练集中其它数据点的邻近度。给定样例z的k-最近邻是指和z最近的k个数据点。通过数据点的的1-最邻近、2-最邻近和3-最邻近，得知选择k的重要性：如果k太小，则最近邻分类器很容易受到由于训练数据中的噪声而产生的过分拟合的影响，如果k太大，最近邻分类器可能会误分类测试样例，因为最近邻表中可能包含远离其邻近的数据点。
k-最近邻分类器算法的原理是通过计算测试样本到各训练样本的距离，取其中最小的K个，并根据这K个训练样本的标记进行投票得到测试样本的标记。
二、算法设计与实现
运行环境：Windows和MATLAB软件环境。
关键算法：
function ceshi_knn
k=10；
kk=zeros（k，1）；
sz_z=100；
x11=rand（sz_z，1）；
x12=rand（sz_z，1）；
x1=[x11 x12]；
y1=ones（sz_z，1）；
sz_f=100；
x21=rand（sz_f，1）+1；
x22=rand（sz_f，1）；
x2=[x21 x22]；
y2=-1*ones（sz_f，1）；
x=[x1；x2]；
y=[y1；y2]；
sz_c=20；
test1=rand（sz_c，1）+0.5；
test2=rand（sz_c，1）；
test=[test1 test2]；
for sz=1： sz_c
for m=1：（sz_z+ sz_f）
dis（m）=（test（sz，1）-x（m，1））^2+（test（sz，2）-x（m，2））^2；
end
for h=1：k
near（h）=10^5；
end
for m=1：（sz_z+sz_f）
for h=1：k
if dis（m） near（h）=dis（m）；
kk（h）=y（m）；
for t=h：k
near（t+1）=near（t）；
end
break
end
end
end
sum=0；
for a=1：k
sum=kk（a）+sum；
end
y_test（sz）=sign（sum）；
end
for m=1：（sz_z+sz_f）
if y（m）>0
plot（x（m，1），x（m，2），'r+'）；
hold on
else
plot（x（m，1），x（m，2），'b.'）；
hold on
end
end
for m=1：sz_c
if y_test（m）>0
plot（test（m，1），test（m，2），'g+'）；
title（'K-最近邻分类器'）；
hold on
else
plot（test（m，1），test（m，2），'y.'）；
hold on
end
end
三、实验结果分析
对于这个实验，使用不同的k值，进行测试，得出如下的结果：k-最近邻分类器算法的思路清晰简单，易于理解和实现的数据分类技术，可以在很多环境下很好的运行，在k值选取合适时算法的性能会达到最优，存在的误差会很小。
四、总结
优点：k-最近邻分类器算法的思路清晰简单，易于理解和实现的数据分类技术，可以在很多环境下很好的运行。
缺点：首先，当数据集不平衡即某个类在数据集中的对象容量很大，而其他对象容量很小时，有可能导致当输入一个新对象时，该对象的k个邻居中大容量类的对象占多数，因此可以采用不同的类添加权值的方法来改进，例如和该对象距离小的邻居权值大；其次对于海量数据计算量过大，每个训练样本都有一个距离必须度量，耗费大量时间。
【参考文献】
[1]pang-ning tan Michael Steinbach.数据挖掘导论.人民邮电出版社，2011.1.
[2]张宇.K-近邻算法的改进与实现[J].电脑开发与应用，2008，19（2）：22-24.
[3]梁循.数据挖掘算法与应用[M].北京大学出版社，2006：31-33.
[4]A.Asuncion and D.Newman.UCI Machine Learning Repository[M].2007.
决策树和基于规则的分类器是积极学习方法例子，消极学习的一个例子rote分类器，它记住整个训练数据，仅当测试实例的属性和某个训练样例完全配对时才进行分类。该方法的一个明显缺点是有些测试记录不能被分类，因为没有任何训练样例与它们匹配。使该方法更为灵活的一个途径是找出和测试样例的属性相对接近的所有训练样例，这些训练样例称为最近邻，可以用来确定测试样例的类标号，下面来进一步研究这个备受关注，同时又灵活有意义的消极学习方法例子——k-最近邻分类器，它是分类器算法中最通俗易懂的一种。
【关键字】
k-最近邻分类器 算法 MATLAB
一、算法思想与原理
最近分类器把每一个样例看作d维空间上的一个数据点，其中d是属性个数。给定一个测试样例，我们使用任意一种邻近性度量，计算该测试样例与训练集中其它数据点的邻近度。给定样例z的k-最近邻是指和z最近的k个数据点。通过数据点的的1-最邻近、2-最邻近和3-最邻近，得知选择k的重要性：如果k太小，则最近邻分类器很容易受到由于训练数据中的噪声而产生的过分拟合的影响，如果k太大，最近邻分类器可能会误分类测试样例，因为最近邻表中可能包含远离其邻近的数据点。
k-最近邻分类器算法的原理是通过计算测试样本到各训练样本的距离，取其中最小的K个，并根据这K个训练样本的标记进行投票得到测试样本的标记。
二、算法设计与实现
运行环境：Windows和MATLAB软件环境。
关键算法：
function ceshi_knn
k=10；
kk=zeros（k，1）；
sz_z=100；
x11=rand（sz_z，1）；
x12=rand（sz_z，1）；
x1=[x11 x12]；
y1=ones（sz_z，1）；
sz_f=100；
x21=rand（sz_f，1）+1；
x22=rand（sz_f，1）；
x2=[x21 x22]；
y2=-1*ones（sz_f，1）；
x=[x1；x2]；
y=[y1；y2]；
sz_c=20；
test1=rand（sz_c，1）+0.5；
test2=rand（sz_c，1）；
test=[test1 test2]；
for sz=1： sz_c
for m=1：（sz_z+ sz_f）
dis（m）=（test（sz，1）-x（m，1））^2+（test（sz，2）-x（m，2））^2；
end
for h=1：k
near（h）=10^5；
end
for m=1：（sz_z+sz_f）
for h=1：k
if dis（m）
kk（h）=y（m）；
for t=h：k
near（t+1）=near（t）；
end
break
end
end
end
sum=0；
for a=1：k
sum=kk（a）+sum；
end
y_test（sz）=sign（sum）；
end
for m=1：（sz_z+sz_f）
if y（m）>0
plot（x（m，1），x（m，2），'r+'）；
hold on
else
plot（x（m，1），x（m，2），'b.'）；
hold on
end
end
for m=1：sz_c
if y_test（m）>0
plot（test（m，1），test（m，2），'g+'）；
title（'K-最近邻分类器'）；
hold on
else
plot（test（m，1），test（m，2），'y.'）；
hold on
end
end
三、实验结果分析
对于这个实验，使用不同的k值，进行测试，得出如下的结果：k-最近邻分类器算法的思路清晰简单，易于理解和实现的数据分类技术，可以在很多环境下很好的运行，在k值选取合适时算法的性能会达到最优，存在的误差会很小。
四、总结
优点：k-最近邻分类器算法的思路清晰简单，易于理解和实现的数据分类技术，可以在很多环境下很好的运行。
缺点：首先，当数据集不平衡即某个类在数据集中的对象容量很大，而其他对象容量很小时，有可能导致当输入一个新对象时，该对象的k个邻居中大容量类的对象占多数，因此可以采用不同的类添加权值的方法来改进，例如和该对象距离小的邻居权值大；其次对于海量数据计算量过大，每个训练样本都有一个距离必须度量，耗费大量时间。
【参考文献】
[1]pang-ning tan Michael Steinbach.数据挖掘导论.人民邮电出版社，2011.1.
[2]张宇.K-近邻算法的改进与实现[J].电脑开发与应用，2008，19（2）：22-24.
[3]梁循.数据挖掘算法与应用[M].北京大学出版社，2006：31-33.
[4]A.Asuncion and D.Newman.UCI Machine Learning Repository[M].2007.