Finding Rare Patterns with Weak Correlation Constraint

This paper proposes a notion of indicative concepts in a transaction database, presents a branch-and-bound optimization algorithm to find a top-N indicative concepts in a space of many local minimum solutions. An indicative concept consists of several general items as primitive events, but has a very small degree of correlation in spite of the generality of component items. We regard those indicative concepts as rare patterns. As there exist trivial patterns of general items with no instances, we introduce an objective function for taking into account both the generality of component items and the number of instances as evidences, and solve the problem of finding out indicative concepts under the constraint that the degree of correlation must not exceed a given upper bound. Some experimental results are presented and analyzed from the viewpoint of correlation change discovery.