基于覆盖模式的频繁子树挖掘方法

来源：计算机应用杂志2017年第9期北京时间：

作者：夏英, 李洪旭

单位：重庆邮电大学 计算机科学与技术学院, 重庆 400065

摘要：无序树常用于半结构化数据建模，对其进行频繁子树挖掘有利于发现隐藏的知识。传统的频繁子树挖掘方法常常输出大规模且带有冗余信息的频繁子树，这样的输出结果会降低后续操作的效率。针对传统方法的不足，提出了一种用于挖掘覆盖模式（MCRP）算法。首先，采用宽度孩子数编码对树进行编码；然后，通过基于最大前缀编码序列的边扩展方式生成所有的候选子树；最后，在频繁子树集和δ'-覆盖概念的基础上输出覆盖模式集。与传统的挖掘频繁闭树模式和极大频繁树模式的算法相比，该算法能够在保留所有频繁子树信息的情况下输出更少的频繁子树，并且将处理效率提高15%到25%。实验结果表明，所提算法能有效减小输出频繁子树的规模，减少冗余信息，在实际操作中具有较高的可行性。

关键词：无序树,频繁子树,最大前缀编码,边扩展,覆盖模式

基金资助：国家自然科学基金资助项目（41201378）。