Sequence mining in categorical domains
Mohammed Javeed Zaki · 2000
We present cSPADE, an efficient algorithm for mining frequent sequences considering a variety of syntactic constraints.These take the form of length or width limitations on the sequences, minimum or maximum gap constraints on consecutive sequence elements, applying a time window on allowable sequences, incorporating item constraints, and finding sequences predictive of one or more classes, even rare ones.Our method is efficient and scalable.Experiments on a number of synthetic and real databases show the utility and performance of considering such constraints on the set of mined sequences. INTRODUCTIONThis paper focuses on sequence data in which each example is represented as a sequence of "events", where each event might be described by a set of predicates, i.e., we are dealing with categorical sequential domains.Examples of sequence data include text, DNA sequences, web usage data, multi-player games, plan execution traces, and so on.The sequence mining task is to discover a sequence of attributes, shared across time among a large number of objects in a given database.For example, consider a web access database at a popular site, where an object is a web user and an attribute is a web page.The discovered patterns are the sequences of most frequently accessed pages at that site.This kind of information can be used to restructure the web-site, or to dynamically insert relevant links in web pages based on user access patterns.There are many other domains where sequence mining has been applied, which include discovering customer buying patterns in retail stores, identifying plan failures [12], finding network alarms [3], and so on.The task of discovering all frequent sequences in large databases is quite challenging.The search space is extremely large.For example, with m attributes there are O(m k ) potentially frequent sequences of length at most k.Many techniques have been proposed to mine temporal databases for the frequently occurring sequences.However, an unconstrained search can produce millions of rules or may even be intractable in some domains.Furthermore, in many do-