Package {dbscan}


Title: Density-Based Spatial Clustering of Applications with Noise (DBSCAN) and Related Algorithms
Version: 1.3.0
Date: 2026-11-15
Description: A fast reimplementation of several density-based algorithms of the DBSCAN family. Includes the clustering algorithms DBSCAN (density-based spatial clustering of applications with noise) and HDBSCAN (hierarchical DBSCAN), the ordering algorithm OPTICS (ordering points to identify the clustering structure), shared nearest neighbor clustering, and the outlier detection algorithms LOF (local outlier factor) and GLOSH (global-local outlier score from hierarchies). The implementations use the k-d tree data structure (from library ANN) for faster k-nearest neighbor search. An R interface to fast kNN and fixed-radius NN search is also provided. Hahsler, Piekenbrock and Doran (2019) <doi:10.18637/jss.v091.i01>.
License: GPL (≥ 3)
URL: https://github.com/mhahsler/dbscan, https://michael.hahsler.net/dbscan/
BugReports: https://github.com/mhahsler/dbscan/issues
Depends: R (≥ 4.3.0)
Imports: generics, graphics, Rcpp (≥ 1.0.11), stats
Suggests: dendextend, fpc, igraph, knitr, microbenchmark, reticulate (≥ 1.41), rmarkdown, testthat (≥ 3.0.0), tibble, tidyverse
LinkingTo: Rcpp
VignetteBuilder: knitr
Config/testthat/edition: 3
Copyright: ANN library is copyright by University of Maryland, Sunil Arya and David Mount. All other code is copyright by Michael Hahsler and Matthew Piekenbrock.
Encoding: UTF-8
Config/roxygen2/version: 8.1.1
Collate: 'AAA_dbscan-package.R' 'AAA_definitions.R' 'DBCV_datasets.R' 'DS3.R' 'GLOSH.R' 'LOF.R' 'NN.R' 'RcppExports.R' 'broom-dbscan-tidiers.R' 'comps.R' 'dbcv.R' 'dbscan.R' 'dendrogram.R' 'extractFOSC.R' 'frNN.R' 'hdbscan.R' 'hullplot.R' 'jpclust.R' 'kNN.R' 'kNNdist.R' 'moons.R' 'mst.R' 'ncluster.R' 'nobs.R' 'optics.R' 'optics_extractXi.R' 'pointdensity.R' 'predict.R' 'reachability.R' 'sNN.R' 'sNNclust.R' 'utils.R' 'zzz.R'
NeedsCompilation: yes
Packaged: 2026-11-16 02:01:13 UTC; mhahsler
Author: Michael Hahsler ORCID iD [aut, cre, cph], Matthew Piekenbrock [aut, cph], Sunil Arya [ctb, cph], David Mount [ctb, cph], Claudia Malzer [ctb]
Maintainer: Michael Hahsler <mhahsler@lyle.smu.edu>
Repository: CRAN
Date/Publication: 2026-11-17 08:40:09 UTC

dbscan: Density-Based Spatial Clustering of Applications with Noise (DBSCAN) and Related Algorithms

Description

logo

A fast reimplementation of several density-based algorithms of the DBSCAN family. Includes the clustering algorithms DBSCAN (density-based spatial clustering of applications with noise) and HDBSCAN (hierarchical DBSCAN), the ordering algorithm OPTICS (ordering points to identify the clustering structure), shared nearest neighbor clustering, and the outlier detection algorithms LOF (local outlier factor) and GLOSH (global-local outlier score from hierarchies). The implementations use the k-d tree data structure (from library ANN) for faster k-nearest neighbor search. An R interface to fast kNN and fixed-radius NN search is also provided. Hahsler, Piekenbrock and Doran (2019) doi:10.18637/jss.v091.i01.

Key functions

Author(s)

Maintainer: Michael Hahsler mhahsler@lyle.smu.edu (ORCID) [copyright holder]

Authors:

Other contributors:

References

Hahsler M, Piekenbrock M, Doran D (2019). dbscan: Fast Density-Based Clustering with R. Journal of Statistical Software, 91(1), 1-30. doi:10.18637/jss.v091.i01

See Also

Useful links:


DBCV Paper Datasets

Description

The four synthetic 2D datasets used in Moulavi et al (2014).

Format

Four data frames with the following 3 variables.

x

a numeric vector

y

a numeric vector

class

an integer vector indicating the class label. 0 means noise.

Source

https://github.com/pajaskowiak/dbcv

References

Davoud Moulavi and Pablo A. Jaskowiak and Ricardo J. G. B. Campello and Arthur Zimek and Jörg Sander (2014). Density-Based Clustering Validation. In Proceedings of the 2014 SIAM International Conference on Data Mining, pages 839-847 doi:10.1137/1.9781611973440.96

Examples

data("Dataset_1")
clplot(Dataset_1[, c("x", "y")], cl = Dataset_1$class)

data("Dataset_2")
clplot(Dataset_2[, c("x", "y")], cl = Dataset_2$class)

data("Dataset_3")
clplot(Dataset_3[, c("x", "y")], cl = Dataset_3$class)

data("Dataset_4")
clplot(Dataset_4[, c("x", "y")], cl = Dataset_4$class)

DS3: Spatial data with arbitrary shapes

Description

Contains 8000 2-d points, with 6 "natural" looking shapes, all of which have an sinusoid-like shape that intersects with each cluster. The data set was originally used as a benchmark data set for the Chameleon clustering algorithm (Karypis, Han and Kumar, 1999) to illustrate the a data set containing arbitrarily shaped spatial data surrounded by both noise and artifacts.

Format

A data.frame with 8000 observations on the following 2 columns:

X

a numeric vector

Y

a numeric vector

Source

Obtained from the Clustering Datasets Repository, University of Joensuu, Finland.

References

Karypis, George, Eui-Hong Han, and Vipin Kumar (1999). Chameleon: Hierarchical clustering using dynamic modeling. Computer 32(8): 68-75.

Examples

data(DS3)
plot(DS3, pch = 20, cex = 0.25)

NN — Nearest Neighbors Superclass

Description

NN is an abstract S3 superclass for the classes of the objects returned by kNN(), frNN() and sNN(). Methods for sorting, plotting and getting an adjacency list are defined.

Usage

adjacencylist(x, ...)

## S3 method for class 'NN'
adjacencylist(x, ...)

## S3 method for class 'NN'
sort(x, decreasing = FALSE, ...)

## S3 method for class 'NN'
plot(
  x,
  data,
  main = NULL,
  pch = 16,
  col = "black",
  linecol = "gray",
  xlab = NULL,
  ylab = NULL,
  ...
)

Arguments

x

a NN object

...

further parameters are passed on to graphics::plot.default().

decreasing

sort in decreasing order?

data

that was used to create x

main

title

pch

plotting character.

col

color used for the data points (nodes). Use NULL to make the points invisible.

linecol

color used for edges.

xlab, ylab

axis labels. The default is to use the column names of data or, if the data is projected, the principal components with the percentage of variance they explain.

Details

plot() draws the neighborhood graph in the first two dimensions of data. If data has more than two columns, then the data is first projected onto its first two principal components using stats::prcomp() (centered, but not scaled, so Euclidean distances are preserved as well as possible) and the graph is drawn in the projection.

Subclasses

kNN, frNN and sNN

Author(s)

Michael Hahsler

See Also

Other NN functions: comps(), frNN(), kNN(), kNNdist(), sNN()

Examples

data(iris)
x <- iris[, -5]

# finding kNN directly in data (using a k-d tree)
nn <- kNN(x, k=5)
nn

# plot the kNN where NN are shown as line connecting points.
# Since the data has more than 2 dimensions, a PCA projection is used.
plot(nn, x)

# show the first few elements of the adjacency list
head(adjacencylist(nn))

## Not run: 
# create a graph and find connected components (if igraph is installed)
library("igraph")
g <- graph_from_adj_list(adjacencylist(nn))
comp <- components(g)
plot(x, col = comp$membership)

# detect clusters (communities) with the label propagation algorithm
cl <- membership(cluster_label_prop(g))
plot(x, col = cl)

## End(Not run)

Find Connected Components in a Nearest-neighbor Graph

Description

Generic function and methods to find connected components in nearest neighbor graphs.

Usage

comps(x, ...)

## S3 method for class 'dist'
comps(x, eps, ...)

## S3 method for class 'kNN'
comps(x, mutual = FALSE, ...)

## S3 method for class 'sNN'
comps(x, ...)

## S3 method for class 'frNN'
comps(x, ...)

Arguments

x

the NN object representing the graph or a dist object

...

further arguments are currently unused.

eps

threshold on the distance

mutual

for a pair of points, do both have to be in each other's neighborhood?

Details

Note that for kNN graphs, one point may be in the kNN of the other but nor vice versa. mutual = TRUE requires that both points are in each other's kNN.

Value

an integer vector with component assignments.

Author(s)

Michael Hahsler

See Also

Other NN functions: NN, frNN(), kNN(), kNNdist(), sNN()

Examples

set.seed(665544)
n <- 100
x <- cbind(
  x=runif(10, 0, 5) + rnorm(n, sd = 0.4),
  y=runif(10, 0, 5) + rnorm(n, sd = 0.4)
  )
plot(x, pch = 16)

# Connected components on a graph where each pair of points
# with a distance less or equal to eps are connected
d <- dist(x)
components <- comps(d, eps = .8)
plot(x, col = components, pch = 16)

# Connected components in a fixed radius nearest neighbor graph
# Gives the same result as the threshold on the distances above
frnn <- frNN(x, eps = .8)
components <- comps(frnn)
plot(frnn, data = x, col = components)

# Connected components on a k nearest neighbors graph
knn <- kNN(x, 3)
components <- comps(knn, mutual = FALSE)
plot(knn, data = x, col = components)

components <- comps(knn, mutual = TRUE)
plot(knn, data = x, col = components)

# Connected components in a shared nearest neighbor graph
snn <- sNN(x, k = 10, kt = 5)
components <- comps(snn)
plot(snn, data = x, col = components)

Density-Based Clustering Validation Index (DBCV)

Description

Calculate the Density-Based Clustering Validation Index (DBCV) for a clustering.

Usage

dbcv(x, cl, d, metric = "euclidean", sample = NULL)

Arguments

x

a data matrix or a dist object.

cl

a clustering (e.g., a integer vector)

d

dimensionality of the original data if a dist object is provided.

metric

distance metric used. The available metrics are the methods implemented by dist() plus "sqeuclidean" for the squared Euclidean distance used in the original DBCV implementation.

sample

sample size used for large datasets.

Details

DBCV (Moulavi et al, 2014) computes a score based on the density sparseness of each cluster and the density separation of each pair of clusters.

The density sparseness of a cluster (DSC) is defined as the maximum edge weight of a minimal spanning tree for the internal points of the cluster using the mutual reachability distance based on the all-points-core-distance. Internal points are connected to more than one other point in the cluster. Since clusters of a size less than 3 cannot have internal points, they are ignored (considered noise) in this implementation.

The density separation of a pair of clusters (DSPC) is defined as the minimum reachability distance between the internal nodes of the spanning trees of the two clusters.

The validity index for a cluster is calculated using these measures and aggregated to a validity index for the whole clustering using a weighted average.

The index is in the range [-1,1]. If the cluster density compactness is better than the density separation, a positive value is returned. The actual value depends on the separability of the data. In general, greater values of the measure indicating a better density-based clustering solution.

Noise points are included in the calculation only in the weighted average, therefore clustering with more noise points will get a lower index.

Performance note: This implementation calculates a distance matrix and thus can only be used for small or sampled datasets.

Value

A list with the DBCV score for the clustering, the density sparseness of cluster (dsc) values, the density separation of pairs of clusters (dspc) distances, and the validity indices of clusters (v_c).

Author(s)

Matt Piekenbrock and Michael Hahsler

References

Davoud Moulavi and Pablo A. Jaskowiak and Ricardo J. G. B. Campello and Arthur Zimek and Jörg Sander (2014). Density-Based Clustering Validation. In Proceedings of the 2014 SIAM International Conference on Data Mining, pages 839-847 doi:10.1137/1.9781611973440.96

Pablo A. Jaskowiak (2022). MATLAB implementation of DBCV. https://github.com/pajaskowiak/dbcv

