Deadwood: Outlier Detection via Pruning Mutual Reachability Minimum Spanning Trees

Deadwood

Keywords: Deadwood, outlier detection, anomaly detection, HDBSCAN*, DBSCAN, minimum spanning tree, MST, density estimation, mutual reachability distance.

Deadwood is an anomaly detection algorithm based on a dataset’s mutual reachability minimum spanning tree. It prunes protruding tree segments and marks small debris as outliers.

More precisely:

  • tree edges with weights greater than the detected elbow point are removed;

  • all the resulting connected components whose sizes do not exceed a prespecified threshold are deemed anomalous;

  • the use of a mutual reachability distance pulls peripheral observations farther away from one another;

  • if the dataset is comprised of well-separated clusters of heterogeneous densities, an attempt to split the dataset and refine the outlierness markers is be made.

Contributing

deadwood is distributed under the open source GNU AGPL v3 license. Its source code can be downloaded from GitHub.

The Python version is available from PyPI. The R version can be fetched from CRAN.

The core functionality is implemented in the form of a C++ library. It can thus be easily adapted for use in other environments. New contributions are welcome, e.g., Julia, Matlab/GNU Octave wrappers.

Author and Maintainer: Marek Gagolewski