Chapter 9: Multivariate Analysis

cluster_hierarchical

Performs a hierarchical cluster analysis given a distance matrix.

Synopsis                                                                                  

#include <imsls.h>

void imsls_f_cluster_hierarchical (int npt, float *dist, …, 0)

The type double function is imsls_d_cluster_hierarchical.

Required Arguments

int npt  (Input)
Number of data points to be clustered.

void *dist  (Input/Ouput)
An npt by npt symmetric matrix containing the distance (or similarity) matrix.
dist is a symmetric matrix. On input, only the upper triangular part needs to be present. The function imsls_f_cluster_hierarchical saves the upper triangular part of dist in the lower triangle. On return from imsls_f_cluster_hierarchical, the upper triangular part of dist is restored, and the matrix is made symmetric.

Synopsis with Optional Arugments

#include <imsls.h>

float *imsls_f_cluster_hierarchical (int npt, float *dist,
IMSLS_METHOD, int imeth,
IMSLS_TRANSFORMATION, int itrans,
IMSLS_CLUSTERS, float **clevel,  int **iclson,  int **icrson,
IMSLS_CLUSTERS_USER, float clevel[],  int iclson[],  int icrson[],
0)                            

Optional Arguments

IMSLS_METHOD, int imeth  (Input)
Option giving the clustering method to be used. 
Default: imeth = 0.

Imeth

Method

0

Single linkage (minimum distance)

1

Complete linkage (maximum distance)

2

Average distance within (average distance between objects within the merged cluster)

3

Average distance between (average distance between objects in the two clusters)

4

Ward’s method (minimize the within-cluster sums of squares). For Ward’s method, the elements of dist are assumed to be Euclidean distances.

IMSLS_TRANSFORMATION, int itrans  (Input)
Option giving the method to be used for clustering. 
Default: itrans = 0.

Imeth

Method

0

No transformation is required. The elements of dist are distances.

1

Convert similarities to distances by multiplication by -1.0.

2

Convert similarities (usually correlations) to distances by taking the reciprocal of the absolute value.

IMSLS_CLUSTERS, float **clevel,  int **iclson,  int **icrson   (Output)
Argument clevel is the address of an array of length npt - 1 containing the level at which the clusters are joined.  clevel[k-1] contains the distance (or similarity) level at which cluster npt + k was formed. If the original data in dist was transformed via the optional argument IMSLS_TRANSFORMATION, the inverse transformation is applied to the values in clevel prior to exit from imsls_f_cluster_hierarchical. Argument iclson is the address of an array of length npt - 1 containing the left sons of each merged cluster.   Argument icrson is the address of an array of length npt - 1 containing the right sons of each merged cluster.   Cluster
npt + k is formed by merging clusters iclson[k-1] and icrson[k-1].

IMSLS_CLUSTERS_USER, float clevel[],  int iclson[],  int icrson[]   (Output)
Storage for arrays clevel, iclson, and icrson is provided by the user.  See IMSLS_CLUSTERS.                                 

Description

Function imsls_f_cluster_hierarchical conducts a hierarchical cluster analysis based upon the distance matrix, or by appropriate use of the IMSLS_TRANSFORMATION optional argument, based upon a similarity matrix. Only the upper triangular part of the matrix dist is required as input to imsls_f_cluster_hierarchical.

Hierarchical clustering in imsls_f_cluster_hierarchical proceeds as follows. Initially, each data point is considered to be a cluster, numbered 1 to
n = npt.

1.         If the data matrix contains similarities, they are converted to distances by the method specified by IMSLS_TRANSFORMATION. Set k = 1.

2.         A search is made of the distance matrix to find the two closest clusters. These clusters are merged to form a new cluster, numbered n + k. The cluster numbers of the two clusters joined at this stage are saved in icrson and iclson, and the distance measure between the two clusters is stored in clevel.

3.         Based upon the method of clustering, updating of the distance measure in the row and column of dist corresponding to the new cluster is performed.

4.         Set k = k + 1. If k < n, go to Step 2.

