最近邻分类的若干改进算法研究.pdf
《最近邻分类的若干改进算法研究.pdf》由会员分享,可在线阅读,更多相关《最近邻分类的若干改进算法研究.pdf(58页珍藏版)》请在三一文库上搜索。
1、硕士论文 最近邻分类的若干改进算法研究 目录 摘要I A b s t r a c t I I 目j 录I H l 绪论1 1 1 模式分类的研究意义1 1 1 1 模式分类的地位1 1 1 2 分类算法的应用3 1 2 模式分类算法综述。5 1 2 1 贝叶斯分类方法5 1 2 2 支持向量机分类方法5 1 2 3 最近邻分类方法6 1 2 4 多种分类方法融合方法8 1 3 本文研究工作概述8 1 4 本文的内容安排8 2 最近邻分类的改进算法1 1 2 1 引言1 1 2 2 目前基于最近邻的改进算法1 l 2 2 1 基于稀疏表示的K N N 改进算法1 1 2 2 2 基于中心的K N
2、 N 改进算法13 2 2 3 基于S V M 的K N N 改进算法15 2 2 4 基于属性值的K N N 改进算法1 7 2 2 5 基于特征加权的改进算法18 2 2 6 布尔序列的一种K N N 改进算法1 8 2 3 本章小结1 9 3K 最近邻均值算法2 1 3 1 引言21 3 2 传统呵N 及其不足2 1 3 2 1K 最近邻算法2 l 3 2 2K - 最近邻的不足2 2 3 3 局部均值算法2 3 3 4K 最近邻均值算法2 4 I I I 目录硕士论文 3 5K 最近邻均值算法的优点2 5 3 6 试验与分析2 6 3 6 1 引言2 6 3 6 2 在N U S T
3、6 0 3 H W 上的试验2 6 3 6 3 在C E N P A R M I 上的试验2 9 3 6 4 试验分析3 2 3 7 本章小结3 3 4K _ 最近邻回归分类算法3 5 4 1 引言3 5 4 2 最近邻线、最近邻面算法。3 5 4 3 最近邻子空间算法3 6 4 4 线性回归分类算法。3 8 4 5K 最近邻回归分类算法3 8 4 6 试验与分析3 9 4 6 1 引言。3 9 4 6 2 在Y a l eB 上的试验:一3 9 4 6 3 在F K P 上的试验4 1 4 6 4 在A R 上的试验4 2 4 6 5 在O R L 上的试验4 3 4 6 6 试验分析4 4
4、 4 7 本章小结4 5 5 全文总结与展望4 7 5 1 工作总结4 7 5 2 工作展望4 7 垂i 谢。4 9 参考文献5 1 附j 录5 5 I V 硕士论文 最近邻分类的若干改进算法研究 1 绪论 1 1 模式分类的研究意义 1 1 1 模式分类的地位 随着科学技术的发展,模式识别已经成为人们日常生活中经常用到的技术手段。从 1 9 4 0 年代计算机的出现,到1 9 5 0 年代人工智能的崛起,人们越来越多的使用计算机的 智能功用来代替人脑。 模式识别( P a t t e mR e c o g n i t i o n ) 是指对表征事物或现象的各种形式的( 数值的、文字的 和逻辑
5、关系的) 信息进行处理和分析,以对事物或现象进行描述、辨认、分类和解释的 过程,是信息科学和人工智能的重要组成部分L l l 。 有两种基本的模式识别方法,即统计模式识别方法和结构( 句法) 模式识别方法,与 此相对应的模式识别系统都有两个过程所组成,即设计和实现;设计是指用一定数量的 样本( n q 做训练集或学习集) 进行分类器的设计,实现是指用所设计的分类器对待识别的 样本进行分类决策【2 】。 通常我们研究的都是基于统计方法的模式识别系统,其基本过程如下:将研究对象 经过测量和量化,变成计算机可以计算的符号,比如矩阵或向量。然后经过预处理,其 目的是去除噪声,加强有用信息并且对于输入或
6、者其他因素造成的干扰进行修复。接着 对测量空间进行变换,抽取最能反映分类特征的维数较低的特征空间。最后利用统计方 法确定的判决规则把被识别样本进行分类,使得错误识别率最小。 具体主要有4 个部分组成:数据获取,预处理,特征提取和选择,分类决策【l 】,如 下图所示。 图1 1 模式识别的组成 l 绪论硕士论文 下面简单说明下各个部分。 1 信息获取 我们使用计算机能够计算的符号去表示所研究的事物,以便它对所研究的各种对象 能够进行分类识别。一般情况下,有以下三种输入对象的信息类型: ( 1 ) 二维图像:如文字,指纹,地图,照片等。 ( 2 ) 一维波形:如脑电图,心电图,机械振动波形等。 (
7、 3 ) 物理参量和逻辑值:物理参量比如在工业生产中产品的大小和各种属性数据 等;逻辑值比如对于某个指标是否合格的判断或者对于具体特征的描述,例如是否需要 外包装,是否易碎等,可用逻辑值0 来表示“是”且用1 来表示“否”。现在很多系统中, 也引入了模糊逻辑的概念,除了0 和1 之外还可以使用模糊逻辑值来表示,例如有点疼, 特别疼等等。为了使机器( 也包括人) 能够辨认,我们通过测量采样和量化,把二维图像 或者一维波形用矩阵或向量表示。这就是信息获取的过程。 2 预处理 对原始数据进行预处理是为了降低其噪声,突出加强有用的信息,在数据获取时, 经常出现一些退化现象( 例如输A 澳J J 量仪器
8、的不精确或者其他因素所造成的影响) ,预处 理就是对这些退化现象进行复原,为下面的特征抽取和分类做准备,以便获得更好的结 果。这就是预处理的过程。 3 特征提取和选择 一般待测对象的数据量是比较大的,常常动辄几千个、几万个,甚至上百万个数据, 如果直接对这些数据进行识别,效率显然会比较低。为了更加有效的进行分类识别,我 们只抽取得到最能反映分类本质的特征,利用这些特征就代替原始数据进行识别。这就 是特征提取和选择的过程。 目前比较主流的方法基本上都是基于整体的特征提取方法,例如主分量分析法 ( P C A ,又称为K - L 变化) ,线性鉴别分析( L D A ) 方法,基于独立分量分析(
9、I C A ) 的方法,基于神经网络的方法等等。 4 分类决策 在特征抽取和选择之后,在特征空间确定某个判别规则,这个规则通常是用统计的 方法,根据规则把被识别对象归为某一类别,其基本做法是:在经过特征抽取的样本训 练集上,对待测样本进行分类,利用某个分类判别规则使得误分类率尽可能的小。这就 是分类决策的过程。 随着模式识别的应用不断加深扩宽,对其研究的热潮也在随之升温。模式分类作为 模式识别中的一个重要环节,一直以来都是学者们重点研究的对象。模式分类是一种机 器学习程序,因此归为人工智能的范畴中。人工智能的多个领域,包括数据挖掘,专家 系统,模式识别都用到此类程序。分类算法的好坏,直接影响着
10、分类的正确率及时间空 2 硕+ 论文最近邻分类的若f :改进算法研究 间效率。因此,对于分类算法的研究更加显得必要。 1 1 2 分类算法的应用 在1 9 6 0 年代以前,模式识别更多地贡献在以统计学为主的理论研究。计算机诞生 后,模式识别实际应用的能力不断增强,从而促进了分类算法的发展和应用。经过多年 的研究和发展,分类算法己广泛被应用于各个方面:比如智能系统、计算机视觉、生物 信息学、海洋探测、航空航天技术、工业生产、安全监控、科学理论研究等许多重要领 域。分类算法的不断创新改进,使得人们的生活生产都得到了切实的促进,从而提高了 国家的整体经济国防实力。 分类算法应用广泛,下面介绍几种比
11、较流行的应用,图1 2 依次为字符识别、语音 识别、人脸识别、指纹识别、细胞识别和掌纹识别。 图1 2 儿种常见的分类应用 1 字符识别 字符识别是分类算法应用的重要分支,处理的信息可分为两大类:第一类是印刷体 字符识别,主要处理各种印刷字体,包括汉语、英语、R 语、韩语、阿拉伯数字等各个 国家民族的语言和文字,由于印刷体字符识别发展时间较长,目前使用的技术也比较完 善,市面上已有不少趋于成熟的应用系统;另一类是手写体字符识别,典型的商业应用 如银行支票的识别,邮政编码的识别,及统计报表、财务报表的识别等等,这满足了人 类技能接口的需求,同时也获得了巨大的商业利益。 2 语音识别 1 绪论 硕
12、十论文 语音识别是分类算法的另一个研究领域。语言是人类最普遍的沟通交流方式,因此, 能够建立语音识别的智能机器将会带来莫大的便利与利益。近几年来,生物识别技术领 域不断发展,人们对日常生活和工作中的安全要求也不断提高,将语音识别应用到需要 门禁监控,人员验证的场景中,不仅提供了准确便捷的安全保证,也节省了人力成本增 加经济效益,因此越来越受到人们的关注。 3 人脸识别 人脸识别可谓分类算法应用的重要组成部分。人脸识别技术是一门多学科交叉的技 术,它涉及到计算机视觉、图像处理、模式识别、心理学、生理学、人工神经网络等多 个研究领域。人脸识别技术是以计算机为辅助手段,将静态图像或视频图像和数据库中
13、 的人脸图像进行对比,从中识别出对应的人脸,从而达到身份识别的最终目的。目前广 泛应用于智能门禁,安检系统等。 4 指纹识别 指纹识别是分类算法继人脸识别之后又一新的应用。人的皮肤有三部分组成,分别 是表皮、真皮和皮下组织。指纹就是表皮上突起的纹线,总体可以划分成如下几种类型: 一种叫斗形纹,另一种叫箕形纹,还有弓线纹等等。世界上没有指纹完全相同的两个人, 于是我们利用这种特性,可以进行身份识别等应用。 5 细胞识别 细胞识别作为新兴的一个应用,目前在识别技术中引起广泛讨论。过去,我们只能 通过望闻问切等古老手段对疾病进行诊断,后来虽然有了先进的仪器和技术,但是仍然 主要依赖人的经验进行判断,
14、难免出现误判错判的情况,这是因为医疗数据较难解释并 且解释结果过分依赖医生的经验;现在,我们利用计算机技术对疾病进行自动识别,通 过一系列疾病的研究和分析去总结归纳疾病的病因,建立研究医疗方案系统,抽取疾病 特征并且确定分类规则,还可以持续观测医疗疗效泳衣反馈,最终实现错误诊断率的降 低。 6 掌纹识别 掌纹包含屈肌线( P r i n c i p a ll i n e ) 、褶皱线( W r i n k l e ) 、三角点( D e l t ap o 硫) 、脊线 细节点( M i n u t i a e ) 等特征。屈肌线的形状和空间信息是掌纹中最明显最突出最稳定的 特征。褶皱线是比屈肌
15、线细的直线或曲线且不规则。手掌中三角区域有一些中心点,叫 做三角点。脊线细节特征是指类似指纹的细小规则的纹路。高分辨率( 4 0 0 d p f ) 图像 能够获得上述全部特征,可用于刑侦侦查;而低分辨率( 1 0 0 d p i ) 图像只能获得主线、 褶皱等,统称为线特征,更适合用在商业与公共场合下。掌纹具有唯一性,即使双胞胎 的掌纹特征也不相同。因此,近年来模式识别已经将掌纹特征列入研究,并越来越受关 注。 4 硕士论文最近邻分类的若干改进算法研究 1 2 模式分类算法综述 模式分类能力其实很早就被人们所掌握应用,生活中最简单的对人类性别、动物种 类的分类,工作中繁琐多样的对事物属性、人
16、际关系的分类,研究中抽象复杂的对公式 结果、文子图像的分类我们几乎无时不刻都在进行模式分类。在进入信息时代之后, 人们很自然地试图利用计算机进行分类。 在这个过程中,我们发现,需要为计算机指定一个方法( 即分类决策函数) ,并建 立反映该方法优劣的指标才能进行识别,而这个方法的选取并不像人们以为的那样简 单,这就使得分类算法成为一个研究方向。新分类方法的不断涌现,加上传统分类方法 的进一步发展,使得分类方法向着更加高级、更加综合化和更加多样化的方向发展。 1 2 1 贝叶斯分类方法 贝叶斯( B a y e s ) 分类是一种用概率统计进行分类的分类方法,根据贝叶斯定理来 预测一个未知类别的样
17、本的可能属性,并且将该样本归类为可能性最大的那个类别。 但是应用贝叶斯分类法必须假设各个样本类别中特征属性的取值是相互独立的,而 且必须满足一定的条件:即各类别总体的概率分布是已知的,被决策的分类数是一定的 3 1 。由于这个条件在实际情况中经常不能达到,所以其分类的准确率受到影响。 基于最小错误率的贝叶斯决策规则,和基于最小风险的贝叶斯决策规则,是两种常 用的贝叶斯分类规则【2 】。目前也出现了许多贝叶斯改进分类算法,比如降低独立性假设 的T A N ( t r e ea u g m e n t e db a y e sn e t w o r k ) 算法【4 J 。该算法发现了属性对之间的
18、依赖关系,并 且利用该关系来降低朴素贝叶斯( N a i v eB a y e s ) 算法中任意属性之间独立的假设,跟朴 素贝叶斯网络相比,它在网络上增加了属性对之间的关联。其方法是:属性用结点来表 示,属性之间的依赖关系用有向边来表示,根结点为类别属性,其子节点即为它剩余的 所有属性,属性彳,对类别变量C 的影响取决于属性4 ,用属性A 与西之间的边来表示。 T A N 算法考虑了甩个属性中两两属性间的关联性,尽可能地降低了属性之间独立性的假 设,但没有考虑属性之间可能存在更多的其他关联性,因此,其适用范围仍然受到限制。 此外,还出现了贝叶斯信念网络、半朴素贝叶斯算法、B A N 算法等多
19、种改进算法【5 1 , 但贝叶斯分类算法学习是很困难的,有些研究已经证明其学习属于N P c o m p l e t e 问题。 1 2 2 支持向量机分类方法 1 9 9 5 年,C o r i n n aC o r t e s 和V a p n i k 提出支持向量机( S u p p o r tV e c t o rM a c h i n e ,S V M ) 理论,用来解决二分类问题。它基于结构风险最小化原则,具体过程为:首先在向量空 间中寻找一个决策面,这个面能够最好地分割两个分类中的数据点;支持向量机的原理 是通过一个事先选择的非线性映射将一个线性不可分的空间映射到一个高维的线性可
20、 分的空间,在这个空间利用结构风险最小化原则构造最优分类超平面,使两类模式之间 5 1 绪论硕士论文 的空白最大1 6 J 。 支持向量机是一种有效的数据挖掘工具,主要用于进行分类、聚类和时间序列分析。 但是,随着数据集的增大,S V M 的训练时间也会跟着增加,所以S V M 往往需要较长的 训练时间去处理大规模数据集。但在实际的应用中,经常出现大规模数据的情况,这就 使得S v 】受到局限。 针对这个问题,文【7 t 8 】的基本思想是选择- d , 部分最有代表性的数据来代替整个训 练数据集,使得学习效果最大化,用选择性采样或者主动学习方法来训练S V M 。随机 采样 g A o 】也
21、是与主动学习思想类似的方法,这两种方法都需要多次对数据集进行扫描。 与这两种方法不同,文【1 1 】层次聚类( h i e r a r c h i c a lc l u s t e r i n g ) 跟S V M 相结合,使得S V M 对大规模数据的处理速度加快。文中所提出的新方法称C l u s t e r i n g B a s e dS V M ( C B S V M ) ,C B S V M 用一个层次微聚类( h i e r a r c h i c a lm i c r o c l u s t e r i n g ) 算法对整个数据集 进行单遍扫描,为支持向量机提供高质量的样本,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 近邻 分类 若干 改进 算法 研究
链接地址:https://www.31doc.com/p-3582393.html