Mining condensed frequent subtree base

摘要

In frequent tree pattern mining, the number of frequent subtrees generated is often too large. To tackle this problem, the concept of condensed frequent subtree base is proposed. The base consists of the maximal frequent subtrees for a series of support thresholds. It is a subset of frequent subtrees, and is used to approximate the support of arbitrary frequent subtrees with guaranteed maximal error bound. In. addition, an algorithm is developed to mine such a condensed subtree base in a database of labeled rooted ordered trees. The algorithm adopts the way of right-most extension to generate systematically all frequent rooted ordered subtrees. Several techniques are proposed to prune the branches that do not correspond to the maximal frequent subtrees. Heuristic techniques are used to arrange the order of computation so that relatively expensive computation is avoided as much as possible. Experimental results show that the size of the base is less than 10 percent of that of the complete set, and the algorithm outperforms the previous algorithms.