最近邻分类的若干改进算法研究.pdf

硕士论文 最近邻分类的若干改进算法研究目 录摘 要．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．…．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．IAbstract．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．…．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．…．．．．．．．．．．．．．．．．．．．．．…．．．II目j录．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．IHl绪论．…．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．…．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．…．．．．．．．．11．1模式分类的研究意义……………………………………………………………11．1．1模式分类的地位…………………………………………………………．11．1．2分类算法的应用…………………………………………………………．．31．2模式分类算法综述………………………………………………………………。

51．2．1贝叶斯分类方法……………………………………………………………51．2．2支持向量机分类方法……………………………………………………．51．2．3最近邻分类方法…………………………………………………………．61．2．4多种分类方法融合方法…………………………………………………．81．3本文研究工作概述………………………………………………………………．81．4本文的内容安排…………………………………………………………………．82最近邻分类的改进算法……………………………………………………………．．112．1引言………………………………………………………………………………………………………．112．2目前基于最近邻的改进算法…………………………………………………．．1l2．2．1基于稀疏表示的KNN改进算法………………………………………112．2．2基于中心的KNN改进算法……………………………………………1 32．2．3基于SVM的KNN改进算法…………………………………………．．1 52．2．4基于属性值的KNN改进算法…………………………………………172．2．5基于特征加权的改进算法………………………………………………1 82．2．6布尔序列的一种KNN改进算法………………………………………182．3本章小结………………………………………………………………………．．193 K．最近邻均值算法………………………………………………………………………．213．1引言………………………………………………………………………………………………………．2 1．3．2传统Ⅺ呵N及其不足……………………………………………………………213．2．1 K．最近邻算法……………………………………………………………2l3．2．2 K-最近邻的不足…………………………………………………………223．3局部均值算法……………………………………………………………………233．4 K．最近邻均值算法………………………………………………………………24III目录 硕士论文3．5 K．最近邻均值算法的优点………………………………………………………253．6试验与分析………………………………………………………………………263．6．1引言……………………………………………………………………………………………．263．6．2在NUST603HW上的试验………………………………………………263．6．3在CENPARMI上的试验………………………………………………293．6．4试验分析…………………………………………………………………323．7本章小结…………………………………………………………………………334 K_最近邻回归分类算法…………………………………………………………………354．1引言………………………………………………………………………………………………………．354．2最近邻线、最近邻面算法……………………………………………………。

354．3最近邻子空间算法……………………………………………………………．．364．4线性回归分类算法……………………………………………………………384．5 K．最近邻回归分类算法…………………………………………………………384．6试验与分析………………………………………………………………………394．6．1引言……………………………………………………………………………………………394．6．2在Yale B上的试验………………………………………………：……一394．6．3在FKP上的试验…………………………………………………………414．6．4在AR上的试验…………………………………………………………424．6．5在ORL上的试验…………………………………………………………434．6．6试验分析…………………………………………………………………444．7本章小结…………………………………………………………………………455全文总结与展望………………………………………………………………………．475．1工作总结…………………………………………………………………………475．2工作展望…………………………………………………………………………47垂i[ 谢。

．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．49参考文献…………………………………………………………………………………………51附j录．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．55IV硕士论文 最近邻分类的若干改进算法研究1绪论1．1模式分类的研究意义1．1．1模式分类的地位随着科学技术的发展，模式识别已经成为人们日常生活中经常用到的技术手段从1940年代计算机的出现，到1950年代人工智能的崛起，人们越来越多的使用计算机的智能功用来代替人脑模式识别(Pattem Recognition)是指对表征事物或现象的各种形式的(数值的、文字的和逻辑关系的)信息进行处理和分析，以对事物或现象进行描述、辨认、分类和解释的过程，是信息科学和人工智能的重要组成部分Lll有两种基本的模式识别方法，即统计模式识别方法和结构(句法)模式识别方法，与此相对应的模式识别系统都有两个过程所组成，即设计和实现；设计是指用一定数量的样本(nq做训练集或学习集)进行分类器的设计，实现是指用所设计的分类器对待识别的样本进行分类决策【2】。

通常我们研究的都是基于统计方法的模式识别系统，其基本过程如下：将研究对象经过测量和量化，变成计算机可以计算的符号，比如矩阵或向量然后经过预处理，其目的是去除噪声，加强有用信息并且对于输入或者其他因素造成的干扰进行修复接着对测量空间进行变换，抽取最能反映分类特征的维数较低的特征空间最后利用统计方法确定的判决规则把被识别样本进行分类，使得错误识别率最小具体主要有4个部分组成：数据获取，预处理，特征提取和选择，分类决策【l】，如下图所示图1．1模式识别的组成l绪论 硕士论文下面简单说明下各个部分1．信息获取我们使用计算机能够计算的符号去表示所研究的事物，以便它对所研究的各种对象能够进行分类识别一般情况下，有以下三种输入对象的信息类型：(1)二维图像：如文字，指纹，地图，照片等2)一维波形：如脑电图，心电图，机械振动波形等3)物理参量和逻辑值：物理参量比如在工业生产中产品的大小和各种属性数据等；逻辑值比如对于某个指标是否合格的判断或者对于具体特征的描述，例如是否需要外包装，是否易碎等，可用逻辑值0来表示“是”且用1来表示“否”现在很多系统中，也引入了模糊逻辑的概念，除了0和1之外还可以使用模糊逻辑值来表示，例如有点疼，特别疼等等。

