示例学习的扩张矩阵算法研究

论文摘要

示例学习是从某一概念的已知正例集合和反例集合中归纳出描述所有正例并排斥所有反例的该概念的一般规则,因此,示例学习也称为概念获取(concept acquisition)。现有的示例学习算法主要分成两大类：覆盖算法和分治算法。覆盖算法生成归纳规则,一般表示为析取范式。本文主要讨论基于扩张矩阵理论抽取规则的覆盖算法。扩张矩阵最主要的优点在于具有很高的准确率。本文对一种典型的扩张矩阵算法FCV给出了一种改进。改进的主要思想是省略FCV算法中建立扩张矩阵、寻找公共路径这一步,直接从评价矩阵中记录选择子得到公式,从而生成规则。进一步的分析和实验结果表明,改进的FCV算法其时间和空间复杂度均有所降低,其泛化能力明显高于原有的FCV算法。此外,本文通过对各种扩张矩阵算法进行的深入研究,以及对FCV和NCV两种典型算法的比较,总结出基于扩张矩阵提取的规则的特点。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 研究背景
• 1.2 国内外研究现状
• 1.3 本文研究重点和主要内容
• 1.4 文章组织
• 第2章 扩张矩阵算法简介
• 2.1 扩张矩阵的相关概念
• 2.2 典型的扩张矩阵算法
• 2.2.1 AQ系列算法
• 2.2.2 AE系列算法
• 2.2.3 FCV算法
• 2.2.4 NCV算法
• 2.2.5 分组覆盖算法
• 2.2.6 扩张图方法
• 第3章 扩张矩阵算法的比较研究与优化
• 3.1 一种扩张矩阵算法的优化及影响
• 3.1.1 FCV算法
• 3.1.2 FCV算法描述
• 3.1.3 算法优化依据
• 3.1.4 优化后算法（IFCV）描述
• 3.1.5 算法复杂性分析
• 3.1.6 测试结果分析
• 3.2 扩张矩阵算法的比较研究
• 3.2.1 扩大规则空间的比较
• 3.2.2 寻求一致公式的过程比较
• 3.2.3 适用数据集范围的比较
• 第4章 总结与展望
• 参考文献
• 攻读硕士学位期间科研工作情况
• 致谢