Structural geography of the space of emerging patterns

Describing and capturing significant differences between two classes of data is an important data mining and classification research topic. In this paper, we use emerging patterns to describe these significant differences. Such a pattern occurs in one class of samples-its "home" class-with a high frequency but does not exist in the other class, so it can be considered as a characteristic property of its home class. We call the collection of all such patterns a space. Beyond the space, there are patterns that occur in both of the classes or that do not occur in any of the two classes. Within the space, the most general and most specific patterns bound the other patterns in a lossless convex way. We decompose the space into a terrace of pattern plateaus based on their frequency. We use the most general patterns to construct accurate classifiers. We also use these patterns in the bio-medical domain to suggest treatment plans for adjusting the expression levels of certain genes so that patients can be cured. © 2005-IOS Press and the authors. All rights reserved