Mining for Outliers in Sequential Databases
Pei Sun, Sanjay Chawla, Bavani Arunasalam · SIAM International Conference on Data Mining · 2006
The mining of outliers (or anomaly detection) in large databases continues to remain an active area of research with many potential applications. Over the last several years many novel methods have been proposed to efficiently and accurately mine for outliers. In this paper we propose a unique approach to mine for sequential outliers using Probabilistic Suffix Trees (PST). The key insight that underpins our work is that we can distinguish outliers from non-outliers by only examining the nodes close to the root of the PST. Thus, if the goal is to just mine outliers, then we can drastically reduce the size of the PST and reduce its construction and query time. In our experiments, we show that on a real data set consisting of protein sequences, by retaining less than 5% of the original PST we can retrieve all the outliers that were reported by the full-sized PST. We also carry out a detailed comparison between two measures of sequence similarity: the normalized probability and the odds and show that while the current research literature in PST favours the odds, for outlier detection it is normalized probability which gives far superior results. We provide an information theoretic argument based on entropy to explain the success of the normalized probability measure. Finally, we describe a more efficient implementation of the PST algorithm, which dramatically reduces its construction time compared to the implementation of Bejerano [3].
Cited by 117 works. doi:10.1137/1.9781611972764.9
Authors
References
- Information Theory
- LOF
- Algorithms for Mining Distance-Based Outliers in Large Datasets
- Efficient algorithms for mining outliers from large data sets
- A Comparative Study of Anomaly Detection Schemes in Network Intrusion Detection
- The power of amnesia: Learning probabilistic automata with variable memory length
- Mining distance-based outliers in near linear time with randomization and a simple pruning rule
- Variations on probabilistic suffix trees: statistical modeling and prediction of protein families
- Efficient Index Structures for String Databases
- A scalable algorithm for clustering sequential data