Pattern Mining with Evolutionary Algorithms

This book provides a comprehensive overview of the field of pattern mining with evolutionary algorithms. To do so, it covers formal definitions about patterns, patterns mining, type of patterns and the usefulness of patterns in the knowledge discovery process. As it is described within the book, the discovery process suffers from both high runtime and memory requirements, especially when high dimensional datasets are analyzed. To solve this issue, many pruning strategies have been developed. Nevertheless, with the growing interest in the storage of information, more and more datasets comprise such a dimensionality that the discovery of interesting patterns becomes a challenging process. In this regard, the use of evolutionary algorithms for mining pattern enables the computation capacity to be reduced, providing sufficiently good solutions. This book offers a survey on evolutionary computation with particular emphasis on genetic algorithms and genetic programming. Also included is an analysis of the set of quality measures most widely used in the field of pattern mining with evolutionary algorithms. This book serves as a review of the most important evolutionary algorithms for pattern mining. It considers the analysis of different algorithms for mining different type of patterns and relationships between patterns, such as frequent patterns, infrequent patterns, patterns defined in a continuous domain, or even positive and negative patterns. A completely new problem in the pattern mining field, mining of exceptional relationships between patterns, is discussed. In this problem the goal is to identify patterns which distribution is exceptionally different from the distribution in the complete set of data records. Finally, the book deals with the subgroup discovery task, a method to identify a subgroup of interesting patterns that is related to a dependent variable or target attribute. This subgroup of patterns satisfies two essential conditions: interpretability and interestingness. Preface 8 Acknowledgments 10 Contents 12 1 Introduction to Pattern Mining 15 1.1 Definitions 15 1.2 Type of Patterns 17 1.2.1 Frequent and Infrequent Patterns 17 1.2.2 Closed and Maximal Frequent Patterns 20 1.2.3 Positive and Negative Patterns 21 1.2.4 Continuous Patterns 23 1.2.5 Colossal Patterns 24 1.2.6 Sequential Patterns 25 1.2.7 Spatio-Temporal Patterns 26 1.3 Pattern Space Pruning 27 1.4 Traditional Approaches for Pattern Mining 29 1.5 Association Rules 36 References 38 2 Quality Measures in Pattern Mining 41 2.1 Introduction 41 2.2 Objective Interestingness Measures 42 2.2.1 Quality Properties of a Measure 44 2.2.2 Relationship Between Quality Measures 49 2.2.3 Other Quality Properties 52 2.3 Subjective Interestingness Measures 55 References 56 3 Introduction to Evolutionary Computation 59 3.1 Introduction 59 3.2 Genetic Algorithms 62 3.2.1 Standard Procedure 62 3.2.2 Individual Representation 64 3.2.3 Genetic Operators 64 3.3 Genetic Programming 67 3.3.1 Individual Representation 67 3.3.2 Genetic Operators 69 3.3.3 Code Bloat 71 3.4 Other Bio-Inspired Algorithms 72 References 73 4 Pattern Mining with Genetic Algorithms 76 4.1 Introduction 76 4.2 General Issues 78 4.2.1 Pattern Encoding 79 4.2.2 Genetic Operators 84 4.2.3 Fitness Function 86 4.3 Algorithmic Approaches 89 4.4 Successful Applications 95 References 96 5 Genetic Programming in Pattern Mining 99 5.1 Introduction 99 5.2 General Issues 101 5.2.1 Canonical Genetic Programming 101 5.2.2 Syntax-Restricted Programming 105 5.3 Algorithmic Approaches 109 5.3.1 Frequent Patterns 109 5.3.2 Infrequent Patterns 114 5.3.3 Highly Optimized Continuous Patterns 119 5.3.4 Mining Patterns from Relational Databases 122 5.4 Successful Applications 126 References 128 6 Multiobjective Approaches in Pattern Mining 130 6.1 Introduction 130 6.2 General Issues 131 6.2.1 Multiobjective Optimization 132 6.2.2 Quality Indicators of the Pareto Front 133 6.2.3 Quality Measures to Optimize in Pattern Mining 136 6.3 Algorithmic Approaches 138 6.3.1 Genetic Algorithms 138 6.3.2 Genetic Programming 142 6.3.3 Other Algorithms 146 6.4 Successful Applications 148 References 148 7 Supervised Local Pattern Mining 151 7.1 Introduction 151 7.2 Subgroup Discovery 153 7.2.1 Problem Definition 153 7.2.2 Quality Measures 154 7.2.3 Deterministic Algorithms 156 7.2.4 Evolutionary Algorithms 158 7.3 Other Supervised Local Pattern Mining Approaches 167 References 169 8 Mining Exceptional Relationships Between Patterns 172 8.1 Introduction 172 8.2 Mining the Exceptionableness 174 8.2.1 Exceptional Model Mining Problem 174 8.2.2 Exceptional Relationship Mining 176 8.3 Algorithmic Approach 178 8.4 Successful Applications 182 References 184 9 Scalability in Pattern Mining 186 9.1 Introduction 186 9.2 Traditional Methods for Speeding Up the Mining Process 188 9.2.1 The Role of Evolutionary Computation in Scalability Issues 188 9.2.2 Parallel Algorithms 190 9.2.3 New Data Structures 192 9.3 New Trends in Pattern Mining: Scalability Issues 194 References 197 Front Matter....Pages i-xiii Introduction to Pattern Mining....Pages 1-26 Quality Measures in Pattern Mining....Pages 27-44 Introduction to Evolutionary Computation....Pages 45-61 Pattern Mining with Genetic Algorithms....Pages 63-85 Genetic Programming in Pattern Mining....Pages 87-117 Multiobjective Approaches in Pattern Mining....Pages 119-139 Supervised Local Pattern Mining....Pages 141-161 Mining Exceptional Relationships Between Patterns....Pages 163-176 Scalability in Pattern Mining....Pages 177-190 . Introduction To Pattern Mining -- Quality Measures In Pattern Mining -- Introduction To Evolutionary Computation -- Pattern Mining With Genetic Algorithms -- Genetic Programming In Pattern Mining -- Multiobjective Approaches In Pattern Mining -- Supervised Local Pattern Mining -- Mining Exceptional Relationships Between Patterns -- Scalability In Pattern Mining. . By Sebastián Ventura, José María Luna.