Examples

# Load a test dataset
data(Dataset_1)
x <- Dataset_1[, c("x", "y")]
class <- Dataset_1$class

clplot(x, class)

# We use MinPts 3 and use the knee at eps = .1 for dbscan
kNNdistplot(x, minPts = 3)

cl <- dbscan(x, eps = .1, minPts = 3)
clplot(x, cl)

dbcv(x, cl)

# compare to the DBCV index on the original class labels and
# with a random partitioning
dbcv(x, class)
dbcv(x, sample(1:4, replace = TRUE, size = nrow(x)))

# find the best eps using dbcv
eps_grid <- seq(.05,.2, by = .01)
cls <- lapply(eps_grid, FUN = function(e) dbscan(x, eps = e, minPts = 3))
dbcvs <- sapply(cls, FUN = function(cl) dbcv(x, cl)$score)

plot(eps_grid, dbcvs, type = "l")

eps_opt <- eps_grid[which.max(dbcvs)]
eps_opt

cl <- dbscan(x, eps = eps_opt, minPts = 3)
clplot(x, cl)

Density-based Spatial Clustering of Applications with Noise (DBSCAN)

Description

Fast reimplementation of the DBSCAN (Density-based spatial clustering of applications with noise) clustering algorithm using a k-d tree.

Usage

dbscan(x, eps, minPts = 5, weights = NULL, borderPoints = TRUE, ...)

is.corepoint(x, eps, minPts = 5, ...)

## S3 method for class 'dbscan_fast'
predict(object, newdata, data, ...)

Arguments

x

a data matrix, a data.frame, a dist object or a frNN object with fixed-radius nearest neighbors.

eps

size (radius) of the epsilon neighborhood. Can be omitted if x is a frNN object.

minPts

number of minimum points required in the eps neighborhood for core points (including the point itself).

weights

numeric; weights for the data points. Only needed to perform weighted clustering. The sum of the weights of the points in an eps neighborhood (instead of their number) is compared to minPts.

borderPoints

logical; should border points be assigned to clusters. The default is TRUE for regular DBSCAN. If FALSE then border points are considered noise (see DBSCAN* in Campello et al, 2013).

...

additional arguments are passed on to the fixed-radius nearest neighbor search algorithm. See frNN() for details on how to control the search strategy.

object

clustering object.

newdata

new data points for which the cluster membership should be predicted.

data

the data set used to create the clustering object.

Details

The implementation is significantly faster and can work with larger data sets than fpc::dbscan() in fpc. Use dbscan::dbscan() (with specifying the package) to call this implementation when you also load package fpc.

The Algorithm

This implementation of DBSCAN follows the original algorithm as described by Ester et al (1996). DBSCAN performs the following steps:

  1. Estimate the density around each data point by counting the number of points in a user-specified eps-neighborhood and applies a user-specified minPts threshold to identify

    • core points (points with at least minPts points in their neighborhood, including the point itself),

    • border points (non-core points with a core point in their neighborhood) and

    • noise points (all other points).

  2. Core points form the backbone of clusters by joining them into a cluster if they are density-reachable from each other (i.e., there is a chain of core points where one falls inside the eps-neighborhood of the next).

  3. Border points are assigned to clusters.

The algorithm needs the parameters eps (the radius of the epsilon neighborhood) and minPts (the density threshold).

Border points are arbitrarily assigned to clusters in the original algorithm. DBSCAN* (see Campello et al 2013) treats all border points as noise points. This is implemented with borderPoints = FALSE.

Specifying the Data

If x is a matrix or a data.frame, then fast fixed-radius nearest neighbor computation using a k-d tree is performed using Euclidean distance. See frNN() for more information on the parameters related to nearest neighbor search. Note that only numerical values are allowed in x.

Any precomputed distance matrix (dist object) can be specified as x. You may run into memory issues since distance matrices are large.

A precomputed frNN object can be supplied as x. In this case eps does not need to be specified. This option is useful for large data sets, where a sparse distance matrix is available. See frNN() how to create frNN objects.

Setting Parameters for DBSCAN

The parameters minPts and eps define the minimum density required in the area around core points which form the backbone of clusters. minPts is the number of points required in the neighborhood around the point defined by the parameter eps (i.e., the radius around the point). Both parameters depend on each other and changing one typically requires changing the other one as well. The parameters also depend on the size of the data set with larger datasets requiring a larger minPts or a smaller eps.

Predict Cluster Memberships

predict() can be used to predict cluster memberships for new data points. A point is considered a member of a cluster if it is within the eps neighborhood of a core point of the cluster. Points which cannot be assigned to a cluster will be reported as noise points (i.e., cluster ID 0). Important note: predict() currently can only use Euclidean distance to determine the neighborhood of core points. If dbscan() was called using distances other than Euclidean, then the neighborhood calculation will not be correct and only approximated by Euclidean distances. If the data contain factor columns (e.g., using Gower's distance), then the factors in data and query first need to be converted to numeric to use the Euclidean approximation.

Value

dbscan() returns an object of class dbscan_fast with the following components:

eps

value of the eps parameter.

minPts

value of the minPts parameter.

metric

used distance metric.

cluster

A integer vector with cluster assignments. Zero indicates noise points.

is.corepoint() returns a logical vector indicating for each data point if it is a core point.

Author(s)

Michael Hahsler

References

Hahsler M, Piekenbrock M, Doran D (2019). dbscan: Fast Density-Based Clustering with R. Journal of Statistical Software, 91(1), 1-30. doi:10.18637/jss.v091.i01

Martin Ester, Hans-Peter Kriegel, Joerg Sander, Xiaowei Xu (1996). A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise. Institute for Computer Science, University of Munich. Proceedings of 2nd International Conference on Knowledge Discovery and Data Mining (KDD-96), 226-231. https://dl.acm.org/doi/10.5555/3001460.3001507

Campello, R. J. G. B.; Moulavi, D.; Sander, J. (2013). Density-Based Clustering Based on Hierarchical Density Estimates. Proceedings of the 17th Pacific-Asia Conference on Knowledge Discovery in Databases, PAKDD 2013, Lecture Notes in Computer Science 7819, p. 160. doi:10.1007/978-3-642-37456-2_14

Sander, J., Ester, M., Kriegel, HP. et al. (1998). Density-Based Clustering in Spatial Databases: The Algorithm GDBSCAN and Its Applications. Data Mining and Knowledge Discovery 2, 169-194. doi:10.1023/A:1009745219419

See Also

Other clustering functions: extractFOSC(), hdbscan(), jpclust(), ncluster(), optics(), sNNclust()

Examples

## Example 1: use dbscan on the iris data set
data(iris)
iris <- as.matrix(iris[, 1:4])

## Find suitable DBSCAN parameters:
## 1. We use minPts = dim + 1 = 5 for iris. A larger value can also be used.
## 2. We inspect the k-NN distance plot for k = minPts - 1 = 4
kNNdistplot(iris, minPts = 5)

## Noise seems to start around a 4-NN distance of .7
abline(h=.7, col = "red", lty = 2)

## Cluster with the chosen parameters
res <- dbscan(iris, eps = .7, minPts = 5)
res

pairs(iris, col = res$cluster + 1L)
clplot(iris, res)

## Use a precomputed frNN object
fr <- frNN(iris, eps = .7)
dbscan(fr, minPts = 5)

## Example 2: use data from fpc
set.seed(665544)
n <- 100
x <- cbind(
  x = runif(10, 0, 10) + rnorm(n, sd = 0.2),
  y = runif(10, 0, 10) + rnorm(n, sd = 0.2)
  )

res <- dbscan(x, eps = .3, minPts = 3)
res

## plot clusters and add noise (cluster 0) as crosses.
plot(x, col = res$cluster)
points(x[res$cluster == 0, ], pch = 3, col = "grey")

clplot(x, res)
hullplot(x, res)

## Predict cluster membership for new data points
## (Note: 0 means it is predicted as noise)
newdata <- x[1:5,] + rnorm(10, 0, .3)
hullplot(x, res)
points(newdata, pch = 3 , col = "red", lwd = 3)
text(newdata, pos = 1)

pred_label <- predict(res, newdata, data = x)
pred_label
points(newdata, col = pred_label + 1L,  cex = 2, lwd = 2)

## Compare speed against fpc version (if microbenchmark is installed)
## Note: we use dbscan::dbscan to make sure that we do now run the
## implementation in fpc.
## Not run: 
if (requireNamespace("fpc", quietly = TRUE) &&
    requireNamespace("microbenchmark", quietly = TRUE)) {
  t_dbscan <- microbenchmark::microbenchmark(
    dbscan::dbscan(x, .3, 3), times = 10, unit = "ms")
  t_dbscan_linear <- microbenchmark::microbenchmark(
    dbscan::dbscan(x, .3, 3, search = "linear"), times = 10, unit = "ms")
  t_dbscan_dist <- microbenchmark::microbenchmark(
    dbscan::dbscan(x, .3, 3, search = "dist"), times = 10, unit = "ms")
  t_fpc <- microbenchmark::microbenchmark(
    fpc::dbscan(x, .3, 3), times = 10, unit = "ms")

  r <- rbind(t_fpc, t_dbscan_dist, t_dbscan_linear, t_dbscan)
  r

  boxplot(r,
    names = c('fpc', 'dbscan (dist)', 'dbscan (linear)', 'dbscan (kdtree)'),
    main = "Runtime comparison in ms")

  ## speedup of the k-d tree-based version compared to the fpc implementation
  median(t_fpc$time) / median(t_dbscan$time)
}
## End(Not run)

## Example 3: manually create a frNN object for dbscan (dbscan only needs ids and eps)
nn <- structure(list(id = list(c(2,3), c(1,3), c(1,2,3), c(3,5), c(4,5)), eps = 1),
  class =  c("NN", "frNN"))
nn
dbscan(nn, minPts = 2)


Turn a dbscan clustering object into a tidy tibble

Description

Provides tidy(), augment(), and glance() verbs for clusterings created with algorithms in package dbscan to work with tidymodels.

Usage

tidy(x, ...)

## S3 method for class 'dbscan'
tidy(x, ...)

## S3 method for class 'hdbscan'
tidy(x, ...)

## S3 method for class 'general_clustering'
tidy(x, ...)

augment(x, ...)

## S3 method for class 'dbscan'
augment(x, data = NULL, newdata = NULL, ...)

## S3 method for class 'hdbscan'
augment(x, data = NULL, newdata = NULL, ...)

## S3 method for class 'general_clustering'
augment(x, data = NULL, newdata = NULL, ...)

glance(x, ...)

## S3 method for class 'dbscan'
glance(x, ...)

## S3 method for class 'hdbscan'
glance(x, ...)

## S3 method for class 'general_clustering'
glance(x, ...)

Arguments

x

A clustering object returned by dbscan(), hdbscan(), jpclust() or sNNclust().

...

further arguments are ignored without a warning.

data

The data used to create the clustering.

newdata

New data to predict cluster labels for.

Details

Methods are available for the clustering objects created by dbscan(), hdbscan(), jpclust() and sNNclust(). Clusterings created by optics() are not supported.

All three verbs return a tibble. Cluster 0 represents noise points. Noise points are not assigned to a cluster.

tidy()

Returns one row per cluster, including the noise cluster 0, with the columns:

augment()

Returns the data (or newdata) as a tibble with additional columns. The original data used to create the clustering always needs to be passed as data because the clustering object does not store it. If newdata is specified, then the cluster labels of the new points are predicted with predict(). Otherwise, the labels in the clustering are used. The added columns are:

Augmenting newdata is not supported for jpclust() and sNNclust().

glance()

Returns a one-row summary of the clustering with the columns:

Value

A tibble (see Details for the columns).

See Also

generics::tidy(), generics::augment(), generics::glance(), dbscan()

Examples



data(iris)
x <- scale(iris[, 1:4])

## dbscan
db <- dbscan(x, eps = .9, minPts = 5)
db

# summarize model fit with tidiers
tidy(db)
glance(db)

# augment for this model needs the original data
augment(db, x)

# to augment new data, the original data is also needed
augment(db, x, newdata = x[1:5, ])

## hdbscan
hdb <- hdbscan(x, minPts = 5)

# summarize model fit with tidiers
tidy(hdb)
glance(hdb)

# augment for this model needs the original data
augment(hdb, x)

# to augment new data, the original data is also needed
augment(hdb, x, newdata = x[1:5, ])

## Jarvis-Patrick clustering
cl <- jpclust(x, k = 20, kt = 15)

# summarize model fit with tidiers
tidy(cl)
glance(cl)

# augment for this model needs the original data
augment(cl, x)

## Shared Nearest Neighbor clustering
cl <- sNNclust(x, k = 20, eps = 0.8, minPts = 15)

# summarize model fit with tidiers
tidy(cl)
glance(cl)

# augment for this model needs the original data
augment(cl, x)


Coercions to Dendrogram

Description

Provides a new generic function to coerce objects to dendrograms with stats::as.dendrogram() as the default. Additional methods for hclust, hdbscan and reachability objects are provided.

Usage

as.dendrogram(object, ...)

## Default S3 method:
as.dendrogram(object, ...)

## S3 method for class 'hclust'
as.dendrogram(object, ...)

## S3 method for class 'hdbscan'
as.dendrogram(object, ...)

## S3 method for class 'reachability'
as.dendrogram(object, ...)

Arguments

object

the object

...

further arguments

Details

Coercion methods for hclust, hdbscan and reachability objects to dendrogram are provided.

The coercion from hclust is a faster C++ reimplementation of the coercion in package stats. The original implementation can be called using stats::as.dendrogram().

The coercion from hdbscan builds the non-simplified HDBSCAN hierarchy as a dendrogram object.


Framework for the Optimal Extraction of Clusters from Hierarchies

Description

Generic reimplementation of the Framework for Optimal Selection of Clusters (FOSC; Campello et al, 2013) to extract clusterings from hierarchical clustering (i.e., hclust objects). Can be parameterized to perform unsupervised cluster extraction through a stability-based measure, or semisupervised cluster extraction through either a constraint-based extraction (with a stability-based tiebreaker) or a mixed (weighted) constraint and stability-based objective extraction.

Usage

extractFOSC(
  x,
  constraints,
  alpha = 0,
  minPts = NULL,
  prune_unstable = FALSE,
  validate_constraints = FALSE,
  cluster_selection_epsilon = 0
)

Arguments

x

a valid hclust object created via hclust() or the result of hdbscan(). For an hdbscan() result, its hierarchy (the hc component) is used.

constraints

Pairwise constraints given as a list, a vector (like a dist object) or a matrix. If missing, an unsupervised measure of stability is used to make local cuts and extract the optimal clusters. See details.

alpha

numeric; weight between [0, 1] for mixed-objective semi-supervised extraction. Defaults to 0.

minPts

integer; minimum cluster size to extract (must be at least 2). The default value of NULL uses for an x that was created by hdbscan() its stored minPts value, otherwise 2 is used.

prune_unstable

logical; should significantly unstable subtrees be pruned? The default is FALSE for the original optimal extraction framework (see Campello et al, 2013). See details for what TRUE implies.

validate_constraints

logical; should constraints be checked for validity? See details for what are considered valid constraints.

cluster_selection_epsilon

double; a distance threshold below which no clusters should be selected (see Malzer & Baum 2020, and hdbscan()). The default of 0.0 means this feature is not used.

Details

Campello et al (2013) suggested a Framework for Optimal Selection of Clusters (FOSC) as a framework to make local (non-horizontal) cuts to any cluster tree hierarchy. This function implements the original extraction algorithms as described by the framework for hclust objects. Traditional cluster extraction methods from hierarchical representations (such as hclust objects) generally rely on global parameters or cutting values which are used to partition a cluster hierarchy into a set of disjoint, flat clusters. This is implemented in R in function stats::cutree(). Although such methods are widespread, using global parameter settings are inherently limited in that they cannot capture patterns within the cluster hierarchy at varying local levels of granularity.

The role of minPts for condensing the clustering tree

Rather than partitioning a hierarchy based on the number of the cluster one expects to find (k) or based on some linkage distance threshold (H), the FOSC proposes that the optimal clusters may exist at varying distance thresholds in the hierarchy. To enable this idea, FOSC uses the minPts parameter. It represents the minimum number of points that constitute a valid cluster. The first step of the FOSC algorithm is to traverse the given cluster hierarchy divisively, recording new clusters at each split if both branches represent more than or equal to minPts. Branches that contain less than minPts points at one or both branches inherit the parent clusters identity. Note that using FOSC, due to the constraint that minPts must be greater than or equal to 2, points that leave a cluster in a branch with fewer than minPts points are not part of any new cluster. Depending on the local cuts chosen by the optimal solution, such points can end up as noise, which is denoted as 0 in the final solution.

For a hierarchy created by hdbscan(), extractFOSC() recomputes the stability on the raw hierarchy using minPts. By default, the minPts value stored in the hierarchy is used, but a different value can be specified: minPts in hdbscan() controls noise and density estimate smoothing, while minPts in extractFOSC() controls the cluster scale.

Cluster extraction

The simplified cluster tree is then post-processed recursively to extract clusters that maximize for each cluster C_i the cost function

\max_{\delta_2, \dots, \delta_k} J = \sum\limits_{i=2}^{k} \delta_i S(C_i)

where S(C_i) is the stability-based measure as

S(C_i) = \sum_{x_j \in C_i}(\frac{1}{h_{min} (x_j, C_i)} - \frac{1}{h_{max} (C_i)})

\delta_i represents an indicator function, which constrains the solution space such that clusters must be disjoint (cannot assign more than 1 label to each cluster). The measure S(C_i) used by FOSC is an unsupervised validation measure based on the assumption that, if you vary the linkage/distance threshold across all possible values, more prominent clusters that survive over many threshold variations should be considered as stronger candidates of the optimal solution. For this reason, using this measure to detect clusters is referred to as an unsupervised, stability-based extraction approach. In some cases it may be useful to enact instance-level constraints that ensure the solution space conforms to linkage expectations known a priori. This general idea of using preliminary expectations to augment the clustering solution will be referred to as semisupervised clustering. If constraints are given in the call to extractFOSC(), the following alternative objective function is maximized:

J = \frac{1}{2n_c}\sum\limits_{j=1}^n \gamma (x_j)

n_c is the total number of constraints given and \gamma(x_j) represents the number of constraints involving object x_j that are satisfied. In the case of ties (such as solutions where no constraints were given), the unsupervised solution is used as a tiebreaker. See Campello et al (2013) for more details.

To prioritize the degree at which the unsupervised and semisupervised solutions contribute to the overall optimal solution, the parameter \alpha can be set to enable the extraction of clusters that maximize the mixed objective function

J = \alpha S(C_i) + (1 - \alpha) \gamma(C_i)

FOSC expects the pairwise constraints to be passed as either 1) an n(n-1)/2 vector of integers representing the constraints, where 1 represents should-link, -1 represents should-not-link, and 0 represents no preference using the unsupervised solution (see below for examples). Alternatively, if only a few constraints are needed, a named list representing the (symmetric) adjacency list can be used, where the names correspond to indices of the points in the original data, and the values correspond to integer vectors of constraints (positive indices for should-link, negative indices for should-not-link). Again, see the examples section for a demonstration of this.

