基于K近邻法的分类器的设计与实现.doc

基于K近邻法的分类器的设计与实现 王芳 （天津师范大学计算机与信息工程学院，中国天津300387） 【摘要】模式识别的目的就是对的样本，判断它所在的类别。人类的模式识别能力使得人们可以很好的认识周围的环境并与之交流。分类器是模式识别系统的重要组成部分；也是机器学习的重要研究领域。 关键词模式识别；分类器 1近邻分类器 1.1算法原理 ）分类问题的两大类基本方法 （）决策域/判别函数：利用判别函数或决策面方程将特征空间划分成决策域 （）模板匹配：将待分类样本与标准模板进行比较，根据与各类别模板的匹配度情况，确定测试样本的类别 近邻法属于典型的模板匹配方法也是基于样本直接设计的非线性分类器 ）最小距离分类器： （）将各类训练样本划分若干子类，并在每个子类中确定代表点，一般用子类的质心或邻近质心的某一样本作为代表点，测试样本的类别则以这些代表点的距离最近作决策。 （）当选择的代表点不一定能很好地代表各类时，错误率增加 ）最近邻分类器(NNC-NearestNeighborClassifier) 基本思想：以全部训练样本为代表点，计算测试样本与这些代表点，即所有样本的距离，并以最近者的类别作为决策。 （）Cover和Hart于1968年提出，非参数法中最重要的方法之一 （）可以理解为最小距离分类器的一种极端情况 （）从模板匹配的角度理解：将训练样本集中的每个样本都作为模板，用测试样本与每个模板做比较，看与哪个模板最相似(即为近邻)，按最相似模板的类别作为自己的类别 （）最近邻决策规则： 对于C类模式识别问题i，i=1，2，3，4C，各类有Ni个训练样本。 （）缺点：近邻法的缺点：存储量大，计算量大 1.2算法实现 本分类器采用的是UCI机器学习数据集中的Letter_Recognition。这个数据集中一共有20000个样本，根据前人经验，该分类器的设计取前16000个样本作为训练样本，将得到的运算结果模型用于预测剩下的4000个样本的分类情况。 本程序的设计采用的是C语言，是在MicrosoftVisualStudioxx这个开发环境下进行的。MicrosoftVisualStudioxx是对MicrosoftVisualStudioxx版本的升级，适用于win7、vista等操作系统。 VisualStudioxx的语言更加的简洁，使用起来更加的方便。同时VSxx还提供了很多其他开发软件不具有的高级的开发工具，可以帮助开发者提高开发程序的效率，开发出更有价值的程序。 （1）数据的读入和存储 定义了结构体SAMPLE用来存放读入的样本集；利用整型二维数组testWangFang_TSIZE16存放读入的测试样本；利用pareWangFang_TSIZE数组存放测试样本的正确分类情况，为正确率的计算做准备。由于样本的数量较大，采用文件的方式进行数据的读入与存储。 structSAMPLE charwf_classlabel; intwf_attribute16;/*已知特征向量为位*/ ; typedefstructSAMPLESAMPLE; SAMPLEsampleWangFang_SSIZE;/*样本集*/ inttestWangFang_TSIZE16;/*测试集*/ charpareWangFang_TSIZE;/*对比集*/ （2）计算测试样本到每个已知类别样本的距离 距离的计算采用的是n维空间的欧氏距离公式。n维欧氏空间是一个点集,它的每个点X可以表示为(x1，x2，xn)，其中xi(i=1，2，n)是实数，称为X的第i个坐标，两个点A=(a1，a2，an)和B=(b1，b2，bn)之间的距离d(A，B)定义为下面的公式： d(A，B)=sqrt(ai-bi)2)(i=1，2，n) 部分代码如下： doubledistance(structSAMPLEm,intn16) inti; doubledd; doublesum=0.0; for(i=0;i16;i+)sum+=(m.wf_attributei-ni)*(m.wf_attributei-ni); dd=sqrt(sum); returndd; （3）寻找最小距离并分类 对于某一测试样本，一次计算他与各个样本的距离，存入数组dSSIZE，设一个最小距离dmin，dmin的初始值设为d0，一次用dmin和di比较，如果di大于dmin，则将其值存入dmin，并记录标号i。 （4）计算正确率 将测试集的分类结果和数组pare的内容比较，计算正确率。部分代码如下： doubleAuracy(charaWangFang_TSIZE) inti; doublej; intsum=0; for(i=0;i j=(double)sum/WangFang_TSIZE; returnj; （5）执行结果的输出，把程序的执行结果输出到putout.txt中。 1.3运行结果 由于采用的是文件输入输出，因而详细结果在文件中显示。见putout.txt文档。 2结论 经历了数月的设计，基本实现了K-近邻算法的分类器，并且对数据测试结果表明：基本实现了预定目标，达到分类的效果。 K-近邻分类算法具有主观性，因为必须定义一个距离尺度，由于对距离的理解还不是深刻的，而分类的结果完全依赖使用的距离，这样对于用一组数据，两个不同的分类算法会产生两种完全不同的分类结果，一般需要专家来评测结果是否有效。由于对