Integer, Intent (In)	::	n, m, ldx, isx(m), nvar, k, ldc, maxit
Integer, Intent (Inout)	::	ifail
Integer, Intent (Out)	::	inc(n), nic(k), iwk(n+3*k)
Real (Kind=nag_wp), Intent (In)	::	x(ldx,m), wt(*)
Real (Kind=nag_wp), Intent (Inout)	::	cmeans(ldc,nvar)
Real (Kind=nag_wp), Intent (Out)	::	css(k), csw(k), wk(n+2*k)
Character (1), Intent (In)	::	weight

C Header Interface

#include <nag.h>

void

g03eff_ (const char *weight, const Integer *n, const Integer *m, const double x[], const Integer *ldx, const Integer isx[], const Integer *nvar, const Integer *k, double cmeans[], const Integer *ldc, const double wt[], Integer inc[], Integer nic[], double css[], double csw[], const Integer *maxit, Integer iwk[], double wk[], Integer *ifail, const Charlen length_weight)

The routine may be called by the names g03eff or nagf_mv_cluster_kmeans.

3 Description

Given

n

objects with

p

variables measured on each object,

x_{i j}

, for

i = 1, 2, \dots, n

and

j = 1, 2, \dots, p

, g03eff allocates each object to one of

K

groups or clusters to minimize the within-cluster sum of squares:

\sum_{k = 1}^{K} \sum_{i \in S_{k}} \sum_{j = 1}^{p} {(x_{i j} - {\bar{x}}_{k j})}^{2},

where

S_{k}

is the set of objects in the

k

th cluster and

{\bar{x}}_{k j}

is the mean for the variable

j

over cluster

k

. This is often known as

K

-means clustering.

In addition to the data matrix, a

K

p

matrix giving the initial cluster centres for the

K

clusters is required. The objects are then initially allocated to the cluster with the nearest cluster mean. Given the initial allocation, the procedure is to iteratively search for the

K

-partition with locally optimal within-cluster sum of squares by moving points from one cluster to another.

Optionally, weights for each object,

w_{i}

, can be used so that the clustering is based on within-cluster weighted sums of squares:

\sum_{k = 1}^{K} \sum_{i \in S_{k}} \sum_{j = 1}^{p} w_{i} {(x_{i j} - {\tilde{x}}_{k j})}^{2},

where

{\tilde{x}}_{k j}

is the weighted mean for variable

j

over cluster

k

The routine is based on the algorithm of Hartigan and Wong (1979).

4 References

Everitt B S (1974) Cluster Analysis Heinemann

Hartigan J A and Wong M A (1979) Algorithm AS 136: A K-means clustering algorithm Appl. Statist. 28 100–108

Kendall M G and Stuart A (1976) The Advanced Theory of Statistics (Volume 3) (3rd Edition) Griffin

Krzanowski W J (1990) Principles of Multivariate Analysis Oxford University Press

5 Arguments

1: $weight$ – Character(1) Input

On entry: indicates if weights are to be used.

$weight ='U'$: No weights are used.
$weight ='W'$: Weights are used and must be supplied in wt.

Constraint:

weight ='U'

'W'

2: $n$ – Integer Input

On entry:

n

, the number of objects.

Constraint:

n > 1

3: $m$ – Integer Input

On entry: the total number of variables in array x.

Constraint:

m \geq nvar

4: $x (ldx, m)$ – Real (Kind=nag_wp) array Input

On entry:

x (i, j)

must contain the value of the

j

th variable for the

i

th object, for

i = 1, 2, \dots, n

and

j = 1, 2, \dots, m

5: $ldx$ – Integer Input

On entry: the first dimension of the array x as declared in the (sub)program from which g03eff is called.

Constraint:

ldx \geq n

6: $isx (m)$ – Integer array Input

On entry:

isx (j)

indicates whether or not the

j

th variable is to be included in the analysis. If

isx (j) > 0

, the variable contained in the

j

th column of x is included, for

j = 1, 2, \dots, m

Constraint:

isx (j) > 0

for nvar values of

j

7: $nvar$ – Integer Input

On entry:

p

, the number of variables included in the sums of squares calculations.

Constraint:

1 \leq nvar \leq m

8: $k$ – Integer Input

On entry:

K

, the number of clusters.

Constraint:

k \geq 2

9: $cmeans (ldc, nvar)$ – Real (Kind=nag_wp) array Input/Output

On entry:

cmeans (i, j)

must contain the value of the

j

th variable for the

i

th initial cluster centre, for

i = 1, 2, \dots, K

and

j = 1, 2, \dots, p

On exit:

cmeans (i, j)

contains the value of the

j

th variable for the

i

th computed cluster centre, for

i = 1, 2, \dots, K

and

j = 1, 2, \dots, p

10: $ldc$ – Integer Input

On entry: the first dimension of the array cmeans as declared in the (sub)program from which g03eff is called.

Constraint:

ldc \geq k

11: $wt (*)$ – Real (Kind=nag_wp) array Input

Note: the dimension of the array wt must be at least

n

weight ='W'

, and at least

1

otherwise.

On entry: if

weight ='W'

, the first

n

elements of wt must contain the weights to be used.

wt (i) = 0.0

, the

i

th observation is not included in the analysis. The effective number of observation is the sum of the weights.

