近邻分类分类器设计

《近邻分类分类器设计》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、近邻分类分类器设计一、设计任务对“data3.m”数据，采用剪辑法、压缩法生成参考集，近似描绘其决策面，并用所有数据测试其分类效果。二、设计原理1、最近邻法最近邻分类器(nearestneighborhoodclassifier,nnc):最小距离分类器的一种极端的情况，以全部训练样本作为代表点，计算测试样本与所有样本的距离，并以最近邻者的类别作为决策。最初的近邻法是由Cover和Hart于1968年提出的，随后得到理论上深入的分析与研究，是非参数法中最重要的方法之一。最近邻法：将与测试样本最近邻样本的类别作为决策的结果。对一

2、个类别问题，每类有个样本,，则第类的判别函数为：(1)因此，最近邻决策规则：若(2)则决策由上可以看出最近邻法在原理上最直观，方法上也十分简单，但明显的缺点就是计算量大，存储量大。2、-近邻法-近邻法即为最近邻法的扩展，其基本规则是，在所有个样本中找到与测试样本的个最近邻者，其中各类别所占个数表示成,，定义判别函数为：(3)因此，-近邻决策规则：若(4)则决策-近邻一般采用为奇数，跟投票表决一样，避免因两种票数相等而难以决策。决策规则为：3、改进的近邻法近邻法的一个严重问题是需要存储全部训练样本，以及繁重的距离计算量。从而提出

3、了两类改进的方法：一种是对样本集进行组织与整理，分群分层，尽可能将计算压缩到在接近测试样本邻域的小范围内，避免盲目地与训练样本集中每个样本进行距离计算。另一种则是在原有样本集中挑选出对分类计算有效的样本，使样本总数合理地减少，以同时达到既减少计算量，又减少存储量的双重效果。3.1、剪辑近邻法剪辑近邻法：其基本思想是，利用现有样本集对其自身进行剪辑，将不同类别交界处的样本以适当方式筛选，可以实现既减少样本数又提高正确识别率的双重目的。剪辑的过程是：将样本集分成两个互相独立的子集：test集和reference集。第一步：用ref

4、erence集中每一个样本对test集中的样本用近邻法进行分类。如果与不属于同一类别，则将从设计集中删除，最后得到一个剪辑的样本集（剪辑样本集），以取代原样本集，对待识别样本进行分类；第二步：用剪辑的样本集并用最近邻法对未知的样本进行分类。-近邻剪辑：与最近邻剪辑相似，第一步用-近邻法进行剪辑，得到剪辑的样本集；第二步：用剪辑的样本集并用最近邻法对未知的样本进行分类。重复剪辑近邻法：将样本集重复进行剪辑，常用的是MULTIEDIT算法：（1）、将样本集随机划分为个子集，即；（2）、用最近邻法，以为参考集，对中的样本进行分类；（

5、3）、去掉在(2)被错分类的样本；（4）、用所有留下的样本构成新的样本集；（5）、重复(1)~(5)步，直到没有样本被剪辑掉，则停止。3.2、压缩近邻法压缩近邻法：利用现有样本集，逐渐生成一个新的样本集，使该样本集在保留最少量样本的条件下，仍能对原有样本的全部用最近邻法正确分类，那末该样本集也就能对待识别样本进行分类，并保持正常识别率。压缩近邻法的步骤是：定义两个存储器，一个用来存放即将生成的样本集，称为Store；另一存储器则存放原样本集，称为Grabbag。其算法是：（1）、初始化。Store是空集，原样本集存入Grabb

6、ag；从Grabbag中任意选择一样本放入Store中作为新样本集的第一个样本。（2）、样本集生成。在Grabbag中取出第i个样本用Store中的当前样本集按最近邻法分类。若分类错误，则将该样本从Grabbag转入Store中，若分类正确，则将该样本放回Grabbag中。（3）、结束过程。若Grabbag中所有样本在执行第二步时没有发生转入Store的现象，或Grabbag已成空集，则算法终止，否则转入第二步。最后我们以Store中的样本作为最近邻法的设计集，但这时的样本数目却大大减少了，因此可大大节省存储量。三、关键程序由

7、于老师给的数据太长，故在此将其省去，详见随包所带附件，本设计的关键程序如下：%%%%%%%%%%%%%%%%%%%剪辑近邻法%%%%%%%%%%%%%%%%%%%TH=0.3;%阈值，决定考试集和参考集中数据的个数，其中考试集的个数为N*(1-TH),参考集的个数为N*THlxx1=length(x1);lxx2=length(x2);lxx=lxx1+lxx2;Y0=ones(lxx,1);Y=ones(lxx,1);X0=[x1;x2];Y0(lxx1+1:lxx)=-1;ii=1;%总共循环次数NN=1;%统计某次剪辑掉

8、多少个数据num=0;%统计一共剪辑掉多少个数据key=0;%统计一共有多少次一个数据都没有剪辑掉cishu=0;%统计剪辑次数k=1;%当k=1时即为最近邻法，反之则为k近邻法,比如当k=3时即为3近邻法fx=[];fy=[];Xmax=max(X0(:,1));Ymax=