TABLE OF CONTENTS Sunita Sarawagi
Summary. Many interesting real-life mining applications rely on modeling data as sequences of discrete multi-attribute records. Existing literature on sequence mining is partitioned on application-specific boundaries. In this article we distill the basic operations and techniques that are common to these applications. These include conventional mining operations, such as classification and clustering, and sequence specific operations, such as tagging and segmentation. We review state-of-the-art techniques for sequential labeling and show how these apply in two real-life applications arising in address cleaning and information extraction from websites.
Sequences are fundamental to modeling the three primary media of human communication: speech, handwriting and language. They are the primary data types in several sensor and monitoring applications. Mining models for network-intrusion detection view data as sequences of TCP/IP packets. Text information-extraction systems model the input text as a sequence of words and delimiters. Customer data-mining applications profile buying habits of customers as a sequence of items purchased. In computational biology, DNA, RNA and protein data are all best modeled as sequences.
A sequence is an ordered set of pairs ( t 1 x 1) ( t n x n)where t i denotes an ordered attribute like time ( t i -1 ? t i)and x i is an element value. The length n of sequences in a database is typically variable. Often the first attribute is not explicitly specified and the order of the elements is implicit in the...
