（应用数学专业论文）模式分类中数据选择方法的研究.pdf

| | i i ii ii ii iii ii i ii iiiil y 18 8 4 7 5 2 西华大学学位论文独创性声明 作者郑重声明：所呈交的学位论文，是本人在导师的指导下进行研究 工作所取得的成果。尽我所知，除文中已经注明引用内容和致谢的地方外， 本论文不包含其他个人或集体已经发表的研究成果，也不包含其他已申请 学位或其他用途使用过的成果。与我一同工作的同志对本研究所做的贡献 均已在论文中做了明确的说明并表示了谢意。 若有不实之处，本人愿意承担相关法律责任。 学位论文作者张稻 日期： 砂i 口j ，口 指导教师始穆学 日期： 阳 、2 、口 西华大学学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，在校 攻读学位期间论文工作的知识产权属于西华大学，同意学校保留并向国家 有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅，西 华大学可以将本论文的全部或部分内容编入有关数据库进行检索，可以采 用影印、缩印或扫描等复印手段保存和汇编本学位论文( 保密的论文在解 密后遵守此规定) 学位论文作者签名：毒苎乡 指导教师签名： 学位论文作者签名：算乏乡 指导教师签名： 日期：沙j d 、i ) ，彦 日期： 乞甲汕晦咖 刃 、多 西华大学硕士学位论文 摘要 在模式识别中，数据选择越来越重要，对识别的效果起着很关键的作用，尤其是边 界数据、冗余数据、杂质数据对分类效果的影响，它大大降低了样本识别率，成为实际 问题中亟待解决的难题。本文针对边界数据、冗余数据、杂质数据三种数据，对两种已 有的方法进行了拓展，并给出了一种新的数据选择的方法，主要研究成果可归纳如下： 1 k 近邻法通常是按照样本之间的距离来选择k 个近邻，本文用特征分量来选择k 个近邻，该方法的优点是按照分量来找k 个近邻，而不是用整体样本来找k 个近邻，避 免了样本中某一分量的负面影响。 + 2 在剪辑近邻法中通常涉及到两个集合：测试集和参考集，本文通过相互变换两 个集合对剪辑近邻法进行了拓展，改进了原来的剪辑近邻法，在很大程度上提高了样本 识别率。 3 为了去除冗余的数据，保留稳定的或者可靠的数据，我们提出了一种新的方法 来完成样本选择的过程。其主要思想是用k 均值聚类方法先将样本分成c 类，然后在 比较新旧两类样本集，并取出它们的各自公共元素( 样本) 作为更新的样本集。此时， 更新的样本就是比较稳定的样本。另外为了表示不同样本在每一类中的重要性，我们在 更新的样本中给出一种新的模糊关系。 文章的最后，作者总结全文，指出了有待于迸一步解决的问题，并对数据选择的前 景作出了展望。 关键词：样本选择；模式分类；特征分量；。近邻分类器；剪辑算法 模式分类中数据选择方法的研究 a b s t r a c t d a t as e l e c t i o np l a y sag r e a tr o l ei np a t t e r nr e c o g n i t i o n i ns t u d y i n gs y s t e m ，w en o t et h a t b o u n d a r yd a t aa n dr e d u n d a n td a t aw h i c hh a v es e r i o u s l yr e d u c e dt h er e c o g n i t i o nr a t eo ft h e s a m p l eb e c o m eo u rp r o b l e m st ob es o l v e d t h i sa r t i c l ef o c u s e so nt h ei n s t a n c es e l e c t i o n f o r d i f f e r e n tp r o b l e m s ，w ei m p r o v et w oo r i g i n a lm e t h o d s ，a n dg i v eo n en e wv i e w ，a n dt h e a u t h o r sm a i np r o d u c t i o ni sc o n t a i n e da sf o l l o w i n g ： ( 1 ) b a s e do nt h ef e a t u r ea t t r i b u t e ， w ep r o p o s ean o v e lr e c o g n i t i o nm e t h o dt oa v o i dt h e a d v e r s ei n f l u e n c eo f n o i s yd a t ai nt h et r a i n i n g t t h em a i ni d e ao ft h i sm e t h o di st of i n dk n e a r e s tn e i g h b o r si ne a c hf e a t u r e i n s t e a do fkn e a r e s tn e i g h b o r si na l ls a m p l e s ( 2 ) me d i t e dt e c h n i q u eu s u a l l yi n v o l v e st w os e t s ：t h et e s t i n gs e ta n dr e f e r e n c es e t w e e x c h a n g e dt h ee d i t i n gs e ta n dt e s t i n gs e t ， a n di m p r o v e dt h eo r i g i n a lm e t h o d ( 3 ) b a s e do nr e m o v i n gr e d u n d a n td a t aa n dr e t a i n i n gr e l i a b l ed a t a ， w ep r o p o s ean e w m e t h o dt oc o m p l e t ei n s t a n c 圯s e l e c t i o n n l em a i ni d e ao ft h i sm e t h o di st h a tw ec o m p a r e c l a s s e si ni n i t i a lt r a i n i n gs e tw i t hc l u s t e r sa f t e rk - m e a n sc l u s t e r i n g w em a k et h ei n t e r s e c t i o n b e t w e e ne v e r yc l a s sa n dc l u s t e ra st h er e l i a b l es a m p l e s i na d d i t i o n ，t oi n d i c a t ed i f f e r e n t s a m p l e s d i f f e r e n ti m p o r t a n c ei ne a c hc l a s s ，w eg i v eaf u z z yr e l a t i o n s h i pi nt h er e l i a b l ed a t a i nt h ee n d ，t h ea u t h o rs u m m a r i z e st h er e s e a r c hp r o c e s sa n dp o i n t so u ts o m el i m i t a t i o n s o ft h i sp a p e r k e yw o r d s ： i n s t a n c es e l e c t i o n ；p a t t e r nc l a s s i f i c a t i o n ；f e a t u r ea t t r i b u t e ；k - n e a r e s t n e i g h b o r sc l a s s i f i c a t i o n ；e d i t i n gt e c h n i q u e i i 西华大学硕士学位论文 目录 摘 要i a b s t r a c t i i 1 绪论l 1 1 课题研究背景和意义1 1 2 国内外研究现状3 1 2 1 模式识别中数据选择方法的研究历史与现状3 1 2 2 经典数据选择方法的回顾与评价3 1 3 本文的主要研究内容5 2 预备知识6 2 1 模式识别6 2 1 1 模式识别系统6 2 1 2 有监督和无监督分类7 2 1 3k 均值聚类8 2 1 4k 近邻分类器9 2 2 模糊数学知识9 2 2 1模糊集合与隶属函数9 2 2 2 模糊k 近邻分类器1 0 2 3 数据选择方法11 2 3 1 不理想数据的概念1 l 2 3 2 数据的剪辑近邻法1 l 2 3 3 数据的压缩近邻法1 2 2 4 本章小结1 4 o 改进的过滤样本方法1 5 3 1 用特征分量来过滤样本1 5 3 1 1 特征分量的处理。1 5 3 1 2 加权的特征属性1 7 3 1 3 实验结果1 7 3 2 改进的剪辑k 近邻分类器2 0 3 2 1 改进的剪辑近邻法2 0 3 2 2 比较实验一2 l 3 3 本章小结2 3 i l l 模式分类中数据选择方法的研究 4 基于k 均值聚类的数据选择2 4 4 1 过滤样本的背景2 4 4 2 用交集找出稳定的数据2 4 4 3 样本选择后的模糊k 近邻分类器2 7 4 3 1 训练集的初始隶属度2 7 4 3 2 基于修正的训练集的模糊k 近邻分类器2 8 4 4 实验2 9 4 4 1 实验数据2 9 4 4 2 实验结果和分析3 0 4 5 本章小结3 3 结论。3 5 参考文献3 4 攻读硕士学位期间发表学术论文情况3 7 致 射3 8 i v 西华大学硕士学位论文 1绪论 模式识别是研究用计算机自动识别事物的_ f - - j 科学，其目的是用机器完成类似于人 类智能通过视觉、听觉等感官去识别外界环境所进行的工作，它包括语音识别、图像识 别等典型应用 1 】。模式识别中数据选择随着系统的日益复杂变得越来越重要。 1 1 课题研究背景和意义 在模式分类中由于数据的原因，使得分类准确性和计算时间性受到影响，因此需要 不同的方法来对这些数据进行处理，要解决的是模式识别系统中的样本预处理。在有监 督或半监督的分类系统中，随着训练样本的不断增多，样本选择是一个重要的预处理过 程。在无线电信号识别中，原始的信号数据过于粗糙，总会出现各种边界数据，奇异数 据，冗余数据，并且伴随着样本量的增多，计算复杂性受到了很大的影响。已标记训练 样本数据的准确性和稳定性在很大程度上能影响分类效果。一般说来，有监督的分类系 统要求储存整个训练数据以便进行搜索。数据量的增多和己错误分类的样本共同所导致 的大量样本失真，不仅影响了分类效果，也对计算复杂性提出了很高的要求。总之，训 练数据来自现实世界，甚至是在干扰强烈的情况下，我们必须给以足够的重视。 通常原始样本数据量很大，在此情况下分类是比较困难的。样本选择期望达到的效 果：一是减少数据量，提高计算速度；二是剔除杂质数据( 边界数据) ，提高识别率； 三是样本集原型还原，尽量使数据选择后识别率能与之前相同。现在比较难解决的问题 是：( 1 ) 如何找到那些人们希望剔除的数据( 边界点、离群点、冗余数据、被错误识 别点) ；( 2 ) 如何处理训练样本集中样本的关系；( 3 ) 如何减少储存要求和计算负担。 如果以上问题得到解决，则样本识别率和识别速度会有很大提高。 样本选择是处理大数据集和杂质数据集的主要方法。他处理的主要问题是如何提取 出那些具有代表性的子集，这些子集的大小较原来少很多，但所含有的对分类有用的信 息量要和原来的样本集的信息量一样多。除了样本选择，还有其他许多方法也用来处理 杂质数据，例如数据归一化或正规化【2 1 、多元回归树【3 】等等。样本选择的好坏通常用如 下算法来予以验证：机器算法( k n n ，s v m ) 和神经网络算法( n r b f ，f s m ) 。我们选择 运用最广泛的方法，也就是k n n 和f k n n 。k n n 是一种简单但是很有效的分类算法，它在 实际应用中也非常广泛。f k n n 4 是八十年代中期提出的一种算法，它是k n n 的一种拓展。 f k n n 被用来验证的的另外一个重要原因是它能很好的处理训练集中样本的关系，也就是 模式分类中数据选择方法的研究 我们在算法开始必须给定的初始隶属函数。我们希望能用不同的算法来验证新提出的样 本选择的方法，并尝试用于实际问题中。 模式识别中的数据选择的方法的基本流程图如下： 开始( s t a r t ) 上上 数据获取( d a t aa c q u i s i t i o n ) ： 上上 预处理( p r e p r o c e s s i n g ) ：数据选择 上上 特征提取和选择( f e a m i 髑e x t r a c t i o na n ds e l e c t i o n ) ： 寻找有利于分类的本质特征 l l - 己2 - - 分类决策( c l a s s i f i c a t i o nd e c i s i o n ) ： 做出关于样本类别的判断 评价分类器( e v a l u a t ec l a s s i f i e r ) ： 比较分类识别率的高低，评 ii ，l ，步 l 结束) 图1 1 模式识别系统的设计 f i g 1 1 t h ed e s i g no fap a t t e r nr e c o g n i t i o ns y s t e m 西华大学硕士学位论文 1 2 国内外研究现状 1 2 _ 1 模式识别中数据选择方法的研究历史与现状 h a r t 5 】在1 9 6 8 年提出了压缩近邻法( c n n ) ，其基本思想：利用现有样本集，逐渐 生成一个新的样本集，使该样本集在保留样本最少量的条件下，仍能对原有样本集用最 近邻法正确分类，那么该样本集也能对待识别样本进行分类，并保持正常识别率。当时 的改进效果并不是很明显，但是此模型激发了许多的学者在此方向上的拓展。g a t e s l 6 于1 9 7 2 年提出了约简近邻法( r n n ) ，其思路与c n n 基本一致。它并不像c n n 那样从新 的样本集开始，而是从整个训练集开始，去除那些不降低分类识别率的样本。 d r i i i s o n 7 】在g a t e s 工作上又引入了r n n 的学习算法。b r i g h t o na n dm e l l i s h t 8 】提出 了迭代过滤法( i c f ) ，它采取两次剪辑，先用e n n 剪辑，接着用达到率和收敛性进行 剪辑。f a n g i u l l i t 9 】在2 0 0 7 年提出了快速压缩最近邻法( f c n n ) ，大大的减少了因压 缩算法所带来的时间负担。后来v s u r e s h t l 0 】将r o u g h f u z z y 理论与l e a d e r 算法结合， 来处理大的数据集。+ w i l s o n t l l 】在1 9 7 2 年相继提出了剪辑近邻法( e n n ) 和重复选择近邻法( r e n n ) ，利 用现有样本集对其自身进行剪辑，将不同类别交界处的样本以适当的方式筛选，去除那 些很大程度上不完全属于某一类的边界样本，可以实现既减少样本数又提高识别率的双 重目的。该算法消除了那些分类错误的样本，清理了类与类之间的边界。t o m e k 1 2 】于1 9 7 6 年提出了剪辑所有k 近邻法( e a k n n ) ，它是在r e n n 的基础上发展起来的，对于所有的 k 都重复剪辑，能使得训练样本清理地更彻底。m i i n - s h e ny a n g 在t o m e k 的基础上提出 了剪辑模糊k 近邻法( e f k n n ) 。由于不同的应用，在文献【1 3 1 中，剪辑法和近邻法里的 欧式距离被图距离( g a b r i e l 图) 取代，s a n c h e z 建立了基于图的剪辑法。k u n c h e v a 【1 4 】 将遗传算法与剪辑法结合起来剔除一些数据。n r b f 是r b f 的一种正规化改进， j a n k o w s k i 1 5 】将剪辑法用在n r b f 上，提出了e n r b f 。r i q u e l m e 【l6 】提出了一种投影的方法 来剪辑样本，它的主要优点是即省去了距离计算又保留了决策边界。 c n n 的主要作用是减少数据，为原本训练集“瘦身”，提高计算速度，而e n n 的主 要作用是去除杂质数据，使样本集更接近它的本质，提高准确性。 1 2 2 经典数据选择方法的回顾与评价 数据选择的方法大体上可以分为两类：在概率层面上的数据选择和在非概率层 面上的数据选择【i 丌。概率层面的数据选择以概率理论为依据，通过随机化的机械操 作程序取得数据，所以能避免抽样过程中的人为因素的影响，保证样本的客观性 虽然随机样本一般不会与总体完全一致，但它所依据的是大数定律，而且能计算和 模式分类中数据选择方法的研究 控制抽样误差，因此可以正确地说明样本的统计值在多大程度上适合于总体，根据 样本调查的结果可以从数量上推断总体，也可在一定程度上说明总体的性质，特征 现实生活中绝大多数数据选择都采用概率抽样方法来抽取样本t 1 。7 1 概率抽样包括有 简单随机抽样、系统抽样( 等距抽样) 、分层抽样( 类型抽样) 和整群抽样等方法。 概率抽样的基本原则是：样本量越大，抽样误差就越小，而样本量越大，则成本就 越高。根据数理统计规律，样本量增加呈直线递增的情况下( 样本量增加一倍，成 本也增加一倍) ，而抽样误差只是样本量相对增长速度的平方根递减。因此，样本 量的设计并不是越大越好。模式分类中，贝叶斯决策论是解决分类问题的种常用 统计途径【l 引，一般用在模式识别的决策阶段( 如图1 1 ) 。 非概率数据的选取都基于研究者的主观判断( 即有一定的选择标准) ，不进行 严格的统计分析。非概率数据的选择方法与概率数据的不同，后者都采用基于某种 随机机制的选择方法，以确保数据的选择能独立于主观判断( 实用主义抽样) 。这 些数据可以方便地或以某种系统的标准为根据选取。非概率数据选择实际上根据是 一组性质各异，用主观判断选择的数据的抽样方法。由于在模式识别中样本通常不 具备一些统计特征，所以我们一般采用非概率数据选择方法。但是在模式识别中， 非概率数据选择方法是一种颇为有用的工具，广泛应用在很多研究项目。 模式识别中非概率数据的选取方法按照不同的选择标准大致可以从三个方面概 括，即去除噪音方面( n o i s ef i l t e r s ) ，压缩算法方面( c o n d e n s a t i o na l g o r i t h m s ) ， 原型还原方面( p r o t o t y p es e l e c t i o na l g o r i t h m s ) 【2 l 】。下面简要概述一下国内外学者在 这三方面的主要研究成果。 ( 1 ) 去除噪音方面( n o i s ef i l t e r s ) 。这一方面的主要目的是去除噪音，样本选 择标准是样本是否为噪音。自w i l s o n 1 1 】首先提出剪辑近邻规则( e d i t e dn e a r e s t n e i g h b o r r u l e ) 和重复的剪辑近邻规则( r e p e a t e de d i t e d n e a r e s t n e i g h b o r r u l e ) 后， 许多学者在此基础上相继作了不同工作，例如，t o m e k 1 2 】的所有的k 都重复剪辑一遍 ( a l lk n n ) ，以及剪辑径向基函数神经网络 1 4 - 1 5 】( e d i t e dn o r m a l i z e dv e r s i o no f r a d i a l b a s i sf u n c t i o n ) 。 ( 2 ) 压缩算法方面( c o n d e n s a t i o na l g o r i t h m s ) 。这一方面的主要目的是压缩数 据，进而减少计算量( 计算复杂性) ，其选择标准是样本是否存在重叠或冗余。数 据选择方法最早是h a r t 5 提出的压缩近邻规则( c o n d e n s e dn e a r e s tn e i g h b o rr u l e ) ， 接着相应的截使之越来越完善，例如，g a t e s 6 】的缩减近邻规则( r e d u c e dn e a r e s t n e i g h b o r ) ， a h a 【1 9 1 的增量算法( i n c r e m e n t a la l g o r i t h m ) ，b h a t t a c h a r y a 2 0 的关于图 论的剪辑法( g a b r i e l 尉l i t i n ga n dr e l a t i v en e i g h b o r h o o dg r a p he d i t i n g ) ，b r i g h t o n _ ，0 。，一 西华大学硕士学位论文 和m e l l i s h 8 提出的样本迭代过滤法( i t e r a t i v ec a s ef i l t e r i n g ) ，w i l s o n 和m a r t i n e z t 2 2 j 提出的五种模型( d r o p l 5 ) 。 ( 3 ) 原型还原方面( p r o t o t y p es e l e c t i o na l g o r i t h m s ) 。这一方面的主要目的是 尽最大可能的还原成样本集的原型，降低初始样本集和选择后的样本集的本质特征 的差异性。这方面的主要研究成果有：k o h o n e n l 2 3 l 拘l e a r n i n gv e c t o r sq u a n t i z a t i o n 算 法，s k a l a k t 2 4 】的m o n t ec a r l o1a n dr a n d o mm u t a t i o nh i l lc l i m b i n g 算法， c a m e r o n j o n e s t 2 5 1 提出的三种用代价函数定义的方法，后两者是前者的改进( e l h ， e l g r o wa n de x p l o r e ) 。 当然，这三者有时是相互交叉的，可能在去除噪音的同时，在原型还原方面所 起的作用也很大。 1 3 本文的主要研究内容 论文一共分为四个章节，其技术路线和主要工作现归纳如下： 第一章介绍本课题的研究背景和意义，对数据选择问题的研究历史与现状进行了综 述。对文章中用到的基础知识进行了介绍，简单回顾一些经典的数据选择方法，总结了 样本选择的几种确定方法。 第二章详细介绍了模式识别中的一些基本概念，有监督和无监督的分类，和k 近邻 分类器，以及在k 近邻算法中所涉及的模糊集、隶属函数等模糊数学知识，为论文的后 续章节做知识铺垫。 第三章改进了已有的两种方法。在第一部分中，把原始的k 近邻算法进行了改进。 经典的k 近邻法是在样本集中按照样本与样本之间的距离来选择k 个近邻，而本章中用 样本与样本的分量之间的距离来选择k 个近邻。这样就避免和解决的边界和噪声的数据 的负面影响。在第二部分中，在剪辑近邻法中通常涉及到两个集合：测试集和参考集， 通过相互变换两个集合对剪辑近邻法进行了拓展，改进了原来的剪辑近邻法，在很大程 度上提高了样本识别率。 第四章从集合的角度来进行样本选择，在思路上与已有的样本选择方法有很大的区 别，它首先用k 均值聚类所有的样本，得到的样本集与原来的样本集取交，得出交集， 我们认为此交集基本上能代表初始的样本集，并在最后给出了一种改进的模糊隶属函 数，有一定的实际意义。 结论部分概述了论文的主要创新之处，讨论了进一步的研究方向，并对论文中存在 的不足和局限进行了说明。 模式分类中数据选择方法的研究 2 预备知识 2 1模式识别 模式识别诞生于2 0 世纪2 0 年代，随着4 0 年代计算机的出现，5 0 年代人工智能的 兴起，模式识别在6 0 年代初迅速发展成- - i 学科。它所研究的理论和方法在很多科学 和技术领域中得到了广泛的重视，推动了人工智能系统的发展，扩大了计算机应用的可 能性。几十年来，模式识别研究取得了大量的成果，在很多地方得到了成功的应用。但 是由于模式识别涉及到很多复杂的问题，现有的理论和方法对于解决这些问题还有很多 不足之处【l 】。 我们在生活中时时刻刻都在进行模式识别。环顾四周，我们能认出周围的物体是桌 子、椅子，能认出对面的人是张三、李四；听到的声音，我们能区分出是汽车驶过还是 玻璃捏碎，是猫叫还是人语，是谁在说话，说什么内容：闻到气味，我们能知道是炸带 鱼还是臭豆腐。我们所具备的这些模式识别的能力看起来极为平常，谁也不会对此感到 惊讶，就连猫狗也能识别它们的主人。因此过去的心理学家也没有注意到模式识别在多 数方面还远不如人，因此研究人脑中的模式识别过程对提高机器的能力是有益的【1 1 。 人们为了掌握客观事物，按事物相识的程度组成类别。模式识别的作用和目的就在 于面对某一具体事物时将其正确地归入某一类别。通常，我们把通过对具体的个别事物 进行观测所得到的具有时间和空间分布的信息称为模式，而把模式所属的类别或同一类 中的模式的总体称为模式类【。 2 1 1 模式识别系统n 1 模式识别由两种基本的方法够成：统计模式识别方法和结构模式识别方法，与此相 应的模式识别系统都由两个过程所组成，即设计和实现。设计是指用一定数量的样本( 叫 做训练集或学习集) 进行分类器的设计。实现是指用所设计的分类器对待识别的样本进 行分类决策【l 】。 图2 1 模式识别系统的训练过程 f i g 2 i t h et r a i n i n go fap a t t e r nr e c o g n i t i o ns y s t e m 6 西华大学硕士学位论文 其基本步骤为： 1 数据获取【1 】 为了计算机能够对各种现象进行分类识别，要用计算机可以运算的符号来表示所研 究的对象。通常输入对象的信息有下列三种类型，即 ( 1 ) 二维图像，如文字、指纹、地图、照片这类对象。 ( 2 ) 一维波形，如脑电波、心电图、机械振动波形等。 ( 3 ) 物理参量和逻辑值前者如在疾病诊断中病人的体温及各种化验数据等；后者 如对某参量正常与否的判断或对症状有无的描述，如疼与不疼，可用逻辑值即0 和1 表 示。在引入模糊逻辑的系统中，这些值还可以包括模糊逻辑值，比如很大、大、比较大 等。 通过测量、采样、和量化，可以用矩阵或向量表示二维图像或一维波形。这就是数 据获取的过程。 2 预处理 预处理的目的是去除噪声，加强有用的信息，并对输入测量仪器或其他因素所造成 的退化现象进行复原。本文重点处理的是这一部分。 3 特征提取和选择 由图像或波形所得到的数据量相当大。为了有效地实现分类识别，就要对原始数据 进行变换，得到最能反映分类本质的特征。这就是特征提取和选择的过程。 4 分类决策 分类决策就是在特征空间中用统计方法把被识别对象归为某一类别。基本做法是在 样本训练集基础上确定某个判决规则，使按这种判决规则对被识别对象进行分类所造成 的错误识别率最小或引起的损失最小。实际上这个过程也可以叫做训练过程。 2 1 2 有监督和无监督分类 假设有一个可用的训练数据集，并通过挖掘先验已知信息来设计分类器，这就称为 有监督模式识别( s u p e r v i s e dp a t t e r nr e c o g n i t i o n ) 。但是并不总是这种情况，另外一种模 式识别是没有已知类别标签的训练数据可供使用。在这种情况下，给定一组特征向量x 来揭示潜在的相识性，并且将相似的特征向量分为一组，这就是无监督模式识别 ( u n s u p e r v i s e dp a t t e r nr e c o g n i t i o n ) 或聚类( c l u s t e r i n g ) 【l 】。 监督分类( s u p e r v i s e dc l a s s i f i c a t i o n ) 又称训练场地法，是以建立统计识别函数为 理论基础，依据典型样本训练方法进行分类的技术。即根据已知训练区提供的样本，通 过选择特征参数，求出特征参数作为决策规则，建立判别函数以对各待分类影像进行的 7 模式分类中数据选择方法的研究 图像分类，是模式识别的一种方法。要求训练区域具有典型性和代表性。判别准则若满 足分类精度要求，则此准则成立；反之，需重新建立分类的决策规则，直至满足分类精 度要求为止。 非监督分类是指人们事先对分类过程不施加任何的先验知识，而仅凭数据，即自然 聚类的特性，进行“盲目”的分类；其分类的结果只是对不同类别达到了区分，但并不能 确定类别的属性，亦即：非监督分类只能把样本区分为若干类别，而不能给出样本的描 述；其类别的属性是通过分类结束后目视判读或实地调查确定的。非监督分类也称聚类 分析，一般的聚类算法是先选择若干个模式点作为聚类的中心，每一中心代表一个类别， 按照某种相似性度量方法( 如最小距离方法) 将各模式归于各聚类中心所代表的类别， 形成初始分类，然后由聚类准则判断初始分类是否合理，如果不合理就修改分类，如此 反复迭代运算，直到合理为止。与监督法的先学习后分类不同，非监督法是边学习边分 类，通过学习找到相同的类别，然后将该类与其它类区分开。根据待分类样本特征参数 的统计特征，建立决策规则来进行分类；而不需事先知道类别特征。 2 1 3k 均值聚类 聚类是人类最原始的精神活动，用于处理他们每天接收到的大量信息。将每个信息 作为一个单独实体进行处理是不可能的。因此，人类试图将实体( 如对象、个人、事件) 分类，每一类由它包含的实体的共同特征来标测2 1 。k 均值聚类是一种无监督的分类， 无监督分类的训练样本没有类别标签。 聚类分析，是对样本空间的一种硬或者软分类，已经被广泛用在许多方面例如数据 挖掘和模式识别。训练集中噪音样本的存在很大程度上影响了分类的效果。这篇文章中， 根据距离度量公式，k 均值聚类被用来将训练样本分类。k 均值聚类算法的工作过程说 明如下：首先从刀个数据对象中选择k 个对象作为初始聚类中心：对于任意一个对象， 按照距离将样本归入与其最相似的( 聚类中心所代表的) 聚类，然后再重新计算一下新 聚类的聚类中心，放一个样本重新聚一次类，不断重复这一过程直到标准测度函数开始 收敛为止。一般都采用均方差作为标准测度函数。聚类具有以下特点：各聚类本身尽可 能的紧凑，而各聚类之间尽可能的分开【2 1 。 其基本算法如下： 步骤一：输入初始值类别数k ，样本r ，从样本丁中随机选取k 个样本作为k 个初 始中心。 步骤二：按照距离公式，将丁中任意一个样本按照距离将样本归入k 类中一个。则k 类再更新一下中心。 步骤三：按照步骤二重复进行，直到样本? 中的所有的样本都被归入k 类中。 8 西华大学硕士学位论文 对于n 维特征空间中的c 类问题，不妨假设给定丁个已分类的样本，并归于c 类。 在本文中，k 均值聚类将样本集t = 秒。，y ：，y 。) 兰 只础，矽，芹埘) 聚类成c 类 t = 抄。，埘“，咒) 兰 只。胁，g 姗，f 姗) 。 2 1 4k 近邻分类器 近邻分类器( n n ) 和它的推广k 近邻分类器( k n n ) 由于简单性、效果明显，越来 越多的系统用到它。给定一个训练样本集，我们用欧氏距离公式来计算训练样本之间 的距离。训练样本集t 由c 类构成，其中i t i = f 表示所有已标记样本的的数目，c 代表样 本t 的类别数。在这个算法中，我们尽量要找出后个近邻样本。 此算法描述如下： 步骤一：输入近邻数后的值，和已标记样本集t = 秒，y ：，y t ) 兰 p o u ，酽，r ) 步骤二：对于给定的测试样本工，计算x = ( 毛，j c 29o 毛) 与所有样本 y ，= ( y t l ，m 2 ，y i n ) ，也就是，对于所有的f 1 , 2 ，t ) ， d ( x ，y , ) = x - y , l l = 步骤三：将距离d ( x ，咒) ，i = 1 , 2 ，t ，进行排列，然后根据这个排列找出与工最近的 j | 个样本，记这j i 个近邻为正。 步骤四：将七个近邻样本的类别指标进行统计，则分别属于这c 类的样本数为 毛，屯，屯) ，其不同的样本集 只喇，i = 1 ，2 ，c ) ，其中墨满足岛= 尼。 i = l 步骤五：根据测试样本工与这些近邻的距离，按照七中各类的大多数，测试样本就 分到最多的哪一类里。如果k 满足t = m a x k ，ii = 1 , 2 ，c ) ，也就是， k = a r g m a x k i ，于是样本x 被分到样本集中。 2 2 模糊数学知识 2 2 1 模糊集合与隶属函数 在数学上，概念的外延可以通过“集合”来表达。然而，日常生活中涉及的众多的 概念常有内涵的“模糊性( f u z z y ) ”，这必然导致外延的“不清晰性”。例如，对于 “高个子男人”这个概念，如果说1 8 0 m 以上的男人都算高个子，那么1 7 9 m 的男人就 不算高个子了，但是1 8 0 m 与1 7 9 m 仅l c m 之差，肉眼是很难辨别的。因此，“高个子 模式分类中数据选择方法的研究 男人”的外延不应有清晰的边界。然而( c a n t o r 提出的) “经典集合”必定是“清晰的”， 即对集合a 和某具体对象a ，a a 与a 薯a 有一个也仅有一个成立。这说明不能用经典 集合去刻画模糊( f u z z y ) 概念的外延，从而z a d e h 提出了f u z z y 集概念【拘。 定义2 1 1 2 7 设u 为论域，则u 上的一个模糊集合彳由u 上的一个实值函数 u 专【0 ，l 】 以：u h 心( “) 来表示。对于“u ，函数值儿( “) 称为u 对于彳的隶属度，而函数儿称为a 的隶 属函数 由此可见，模糊集合彳是一个抽象的概念，其元素是不确定的，我们只能通过隶属 函数儿来认识和掌握彳。儿( u ) 的数值的大小反映了论域u 中元素u 对于模糊集合彳的 隶属程度，心( u ) 的值越接近1 ，表示“隶属于彳的程度越高；儿( “) 的值越接近于0 ， 表示“隶属于彳的程度越低。特别地，若心( “) = 1 ，n p , y 寸u 完全属于彳；若心( u ) - - 0 ， 则认为u 完全不属于彳。 2 2 2 模糊k 近邻分类器 在我们前面给定的聚类的定义下，每一个向量属于单一聚类，这种聚类类型被称为 硬的或脆的。在z a d e h 的模糊集中介绍了另一个定义。集合x 的模糊聚类是将集合x 分 成m 个类，由m 个函数u ，表示，其中 u ，：x 一 o ，1 】，j = 1 , 2 ，m 且 m “，( ) = 1 ，i = 1 , 2 ，n ，0 ”如f ) n ，= l ，2 ，m ， j - 1 i = i 这些函数被称为隶属函数( m e m b e r s h i pf u n c t i o n s ) 。模糊隶属函数值具有集合的数学特 性，即我们事例中的聚类可能没有精确的定义。也就是说，每一个向量x 同时属于多个 聚类“达到某种程度”，区间【0 ，1 】中的“，相应值量化这个程度，接近1 的值表示与该类 的隶属程度高，接近0 的值表示与该类的隶属程度低。这些隶属函数的值表示了数据集 的结构，在某种意义上，如果隶属函数对于z 的两个向量( 也就是z ，x ，) 的值都接近1 ， 那么认为它们是相似的【2 卅。 1 0 西华大学硕士学位论文 2 3 数据选择方法 2 3 1 不理想数据的概念 通常，如图2 2 所示，有以下几种不同的不理想数据集：奇异数据集，冗余数据集， 边界数据集。奇异数据通常指的是那些距离所在类的中心十分远，但又被分到了该类的 点。由于噪音数据和边界数据的存在，类的中心会严重的偏离它本身的中心。冗余数据 是指那些多余的数据，即不需要这些数据，也能够正确地进行分类。边界数据是指类与 类之间边界相对模糊，难以分清的数据。我们的目的是要尽可能地降低这些数据的重要 性，或者直接不考虑这些数据。对于这三种情况，如何找出不理想的数据，然后它们分 别又属于哪一类，都是比较棘手的问题。 图2 2 不同的数据集 f i g 2 2 t h ed i f f e r e n td a t as e t 2 3 2 数据的剪辑近邻法 剪辑近邻法着眼于如何减少训练样本数目，从而可同时减少分类时的计算量及训练 样本的存储量，同时还能迸一步改进分类器的性能，如降低错误率等要求。本节讨论的 剪辑近邻法除了在样本数量上有一定程度的减少外，更主要的优点是错误率的降低。 剪辑近邻法的基本思想是从这样一个现象出发的，即当不同类别的样本在分布上有 交迭部分的，分类的错误率主要来自处于交迭区中的样本。当我们得到一个作为识别用 的参考样本集时，由于不同类别交迭区域中不同类别的样本彼此穿插，导致用近邻法分 类出错。将不同类别交界处的样本以适当方式筛选，可以实现既减少样本数又提高正确 识别率的双重目的。因此可以利用现有样本集对其自身进行剪辑。下面以两类的情况为 例描述这种方法【l 】。 假设现有一个样本集s ，样本数量为，将此样本集分成两个互相独立的样本子集， 一个被当作考试集s w ，另一个作为参考集s 艘，数量分别为胛与n r ，胛+ n r = n 。 模式分类中数据选择方法的研究 将中的样本表示成x i ，o = 1 , 2 ，n t ) ，而在s 胍中的样本表示为z ，o = 1 , 2 ，n r ) 。 将一个样本集分成两个相互独立的样本子集是指，分完以后的两个子集具有相同的分 布，在每个特征空间的子区域，两个子集都有相同的比例，或说各类数量近似相等。要 注意指出的是每个子区域( 从大空间到小空间) 要从总的集合中以随机抽取的方式进行。 剪辑的过程是：首先对s 胛中每一个置在s 脓中找到其最近邻的样本z ) ，用 r ( 置) 表示i 是五的最近邻参考样本。如果z 与五不属于同一类别，则将五从s 胛中 删除，最后从中得到一个经过剪辑的样本集，称为剪辑样本集s 臃。s 腑可用来取 代原样本集s ，作为参考样本集对待识别样本进行分类。 经过剪辑后，作为新的训练样本集。s 胀是对其性能进行测试的样本，如发现s 胛 中的某个训练样本对分类不利，就要把它剪辑掉。实际上剪辑样本的过程也可以用k 近 邻法进行，即对s 胛中的每个样本置，找到在s 胀中的k 个近邻，用k 近邻法判断置是 否被错分类，从而决定其取舍，其它过程与前述方法完全一样。 剪辑近邻法的剪辑过程也可不止一次，重复多次的称为重复剪辑近邻法。前面我们 已经提到，倘若用近邻法分类，容易出错的区域是在两类的交界处，这时某个训练样本 的存在与否就会影响到某些测试分类的结果。因此剪辑的效果往往把这些处于交界的训 练样本给剪辑掉【l 】