AQ规则学习算法原理和Java实现
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=高]得到一个规则,可以看到,这个规则覆盖了所有例子。
序号 | 眼睛 | 头发 | 身高 | 类别 |
---|---|---|---|---|
1 | 蓝色 | 淡黄 | 高 | + |
2 | 蓝色 | 淡黄 | 矮 | - |
3 | 褐色 | 黑 | 高 | + |
4 | 褐色 | 淡黄 | 高 | - |
此外还有四个重要的概念:
普化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