The five methods differ primarily in how the distance matrix is updated after two clusters have been joined. The IMSLS_METHOD optional argument specifies how the distance of the cluster just merged with each of the remaining clusters will be updated. Function imsls_f_cluster_hierarchical allows five methods for computing the distances. To understand these measures, suppose in the following discussion that clusters “A” and “B” have just been joined to form cluster “Z”, and interest is in computing the distance of Z with another cluster called “C”.

imeth

Method

0

Single linkage method. The distance from Z to C is the minimum of the distances (A to C, B to C).

1

Complete linkage method. The distance from Z to C is the maximum of the distances (A to C, B to C).

2

Average-distance-within-clusters method. The distance from Z to C is the average distance of all objects that would be within the cluster formed by merging clusters Z and C. This average may be computed according to formulas given by Anderberg (1973, page 139).

3

Average-distance-between-clusters method. The distance from Z to C is the average distance of objects within cluster Z to objects within cluster C. This average may be computed according to methods given by Anderberg (1973, page 140).

4

Ward’s method. Clusters are formed so as to minimize the increase in the within-cluster sums of squares. The distance between two clusters is the increase in these sums of squares if the two clusters were merged. A method for computing this distance from a squared Euclidean distance matrix is given by Anderberg (1973, pages 142-145).

In general, single linkage will yield long thin clusters while complete linkage will yield clusters that are more spherical. Average linkage and Ward’s linkage tend to yield clusters that are similar to those obtained with complete linkage.

Function imsls_f_cluster_hierarchical produces a unique representation of the binary cluster tree via the following three conventions; the fact that the tree is unique should aid in interpreting the clusters. First, when two clusters are joined and each cluster contains two or more data points, the cluster that was initially formed with the smallest level (in clevel) becomes the left son. Second, when a cluster containing more than one data point is joined with a cluster containing a single data point, the cluster with the single data point becomes the right son. Finally, when two clusters containing only one object are joined, the cluster with the smallest cluster number becomes the right son.

Comments

1.         The clusters corresponding to the original data points are numbered from 1 to npt. The npt - 1 clusters formed by merging clusters are numbered npt + 1 to npt + (npt - 1).

2.         Raw correlations, if used as similarities, should be made positive and transformed to a distance measure. One such transformation can be performed by specifying optional argument IMSLS_TRANSFORMATION, with itrans = 2 in imsls_f_cluster_hierarchical.

3.         The user may cluster either variables or observations in imsls_f_cluster_hierarchical since a dissimilarity matrix, not the original data, is used. Function imsls_f_dissimilarities (page 585) may be used to compute the matrix dist for either the variables or observations.

Example

In the following example, the average distance within clusters method is used to perform a hierarchical cluster analysis of the Fisher iris data. Function imsls_f_data_sets (see Chapter 15,   “Utilities”;) is first used to obtain the Fisher iris data. The example is typical in that after the program obtains the data, function imsls_f_dissimilarities computes the distance matrix (dist) prior to calling imsls_f_cluster_hierarchical.

 

#include "imsls.h"

 

void main()

{

  int  iscale=1, ncol=5, nrow=150, nvar=4, npt = 150; 

  int i, iclson[149], icrson[149], ind[4] = {1, 2, 3, 4};

  float clevel[149], *dist, *x;

 

  x = imsls_f_data_sets(3, 0);

 

  dist = imsls_f_dissimilarities(nrow, ncol, x,

                            IMSLS_INDEX, nvar, ind,

                            IMSLS_SCALE, iscale,

                            0);

  imsls_f_cluster_hierarchical(npt, dist,

              IMSLS_CLUSTERS_USER, clevel, iclson, icrson,

              IMSLS_METHOD, 2,

              0);

 

  for (i=0;i<149;i+=15) printf("%6.2f\t", clevel[i]);

  printf("\n");

  for (i=0;i<149;i+=15) printf("%6d\t", iclson[i]);

  printf("\n");

  for (i=0;i<149;i+=15) printf("%6d\t", icrson[i]);

  printf("\n");

}

 

Output

  0.00    0.17    0.23    0.27    0.31    0.37    0.41    0.48    0.60    0.78

   143     153      17     140      53     198     186     218     261     249

   102      29       6     113      51      91     212     243     266     262

   

Visual Numerics, Inc.
Visual Numerics - Developers of IMSL and PV-WAVE
http://www.vni.com/
PHONE: 713.784.3131
FAX:713.781.9260