（模式识别与智能系统专业论文）一个集成的无约束手写数字串识别系统.pdf

中同科学院自动化所硕士学位论文 摘要 手写数字识别的目的是使数据信息能够自然、方便地输入计算机，以便于 进一步的处理。手写数字识别有蓉极为广泛的应用前景，在大规模数据统计、 财务、税务、金融领域以及邮件分拣中都有着成功的应用。同时手写数字识别 作为一个有难度的开放问题，可以为理论的深入分析、验证及评估提供具体的 实验平台，因而吸引了世界各地的研究工作者参与。 对于无约束的手写数字串识别来说，难点在于怎样使计算机具有鲁棒的识 别能力，不因为噪声和不同的个人书写方式而导致错误的结果。这就为学习理 论提出了新的挑战。 本文先就手写数字识别的相关研究发展作了综述，然后的一章介绍了机器 学习，包括非监督学习和监督学习，在数字识别中的应用。在非监督学习小节 中，除了比较各种成熟的聚类方法，还提出了自己的交迭聚类算法和基于r b f 核的升维聚类算法。在监督学习章节中，着重描述了将在实际工作中利用和展 开的各种方法，如贝叶斯理论、e m 算法、学习矢量量化、支持向量机等。接下 来的一章着重讲述数字串识别领域的主要研究方向。最后一章描述了一个己实 现的具体的手写数字串识别系统。在该系统中，数字串图像首先被分割为单个 数字字符，然后经过预处理包括平滑去噪、倾斜校正、归一化，再使用多种方 法进行特征提取以便于多特征的分类器集成。在单分类器训练阶段，结合了无 监督聚类和有监督学习的方法，保证学习训练过程的快速和有效。在有监督学 习阶段，高斯混合模型和概率的学习矢量量化被统一在学习算法中并得到了不 错的效果。在多分类器集成阶段，分析了该集成框架对于识别率和识别速度的 影响，并引入决策轮廓矩阵以充分利用各分类器的识别结果信息。我们针对已 有的基于决策模板的算法提出了改进算法。最后给出了我们的集成方法的识别 效果，并和部分的其它集成方法作了比较。可以看出，我们的集成方法取得了 较高的识别效果，在中科院自动化所文字识别工程中心的大规模样本集上达到 9 9 2 2 的识别率。 关键字：手写数字识别，数字串分割，机器学习，聚类，分类器集成 ! 堕型堂堕! 垫些堕堡! 兰竺堡塞 a b s t r a c t t h ep u r p o s eo fh a n d w r i t t e nn u m e r a lr e c o g n i t i o ni st oi n p u td a t ai n t oc o m p u t e r s f o rf u r t h e rd i s p o s a ln a t u r a l l ya n dc o n v e n i e n t l y r e c o g n i t i o no f h a n d w r i t t e nn u m e r a l s h a sb e e ns u c c e s s f u l l yu s e di nf i e l d ss u c ha sl a r g e - s c a l es t a t i s t i c s ，f i n a n c e ，r e v e n u e a n dm a i l ss o r t i n g a sa no p e na n dd i f f i c u l tc h a l l e n g e ，t h er e c o g n i t i o np r o b l e mo f h a n d w r i t t e nn u m e r a l sa l s ob u i l du pa t e s t i n gp l a t f o r m f o r i n d e p t ha n a l y s i s ， v e r i f i c a t i o na n de v a l u a t i o no fd i f f e r e n tk i n d so ft h e o r i e s r e s e a r c h e r sa 1 1o v e rt h e w o r l da r ea p p e a l e dt ot a k ep a r ti nt h ew o r k f o ru n c o n s t r a i n e dh a n d w r i t t e nn u m e r a l s t r i n gr e c o g n i t i o np r o b l e m ，t h e d i f f i c u l t yl i e s i nh o wt ot m d u et h ec o m p u t e rw i t hr o b u s tr e c o g n i t i o na b i l i t ya n d e r r o n e o u so u t c o m ew o u l dn o ta p p e a ra sar e s u l to f n o i s e sa n dd i f f e r e n tw r i t i n gs t y l e s b yp e r s o n t h u sn e wc h a l l e n g e sa r eb r o u g h tf o r w a r dt om a c h i n el e a r n i n gt h e o r i e s i nt h et h e s i s ，t h er e l a t e dr e s e a r c h e si nr e c o g n i t i o no fh a n d w r i t t e nn u m e r a ls t r i n g a r eo v e r v i e w e df o rt h ef i r s t t h ef o l l o w i n gc h a p t e ri n t r o d u c e st h ea p p l i c a t i o no f m a c h i n e l e a r n i n g i nn u m e r a l s r e c o g n i t i o n ，i n c l u d i n gu n s u p e r v i s e dl e a r n i n g m e t h o d sa n ds u p e r v i s e dl e a r n i n gm e t h o d s i nu n s u p e r v i s e dl e a r n i n gc h a p t e r , w e a d v a n c eo u ro v e r l a p p i n gc l u s t e r i n ga l g o r i t h ma n dr b fk e r n e lb a s e dc l u s t e r i n g a l g o r i t h ma s i d e f r o mc o m p a r i s o no fs e v e r a lm a t u r ec l u s t e r i n gm e t h o d s i n s u p e r v i s e dl e a r n i n gc h a p t e r ，w ef o c u so n i n t r o d u c t i o no fm e t h o d st h a tw i l lb e u t i l i z e da n de x p a n d e di no u ra p p l i c a t i o n ，s u c ha sb a y e s i a nt h e o r y ，e ma l g o r i t h m ， l e a r n i n gv e c t o rq u a n t i f i c a t i o na n ds u p p o r t v e c t o rm a c h i n e t h en e x tc h a p t e r c o n c e n t r a t e so nm a i nd i r e c t i o n si nt h er e s e a r c hf i e l do fn u m e r a ls t r i n gr e c o g n i t i o n t h el a s tc h a p t e rd e s c r i b e so u rc o n c r e t eh a n d w r i t t e nn u m e r a ls t r i n gr e c o g n i t i o n s y s t e mi nt h es y s t e m ，i m a g e so f n u m e r a ls t r i n g sa r es e g m e n t e di n t os e p a r a t ed i g i t s f o rt h ef i r s t t h e nt h es e p a r a t e dn u m e r a li m a g e sa r ef e di n t op r e p r o c e s s i n gs t e p ， i n c l u d i n gs m o o t h i n g ，n o i s er e m o v a l ，s l a n tc o r r e c t i o n a n dn o r m a l i z a t i o nt h e n ， s e v e r a lk i n d so ff e a t u r ee x t r a c t i o nm e t h o d sa r ea p p l i e di nf a c i l i t yo ff u t u r ef u s i o no f c l a s s i f i e r s i nt r a i n i n gp h a s eo fs i n g l ec l a s s i f i e r ，u n s u p e r v i s e dc l u s t e r i n g a n d s u p e r v i s e dl e a r n i n gm e t h o d sa r ei n t e g r a t e dt o e n s u r et h er a p i d i t ya n de f f i c i e n c yo f 中国科学院自动化所硕十学位论文 t r a i n i n g i ns u p e r v i s e dl e a r n i n gp h a s e ，g a u s s i a nm i x t u r em o d e la n dp r o b a b i l i s t i c l e a r n i n gv e c t o rq u a n t i f i c a t i o na r ec o m b i n e di n o u ra l g o r i t h mt oa c h i e v eb e t t e r r e s u l t s i nf u s i o np h a s eo fm u l t i p l yc l a s s i f i e r s ，t h ei n f l u e n c eo fo u rf r a m e w o r ki n r e c o g n i t i o na c c u r a c ya n ds p e e di sa n a l y z e d ，a n dt h ec o n c e p to fd e c i s i o np r o f i l e m a t r i xi si n t r o d u c e dt ou t i l i z et h er e s u l t i n gr e c o g n i t i o ni n f o r m a t i o no fe a c hc l a s s i f i e r f u l l y , a l s ow ea d v a n c ea l li m p r o v e dd e c i s i o nt e m p l a t eb a s e df u s i o na l g o r i t h m a t l a s t ，t h er e s u l to fo u rs y s t e mi sp r e s e n t e dt oc o m p a r ew i t ho t h e ri n t e g r a t i o nm e t h o d s i tc a nb es e e nt h a to u rf u s i o ns t r a t e g ya c h i e v e sb e t t e rr e s u l t ，9 9 2 2 a c c u r a c yr a t e o nt h el a r g ep a t t e r ns e to fc h a r a c t e rr e c o g n i t i o ne n g i n e e r i n gc e n t e ri ni n s t i t u t eo f a u t o m a t i o n ，c h i n aa c a d e m yo fs c i e n c e k e y w o r d s ：h a n d w r i t t e nn u m e r a lr e c o g n i t i o n ，m a c h i n e l e a r n i n g ，c l u s t e r i n g ， m u l t i p l ec l a s s i f i e rf u s i o n 2 独创性声明 本人声明所成交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特n ) j n 以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果。与我一同工作的同志对本研究所做的任何贡献 均已在论文中作了明确地说明并表示了谢意。 签名：銎也聋一日期 枷j ，玛 关于论文使用授权的说明 本人完全了解中国科学院自动化研究所有关保留、使用学位论文的规定，即： 中国科学院自动化研究所有权保留送交论文的复印件，允许论文被查阅和借阅； 可以公布论文的全部或部分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 繇强一翩虢幽缉 几期：迎! ! ! 丛 第一章绪论 1 1 模式和模式识别 第一章绪论 模式识别是2 0 世纪6 0 年代发展起来的一门学科。目前，这一技术己在语 音识别、文字识别、图象识别等领域得到广泛的、成功的应用。但由于识别问 题的复杂性，它距离人类的识别能力还有相当大的差距，离人们的期望还有很 长的距离。因此，它仍然只是一门发展中的新兴学科，新的理论和方法层出不 穷；同时，与其它学科如人工智能的相互结合和相互渗透，不断推动模式识别 的研究向前发展。 模式识别的目的是对未知的样本，判别出它所在的类别。人类的模式识别能 力使得人们可以很好地认识周围的环境并与之交流，如果计算机也具有类似的 能力，那么其智能程度将会大大提高，可以发挥更大的功效，更好地为人类服 务。 柬蛔梗蒜 图卜1 模式识别系统框剧 上图显示了一个模式识别系统的框图。可见，模式识别系统主要山网个部 分组成：数据获取、预处理、特征提取和选择、分类决策。数据获取是把识别 对象转化为计算机可处理的矩阵向量的过程；预处理是去除原始数据中包含的 噪声和二f 扰的过程；特征抽取是原始数据经过处理得到能够反映识别对象属性 的特性的过程；特征抽取得到的特征数据往往数量庞大，而且彼此可能相关而 不独立，为更好地进行分类，还需迸一步压缩特征向量的维数，即从已得到的 特征中“选择”更能反映分类本质的特征，这就是特征选择的过程。最后应用 识别理论进行决策和分类，得到输出结果。以上就是模式识别的基本概念与内 容。 更般地说，模式识别系统由相互联系的两火部分组成，即特征提取器和 分类器。通常设计模式识别系统时，分类标准是人为从系统外给定的，通过学 第一章绪论 习过程使系统能完成特定的学习任务。这种方法的缺点是系统的学习能力有限。 1 2 脱机手写数字识别 手写数字识另1 ( h a n d w r i t t e nn u m e r a lr e c o g n i t i o n ) 是光学字符识别技术( o c r ) 的一个分支，它研究的对象是：如何利用电子计算机自动辨认人手写在纸张上 的阿拉伯数字。在整个o c r 领域中，最为困难的就是脱机手写字符的识别。到 目前为止，尽管研究工作者们已在此领域取得长足进步，但距实用还有一定距 离。而在脱机手写数字识别这个方向已经推广到各种实际应用中，作为手写数 据高速自动录入的一种解决方案，节省了大量的人力物力。 对于脱机手写字符识别问题而言，最重要的三个方面就是预处理、特征提取 和分类器设计。预处理的主要目的是消除手写字符的变形；对特征的分析决定 了对字符特点的描述，对给定的数字图像，提取的特征应该尽可能有效地表征 其中的字符特点，为进一步的处理作准备；分类器赠根据提取的特征和已获得 的知识做最后决策。 1 2 1 特征提取 在过去的五十年中，研究工作者们提出了多种提取手写体字符的有效特征的 方法。总的来说，这些方法分为两大类别：全局分析与局部分析。在全局分析 中，常用的方法如模板匹配、象素密度度量、矩、特征点、数学变换( 如傅立 叶、w a l s h 、h a d a m a r d 变换) 等。这类的特征常常和统计分类方法一起使用。局 部分析则主要从字符的轮廓或骨架上提取字符形状的基本特征，包括：圈、端 点、节点、弧、突起、凹陷、笔画等等。与这些结构特征配合使用的往往是句 法分类方法。 1 2 2 分类器设计 根据以前研究者的工作，分类器可分为三大类别：神经系统方法、统计方法 以及结构方法。目前的实用系统中，往往是三者结合使用。导致分类器的误识 原因主要有两个：字符图像质量不高和分类器识别能力不够。原始文档质量、 图像扫描和预处理过程都可能引入噪声产生低质量的图像，从而导致分类器的 第一章绪论 识别能力下降。另方面，从分类器角度来说，分类器设计不当或者训练方法 上的问题也可很能导致识别能力不强。 1 2 2 ，1 神经系统方法 神经系统方法用目前人类在认知心理学上的理论，用计算机来模拟人脑神经 元的活动，并取得了显著的效果。如人工神经网络( a n n ) 8 7 ，目前已经是使 用最广泛的识别方法之一。 人工神经网络是一种模拟人脑神经元细胞的网络结构，它是由大量简单的基 本元件一神经元相互连接成的自适应非线性动态系统。a n n 中的各个神经元的 结构与功能较为简单，但大量的简单神经元的组合却可以非常复杂，从而a n n 具有一定的自适应的学习与组织能力，组成网络的各个“细胞”可以并行工作，并 可以通过调整“细胞”间的连接系数完成分类、识别等复杂的功能。 a n n 可以作为单纯的分类器( 不包含特征提取、选择) ，也可以用作功能完 善的分类器。在类别数目较少的分类问题中，常常将字符的图象点阵直接作为 神经阏络的输入。不同于传统的模式识别方法，在这种情况下，神经网络所“提 取”的特征并无明显的物理含义，而是储存在神经物理中各个神经元的连接之 中，省去了由人来决定特征提取的方法与实现过程。此外，a n n 分类器是一种 非线件的分类器，它可以提供我们很难想象到的复杂的类问分界面，为复杂分 类问题的解决提供了一种可能的解决方式。 目前，我们对人类的认知方法、人脑的工作方式以及a n n 本身的许多问题 还没有找到完美的答案，目前对于神经元的研究还很不完善，所以无法确定a n n 的工作方式是否与人脑神经元的运作方式相同，这也限制了它的进一步发展。 1 2 2 2 统计方法 统计决策论发展较早，理论也较成熟，其思想是提取待识别模式的的一组统 计特征，然后按照一定准则所确定的决策函数进行分类判决。因为统计方法利 用从输入数据得到的统计信息构造决策面，因而对特征提取过程中的噪声和变 形不敏感。 第一章绪论 一种直观的、像素级的统计分类方法是模板匹配或称矩阵匹配。在模板匹配 中，单个的图像像素被用作特征。输入图像与每个字符类别对应的模板( 原型) 集相匹配，找到最相似者，其类别作为识别结果。显然，这里相似度的度量标 准是非常重要的问题。一般的规则是，如果待识别字符图像中的某个像素与模 板图像中的对应像素相同，则相似度增加；如果对应的像素不同则相似度减少。 相似度最大的模板所属类别即为未知样本的类别。 模板匹配的局限性在于：由于待识别的字符可能处于不同的字体，因而同一 类别中可能需要存储较多类型的模板图像：而且对于手写体字符，模板匹配的 相似度度量标准很难用一个比较通用的函数表达。因而，模板匹配往往用于要 求比较固定的场合。 研究者们提出了多种算法以提高模扳匹配方法对于变形字符的鲁棒性，如 a k j 等提出的基于变形能量的模板匹配 8 8 】以及t o r u 提出的基于局部仿射变换 的模板匹配算法 8 9 1 。对于手写体数字识别而言，类别虽然只有十种，而且笔划 简单，但同一数字写法千差万别，各个地区的人的书写带有明显的区域特性， 因而模板匹配的方法很难做到高识别率的数字识别系统。 统计方法的缺点是细分能力较弱，区分相似字符的能力差，对特征信息的统 计建模比较困难。 1 2 2 3 结构方法 结构方法中每个样本类别由结构描述或者结构表征来定义，识别过程就是 求结构相似度的过程。结构分类方法利用结构信息和决策规则来对字符进行分 类。结构特征的定义可以是字符笔画、字符中的空洞以及其它字符属性。对于 输入的字符图像，先提取结构特征，然后利用基于规则的方法进行识别。结构 分类方法的难点在于有效特征集和规则的选取。 1 3 手写体数字识别技术的研究与应用 1 3 1 研究的实际背景 字符识别处理的信息可分为两大类：一类是文字信息，处理的主要是用各幽 家、各民族的文字( 如：汉字、英文等) 书写或印刷的文本信息：另一类是数 第立绪论 据信息，主要是由阿拉伯数字及少量特殊符号组成的各种编号和统计数据，如 邮政编码、统计报表、财务报表、银行票据等等，处理这类信息的核心技术是 手写数字识别。比如我国大力推广的“三金”工程，在很大程度上要依赖数据 信息的输入，如果能通过手写数字识别技术实现信息的自动录入，无疑会促进 这一一事业的进展。因此，手写数字的识别研究有着重大的现实意义，一旦研究 成功并投入应用，将产生巨大的社会和经济效益。 1 3 2 研究的理论意义 手写数字识别作为模式识别领域的一个重要问题，也有着重要的理论价值： l ，阿拉伯数字是唯一的被世界各国通用的符号，对手写数字识别的研究基本上 与文化背景无关，在这一领域大家可以探讨，比较各种研究方法； 2 由于数字识别的类别数较小，有助于做深入分析及验证一些新的理论。这方 面最明显的例子就是人工神经网络，相当部分的人工神经网络模型都以手写 数字识别作为具体的实验平台，验证理论的有效性，评价各种方法的优缺点； 3 尽管人们对手写数字的识别已从事了很长时问的研究，并己取得了很多成 果，但到目前为止机器的识别本领还无法与人的认知能力相比，这仍是一个有 难度的开放问题； 4 手写数字的识别方法很容易推广到其它一些相关问题。 1 3 3 基干手写数字识别的典型应用 手写数字识别有着极为广泛的应用前景，这也正是它受到世界各国的研究l = 作者重视的一个主要原因。 1 手写数字i ： 别在大规模数据统计中的应用： 在大规模的数据统计( 如：行业年鉴、人 _ _ l 普查等) 中，需要输入大量的数据， 以前完全要手工输入，则需要耗费大量的人力和物力。近年来在这类工作中采 用o c r 技术已成为一种趋势。因为在这种应用中，数据的录入是集中组织的，所 以往往可以通过号门设计表格和对书写施加限制以便于机器的自动识别。 2 ，手写数字识别在财务、税务、金融领域中的应用： 财务、税务、会融是手写数字识别大有可为的领域。随着我国经济的迅速发 第一。章绪论 展，每天等待处理的财务、税务报表、支票、付款单等越来越多。如果能把它 们用计算机自动处理，无疑可以节约大量的时间、金钱和劳力。与上面提到的 统计报表处理相比，在这个领域的应用难度更大，原因有：1 、对识别的精度要 求更高；2 、处理的表格往往不止一种，一个系统应能智能地同时处理若干种表 格；3 、由于处理贯穿于整个日常工作之中，因而书写者的写法往往比较自由， 不受到表格等的约束。 3 手写数字识别在邮件分拣中的应用： 随着人们生活水平的提高，经济活动的发展，通信联系的需求使信函的互换 量大幅度增加，我国函件业务量也在不断增长，业务量的急剧上升使得邮件的 分拣自动化成为大势所趋。 随着国家信息化进程的加快，手写数字识别的应用需求将越来越广泛，因此 应当加强这方面的研究工作。当前应用系统的性能的关键与瓶颈仍然在于手写 数字识别核心算法性能上。 第二章手写数字识别中的机器学爿 第二章手写数字识别中的机器学习 2 1 机器学习概述 机器学习致力于研究如何建立使计算机能够根据经验自动提高处理性能的 算法。在机器学习的模型中一般包括四个部分，即环境，知识库，学习环节和 执行环节。环境和知识库是以某种知识表示形式表达的信息的集合，分别代表 外界信息来源和系统具有的知识。学习环节和执行环节代表两个过程。其中学 习环节处理环境提供的信息，以便改善知识库中显式知识。而执行环节利用知 识更新库中的知识来完成某种任务，并把执行中获得的信息回送给予学习环节。 按照学习过程中有无教师指导，机器学习一般分为两类：非监督学习和监督 学习。在手写数字识别这个典型的机器学习任务中，这两种学习方法都频繁地 被用到。 2 2 非监督学习 2 2 1 定义 非监督学习即聚类，可以定义为将一群物体组织为若干个内部成员相似的群 体的过程；作为一种反映数据特征的手段，聚类的目的是使数据样本的类内相 似性最大，而使类i n j 相似性最小。大体上来说，聚类方法分为两种：分割聚类 ( p a r t i t i o n a lc l u s t e r i n g ) 和分层聚类( h i e r a r c h i c a lc l u s t e r i n g ) 。 聚类作为一种数据分析的手段，经过几十年的发展，已经形成了多种具体方 法。然而，处理实际问题时，面对的主要挑战并不是聚类算法形式的选择，而 是算法背后钊对不同问题的优化思想的选择。优化目标不同时，得到的聚类结 果往往会大不相同；因而，怎样确定聚类效果评价标准，根据具体样本的特点 选择算法以尽量避免误分类，是聚类时需要考虑的首要问题。一般来况，评价 聚类算法好坏的标准体现在：1 ) 处理噪声的有效程度；2 ) 能否反映任意形状的 类：3 ) 输入样本数据是否顺序无关：4 ) 高维样本情况下的运算效率；5 ) 输入 参数的个数等方面。目前的聚类算法在这些方面还没有达到让人满意的程度。 事1 史上，所有的聚类算法都对输入的样本数据作出了或多或少的先验假设， 如预定义的距离( 相似性衡量) 函数的合理性、数据在所定义的样本空间是f 第二章手写数字识别中的机器学习 确可分的，或者高斯混合模型中的类中样本服从高斯分布等等，而至今尚没有 办法从理论上对某些假设作出完整的评价。 可以用集合论中的子集和元素来代表模式类和模式。在所有模式组成的集 合m 中定义一个相似性度量r ，根据这种度量关系将m 分成若干子集m ：u 吖， 且m ，n m = 矿( 7 ) 。同一子集m ，中的各个元素在该相似性量度r 下是不可区 分的，而不同子集中的元素则被严格区分。r 的定义有很多种并且随具体问题不 同而相异，最广泛应用的是在空阳j 中定义的某种距离的非增函数。这种将m 分 成若干子类的过程就是聚类的过程。 随着研究的不断深入，聚类的理论和具体方法获得了极大的发展，形成了 若干主要分支。如分层聚类算法 3 0 3 8 】，它将数据按相似关系组织成一个有层 次的树状结构；基于密度的方法认为数据点的高密区是聚类所在的区域 3 3 9 ； 图论中最小生成树方法先以数据点作为顶点建立其最小生成树，再删除某些相 对较长的边，如此反复最后得到若干不连通的子图就是聚类 4 0 】；混合密度分解 方法将数据点看作是由某些数据源按一定的概率分布产生的，并用最大似然法 或e m 算法对有关参数进行确定【1 4 1 】。 2 2 1 1分割聚类 分割聚类的本质是将所有输入样本用若干个具有代表意义的中心点来表 征，这些中，i i , 点形成字典用于匹配。一般分割聚类算法输入样本集s 和整数k ， 输出结果就是子类s ，s ：，一s 。；这样，在定义花费函数c ： x ：x s ) 斗m + 后， 分割聚类就转化为优化过程，使总花费函数c ( s ，) 最小化。常用的花费函数如 i = 1 最著名的平方和函数 和k 均值算法中定义的 s 11 只1 c ( s ，) = ( d ( x 知：) ) 2 ( 2 _ 1 ) l s “ c ( 8 ，) = e a ( 7 。，x ：) ( 2 2 ) 第二章手写数字i = ；! 别中的机器学习 其它还有诸如c ( s ，) = ，m a x d ( x ：。，x ：) 等。 ，e 引入优化算法的优点是简单易于程序实现，但往往引起n p 困难，而且上例 分割聚类优化准则具有普遍缺陷即聚类结果偏向于超球型结构，同时对“噪声” 处理程度不够。其后提出的统计混合模型则在包含以上优化模型的基础上修正 了部分缺陷 1 8 1 9 2 0 。基于密度的聚类 3 3 9 考虑了类的形状和噪声，认为类 是样本空间中分布最“密集”的地区，与之紧密联系的是图论聚类 2 2 2 3 2 4 】 4 0 】。 2 2 1 2 分层聚类 分层聚类本质是分类的逐步细化求精、自上而下或自下而上的过程，适用于 样本集s 不能分成若干个完全互不相干的子集的情况，其目的是产生一棵树 t ( s 1 ，使得s 为根，叶子节点是s 中的单个元素，内部节点定义为相应子节点的 集合，树中每一条路径将遍历的元素集合的元素之间的联系会越来越紧密。 分层聚类算法有两种，即白上而下和自f 而上。前者是分裂算法，不断递归 细分s 直至叶子节点足够小；后者是聚集算法，不断合并某些小数据集合直至 产生s ，实现起来比前者简单一些。 大体上说，自下而上的分层聚类就是将所有样本分配到互斥集合 s ，s ：，s 。，根据花费函数找到一对( s ，s ，) 使得其合并的“代价”最小，用 s u s 代替s ，和s ，如此重复直至单个集合即s 。 作为优化过程，同样可以定义平方和函数为花费函数，集合合并时选取使总 花费增加最小的方案。其它常用的花费函数如 a v e r a g e - l i n k ：丽i 荟影，v p 【2 _ 4 ) c o m p l e t e l i n k ： 嚣黑_ ，d ( x i , x ) ( 2 5 ) 第二章手写数字识别中的机器学习 这些基于中心或基于所有点的、以最小化方差为目标的优化方法，类问的大小 差别以及类形状是否为超球有很大的影响，另外类间噪声也往往会引起误分类。 改进的方法如：基于信息论的方法利用熵增益作为花费函数，可以避免使用方 差而获得样本空间的数据组织结构 4 1 1 5 1 ；对于不同的聚类问题，考虑到其样本 空间的数学属性各异，因而根据具体情况定义样本间的相似度( 距离) ，建立相 似矩阵( 典型如距离矩阵) 用于聚类：s u d i p t og u h a 等人提出的多代表分层聚类 对于噪声有很好的鲁棒性，能够较好地克服类形状和大小所引起的问题 2 6 1 。 2 2 2 聚类算法及其比较 2 2 2 1k 均值聚类及相关 k - 均值方法是一种典型的矢量量化( v e c t o rq u a n t i z a t i o n ) 方法。假设样本集中 的样本分为m 类，x 为输入样本，z ，为第i 类类中心，则整体优化函数可写为 盯吖 d = d ，= p ( x 6 c ) e d ( x ，z ，) l x c ，】 ( 2 - 6 ) j = li = l 给定一个训练样本集 x 。，1 t n ，类c 中出现样本数量计为髟，则 p ( x 旧) = 1 k i ，p ( z ) = k i t ，故 d = i 1 d ( x ，z ，) ( 2 _ 7 ) 1 j e ( 如果d ( x ，z ，) 定义为欧氏距离q z i ) ( x z ，) ，则由v 。d i = 0 得到 i ：= iy x 7 2 - 8 t z - 6 、) z 2 7 己1 1 、c a ( x ，z ，) 采用m a h a l a n o b i s 距离( x zs ) j 1 ( x - - z i ) 时可以得到同样的结果。 k 均值聚类算法就是以此为依据，不断迭代直至收敛的过程。 理论上说，k 均值算法只能逼近局部最优而非全局最优，且对初值的选取 敏感，但因其简单易行，当类中样本分布紧凑、特征空间具有较好的可分离性 时能得到较好的结果，因而褥到了广泛的应用。以此为基础发展而来的模糊k 一 均值算法引入模糊判别函数，认为每个样本以某概率属于每个类，提高了收敛 性，但依然依赖于预先指定的聚类数目。 第一章手写数字识别。 】的机器学习 s u 和c h o u 对样本点的分布情况作了合理的假设，即样本空f 可中每一类的样 本点关于该类中心具有对称性【7 ；输入样本x ，和类c ( 类中心为c ) 之间的对称 性距离定义为 媳，a - 鲁r a i n 悱i i ( x ，j 。i t + f f x i - - c | f ) ( 2 - 9 ) 当x 在c 中有完全对称的样本时，d ，( x ，c ) 取得最小值0 。将k 均值算法与对 称性距离相结合，s u 和c h o u 提出了改进的基于类对称距离的s b k m 算法，并 且在人脸检测中取得了不错的效果。但是，由于确定对称性距离需要遍历整个 样本集，计算量很大。 考虑到k 一均值算法中可能引起的退化，即初值选取不当导致算法终止时产 生无样本的空类，h a n s e n 等提出了引入启发式策略的h 一均值和j 一均值算法 8 】。 相比k 一均值，h 一均值在找到局部最优后，加入了检查退化的步骤，用距离自身 类中心距离最远的f 个样本点代替t 个退化类( 空类) 的类中心，并再次进行迭 代进行样本的重分布。 定义其自身为类中心的样本点为被“占据”的样本点，j 一均值算法引入了类 中心向相邻的、未被“占据”的样本点重定位的过程。试验结果表明，引入启 发式策略对类中心重定位，不仅防止了退化，而且有可能跳出传统k 均值的局 部最优，使聚类结果有了显著的改善。 2 2 2 ，2 高斯混合模型 v q 将输入样本空间分割为分离区域而不考虑原始数据的初始分布，潜在的 问题是导致数据分布结构的破坏：而允许交迭的类概率密度函数的引入则可以 克服这一缺点。 假设输入向量x 1 ，x ，x 。来自于k 个未知的分布e ，e ，。，x ，来自于，的 概率密度是，( x ，i 目) ，其中0 未知，x ，属 二类e ，的概率是r ；，r ：= l 。目标 是最大化似然函数 女 l ( a ，f ) = 兀r ：，( x ，f 吕) ( 2 一l o ) 星三童王要塑主望型堕塑塑堂望 为了便于分析，加入限制条件：每个样本只能属于一个类，并将，属于的类 记为y ，则 l ( o ，f ) _ 乃，( x ，1 0 ) ( 2 - 11 ) r = l 合理假设，) 服从高斯分布，均值“和协方差矩阵未知。方便起见定义 为对角阵，则上式等价于均方和准则，可以由e m 算法确定参数、y ， 然而魍、，能否根据各个分布完全自由变化从而找到一个全局最优依然未知， 为对角阵也是一个过严的限制条件。b a n f i e l d 和r a f t e r y 利用，的半正定性质， 将其分解为，= d ，a ，科，a ，= 爿，丑，为，的特征值，其中2 反映类的大小， a ，反映类的形状 4 l 】。同时考虑到噪声的影响，b a n f i e l d 和r a f l e r y 用泊松过程 对模型进行了修正。 h w a n g 等在高斯混合模型的建立过程中利用h e b b 规则引入有监督的竞争学 习 1 7 】；j l a r s e n 等则提出了在有标签和无标签样本混合的情况下利用高斯混合 模型的概率分层聚类算法【1 8 】，利用后验概率作为权重对类中心均值和协方差进 行软学习，类间的相似度计算考虑了类中样本的分布密度。 总的来说，高斯混合模型的计算效率不高，需要的人工干预比较多，同时对 样本高斯分布的先验假设在某些应用中证明不可行：但由于可以有效利用对类 中样本分布情况的先验知识，提高识别效果，因而依然得到了广泛应用。 2 2 2 3 自组织特征映射( s o f m ) 与增长细胞模型( g c s ) 在神经网络中通过邻近单元的相互学习( 竞争学习) ，可以自适应地发展成 为对于不同性质信号敏感的区域。s o f m 就是在无监督情况下将高维输入信号变 换到二维离散网格并保持一定拓扑有序性的自组织神经网络【1 5 3 8 】。 与s o f m 相似，g c s 模型也是利用h e b b 规则修改权值，在激励区、弱激励 区、抑制区形成“墨西哥草帽”效果并实现数据聚类的一种自适应算法 f 1 0 1 h d 2 。在无监督的情况下，g c s 能通过细胞的不断加入和删除，最终自 动找到合适的网络拓手卜结构而不需要预先指定。在理想的结果状态下，每个输 入样本出现在各细胞( 类中心) 处的概率基本相等，对应的信息熵值达到最大， 反映出g c s 在估计样本的未知概率密度分布方面的良好能力。 s o f t 和g c s 的共同特点和目标是：样本空间中相似的输入样本映射到拓 第 二章手写数字识别中的机器学 j 扑空间中的相邻点；拓扑空间中的相邻点都由样本空间中相似的样本映射而柬； 从拓扑空间中能够得到样本空间的未知概率密度的部分信息，凶而s o f m 和 g c s 的算法步骤中有很多相同的部分。 算法2 1s o f m g c s 算法 1 初始化拓扑结构和相应权值； 2 从样本集中输入样本x ，由指定的距离函数确定最佳匹配( 获胜) 单元 ( 竞争过程) ； 3 确定邻域a ( 协作过程) ，并且根据t t e b b 规则修改权值 w ，( n + 1 ) = w ，( n ) + r l ( n ) x ( n ) 一( 胛) 】，j a ，( 儿) w j ( n + 1 ) = w ，( ) ， 其它 4 ( g c s 独有) ：当满足特定条件时增加或删除节点单元： 5 n 卜h + 1 ，返回2 直到满足结束条件。 结束 比较而言，s o f m 需要预先定义二维的网格拓扑结构，而g c s 只需要预先 取得少量细胞节点，其拓扑结构通过学习利用细胞的不断加入和删除发展而来， 因而针对具体问题g c s 有更好的适应性。还有两种与g c s 方法类似的模型是增 长神经气体( g r o w i n gn e u r a lg a s ，g n g ) 1 6 1 黼( g r o w i n g g r i d ，g g ) 1 3 】。 v 1 a s s i s 等将贝叶斯决策规则m a p 与g c s 聚类过程相结合，提出概率 g c s ( p r o b a b i l i s t i cg c s ，p g c s ) 1 4 。假设类中样本服从多维高斯分布 p ( x ；肛。，。) = ( 2 万) 一，7 2 1 。l 1 ”e x p ( - i 1 ( x p 1 ) ：1 ( x i l t ) 7 ) ( 2 1 2 ) 先验概率估计： 丌= i l 善n p ( 七l k ) ( 2 - 1 3 ) 对输入样 本 x ， ， 确 定其所 属类 k如果 p ( lx 。) ：m “ p ( jx ) ) = m a x 以p 。c ，) ) ，= 1 ，k ，相应调整类中心和类方差 p ? + 1 = l l ? + _ ：”“1 i x 。l 一妒1 ( 2 - 1 4 ) 一 苎三差王里塑! 望型塑塑墨堂望 露。”= 西押+ 讲”“ ( x 。，一p ) ( x 。一i i ：，j ) ) 7 一蠢枷j ( 2 15 ) 细胞节点的插入删除位置分别为： 硼字唧n 声( 9 ) = m um ) n ( 口，厅，+ 盘，# ) ( 2 16 ) 9 9 一 9 盯： 胃。 p g c s 中细胞节点的插入和删除考虑了样本的先验分布以及类的方差，而且 聚类过程中同时调整类中心和方差，所以能得到更好的聚类效果。 2 2 2 4 多代表聚类( c l u s t e r i n gu s i n gr e p r e s e n t a t i v e s c u r e ) 在一般的分割聚类和分层聚类方法中，各类往往只由类中心来代表，即主观 假设类形状为超球；而且优化目标函数往往以最小化方差为目标，从而当类的 形状和大小相差很大或存在噪声时往往导致误分类例如著名的“锁链效应”。 s u d i p r og u h a 等提出的c u r e 分层聚类算法p 6 具有非常简洁的思想。每个 类的所有样本点不再由单个类中心代表，而是由多个散布于类中、能够表现类 几何形状的样本点代表；同时为了消除类外围噪声带来的影响，这些散布的样 本点向类中心“收缩”一个比例因子。力求在表现类形状的同时减小噪声的扰 动。正是这样的特点使得c u r e 能够较好她分辨任意形状的类，同时对噪声具 有很好的鲁棒性。 记初始代表点集合r