Abstract: Unordered tree is widely used for semi-structured data modeling, frequent subtrees mining on it has benefit for finding hidden knowledge. The traditional methods of mining frequent subtrees often output large-scale frequent subtrees with redundant information, such an output will reduce the efficiency of subsequent operations. In view of the shortcomings of traditional methods, the Mining CoveRage Pattern (MCRP) algorithm was proposed for mining coverage patterns. Firstly, a tree coding rule according to the tree width and the number of children was presented. Then, all candidate subtrees were generated by edge extension based on the maximum prefix coding sequence. Finally, a set of coverage patterns was output on the basis of frequent subtrees and δ'-coverage concept. Compared with the traditional algorithms for mining frequent closed tree patterns and maximal frequent tree patterns, the proposed algorithm can output fewer frequent subtrees in the case of preserving all the frequent subtrees, and the processing efficiency is increased by 15% to 25%.The experimental results show that the algorithm can effectively reduce the size and redundant information of the output frequent subtrees, and it has high feasibility in practical operation.

Key words: unordered tree, frequent subtree, maximum prefix coding, edge extension, coverage pattern

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

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