If validate_constraints is TRUE, the constraints are checked (and fixed) for symmetry (if point A has a should-link constraint with point B, point B should also have the same constraint). Asymmetric constraints are not supported. The mixed objective function is used if alpha is greater than 0.

Unstable branch pruning

Unstable branch pruning was not discussed by Campello et al (2013), however in some data sets it may be the case that specific subbranches scores are significantly greater than sibling and parent branches, and thus sibling branches should be considered as noise if their scores are cumulatively lower than the parents. This can happen in extremely nonhomogeneous data sets, where there exists locally very stable branches surrounded by unstable branches that contain more than minPts points. prune_unstable = TRUE will remove the unstable branches.

Value

A list with the elements:

cluster

A integer vector with cluster assignments. Zero indicates noise points (if any). The cluster ids are the ids of the clusters in the simplified cluster tree and are therefore not necessarily consecutive.

hc

The original hclust object with additional list elements "cluster" (the id of the cluster assigned to each of the n - 1 merge steps), "stability", "constraint", and "total" for the n - 1 cluster-wide objective scores from the extraction.

Author(s)

Matt Piekenbrock

References

Campello, Ricardo JGB, Davoud Moulavi, Arthur Zimek, and Joerg Sander (2013). A framework for semi-supervised and unsupervised optimal extraction of clusters from hierarchies. Data Mining and Knowledge Discovery 27(3): 344-371. doi:10.1007/s10618-013-0311-4

See Also

hclust(), hdbscan(), stats::cutree()

Other clustering functions: dbscan(), hdbscan(), jpclust(), ncluster(), optics(), sNNclust()

Other HDBSCAN functions: glosh(), hdbscan(), mst_dist()

Examples

data("moons")

## Regular HDBSCAN using stability-based extraction (unsupervised)
cl <- hdbscan(moons, minPts = 5)
cl$cluster
hullplot(moons, cl)

## Semisupervised constraint-based extraction from the HDBSCAN hierarchy
## alpha = 0: clusters are chosen to satisfy as many constraints as possible,
##            cluster stability only breaks ties.
## constraint: point 12 should link with 49, but not with 47
cl_con <- extractFOSC(cl$hc, minPts = 5,
  constraints = list("12" = c(+49, -47)),
  alpha = 0)
cl_con$cluster
hullplot(moons, cl_con)

## Semisupervised alternative formulation using constraints on distances
## constraint: +1: Link points with a distance < 0.1;
##             -1: do not link points with distance > 1.0;
##              0: no preference for all other links.
dist_moons <- dist(moons)
cl_con2 <- extractFOSC(cl$hc, minPts = 5,
  constraints = ifelse(dist_moons < 0.1, +1L,
                ifelse(dist_moons > 1.0, -1L, 0L)),
  alpha = 0)
hullplot(moons, cl_con)

## Unsupervised extraction with a distance threshold (HDBSCAN(e))
cl_dist <- extractFOSC(cl$hc, cluster_selection_epsilon = 1)
hullplot(moons, cl_dist)

Find the Fixed Radius Nearest Neighbors

Description

This function finds the fixed radius nearest neighbors (including distances) fast.

Usage

frNN(
  x,
  eps,
  query = NULL,
  sort = TRUE,
  search = "kdtree",
  bucketSize = 10,
  splitRule = "suggest",
  shrinkRule = "suggest",
  approx = 0
)

## S3 method for class 'frNN'
sort(x, decreasing = FALSE, ...)

## S3 method for class 'frNN'
adjacencylist(x, ...)

## S3 method for class 'frNN'
print(x, ...)

Arguments

x

a data matrix, a dist object or a frNN object.

eps

radius of the neighborhood (a finite, non-negative number). Points within this distance are neighbors.

query

a data matrix with the points to query. If query is not specified, the NN for all the points in x is returned. If query is specified then x needs to be a data matrix.

sort

sort the neighbors of each point by distance (ties are broken by id)? This is expensive and can be done later using sort().

search

nearest neighbor search strategy (one of "kdtree", "linear", "dist" or "bdtree"). See the section on the search parameters.

bucketSize

max size of the k-d or bd tree leafs.

splitRule

rule to split the k-d or bd tree. One of "std", "midpt", "fair", "sl_midpt", "sl_fair" or "suggest" (SL stands for sliding). The default value "suggest" uses ANNs best guess.

shrinkRule

shrinking rule used to build the box-decomposition tree (only used for search = "bdtree"). One of "none" (no shrinking, equivalent to a k-d tree), "simple", "centroid" or "suggest". The default value "suggest" uses ANNs best guess.

approx

a non-negative number used for approximate nearest neighbors. All NN up to a distance of eps / (1 + approx) are considered and none with a distance greater than eps. The points in between might be considered. Some actual NN may be omitted, but the search will be faster. Ignored by search = "linear" and "dist".

decreasing

for sort(), sort the neighbors by decreasing distance instead of increasing distance?

...

further arguments (ignored).

Details

If x is specified as a data matrix, then Euclidean distances and fast nearest neighbor lookup using a k-d tree (default), a box-decomposition tree or linear search are used (see the section on the search parameters). All points within a distance of eps of a point (including points at exactly distance eps) are its neighbors.

Sorting and self-matches

