Class Relevant Pattern Mining in Output-Polynomial Time
Henrik Großkreutz, Fraunhofer IAIS · 2012
The set of so-called relevant patterns is a subset of all itemsets particularly suited for pattern-based classification tasks.So far, no efficient algorithm has been developed for computing the set of relevant patterns: all existing solutions have a worst-case complexity which is exponential in the size of the input and output.In this paper, we investigate new properties of the relevant patterns and develop, thereupon, the first algorithm whose runtime is polynomial in the size of the input and output.As we show in the experimental section, this result is not only of theoretical interest but also of practical importance, often reducing the search space by orders of magnitude.