weight ='U'

, wt is not referenced and the effective number of observations is

n

Constraint: if

weight ='W'

wt (i) \geq 0.0

and

wt (i) > 0.0

for at least two values of

i

, for

i = 1, 2, \dots, n

12: $inc (n)$ – Integer array Output

On exit:

inc (i)

contains the cluster to which the

i

th object has been allocated, for

i = 1, 2, \dots, n

13: $nic (k)$ – Integer array Output

On exit:

nic (i)

contains the number of objects in the

i

th cluster, for

i = 1, 2, \dots, K

14: $css (k)$ – Real (Kind=nag_wp) array Output

On exit:

css (i)

contains the within-cluster (weighted) sum of squares of the

i

th cluster, for

i = 1, 2, \dots, K

15: $csw (k)$ – Real (Kind=nag_wp) array Output

On exit:

csw (i)

contains the within-cluster sum of weights of the

i

th cluster, for

i = 1, 2, \dots, K

. If

weight ='U'

, the sum of weights is the number of objects in the cluster.

16: $maxit$ – Integer Input

On entry: the maximum number of iterations allowed in the analysis.

Suggested value:

maxit = 10

Constraint:

maxit > 0

17: $iwk (n + 3 \times k)$ – Integer array Workspace

18: $wk (n + 2 \times k)$ – Real (Kind=nag_wp) array Workspace

19: $ifail$ – Integer Input/Output

On entry: ifail must be set to

0

- 1 or 1

. If you are unfamiliar with this argument you should refer to Section 4 in the Introduction to the NAG Library FL Interface for details.

For environments where it might be inappropriate to halt program execution when an error is detected, the value

- 1 or 1

is recommended. If the output of error messages is undesirable, then the value

1

is recommended. Otherwise, if you are not familiar with this argument, the recommended value is

0

. When the value $- 1 or 1$ is used it is essential to test the value of ifail on exit.

On exit:

ifail = 0

unless the routine detects an error or a warning has been flagged (see Section 6).

6 Error Indicators and Warnings

If on entry

ifail = 0

- 1

, explanatory error messages are output on the current error message unit (as defined by x04aaf).

Errors or warnings detected by the routine:

$ifail = 1$: On entry, $k = 〈value〉$ .
Constraint: $k \geq 2$ .

On entry, $ldc = 〈value〉$ and $k = 〈value〉$ .
Constraint: $ldc \geq k$ .

On entry, $ldx = 〈value〉$ and $n = 〈value〉$ .
Constraint: $ldx \geq n$ .

On entry, $m = 〈value〉$ and $nvar = 〈value〉$ .
Constraint: $m \geq nvar$ .

On entry, $maxit = 〈value〉$ .
Constraint: $maxit > 0$ .

On entry, $n = 〈value〉$ .
Constraint: $n > 1$ .

On entry, $nvar = 〈value〉$ .
Constraint: $nvar \geq 1$ .

On entry, $weight = 〈value〉$ .
Constraint: $weight ='U'$ or $'W'$ .

$ifail = 2$: On entry, $i = 〈value〉$ and $wt (i) < 0.0$ .
Constraint: $wt (i) \geq 0.0$ .

On entry, wt has less than two positive values.

$ifail = 3$: On entry, $nvar = 〈value〉$ and $〈value〉$ values of $isx > 0$ .
Constraint: exactly nvar elements of $isx > 0$ .

$ifail = 4$: At least one cluster is empty after the initial assignment. Try a different set of initial cluster centres in cmeans and also consider decreasing the value of k. The empty clusters may be found by examining the values in nic.

$ifail = 5$: Convergence has not been achieved within the maximum number of iterations $maxit = 〈value〉$ . Try increasing maxit and, if possible, use the returned values in cmeans as the initial cluster centres.

$ifail = - 99$: An unexpected error has been triggered by this routine. Please contact NAG.
See Section 7 in the Introduction to the NAG Library FL Interface for further information.

$ifail = - 399$: Your licence key may have expired or may not have been installed correctly.
See Section 8 in the Introduction to the NAG Library FL Interface for further information.

$ifail = - 999$: Dynamic memory allocation failed.
See Section 9 in the Introduction to the NAG Library FL Interface for further information.

7 Accuracy

g03eff produces clusters that are locally optimal; the within-cluster sum of squares may not be decreased by transferring a point from one cluster to another, but different partitions may have the same or smaller within-cluster sum of squares.

8 Parallelism and Performance

g03eff is not threaded in any implementation.

9 Further Comments

The time per iteration is approximately proportional to

np K

10 Example

The data consists of observations of five variables on twenty soils (see Hartigan and Wong (1979)). The data is read in, the

K

-means clustering performed and the results printed.

Interfaces: FL CL AD

NAG FL Interface Introduction

G03 (Mv) Chapter Contents

G03 (Mv) Chapter Introduction

g03ef: FL CL AD

NAG FL Interfaceg03eff (cluster_​kmeans)

▸▿ Contents

1 Purpose

2 Specification

3 Description

4 References

5 Arguments

6 Error Indicators and Warnings

7 Accuracy

8 Parallelism and Performance

9 Further Comments

10 Example

10.1 Program Text

10.2 Program Data

10.3 Program Results

NAG FL Interface
g03eff (cluster_kmeans)