Mining top-n local outliers in large databases

Outlier detection is an important task in data mining with numerous applications, including credit card fraud detection, video surveillance, etc. A recent work on outlier detection has introduced a novel notion of local outlier in which the degree to which an object is outlying is dependent on the density of its local neighborhood, and each object can be assigned a Local Outlier Factor (LOF) which represents the likelihood of that object being an outlier. Although the concept of local outliers is a useful one, the computation of LOF values for every data objects requires a large number of &kgr;-nearest neighbors searches and can be computationally expensive. Since most objects are usually not outliers, it is useful to provide users with the option of finding only n most outstanding local outliers, i.e., the top-n data objects which are most likely to be local outliers according to their LOFs. However, if the pruning is not done carefully, finding top-n outliers could result in the same amount of computation as finding LOF for all objects. In this paper, we propose a novel method to efficiently find the top-n local outliers in large databases. The concept of "micro-cluster" is introduced to compress the data. An efficient micro-cluster-based local outlier mining algorithm is designed based on this concept. As our algorithm can be adversely affected by the overlapping in the micro-clusters, we proposed a meaningful cut-plane solution for overlapping data. The formal analysis and experiments show that this method can achieve good performance in finding the most outstanding local outliers.

• Publication year

  2001

• Venue

  Knowledge Discovery and Data Mining

• Publication date

  2001-08-26

• Fields of study

  Computer Science

• Identifiers
  DOI 10.1145/502512.502554
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• The X-tree : An Index Structure for High-Dimensional Data

  2001cited by this paper
• Efficient algorithms for mining outliers from large data sets

  2000cited by this paper
• LOF: identifying density-based local outliers

  2000influential reference
• CURE: an efficient clustering algorithm for large databases

  1998cited by this paper
• Algorithms for Mining Distance-Based Outliers in Large Datasets

  1998cited by this paper
• A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise

  1996cited by this paper
• BIRCH: an efficient data clustering method for very large databases

  1996cited by this paper
• Efficient and Effective Clustering Methods for Spatial Data Mining

  1994cited by this paper
• Eecient and Eeective Clustering Methods for Spatial Data Mining

  1994cited by this paper
• The R*-tree: an efficient and robust access method for points and rectangles

  1990cited by this paper
• Identification of Outliers

  1988cited by this paper
• Outliers in Statistical Data

  1979cited by this paper

• EODA: A three-stage efficient outlier detection approach using Boruta-RF feature selection and enhanced KNN-based clustering algorithm

  2025cites this paper
• Dynamic GNN-based multimodal anomaly detection for spatial crowdsourcing drone services

  2025cites this paper
• A Multi-Head Approach with Shuffled Segments for Weakly-Supervised Video Anomaly Detection

  2024cites this paper
• GMO-AC: Gaussian-Based Minority Oversampling With Adaptive Outlier Filtering and Class Overlap Weighting

  2024cites this paper
• Anomaly Detection in Graph Structured Data: A Survey

  2024cites this paper
• Reconstruction Error-based Anomaly Detection with Few Outlying Examples

  2023cites this paper
• Local Outlier Reclassifier (LORec): a Method for Relocating Local Outliers Generated by K-means

  2023cites this paper
• BPF: a novel cluster boundary points detection method for static and streaming data

  2023cites this paper
• Exploring Effective Outlier Detection in IoT: A Systematic Survey of Techniques and Applications

  2023cites this paper
• Enhancing anomaly detectors with LatentOut

  2023cites this paper
• Vessel sailing route extraction and analysis from satellite-based AIS data using density clustering and probability algorithms

  2023cites this paper
• Differentiable Unsupervised Feature Selection

  2022cites this paper
• AutoML: state of the art with a focus on anomaly detection, challenges, and research directions

  2022cites this paper
• Diabetic Retinopathy Diagnosis Using ResNet with Fuzzy Rough C-Means Clustering

  2022cites this paper
• Nonparametric tests for detection of high dimensional outliers

  2022cites this paper
• DeCorus: Hierarchical Multivariate Anomaly Detection at Cloud-Scale

  2022cites this paper
