linkage

Arguments

x

A double observation matrix or a condensed distance vector.

If x is a matrix, each row represents an observation. Distances are computed with pdist and then transformed with squareform.

If x is a vector, it is interpreted as a condensed distance vector.

method

Linkage method. The default value is "single".

• "single": single linkage.

• "complete": complete linkage.

• "average": average linkage unweighted by cluster sizes (UPGMA).

• "weighted": weighted average linkage (WPGMA).

• "centroid": centroid method (UPGMC).

• "median": median method (WPGMC).

• "ward": Ward method.

metric

Metric used by pdist when x is a matrix. Default value: "euclidean".

A cell can be used to pass additional arguments to pdist, for example, to set the Minkowski metric.

The methods "centroid", "median" et "ward" require the Euclidean metric.

z

A (n-1) x 3 matrix.

Each row contains the identifiers of the two merged clusters and the corresponding distance.

Initial observations are identified from 1 to n. The new clusters are numbered starting from n+1.

Description

linkage performs agglomerative hierarchical clustering.

Each observation initially constitutes a cluster. At each step, the two closest clusters are merged, and the distances are updated according to the chosen method.

For n observations, linkage performs n-1 merges and returns a matrix (n-1) x 3.

Methods

single

d(U,k) = min(d(r,k), d(c,k))

complete

d(U,k) = max(d(r,k), d(c,k))

average

d(U,k) = (nr*d(r,k) + nc*d(c,k)) / (nr+nc)

weighted

d(U,k) = (d(r,k) + d(c,k)) / 2

centroid

d(U,k)^2 = nr/(nr+nc)*d(r,k)^2 + nc/(nr+nc)*d(c,k)^2 - nr*nc/(nr+nc)^2*d(r,c)^2

Requires the Euclidean metric.

median

d(U,k)^2 = 1/2*d(r,k)^2 + 1/2*d(c,k)^2 - 1/4*d(r,c)^2

Requires the Euclidean metric.

ward

d(U,k)^2 = ((nr+nk)*d(r,k)^2 + (nc+nk)*d(c,k)^2 - nk*d(r,c)^2) / (nr+nc+nk)

Requires the Euclidean metric.

Where:

• r: index of the first cluster being merged.

• c: index of the second cluster being merged.

• U: the new cluster created by merging r and c.

• k: index of any other active cluster, different from r and c.

• nr: number of original observations contained in cluster r.

• nc: number of original observations contained in cluster c.

• nk: number of original observations contained in cluster k.

• d(r,k): distance between clusters r and k.

• d(c,k): distance between clusters c and k.

• d(r,c): distance between the two clusters being merged..

• d(U,k): distance between the newly created cluster U and cluster k.

Examples

X = [2  8  0
    1  9  9
    3  4  2
    8  1  6
    5  5  5
    7  2  1];

Z = linkage(X)

 
--> X = [2  8  0
    1  9  9
    3  4  2
    8  1  6
    5  5  5
    7  2  1];

--> Z = linkage(X)
Z = [5x3 double]

   3.   5.    3.7416574
   1.   7.    4.5825757
   6.   8.    4.5825757
   4.   9.    5.0990195
   2.   10.   6.9282032
   

X = [2  8  0
1  9  9
3  4  2
8  1  6
5  5  5
7  2  1];
methods = ["single", "complete", "average", "weighted", "centroid", "median", "ward"];

for method = methods
    Z = linkage(X, method);
    disp(method + ":", Z);
end

X = [2  8  0
    1  9  9
    3  4  2
    8  1  6
    5  5  5
    7  2  1];
Z = linkage(X, "average", "cityblock");

 
--> X = [2  8  0
    1  9  9
    3  4  2
    8  1  6
    5  5  5
    7  2  1];

--> Z = linkage(X, "average", "cityblock")
 Z = [5x3 double]

   3.   5.    6.       
   4.   6.    7.       
   1.   7.    9.       
   8.   9.    11.166667
   2.   10.   15.2
   

X = [2  8  0
    1  9  9
    3  4  2
    8  1  6
    5  5  5
    7  2  1];
p = 3;
Z = linkage(X, "average", {"minkowski", p})

 
--> X = [2  8  0
    1  9  9
    3  4  2
    8  1  6
    5  5  5
    7  2  1];

--> p = 3;
--> Z = linkage(X, "average", {"minkowski", p})
 Z = [5x3 double]

   3.   5.    3.3019272
   6.   7.    4.4027021
   4.   8.    5.1802944
   1.   9.    6.4984308
   2.   10.   8.4813034
            

Y = [3 4 10 12 5 11 13 6 8 2];
Z = linkage(Y, "average")

 
--> Y = [3 4 10 12 5 11 13 6 8 2];
--> Z = linkage(Y, "average")
 Z = [4x3 double]

   4.   5.   2. 
   1.   2.   3. 
   3.   7.   4.5
   6.   8.   10.
            

See Also

• pdist — Pairwise distances between observations
• squareform — Conversion between a distance vector and a symmetric distance matrix

History