（计算机软件与理论专业论文）示例学习的扩张矩阵算法研究.pdf

摘要 摘要 示例学习是从某一概念的已知正例集合和反例集合中归纳出描述所有正例并排斥 所有反例的该概念的般规则，因此，示例学习也称为概念获取( c o n c e p ta c q u i s i t i o n ) 。 现有的示例学习算法主要分成两大类：覆盖算法和分治算法。覆盖算法生成归纳规则， 一般表示为析取范式。本文主要讨论基于扩张矩阵理论抽取规则的覆盖算法。 扩张矩阵最主要的优点在于具有很高的准确率。本文对一种典型的扩张矩阵算法 f c v 给出了一种改进。改进的主要思想是省略f c v 算法中建立扩张矩阵：寻找公共路 径这一步，直接从评价矩阵中记录选择子得到公式，从而生成规则。进一步的分析和实 验结果表明，改进的f c v 算法其时间和空间复杂度均有所降低，其泛化能力明显高于 原有的f c v 算法。此外，本文通过对各种扩张矩阵算法进行的深入研究，以及对f c v 和n c v 两种典型算法的比较，总结出基于扩张矩阵提取的规则的特点。 关键词扩张矩阵；评价矩阵；选择子；公共元素；规则空间 a b s t r a c t a b s t r a c t l e 锄i n g 舶me x 锄p l e si st oc o n c l u d et h eg e n e r a l1 1 l l e sw h i c ha c c e p ta l lp o s i t i v e e x 锄p l e sa n dr e j e c ta l ln e g a t i v ee x 锄p l e sg i v e ni nad a t a s e ti n 、v h i c he x 锄p l e sa r ec l a l s s i f i e d 铆oc l u s t e r s ，也e r e f o r e ，1 e 锄i n g 丘o me x 锄p l e si sr e g a r d e da sc o n c e p ta c q u i s i t i o ni i lm a l l y r e f e r e n c e s 1 1 1 e r ea r e 伽ol ( i n d so fa l g o r i t so fl e 锄i n g 舶me x 锄p l e s ，o n ei sc a l l e d c o v e r a g ea l g o r i t i m la n dt h eo t h e ri sc a l l e dd i v i s i o na l g o r i t h m u s u a l l yc o v e m g ea l g o r i t h m s c 锄o u t p u ti n d u c t i v e - m l e s 谢t hd i s j 吼c t i v en o m a lf o m t m sp a p e rm a i n l yi n v e s t i g a t e sm e e x t e n s i o nm 撕x m g o r i m mo fl e 锄i n gf 两me x 锄p l e s ，w h i c hi sa 哆p i c a lc o v e r a g ea l g o r i t i l i l l 1 1 l em a i na d v a i l t a g eo fe x t e n s i o nm a t r i xa l g o r i t h mi si t sh i 曲l e a m i n ga c c u r a c y 1 1 1 i s p a p e rg i v e sa 1 1i m p r o v e dv e r s i o no fm ef c va l g o r i t h m ( w h i c h i sat y p i c a lc o v e r a g ea l g o r i t h m b a s e do ne x t e i l s i o nm 撕x ) t l l ei m p r o v e m e n ti st or e m o v et h es t 印o fe 虹b l i s h i n ge x t e n s i o n m a t r i xa 1 1 ds e a r c l l i n gc o 删m o np a t l l si i lf c va l g o r i m m ，觚dt l l e nt 0g e n e r a t ed i r e c t l ym l e s f 砧ms a v i n gs e l e c t o r si i le v a l 嘣i o nm a t r i x e s t h e 如r t h e ra n a l y s i sa n de x p 面m e n t a lr e s u l t s s h o wm a to u ri m p r o v e da l g o r i t hi ss i 鲥f i c a n t l ys u p 甜o rt 0t h eo 姆n a lf c va l g o r i t l u i li n t e m so ft i m ea i l ds p a c ec o m p l e x 时a n dt 1 1 eg e n e r a l i z a t i o nc a p a b i l i t ) r b a l s e do nad e t a i l e d r e s e a r c ho nt h ev a r i o u sa l g o r i t h m so fe x t e n s i o nm 撕xa n dac o m p a r i s o nb e t w e e nt w o t y p i c a l a l g o r i t h m sn 锄e df c va i l dn c v ，t h i sp a p e rs 1 衄m 撕z e san u m b e ro fc h 锄i c t e r i s t i c so ft h e 1 1 l l e sg e n e r a t e db a s e do ne x t e i l s i o nm 撕x a l g o r i t h m s k e y w o r d s ：e x t e n s i o nm a t r i x ；e v a l u a t i o nm a t r i x ；s e l e c t o r ；c o 删 1 1 0 ne l e m e n t ；r u l es p a c e 河北大学 学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写的研究成果，也不包含为获得河北大学或其他教育机构的学位或证书 所使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确 的说明并表示了致谢。 作者签名：萎二- 季一 日期：业红月扛日 学位论文使用授权声明 本人完全了解河北大学有关保留、使用学位论文的规定，即：学校有权保留并向国 家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。学校可以公布 论文的全部或部分内容，可以采用影印、缩印或其他复制手段保存论文。 本学位论文属于 1 、保密口，在年月r 解密后适用本授权声明。 2 、不保密 ( 请在以上相应方格内打“巾) 作者签名： 丕拿 日期：型年j 红月卫日 导师签名： 日期：趔年月3 韭日 保护知识产权声明 本人为申请河北大学学位所提交的题目为( 示例学习的扩张矩阵算法研究) 的学 位论文，是我个人在导师( 王熙照教授，翟俊海副教授) 指导并与导师合作下取得的研 究成果，研究工作及取得的研究成果是在河北大学所提供的研究经费及导师的研究经费 资助下完成的。本人完全了解并严格遵守中华人民共和国为保护知识产权所制定的各项 法律、行政法规以及河北大学的相关规定。 本人声明如下：本论文的成果归河北大学所有，未经征得指导教师和河北大学的书 面同意和授权，本人保证不以任何形式公开和传播科研成果和科研工作内容。如果违反 本声明，本人愿意承担相应法律责任。 声明人：羔 一嗍丛年丑月卫日 v1 作者签名： 堑簟日期：丝墅咀月五日 导师签名： 日期：塑堑年妙日 第1 章绪论 1 1 研究背景 第l 章绪论 近年来，信息科学技术已经成为社会发展的重要推动力。随着计算机技术的发展以 及网络的普及，特别是数据存储技术的发展，在工商企业、银行、行政、医疗、军事、 保险等应用领域中，大量的数掘被搜集和存储在各种各样的数据库中。如此丰富的数据， 已经远远超出了人的理解能力。 自从人工智能成为一个独立的学科以来，机器学习已经成为该领域的中心研究课 题。机器学习理论致力于回答这样的问题“学习性能是怎样随着给定的训练样例的数量 而变化的? 和“对于各种不同类型的学习任务，哪个学习算法更适合? 如果我们理 解了计算机学习的内在机制，即怎样使它们根据经验来自动提高，那么影响将是空前的。 想象一下，在未来，计算机能从医疗记录中学习，获取治疗新疾病的最有效方法；从住 宅管理系统分析住户的用电模式，以降低能源消耗；从个人软件助理跟踪用户的兴趣， 并为其选择最感兴趣的在线新闻等。对计算机学习的成功理解将开辟出全新的应用领 域，并使其计算能力和可定制性上升到新的层次。同时，透彻地理解机器学习的信息处 理算法，也会有助于更好地理解人类的学习能力。目前，我们还不知道怎样使计算机的 学习能力和人类相媲美。然而，一些针对特定学习任务的算法已经产生，关于学习的理 论认识也已经开始逐步形成。迄今为止，人们开发出很多实践性的课题，基于机器学习 的算法明显胜过其他的方法。 示例学习【l 】是机器学习较为成熟的一个重要分支。示例学习是从某一概念的已给的 正例集合和反例集合中归纳产生出描述所有正例并排除所有反例的该概念的一般规则。 因此，示例学习也称作概念获取。由于知识获取已公认为专家系统发展的瓶颈问题，示 例学习获得更加广泛的重视和深入的研究。 1 2 国内外研究现状 长期以来，示例学习只局限于具体近似算法及其应用的研究，而理论研究却基本上 河北人学f ：学硕十学位论文 是一片空白【。例如，是否存在精确( 最优) 示例学习的多项式算法，它的计算复杂度的 问题一直未能得到肯定的解答。1 9 8 5 年，洪家荣教授中提出了示例学习的扩张矩阵理 论，率先证明了最优示例学习问题等都是n p 难题。现有的示例学习算法主要分成两大 类：覆盖算法和分治算法。覆盖算法生成归纳规则，一般是析取范式；分治算法生成决 策树1 2 1 。著名的覆盖算法有a q l l ，a e l ，a e 9 ，h c v ，f c v ，g s ，i l a ，扩张图方法； 分治算法有c l s ，i d 3 等。然而，这些算法都遇到了类似的问题所产生的规则表达 式较长或者决策树较大，这样在应用于大规模的问题时效率较低，影响了在实际中的应 用，因此还需要进一步研究和改进。 扩张矩阵理论的前身是a q 系统肼，5 1 ，a q 系统的核心是s t a r 算法。扩张矩阵的基 本思想是，首先建立覆盖一个正例同时排除一个反例的初始规则，接着把该规则泛化到 覆盖该正例并排除所有反例的一般规则，最后把该规则进一步泛化到覆盖所有正例的最 终规则，该规则覆盖所有正例，并排斥所有反例。 扩张矩阵理论发展了a q 系统，遵循的是在整个反例集背景下建立所有正例的扩张 矩阵并提取规则的理念，最先是由洪家荣教授在1 9 9 1 年提出的。早在1 9 8 5 年，基于扩 张矩阵理论的归纳学习算法a e l 【6 】算法就已经诞生了，算法提出者是洪家荣教授，主题 思想是首先利用一种启发式策略，即从非死元素最多的列开始搜索，来对各个正例的扩 张矩阵生成各自的公共路，然后再使用一些推理规则来删除冗余，优化后得到的公共路 集合就是最后的规则集。1 9 8 9 年，洪家荣等在a e l 算法上进行修改和扩充，给出了a e 5 【7 l 算法。继而，在1 9 9 4 年，洪家荣、陈彬等又提出了算法a e 9 【8 1 ，它每次都试图寻找覆 盖数目最多的一致公式，这样有可能使覆盖整个整理集的一致公式的总数较少。a e 系 列算法的更多的是以数学知识为基础，生成大量公式后通过删除冗余公式、冗余选择子 来得到最后的规则。 a e 系列算法中抽取一条规则实际等价于在扩张矩阵中搜索一条路径。它们的优点 是每次都试图寻找覆盖例子数目最多的一致公式，这样可使覆盖整个正例集的一致公式 的总数最少，但仍不能保证总能找到最优解。相继出现的f c v l 9 】、n c v 【2 1 算法主要的改 进是在扩张矩阵中提出新的进行搜索的启发式策略。f c v 算法是1 9 9 7 年由陈彬等提出 的一个寻求最大复合的算法。a e 系列算法的理解和实现需要有大量的数学基础，公式 的化简也比较复杂。相对于a e 系列算法，f c v 算法更加明了易懂，易于实现。f c v 第1 章绪论 算法采用”作为联结符，通过评价矩阵排除最少的j 下例，找出具有最大复合的正例集： 然后通过建立扩张矩阵来找到这个最大复合。 近年来，人们越来越重视扩张矩阵在概念获取中的应用。人们想到把扩张矩阵与其 他算法( 如遗传算法3 1 、粗糙集悼1 引、扩张图方法1 1 9 之等) 结合来提取规则，以达到扬 长避短的效果。因为现实生活中，难免存在出现噪声的现象，扩张矩阵算法的抗噪声能 力也不断提高【2 2 之6 】。 相比其他启发式学习算法而言，扩张矩阵这种表示方法容易操作且易于实现。 1 3 本文研究重点和主要内容 示例学习是机器学习的一个重要分支，它一般考虑两类学习问题，即正、负类。示 例学习的主要目的是找出一组规则，这组规则覆盖所有训练正例，排除所有训练负例。 示例学习在过去的几十年中有了长足发展。 本文针对文献 9 中提出的f c v 算法给出了种优化方法。改进的主要思想是省略 f c v 算法中建立扩张矩阵、寻找公共路径这一步，直接从评价矩阵中记录选择子得到公 式，从而生成规则。实验结果表明，优化后的算法在时间和空间性能上都有提高，其泛化 能力明显高于f c v 算法。 本文通过对f c v 和n c a 这两种典型算法的比较和总结，分析了两种算法的优缺点， 为扩张矩阵算法适用不同的场合提供了参考依据。f c v 算法和n c a 算法是两种典型的 基于扩张矩阵归纳规则的覆盖算法。前者采用“”作为选择子的关系运算符，给出了 求解最大复合问题的近似算法；后者采用“= ”作为关系运算符，叙述了一种新的基于 扩张矩阵的规则抽取算法。 1 4 文章组织 全文的组织结构概括如下： 第1 章绪论。简要介绍扩张矩阵的研究背景和国内外研究现状。 第2 章扩张矩阵算法简介。介绍扩张矩阵的基本概念，阐述扩张矩阵典型算法的 主题思想。 河北人学i ：学硕十学何论文 第3 章扩张矩阵算法的比较研究与优化。本章针对文献 9 】中提出的f c v 算法给出 了一种优化改进。通过对两种典型扩张矩阵算法的比较和总结，分析了两 种算法的优缺点，为扩张矩阵算法适用不同的场合提供了参考依据。 第4 章总结与展望。对所做的研究工作进行总结，并对今后的研究工作提出建议。 第2 章扩张矩阵算法简介 第2 章扩张矩阵算法简介 本章首先对扩张矩阵的相关概念进行了介绍，接着介绍了些典型扩张矩阵算法的 主题思想。 2 1 扩张矩阵的相关概念 为了叙述方便，本章使用了符号值数据集乜们，如表2 1 所示。 表2 1p l a y t e l l i l i s 的训练样例 因为扩张矩阵理论在抽取规则的过程中，以f 例为种子在整个反例矩阵上建立扩张 矩阵，为方便起见，把符号值映射到整数值，并把样例分成正例集合( 雎) 和反例集合 ( m ) 。如表2 - 2 ，表2 3 所示。 表2 2 符号值和整数值之间的映射关系 河北人学t 学硕十学位论文 表2 3 数值化以后的j 下反例集合 p en e 群 a la 2a 3a l 4 撑 a 1a 2a 3a 4 3 1oooloo00 421o02 0ool 5221o62 21l 712il80loo 9 o21o1 421ol l o 21l0 1 1o1l1 1 2llo1 1 3l01o 设e = 日q 是”维有穷向量空间，其中q 是有穷离散符号集。e 中的元素 p m ，屹 ，简记为 ，叫做例子，其中q 。设饱和砸是e 的两个子集， 为区别起见，分别叫做正例集和反例集【l 】o 例如表2 1 中： 称为一个例子。 定义l 1 1 选择子是形为【_ 4 j ( 也用 _ = 4 】做选择子) 的关系语句，其中_ 为第 j 个属性，4 互q 。 定义2 公式( 或项) 是选择子的合取式，即搿_ 4 】，其中， 1 ，玎) ；规则 是公式的析取式，即苫厶，其中厶为公式，一个例子p = 满足选择子【_ 4 ，】 当且仅当1 ，不是4 ，的元素，即丫，4 ，；p 满足一个公式当且仅当它满足该公式的每一 个选择子：p 满足一条规则当目仅当p 满足该规则的至少一个公式。 第2 章扩张矩阵算法简介 例子满足选择子( 公式、规则) 也称做选择子( 公式、规则) 覆盖该例子。 定义3 【1 1 选择子( 公式、规则) 在反例p 一背景下覆盖正例矿当且仅当它覆盖该正例 而不覆盖该反例；选择予( 公式、规则) 在反例集 7 ：e 背景下覆盖一正例，当且仅当它在e 中的每一个反例背景下覆盖该正例：一条规则叫做j 下例集船在反例集砸背景下的一 个覆盖当且仅当雎中的任何一个正例都在反例集背景下被该规则中的一个公式所覆 ， 皿。 例如： ( d 刎d 础s “ 缈 所耐跚d 愕) v 0 h t l m i d i l ) 7 h g h 八o u t l o o k r n i 确 v ( d “砌d 露j s 钰玎，纱 d 材f 肠d 七r 口f ，z ) 是由选择子的合取式生成公式，又由公式的析取式得到规则的实例。 定义4 1 1 1 假设正例集及反例集分别为雎和e ，矿雎，p 一砸， p + = ( v l + ，吃+ ，+ ) ，p 一= ( q 一，吃一，一) ，p + 在p 一背景下的扩张矩阵定义如下： 删0 + ip 一) 是一个矢量( 吒，吃，0 ) 其中： ，一jo 一 哆丐 铲t ：t ：号 木叫做死元素，e + 叫扩张矩阵的种子，e + 在反例背景e 下的扩张矩阵记为 胧( p + i 旭) 。 定义5 f l 】在扩张矩阵删( 矿l 凇) 中，由分别来自不同行的膨个非死元素组成的集 合叫做一条路。在两个以上的扩张矩阵中，具有相同值的对应的非死元素叫做它们的公 共元素。只由公共元素组成的路叫做它们的公共路。具有公共路的扩张矩阵叫做相交的； 否则叫做不相交的。 定义6 川如果一个扩张矩阵中有一个公式( 即路) 覆盖一个例子，我们称该扩张矩阵 覆盖这个例子。 表2 4 给出了正例3 和反例1 建立的扩张矩阵。 河北人学t ：学硕十学位论文 表2 - 4 肼( 0k ) 表2 5 给出了正例3 ，4 在反例矩阵上建立的扩张矩阵。 表2 5 删( 矿i 肥) e m t e ：n e 、 e m 沁：n e 、 撑 a l a 2a 3a 4a la 2a 3a 4 l o 们o 一 2 1 介o 1 62 2 卜、丫n_ _ ，u 8 仃、一l 弋 1 42l 。 表2 。5 中，从分别来自五行的五个圈定的非死元素组成的路径称为一条路。在上面 两个扩张矩阵中，圈定的全是这两个扩张矩阵的公共元素( 对应位置上的元素相等，称 为公共元素) ，因此，图中的路径是公共路径，两个扩张矩阵是相交的。 定义7 阻1 由最多的一组相交扩张矩阵所具有的公共路叫做最大公共路，由最大公共 路形成的公式叫做最大复合。 引理睛1 扩张矩阵肼( p + i e ) 中的路同矿在e 背景下所满足的公式一一对应。 扩张矩阵具有如下性质： 定理设肼( 矿i e ) 是正例p + 在胞背景下的扩张矩阵，其中删( 矿) = 】， p + = ( v l + ，v 2 + ，+ ) 及人匹= 【v ，一】，则 ( 1 ) p k 。 【卑 ( 2 ) 如果p + 不是e 的元素，则删( p + ) 中的每一行至少存在一个非死元素，因此， 8 第2 苹扩g l ，矩阿弭法伺介 至少存在一条路。 ( 3 ) 在反例矩阵中，如果有一个元素在删 + ) 中的对应位置上出现，那么任何同该 元素在同一列并具有相同值的元素也必在删( p + ) 中的相应位置上出现，这样的元素叫 做相似元素。 ( 4 ) 扩张矩阵点m ( p + ) 中的路同矿在砸背景下所满足的公式一一对应。 现在，已知两个正例e + = 及e ，+ = ，则 ( 5 ) 艇中的元素是删( + ) 和删( 白+ ) 的公共元素当且仅当一+ 并且 i 季i e ( 6 ) 两个扩张矩阵删( 气+ ) 和删( q + ) 是不相交的当且仅当存在至少一行，设为i ， 使得一= + 或者峋一= + 对每一列 l ，刀) 都成立。 2 2 典型的扩张矩阵算法 2 2 1a q 系列算法 a q 系列算法的主要成员是a q l1 ( m i c h a l s k je ta i ，1 9 7 8 ) ，a q l 5 ( m i c h a l s l ( i e ta 1 ， 1 9 8 6 ) ，a q l 8 ( k a u 缸a i l 锄dm i c h a l s k i ，2 0 0 0 a ) 。严格的说，a q 系列算法属于覆盖算法， 是扩张矩阵算法的前身，并不能归于扩张矩阵算法，这里做简单的介绍，为我们更好的 理解扩张矩阵算法打下了基础。 a q 算法的主要思想【3 卅是： xd o m a i n - x 1 1 0 m i n a l o ，1 ，2 ) yd o m a i n j 亿 n o m i n a l 0 ，1 ) zd o m a i n y zn o m i m l 0 ，1 ) g r o u pd o m a i n _ g r o u pn o m i n a l g o o d ，b a d ) x ，yz ， g r o u p ooo g o o d 河北人学1 ：学硕十学何论文 201 g o o d l1l g o o d l 1 0b a d 210b a d 011b a d 先任意选择第一个例子做为标准s 切r ，t l l ef i r s t1 i s tc 锄b er e p r e s e n t e da u sac o n d i t i o n 【x = o 】【y = o 】【z = o 】， c o v e rt h es e e d 柚dd o n tc o v e rt h ef i r s tn e g a t v ee v e n t “x ：0 ，2 】( p = 2 ，n _ 2 ) ，【y = o 】，( p = 2 ，n = 0 ) ) s e l e c to n er u l e 【y = o 】 c 0 v e rt h es e e da n dd o n tc o v e rt h es e c o n dn e g a t i v ee v e n t 【x ：o ，1 】( p = 2 ，n = 2 ) = o 】，( p = 2 ，n = 0 ) ) s e l e c to n em l e 【y = o 】 c o v e rt h es d 锄dd o n tc o v e rt h et h i r dn e g a t i v ee v e n t 【y = 0 】( p = 2 ，n = o ) ，【z = o 】，( p = l ，n - 2 ) ) _ 【、，= 0 ( p = 2 ，n = o ) ，【y = o 】 z - 0 】，( p = l ，n = 0 ) ) s e l e c to n em l e 【y = 0 】 最后选择了一个规则【y - o 】，但是这个规则不能覆盖所有的正例，所以在没有覆盖 的例子里继续寻求规则。【y = 0 覆盖了第一个和第二个例子，不能覆盖第三个例子。 如上，第三个例子找到的规则是 x = 1 】 z = 1 】。这样找到能覆盖所有j 下例的规则的析 取式。 2 2 2a e 系列算法 扩张矩阵理论是在1 9 9 1 年由洪家荣教授正式提出的，在理论上给出了明确的定义、 定理及证明。但早在1 9 8 5 年，基于扩张矩阵理论的归纳学习算法a e l 算法就已经诞生了， 算法提出者是洪家荣教授，主题思想是首先利用一种启发式策略，即从非死元素最多的 列丌始搜索，来对各个j 下例的扩张矩阵生成各自的公共路，然后再使用一些推理规则来 删除冗余，优化后得到的公共路集合就是最后的规则集。1 9 8 9 年，洪家荣等在a e l 算法 上进行修改和扩充，给出了a e 5 算法。继而，在1 9 9 4 年，洪家荣、陈彬等又提出了算法 a e 9 ，它每次都试图寻找覆盖数目最多的一致公式，这样有可能使覆盖整个整理集的一 致公式的总数较少。 第2 章扩张矩阵算法简介 a e 系列算法的更多的是以数学知识为基础，生成大量公式后通过删除冗余公式、 冗余选择子来得到最后的规则。下面分别介绍算法a e l 、a e 5 、a e 9 及其优缺点。 a e l 算法【6 】 a e l 算法的核心是通过研究如何利用扩张矩阵的性质来生成一组公式，使它们覆盖 所有的正例而且不覆盖任何的反例。a e l 首先利用一种启发式策略，即从非死元素最多 的列丌始搜索，来对各个j 下例的扩张矩阵生成各自的公共路，然后再使用一些推理规则 来删除冗余。但由于这个启发式策略较为简单，而且冗余的消除也比较困难，因此a e l 生 成的决策规则有时不够优化。其中： ( 1 ) 公式( 路) 的生成。寻找正例矿在砸背景下所满足的公式等价于在反例矩阵中找出 一条路。肼( 矿) 中路的结点( 即非死元素) 由下列公式决定： 一 iv f ， 铲t ： 因此，在算法的具体实现中，完全没有必要去生成扩张矩阵，而只需用上述公式 在同一个反例矩阵中搜索非死元素即可。 ( 2 ) 最优覆盖问题的近似解法。为了生成总数较少的公式集，最好选择扩张矩阵的“最 大公共路”，即在最多数目扩张矩阵中出现的路；而“最大公共元素”，即在最多数 目扩张矩阵中出现的元素，就最有可能在最大公共路中。因此，在扩张矩阵中，可按 元素在各扩张矩阵中出现的频率选择路的结点。公式生成后，a e l 开始删除冗余公式。 一个公式叫做冗余的，如果它所覆盖的正例全部被其余公式的集合所覆盖。具体方法 有： ( i ) 直接按上述定义做；( i i ) 使用吸收律，即如果一个公式在公共集中有一个子公 式，则它是冗余的；( i i i ) 利用逻辑公式口 6 v ，口 6 h 6 。 ( 3 ) 最短公式问题的近似解法。具有最小数目且选择子的公式相应于一条在扩张矩阵中 涉及列最少的路。因此，a e l 为解决这个问题总是从含有最多非死元素的列进行搜索。 当一条路生成后，a e l 开始消除冗余元素。具体方法有：( i ) 生成“最一般公式”法；( i i ) 使用逻辑公式口v ，口人6 付口v 6 。 一一秽一v v y = +，+， v v 河北人学i i 学硕十学位论文 a e l 算法为a e 系列的核心思想，运行效率比彳q 1 1 快很多倍，并为扩张矩阵理论的 提出奠定了基础。 a e 5 算法【7 】 a e 5 算法在a e l 基础上增加了新的功能。列举如下： ( 1 ) 构造性学习模块。用户可以提供一些可供学习的背景知识。这些知识一般以算术表 达式或逻辑规则的形式出现。a e 5 应用这些背景知识于例子集合雎和e ，产生原来 没有的新概念( 即属性或变元) ，然后从这些新属性中筛选出一部分具有最强特征或模式 的属性，并赋予较高的搜索优先级，最后用a e l 算法，产生所需要的规则。这种方法 与归纳结合起来，并用深层知识指导学习过程，很符合人类学习的过程。 ( 2 ) 渐近学习模块。尽管a e l 比著名的爿q 1 l 快很多倍，但它仍面临示例学习的一些普 遍问题：当例子的集合很大时，如何加速学习过程? 当增加一些新例子时，是否需要重 新生成规则? 当知识库出现不一致时，如何消除不一致性? 这些问题都可以用渐近学习 来解决。 ( 3 ) 测试模块。a e 5 具有一个测试模块，它使用知识库中的规则( 专家给出的或机器学习 的) 对用户提供的例子进行测试( 匹配) 。a e 5 具有两种匹配模式：严格匹配与相似匹配。 严格匹配是直接测试李子是否满足规则，满足结果是1 ，不满足是o ；相似匹配是当例 子不满足任何规则时去估计该例子对规则的近似匹配程度，然后将该例子归于具有最 大”接近度”的那个规则所描述的集合。 ( 4 ) 从经验中学习。a e 5 有两种从经验中学习的方法：剪枝法与嫁接法。剪枝法是用同 一个学习算法a e l ，按最优化要求产生几个覆盖；然后用集合覆盖算法从中选择一个较 小的子覆盖：嫁接法是用分别用不同的学习算法a e l 与a q l l 产生两个覆盖。然后用 集合覆盖算法选出较优的字覆盖。这种学习方法颇似人类的学习过程。 a e 5 已被应用于许多领域的知识自动获取。由a e 5 自动获取的知识用于测试和诊 断一般均达到或超过领域专家的水平。同a q l l 相比，a e 5 要快1 0 倍以上。特别是a e 5 可以应用于大规模问题。 a e 9 算法【s 1 第2 章扩张矩阵算法简介 a e 9 算法中增加了选定必选元素的步骤，结合合并运算，每次试图寻找覆盖数目最 多的一致公式，这样有可能使覆盖整个正例集的一致公式的总数较少。但这并不能保证 a e 9 总能找到最优解。a e 9 比a q l 5 产生的决策规则更优化，有较大的实用和推广价值。 2 2 3f c v 算法 f c v 算法是1 9 9 7 年由陈彬等提出的一个寻求最大复合的算法。a e 系列算法的理 解和实现需要有大量的数学基础，公式的化简也比较复杂。相对于a e 系列算法，f c v 算法更加明了易懂，易于实现。f c v 算法采用”作为联结符，通过评价矩阵排除最少 的正例，找出具有最大复合的j 下例集；然后通过建立扩张矩阵来找到这个最大复合。 f c v 算法描述1 9 】 要求排斥的反例多而正例少，设排斥的反例数为肫，排斥的正例数为尸p ，即剜肫 最小。 正例集阳和阳，反例集砸和砸，朋= 饱，e = e 。；扩张矩阵删，j 下例 评价矩阵删和反例评价矩阵删；特征取值范围，特征数f 。 s t e p l 建立p e 。的评价矩阵彪m 和e 的评价矩阵删； s t e p 2 遍历评价矩阵雎m 和删，求删【f ，】和砸m f ，】中对应元素比值的最 小值时，对应的【f ，】值( j 为特征，i 为特征数) ； s t e p 3 在船和e 中删除第j 个特征为i 的例子； s t e p 4 如果泄不空，转到s t e p l ；否则，建立阳在砸背景下的扩张矩阵膨， 寻找一条公共路即公式；饱= 饱一雎；e 。= e ；雎= 阳； 循环以上步骤直到雎为空，即可得到覆盖正例集雎，排除所有反例旭的规则。 f c v 算法时间复杂度的计算 用尸e 一门甜所表示正例的个数，用m 一玎z ，m 表示反例的个数，属性的个数为 ，一，7 “聊，属性值的取值范围用一门“朋表示。f c v 的算法中，s t e p l 的时l 日j 复杂性为 1 3 河北人学r 学硕十学何论文 o ( ( 饱一刀“聊+ 砸一万“m ) f 一即“聊) ，s t e p 2 的时间复杂性为o ( 一挖“m f 一玎“m ) ， s t e p 3 的时间复杂性为o ( p e n 啪+ n e n 啪) ，s t e p 4 的时间复杂性为 o ( 砸一行姗尸一刀甜m ) ；算法最多循环砸一删r ，次。 f c v 算法流程图 图2 1f c v 算法的主流程 f c v 算法的优缺点 f c v 算法通过评价矩阵，总是寻找当前情况下，在反例背景下覆盖最多的正例的 一致公式，考虑到了整个例子集，以达到训练到的一致公式以及选择子数目最少。 据f c v 算法描述，采用逆向思维的方式，利用评价矩阵来求得当前情况下驯肫的 最小值，排除所有反例和最少的正例，然后把少量f 例排除，求剩余的正例在反例背景 下的最大复合。实验结果表明，因为f c v 算法采用的逆思维方式，f c v 算法对有些数 据集的学习归纳不适用，而且算法本身并不能解决这个弊端。 2 2 4n c v 算法 新算法( n c a ) 是由王亚东、郭茂祖、张宝昌于2 0 0 0 年在哈尔滨工业大学学报上发 表的“一个基于扩张矩阵的规则抽取覆盖算法”一文中提出的。该文指出新算法有两个 特点：第一，算法执行后得到的选择子数目较少；第二，按照人们习惯，利用等号( = ) 1 4 第2 章扩张矩阵算法简介 作为选择子的关系运算符，而代替其它系统采用不等号( ) 。新算法一文重点叙述了算 法的实现过程以及实验结果比较，通过论文中的实验结果表明，此新算法是可行的，而 且具有其自身的优越性。 n c a 算法【2 】 算法描述：a 1 9 0 r i t n c a ( p e ，n e ) 假设p e 和n e 分别是正例集合和反例集合。 ( 1 ) 初始化c l a s s = l ，e x i 仁o ，n 啪b e f 0 ； ( 2 ) 建立当前序号为n 啪b e r 的正例的扩张矩阵。 ( 3 ) 计算扩张矩阵的大小，如果此时扩张矩阵元素的个数为零，则转到7 。 ( 4 ) 对扩张矩阵每一列统计木的个数，获得木的个数最小那些列，得到这些选择子， 分别计算它们合取的启发值a v ，如果a v 值最小，则删除当前n e 扩张矩阵中的第j 列不含水的所有向量，则转到3 。 ( 5 ) 删除该规则所覆盖的所有正例，设置b e r 值，计算当前正例数的大小。如果 正例数零，则转到2 。 ( 6 ) c l a l s s = c l a s s + l ；如果此时c l a s s 还没有类别总数则转到2 。 ( 7 ) e x i t = 1 ；输出规则，程序结束。 n c a 算法的优缺点 n c a 算法是顺序求得当前未处理的j 下例的扩张矩阵，求得最简公式以后再把该公 式覆盖的正例去除掉，覆盖正例的多少很难预测。这是n c a 算法的缺点，但同时，因 为n c a 算法是顺序求得正例集中每个正例的扩张矩阵，在得到的扩张矩阵上寻找路径 组成公式，可以控制训练集的学习训练程度。从这个角度考虑，n c a 算法简单，适用 广泛的数据集。 2 2 5 分组覆盖算法 分组覆盖算法【2 8 2 9 1 是在2 0 0 3 年由谌卫军等提出的，该算法是利用作为联结符， 通过h g r 算法先把j 下例分成若干个组，然后再训练得到规则，这样就解决了n c v 算 法局部要求选择子最少，而不考虑全局公式个数的缺陷，达到了较好的效果。该算法给 1 5 河北大学t 学硕+ 学何论文 定义1 分离矩阵：对一组正例 才，艿， ，他们的分离矩阵脚为所有扩张矩 也材，辫掣 定义2 两个正例样本订和称为相容的，如果在它们的扩张矩阵删( 茚) 和 脚( 露) 中存在着一条公共路。如果订和相容，称对是的朋友。显然，如果一组正 着一个一致的公式( 通过分离矩阵来确定是不是改组存在一致公式) ，它覆盖了组内所有 第2 章扩张矩阵算法简介 2 2 6 扩张图方法1 9 】 扩张图方法1 1 9 ，2 0 1 是运用了一种几何理论，通过图的连通情况来寻找公式。首先介绍 一个把例子集映射到图的定义和一个生成公式的定理。 定义l 给定正例集雎与反例集e ，构造有向图g = 如下： ( 1 ) y = 形i 饱u 旭，f = 1 ，历，聊为例子数) ，即一个例子( j 下例或反例) 作为图 g 的一个项点； ( 2 ) 边集e 中元素，即g 得边按以下原则构造： a 对于q + = ( e l 一，) ，e = ( i 一，) ，若存在l p 胛，对所有l 七胛满足：当 后p 时，= ，则连结顶点= v 归形成一条有向边，并以表达式吒= 表示，该边 称为内边； b 对于q + = ( v l 一，v 坍) ，p j = ( 1 一，) ，若存在1 e 玎，对所有l j 打满足：当 七p 时，= ，则连结顶点= k 形成一条有向边，并以表达式t 表示，该边 称为外边； c 对于q 一= ( v f l 一，v 册) ，p j = ( y ，l ，) ，若存在1 p 刀，对所有l 七刀满足：当 七p 时，= v 屑，则连结顶点= k 形成一条有向边，并以表达式= 表示，该边 称为无关边； 按a 、b 、c 的顺序生成图g 的边集，并避免出现回路，则称图g 为该学习问题的扩 张图。 定理1 对扩张图所有表示外边的表达式作为选择子进行合取得到的公式即是雎在 船背景下满足的公式。 图2 2 是扩张图的一个例子，在图中所有外边表达式的合取式 【曼l 】 吃l 】兰【x ：= o ，2 墨= 0 ，2 ，该公式和用规则扩张矩阵方法求得的结果完全一致。 河北人学丁学硕十学位论文 0 0 l 1 0 1 0 1 0 图2 2 扩张图 本节通过对示例学习的扩张图方法的研究，得到了一种对例子空间的新的知识表 示，该方法有助于今后应用图论中的一些重要结论解决示例学习问题。 第3 章扩张矩阵算法的比较研究与优化 第3 章扩张矩阵算法的比较研究与优化 扩张矩阵算法一般考虑两类学习问题，即正、负类，扩张矩阵的主要目的就是找出 一组规则，这组规则覆盖所有训练正例，排除所有训练负例，扩张矩阵算法研究在过去 的几十年中有了长足发展，并且一些成果被应用到实际中。扩张矩阵典型算法有a q l l ， a e l ，a e 9 ，h c v ，f c v ，g s ，n c v 等。 3 1 一种扩张矩阵算法的优化及影响 本节是针对文献 8 中提出的f c v 算法给出了一种优化改进。改进的主要思想是省 略f c v 算法中建立扩张矩阵、寻找公共路径这一步，直接从评价矩阵中记录选择子得到 公式，从而生成规则。实验结果表明，优化后的算法在时间和空间性能上都有提高，其泛 化能力明显高于f c v 算法。 3 1 1f c v 算法 引用什么天气适合打网球的例子n 引，为简单起见，我们把符号值映射到整数，映射关 系如表3 1 所示。 表3 1 符号值和整数值之间的映射关系 把例子分为j 下例集( 砸) 和反例集( 砸) ，如表3 2 所示。 河北人学r ：学硕十学何论文 表3 2 数值化以后的j 下反例集合 p en e 拌a la 2a 3a 4拌a 1a 2a 3a 4 3 1o0o 1 0oo0 42 10o 2 o0o1 522106221l 7l21180l00 902lo1 42l0l 1 0 2l10 1 1 0111 1 2llol 1 31o10 1 ) 建立评价矩阵 正例集雎和反例集砸的评价矩阵删和删如表3 3 所示。评价矩阵删的 元素删【f ，j 】就是正例集雎中第j 个特征，特征值为i 的例子数；评价矩阵删的 元素删【f ，】就是反例集e 中第j 个特征，特征值为i 的例子数。 每次筛选时要求排斥反例多而正例少，设排斥的正例数为心，排斥的反例数为肫， 即叫肫最小；遍历整个评价矩阵，求删 f ，刀和删 f ，】中对应元素比值的最小值。 表3 3 评价矩阵 p m en m e 群a 1a 2a 3a 4撑宣la 2a 3a 4 0 2236 o 3242 l4463 l 0213 233221 此次循环求得的最小值为2 3 ，i = 0 ，j = l ( 口1 = 0 ) 。把j 下例、反例中口l = 0 的例子排除，这 样j 下例中被排除的例子为9 ，1 1 ，反例被排除的例子为1 ，2 ，8 。 第3 章扩张矩阵算法的比较研究与优化 因为要求排除最少正例，同时，排除所有反例，以寻求一致路径达到最大复合，所 以需要循环建立评价矩阵，求删【f 砸m f ，】最小值，直到反例集中的例子完全被 排除。 经过第一轮处理后反例集中还有例子剩余，需要再次建立评价矩阵，如表3 4 所示。 表3 - 4 评价矩阵 p m en m e 撑 a l a 2a 3a 4群a 1a 2a 3a 4 o0235oo0lo 14342lo1l2 232 2 2 1 第二轮循环求得的最小值为2 2 ，滓l ，j = 4 ( 口4 = 1 ) 。f 例集中被排除例子7 ，1 2 ，反 例集中被排除例子为6 ，1 4 。至此反例集中所有的例子都被排除。第一次筛选完成。剩 余的正例集合在反例背景下得到的公式是一个最大复合。 2 ) 建立扩张矩阵、寻找公共路径 把未被排除的正例集( 3 ，4 ，5 ，1 0 ，1 l ，1 3 ) 和整个反例集( 1 ，2 ，6 ，8 ，1 4 ) 建立扩 张矩阵。具体实现时，没有必要生成一个个扩张矩阵，而只要在一个反例矩阵e 中， 根据扩张矩阵定义【2 】中填充死元素的特点，在相应的位置上填充非死元素的个数，例 如口1 = 0 位置上填5 ，记录的是j 下例集5 个例子中口1 o 的个数为5 。因为正例集中共有 5 个例子，所以在反例矩阵砸上统计次数为5 的位置上的元素为公共元素，由这些公共 元素组成公共路径。如表3 5 所示。 从扩张矩阵找出的选择子是口1 0 ，口4