Sequence Data Mining (eBook)

Foreword 7
Biography 9
Preface 10
Contents 12
Introduction 15
Examples and Applications of Sequence Data 15
Examples of Sequence Data 16
Examples of Sequence Mining Applications 18
Basic Definitions 20
Sequences and Sequence Types 20
Characteristics of Sequence Data 21
Sequence Patterns and Sequence Models 22
General Data Mining Processes and Research Issues 25
Overview of the Book 26
Frequent and Closed Sequence Patterns 28
Sequential Patterns 28
GSP: An Apriori-like Method 31
PrefixSpan: A Pattern-growth, Depth-first Search Method 33
Apriori-like, Breadth-first Search versus Pattern-growth, Depth-first Search 33
PrefixSpan 35
Pseudo-Projection 39
Mining Sequential Patterns with Constraints 41
Categories of Constraints 42
Mining Sequential Patterns with Prefix-Monotone Constraints 46
Prefix-Monotone Property 46
Pushing Prefix-Monotone Constraints into Sequential Pattern Mining 48
Handling Tough Aggregate Constraints by Prefix-growth 52
Mining Closed Sequential Patterns 55
Closed Sequential Patterns 55
Efficiently Mining Closed Sequential Patterns 57
Summary 58
Classification, Clustering, Features and Distances of Sequence Data 60
Three Tasks on Sequence Classification/Clustering 60
Sequence Features 61
Sequence Feature Types 61
Sequence Feature Selection 63
Distance Functions over Sequences 64
Overview on Sequence Distance Functions 64
Edit, Hamming, and Alignment based Distances 65
Conditional Probability Distribution based Distance 66
An Example of Feature based Distance: d2 66
Web Session Similarity 67
Classification of Sequence Data 68
Support Vector Machines 68
Artificial Neural Networks 70
Other Methods 71
Evaluation of Classifiers and Classification Algorithms 71
Clustering Sequence Data 73
Popular Sequence Clustering Approaches 73
Quality Evaluation of Clustering Results 78
Sequence Motifs: Identifying and Characterizing Sequence Families 79
Motivations and Problems 80
Motivations 80
Four Motif Analysis Problems 81
Motif Representations 82
Consensus Sequence 83
Position Weight Matrix (PWM) 83
Markov Chain Model 86
Hidden Markov Model (HMM) 89
Representative Algorithms for Motif Problems 91
Dynamic Programming for Sequence Scoring and Explanation with HMM 92
Gibbs Sampling for Constructing PWM-based Motif 94
Expectation Maximization for Building HMM 96
Discussion 98
Mining Partial Orders from Sequences 100
Mining Frequent Closed Partial Orders 102
Problem Definition 102
How Is Frequent Closed Partial Order Mining Different from Other Data Mining Tasks? 105
TranClose: A Rudimentary Method 108
Algorithm Frecpo 111
Applications 117
Mining Global Partial Orders 118
Motivation and Preliminaries 118
Mining Algorithms 119
Mixture Models 122
Summary 123
Distinguishing Sequence Patterns 124
Categories of Distinguishing Sequence Patterns 124
Class-Characteristics Distinguishing Sequence Patterns 126
Definitions and Terminology 126
The ConSGapMiner Algorithm 128
Extending ConSGapMiner: Minimum Gap Constraints 135
Extending ConSGapMiner: Coverage and Prefix-Based Pattern Minimization 137
Surprising Sequence Patterns 139
Related Topics 142
Structured-Data Mining 142
Partial Periodic Pattern Mining 143
Bioinformatics 145
Sequence Alignment 146
Biological Sequence Databases and Biological Data Analysis Resources 148
References 149
Index 157