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

Abstract: Unordered tree is widely used for semi-structured data modeling, frequent subtree 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, this paper proposed a MCRP(Mining Coverage Pattern) algorithm for mining coverage pattern, the algorithm can effectively reduce the size and redundant information of the output frequent subtree. it firstly presents a tree coding rule according to the tree width and numbers of children, and then all candidate subtrees are generated by edge extension based on the maximum prefix coding sequence, finally a set of coverage patterns will be 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 algorithm can output fewer frequent subtrees in the case of preserving all the frequent subtrees, and has a certain superiority in processing efficiency.

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