Abstract
In recent years, there has been an enormous growth in the amount of sequence data, such as the log of customer transactions and events. Providing efficient ways to analyze the larger amount of sequence data and to make use of the analyzed results has become one of the most important issues nowadays. In this thesis, a framework aiming at efficiently and effectively deriving and retrieving significant rules when given the sequence datasets is proposed. In the framework, given a set of sequences composed of customer transactions, we aim at deriving the customer buying behavior (sequence rules) for the recommendation of hot items. On the other hand, we utilize the discovered rules (episode rules) from the past sequence of events for the prediction of coming events. In each of these works, efficient and effective methods for mining the sequence data and retrieving the discovered rules are developed respectively. Given a large number of customer sequences, mining sequence rules in the form of X□Y can be useful some applications. i.e., item recommendation. The rule X□Y implies that if a customer has the buying behavior corresponding to X (the predicate), she/he will likely buy the items in Y (the consequent). In general, the sequence rules are derived from the frequent sequences. A sequence (an ordered list of item-sets) is frequent if the number of customer sequences containing it satisfies the user-specified threshold. The 1-sequence is a special type of sequences because it consists of only a single itemset instead of an ordered list, while the k-sequence is a sequence composed of k itemsets. Compared with the cost of mining frequent 1-sequences and mining frequent k-sequences (k□2), the cost of mining frequent 1-sequences is negligible. In this thesis, we adopt a two-phase architecture to find the two types of frequent sequences separately in order that the discovery of frequent k-sequences can be well designed and optimized. For efficient frequent k-sequence mining, every frequent 1-sequence is encoded as a unique symbol and the database is transformed into one constituted by the symbols. We find that it is unnecessary to encode all the frequent 1-seqences, and make full use of the discovered frequent 1-sequences to transform the database into one with a smaller size. For every k□2, the customer sequences in the transformed database are scanned to find all the frequent k-sequences. We devise the compact representation for a customer sequence and elaborate the method to enumerate all distinct subsequences from a customer sequence without redundant scans. In many applications, events such as alarms in telecommunication networks and stock fluctuations in the stock market often come in a stream. The prediction of coming events has great importance in such applications. In an event stream, a sequence of events which matches the predicate of the episode rule satisfying a specified time constraint is called an occurrence of the predicate. After finding the occurrence, the consequent event which will occur in a time interval can be predicted. However, the time intervals computed from some occurrences for predicting the event can be contained in the time intervals computed from other occurrences, and become duplicate. In this thesis, an effective scheme is proposed to avoid matching the predicate events corresponding to duplicate predicting intervals. Based on the scheme, we propose two algorithms for the efficient matching of predicate events over event streams. The first algorithm constructs an event filter to incrementally maintain parts of the matched results as events arrive, and thus it avoids backward scans of the event stream. On the other hand, the second one is to maintain the recently arrived events in a tree structure. The matching of predicate events is only triggered by distinguishable events, and an efficient matching algorithm is proposed from the tree structure, which avoids exhaustive scans of the arrived events.