Outlier Ensembles : An Introduction

"This book discusses a variety of methods for outlier ensembles and organizes them by the specific principles with which accuracy improvements are achieved. In addition, it covers the techniques with which such methods can be made more effective. A formal classification of these methods is provided, and the circumstances in which they work well are examined. The authors cover how outlier ensembles relate (both theoretically and practically) to the ensemble techniques used commonly for other data mining problems like classification. The similarities and (subtle) differences in the ensemble techniques for the classification and outlier detection problems are explored. These subtle differences do impact the design of ensemble algorithms for the latter problem. This book can be used for courses in data mining and related curricula. Many illustrative examples and exercises are provided in order to facilitate classroom teaching. A familiarity is assumed to the outlier detection problem and also to generic problem of ensemble analysis in classification. This is because many of the ensemble methods discussed in this book are adaptations from their counterparts in the classification domain. Some techniques explained in this book, such as wagging, randomized feature weighting, and geometric subsampling, provide new insights that are not available elsewhere. Also included is an analysis of the performance of various types of base detectors and their relative effectiveness. The book is valuable for researchers and practitioners for leveraging ensemble methods into optimal algorithmic design"--Provided by publisher Preface 6 Acknowledgements 8 Contents 9 About the Authors 13 1 An Introduction to Outlier Ensembles 15 1.1 Introduction 15 1.1.1 Motivations for Ensemble Methods in Outlier Analysis 17 1.1.2 Common Settings for Existing Ensemble Methods 18 1.1.3 Types of Ensemble Methods 20 1.1.4 Overview of Outlier Ensemble Design 21 1.2 Categorization by Component Independence 22 1.2.1 Sequential Ensembles 23 1.2.2 Independent Ensembles 25 1.3 Categorization by Constituent Components 26 1.3.1 Model-Centered Ensembles 26 1.3.2 Data-Centered Ensembles 28 1.3.3 Discussion of Categorization Schemes 30 1.4 Categorization by Theoretical Approach 31 1.4.1 Variance Reduction in Outlier Ensembles 32 1.4.2 Bias Reduction in Outlier Ensembles 32 1.5 Defining Combination Functions 33 1.5.1 Normalization Issues 33 1.5.2 Combining Scores from Different Models 34 1.6 Research Overview and Book Organization 37 1.6.1 Overview of Book 41 1.7 Conclusions and Discussion 44 References 45 2 Theory of Outlier Ensembles 49 2.1 Introduction 49 2.2 The Bias-Variance Trade-Off for Outlier Detection 51 2.2.1 Relationship of Ensemble Analysis to Bias-Variance Trade-Off 56 2.2.2 Out-of-Sample Issues 57 2.2.3 Understanding How Ensemble Analysis Works 58 2.2.4 Data-Centric View Versus Model-Centric View 64 2.3 Examples and Applications of the Bias-Variance Tradeoff 72 2.3.1 Bagging and Subsampling 73 2.3.2 Feature Bagging 74 2.3.3 Boosting 75 2.4 Experimental Illustration of Bias-Variance Theory 75 2.4.1 Understanding the Effects of Ensembles on Data-Centric Bias and Variance 76 2.4.2 Experimental Examples of Bias-Variance Decomposition 82 2.5 Conclusions 86 References 87 3 Variance Reduction in Outlier Ensembles 89 3.1 Introduction 89 3.2 Motivations for Basic Variance Reduction Framework 92 3.3 Variance Reduction Is Not a Panacea 97 3.3.1 When Does Data-Centric Variance Reduction Help? 98 3.3.2 When Does Model-Centric Variance Reduction Help? 105 3.3.3 The Subtle Differences Between AUCs and MSEs 107 3.4 Variance Reduction Methods 107 3.4.1 Feature Bagging (FB) for High-Dimensional Outlier Detection 108 3.4.2 Rotated Bagging (RB) 113 3.4.3 Projected Clustering and Subspace Histograms 114 3.4.4 The Point-Wise Bagging and Subsampling Class of Methods 121 3.4.5 Wagging (WAG) 144 3.4.6 Data-Centric and Model-Centric Perturbation 145 3.4.7 Parameter-Centric Ensembles 145 3.4.8 Explicit Randomization of Base Models 146 3.5 Some New Techniques for Variance Reduction 148 3.5.1 Geometric Subsampling (GS) 148 3.5.2 Randomized Feature Weighting (RFW) 150 3.6 Forcing Stability by Reducing Impact of Abnormal Detector Executions 151 3.6.1 Performance Analysis of Trimmed Combination Methods 154 3.6.2 Discussion of Commonly Used Combination Methods 157 3.7 Performance Analysis of Methods 159 3.7.1 Data Set Descriptions 159 3.7.2 Comparison of Variance Reduction Methods 161 3.8 Conclusions 171 References 172 4 Bias Reduction in Outlier Ensembles: The Guessing Game 176 4.1 Introduction 176 4.2 Bias Reduction in Classification and Outlier Detection 178 4.2.1 Boosting 179 4.2.2 Training Data Pruning 180 4.2.3 Model Pruning 181 4.2.4 Model Weighting 182 4.2.5 Differences Between Classification and Outlier Detection 183 4.3 Training Data Pruning 184 4.3.1 Deterministic Pruning 184 4.3.2 Fixed Bias Sampling 185 4.3.3 Variable Bias Sampling 187 4.4 Model Pruning 188 4.4.1 Implicit Model Pruning in Subspace Outlier Detection 191 4.4.2 Revisiting Pruning by Trimming 191 4.4.3 Model Weighting 193 4.5 Supervised Bias Reduction with Unsupervised Feature Engineering 194 4.6 Bias Reduction by Human Intervention 195 4.7 Conclusions 197 References 197 5 Model Combination Methods for Outlier Ensembles 200 5.1 Introduction 200 5.2 Impact of Outlier Evaluation Measures 203 5.3 Score Normalization Issues 206 5.4 Model Combination for Variance Reduction 208 5.5 Model Combination for Bias Reduction 209 5.5.1 A Simple Example 211 5.5.2 Sequential Combination Methods 212 5.6 Combining Bias and Variance Reduction 213 5.6.1 Factorized Consensus 214 5.7 Using Mild Supervision in Model Combination 216 5.8 Conclusions and Summary 217 References 217 6 Which Outlier Detection Algorithm Should I Use? 219 6.1 Introduction 219 6.2 A Review of Classical Distance-Based Detectors 224 6.2.1 Exact k-Nearest Neighbor Detector 225 6.2.2 Average k-Nearest Neighbor Detector 226 6.2.3 An Analysis of Bagged and Subsampled 1-Nearest Neighbor Detectors 226 6.2.4 Harmonic k-Nearest Neighbor Detector 228 6.2.5 Local Outlier Factor (LOF) 229 6.3 A Review of Clustering, Histograms, and Density-Based Methods 231 6.3.1 Histogram and Clustering Methods 231 6.3.2 Kernel Density Methods 236 6.4 A Review of Dependency-Oriented Detectors 237 6.4.1 Soft PCA: The Mahalanobis Method 238 6.4.2 Kernel Mahalanobis Method 243 6.4.3 Decomposing Unsupervised Learning into Supervised Learning Problems 251 6.4.4 High-Dimensional Outliers Based on Group-Wise Dependencies 254 6.5 The Hidden Wildcard of Algorithm Parameters 255 6.5.1 Variable Subsampling and the Tyranny of Parameter Choice 257 6.6 TRINITY: A Blend of Heterogeneous Base Detectors 259 6.7 Analysis of Performance 260 6.7.1 Data Set Descriptions 261 6.7.2 Specific Details of Setting 263 6.7.3 Summary of Findings 265 6.7.4 The Great Equalizing Power of Ensembles 272 6.7.5 The Argument for a Heterogeneous Combination 276 6.7.6 Discussion 281 6.8 Conclusions 283 References 283 Index 287 Front Matter....Pages i-xvi An Introduction to Outlier Ensembles....Pages 1-34 Theory of Outlier Ensembles....Pages 35-74 Variance Reduction in Outlier Ensembles....Pages 75-161 Bias Reduction in Outlier Ensembles: The Guessing Game....Pages 163-186 Model Combination Methods for Outlier Ensembles....Pages 187-205 Which Outlier Detection Algorithm Should I Use?....Pages 207-274 Back Matter....Pages 275-276