论文部分内容阅读
数据库知识发现(Knowledge Discovery in Databases,简称KDD)是当前涉及人工智能和数据库等学科的一门相当活跃的研究领域,序列模式发现是其中的一个重要研究方向。当前序列模式发现研究存在以下三个主要问题:①传统的序列模式发现算法(如AprioriAll算法等)需要多次扫描数据库,因而时间开销较大:②传统的序列模式发现期望挖掘出所有的频繁序列,整个过程缺乏针对性,时间代价高,结果数量巨大且难以理解;③在实际应用中,最小支持度的设置是一个敏感问题。本文针对这三个问题进行了研究。主要工作如下: 传统算法需要多次扫描数据库,因而时间开销较大。基于概念格扩展模型挖掘序列模式可以较好地提高时间性能。概念格扩展模型(ECL)适用于挖掘包括序列模式在内的各种知识。依据序列模式发现的特点和阈值,对ECL进行剪枝而得到的频繁概念格可以改善模式发现的时空性能。由于构造频繁概念格的时间性能是基于频繁概念格进行序列模式发现的关键,因此,本文提出了一种逐层构造频繁概念格的算法FL-Chein,仅需扫描数据库一次。在此基础上,实现了基于频繁概念格的序列模式发现算法SECLSP。 传统的序列模式挖掘发现所有的频繁序列,整个过程缺少针对性,时间代价高,结果数量巨大且难以理解。在序列模式发现中引入闭合模式概念,可以在信息不丢失的情况下减少冗余序列,大大降低结果的规模。本文抛弃了传统的升维的挖掘思想,从最长的序列模式开始挖掘,并采用了一定的优化策略,提出了一种有效的闭合序列发现算法Multi-pass CS。 top-k闭合模式是闭合模式的进一步扩展,而挖掘top-k闭合序列模式,可以解决传统序列模式挖掘存在的第三个难题——最小支持度设置敏感问题。基于Multi-pass CS算法的思想,本文提出了一种快速的top-k闭合序列模式发现算法TKCS。 基于上述研究,实现了一个原型系统。并从理论和实验上证明了所提出的算法对于解决上述三个问题具有一定的优越性。