Deadwood: Outlier Detection via Trimming of 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 Mutual Reachability Minimum Spanning Trees. It trims protruding tree segments and marks small debris as outliers.

More precisely:

  • the use of a mutual reachability distance pulls peripheral points farther away from each other,

  • tree edges with weights beyond the detected elbow point are removed,

  • all the resulting connected components whose sizes are smaller than a given threshold are deemed anomalous.

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