示例学习的最大复合问题及算法

本文证明了示例学习中的最大复合问题（ＭＧＣ）是ＮＰ难题，给出了求解最大复合问题的近似算法，并将此示例学习算法应用于手写数字识别．实验证明，基于最大复合的学习算法和ＡＱ１５相比，速度快、得到的公式少、匹配精度高．

容忍噪音的最大复合问题启发式算法

1.引言 从给定的数据集中发现有用的知识一直是示例学习和数据库知识发现等领域研究的重要内容[1,2].一般地说[3]:规则越简单,归纳概括能力就越强,分类精度越高.因此,近几年来,从给定示例中归纳简单而概括的规则,即最大复合问题的算法研究逐渐成为上述诸领域的一个热点.然而,现有的规则归纳算法多为建立在不含噪音的理想数据基础上的,而在实际的应用领域中不可避免地存在噪音数据[4,5],这样致使现有的算法一直得不到令人满意的结果,甚至很难应用于实际领域,从而给实际领域规则的获取带来了一定难度.噪音数据一般可以分为如下三种形式[6],即个别属性值错误型噪音、未知属性值型噪音和冗余属性值型噪音.规则归纳算法能否有效地解决上述三种情况的噪音、是其能否成功应用于实际领域的关键.