Using a frNN object as x

If x is a frNN object, then the neighborhoods are reduced to the smaller radius eps. An error is raised if eps is larger than the radius stored in x. All other arguments are ignored.

Input requirements

Memory

The size of the result grows with the number of neighbors of all points, which can approach O(n^2) for a large eps. Choose eps carefully for large data sets.

Creating a frNN object from scratch

A frNN object is a list with class c("frNN", "NN") and the components described in the value section. You need to supply at least id and eps. dist is needed for sorting and plotting, and sort should be set to FALSE unless the neighbors are already sorted. metric is informational.

Details on the search parameters:

Handling of NAs:

The tree-based searches and search = "linear" cannot handle NA, NaN or infinite values in the data (in x or query); an error is raised. (The ANN library does not check its input and would silently return wrong results.) With search = "dist", the distances are calculated by dist(), which leaves out coordinates that are NA for a pair of points and scales up the remaining sum. These distances are not exactly Euclidean distances. The resulting distance matrix (and a dist object supplied as x) cannot contain NAs, which happens, for example, if a point has only NA values. Otherwise, remove or impute missing values before performing the search.

Value

frNN() returns an object of class frNN (subclass of NN) containing a list with the following components:

id

a list with one integer vector per point in x (or query). Each vector contains the ids (row numbers in x) of the fixed radius nearest neighbors. A point without neighbors has an empty vector (integer(0)). The list is named with the row names if available.

dist

a list with the distances (same structure as id).

eps

neighborhood radius eps that was used.

sort

logical; are the neighbors of each point sorted by increasing distance (with ties broken by id)?

metric

used distance metric. This is "euclidean" for data matrices. For a dist object, it is the method stored in the object (which can be NULL).

adjacencylist() returns a list with one entry per data point in x. Each entry contains the id of the nearest neighbors.

Author(s)

Michael Hahsler

References

David M. Mount and Sunil Arya (2010). ANN: A Library for Approximate Nearest Neighbor Searching, http://www.cs.umd.edu/~mount/ANN/.

See Also

dbscan(), which accepts a precomputed frNN object.

Other NN functions: NN, comps(), kNN(), kNNdist(), sNN()

Examples

data(iris)
x <- iris[, -5]

# Example 1: Find fixed radius nearest neighbors for each point
nn <- frNN(x, eps = .5)
nn

# Number of neighbors
hist(lengths(adjacencylist(nn)),
  xlab = "Number of neighbors", main = "Number of Neighbors",
  sub = paste("Neighborhood size eps =", nn$eps))

# Explore neighbors of point i = 10
i <- 10
nn$id[[i]]
nn$dist[[i]]
plot(x, col = ifelse(seq_len(nrow(iris)) %in% nn$id[[i]], "red", "black"))

# get an adjacency list
head(adjacencylist(nn))

# plot the fixed radius neighbors (and then reduced to a radius of .3)
plot(nn, x)
plot(frNN(nn, eps = .3), x)

## Example 2: find fixed-radius NN for query points
q <- x[c(1,100),]
nn <- frNN(x, eps = .5, query = q)

plot(nn, x[, 1:2], col = "grey")
points(q, pch = 3, lwd = 2)

## Example 3: a precomputed frNN object can be used for DBSCAN
nn <- frNN(x, eps = .5)
db <- dbscan(nn, minPts = 5)
db

clplot(x, cl = db)

Global-Local Outlier Score from Hierarchies

Description

Calculate the Global-Local Outlier Score from Hierarchies (GLOSH) score for each data point using a k-d tree to speed up kNN search.

Usage

glosh(x, k = 4, ...)

Arguments

x

an hclust object, data matrix, or dist object.

k

size of the neighborhood.

...

further arguments are passed on to kNN().

Details

GLOSH compares the density of a point to densities of any points associated within current and child clusters (if any). Points that have a substantially lower density than the density mode (cluster) they most associate with are considered outliers. GLOSH is computed from a hierarchy a clusters.

Specifically, consider a point x and a density or distance threshold lambda. GLOSH is calculated by taking 1 minus the ratio of how long any of the child clusters of the cluster x belongs to "survives" changes in lambda to the highest lambda threshold of x, above which x becomes a noise point.

Scores close to 1 indicate outliers. For more details on the motivation for this calculation, see Campello et al (2015).

Value

A numeric vector of length equal to the size of the original data set containing GLOSH values for all data points.

Author(s)

Matt Piekenbrock

References

Campello, Ricardo JGB, Davoud Moulavi, Arthur Zimek, and Joerg Sander. Hierarchical density estimates for data clustering, visualization, and outlier detection. ACM Transactions on Knowledge Discovery from Data (TKDD) 10, no. 1 (2015). doi:10.1145/2733381

See Also

Other Outlier Detection Functions: kNNdist(), lof(), pointdensity()

Other HDBSCAN functions: extractFOSC(), hdbscan(), mst_dist()

Examples

set.seed(665544)
n <- 100
x <- cbind(
  x=runif(10, 0, 5) + rnorm(n, sd = 0.4),
  y=runif(10, 0, 5) + rnorm(n, sd = 0.4)
  )

### calculate GLOSH score
glosh <- glosh(x, k = 3)

### distribution of outlier scores
summary(glosh)
hist(glosh, breaks = 10)

### simple function to plot point size is proportional to GLOSH score
plot_glosh <- function(x, glosh){
  plot(x, pch = ".", main = "GLOSH (k = 3)")
  points(x, cex = glosh*3, pch = 1, col = "red")
  text(x[glosh > 0.80, ], labels = round(glosh, 3)[glosh > 0.80], pos = 3)
}
plot_glosh(x, glosh)

### GLOSH with any hierarchy
x_dist <- dist(x)
x_sl <- hclust(x_dist, method = "single")
x_upgma <- hclust(x_dist, method = "average")
x_ward <- hclust(x_dist, method = "ward.D2")

## Compare what different linkage criterion consider as outliers
glosh_sl <- glosh(x_sl, k = 3)
plot_glosh(x, glosh_sl)

glosh_upgma <- glosh(x_upgma, k = 3)
plot_glosh(x, glosh_upgma)

glosh_ward <- glosh(x_ward, k = 3)
plot_glosh(x, glosh_ward)

## GLOSH is automatically computed with HDBSCAN
all(hdbscan(x, minPts = 3)$outlier_scores == glosh(x, k = 3))

Hierarchical DBSCAN (HDBSCAN)

Description

Fast C++ implementation of the HDBSCAN (Hierarchical DBSCAN) and its related algorithms.

Usage

hdbscan(
  x,
  minPts,
  cluster_selection_epsilon = 0,
  gen_hdbscan_tree = FALSE,
  gen_simplified_tree = FALSE,
  verbose = FALSE
)

## S3 method for class 'hdbscan'
print(x, ...)

## S3 method for class 'hdbscan'
plot(
  x,
  scale = "suggest",
  gradient = c("yellow", "red"),
  show_flat = FALSE,
  main = "HDBSCAN*",
  ylab = "eps value",
  leaflab = "none",
  ...
)

coredist(x, minPts, ...)

mrdist(x, minPts, coredist = NULL)

## S3 method for class 'hdbscan'
predict(object, newdata, data, ...)

Arguments

x

a data matrix (Euclidean distances are used) or a dist object calculated with an arbitrary distance metric.

minPts

integer; Main parameter to control density estimate smoothing and the minimum clusters size. See details. For mrdist() (and mst_mrdist()) it can be omitted if coredist is specified.

cluster_selection_epsilon

double; a distance threshold below which no clusters should be selected (see Malzer & Baum 2020). The threshold is specified in mutual reachability distance (see mrdist()). The default of 0.0 means this feature is not used.

gen_hdbscan_tree

logical; should the robust single linkage tree be explicitly computed (see cluster tree in Chaudhuri et al, 2010).

gen_simplified_tree

logical; should the simplified hierarchy be explicitly computed (see Campello et al, 2013).

verbose

report progress.

...

additional arguments are passed on.

scale

integer; used to scale condensed tree based on the graphics device. Lower scale results in wider colored trees lines. The default 'suggest' sets scale to the number of clusters.

gradient

character vector; the colors to build the condensed tree coloring with.

show_flat

logical; whether to draw boxes indicating the most stable clusters.

main

Title of the plot.

ylab

the label for the y axis.

leaflab

a string specifying how leaves are labeled (see stats::plot.dendrogram()).

coredist

numeric vector with precomputed core distances (optional).

object

clustering object.

newdata

new data points for which the cluster membership should be predicted.

data

the data set used to create the clustering object.

Details

This fast implementation of HDBSCAN (Campello et al., 2013) computes the hierarchical cluster tree representing density estimates along with the stability-based flat cluster extraction. HDBSCAN essentially computes the hierarchy of all DBSCAN* clusterings, and then uses a stability-based extraction method to find optimal cuts in the hierarchy, thus producing a flat solution. It uses Prim's algorithm and is memory efficient by avoiding to create a complete distance matrix.

The algorithm

The algorithm uses as the main parameter minPts which is used in several of the HDBSCAN steps:

  1. Compute mutual reachability distances from core distances. For core distances, minPts is a smoothing parameter for the density estimates; larger values for minPts give larger and smoother density estimates.

  2. Construct a minimum spanning tree from the mutual reachability distances.

  3. Prune the tree using stability. Here minPts controls the minimum cluster size because splits are only allowed when both branches have at least minPts points.

  4. Extract the clusters from the pruned tree.

The individual steps are described in the following.

Core and mutual reachability distances

These can be calculated using the following two exposed functions:

To use non-Euclidean distances, the call hdbscan(), coredist(), or mrdist() with a precomputed distance matrix.

Minimum spanning tree construction

mst_dist() constructs a MST from a data from the mutual reachability distance matrix. Since distance matrices are of size O(n^2) and thus can become very large, mst_mrdist() is also provides which directly constructs the MST from matrix data without creating the full distance matrix. This reduces memory complexity O(d n) and speeds up the calculation, but only works with Euclidean distances.

Tree pruning and cluster selection

The MST is pruned using stability and clusters are extracted in the unsupervised version implemented in extractFOSC(). Because one minPts value sets both the density smoothing and the minimum cluster size in HDBSCAN, using a different minimum cluster size requires an explicit call to extractFOSC() with the new minPts, e.g., extractFOSC(res, minPts = 20). This keeps the density estimates using the original minPtsand the hierarchy of res, but recomputed stability and cluster extraction using the new minPts value.

HDBSCAN* and DBSCAN*

Campello, Moulavi, and Sander (2013) introduced DBSCAN* and HDBSCAN* and demonstrated that for a fixed minimum points parameter minPts, the HDBSCAN* hierarchy encodes a one-to-one correspondence with the complete set of flat clusterings obtainable by DBSCAN* across every possible radius eps. Malzer and Baum (2020) describe that a combination between DBSCAN* and HDBSCAN* can be achieved by using a cluster_selection_epsilon greater than 0.0. The tree below cluster_selection_epsilon produces a result identical to DBSCAN* with eps = cluster_selection_epsilon. The remaining part (on levels above the threshold) is still processed by HDBSCAN*'s stability-based selection algorithm and can therefore return clusters of variable densities. Note that there is not always a remaining part, especially if the parameter value is chosen too large, or if there aren't enough clusters of variable densities. In this case, the result will be equal to DBSCAN*. cluster_selection_epsilon is especially useful for cases where HDBSCAN* produces too many small clusters that need to be merged, while still being able to extract clusters of variable densities at higher levels.

Cluster membership prediction for new points

Related Methods

Value

hdbscan() returns object of class hdbscan with the following components:

cluster

A integer vector with cluster assignments. Zero indicates noise points.

minPts

value of the minPts parameter.

cluster_scores

The sum of the stability scores for each salient (flat) cluster. Corresponds to cluster IDs given the in "cluster" element.

membership_prob

The probability or individual stability of a point within its clusters. Between 0 and 1.

outlier_scores

The GLOSH outlier score of each point.

coredist

The core distance of each data point (see coredist()).

hc

An hclust object of the HDBSCAN hierarchy (the single-linkage hierarchy of the minimum spanning tree of the mutual reachability distances before condensing). It also stores the used minPts value and can be used as input for extractFOSC().

hdbscan_tree

