挖掘序列模式和结构化模式的精简集

论文摘要

在今天的信息社会中,人们已经拥有了大量的数据,迫切需要将这些数据转化为有用的信息和知识。在这样的背景下,数据挖掘这门新兴学科受到广泛的关注。数据挖掘是在大量的数据中寻找知识,其中,序列模式和结构化模式的挖掘是一个重要的数据挖掘问题,有着广泛的应用。在序列模式的挖掘中,最为重要、最有影响力的算法包括GSP算法和PrefixSpan算法。这些算法都是挖掘频繁序列模式的全集,当序列模式的数量很大时,挖掘序列模式的全集不仅效率很低,而且效果也不好,因为要存储和理解这么多的序列模式是不现实的。解决这个问题的一种途径就是不再去挖掘序列模式的全集,而是只挖掘它的一个精简集。精简集保留了频繁序列模式的总体信息,但序列模式的数目大为减少,有助于用户理解挖掘结果,也有助于提高挖掘算法的效率。精简的频繁序列模式基就是这样一种精简集,它是频繁序列模式全集的一个特殊子集,能用它来估计不在其中的序列模式的支持度,而且误差能保证在用户指定的误差上限内。有两种构造精简的频繁序列模式基的方法:第一种方法逐级检查所有的频繁序列模式,当一个频繁序列模式不能被它在精简基中的子模式估计支持度时,它才被加到精简基中;第二种方法用相对于一系列支持度阈值的最大序列模式构造精简的频繁序列模式基。在采用这种方法的算法中,给出了如何判断最大序列模式的方法,还设计了一些搜索空间剪枝技术,提前剪掉那些不可能生成最大序列模式的分支来加速挖掘过程。压缩频繁序列模式集是针对频繁序列模式的全集太大这个问题的另一种解决方法。为了得到高质量的压缩效果,先对频繁序列模式聚簇,再从每个簇中挑选出有代表性的序列模式,使这些有代表性的序列模式的数目尽可能地少。一个贪婪算法和一个基于候选集的快速算法是压缩频繁序列模式集的有效算法。有代表性的序列模式集合也是频繁序列模式的一种精简集,实验结果表明它能取得很好的压缩效果。树模式的挖掘比序列模式的挖掘更为困难,因为在树模式的挖掘中,子树的组合方式太多。而精简的频繁子树基由相对于一系列支持度阈值的最大频繁子树组成,它是频繁子树的一个精简集,可以用它来估计任一频繁子树的支持度,并能将误差控制在确定范围内。一个算法能用来从带标号的有根有序树的数据库中挖掘子树精简基,这个算法经过简单的扩展后也能用来挖掘有根无序树。该算法采用最右扩展的方式系统地生成频繁子树,采用的剪枝技术能减小搜索空间,合理安排的计算次序能提高计算的效率。数据库中的频繁模式可以用于建立数据库索引。基于树模式的数据库索引首先挖掘频繁子树,并从中挑选出有判别力的子树作为索引属性,然后将索引属性集合中的子树转换成序列,并将索引组织成前缀树的形式。频繁子结构能揭示数据的内在特性,对于数据库修改也很稳定,用有判别力的频繁子树为树数据库构造索引,能显著地提高子树查询的性能。

论文目录

• 摘要
• ABSTRACT
• 1 绪论
• 1.1 背景
• 1.2 序列模式的挖掘
• 1.3 结构化模式的挖掘
• 1.4 本文的贡献
• 1.5 本文的组织
• 2 经典的序列模式挖掘算法
• 2.1 问题定义
• 2.2 GSP 算法
• 2.3 PrefixSpan 算法
• 2.4 小结
• 3 序列模式精简基的挖掘
• 3.1 序列模式精简基
• BASE'>3.2 逐级构造一个精简的SP_BASE
• BASE'>3.3 用最大序列模式构造一个精简的SP_BASE
• 3.4 性能分析
• 3.5 小结
• 4 压缩频繁序列模式集
• 4.1 问题定义
• 4.2 挖掘有代表性的序列模式
• 4.3 性能分析
• 4.4 支持度估计函数
• 4.5 序列模式其它类型的子集
• 4.6 基于约束的序列模式挖掘
• 4.7 小结
• 5 挖掘频繁子树精简基
• 5.1 问题定义
• 5.2 构造子树精简基
• 5.3 挖掘有根的有序子树精简基
• 5.4 挖掘有根的无序子树精简基
• 5.5 实验
• 5.6 小结
• 6 频繁模式在数据库索引中的应用
• 6.1 基于序列模式的数据库索引
• 6.2 基于树模式的数据库索引
• 6.3 实验
• 6.4 小结
• 7 结论
• 7.1 总结
• 7.2 未来的研究方向
• 致谢
• 参考文献
• 附录 攻读博士学位期间发表的学术论文