deadwood: Deadwood: Outlier Detection via Pruning Mutual Reachability Minimum Spanning Trees¶

Description¶

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 will be made.

Usage¶

deadwood(d, ...)

## Default S3 method:
deadwood(
  d,
  M = 10L,
  min_cluster_factor = 0.15,
  max_k = NA_integer_,
  contamination = NA_real_,
  max_debris_size = NA_real_,
  max_contamination = 0.5,
  ema_dt = 0.01,
  distance = c("euclidean", "l2", "manhattan", "cityblock", "l1", "cosine"),
  verbose = FALSE,
  ...
)

## S3 method for class 'dist'
deadwood(
  d,
  M = 10L,
  min_cluster_factor = 0.15,
  max_k = NA_integer_,
  contamination = NA_real_,
  max_debris_size = NA_real_,
  max_contamination = 0.5,
  ema_dt = 0.01,
  verbose = FALSE,
  ...
)

## S3 method for class 'mstclust'
deadwood(
  d,
  min_cluster_factor = 0.15,
  max_k = NA_integer_,
  contamination = NA_real_,
  max_debris_size = NA_real_,
  max_contamination = 0.5,
  ema_dt = 0.01,
  verbose = FALSE,
  ...
)

## S3 method for class 'mst'
deadwood(
  d,
  min_cluster_factor = 0.15,
  max_k = NA_integer_,
  contamination = NA_real_,
  max_debris_size = NA_real_,
  max_contamination = 0.5,
  ema_dt = 0.01,
  cut_edges = NULL,
  verbose = FALSE,
  ...
)

Arguments¶


`d`	a numeric matrix with \(n\) rows and \(p\) columns (or an object coercible to one, e.g., a data frame with numeric-like columns), an object of class `dist` (see `dist`), an object of class `mstclust` (see genieclust and lumbermark), or an object of class `mst` (see `mst`)
`...`	further arguments passed to `mst`
`M`	smoothing factor; \(M \leq 1\) gives the selected `distance`; otherwise, the mutual reachability distance based on the \(M\)-th nearest neighbours is used
`min_cluster_factor`	in the `k`-th iteration of the cluster refinement stage, clusters will not be smaller than `min_cluster_factor*n/(k+1)`, which is similar to what happens in the Lumbermark clustering algorithm
`max_k`	maximal number of clusters to detect; by default (`NA`), at most 10 clusters are requested unless `cut_edges` is given, in which case there will be no further cluster refinement
`contamination`	single numeric value or `NA`; the estimated (approximate) proportion of outliers in the dataset; if `NA`, the contamination amount will be determined by identifying the most significant elbow point of the curve comprised of increasingly ordered tree edge weights smoothened with an exponential moving average
`max_debris_size`	single integer value or `NA`; the maximal size of the leftover connected components that will be considered outliers; if `NA`, \(\sqrt{n}\) is assumed
`max_contamination`	single numeric value; maximal contamination level assumed when `contamination` is `NA`
`ema_dt`	single numeric value; controls the smoothing parameter \(\alpha = 1-\exp(-dt)\) of the exponential moving average (in edge length elbow point detection), \(y_i = \alpha w_i + (1-\alpha) y_{i-1}\), \(y_1 = d_1\)
`distance`	metric used in the case where `d` is a matrix; one of: `"euclidean"` (synonym: `"l2"`), `"manhattan"` (a.k.a. `"l1"` and `"cityblock"`), `"cosine"`
`verbose`	logical; whether to print diagnostic messages and progress information
`cut_edges`	numeric vector or `NULL`; \(k-1\) indexes of the tree edges whose omission lead to \(k\) connected components (clusters), where the outliers are to be sought independently; most frequently this is generated via genieclust or lumbermark

Details¶

As with all distance-based methods (this includes k-means and DBSCAN as well), applying data preprocessing and feature engineering techniques (e.g., feature scaling, feature selection, dimensionality reduction) might lead to more meaningful results.

If d is a numeric matrix or an object of class dist, mst will be called to compute an MST, which generally takes at most \(O(n^2)\) time. However, by default, for low-dimensional Euclidean spaces, a faster algorithm based on K-d trees is selected automatically; see mst_euclid from the quitefastmst package.

Once the spanning tree with increasingly sorted edge weights is determined (\(\Omega(n \log n)\)-\(O(n^2)\)), the Deadwood algorithm runs in \(O(k n \log n)\) time, where \(k\) is the number of detected subclusters. Memory use is \(O(n)\).

Value¶

A logical vector y of length \(n\), where y[i] == TRUE means that the i-th observation is deemed to be an outlier.

The mst attribute gives the computed minimum spanning tree which can be reused in further calls to the functions from genieclust, lumbermark, and deadwood. cut_edges gives the cut_edges passed as argument. contamination gives the detected contamination levels in each cluster (which can be different from the observed proportion of outliers detected).

The cluster attribute gives the \(n\) detected cluster IDs (positive integers or NA in case of outliers).

Author(s)¶

Marek Gagolewski

References¶

M. Gagolewski, Deadwood, in preparation, 2026, TODO

M. Gagolewski, Lumbermark: Resistant clustering by chopping up mutual reachability minimum spanning trees*, preprint, 2026, doi:10.48550/arXiv.2604.07143

V. Satopää, J. Albrecht, D. Irwin, B. Raghavan, Finding a “Kneedle” in a haystack: Detecting knee points in system behavior, In: 31st Intl. Conf. Distributed Computing Systems Workshops, 2011, 166-171, doi:10.1109/ICDCSW.2011.20

R.J.G.B. Campello, D. Moulavi, J. Sander, Density-based clustering based on hierarchical density estimates, Lecture Notes in Computer Science 7819, 2013, 160-172, doi:10.1007/978-3-642-37456-2_14

Examples¶

library("datasets")
data("iris")
X <- jitter(as.matrix(iris[1:2]))  # some data
is_outlier <- deadwood(X, M=5)
plot(X, col=c("#ff000066", "#55555555")[is_outlier+1],
    pch=c(16, 1)[is_outlier+1], asp=1, las=1)

plot of chunk deadwood