A dendrogram of the hierarchy. Only present if gen_hdbscan_tree = TRUE.

simplified_tree

A dendrogram of the simplified hierarchy. Only present if gen_simplified_tree = TRUE.

coredist() returns a vector with the core distance for each data point.

mrdist() returns a dist object containing pairwise mutual reachability distances.

Author(s)

Matt Piekenbrock

Claudia Malzer (added cluster_selection_epsilon)

References

Campello RJGB, Moulavi D, Sander J (2013). Density-Based Clustering Based on Hierarchical Density Estimates. Proceedings of the 17th Pacific-Asia Conference on Knowledge Discovery in Databases, PAKDD 2013, Lecture Notes in Computer Science 7819, p. 160. doi:10.1007/978-3-642-37456-2_14

Campello RJGB, Moulavi D, Zimek A, Sander J (2015). Hierarchical density estimates for data clustering, visualization, and outlier detection. ACM Transactions on Knowledge Discovery from Data (TKDD), 10(5):1-51. doi:10.1145/2733381

Malzer, C., & Baum, M. (2020). A Hybrid Approach To Hierarchical Density-based Cluster Selection. In 2020 IEEE International Conference on Multisensor Fusion and Integration for Intelligent Systems (MFI), pp. 223-228. doi:10.1109/MFI49285.2020.9235263

See Also

Other HDBSCAN functions: extractFOSC(), glosh(), mst_dist()

Other clustering functions: dbscan(), extractFOSC(), jpclust(), ncluster(), optics(), sNNclust()

Examples

## cluster the moons data set with HDBSCAN
data(moons)

res <- hdbscan(moons, minPts = 5)
res

plot(res)
clplot(moons, res)

## cluster the moons data set with HDBSCAN using Manhattan distances
res <- hdbscan(dist(moons, method = "manhattan"), minPts = 5)
plot(res)
clplot(moons, res)

## Example for HDBSCAN(e) using cluster_selection_epsilon
# data with clusters of various densities.
X <- data.frame(
 x = c(
  0.08, 0.46, 0.46, 2.95, 3.50, 1.49, 6.89, 6.87, 0.21, 0.15,
  0.15, 0.39, 0.80, 0.80, 0.37, 3.63, 0.35, 0.30, 0.64, 0.59, 1.20, 1.22,
  1.42, 0.95, 2.70, 6.36, 6.36, 6.36, 6.60, 0.04, 0.71, 0.57, 0.24, 0.24,
  0.04, 0.04, 1.35, 0.82, 1.04, 0.62, 0.26, 5.98, 1.67, 1.67, 0.48, 0.15,
  6.67, 6.67, 1.20, 0.21, 3.99, 0.12, 0.19, 0.15, 6.96, 0.26, 0.08, 0.30,
  1.04, 1.04, 1.04, 0.62, 0.04, 0.04, 0.04, 0.82, 0.82, 1.29, 1.35, 0.46,
  0.46, 0.04, 0.04, 5.98, 5.98, 6.87, 0.37, 6.47, 6.47, 6.47, 6.67, 0.30,
  1.49, 3.21, 3.21, 0.75, 0.75, 0.46, 0.46, 0.46, 0.46, 3.63, 0.39, 3.65,
  4.09, 4.01, 3.36, 1.43, 3.28, 5.94, 6.35, 6.87, 5.60, 5.99, 0.12, 0.00,
  0.32, 0.39, 0.00, 1.63, 1.36, 5.67, 5.60, 5.79, 1.10, 2.99, 0.39, 0.18
  ),
 y = c(
  7.41, 8.01, 8.01, 5.44, 7.11, 7.13, 1.83, 1.83, 8.22, 8.08,
  8.08, 7.20, 7.83, 7.83, 8.29, 5.99, 8.32, 8.22, 7.38, 7.69, 8.22, 7.31,
  8.25, 8.39, 6.34, 0.16, 0.16, 0.16, 1.66, 7.55, 7.90, 8.18, 8.32, 8.32,
  7.97, 7.97, 8.15, 8.43, 7.83, 8.32, 8.29, 1.03, 7.27, 7.27, 8.08, 7.27,
  0.79, 0.79, 8.22, 7.73, 6.62, 7.62, 8.39, 8.36, 1.73, 8.29, 8.04, 8.22,
  7.83, 7.83, 7.83, 8.32, 8.11, 7.69, 7.55, 7.20, 7.20, 8.01, 8.15, 7.55,
  7.55, 7.97, 7.97, 1.03, 1.03, 1.24, 7.20, 0.47, 0.47, 0.47, 0.79, 8.22,
  7.13, 6.48, 6.48, 7.10, 7.10, 8.01, 8.01, 8.01, 8.01, 5.99, 8.04, 5.22,
  5.82, 5.14, 4.81, 7.62, 5.73, 0.55, 1.31, 0.05, 0.95, 1.59, 7.99, 7.48,
  8.38, 7.12, 2.01, 1.40, 0.00, 9.69, 9.47, 9.25, 2.63, 6.89, 0.56, 3.11
 )
)

## HDBSCAN splits one cluster
hdb <- hdbscan(X, minPts = 3)
plot(hdb, show_flat = TRUE)
hullplot(X, hdb, main = "HDBSCAN")

## DBSCAN* marks the least dense cluster as outliers
db <- dbscan(X, eps = 1, minPts = 3, borderPoints = FALSE)
hullplot(X, db, main = "DBSCAN*")

## HDBSCAN(e) mixes HDBSCAN AND DBSCAN* to find all clusters
hdbe <- hdbscan(X, minPts = 3, cluster_selection_epsilon = 1)
plot(hdbe, show_flat = TRUE)
hullplot(X, hdbe, main = "HDBSCAN(e)")

## Manually perform the steps of HDBSCAN
d <- mrdist(X, minPts = 3)
mst_hc <- mst_dist(d)
cl <- extractFOSC(mst_hc)
hullplot(X, cl$cluster, main = "HDBSCAN")

Plot Clusters

Description

clplot() produces a two-dimensional scatter plot of data points and colors the data points according to a supplied clustering. Noise points are marked as x. hullplot() also adds convex hulls to clusters.

Usage

hullplot(
  x,
  cl,
  col = NULL,
  pch = NULL,
  cex = 0.5,
  hull = TRUE,
  hull_lwd = 1,
  hull_lty = 1,
  solid = TRUE,
  alpha = 0.2,
  main = "Convex Cluster Hulls",
  xlab = NULL,
  ylab = NULL,
  ...
)

clplot(
  x,
  cl,
  col = NULL,
  pch = NULL,
  cex = 0.5,
  main = "Cluster Plot",
  xlab = NULL,
  ylab = NULL,
  ...
)

Arguments

x

a data matrix. If more than 2 columns are provided, then the data is plotted using the first two principal components.

cl

a clustering. Either a numeric cluster assignment vector or a clustering object (a list with an element named cluster).

col

colors used for clusters. Defaults to the standard palette. The first color (default is black) is used for noise/unassigned points (cluster id 0).

pch

a vector of plotting characters. By default o is used for points and x for noise points.

cex

expansion factor for symbols.

hull

logical; calculate and show convex hulls for clusters.

hull_lwd, hull_lty

line width and line type used for the convex hull.

solid, alpha

draw filled polygons instead of just lines for the convex hulls? alpha controls the level of alpha shading.

main

main title.

xlab, ylab

axis labels. The default is to use the column names of x or, if the data is projected, the principal components with the percentage of variance they explain.

...

further parameters are passed on to graphics::plot.default().

Author(s)

Michael Hahsler

Examples

set.seed(2)
n <- 400

x <- cbind(
  x = runif(4, 0, 1) + rnorm(n, sd = 0.1),
  y = runif(4, 0, 1) + rnorm(n, sd = 0.1)
  )
cl <- rep(1:4, times = 100)

### original data with true clustering
clplot(x, cl, main = "True clusters")
hullplot(x, cl, main = "True clusters")

### use different symbols for each cluster
clplot(x, cl, main = "True clusters", pch = cl)

### plot just the hulls
hullplot(x, cl, main = "True clusters", pch = NA)

### a version suitable for b/w printing)
hullplot(x, cl, main = "True clusters", solid = FALSE,
  col = c("grey", "black"), pch = cl)


### run some clustering algorithms and plot the results
db <- dbscan(x, eps = .07, minPts = 10)
clplot(x, db, main = "DBSCAN")
hullplot(x, db, main = "DBSCAN")

op <- optics(x, eps = 10, minPts = 10)
opDBSCAN <- extractDBSCAN(op, eps_cl = .07)
hullplot(x, opDBSCAN, main = "OPTICS")

opXi <- extractXi(op, xi = 0.05)
hullplot(x, opXi, main = "OPTICSXi")

# Extract minimal 'flat' clusters only
opXi <- extractXi(op, xi = 0.05, minimum = TRUE)
hullplot(x, opXi, main = "OPTICSXi")

km <- kmeans(x, centers = 4)
hullplot(x, km, main = "k-means")

hc <- cutree(hclust(dist(x)), k = 4)
hullplot(x, hc, main = "Hierarchical Clustering")

Jarvis-Patrick Clustering

Description

Fast C++ implementation of the Jarvis-Patrick clustering which first builds a shared nearest neighbor graph (k nearest neighbor sparsification) and then places two points in the same cluster if they are in each others nearest neighbor list and they share at least kt nearest neighbors.

Usage

jpclust(x, k, kt, ...)

Arguments

x

a data matrix/data.frame (Euclidean distance is used), a precomputed dist object or a kNN object created with kNN().

k

Neighborhood size for nearest neighbor sparsification. If x is a kNN object then k may be missing.

kt

threshold on the number of shared nearest neighbors (including the points themselves) to form clusters. Range: [1, k]

...

additional arguments are passed on to the k nearest neighbor search algorithm. See kNN() for details on how to control the search strategy.

Details

Following the original paper, the shared nearest neighbor list is constructed as the k neighbors plus the point itself (as neighbor zero). Therefore, the threshold kt needs to be in the range [1, k].

Fast nearest neighbors search with kNN() is only used if x is a matrix. In this case Euclidean distance is used.

Value

A object of class general_clustering with the following components:

cluster

A integer vector with cluster assignments. Zero indicates noise points.

type

name of used clustering algorithm.

metric

the distance metric used for clustering.

param

list of used clustering parameters.

Author(s)

Michael Hahsler

References

R. A. Jarvis and E. A. Patrick. 1973. Clustering Using a Similarity Measure Based on Shared Near Neighbors. IEEE Trans. Comput. 22, 11 (November 1973), 1025-1034. doi:10.1109/T-C.1973.223640

See Also

Other clustering functions: dbscan(), extractFOSC(), hdbscan(), ncluster(), optics(), sNNclust()

Examples

data("DS3")

# use a shared neighborhood of 20 points and require 12 shared neighbors
cl <- jpclust(DS3, k = 20, kt = 12)
cl

clplot(DS3, cl)
# Note: JP clustering does not consider noise and thus,
# the sine wave points chain clusters together.

# use a precomputed kNN object instead of the original data.
nn <- kNN(DS3, k = 30)
nn

cl <- jpclust(nn, k = 20, kt = 12)
cl

# cluster with noise removed (use low pointdensity to identify noise)
d <- pointdensity(DS3, eps = 25)
hist(d, breaks = 20)
DS3_noiseless <- DS3[d > 110,]

cl <- jpclust(DS3_noiseless, k = 20, kt = 10)
cl

clplot(DS3_noiseless, cl)

Find the k Nearest Neighbors

Description

This function finds all k nearest neighbors in a data matrix (including distances).

Usage

kNN(
  x,
  k,
  query = NULL,
  sort = TRUE,
  search = "kdtree",
  bucketSize = 10,
  splitRule = "suggest",
  shrinkRule = "suggest",
  approx = 0
)

## S3 method for class 'kNN'
sort(x, decreasing = FALSE, ...)

## S3 method for class 'kNN'
adjacencylist(x, ...)

## S3 method for class 'kNN'
print(x, ...)

Arguments

x

a numeric data matrix (or data.frame), a dist object or a kNN object.

k

number of neighbors to find.

query

a data matrix with the points to query. If query is not specified, the NN for all the points in x is returned. If query is specified then x needs to be a data matrix.

sort