• A novel anomaly detection method for multimodal WSN data flow via a dynamic graph neural network

  2022cites this paper
• Fast anomaly detection with locality-sensitive hashing and hyperparameter autotuning

  2022cites this paper
• $${{\mathrm {Latent}}Out}$$ Latent O u t : an unsupervised deep anomaly detection approach exploiting latent space distribution

  2022cites this paper
• Outlier quantification for multibeam data

  2022cites this paper
• Probabilistic Robust Autoencoders for Anomaly Detection

  2021cites this paper
• GMOTE: Gaussian based minority oversampling technique for imbalanced classification adapting tail probability of outliers

  2021cites this paper
• Outlier detection from multiple data sources

  2021cites this paper
• Probabilistic Robust Autoencoders for Outlier Detection

  2021cites this paper
• CELOF: Effective and fast memory efficient local outlier detection in high-dimensional data streams

  2021cites this paper
• A Generic Distributed Clustering Framework for Massive Data

  2021cites this paper
• POD: A Parallel Outlier Detection Algorithm Using Weighted kNN

  2021cites this paper
• Meta-feature Extraction Strategies for Active Anomaly Detection

  2021cites this paper
• Capacity-Fading Behavior Analysis for Early Detection of Unhealthy Li-Ion Batteries

  2021cites this paper
• Characterizing and understanding ensemble-based anomaly-detection

  2021cites this paper
• Ultrafast Local Outlier Detection from a Data Stream with Stationary Region Skipping

  2020cites this paper
• Anomaly Detection Using Local Kernel Density Estimation and Context-Based Regression

  2020cites this paper
• Abnormal activity capture from passenger flow of elevator based on unsupervised learning and fine-grained multi-label recognition

  2020cites this paper
• TADILOF: Time Aware Density-Based Incremental Local Outlier Detection in Data Streams

  2020cites this paper
• Unsupervised learning trajectory anomaly detection algorithm based on deep representation

  2020cites this paper
• Improving Deep Unsupervised Anomaly Detection by Exploiting VAE Latent Space Distribution

  2020cites this paper
• Outlier Detection

  2020cites this paper
• Internal Evaluation of Unsupervised Outlier Detection

  2020cites this paper
• A nonparametric framework for water consumption data cleansing: an application to a smart water network in Naples (Italy)

  2020cites this paper
• ELOF: fast and memory-efficient anomaly detection algorithm in data streams

  2020cites this paper
• Outlier Detection Using Structural Scores in a High-Dimensional Space

  2020cites this paper
• Research on library long-tail server based on K-means algorithms

  2019cites this paper
• EnsembleLens: Ensemble-based Visual Exploration of Anomaly Detection Algorithms with Multidimensional Data

  2019cites this paper
• Scalable Robust Models Under Adversarial Data Corruption

  2019cites this paper
• Outlier Detection in High Dimensional Data

  2019cites this paper
• A Fuzzy Constraint Based Outlier Detection Method

  2019cites this paper
• Unsupervised Boosting-based Autoencoder Ensembles for Outlier Detection

  2019cites this paper
• Outliers Identification Model in Point-of-Sales Data Using Enhanced Normal Distribution Method

  2019cites this paper
• A Semi-Supervised CNN With Fuzzy Rough C-Mean for Image Classification

  2019influential citation
• CFOF: A Concentration Free Measure for Anomaly Detection

  2019cites this paper
• Robust Regression via Heuristic Corruption Thresholding and Its Adaptive Estimation Variation

  2019cites this paper
• Simplification and Detection of Outlying Trajectories from Batch and Streaming Data Recorded in Harsh Environments

  2019cites this paper
• A Fast Algorithm for Density-based Top-nnn Local Outlier Detection

  2019cites this paper
• Sample Balancing for Deep Learning-Based Visual Recognition

  2019cites this paper
• Distributed Local Outlier Factor with Locality-Sensitive Hashing

  2019cites this paper
• Research Issues in Outlier Detection

  2019cites this paper
• Using Radial Basis Function for Water Quality Events Detection

  2019cites this paper
• Fast local outlier detection algorithm using K kernel space

  2019cites this paper
