Fast outlier detection for very large log data

Density-based outlier detection identifies an outlying observation with reference to the density of the surrounding space. In spite of the several advantages of density-based outlier detections, its computational complexity remains one of the major barriers to its application. The purpose of the pre...

Full description

Saved in:
Bibliographic Details
Published in:Expert systems with applications 2011-08, Vol.38 (8), p.9587-9596
Main Authors: Kim, Seung, Cho, Nam Wook, Kang, Bokyoung, Kang, Suk-Ho
Format: Article
Language:English
Subjects:
Algorithms
anomaly) detection
Approximated k-nearest neighbors
Approximation
Computation
Density
Density-based outlier detection
Expert systems
Intrusion (novelty
Kd-tree
Learning theory
Mathematical analysis
Neural networks
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Density-based outlier detection identifies an outlying observation with reference to the density of the surrounding space. In spite of the several advantages of density-based outlier detections, its computational complexity remains one of the major barriers to its application. The purpose of the present study is to reduce the computation time of LOF (Local Outlier Factor), a density-based outlier detection algorithm. The proposed method incorporates kd-tree indexing and an approximated k-nearest neighbors search algorithm (ANN). Theoretical analysis on the approximation of nearest neighbor search was conducted. A set of experiments was conducted to examine the performance of the proposed algorithm. The results show that the method can effectively detect local outliers in a reduced computation time.
ISSN:0957-4174
1873-6793
DOI:10.1016/j.eswa.2011.01.162