sort the neighbors of each point by distance (ties are broken by id)? sort = FALSE skips this step and returns the neighbors in the order found by the search, which is faster. kNN objects can be sorted later using sort().

search

nearest neighbor search strategy (one of "kdtree", "linear", "dist" or "bdtree"). See the section on the search parameters.

bucketSize

max size of the k-d or bd tree leafs.

splitRule

rule to split the k-d or bd tree. One of "std", "midpt", "fair", "sl_midpt", "sl_fair" or "suggest" (SL stands for sliding). The default value "suggest" uses ANNs best guess.

shrinkRule

shrinking rule used to build the box-decomposition tree (only used for search = "bdtree"). One of "none" (no shrinking, equivalent to a k-d tree), "simple", "centroid" or "suggest". The default value "suggest" uses ANNs best guess.

approx

approximation factor for the tree-based searches. The j-th neighbor found is at most (1 + approx) times as far away as the true j-th nearest neighbor. 0 (default) gives exact results; larger values are faster, but some true nearest neighbors may be omitted. Ignored by search = "linear" and "dist".

decreasing

for sort(), sort the neighbors by decreasing distance instead of increasing distance?

...

further arguments (ignored).

Details

To speed up k nearest neighbors, a k-d tree is used for data matrices by default. Box-decomposition trees, linear search, and precomputing distance matrices are also available.

Using a kNN object as x

If x is a kNN object, then the first k neighbors are returned (sorted by distance). All other arguments are ignored. An error is raised if x contains fewer than k neighbors.

Sorting, ties and self-matches

Input requirements

Non-Euclidean distances

To use non-Euclidean distances, a distance matrix needs to be precomputed by the user and supplied as x. Note that this leads to restrictions of the number of observations that can be used since the distance matrix grows with O(n^2).

Details on the search parameters:

Handling of NAs:

The tree-based searches and search = "linear" cannot handle NA, NaN or infinite values in the data (in x or query); an error is raised. (The ANN library does not check its input and would silently return wrong results.) With search = "dist", the distances are calculated by dist(), which leaves out coordinates that are NA for a pair of points and scales up the remaining sum. These distances are not exactly Euclidean distances. The resulting distance matrix (and a dist object supplied as x) cannot contain NAs, which happens, for example, if a point has only NA values. Otherwise, remove or impute missing values before performing the search.

Value

An object of class kNN (subclass of NN) containing a list with the following components:

dist

a matrix with distances (one row per point in x or query, one column per neighbor).

id

a matrix with the row numbers in x of the neighbors.

k

number k used.

sort

logical; are the neighbors in each row sorted by increasing distance (with ties broken by id)?

metric

used distance metric. This is "euclidean" for data matrices. For a dist object, it is the method stored in the object (which can be NULL).

Author(s)

Michael Hahsler

References

David M. Mount and Sunil Arya (2010). ANN: A Library for Approximate Nearest Neighbor Searching, https://www.cs.umd.edu/~mount/ANN/.

See Also

Other NN functions: NN, comps(), frNN(), kNNdist(), sNN()

Examples

data(iris)
x <- iris[, -5]

# Example 1: finding kNN for all points in a data matrix (using a k-d tree)
nn <- kNN(x, k = 5)
nn

# explore neighborhood of point 10
i <- 10
nn$id[i,]
plot(x, col = ifelse(seq_len(nrow(iris)) %in% nn$id[i,], "red", "black"))

# visualize the 5 nearest neighbors
plot(nn, x)

# visualize a reduced 2-NN graph
plot(kNN(nn, k = 2), x)

# Example 2: find kNN for query points
q <- x[c(1,100),]
nn <- kNN(x, k = 10, query = q)

# we plot the first two features for iris
plot(nn, x[, 1:2], col = "grey")
points(q, pch = 3, lwd = 2)

# Example 3: find kNN using a precomputed (non-Euclidean) distance matrix
d <- dist(x, method = "manhattan")
nn <- kNN(d, k = 1)
plot(nn, x)

Calculate and Plot k-Nearest Neighbor Distances

Description

Fast calculation of the k-nearest neighbor distances for a dataset represented as a matrix of points. The kNN distance is defined as the distance from a point to its k nearest neighbor. The kNN distance plot displays the kNN distance of all points sorted from smallest to largest. The plot can be used to help find suitable parameter values for dbscan().

Usage

kNNdist(x, k, all = FALSE, ...)

kNNdistplot(
  x,
  k,
  minPts,
  type = "l",
  xlab = NULL,
  ylab = NULL,
  kNNdist_param = NULL,
  ...
)

Arguments

x

the data set as a matrix of points (Euclidean distance is used) or a precalculated dist object.

k

number of nearest neighbors used for the distance calculation. For kNNdistplot() also a range of values for k or minPts can be specified.

all

should a matrix with the distances to all k nearest neighbors be returned?

...

for kNNdist(), further arguments (e.g., k-d tree related parameters) are passed on to kNN(). For kNNdistplot(), further graphical parameters are passed on to graphics::plot.default() (or graphics::matplot() if several values of k are given).

minPts

to use a k-NN plot to determine a suitable eps value for dbscan(), minPts used in dbscan can be specified and will set k = minPts - 1.

type, xlab, ylab

plot type and axis labels for kNNdistplot(). The default NULL for xlab and ylab uses a descriptive label.

kNNdist_param

a named list of additional arguments (e.g., k-d tree related parameters) passed on to kNNdist() and then to kNN() by kNNdistplot(), for example, list(search = "linear").

Value

kNNdist() returns a numeric vector with the distance to its k nearest neighbor. If all = TRUE then a matrix with k columns containing the distances to all 1st, 2nd, ..., kth nearest neighbors is returned instead.

Author(s)

Michael Hahsler

See Also

Other Outlier Detection Functions: glosh(), lof(), pointdensity()

Other NN functions: NN, comps(), frNN(), kNN(), sNN()

Examples

data(iris)
iris <- as.matrix(iris[, 1:4])

## Find the 4-NN distance for each observation (see ?kNN
## for different search strategies)
kNNdist(iris, k = 4)

## Get a matrix with distances to the 1st, 2nd, ..., 4th NN.
kNNdist(iris, k = 4, all = TRUE)

## Produce a k-NN distance plot to determine a suitable eps for
## DBSCAN with MinPts = 5. Use k = 4 (= MinPts -1).
## The knee is visible around a distance of .7
kNNdistplot(iris, k = 4)

## Look at k-NN distance plots for different k values
## Note that k-NN distances are increasing in k, so the
## lowest line is for the lowest k value.
kNNdistplot(iris, k = c(1, 5, 10, 20))

cl <- dbscan(iris, eps = .7, minPts = 5)
pairs(iris, col = cl$cluster + 1L)
## Note: black points are noise points

Local Outlier Factor Score

Description

Calculate the Local Outlier Factor (LOF) score for each data point using a k-d tree to speed up kNN search.

Usage

lof(x, minPts = 5, ...)

Arguments

x

a data matrix or a dist object.

minPts

number of nearest neighbors used in defining the local neighborhood of a point (includes the point itself).

...

further arguments are passed on to kNN(). Note: sort cannot be specified here since lof() uses always sort = TRUE.

Details

LOF compares the local reachability density (lrd) of a point to the lrd of its neighbors. A LOF score of approximately 1 indicates that the lrd around the point is comparable to the lrd of its neighbors and that the point is not an outlier. Points that have a substantially lower lrd than their neighbors are considered outliers and produce scores significantly larger than 1.

If a data matrix is specified, then Euclidean distances and fast nearest neighbor search using a k-d tree is used.

Note on duplicate points: If there are more than minPts duplicates of a point in the data, then LOF the local readability distance will be 0 resulting in an undefined LOF score of 0/0. We set LOF in this case to 1 since there is already enough density from the points in the same location to make them not outliers. The original paper by Breunig et al (2000) assumes that the points are real duplicates and suggests to remove the duplicates before computing LOF. If duplicate points are removed first, then this LOF implementation in dbscan behaves like the one described by Breunig et al.

Value

A numeric vector of length nrow(x) containing LOF values for all data points.

Author(s)

Michael Hahsler

References

Breunig, M., Kriegel, H., Ng, R., and Sander, J. (2000). LOF: identifying density-based local outliers. In ACM Int. Conf. on Management of Data, pages 93-104. doi:10.1145/335191.335388

See Also

Other Outlier Detection Functions: glosh(), kNNdist(), pointdensity()

Examples

set.seed(665544)
n <- 100
x <- cbind(
  x=runif(10, 0, 5) + rnorm(n, sd = 0.4),
  y=runif(10, 0, 5) + rnorm(n, sd = 0.4)
  )

### calculate LOF score with a neighborhood of 3 points
lof <- lof(x, minPts = 3)

### distribution of outlier factors
summary(lof)
hist(lof, breaks = 10, main = "LOF (minPts = 3)")

### plot sorted lof. Looks like outliers start around a LOF of 2.
plot(sort(lof), type = "l",  main = "LOF (minPts = 3)",
  xlab = "Points sorted by LOF", ylab = "LOF")

### point size is proportional to LOF and mark points with a LOF > 2
plot(x, pch = ".", main = "LOF (minPts = 3)", asp = 1)
points(x, cex = (lof - 1) * 2, pch = 1, col = "red")
text(x[lof > 2,], labels = round(lof, 1)[lof > 2], pos = 3)

Moons Data

Description

Contains 100 2-d points, half of which are contained in two moons or "blobs"" (25 points each blob), and the other half in asymmetric facing crescent shapes. The three shapes are all linearly separable.

Format

A data frame with 100 observations on the following 2 variables.

X

a numeric vector

Y

a numeric vector

Details

This data was generated with the following Python commands using the SciKit-Learn library:

import sklearn.datasets as data

moons = data.make_moons(n_samples=50, noise=0.05)
blobs = data.make_blobs(n_samples=50,
                        centers=[(-0.75,2.25), (1.0, 2.0)],
                        cluster_std=0.25)
test_data = np.vstack([moons, blobs])

Source

See the HDBSCAN notebook from github documentation: https://hdbscan.readthedocs.io/en/latest/how_hdbscan_works.html

References

Pedregosa, Fabian, Gael Varoquaux, Alexandre Gramfort, Vincent Michel, Bertrand Thirion, Olivier Grisel, Mathieu Blondel et al. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research 12, no. Oct (2011): 2825-2830.

Examples

data(moons)
plot(moons, pch=20)

Minimum Spanning Tree Hierarchies

Description

Computes the minimum spanning tree (MST) of a graph with Prim's algorithm and returns it as a single-linkage hierarchy (hclust object).

Usage

mst_dist(x)

mst_mrdist(x, minPts, coredist = NULL)

Arguments

x

for mst_dist() a dist object with finite distances for at least two objects. For mst_mrdist() a data matrix (or an object that can be converted to a numeric matrix) with finite values.

minPts

integer; minimum number of points used to calculate the core distances (see coredist()). It can be omitted if coredist is specified. If given, it is stored in the result.

coredist

optional vector with the core distance of each point. If NULL, then it is calculated with coredist() (and minPts is required).

Details

MSTs are not unique if there are ties in the distances. Many ties are very likely for mutual reachability distances constructed as mrd(a, b) = max(coredist(a), coredist(b), dist(a, b)). Ties in this implementation are broken in order of the rows in the input data which is consistent with many other implementations.

extractFOSC() can be used to extract stable clusters from an MST.

Value

an hclust object representing the single-linkage hierarchy of the MST. Note: the rows of the merge matrix keep the order in which the MST was built and are not normalized to the convention documented in hclust (singletons before clusters, singletons in increasing index order, clusters in increasing step order). The raw order is kept so that cluster ids stay consistent with hdbscan(). Code that relies on this convention (e.g., other packages reading ⁠$merge⁠ directly) may fail or give unexpected results. The method component is "robust single". dist.method is taken from the "method" attribute of x for mst_dist() (it is omitted if x has none) and is "mutual reachability (euclidean)" for mst_mrdist(). mst_mrdist() also stores minPts in the result (if specified).

See Also

Other HDBSCAN functions: extractFOSC(), glosh(), hdbscan()

Examples

data("moons")

## MST of a mutual reachability distance matrix
d <- mrdist(moons, minPts = 5)
hc_mr <- mst_dist(d)
hc_mr
plot(hc_mr)

