（管理科学与工程专业论文）基于rbfnn的复杂样本分类研究.pdf

中文摘要 径向基函数神经网络( r a d i a lb a s i sf u n c t i o nn e u r a ln e t w o r k ，r b f n n ) 是一种 三层前馈性网络，具有泛化能力强、收敛速发快等特点，引起各领域工作者的极 大关注，已成功的运用j 二系统识别、数捌挖掘等许多领域。本文在r b f n n 的基 础上对复杂样本分类问题进行了较深入的研究，主要包括以下几个方面： 在普通的两阶段构造r b f n n 基础上，把最近邻衰减聚类的思想与误差平方 和准则结合起来，提出了一种r b f n n 三阶段学习算法。首先利用基于最近邻衰 减半径的聚类算法确定隐层中心的初始结构，同时利用样本信息动态控制最小聚 类半径，既防止了固定半径聚类较差的自适应性，避免了衰减最小半径经验值的 多次试探确定，又有效降低了半径无限缩减引起的过学习现蒙的产生。然后，加 入了利用误差平方和对由衰减聚类确定的中心点进行微调的阶段，通过考察样本 移动对其的影响，调整中一1 1 , 点数值，使得结果的测试精度更高。同时利用类内类 | 、日j 距确定径基宽度，充分考虑了类m 蹲对样本聚类的影响，避免了统一的径基宽 度可能引起的分类区域过度取叠。域后利j h 伪逆法确定权值。经i r i s 、w i n e s 和 g l a s s 数据集的仿真实验验证该算法确实具有较强的分类能力。 以提高r b f n n 分类能力为出发点，结合遗传算法( g e n e t i ca l g o r i t h m ，a a ) 群体并行搜索能力，提出了一种有效的g a ，r b f n n 学习算法。该算法在r b f n n 三阶段学习算法确定网络初始结构的基础k ，加入控制向量，设计了包含整个网 络隐节点结构和相关参数的矩阵式混合编码方式，以及相应的交叉和变异算予， 权值由伪逆法求解确定。该算法快速有效，既使得基f 衰减聚类的最近邻学习算 法在分类问题上的优势得到保障和扩充，又使得遗传算法的全局搜索能力与其的 结合在根本上改善了传统r b f n n 训练方法的效果，具有较强的复杂样本分类能 力。经i r i s 、w i n e s 和g l a s s 数据集的仿真实验验证，该算法快速有效，具有较强 的复杂样本分类能力。 关键词：r b f n n 遗传算法衰减半径聚类误差半方和混合编码分类能力 a b s t r a c t r a d i a lb a s i sf u n c t i o nn e u r a 】n e t w o r kf r b f n n ) c a nb ev i e w e da sa t h r e e - l a y e r f e e d f o r w a r dn e u r a ln e t w o r k w h i c hh a sd r a w nm u c ha t t e n t i o nd u et oi t sg o o d g e n e r a l i z a t i o na b i l i t ya n df a s tc o n v e r g e n c ea n di th a sb e e ns h c c e s s f u l l yu s e di nm a n y f i e l d s ，s u c ha ss y s t e mi d e n t i f i c a t i o na n dd a t am i n i n g a i m i n ga ti m p r o v i n gt h ea b i l i t y o ft h er b f n nf o rc o m p l e xc l a s s i f i c a t i o n s o m er e s e a r c h e sb a s e do nr b f n nh a v e b e e ns t u d i e di nt h i st h e s i ss u b s t a n t i a l l ya sf o l l o w s ： at h r e e p h a s er b f n nl e a r n i n ga l g o r i t h mi sp r o p o s e di nt h i st h e s i s w h i c h c o m b i n e st h ed e c a y e dr a d i u ss e l e c t i o nc l u s t e r i n g ( d r s c ) m e t h o dw i t ht h es u i s q u a r e de r r o r ( s s e ) r u l e ，i e ，a ne x t r at u n i n gp r o c e s s f i r s t l y ，t h ei n i t i a lh i d d e n s t r u c t u r eo ft h en e t w o r ki sd e t e r m i n e db yd r s c ，a n dt h em i n i m u md e c a y e dr a d i u sf o r c l u s t e r i n gi sa d j u s t e ds i m u l t a n e o u s l yr a t h e rt h a nb e i n gk e p tf i x e d ，w h i c hi m p r o v e st h e s e l f - a d a p t i n ga b i l i t yo ft h em i n i m u mr a d i u sa n dp r e v e n t sm a n yt r i a l sb e f o r eg e t t i n gt o t h eo p t i m u mn e t w o r k ，a n da v o i d st h eo v e r 1 e a r n i n ga st h er a d i u sd e c r e a s e si n f i n i t e l y t h e nt h ep o s i t i o n so ft h eh i d d e nl a y e rc e n t e r sa r ea d j u s t i n gs l i g h t l yw i t ht h es s er u l e b yc o n s i d e r i n gt h ee f f e c tw h e nac e r t a i ns a m p l e sa r em o v e df r o mo n ec l a s st oa n o t h e r t h ew i t l l i n c l u s t e ra n db e t w e e n c l u s t e rd i s t a n c e sa r eh e r ee m p l o y e dt oc a l c u l a t et h e c o r r e s p o n d i n gr a d i u sw i d t h s t h eb e t w e e n c l u s t e rd i s t a n c e sa r et a k e ni n t oa c c o u n t e s p e c i a l l yi nt h i st h e s i s w h i c ha r ea b l et os h r i n kt h er e g i o no fo v e r l a p f i n a l l yt h e p s e u d o i n v e r s ea l g o r i t h mj su “l i z e dt ot r a i nt h ew e i g h t sb e t w e e nt h eh i d d e nl a y e ra n d t h eo u t p u tl a y e r t h ee x p e r i m e n t sa r ei r n p l e m e n t e do ni r i s ，w i n e sa n dg l a s sd a t a s e t s ， w h i c hs h o wt h a tt h ep r o p o s e dr b f n nt r a | n i n ga l g o r i t h mh a sab e t t e rc l a s s i f i c a t i o n a b i l i t yc o m p a r e dw i t ht h ec o n v e n t i o n a jm e t h o d s a na d a p t i v el e a r n i n ga l g o r i t h m ，e g g a - r b f n n ，i sp r e s e n t e d ，t ob u i l da r b f n nm o d e lb ye m p l o y i n gt h eg e n e t i ca l g o r i t h m ( g a ) sp a r a l l e l s e a r c ha b i l i t y w i t ht h ea i ma ti m p r o v i n gt h ec l a s s i f i c a t i o na c c u r a c yo ft h er b f n n f i r s t l y ，t h e i n i t i a ln e t w o r kh i d d e ns t r u c t u r eo far b f n nm o d e ii sd e t e r m i n e db yt h et h r e e - p h r a s e l e a r n i n ga l g o r i t h m t h e nt h eh i d d e nc e n t e r so far b f n na r em o d i f i e db yas p e c i a l l y d e s i g n e dg a ，w h i c hi sb a s e do nt h em a t r i x f o r mm i x e de n c o d i n gs c h e m ew i t ha c o n t r o lv e c t o rf o rr e g u l a t i n gt h es t r u c t u r eo far b f n n a n dt h en e wg e n e t i co p e r a t o r s a r ep r e s e n t e dc o r r e s p o n d i n g l yt h ep s e u d o i n v e r s ea l g o r i t h mi sa d o p t e dt ot r a i nt l l e w e i g h t s f i n a l l y e x p e r i m e n t sa r ei r a p l e m e n t e do nd a t a s e t sa si r i s ，w i n e s ，a n dg l a s s ， w h i c hs h o wt h a tt h ep r o p o s e da l g o r i t b mh a sp e r f o r m e db e t t e rc o m p a r e dw i mt h e c o n v e n t i o n a im e t h o d s k e yw o r d s ：r b f n n ，g a ，d e c a y e dr a d i u sc l u s t e r i n g ，s s e ，m i x e dc o d i n g ， c l a s s i f i c a t i o na b i l i t y 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得墨注盘鲎或其他教育机构的学位或证 书丽使用过的材料。与我一同工作的同志对本研究所傲的 壬j 可贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名；忉l 摹签字目期：伽巾年6 月形日 i 。 学位论文版权使用授权书 本学位论文作者完全了解鑫盎盘堂有关保留、使用学位论文的规定。 特授权墨鲞盎堂可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者繇妒1 多 签字日期：略年占月p 阳 聊虢辔 签字日期：如哲年占月搿日 第一章绪论 第一章绪论 本章首先阐明了论文所选课题的研究背景及其所具有的研究价值，对径向基 函数神经网络( r a d i a lb a s i sf u n c t i o nn e u r a ln e t w o r k ，r b f n n ) 的发展历史作了简 要介绍，然后着重评述了分类问题的基本原理、常用方法以及神经网络学习理论， 最后综述了本文的主要内容和创新点。 1 1 选题背景与研究意义 随着网络技术的发展和计算机使用的日益广泛，电子化数据越来越多，人们 正面临“数据丰富而知识贫乏”的问题。八十年代末兴起的数据挖掘( d a t a m i n i n g ， d m ) 技术或数据库中的知识发现( k n o w l e d g ed i s c o v e r yi nd a t a b a s e s ，k d d ) 技术 为解决此问题开辟了一条道路。数据挖掘是在大量的数据中抽取隐含的、以前未 知的潜在有用信息，发现有价值的模式和数掘问关系( 知识) 的过程。被挖掘出 来的知谚 ，能够用于信息管理、查询处理、决策支持、过程控制以及许多其它应 用领域。数据库系统、人工智能、机器学习、知识获取、统计学等领域的研究人 员，都对数据挖掘表现出浓厚的兴趣：而且一些新兴的信息形式，例如在线服务 和w e b 查询系统等，也认为数据挖掘能够帮助更好地理解用户的行为，从而增 加商业机会。因此如何自动有效地从巨量信息中获取知识，是亟待解决的问题 而正确地对知识进行分类则是其中需要解决的一项重要任务。 分类问题旨在找出用于描述和区分数据类或概念的分类模型( 或分类函数) ， 以便能够使用该模型把数据库中的数据项映射到给定类别中的某一个，即预测类 标记未知的对象类。分类问题作为数据挖掘中的一个基本问题，已经被广泛研究， 其基础理论包括监督学习、半监督学习、p l s 路径建模和分类、集成分类技术、 多标签分类和p r e f e r e n c e 学习、多事例分类等，相关的分类研究包括文本分类、 w e b 页面分类，时间序列分类、图像与视频检索、计算机视觉分类和生物特征识 别分类等川。 因此分类技术被广泛应用于诸多应用领域中，诸如模式识别、数据分析、图 像处理及市场研究，并收到明显的效益。在金融方面，通过分类将市场分成有意 义的群组和部门，协助业务人员更好地集中于有促进作用的活动和设计新的市场 运动。在过程控制，质量监督方面，利用分类技术协助管理变量之间的相互作用， 自动发现某些不正常的数据分布，暴露操作过程中变化情况，协助质检部门及时 第一章绪论 注意问题发生和采取改f 措施。在信息安全方面，在对收集的审计记录进行分析 的基础上，利用分类技术对系统各不同类别用户的行为方式进行建模，结合专家 系统进行入侵检测。 分类问题已经成为数据挖掘领域中个非常活跃的研究课题【2 i d d ，本文利 用r b f n n 对复杂样本分类问题进行了研究，为构建有效的样本分类算法做出了 自己的努力。 1 2r b f n n 发展与应用 径向基函数神经网络( r a d i a lb a s i sf u n c t i o n n e u r a ln e t w o r k ，r b f n n ) 是近几 年兴起的一种单隐层前馈性网络。它以径向基函数作为隐节点激活函数，具有收 敛速度快、逼近精度高、j 阕络规模小等特点，引起各领域工作者的极大关注。 1 9 8 5 年，p o w e l l 提出了用于严格多变量差值的径向基函数r b f 方法。1 9 8 8 年，b r o o m h e a d 和l o w e 首先将r b f 用于神经网络设计之中，对r b f 和多层神 经网络进行比较【5 j ，并初步讨论了r b f 用于神经网络设计与传统插值领域的不 同特点，揭示了二者的关系，提出一种两层结构的r 8 f n n 。 生物研究发现，在生物大脑皮层区域中，局部调节及交叠的感受野( r e c e p t i v e f i e l d ) 是大脑反应的特点。基于感受野这特性，m o o d y 和d a r k e n 于1 9 8 9 年提 出一种含有局部响应特性的计算元的神经网络i “，这种网络实际上于b r o o m h e a d 和l o w e 提出的r b f n n 是一致的。同时他们还初步提出了r b f n n 的训练算法。 同年，k a c k o n 论证了r b f n n 对非线性连续函数的一致逼近性能。 之后的研究者又针对以前研究中存在的问题与不足提出许多改进的算法比 如c h e n 等人提出的o f r ( o r t h o g o n a lf o r w a r dr e g r e s s i o n ) 方法；s l e e 等人提出 的h s o l ( h i e r a r c h i c a l l ys e l f - o r g a n i z i n gl e a r n i n g ) 算法；p l a t t 提出的r a n ( r e s o u r c e a l l o c a t i n gn e t w o r k ) 连续学习算法；k a d i r k a m a n a t h a n 和n i r a n j a l l 提出的r a n e k f ( r a nv i ae x t e n d e dk a l m a nf i l t e r ) 算法等。 随着研究日渐成熟，r b f n n 由于其结构简单、算法简便，被广泛用于函数 逼近、系统t _ 别、时间序列预测、语音识别、自动控制、数据挖掘等许多领域 j 。 例如b i l l i n g s 将r b f n n 用于非线性系统识别并将其与标准的反传前馈网络进行 了比较；c h e n 将r b f n n 用于通信信道平衡；p l a t t 和k a d i r k a m a n a t h a n 将用r a n 和r a n e k f 算法训练的r b f n n 用于m a c k e y g l a s s 随机时间序列的预测； n i r a n j a n 等将r b f n n 用于静态语音识别 s a n n e r 和s l o t i n 将它用于补偿自动控 制中的非线性变量；x f u 将它用于数据挖掘中的规则提取。 第一章绪论 1 3 分类基本原理与常用方法 分类作为数据挖掘中的一种关键的数据分析方法，可以用于提取和描述重要 数据类的模型。所谓“分类”是指找出用于描述和区分数据类或概念的模型( 或 函数) ，以便能够使用该模型预测类标记未知的对象类。这种模型是通过对训练 数据集( 即类标记已知的数据对象集) 的分析而得到的。 数据分类一般分为两个阶段：第一阶段是通过对训练数据集的分析，建立一 个预测模型，该模型描述了预定的数据类集或概念集。这是一个有监督的学习过 程。第二阶段则是通过使用第一阶段建立的模型进行分类，从而达到对类标号预 测的目的。 常用的分类方法主要有决策树归纳分类、贝叶斯分类、神经网络分类和k 一 近邻分类等。以下介绍了几种主要分类方法的特点，并对它们各自适用的应用领 域进行了比较。 1 3 1 决策树归纳分类 决策树( d e c i s i o nt r e e ) 也称判定树，它是一种以搜索树的方式对数据进行分类 的方法。树中的非叶子结点表示对某一个属性的判断；每个分支表示一次判断的 输出；而叶子结点则代表得到的一个类或类分布。所以从树根到叶子结点的一条 路径就对应一条合取规则。整棵决策树对应_ 组析取表达式规则。 决策树归纳分类的过程可分为两个步骤，即第一步通过对训练数据集的分 析，从而构造一棵决策树( 其中包括数据的预处理、决策树的归纳形成、树的剪 枝等) 。其实这是建立预测模型的过程，在知识发现中也将这一过程称之为“学 习”。第二步是用建立的预测模型或从决策树中提取的分类规则进行新数据的分 类，即经过一条与从根结点到时子结点的路径对应的合取规则的测试，最后得到 数据所属的类。 决策树的传统学习算法是由h u n t 于1 9 6 6 年提出的c l s ( c o n c e p tl e a r n i n g s y s t e m ) 学习算法，其主要思想是：从棵空的决策树出发，通过增加新的判定 结点来改善原来的决策树，直至该决策树能够正确地将训练数据分类为止。这是 - s e e 自上而下递归的贪婪算法。在此基础上，提出的改进学习算法主要有： q u i n l a n 提出的i d 3 ( i n t e r a c t i v ed i c h o t o m i z e r3 ) 算法和c 4 5 算法。前者是以信息 熵的下降速度作为选取测试属性的算法；而后者则提出了被离散化的连续型属性 相对于离散变量的属性来说更容易被选取的思想。 以决策树为指导思想的学习算法的优点是：在学习过程中不需要使用者了解 很多背景知识，而只要训练数据集能够用“属性一结论”的方式表达，就能使用 第一章绪论 1 3 分类基本原理与常用方法 分类作为数据挖掘中的- 4 十关键的数摒分析方法，可以用于提取和描述重要 数据类的模型。所谓“分类”是指找出用于描述和区分数据类或概念的模型( 或 函数) ，以便能够使用该模型预测类标记未知的对象类。这种模型是通过对训练 数据集( 即类标记已知的数据对象集) 的分析而得到的川。 数据分类一般分为两个阶段：第一阶段是通过对训练数据集的分析，建立一 个预测模型，该模型描述了预定的数据类集或概念集。这是一个有监督的学习过 程。第二阶段则是通过使用第一阶段建立的模型进行分类，从而达到对类标号预 钡4 的目的。 常用的分类方法主篮有决策树归纳分类、贝叶斯分类、神经网络分类和k 近邻分类等。以下介绍了几种主要分类方法的特点，并对它们各自适用的应用领 域进行了比较。 1 3 1 决策树归纳分类 决篡树( d e c i s i o nt r e e ) 也称判定捌，它是一种以搜索树的方式对数据进行分类 的方法。树中的非叶子结点表示对巢一个属性的判断：每个分支表示次判断的 输出；而叶子结点则代表得到的一个类或类分布。所以从树根到叶子结点的一条 路径就对应一条台取规则。整棵决策树对应一组析取表达式规则。 决策树归纳分类的过程可分为两个步骤，即第一步通过对训练数据集的分 析，从而构造一棵决策树( 其中包括数据的预处理、决策树的归纳形成、树的剪 枝等) 。其实这是建立预测模型的过程，在知识发现中也将这一过程称之为“学 习”。第二步是用建立的预测模型或从决策树中提取的分类规则进行新数据的分 类，即经过条与从根结点到叶子结点的路径对应的台取规则的测试，最后锶到 数据所属的类。 决策树的传统学习算法是由h u n t 于1 9 6 6 年提出的c l s ( c o n c e p tl e a r n i n g s y s t e m ) 学习算法，其主要思想是：从一棵空的决策树出发，通过增加新的判定 结点来改善原来的决策树，直至该决策树能够正确地将训练数据分类为止。这是 - - e r 自上而下递归的贪婪算法。在此基础上，提出的改进学习算法主要有： q u i n l m l 提出的i d 3 ( i n t e r a c t l v ed i c h o t o m i z e r3 ) 算法和c 4 5 算法。前者是以信息 熵的下降速度作为选取测试属性的算法：而后者则提出了被离散化的连续型属性 相对于离散变量的属性来说更容易被选取的思想。 以决策树为指导思想的学习算法的优点足：在学习过程中不需要使用者了解 很多背景知识而只要训练数据集能够用“属性- 当；论”的方式表达，就能使用 很多背景知识，而只要训练数据集能够用“属性结论”的方式表达，就能使用 第一章绪论 浚算法进行学习省f 。由此可见，决策树分类方法比较简单，且得到的树结构容易 转换成分类规则，因此应用也比较广泛，如在语音识别、模型识别、专家系统以 及商务领域部得到了成功地应用。但是决策树分类也存在着一些问题，其中最主 要的是可伸缩性问题。因为传统的学习算法及i d 3 和c 4 5 算法，对于相对较小 的数据集非常有效，但当它被用于大型数据库挖掘时，有效性和伸缩性就会大大 降低。而且大部分决策树算法都限制训练样本驻留主存，若训练样本过大，那么 它在主存和高速缓存之间的切抵换将造成很大的开销，使效率降低。 最后要指出的是：所有的决策树都有不等价的人工神经网络表示，所以也可 以通过神经网络的训练算法来实现与决策树相同的功能1 8 j 。 1 3 2 贝叶斯分类 贝叶斯的论文关于几率性问题求解的评论奠定了贝叶斯理论的基础，经 过后继学者的不断修正与扩充，这一理论的内涵发生了较大的变化，并取得了很 大的完善。贝叶斯理论给出了信任函数在数学上的计算方法，具有稳固的数学基 础，同时也刻画了信任度与证据的一致性以及信任度随证据而变化的增量学习特 性。贝叶斯分析方法是以贝叶斯定理和贝叶斯假设为基础，其特点是用概率来表 示形式的不确定性，学习或其他形式的推理都用概率规则来实现。学习结果则表 现为随机变量的概率分布，即对不同可能性的信任程度。 在数据挖掘领域，贝叶斯方法有耆“泛的应用，其中几个较为典型的应用有： 1 用于数据分类和回归分析。 2 用于因果推理和不确定知识表达。 3 用于聚类模式发现。 数据分类的第一阶段即预测模型的建立，实质就是分类规则的发现：而第二 阶段的分类过程则是根据事物的特征向量值和其他约束条件将其分到某一类中 去。就分类问题而言，可分为确定性的分类问题和重叠性的分类问题。对于前者， 事物的特征向量唯一地对应一个类；而后者则表示某一事物属于某类的概率有多 少，但最终必须为它确定一个归属的类。在实际分类中，后者更为常见，也容易 被接受。对于第二类分类问题，用贝叶斯方法进行分类时，一般用两种方法作出 归属决定，即选择后验概率最大的类别和选择效用函数最大( 或损失最小) 的类 别。 对于数据分类，已有的成功贝叶斯模型有：朴素贝叶斯( 也称简单贝叶斯) 、 贝叶斯信念网络和贝叶斯神经网络等。朴素贝叶斯分类假定类条件独立，当这一 假定成立时，分类比较准确。由于实际应用中，变量之间很可能存在依赖性，所 以贝叶斯信念网络用概率权重来描述数据间的相关性，使之具有处理不完整、带 第章绪论 噪声数据集的能力。从理论上讲，与其他所有分类方法相比，贝叶斯分类具有最 小的出错率，但往往会由于对其应用假定的不准确，以及缺乏可用的概率数据， 造成实际情况与理论的不一致。 1 3 3 神经网络学习分类 神经网络学习算法是对前馈型神经网络采用误差反向传播的方法进行训练 从而确定网络参数的算法，是一种有监督的学习方法。在数据分类中，通过提供 的训练样本及样本所属的类，对神经网络的权值进行调整，从而使该神经网络具 有对其他样本数据进行分类的能力，现在较常用于分类问题求解的有b p 神经网 络( b p n n ) $ ! ar b f n n 。 由于神经网络需要的训练时间较长，因而较适合于有足够长训练时矧的应用 场合。在学习过程中，要确定的参数较多，但有些参数( 如拓扑结构) ，主要还 是靠经验来确定：如在开始训练之前，必须明确输入层的结点数、隐含层数，每 一隐含层的结点数和输出层的结点数。网络拓扑结构的设计是一个实验过程，它 可能影响结果训练网络的可行性；权的初值也可能影响结果的准确性。一旦网络 经过训练，并且其准确率不能被接受，则通常使用不同的网络拓扑或使用不同的 初始权值，重新进行训练。 例如，用b p n n 算法进行学习时，是通过迭代处理一组训练样本，并将每 个样本的网络预测与实际知道的类标号比较，从而进行学习。对于每个训练样本 来修改权值，使得网络预测和实际类之间的均方误差最小。 神经网络的优点是其具有对噪声数据的高承受能力，以及对未经训练的数据 模式进行分类的能力。其缺点是可解释性较差，因为人们往往很难解释蕴含在学 习权之中的符号含义。正是因为这一点，导致了知识的表示比较困难，尤其是用 加权链连接结点的网络表示的知识很难被人理解。但目前已有不少研究工作致力 于如何提取隐藏在经过训练的神经网络中的知识，并合理地进行解释的研究。利 用网络提取规则和灵敏度分析是两种具有代表性的方法。 1 3 4k 近邻分类 k 近邻分类是一种基于类比的学习方法。首先给出训练样本与多维空问的映 射及空间点之间距离的定义： 假设训练集中的样本可由n 个属性数据罐i ( a ，4 ：，“。) 进行描述，那么以n 个属性为维度，建立一个n 维的空间掣，每个样本则对应这h 维空间中的一个 点。由此可得，任意两点x ，y 之间的欧几罩德距离为1 1 ：d ( x ，j ，) = 、f ( 一只j 2 ， v ，一i 第一章绪殓 其中x ，y r 4 。 k 近邻分类方法就是通过先将训练集中的所有样本存放到n 维的模式空间 矗“中去，对于待分类的样本，在空l 日jr “中寻找k 个与这一样本距离最邻近的训 练样本，并以上述的欧几里德距离的大小作为邻近程度的比较。最后，根据这k 个训练样本所属的类概率，来决定待分类样本所属的类。对于k 取1 的特殊情 况最近邻分类就是从训练集中找一个与待分类样本之间欧几里德距离最近的点， 以该样本( 点) 所在的类作为待分类样本的归属类。 显然，与决策树归纳分类法和b p 神经网络分类法不同，k 近邻分类是基于 要求的或称为懒散的学习方法，即它存放所有的训练样本，直到未知样本需要分 类时，才建立分类。正是这一点，使得该分类方法存在以下几个问题： 1 性能问题。当训练样本所在的空削r 叩p 存在大量与待分类样本邻近的点 时，这种懒散的学习方法可能导致较高的计算开销。 2 可解释性问题。最邻近分类法对每个属性指定的权重都是相同的，当数 据中存在许多相关属性时，这种分类法的可行性和可解释性受到质疑。 对于数据分类，以上只介绍了几种较为常用的方法及其特点。实际上还存在 许多分类法，如遗传算法，粗糙集方法等。它们许多还处于模型的研究阶段，而 在实践中还未广泛地应用。 1 4 神经网络学习理论 通过向环境学习获取知识并改进自身性能是神经网络的一个重要特点，一般 情况下，性能的改善是按某种预定的度量通过调节自身参数( 如权值) 随时f 白j 午畦 移逐步达到的，学习方式( 按环境所提供的信息多少分) 有三种： ( 1 ) 监督学习( 有教师学习) 这种学习方式需要外晃存在一个“教师”，可对一组给定输入提供应有的输 出结果( 正确答案) ，这组已知的输入输出数据称为训练样本集。学习系统可根 据已知输出与实际输出之间的差值来调节系统参数。 ( 2 ) 无监督学习( 无教师学习) 该方式下不存在外部教师，学习系统完全按照环境所提供的数据的某些统计 规律来调节自身参数或结构，是一种自组织的过程，以表示外部输入的某种固定 特征。 ( 3 ) 再励学习( 强化学习) 这种学习介于上述两种情况之问，外部环境对系统输出结果只给出评价，而 不是正确答案，学习系统通过强化那些受奖励的动作来改善自身性能。 第一章绪论 1 4 1 学习的统计性能 学习问题就是在组已定的函数族( 某固定结构的网络) 中选择某一一特定 砸，w ) ，使得输出在某种统计意义上最佳逼近应有响应y 。这个选择是基于一组 | v 个独立同分布的训练样本( 一，y ) ，( x ：，北) ，( x 。，) 上的。对前述学习模型， 存在如下问题：给出的训练样本中是否包含足够的信息，使学习后的网络具有良 好的推广能力，对于此问题的回答要用到v a p n i k 和c h e r v o n e n k o 的经验风险最 小化理论 9 l 。 1 4 1 1 经验风险最小化原则 令l ( y ，f ( x ，w ) ) 表示某输入x 的应有输出j ，与实际响应f ( x ，w ) 间的损失。 种常用的定义为 l ( y ，f ( x ，w ) ) = ( y f ( x ，) ) 2( 1 1 ) 损失的期望值称为风险( r i s k ) 【1 0 1 r ( ，) = i l ( y ，f ( x ，w ) ) d p ( x ，y ) 0 - 2 ) 其中p ( x ，y ) 为工与y 的联合分布。学习的目的是在函数类y ( x ，) 中寻找使尺( ，) 值最小的函数。由于联合分布p ( x ，y ) = p ( y l x ) p ( x ) 未知，所以很难计算期望风 险r ( w ) 。唯一的信息来源是训练样本，故构造经验风险函数 r 。，( w ) = 专工( y ，f ( x i i ，) ) 0 - 3 ) 该式不需要明确p ( x ，j ，) 。用r 。，( ，) 代替真_ i f 风险r ( w ) ，令w 。和f ( x ，w ) 分 别为使r 。( h ，) 达最小的权值和相应的响应，w 。和f ( x ，w o ) 分别为使矗( ) 值达最 小的权值和相应的响应。对于某固定的权值，+ ，风险函数r ( w + ) 确定了随机变 量z 。的数学期望，其中z 。= l ( y ，f ( x ，i ，) ) 。而经验风险函数咒。( i i ，) 则是随机 变量z 。的均值。经验风险r 。( 彬) 最小化原理简述如下： 令忆，表示使经验风险r o ，( w ) 最小化的权值，则在经验风险足。( w ) 一致收 敛于实际风险的条件下，r ( 毗。) 以概率收敛于实际风险胄( ，) 的可能最小值。 其中一致收敛是指若经验风险8 。( ，) 以误差s 按- t ，一致逼近于r ( w ) ，则 墨一( w ) 的最小值与r ( w ) 的最小值的偏差不超过2 s 。即对任何w w 和g 0 ， 下述概率关系成立： r、 p s u p 陋( ) 尺唧( i ，) i s 斗0 ，当n 斗。时 ( 1 - 4 ) l m e ， 这等价于对任何口 0 ，有 f、 尸 s u p p ( 舻) 一足唧( ) f 占 2 s 口( 1 - 6 ) 必定成立。此条件是经验风险具有一致性的充要条件。所谓的经验风险最小化的 一致性可理解为，当样本趋于无穷时，使经验风险最小化的k 。对应的期望风险， 也几乎为最小。 1 4 1 2v c 维数 上述原则在理论上奠定了经验风险晟小化的可行性，但实际上不可能无 穷大，凼此还需要研究收敛的速度问题，这要用到一个重要概念“v c 维数”i ， 它代表的是函数类( 分类函数簇) 的容量这一概念。 假定m 维空间曰”中有a 个样本( 工，j ，) ，x r ”，j ， 0 ，l ( 即研究的是两 类划分问题) ，( 戈，y ) 是随机地从r “ o ，1 上按某个概率抽取的，f 是月斗 o ，1 的某种函数，令s 表示月“中个点的集合，d 。( s ) 表示由f f 对s 产生的不 同：分割数，且以( ) = m a x d 。( s ) ，其中s 是所有点数为的s c r 的集合。 当d ，( j ，) 能实现s 中所有2 ”个可能的2 2 分割( 即d ，( ) = 2 “) 时，称s 可被， 打散。函数类，的v c 维数定义为能被，细分的s 的最大元素数，即能使 d ，( | ) = 2 ”的最大值。当d ( ) = 2 ”对任意大的都成立( 即不管有多少元 素的s ，f 都能把它细分) 时，称f 的v c 维数为无穷大，靠( ) 称为函数类f 的增长函数。 如果用函数类 f ( x ，彬) ；w 代表一个学习机，确定后就确定了个判 别函数r f ，因此也可把v c 维数理解为该学习机能学习的可以由其分类函数 正确给以所有可能二值标识的最大训练样本数。一般情况下要给出神经网络的 v c 维数的解析表达式较困难，通常只能给出它的界。 1 4 1 3 结构风险最小化 用推广误差k ( w ) 表示分类器对训练样本以外样本上的误差，h 为判别函数 类 f ( x ，坩) ；w 对于输入空间的v c 维数，则吒( ，) 将以概率l a 小于某一称 之为“保证风险”的k ( w ) ，且有 k ( ) = 矿( ，力十毛( n ，h ，口，矿)( 】- 7 ) 其中v ( w ) 仍指训练集上的误差。当固定时，矿( f i ，) 随着v c 维数h 的增加单调 下降，置信区间岛随着h 单调上升，而k 会出现极小值，在达此极小值f ；订学习问 题是超定的，即学习机的容量比训练样本少；过了极小值变为欠定的，即学习机 的容量相对于训练样本来说过大。因此学习问题在于应使学习机的容量( v c 维 数) 与已有训练样本数“匹配”。结构风险最小化就是通过控制学习机的v c 维 数来达到这一目的的。 第一章绪论 考虑如下n 个有序的判别函数序列： e = f ( x ，w ) ； ， ，k = 1 2 ”，日只c 五 c 只( 1 - 8 ) 其v c 维数满足 _ 1 2 j 也 ( 1 - 9 ) 其中c 表示“包含于”，则结构风险最小化按下述方式进行1 1 0 】： ( 1 ) 使经验风险( 训练误差) 最小，选出对应较小v ( w ) 的子集。 ( 2 ) 对f 确定( 1 7 ) 式右端相互矛盾的两项之值。其方法是寻找一个网络结 构，使得在训练误差增加尽可能小的条件下降低v c 维数。 以下举出三种可能的途径： f 1 ) 控制隐单元数量，此时学习机的容量通过隐单元数来控制。 ( 2 ) 约束权的数量，此时网络结构固定，但对连接权的个数加以约束( 例如 加入对权值的惩罚项) 。 ( 3 ) 前处理，即设法降低输入空间的维数。 对任何复杂的连续( 实际上包括具有可数个的不连续点) 函数，总存在一个 三层前馈网络，可任意逼近所给函数。经验风险最小化理论说明在一定条件下， 这个逼近可以通过向样本学习达到。 1 4 2 学习的动态特性 可以用一个统一的观点来看待学习过程，即把它看作是一个在多维空间的搜 索过程，其目的是寻找一个使预定的目标函数达最优的解，这种优化可以是有约 束条件的，也可以是无约束的。在这一统一框架下，一个连续时间的学习规则可 当作一个一一阶随机微分方程，它代表的是一个动态系统，学习机的状态则按此方 程演变直到使目标函数达到最优的平衡状态。这罩采用种近似方法，即研究此 随机系统在平均意义上的渐进解，这种近似导致一种平均学习方程。此平均学习 方程在多数情况下对应于一个全局渐进稳定的梯度系统，此系统的稳定平衡点则 是使某一目标函数最优的状态，以下给出几个常用的学习规则的平均意义下的动 态过程。 1 4 2 1l m s 规则 考虑有h 个输入的单个神经元，其权向量为，输入向量茹r ”。外加 期望输出值j ，输入信号由环境按未知概率分布p ( x ，) ( 当y 未知，即非监督学 习时按p ( x ) ) 提供，则在目标函数连续的情况下，省略时间变量f ，简化后的学 习方程为l h ，= r l r ( w ，z ，y ) x 一丑w ( 1 - 1 0 ) 第一章绪论 其中卵，丑为正实数，w = d w d t ，r ( w ，上，y ) 称为学习信号。在式( 1 - l o ) e p ，若令 r ( w ，x ，j ，) = y w 7 x ( 实际输出与期望输出之恻的误差) ，五= 0 可得随机微分方 程h ，= q ( y w 7 x ) x ，其平均学习方程为 = 叩 = 叩 ( 1 - 1 1 ) 其中 ，为板分布p ( x ) 对x 的所有可能值取平均。在平衡点，+ 处应有 = 0 ，即 = 0 ，所以 = ，或 w + = 。 用尺。= 表示x 的自相关阵，p = 为y 与x 的互相关阵，只要 d e t r 。0 ，则有w + = r x x p 。对应判据为 ，( ，) = 一r ( y - t ) 础= 去( j ，一w x ) 2 = 告( y 多) 2 ( 1 一1 2 ) 其h e s s i a n 阵为 = v v = = = r 。只要如为i e 定，d e t 氏0 ，即w + = - i p 为平均学习方程唯一的渐进稳定解，且叩满足 0 ，7 l ，2 m 。为氐的最大特征值，学习过程就是收敛的。 1 4 2 2h e b b 规则f l i j 把式( 1 1 0 ) 看作是寻求是某一瞬问判据j 最小值的最陡梯度下降过程，即 1 9 = 一q v 。j ( x ，w ，y ) = q r ( x ，w ，) 一2 w ( 1 1 3 ) 若x 是遍历的，且是只由分布p ) 约束的独立的随机过程，权向量的变化方 向随机地由x 确定，得出坩的平均值与判据i ，的平均梯度成比例。于是有 = - r l v = r - 2 ( 1 - 1 4 ) 在式( 1 1 0 ) e e 取r ( w ，x