基于ILP的多关系关联规则分析

归纳逻辑程序设计(ILP)是机器学习与逻辑程序设计的交叉研究领域，归纳逻辑程序设计使用了一阶逻辑的框架，将传统的单表关联规则挖掘算法更好地扩展到了多表情况。ILP在多关系环境下使用一阶谓词逻辑语言表示机制，通常利用Prolog语言在其形式化系统中允许在一个模式中使用多个变量与关系，为机器学习提供了更深入的理论和方法，从而克服了描述能力和背景知识利用的限制。在ILP当中，所有的表达式由常量、变量、谓词符号以及函数符号组成，这些符号可以组成项、句节和子句等表达式，关联规则是一组具有类似X←Y的形式的语句，其中X、Y均由一组谓词组成。如果元组给每一变量赋值后使谓词取值为真的就是支持本谓词的元组，而同时满足关联规则箭头两端的谓词的元组就是关联规则的支持元组。

图7-5　多维关系型数据库示例

以如图7-5所示的数据库为例，这是一个由表student、prefer、where、study组成的多维关系型数据库，每个表所代表的关系用谓词的形式可以表示为：student(name)、prefer(name，subject)、where(name，address，time)、study(name，subject)。对于该数据库，某个position与subject的关联规则以Prolog查询形式可以表现为：

Student(name)，prefer(name，Y)，where(name，X，time)→study(name，X，Y)

当且仅当该查询返回非空解∂时，称这个查询符合数据库D。对于一个特定的数据库，每一个谓词的支持度计算公式为(www.xing528.com)

一个关联规则的支持度为：

实体表中的某一个属性值是否为真，或者关系表中某一种关系是否成立均可以转换为一种谓词，然后根据所关注的谓词和相应的形式，过滤出那些支持度小于最小支持度阈值的谓词组合，得到符合要求的关联规则。

用基于ILP的技术挖掘多表关联规则的典型算法有WARMR和算法FARMER，这类算法使用逻辑原子的方式取代Apriori算法中的项集，使用基于逻辑的DATALOG数据查询语言实现对数据的演绎推理，通过分层迭代的方法找到大于阈值的候选集合关联规则。以WARMR算法为例，该算法采用宽度优先的分层方法查找频繁Prolog查询，首先使用具体化算子和剪枝操作层层迭代产生候选项集，然后通过计算候选查询的支持度确定频繁项集，整个迭代过程持续到没有新频繁查询出现时终止。基于ILP的多关系关联规则分析算法具有更强的知识表达能力与更大的搜索空间，但在查询速度优化和海量数据处理能力上还有不足，近几年来已经有一些性能更高、伸缩性更强的方法被相继提出。