| 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 |
| 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
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
Clustering:
dbscan(),hdbscan(),optics(),jpclust(),sNNclust()Outliers:
lof(),glosh(),pointdensity()
Author(s)
Maintainer: Michael Hahsler mhahsler@lyle.smu.edu (ORCID) [copyright holder]
Authors:
Michael Hahsler mhahsler@lyle.smu.edu (ORCID) [copyright holder]
Matthew Piekenbrock [copyright holder]
Other contributors:
Sunil Arya [contributor, copyright holder]
David Mount [contributor, copyright holder]
Claudia Malzer [contributor]
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:
Report bugs at https://github.com/mhahsler/dbscan/issues
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 |
... |
further parameters are passed on to |
decreasing |
sort in decreasing order? |
data |
that was used to create |
main |
title |
pch |
plotting character. |
col |
color used for the data points (nodes). Use |
linecol |
color used for edges. |
xlab, ylab |
axis labels. The default is to use the column names of
|
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
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 |
|
... |
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 |
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
|
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 |
borderPoints |
logical; should border points be assigned to clusters.
The default is |
... |
additional arguments are passed on to the fixed-radius nearest
neighbor search algorithm. See |
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:
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).
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).
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.
-
minPts:The original DBSCAN paper (Ester et al, 1996) suggests to start by setting\text{minPts} \ge d + 1, the data dimensionality plus one or higher with a minimum of 3. Larger values are preferable since increasing the parameter suppresses more noise in the data by requiring more points to form clusters. Sander et al (1998) uses in the examples two times the data dimensionality. Note that setting\text{minPts} \le 2is equivalent to hierarchical clustering with the single link metric and the dendrogram cut at heighteps. -
eps:A suitable neighborhood size parameterepsgiven a fixed value forminPtscan be found visually by inspecting thekNNdistplot()of the data usingk = \text{minPts} - 1(minPtsincludes the point itself, while the k-nearest neighbors distance does not). The k-nearest neighbor distance plot sorts all data points by their k-nearest neighbor distance. A sudden increase of the kNN distance (a knee) indicates that the points to the right are most likely outliers. Chooseepsfor DBSCAN where the knee is.
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 |
minPts |
value of the |
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 |
... |
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:
-
cluster: the cluster label as a factor (the levels are0to the number of clusters). -
size: the number of points in the cluster. -
noise:TRUEfor cluster 0 (the noise points). -
cluster_score(only forhdbscan()): the stability score of the cluster (see the componentcluster_scoresinhdbscan()). It isNAfor the noise cluster.
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:
-
.cluster: the cluster label as a factor. -
noise(only fordbscan()):TRUEif the point is a noise point. -
.coredist,.membership_proband.outlier_scores(only forhdbscan()): the core distance, the cluster membership probability and the GLOSH outlier score of each point (seehdbscan()). They areNAfor points innewdata.
Augmenting newdata is not supported for jpclust() and sNNclust().
glance()
Returns a one-row summary of the clustering with the columns:
-
nobs: the number of points. -
n.clusters: the number of clusters (without noise). -
nexcluded: the number of noise points.
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 |
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 |
minPts |
integer; minimum cluster size to extract (must be at least 2).
The default
value of |
prune_unstable |
logical; should significantly unstable subtrees be
pruned? The default is |
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
|
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
|
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 |
sort |
sort the neighbors of each point by distance (ties are broken by
id)? This is expensive and can be done later using |
search |
nearest neighbor search strategy (one of |
bucketSize |
max size of the k-d or bd tree leafs. |
splitRule |
rule to split the k-d or bd tree. One of |
shrinkRule |
shrinking rule used to build the box-decomposition tree
(only used for |
approx |
a non-negative number used for approximate nearest neighbors.
All NN up to a distance of |
decreasing |
for |
... |
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
-
Sorting: With
sort = TRUE(default), the neighbors of each point are ordered by increasing distance and ties are broken by id. Withsort = FALSE, the neighbors are returned in no particular order, which avoids the cost of sorting. AfrNNobject can be sorted later usingsort(). -
Self-matches: If no
queryis specified, then self-matches are removed. Ifqueryis specified, then a query point that is also inxis returned as its own neighbor (at distance 0).
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
-
xcan be a numeric matrix, a data.frame with only numeric columns, a dist object or afrNNobject. -
queryneeds to be a numeric matrix or data.frame with the same number of columns asx, and can only be used ifxis a data matrix.
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:
-
searchcontrols what method is used ifxis a data matrix. Available methods are:-
"kdtree"uses a Euclidean k-d tree to speed up NN search. This is the default with good overall performance. -
"bdtree"uses a box-decomposition tree. Its spatial boxes can, in addition to splitting, also shrink. According to the ANN authors, this tree type may be faster than a k-d tree on tightly clustered data. -
"linear"performs linear search directly on the data. -
"dist"precomputes Euclidean distances first usingdist(). While fast for small data sets, the memory requirements for the distance matrix grow withO(n^2).
The trees and linear search use the highly optimized ANN library (Mount and Arya, 2010) for Euclidean distances.
If
xis a distance matrix, thensearchis ignored and"dist"is used. -
Tree specific parameters
-
bucketSize,splitRuleandshrinkRulecontrol how the tree is built.bucketSizeandsplitRuleapply to k-d and bd trees;shrinkRuleapplies only to bd trees ("none"gives a tree that behaves like a k-d tree). -
approxuses the approximate fixed-radius search implemented in ANN. All neighbors up to a distance ofeps / (1 + approx)are considered and none with a distance greater thaneps. The points in between might be considered, so some actual neighbors may be omitted. This can lead to a significant speedup. The defaultapprox = 0gives exact results.approxis only used by the tree-based searches. For more details see Mount and Arya (2010).
-
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 |
dist |
a list with the distances (same structure as
|
eps |
neighborhood radius |
sort |
logical; are the neighbors of each point sorted by increasing distance (with ties broken by id)? |
metric |
used distance metric. This is |
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 |
|
k |
size of the neighborhood. |
... |
further arguments are passed on to |
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 |
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 |
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 |
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 |
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:
Compute mutual reachability distances from core distances. For core distances,
minPtsis a smoothing parameter for the density estimates; larger values forminPtsgive larger and smoother density estimates.Construct a minimum spanning tree from the mutual reachability distances.
Prune the tree using stability. Here
minPtscontrols the minimum cluster size because splits are only allowed when both branches have at leastminPtspoints.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:
-
coredist(): The core distance is defined for each point as the distance to the (minPts - 1)-th nearest neighbor. It produces a density estimate where larger values forminPtslead to larger and smoother estimates. The core distance is For matrix data, a fast k-d tree based on Euclidean distance is used. Additional parameters tocoredist()are passed on tokNNdist(). A core distance vector is returned. -
mrdist(): The mutual reachability distance is defined between two points asmrd(a, b) = max(coredist(a), coredist(b), dist(a, b)). It has the effect of increasing distances in low density areas, separating clusters better.
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
-
predict()assigns each new data point to the same cluster as the nearest point if it is not more than that points core distance away. Otherwise the new point is classified as a noise point (i.e., cluster ID 0).
Related Methods
-
extractFOSC()implements a more general framework for clusters selection from hierarchies (i.e., dendrograms) In addition to HDBSCAN's unsupervised cluster extraction, it also provides semisupervised methods with cluster constraints. -
glosh()implements the GLOSH outlier score.
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 |
cluster_scores |
The sum of the stability scores for each salient
(flat) cluster. Corresponds to cluster IDs given the in |
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 |
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 |
hdbscan_tree |
A dendrogram of the hierarchy. Only present if
|
simplified_tree |
A dendrogram of the simplified hierarchy.
Only present if |
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 |
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 |
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 |
... |
further parameters are passed on to |
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 |
k |
Neighborhood size for nearest neighbor sparsification. If |
kt |
threshold on the number of shared nearest neighbors (including the
points themselves) to form clusters. Range: |
... |
additional arguments are passed on to the k nearest neighbor
search algorithm. See |
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 |
sort |
sort the neighbors of each point by distance (ties are broken by
id)? |
search |
nearest neighbor search strategy (one of |
bucketSize |
max size of the k-d or bd tree leafs. |
splitRule |
rule to split the k-d or bd tree. One of |
shrinkRule |
shrinking rule used to build the box-decomposition tree
(only used for |
approx |
approximation factor for the tree-based searches. The j-th
neighbor found is at most |
decreasing |
for |
... |
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
-
Sorting: With
sort = TRUE(default), the neighbors of each point are ordered by distance and ties are broken by id. Withsort = FALSE, the neighbors are returned in the order found by the search (the tree-based searches return them by increasing distance, but tied neighbors are not ordered by id), which avoids the cost of sorting. AkNNobject can be sorted later usingsort(). -
Ties: If the kth and the (k+1)th nearest neighbor are tied, then the neighbor found first is returned and the other one is ignored.
-
Self-matches: If no
queryis specified, then self-matches are removed. Ifqueryis specified, then a query point that is also inxis returned as its own nearest neighbor (at distance 0).
Input requirements
-
xcan be a numeric matrix, a data.frame with only numeric columns, a dist object or akNNobject. -
queryneeds to be a numeric matrix or data.frame with the same number of columns asx, and can only be used ifxis a data matrix. -
kneeds to be a whole number with1 <= k < nrow(x).
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:
-
searchcontrols what method is used ifxis a data matrix. Available methods are:-
"kdtree"uses a Euclidean k-d tree to speed up NN search. This is the default with good overall performance. -
"bdtree"uses a box-decomposition tree. Its spatial boxes can, in addition to splitting, also shrink. According to the ANN authors, this tree type may be faster than a k-d tree on tightly clustered data. -
"linear"performs linear search directly on the data. -
"dist"precomputes Euclidean distances first usingdist(). While fast for small data sets, the memory requirements for the distance matrix grow withO(n^2).
The trees and linear search use the highly optimized ANN library (Mount and Arya, 2010) for Euclidean distances.
If
xis a distance matrix, thensearchis ignored and"dist"is used. -
Tree specific parameters
-
bucketSize,splitRuleandshrinkRulecontrol how the tree is built.bucketSizeandsplitRuleapply to k-d and bd trees;shrinkRuleapplies only to bd trees ("none"gives a tree that behaves like a k-d tree). -
approxuses the approximate nearest neighbor search implemented in ANN. Ifapprox > 0, the distance to the j-th returned neighbor is at most(1 + approx)times the distance to the true j-th nearest neighbor, so some true nearest neighbors may be omitted. This can lead to a significant speedup. The defaultapprox = 0gives exact results.approxis only used by the tree-based searches. For more details see Mount and Arya (2010).
-
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 |
id |
a matrix with the row numbers in |
k |
number |
sort |
logical; are the neighbors in each row sorted by increasing distance (with ties broken by id)? |
metric |
used distance metric. This is |
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
|
all |
should a matrix with the distances to all k nearest neighbors be returned? |
... |
for |
minPts |
to use a k-NN plot to determine a suitable |
type, xlab, ylab |
plot type and axis labels for |
kNNdist_param |
a named list of additional arguments (e.g., k-d tree
related parameters) passed on to |
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 |
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 |
minPts |
integer; minimum number of points used to calculate the core
distances (see |
coredist |
optional vector with the core distance of each point. If
|
Details
-
mst_dist()computes the MST of the complete graph defined by a dist object. -
mst_mrdist()computes the MST of the graph of mutual reachability distances (seemrdist()) directly from a data matrix andminPts. The core distances are calculated first (seecoredist()). The mutual reachability distances are computed on the fly, so no complete distance matrix is created. This saves memory (O(n d)instead ofO(n^2)) and is used byhdbscan()for data matrices. The result is the same asmst_dist(mrdist(x, minPts)). Only Euclidean distances are supported.
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 |
... |
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 |
minPts |
the parameter is used to identify dense neighborhoods. The
core distance of a point is the distance to its ( |
... |
additional arguments are passed on to fixed-radius nearest
neighbor search algorithm. See |
col |
colors used to plot the reachability distances in the order of
the points in the ordering. The default |
object |
clustering object. |
eps_cl |
Threshold to identify clusters ( |
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 |
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:
-
extractDBSCAN()extracts a clustering from an OPTICS ordering that is similar to what DBSCAN would produce with an eps set toeps_cl(see Ankerst et al, 1999). The only difference to a DBSCAN clustering is that OPTICS is not able to assign some border points and reports them instead as noise. -
extractXi()extract clusters hierarchically specified in Ankerst et al (1999) based on the steepness of the reachability plot. One interpretation of thexiparameter is that it classifies clusters by change in relative cluster density. The algorithm is a port of the implementation in the ELKI framework (version 0.8.0). It follows Ankerst et al (1999) with the improvements described in Schubert and Gertz (2018). WithcorrectPredecessors = TRUE(the default), the end of each cluster is shortened so that the predecessor of its last point is inside the cluster. This step is not part of the original algorithm and removes a common artifact (found by the ELKI framework). Clusters with fewer thanminPtspoints are not reported.
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 |
minPts |
value of |
order |
optics order for the data points in |
reachdist |
reachability distance for each data point in |
coredist |
core distance for each data point in |
For extractDBSCAN(), in addition the following
components are available:
eps_cl |
the value of the |
cluster |
assigned cluster labels in the order of the data points in |
For extractXi(), in addition the following components
are available:
xi |
Steepness threshold |
cluster |
assigned cluster labels in the order of the data points in |
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 |
|
search, bucketSize, splitRule, shrinkRule, approx |
algorithmic parameters for
|
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
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 |
... |
for |
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 ( |
type |
plot type passed on to |
object |
any object that can be coerced to class
|
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 |
reachdist |
reachability distance for each data point in |
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 |
|
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
|
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 |
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 |
search |
nearest neighbor search strategy (one of |
bucketSize |
max size of the k-d or bd tree leafs. |
splitRule |
rule to split the k-d or bd tree. One of |
shrinkRule |
shrinking rule used to build the box-decomposition tree
(only used for |
approx |
approximation factor for the tree-based searches. The j-th
neighbor found is at most |
decreasing |
for |
... |
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
-
Threshold
kt: Ifktis specified, then only edges with at leastktshared neighbors are kept (ktneeds to be at mostk). The entries for removed edges are set toNAinid,distandshared.adjacencylist()skips them. -
Sorting: The neighbors are found without sorting. With
sort = TRUE(default), the neighbors of each point (the columns ofid,distandshared) are then reordered by decreasing number of shared neighbors (ties are broken by id). The columns then no longer follow the distance rank, and$sortisFALSE. AsNNobject can be sorted later usingsort().
Details on the search parameters:
-
searchcontrols what method is used ifxis a data matrix. Available methods are:-
"kdtree"uses a Euclidean k-d tree to speed up NN search. This is the default with good overall performance. -
"bdtree"uses a box-decomposition tree. Its spatial boxes can, in addition to splitting, also shrink. According to the ANN authors, this tree type may be faster than a k-d tree on tightly clustered data. -
"linear"performs linear search directly on the data. -
"dist"precomputes Euclidean distances first usingdist(). While fast for small data sets, the memory requirements for the distance matrix grow withO(n^2).
The trees and linear search use the highly optimized ANN library (Mount and Arya, 2010) for Euclidean distances.
If
xis a distance matrix, thensearchis ignored and"dist"is used. -
Tree specific parameters
-
bucketSize,splitRuleandshrinkRulecontrol how the tree is built.bucketSizeandsplitRuleapply to k-d and bd trees;shrinkRuleapplies only to bd trees ("none"gives a tree that behaves like a k-d tree). -
approxuses the approximate nearest neighbor search implemented in ANN. Ifapprox > 0, the distance to the j-th returned neighbor is at most(1 + approx)times the distance to the true j-th nearest neighbor, so some true nearest neighbors may be omitted. This can lead to a significant speedup. The defaultapprox = 0gives exact results.approxis only used by the tree-based searches. For more details see Mount and Arya (2010).
-
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 |
dist |
a matrix with the distances to the neighbors. |
shared |
a matrix with the number of shared nearest neighbors. |
k |
the number |
sort |
logical; are the neighbors sorted by increasing distance? This
is |
sort_shared |
logical; are the neighbors sorted by decreasing number of shared neighbors? |
kt |
the threshold |
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 |
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 |
minPts |
minimum number of points that share at least |
borderPoints |
should border points be assigned to clusters like in DBSCAN? |
... |
additional arguments are passed on to the k nearest neighbor
search algorithm. See |
Details
Algorithm:
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]).Find each points SNN density, i.e., the number of points which have a similarity of
epsor greater.Find the core points, i.e., all points that have an SNN density greater than
MinPts.Form clusters from the core points and assign border points (i.e., non-core points which share at least
epsneighbors 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)