AQ原理及实现

AQ算法是机器学习中基本的规则学习算法,首先介绍下规则学习中的基本概念

规则学习基本概念

例子:设E=D1×D2×…×Dn是n维有穷向量空间,其中Di是有穷离散符号集。E中的元素e=(V1,V2,…,Vn)简记为< Vi >叫做例子，其中Vi∈Di
选择子：选择子是形如[xi=Ai]的关系语句，其中xi为第i个属性，Ai∈Di
公式：公式是选择子的合取式
规则：规则是公式的析取式
举个例子解释下这些概念。下面是由三个例子构成的列表，共有三个有穷离散符号集，D1={蓝色，褐色},D2={淡黄，黑},D3={高，矮}。其中e1=(蓝色，淡黄，高)，最后的类别为+表示e1为正例，同理能够写出第二个和第三个例子的规范形式。
对于选择子x1=蓝色，x2=淡黄，将它俩合取x1=蓝色 ∧ x2=淡黄，这就是一个公式，可以发现e1和e2满足该公式，我们称，该公式覆盖例子e1和e2。再来一个公式[x1=褐色 ∧ x3=高]，将这两个公式做析取，[x1=蓝色 ∧ x2=淡黄]∨[x1=褐色 ∧ x3=高]得到一个规则，可以看到，这个规则覆盖了所有例子。

此外还有四个重要的概念：
普化generalize：减少规则的约束，使其覆盖更多的训练例子
特化specialize：增加规则的约束，使其覆盖较少的训练例子
一致：只覆盖正例不覆盖反例的规则称其是一致的
完备：覆盖所有正例的规则称作是完备的。

AQ算法的任务就是对一个例子集，寻找它的一致且完备的规则。

AQ算法原理

AQ算法共有四个输入参数：例子集合dataSet、solution集合最大容量nSOL、consistent集合最大容量nCONS、候选表达式的数量m。此外还有自定义的优化标准，用以当算法执行过程中发现一些覆盖正例数相同的公式，如何在这些公式中做出取舍，本文选择的是选择覆盖反例数最少的。nSOL等参数会在后面算法详细执行过程中解释。
AQ算法返回值时规则rule。主流程如下图所示，首先对dataSet进行划分，得到全正例集合PE和全反例集合NE。整体思路就是：从PE中选择一个例子example->从这个example出发执行induce函数得到一个最优公式formula，这个公式一定是一致的，rule=rule ∨ formula->将formula覆盖的所有正例从PE中剔除，再从PE中重新选择一个例子执行这个过程直到PE为空，最后输出rule。其实很多规则学习算法大体流程都是如此，比如FOIL、GS算法等，对正例集PE进行遍历，并不断删除新得到公式覆盖的例子。

AQ算法的核心是induce函数，其主要目的是依据输入的例子example生成solution和consistent集合，solution集合里存放是一致且完备的公式，consistent存放的是一致但不完备的公式，如果执行一次后两个集合都没有满，即solution大小小于nSOL、consistent大小小于nCONS，会递归调用induce函数。

以表格中例子集举例，设定nCONS、nSOL和m均为一。对例子e1=(蓝色，淡黄，高),包含三个选择子x1=蓝色,x2=淡黄,x3=高，考察这三个选择子正反例覆盖情况：x1=蓝色 覆盖了1个正例、1个反例；x2=淡黄 覆盖了1个正例、2个反例；x3=高 覆盖了2个正例、1个反例。明显，这三个选择子没有一个是一致的，因此都不能直接加入到solution或consistent集合之中。假定m = 1，需要在这三个选择子中挑选1个进入到下一个induce循环之中，这里我们选择标准是正例数和反例数的比值，比值越大，优先级越高。
于是我们选择了x3 = 高 进入下一次induce，现在尝试将其与x1=蓝色,x2=淡黄 进行合取，x1=蓝色 ∧ x3 = 高 覆盖了1个正例，0个反例，是一致的但不完备，x2=淡黄 ∧ x3 = 高覆盖了1个正例，1个反例，不一致。因此将 x1=蓝色 ∧ x3 = 高 作为公式放入到consitent中，因为事先设定nCONS = 1,因此对于例子e1的induce执行结束。
比较consistent和solution集合里所有公式的表现，依然是使用（正例数/反例数）作为评价依据，选出最优的一个公式，这里只有一个x1=蓝色 ∧ x3 = 高，因此rule = rule ∨ (x1=蓝色 ∧ x3 = 高)。发现新的规则覆盖了e1，于是PE剔除e1，继续下一轮循环，选出e3进行induce。
最终得到一致且完备的规则为(x1=蓝色 ∧ x3 = 高) v (x2=黑)

AQ算法的Java实现

这是我用Java实现AQ算法的项目结构图，Datasets.java负责生成数据集；AQ.java负责从数据集中挖掘一致且完备的规则；Choice.java是定义的选择子类，包含attribute和value两个属性，并覆写了toString函数，按标准的逻辑表达式输出；Formula.java定了公式，包含类型为Set的choices属性和表示公式覆盖正反例比值的performance属性，同样也重写了toString函数
上图展示了测试结果图，可以验证输出的规则是一致完备的。数据量很大时也能够保证运算结果的正确性。
这里说明一下，实验数据集全部是由随机产生，不是来自于现实中的数据，没有任何规律性，因此将例子集换分为训练集和验证集减少过拟合是无法进行的，对于一个随机生成的一个新的测试例子，无法准确判断。

源码：[email protected]:MoonlightStill/AQ_Algorithm.git