Online Anomaly Detection With Bandwidth Optimized Hierarchical Kernel Density Estimators

We propose a novel unsupervised anomaly detection algorithm that can work for sequential data from any complex distribution in a truly online framework with mathematically proven strong performance guarantees. First, a partitioning tree is constructed to generate a doubly exponentially large hierarchical class of observation space partitions, and every partition region trains an online kernel density estimator (KDE) with its own unique dynamical bandwidth. At each time, the proposed algorithm optimally combines the class estimators to sequentially produce the final density estimation. We mathematically prove that the proposed algorithm learns the optimal partition with kernel bandwidths that are optimized in both region-specific and time-varying manner. The estimated density is then compared with a data-adaptive threshold to detect anomalies. Overall, the computational complexity is only linear in both the tree depth and data length. In our experiments, we observe significant improvements in anomaly detection accuracy compared with the state-of-the-art techniques.

Automated summary

The proposed algorithm is an unsupervised anomaly detection algorithm that can handle sequential data from complex distributions online with strong performance guarantees. By constructing a partitioning tree and training online kernel density estimators, the algorithm sequentially produces a final density estimation for anomaly detection by comparing it with a data-adaptive threshold. The computational complexity is linear in both tree depth and data length, and significant improvements in accuracy compared to state-of-the-art techniques have been observed in experiments.