nagdmc hclust

NAG DMCCluster Analysis: nagdmc hclust
Purposenagdmc hclust computes an hierarchical cluster analysis.

Declaration#include <nagdmc.h>void nagdmc hclust(long rec1, long nvar, long nrec, long dblk, double data[],long nxvar, long xvar[], int ctype, long lmerge[],long umerge[], double mergedist[], long denord[],double dendist[], int *info);

Parameters1:

rec1 – long

Input

On entry: the index in the data of the first data record used in the analysis.
Constraint: rec1 ≥ 0.
2:

nvar – long

Input

On entry: the number of variables in the data.
Constraint: nvar ≥ 1.
3:

nrec – long

Input

On entry: the number of consecutive records, beginning at rec1, used in the analysis.
Constraint: nrec > 1.
4:

dblk – long

Input

On entry: the total number of records in the data block.
Constraint: dblk ≥ rec1 + nrec.
5:

data[dblk ∗ nvar] – double

Input

On entry: the data values for the jth variable (for j = 0, 1, . . . , nvar−1) are stored in data[i∗nvar+j],
for i = 0, 1, . . . , dblk − 1.
6:nxvar – long

Input

On entry: the number of variables in the analysis. If nxvar = 0, all variables in the data are usedin the analysis.
Constraint: 0 ≤ nxvar ≤ nvar.
7:

xvar[nxvar] – long

Input

On entry: the indices indicating the position in data in which the variables are stored. If nxvar = 0
then xvar must be 0, and the indices of variables are given by j = 0, 1, . . . , nvar − 1 .
Constraints: if nxvar > 0, 0 ≤ xvar[i] < nvar, for i = 0, 1, . . . , nxvar − 1; otherwise xvar must be0.
8:

ctype – int

Input

On entry: if ctype is set equal to zero, the group average method is used; otherwise ctype must
equal one, and the minimum variance method is used.
Constraint: ctype ∈ {0, 1}.
9:lmerge[nrec−1] – double

OutputOn exit: see mergedist.
10:

umerge[nrec−1] – double

OutputOn exit: see mergedist.

nagdmc hclust.1

nagdmc hclust

NAG DMC11:

mergedist[nrec−1] – double
OutputOn exit: cluster umerge[i] is merged into cluster lmerge[i] at a distance mergedist[i], fori = 0, 1, . . . , nrec − 2.

12:denord[nrec] – long
On exit: the order of the data records required for producing a dendrogram.

13:

dendist[nrec] – double
OutputOn exit: dendist[i] is the distance at which cluster denord[i] merges with cluster denord[i + 1].
dendist[nrec − 1] contains the maximum distance.

14:

info – int *On exit: info gives information on the success of the function call:

OutputOutput0: the function successfully completed its task.
i; i = 1, 2, 3, 4, 6, 7, 8: the specification of the ith formal parameter was incorrect.
99: the function failed to allocate enough memory.
100: an internal error occurred during the execution of the function.

Notation
nrec
the number of data records, n.
nxvar
the number of variables, p.
lmerge[i]j at step i + 1 of the clustering.
umerge[i]k at step i + 1 of the clustering.
mergedist[i] the distance djk at which clusters j and k merged at step i + 1 of the clustering.
denordthe order, R, of data records for a dendrogram.
dendistthe merged distances in the order required by denord.

Description
Given n data records, a distance or dissimilarity matrix is a symmetric matrix with zero diagonal
elements such that the jkth element represents how far apart or how dissimilar the jth and kth
data records are.
Let X be an n by p data matrix of observations of p variables on n data records, then the squared
Euclidean distance between the jth and kth data records, djk , is:
djk =pX(xji − xki )2 ,i=1

where xji and xki are the (j, i)th and (k, i)th elements of X.
Given a distance or dissimilarity matrix for n data records, cluster analysis aims to group the ndata records into a number of similar groups or clusters. With agglomerative clustering methods,
an hierarchical tree is produced by starting with n clusters, each containing a single record. At
each of the n − 1 stages, the method merges the two nearest clusters to form a larger cluster. This
process continues until all data records belong to a single cluster.
Methods differ as to how the distance between the new cluster and other clusters are computed.
For three clusters i, j and k let ni , nj and nk be the number of data records in each cluster andlet dij , dik and djk be the distances between the clusters. Let clusters j and k be merged to givecluster jk, then the distance from cluster i to cluster jk, di.jk , can be computed in the followingways.
njnk
dij +
d ;
(a) Group average: di.jk =nj + nk
nj + nk ik
(b) Minimum variance: di.jk = (ni + nj )dij + (ni + nk )dik − ni djk /(ni + nj + nk ).
For convenience, clusters are numbered 0, 1, . . . , n − 1. If clusters j and k, j < k, merge then thenew cluster will be referred to as cluster j. Information on the merging of clusters is given by thenagdmc hclust.2

nagdmc hclust

NAG DMC

values of j, k and djk for each of the n − 1 clustering steps. The results of an hierarchical clustering
can be represented as a tree diagram, also known as a dendrogram, as shown in Figure 1. The
order of data records, R, required to draw a dendrogram without crossing dendrites is returned by
the function. This ordering is computed so that the first element is 0. The distances associatedwith this ordering are also returned by the function.

804

Merged Distances

12In Figure 1 the hierarchical clustering of five data records proceeds as follows. Reading thedendrogram from the record labels upwards, each record begins in its own cluster giving five clusters
labelled 0, 1, . . . , .4. At a distance of 2, clusters 0 and 1 combine to give four clusters labelled 0, 2, 3
and 4. Similarly, at a distance of 4 clusters 2 and 3 combine giving three clusters labelled 0, 2 and
4. At distance 9, cluster 4 joins the cluster labelled 2, giving two clusters labelled 0 and 2. Finally,
at a distance of 11 clusters 0 and 2 join to give a single cluster labelled 0.

01

32

4

Data Records

Figure 1: Dendrogram of example results from an hierarchical clustering. The orderof data record labels, R, ensures that none of the dendrites cross in the dendrogram.
This implementation of an hierarchical clustering procedure does not store in memory thedissimilarity matrix, thus reducing the storage required by O(n2 ). Hence this method can beapplied to higher numbers of data records than standard implementations.

References and Further Reading
Everitt B S (1974) Cluster Analysis Heinemann.
Krzanowski W J (1990) Principles of Multivariate Analysis Oxford University Press.

See Also
nagdmc cindnagdmc tab2
hclust ex.ccomputes cluster memberships following an hierarchical clustering.
cross-tabulates known groupings and cluster memberships.
the example calling program.

nagdmc hclust.3