# Sequential Outlier Detection based on Incremental Decision Trees

arXiv: https://arxiv.org/abs/1803.03674 · HTML: https://mlsanity.com/paper/1803.03674/

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Mar 2018.

## Built on by (most cited first, 21 of 21)

- [Generalized Huber Loss for Robust Learning and its Efficient Minimization for a Robust Statistics](https://mlsanity.com/paper/2108.12627/) (2021)
- [Optimally Efficient Sequential Calibration of Binary Classifiers to Minimize Classification Error](https://mlsanity.com/paper/2108.08780/) (2021)
- [Nonparametric Extrema Analysis in Time Series for Envelope Extraction, Peak Detection and Clustering](https://mlsanity.com/paper/2109.02082/) (2021)
- [Low Regret Binary Sampling Method for Efficient Global Optimization of Univariate Functions](https://mlsanity.com/paper/2201.07164/) (2022)
- [Optimal and Efficient Algorithms for General Mixable Losses against Switching Oracles](https://mlsanity.com/paper/2108.06411/) (2021)
- [Cumulative Regret Analysis of the Piyavskii--Shubert Algorithm and Its Variants for Global Optimization](https://mlsanity.com/paper/2108.10859/) (2021)
- [Nonconvex Extension of Generalized Huber Loss for Robust Learning and Pseudo-Mode Statistics](https://mlsanity.com/paper/2202.11141/) (2022)
- [Efficient, Anytime Algorithms for Calibration with Isotonic Regression under Strictly Convex Losses](https://mlsanity.com/paper/2111.00468/) (2021)
- [Smoothing with the Best Rectangle Window is Optimal for All Tapered Rectangle Windows](https://mlsanity.com/paper/2203.02997/) (2022)
- [Efficient Minimax Optimal Global Optimization of Lipschitz Continuous Multivariate Functions](https://mlsanity.com/paper/2206.02383/) (2022)
- [Natural Hierarchical Cluster Analysis by Nearest Neighbors with Near-Linear Time Complexity](https://mlsanity.com/paper/2203.08027/) (2022)
- [Blind Source Separation for Mixture of Sinusoids with Near-Linear Computational Complexity](https://mlsanity.com/paper/2203.14324/) (2022)
- [A Log-Linear Time Sequential Optimal Calibration Algorithm for Quantized Isotonic L2 Regression](https://mlsanity.com/paper/2206.00744/) (2022)
- [Merging Knockout and Round-Robin Tournaments: A Flexible Linear Elimination Tournament Design](https://mlsanity.com/paper/2203.12011/) (2022)
- [Robust, Nonparametric, Efficient Decomposition of Spectral Peaks under Distortion and Interference](https://mlsanity.com/paper/2204.08411/) (2022)
- [An Auto-Regressive Formulation for Smoothing and Moving Mean with Exponentially Tapered Windows](https://mlsanity.com/paper/2206.14749/) (2022)
- [1D to nD: A Meta Algorithm for Multivariate Global Optimization via Univariate Optimizers](https://mlsanity.com/paper/2209.03246/) (2022)
- [Formulation of Weighted Average Smoothing as a Projection of the Origin onto a Convex Polytope](https://mlsanity.com/paper/2303.11958/) (2023)
- [Efficient Lipschitzian Global Optimization of H"older Continuous Multivariate Functions](https://mlsanity.com/paper/2303.14293/) (2023)
- [Sequential Linearithmic Time Optimal Unimodal Fitting When Minimizing Univariate Linear Losses](https://mlsanity.com/paper/2304.02141/) (2023)
- [Residual-based Adaptive Huber Loss (RAHL) -- Design of an improved Huber loss for CQI prediction in 5G networks](https://mlsanity.com/paper/2408.14718/) (2024)

## Abstract (arXiv)

We introduce an online outlier detection algorithm to detect outliers in a sequentially observed data stream. For this purpose, we use a two-stage filtering and hedging approach. In the first stage, we construct a multi-modal probability density function to model the normal samples. In the second stage, given a new observation, we label it as an anomaly if the value of aforementioned density function is below a specified threshold at the newly observed point. In order to construct our multi-modal density function, we use an incremental decision tree to construct a set of subspaces of the observation space. We train a single component density function of the exponential family using the observations, which fall inside each subspace represented on the tree. These single component density functions are then adaptively combined to produce our multi-modal density function, which is shown to achieve the performance of the best convex combination of the density functions defined on the subspaces. As we observe more samples, our tree grows and produces more subspaces. As a result, our modeling power increases in time, while mitigating overfitting issues. In order to choose our threshold level to label the observations, we use an adaptive thresholding scheme. We show that our adaptive threshold level achieves the performance of the optimal pre-fixed threshold level, which knows the observation labels in hindsight. Our algorithm provides significant performance improvements over the state of the art in our wide set of experiments involving both synthetic as well as real data.