Filtering and refinement: A two-stage approach for efficient and effective anomaly detection

Xiao Yu, Lu An Tang, Jiawei Han

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publicationICDM 2009 - The 9th IEEE International Conference on Data Mining
Pages617-626
Number of pages10
DOIs
StatePublished - 2009
Event9th IEEE International Conference on Data Mining, ICDM 2009 - Miami, FL, United States
Duration: Dec 6 2009Dec 9 2009

Publication series

NameProceedings - IEEE International Conference on Data Mining, ICDM
ISSN (Print)1550-4786

Other

Other9th IEEE International Conference on Data Mining, ICDM 2009
Country/TerritoryUnited States
CityMiami, FL
Period12/6/0912/9/09

ASJC Scopus subject areas

  • General Engineering

Fingerprint

Dive into the research topics of 'Filtering and refinement: A two-stage approach for efficient and effective anomaly detection'. Together they form a unique fingerprint.

Cite this