## MST of the mutual reachability graph without creating the distance matrix.
hc_mr2 <- mst_mrdist(moons, minPts = 5)

## same as
all.equal(hc_mr$merge, hc_mr2$merge)

Number of Clusters, Noise Points, and Observations

Description

Extract the number of clusters or the number of noise points for a clustering. This function works with any clustering result that contains a list element named cluster with a clustering vector. In addition, nobs (see stats::nobs()) is also available to retrieve the number of clustered points.

Usage

ncluster(object, ...)

nnoise(object, ...)

Arguments

object

a clustering result object containing a cluster element.

...

additional arguments are unused.

Value

returns the number if clusters or noise points.

See Also

Other clustering functions: dbscan(), extractFOSC(), hdbscan(), jpclust(), optics(), sNNclust()

Examples

data(iris)
iris <- as.matrix(iris[, 1:4])

res <- dbscan(iris, eps = .7, minPts = 5)
res

ncluster(res)
nnoise(res)
nobs(res)

# the functions also work with kmeans and other clustering algorithms.
cl <- kmeans(iris, centers = 3)
ncluster(cl)
nnoise(cl)
nobs(res)

Ordering Points to Identify the Clustering Structure (OPTICS)

Description

Implementation of the OPTICS (Ordering points to identify the clustering structure) point ordering algorithm using a k-d tree.

Usage

optics(x, eps = Inf, minPts = 5, ...)

## S3 method for class 'optics'
print(x, ...)

## S3 method for class 'optics'
plot(x, col = NULL, ...)

## S3 method for class 'optics'
as.reachability(object, ...)

## S3 method for class 'optics'
as.dendrogram(object, ...)

extractDBSCAN(object, eps_cl)

extractXi(object, xi, minimum = FALSE, correctPredecessors = TRUE)

## S3 method for class 'optics'
predict(object, newdata, data, ...)

Arguments

x

a data matrix or a dist object.

eps

maximum epsilon neighborhood size only used for performance. The default Inf does not restrict the neighborhood and gives the complete reachability structure. NULL is treated as Inf. See details.

minPts

the parameter is used to identify dense neighborhoods. The core distance of a point is the distance to its (minPts - 1)-th nearest neighbor (minPts includes the point itself). It is used to calculate the reachability distances and controls the smoothness of the reachability plot. Default is 5 points.

...

additional arguments are passed on to fixed-radius nearest neighbor search algorithm. See frNN() for details on how to control the search strategy. For plot(), they are passed on to plot.reachability() (e.g., hide_first and type).

col

colors used to plot the reachability distances in the order of the points in the ordering. The default NULL colors the points by cluster (noise is shown in black).

object

clustering object.

eps_cl

Threshold to identify clusters (eps_cl <= eps).

xi

Steepness threshold between 0 and 1 (exclusive) to identify clusters hierarchically using the Xi method.

minimum

logical, representing whether or not to extract the minimal (non-overlapping) clusters in the Xi clustering algorithm.

correctPredecessors

logical, correct a common artifact by pruning the steep up area for points that have predecessors not in the cluster–found by the ELKI framework, see details for extractXi().

newdata

new data points for which the cluster membership should be predicted.

data

the data set used to create the clustering object.

Details

The Algorithm

This implementation of OPTICS implements the original algorithm as described by Ankerst et al (1999). OPTICS is an ordering algorithm with methods to extract a clustering from the ordering. While using similar concepts as DBSCAN, minPts in OPTICS has a different effect than in DBSCAN. Since it is also used to calculate the reachability distance, larger values will make the reachability distance plot smoother. The parameter eps is optional. It represents an upper limit for the neighborhood size that can be used to reduce computational complexity for large data sets. The default eps = Inf does not limit the neighborhood size and gives the complete reachability structure.

OPTICS linearly orders the data points such that points which are spatially closest become neighbors in the ordering. The closest analog to this ordering is dendrogram in single-link hierarchical clustering. The algorithm also calculates the reachability distance for each point. plot() (see reachability_plot) produces a reachability plot which shows each points reachability distance between two consecutive points where the points are sorted by OPTICS. Valleys represent clusters (the deeper the valley, the more dense the cluster) and high points indicate points between clusters.

Specifying the Data

If x is specified as a data matrix, then Euclidean distances and fast nearest neighbor lookup using a k-d tree are used. See kNN() for details on the parameters for the k-d tree.

The effect of eps

The default eps = Inf (NULL is also treated as Inf) does not restrict the neighborhood and results in the complete reachability structure (only the first reachability distance is undefined). This is the original OPTICS behavior. Computation in this implementation uses Prim's algorithm on the reachability graph using core distances and distances that are calculated on the fly. This needs only O(n) additional memory, but the running time is quadratic in the number of data points, so it can still be slow for large data sets.

A finite eps restricts the maximum epsilon neighborhood size, which can improve performance significantly for large data sets. If eps is too small, then points can have undefined core distances (they are noise) and reachability distances. Undefined reachability distances are shown as dotted lines in the reachability plot, and the ordering can differ from the one for eps = Inf. optics() gives a warning if a finite eps results in undefined reachability distances in addition to the first one. If the plot shows too many dotted lines then eps should be increased.

Ties

OPTICS repeatedly processes the unprocessed point with the smallest reachability distance. If several points have the same reachability distance, ties are broken by the position of the point in the data: the point with the lower id (row number) is processed first. This follows the ELKI implementation. With ties, the returned order (and therefore the reachability plot and extracted clusters) can depend on the row order of the data. Ties are common for data with repeated values or for data on a regular grid.

Extracting a Clustering

Several methods to extract a clustering from the order returned by OPTICS are implemented:

Predict Cluster Memberships

predict() requires an extracted DBSCAN clustering with extractDBSCAN() and then uses predict for dbscan().

Value

An object of class optics with components:

eps

value of eps parameter.

minPts

value of minPts parameter.

order

optics order for the data points in x.

reachdist

reachability distance for each data point in x.

coredist

core distance for each data point in x.

For extractDBSCAN(), in addition the following components are available:

eps_cl

the value of the eps_cl parameter.

cluster

assigned cluster labels in the order of the data points in x.

For extractXi(), in addition the following components are available:

xi

Steepness threshold xi.

cluster

assigned cluster labels in the order of the data points in x.

clusters_xi

data.frame containing the start and end of each cluster found in the OPTICS ordering.

Author(s)

Michael Hahsler and Matthew Piekenbrock

References

Mihael Ankerst, Markus M. Breunig, Hans-Peter Kriegel, Joerg Sander (1999). OPTICS: Ordering Points To Identify the Clustering Structure. ACM SIGMOD international conference on Management of data. ACM Press. pp. 49-60. doi:10.1145/304181.304187

Hahsler M, Piekenbrock M, Doran D (2019). dbscan: Fast Density-Based Clustering with R. Journal of Statistical Software, 91(1), 1-30. doi:10.18637/jss.v091.i01

Erich Schubert, Michael Gertz (2018). Improving the Cluster Structure Extracted from OPTICS Plots. In Lernen, Wissen, Daten, Analysen (LWDA 2018), pp. 318-329.

See Also

reachability, dbscan(), hdbscan().

Other clustering functions: dbscan(), extractFOSC(), hdbscan(), jpclust(), ncluster(), sNNclust()

Examples

set.seed(2)
n <- 400

x <- cbind(
  x = runif(4, 0, 1) + rnorm(n, sd = 0.1),
  y = runif(4, 0, 1) + rnorm(n, sd = 0.1)
  )

plot(x, col=rep(1:4, times = 100), asp = 1)

### run OPTICS (Note: we use the default eps = Inf)
res <- optics(x, minPts = 10)
res

### get order
res$order

### plot produces a reachability plot
plot(res)

### plot the order of points in the reachability plot
plot(x, col = "grey", pch = 19, asp = 1)
polygon(x[res$order, ])

### extract a DBSCAN clustering by cutting the reachability plot at eps_cl
res <- extractDBSCAN(res, eps_cl = .065)
res

plot(res)  ## black is noise
hullplot(x, res, asp = 1)

### re-cut at a higher eps threshold
res <- extractDBSCAN(res, eps_cl = .07)
res
plot(res)
hullplot(x, res, asp = 1)

### extract hierarchical clustering of varying density using the Xi method
res <- extractXi(res, xi = 0.01)
res

plot(res)
hullplot(x, res, asp = 1)

# Xi cluster structure
res$clusters_xi

### use OPTICS on a precomputed distance matrix
d <- dist(x)
res <- optics(d, minPts = 10)
plot(res)

Calculate Local Density at Each Data Point

Description

Calculate the local density at each data point as either the number of points in the eps-neighborhood (as used in dbscan()) or perform kernel density estimation (KDE) using a uniform kernel. The function uses a k-d tree for fast fixed-radius nearest neighbor search.

Usage

pointdensity(
  x,
  eps,
  type = "frequency",
  search = "kdtree",
  bucketSize = 10,
  splitRule = "suggest",
  shrinkRule = "suggest",
  approx = 0
)

Arguments

x

a data matrix or a dist object.

eps

radius of the eps-neighborhood, i.e., bandwidth of the uniform kernel). For the Gaussian kde, this parameter specifies the standard deviation of the kernel.

type

"frequency", "density", or "gaussian". should the raw count of points inside the eps-neighborhood, the eps-neighborhood density estimate, or a Gaussian density estimate be returned?

search, bucketSize, splitRule, shrinkRule, approx

algorithmic parameters for frNN().

Details

dbscan() estimates the density around a point as the number of points in the eps-neighborhood of the point (including the query point itself). Kernel density estimation (KDE) using a uniform kernel, which is just this point count in the eps-neighborhood divided by (2\,eps\,n), where n is the number of points in x.

Alternatively, type = "gaussian" calculates a Gaussian kernel estimate where eps is used as the standard deviation. To speed up computation, a k-d tree is used to find all points within 3 times the standard deviation and these points are used for the estimate.

Points with low local density often indicate noise (see e.g., Wishart (1969) and Hartigan (1975)).

Value

A vector of the same length as data points (rows) in x with the count or density values for each data point.

Author(s)

Michael Hahsler

References

Wishart, D. (1969), Mode Analysis: A Generalization of Nearest Neighbor which Reduces Chaining Effects, in Numerical Taxonomy, Ed., A.J. Cole, Academic Press, 282-311.

John A. Hartigan (1975), Clustering Algorithms, John Wiley & Sons, Inc., New York, NY, USA.

See Also

frNN(), stats::density().

Other Outlier Detection Functions: glosh(), kNNdist(), lof()

Examples

set.seed(665544)
n <- 100
x <- cbind(
  x=runif(10, 0, 5) + rnorm(n, sd = 0.4),
  y=runif(10, 0, 5) + rnorm(n, sd = 0.4)
  )
plot(x)

### calculate density around points
d <- pointdensity(x, eps = .5, type = "density")

### density distribution
summary(d)
hist(d, breaks = 10)

### plot with point size is proportional to Density
plot(x, pch = 19, main = "Density (eps = .5)", cex = d*5)

### Wishart (1969) single link clustering after removing low-density noise
# 1. remove noise with low density
f <- pointdensity(x, eps = .5, type = "frequency")
x_nonoise <- x[f >= 5,]

# 2. use single-linkage on the non-noise points
hc <- hclust(dist(x_nonoise), method = "single")
plot(x, pch = 19, cex = .5)
points(x_nonoise, pch = 19, col= cutree(hc, k = 4) + 1L)

Reachability Distances

Description

Reachability distances can be plotted to show the hierarchical relationships between data points. The idea was originally introduced by Ankerst et al. (1999) to visualize the order generated by OPTICS. Later, Sander et al. (2003) showed that the visualization is useful for other hierarchical structures and introduced an algorithm to convert dendrogram representation to reachability plots. We implement dendrogram conversion and reachability plots.

Usage

## S3 method for class 'reachability'
print(x, ...)

## S3 method for class 'reachability'
plot(
  x,
  order_labels = FALSE,
  xlab = "Order",
  ylab = "Reachability dist.",
  main = "Reachability Plot",
  hide_first = FALSE,
  type = "h",
  ...
)

as.reachability(object, ...)

## S3 method for class 'dendrogram'
as.reachability(object, ...)

Arguments

x

