linkage

linkage(X, [method="single"], [metric="euclidean"], [optimalOrdering=false])

Calculates hierarchical clustering using an agglomerative algorithm. The function iteratively merges clusters according to the selected linkage method and returns a linkage matrix that records the merge history.

If X is a vector, it is treated as a condensed distance matrix and clustering is performed directly on the provided pairwise distances. If X is a matrix, each column is treated as an observation and each row as a feature; pairwise distances between columns are calculated according to metric before clustering. The implementation uses an optimized O(n²) algorithm, where n is the number of original observations.

The returned linkage matrix can be further used with fcluster to generate cluster labels.

DolphinDB linkage provides the similar core functionality as SciPy linkage, with the following differences:

X A numeric vector or matrix.

• If X is a vector, it specifies a condensed distance matrix, which is formed by arranging the upper triangular part of the original distance matrix (excluding the diagonal) in row-major order. The length must be n * (n - 1) / 2, where n is the number of original observations.

• If X is a matrix, it specifies observation data, where each column is an observation vector and each row is a feature. The matrix must contain at least two columns.

method (optional) A string scalar specifying the linkage method. The default value is "single". Supported values:

• "single": single linkage, nearest-point distance.

• "complete": complete linkage, farthest-point distance.

• "average": average linkage, UPGMA.

• "weighted": weighted average linkage, WPGMA.

• "centroid": centroid linkage, UPGMC.

• "median": median linkage, WPGMC.

• "ward": Ward's minimum variance linkage.

metric (optional) A string scalar. It takes effect only when X is a matrix and specifies the distance metric between observations. Supported values:

• "euclidean": the default value, indicating Euclidean distance. If method is “centroid”, “median”, or “ward” and the input is a matrix, metric must be “euclidean”.

• "cosine": cosine distance, defined as 1 - dot(x, y) / (norm(x) * norm(y)).

optimalOrdering (optional) A boolean scalar specifying whether to reorder the linkage matrix so that adjacent leaf nodes have small distances. The default value is false. Currently only false is supported.

Returns a DOUBLE matrix of shape (n - 1) × 4, where n is the number of original observations. Row i records the i-th cluster merge: columns 0 and 1 are the IDs of the two clusters being merged, column 2 is the distance between the two clusters at the time of the merge, and column 3 is the number of original observations contained in the new cluster. Original observations are numbered 0 to n−1, and newly generated clusters are numbered n, n+1, ..., 2n−2 in merge order.

Example 1. Condensed distance matrix input

X = [1.0, 2.0, 3.0]
linkage(X)

// Matrix input: each column is an observation vector
X = matrix(0.0 0.0, 0.0 4.0, 3.0 0.0)
linkage(X, method="single", metric="euclidean")

X = matrix(1.0 0.0, 0.0 1.0, 1.0 1.0)
linkage(X, method="average", metric="cosine")

// Construct observation data: 3 observations, each with 2 features
X = matrix(0.0 0.0, 0.0 4.0, 3.0 0.0)
// Generate the linkage matrix
Z = linkage(X, method="single", metric="euclidean")
// Generate cluster labels with fcluster based on a distance threshold
// Set threshold t=3.5 and criterion to 'distance'
labels = fcluster(Z, 3.5, criterion="distance")
labels
// output: [1, 2, 1]
// Observations 0 and 2 are close to each other (distance 3.0) and are assigned to cluster 1; observation 1 is farther away and is assigned to cluster 2.

Related functions: fcluster