为了使机器(也包括人)能够辨认，我们通过测量采样和量化，把二维图像或者一维波形用矩阵或向量表示这就是信息获取的过程2．预处理对原始数据进行预处理是为了降低其噪声，突出加强有用的信息，在数据获取时，经常出现一些退化现象(例如输A．澳JJ量仪器的不精确或者其他因素所造成的影响)，预处理就是对这些退化现象进行复原，为下面的特征抽取和分类做准备，以便获得更好的结果这就是预处理的过程3．特征提取和选择一般待测对象的数据量是比较大的，常常动辄几千个、几万个，甚至上百万个数据，如果直接对这些数据进行识别，效率显然会比较低为了更加有效的进行分类识别，我们只抽取得到最能反映分类本质的特征，利用这些特征就代替原始数据进行识别这就是特征提取和选择的过程目前比较主流的方法基本上都是基于整体的特征提取方法，例如主分量分析法(PCA，又称为K-L变化)，线性鉴别分析(LDA)方法，基于独立分量分析(ICA)的方法，基于神经网络的方法等等4．分类决策在特征抽取和选择之后，在特征空间确定某个判别规则，这个规则通常是用统计的方法，根据规则把被识别对象归为某一类别，其基本做法是：在经过特征抽取的样本训练集上，对待测样本进行分类，利用某个分类判别规则使得误分类率尽可能的小。

这就是分类决策的过程随着模式识别的应用不断加深扩宽，对其研究的热潮也在随之升温模式分类作为模式识别中的一个重要环节，一直以来都是学者们重点研究的对象模式分类是一种机器学习程序，因此归为人工智能的范畴中人工智能的多个领域，包括数据挖掘，专家系统，模式识别都用到此类程序分类算法的好坏，直接影响着分类的正确率及时间空2硕+论文 最近邻分类的若f：改进算法研究间效率因此，对于分类算法的研究更加显得必要1．1．2分类算法的应用在1960年代以前，模式识别更多地贡献在以统计学为主的理论研究计算机诞生后，模式识别实际应用的能力不断增强，从而促进了分类算法的发展和应用经过多年的研究和发展，分类算法己广泛被应用于各个方面：比如智能系统、计算机视觉、生物信息学、海洋探测、航空航天技术、工业生产、安全监控、科学理论研究等许多重要领域分类算法的不断创新改进，使得人们的生活生产都得到了切实的促进，从而提高了国家的整体经济国防实力分类算法应用广泛，下面介绍几种比较流行的应用，图1．2依次为字符识别、语音识别、人脸识别、指纹识别、细胞识别和掌纹识别图1．2儿种常见的分类应用1字符识别字符识别是分类算法应用的重要分支，处理的信息可分为两大类：第一类是印刷体字符识别，主要处理各种印刷字体，包括汉语、英语、R语、韩语、阿拉伯数字等各个国家民族的语言和文字，由于印刷体字符识别发展时间较长，目前使用的技术也比较完善，市面上已有不少趋于成熟的应用系统；另一类是手写体字符识别，典型的商业应用如银行支票的识别，邮政编码的识别，及统计报表、财务报表的识别等等，这满足了人类技能接口的需求，同时也获得了巨大的商业利益。

2语音识别1绪论 硕十论文语音识别是分类算法的另一个研究领域语言是人类最普遍的沟通交流方式，因此，能够建立语音识别的智能机器将会带来莫大的便利与利益近几年来，生物识别技术领域不断发展，人们对日常生活和工作中的安全要求也不断提高，将语音识别应用到需要门禁监控，人员验证的场景中，不仅提供了准确便捷的安全保证，也节省了人力成。