Plan Mining by Divide-and-Conquer
Jiawei Han, Qiang Yang, Edward Kim · 1999
Plans or sequences of actions are an important form of data. With the proliferation of database technology, plan databases (or planbases) are increasingly common. Efficient discovery of important patterns of actions in plan databases presents a challenge to data mining. In this paper, we present a method for mining significant patterns of successful actions in a large planbase using a divide-and-conquer strategy. The method exploits multi-dimensional generalization of sequences of actions and extracts the inherent hierarchical structure and sequential patterns of plans at different levels of abstraction. These patterns are used in turn to subsequently narrow down the search for more specific patterns. The process is analogous to the use of divide-and-conquer methods in hierarchical planning. We illustrate our approach using a travel planning database. 1 Introduction In recent years, data mining has achieved great success in a variety of application domains [AS95, MTV95, FPSSe96, HK99]...