• An Outlier Detection Approach Based on Improved Self-Organizing Feature Map Clustering Algorithm

  2019cites this paper
• Fuzzy Rough C-Mean Based Unsupervised CNN Clustering for Large-Scale Image Data

  2018influential citation
• Data-Defect Inspection With Kernel-Neighbor-Density-Change Outlier Factor

  2018cites this paper
• There and back again: Outlier detection between statistical reasoning and data mining algorithms

  2018cites this paper
• Distributed Mining of Outliers from Large Multi-Dimensional Databases

  2018cites this paper
• A Kernel Connectivity-based Outlier Factor Algorithm for Rare Data Detection in a Baking Process

  2018cites this paper
• QANet: Tensor Decomposition Approach for Query-Based Anomaly Detection in Heterogeneous Information Networks

  2018cites this paper
• A Distance-Based Outlier Detection Using Particle Swarm Optimization Technique

  2018cites this paper
• Smoothing of Trajectory Data Recorded in Harsh Environments and Detection of Outlying Trajectories

  2018cites this paper
• Deep learning of virtual marine sensors

  2018cites this paper
• A Relative Kernel-density Based Outlier Detection Algorithm

  2018cites this paper
• Detecting Outliers in Data with Correlated Measures

  2018cites this paper
• Anomalous Trajectory Detection Between Regions of Interest Based on ANPR System

  2018cites this paper
• LITERATURE REVIEW OF MACHINE LEARNING TECHNIQUES TO ANALYSE FLIGHT DATA

  2018cites this paper
• Chapter 3 Identifying Water Network Anomalies Using Multi Parameters Random Walk : Theory and Practice

  2018cites this paper
• Graph-based selective outlier ensembles

  2018cites this paper
• Outlier Detection in Vehicle Trajectories

  2017cites this paper
• A local density-based approach for outlier detection

  2017cites this paper
• Consensus score based outlier detection using extended Hough Transform

  2017cites this paper
• Intelligent data analysis for medicinal diagnosis

  2017cites this paper
• Fast Memory Efficient Local Outlier Detection in Data Streams

  2017cites this paper
• FRIOD: A Deeply Integrated Feature-Rich Interactive System for Effective and Efficient Outlier Detection

  2017cites this paper
• Large dataset summarization with automatic parameter optimization and parallel processing for outlier detection

  2017cites this paper
• Distributed Top-N local outlier detection in big data

  2017influential citation
• Good and Bad Neighborhood Approximations for Outlier Detection Ensembles

  2017cites this paper
• Information Outliers and Their Detection

  2017cites this paper
• Multiobjective genetic algorithm for outliers detection

  2017cites this paper
• A Comparative Study of Bagging and Boosting of Supervised and Unsupervised Classifiers For Outliers Detection

  2017cites this paper
• Novelty-focused weak signal detection in futuristic data: Assessing the rarity and paradigm unrelatedness of signals

  2017cites this paper
• Concentration Free Outlier Detection

  2017cites this paper
• Detecting Interesting Differences: Data Mining in Health Insurance Data using Outlier Detection and Subgroup Discovery

  2017cites this paper
• Image noise Detection and Removal based on Enhanced GridLOF Algorithm

  2017cites this paper
• On the improvement of complexity time and detection rate of outlier detectors : an unsupervised ensemble perspective

  2017cites this paper
• Trajectory outlier detection based on partition-and-detection framework

  2017cites this paper
• An Introduction to Outlier Ensembles

  2017cites this paper
• Outlier detection in medical data using linguistic summaries

  2017influential citation
• Scalable Top-n Local Outlier Detection

  2017cites this paper
• A Comparative Study of Machine Learning Methods for Generation of Digital Forensic Validated Data

  2017cites this paper
• Identifying Water Network Anomalies Using Multi Parameters Random Walk: Theory and Practice

  2017cites this paper
• Research on outlier detection algorithm for express logistics

  2017cites this paper
• Converting SVDD scores into probability estimates: Application to outlier detection

  2017cites this paper
• Outlier detection using the multiobjective genetic algorithm

  2017cites this paper