Filtering and Refinement: A Two-Stage Approach for Efficient and Effective Anomaly Detection

Anomaly detection is an important data mining task. Most existing methods treat anomalies as inconsistencies and spend the majority amount of time on modeling normal instances. A recently proposed, sampling-based approach may substantially boost the efficiency in anomaly detection but may also lead...

Full description

Saved in:
Bibliographic Details
Main Authors: Xiao Yu, Lu An Tang, Jiawei Han
Format: Conference Proceeding
Language:English
Subjects:
Algorithm design and analysis
Computer science
Costs
Data mining
Density measurement
Filtering
Intrusion detection
Partitioning algorithms
Robustness
USA Councils
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Anomaly detection is an important data mining task. Most existing methods treat anomalies as inconsistencies and spend the majority amount of time on modeling normal instances. A recently proposed, sampling-based approach may substantially boost the efficiency in anomaly detection but may also lead to weaker accuracy and robustness. In this study, we propose a two-stage approach to find anomalies in complex datasets with high accuracy as well as low time complexity and space cost. Instead of analyzing normal instances, our algorithm first employs an efficient deterministic space partition algorithm to eliminate obvious normal instances and generates a small set of anomaly candidates with a single scan of the dataset. It then checks each candidate with density-based multiple criteria to determine the final results. This two-stage framework also detects anomalies of different notions. Our experiments show that this new approach finds anomalies successfully in different conditions and ensures a good balance of efficiency, accuracy, and robustness.
ISSN:1550-4786
2374-8486
DOI:10.1109/ICDM.2009.44