Defining outliers by their distance to neighboring examples is a popular approach to finding unusual examples in a data set. Recently, much work has been conducted with the goal of finding fast algorithms for this task. We show that a simple nested loop algorithm that in the worst case is quadratic can give near linear time performance when the data is in random order and a simple pruning rule is used. We test our algorithm on real high-dimensional data sets with millions of examples and show that the near linear scaling holds over several orders of magnitude. Our average case analysis suggests that much of the efficiency is because the time to process non-outliers, which are the majority of examples, does not depend on the size of the data set.

Many algorithms in data mining can be formulated as a set mining problem where the goal is to nd conjunctions (or disjunctions) of terms that meet user speci ed constraints.Set mining techniques have been largely designed for categorical or discrete data where variables can only take o n a xed numb e r o f v alues.However, many data sets also contain continuous variables and a common method of dealing with these is to discretize them by breaking them into ranges.Most discretization methods are univariate and consider only a single feature at a time (sometimes in conjunction with the class variable).We argue that this is a sub-optimal approach for knowledge discovery as univariate discretization can destroy hidden patterns in data.Discretization should consider the eects on all variables in the analysis and that two regions X and Y should only be in the same cell after discretization if the instances in those regions have similar multivariate distributions (Fx Fy) across all variables and combinations of variables.We present a b o ttom up merging algorithm to discretize continuous variables based on this rule.Our experiments indicate that the approach is feasible, that it does not destroy hidden patterns and that it generates meaningful intervals.

Article Detecting change in categorical data: mining contrast sets Share on Authors: Stephen D. Bay Department of Information and Computer Science, University of California, Irvine, Irvine, CA Department of Information and Computer Science, University of California, Irvine, Irvine, CAView Profile , Michael J. Pazzani Department of Information and Computer Science, University of California, Irvine, Irvine, CA Department of Information and Computer Science, University of California, Irvine, Irvine, CAView Profile Authors Info & Claims KDD '99: Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data miningAugust 1999 Pages 302–306https://doi.org/10.1145/312129.312263Online:01 August 1999Publication History 106citation1,021DownloadsMetricsTotal Citations106Total Downloads1,021Last 12 Months37Last 6 weeks2 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

Combining multiple classifiers is an effective technique for improving accuracy. There are many general combining algorithms, such as Bagging, Boosting, or Error Correcting Output Coding, that significantly improve classifiers like decision trees, rule learners, or neural networks. Unfortunately, these combining methods do not improve the nearest neighbor classifier. In this paper, we present MFS, a combining algorithm designed to improve the accuracy of the nearest neighbor (NN) classifier. MFS combines multiple NN classifiers each using only a random subset of features. The experimental results are encouraging: On 25 datasets from the UCI repository, MFS significantly outperformed several standard NN variants and was competitive with boosted decision trees. In additional experiments, we show that MFS is robust to irrelevant features, and is able to reduce both bias and variance components of error.