● 摘要
关联规则挖掘是寻找大量数据中项集之间有趣的相关联系。由于关联规则挖掘可以发现用传统的人工智能和统计方法无法发现的项与项或属性与属性间的关系规律，满足了人们从大规模数据存储中获取知识的迫切需求，因此具有重要的研究价值。近年来，作为传统关联规则的一个补充，跨事务关联规则挖掘具有更广泛的实用价值并受到越来越多的关注。传统关联规则挖掘是寻找项集同步发生的规律，跨事务关联规则挖掘是寻找项集异步发生的规律。由于跨事务关联规则挖掘没有事务的限制，即构建规则的事务可以发生在任意时刻，这一性质导致候选项集及规则数目急剧增大。已经有一些算法实现了跨事务关联规则的挖掘，但现有的跨事务关联规则算法存在两个方面的不足：忽略了数量信息，无法挖掘带有数量关系的跨事务关联规则；以每一个非空事务为起点，引入滑动窗口，将原始数据库转化为广义数据库。未用到数据库的分布信息，造成数据冗余。基于此类算法研究现状，本文给出了跨事务关联规则挖掘的两个算法。第一个算法挖掘FCP模式，即挖掘带有数量关系的跨事务关联规则。算法采用序列化步骤及基于互信息的剪枝策略及间隔约束来提高算法效率，避免了滑动窗口的引入而导致的较高的计算复杂度。实验证明了本论文提出的算法在识别时序数据库中的FCP模式是快速有效的。第二个算法(ITAR)挖掘一般的跨事务关联规则，该算法采用分层挖掘的方法，按不同的间隔值(Interval) 划分原始数据库。针对划分后的各个子数据库，分别挖掘其频繁项集，采用分而致之的方法使处理对象简化。采用了剪枝策略及快速搜索策略优化算法执行过程。最终输出广义频繁项集，即跨事务频繁项集。该算法通过按时间节点间隔划分数据对，充分利用数据库的分布信息，降低数据冗余。与EH-Apriori算法的对比实验结果证明了ITAR算法挖掘跨事务关联规则的有效性。这两个算法分别从不同角度分析，以不同方法弥补了现有相关算法的不足。