object of class reachability.

...

for plot() graphical parameters are passed on to graphics::plot.default(). or arguments for other methods.

order_labels

whether to plot text labels for each points reachability distance.

xlab

x-axis label.

ylab

y-axis label.

main

Title of the plot.

hide_first

logical; do not draw the first reachability distance. It is undefined (Inf) for the first point in the ordering and is otherwise drawn at the top of the plot.

type

plot type passed on to plot(). The default "h" draws vertical bars.

object

any object that can be coerced to class reachability, such as an object of class optics or stats::dendrogram.

Details

Reachability Plots

A reachability plot displays the points as vertical bars, were the height is the reachability distance between two consecutive points. Reachability distances are undefined (stored as Inf) for the first point in the ordering, since it has no preceding point, and for points that do not have enough neighbors in the epsilon neighborhood. Undefined distances are shown in the plot as dotted vertical lines. A dotted line at the first position is therefore always present unless hide_first = TRUE. If many additional dotted lines show up for OPTICS then you need to increase eps there.

The central idea behind reachability plots is that the ordering in which points are plotted identifies underlying hierarchical density representation as mountains and valleys of high and low reachability distance.

Different hierarchical representations, such as dendrograms or reachability plots, may be preferable depending on the context. In smaller datasets, cluster memberships may be more easily identifiable through a dendrogram representation, particularly is the user is already familiar with tree-like representations. For larger datasets however, a reachability plot may be preferred for visualizing macro-level density relationships.

Reachability Plots for OPTICS

The original ordering algorithm OPTICS as described by Ankerst et al. (1999) introduced the notion of reachability plots. OPTICS linearly orders the data points such that points which are spatially closest become neighbors in the ordering. Valleys represent clusters, which can be represented hierarchically. Although the ordering is crucial to the structure of the reachability plot, it depends on the order of the data points and on how ties are broken. Just like the dendrogram, isomorphisms may exist. Reachability plots were shown to essentially convey the same information as the more traditional dendrogram structure by Sander et al. (2003).

A variety of cluster extraction methods have been proposed using reachability plots. Because both cluster extraction depend directly on the ordering OPTICS produces, they are part of the optics() interface. Nonetheless, reachability plots can be created directly from other types of linkage trees, and vice versa.

Value

An object of class reachability with components:

order

order to use for the data points in x.

reachdist

reachability distance for each data point in x.

Author(s)

Matthew Piekenbrock

References

Ankerst, M., M. M. Breunig, H.-P. Kriegel, J. Sander (1999). OPTICS: Ordering Points To Identify the Clustering Structure. ACM SIGMOD international conference on Management of data. ACM Press. pp. 49–60.

Sander, J., X. Qin, Z. Lu, N. Niu, and A. Kovarsky (2003). Automatic extraction of clusters from hierarchical clustering representations. Pacific-Asia Conference on Knowledge Discovery and Data Mining. Springer Berlin Heidelberg.

See Also

optics(), as.dendrogram(), and stats::hclust().

Examples

set.seed(2)
n <- 20

x <- cbind(
  x = runif(4, 0, 1) + rnorm(n, sd = 0.1),
  y = runif(4, 0, 1) + rnorm(n, sd = 0.1)
)

plot(x, xlim = range(x), ylim = c(min(x) - sd(x), max(x) + sd(x)), pch = 20)
text(x = x, labels = seq_len(nrow(x)), pos = 3)

### run OPTICS
res <- optics(x, eps = 10,  minPts = 2)
res

### plot produces a reachability plot.
plot(res)

### Manually extract reachability components from OPTICS
reach <- as.reachability(res)
reach

### plot also produces a reachability plot; point IDs
### (rows in the original data) can be displayed with order_labels = TRUE
### the plotting parameter type can be used to change the plot style.
plot(reach, order_labels = TRUE, type = "l")

### Reachability objects can be directly converted to dendrograms
dend <- as.dendrogram(reach)
dend
plot(dend)

### A dendrogram can be converted back into a reachability object
plot(as.reachability(dend))

Find Shared Nearest Neighbors

Description

Calculates the number of shared nearest neighbors and creates a shared nearest neighbors graph.

Usage

sNN(
  x,
  k,
  kt = NULL,
  jp = FALSE,
  sort = TRUE,
  search = "kdtree",
  bucketSize = 10,
  splitRule = "suggest",
  shrinkRule = "suggest",
  approx = 0
)

## S3 method for class 'sNN'
sort(x, decreasing = TRUE, ...)

## S3 method for class 'sNN'
print(x, ...)

Arguments

x

a data matrix, a dist object or a kNN object.

k

number of neighbors to consider to calculate the shared nearest neighbors.

kt

minimum threshold on the number of shared nearest neighbors to build the shared nearest neighbor graph. Edges are only preserved if kt or more neighbors are shared.

jp

In regular sNN graphs, a point and one of its neighbors can have shared neighbors even if the point is not one of the neighbor's k nearest neighbors. Jarvis and Patrick (1973) require the neighbor relation to be mutual: the point also needs to be among the neighbor's k nearest neighbors, otherwise the count is zeroed out. TRUE uses this behavior.

sort

sort the neighbors of each point by the number of shared nearest neighbors (decreasing, ties are broken by id)? Note that this is expensive and sort = FALSE is much faster. sNN objects can be sorted later using sort().

search

nearest neighbor search strategy (one of "kdtree", "linear", "dist" or "bdtree"). See the section on the search parameters.

bucketSize

max size of the k-d or bd tree leafs.

splitRule

rule to split the k-d or bd tree. One of "std", "midpt", "fair", "sl_midpt", "sl_fair" or "suggest" (SL stands for sliding). The default value "suggest" uses ANNs best guess.

shrinkRule

shrinking rule used to build the box-decomposition tree (only used for search = "bdtree"). One of "none" (no shrinking, equivalent to a k-d tree), "simple", "centroid" or "suggest". The default value "suggest" uses ANNs best guess.

approx

approximation factor for the tree-based searches. The j-th neighbor found is at most (1 + approx) times as far away as the true j-th nearest neighbor. 0 (default) gives exact results; larger values are faster, but some true nearest neighbors may be omitted. Ignored by search = "linear" and "dist".

decreasing

for sort(), sort by decreasing number of shared neighbors (the default)? Use FALSE for increasing order.

...

further arguments (ignored).

Details

The number of shared nearest neighbors of two points p and q is the size of the intersection of the kNN neighborhoods of the two points. Note that each point is considered to be part of its own kNN neighborhood. The range for the shared nearest neighbors is [0, k]. The result is a n-by-k matrix called shared. Each row is a point and the columns are the point's k nearest neighbors. The value shared[i, j] is the count of the shared neighbors of point i and its j-th neighbor.

The shared nearest neighbor graph connects a point with all its nearest neighbors if they have at least one shared neighbor. The number of shared neighbors can be used as an edge weight. Jarvis and Patrick (1973) use a slightly modified (see parameter jp) shared nearest neighbor graph for clustering.

The k nearest neighbors are found with kNN(). The search parameters are passed on to it (see the section on the search parameters below).

Using a kNN object as x

If x is a kNN object, then k can be omitted and x$k is used. If k is smaller than x$k, then the first k neighbors (by distance) are used. An error is raised if x contains fewer than k neighbors. The search parameters are ignored. A query is not supported.

Thresholding and sorting

Details on the search parameters:

Handling of NAs:

The tree-based searches and search = "linear" cannot handle NA, NaN or infinite values in the data (in x or query); an error is raised. (The ANN library does not check its input and would silently return wrong results.) With search = "dist", the distances are calculated by dist(), which leaves out coordinates that are NA for a pair of points and scales up the remaining sum. These distances are not exactly Euclidean distances. The resulting distance matrix (and a dist object supplied as x) cannot contain NAs, which happens, for example, if a point has only NA values. Otherwise, remove or impute missing values before performing the search.

Value

An object of class sNN (subclass of kNN and NN) containing a list with the following components (the matrices have one row per point and k columns; edges removed by kt are NA):

id

a matrix with the ids (row numbers in x) of the neighbors.

dist

a matrix with the distances to the neighbors.

shared

a matrix with the number of shared nearest neighbors.

k

the number k used.

sort

logical; are the neighbors sorted by increasing distance? This is FALSE if sort = TRUE was used, since the neighbors are then sorted by the number of shared neighbors.

sort_shared

logical; are the neighbors sorted by decreasing number of shared neighbors?

kt

the threshold kt used (NULL if none).

metric

the used distance metric.

Author(s)

Michael Hahsler

References

R. A. Jarvis and E. A. Patrick. 1973. Clustering Using a Similarity Measure Based on Shared Near Neighbors. IEEE Trans. Comput. 22, 11 (November 1973), 1025-1034. doi:10.1109/T-C.1973.223640

David M. Mount and Sunil Arya (2010). ANN: A Library for Approximate Nearest Neighbor Searching, http://www.cs.umd.edu/~mount/ANN/.

See Also

sNNclust() and jpclust(), which cluster using the shared nearest neighbor graph.

Other NN functions: NN, comps(), frNN(), kNN(), kNNdist()

Examples

data(iris)
x <- iris[, -5]

# finding kNN and add the number of shared nearest neighbors.
k <- 5
nn <- sNN(x, k = k)
nn

# shared nearest neighbor distribution
table(as.vector(nn$shared))

# explore number of shared points for the k-neighborhood of point 10
i <- 10
nn$shared[i,]

plot(nn, x)

# apply a threshold to create a sNN graph with edges
# if more than 3 neighbors are shared.
nn_3 <- sNN(nn, kt = 3)
plot(nn_3, x)

# get an adjacency list for the shared nearest neighbor graph
adjacencylist(nn_3)

# Jarvis-Patrick graph (requires mutual nearest neighbors)
nn_jp <- sNN(x, k = k, jp = TRUE)
table(as.vector(nn_jp$shared))

Shared Nearest Neighbor Clustering

Description

Implements the shared nearest neighbor clustering algorithm by Ertoz, Steinbach and Kumar (2003).

Usage

sNNclust(x, k, eps, minPts, borderPoints = TRUE, ...)

Arguments

x

a data matrix/data.frame (Euclidean distance is used), a precomputed dist object or a kNN object created with kNN().

k

Neighborhood size for nearest neighbor sparsification to create the shared NN graph.

eps

Two objects are only reachable from each other if they share at least eps nearest neighbors. Note: this is different from the eps in DBSCAN!

minPts

minimum number of points that share at least eps nearest neighbors for a point to be considered a core points.

borderPoints

should border points be assigned to clusters like in DBSCAN?

...

additional arguments are passed on to the k nearest neighbor search algorithm. See kNN() for details on how to control the search strategy.

Details

Algorithm:

  1. Constructs a shared nearest neighbor graph for a given k. The edge weights are the number of shared k nearest neighbors (in the range of [0, k]).

  2. Find each points SNN density, i.e., the number of points which have a similarity of eps or greater.

  3. Find the core points, i.e., all points that have an SNN density greater than MinPts.

  4. Form clusters from the core points and assign border points (i.e., non-core points which share at least eps neighbors with a core point).

Note that steps 2-4 are equivalent to the DBSCAN algorithm (see dbscan()) and that eps has a different meaning than for DBSCAN. Here it is a threshold on the number of shared neighbors (see sNN()) which defines a similarity.

Value

A object of class general_clustering with the following components:

cluster

A integer vector with cluster assignments. Zero indicates noise points.

type

name of used clustering algorithm.

param

list of used clustering parameters.

Author(s)

Michael Hahsler

References

Levent Ertoz, Michael Steinbach, Vipin Kumar, Finding Clusters of Different Sizes, Shapes, and Densities in Noisy, High Dimensional Data, SIAM International Conference on Data Mining, 2003, 47-59. doi:10.1137/1.9781611972733.5

See Also

Other clustering functions: dbscan(), extractFOSC(), hdbscan(), jpclust(), ncluster(), optics()

Examples

data("DS3")

# Out of k = 20 NN 7 (eps) have to be shared to create a link in the sNN graph.
# A point needs a least 16 (minPts) links in the sNN graph to be a core point.
# Noise points have cluster id 0 and are shown in black.
cl <- sNNclust(DS3, k = 20, eps = 7, minPts = 16)
cl

clplot(DS3, cl)