Reorder Tree 

Home
About Clustan
Cluster Analysis
Applications
ClustanGraphics
User Support
Clustan/PC
Orders
What's New
White Papers
Contact Us

In our Cars case study, a distance matrix was computed from standardized variables.  It has the following values: 

Case

Renault

Volvo

Vauxhall

Toyota

Audi

BMW

Rover

Nissan

Volvo

0.229

 

 

 

 

 

 

 

Vauxhall

0.311

0.701

 

 

 

 

 

 

Toyota

1.243

1.864

0.917

 

 

 

 

 

Audi

1.066

1/848

0.453

1.954

 

 

 

 

BMW

3.105

3.996

2.089

4.935

0.752

 

 

 

Rover

0.650

1.111

0.368

0.435

1.004

3.068

 

 

Nissan

2.238

3.299

2.211

0.997

2.769

6.055

1.638

 

Honda

1.716

1.642

2.084

1.076

3.746

7.488

1.405

1.539

We obtain a hierarchical cluster analysis on this distance matrix using Increase in Sum of Squares (Ward's Method) which produced the following tree:

 

ClustanGraphics can display a shaded representation of the proximity matrix, with the rows re-ordered to correspond to the tree:

 

However, this proximity matrix and the corresponding tree may not be optimally ordered.  There are many ways to display a tree, because the order of the cases within any of the clusters can be reversed.  Thus there are 2n-1 different ways to order a tree of n cases.  Even in this small example, involving 9 cases, there are 256 different tree orders.

ClustanGraphics can examine these different orderings and find a new order which concentrates the strongest proximities close to the diagonal.  The objective is to maximize the rank order of the proximities in every row, such that they correspond as closely as possible to the "perfect" rank order", as follows: 

Case

Renault

Volvo

Vauxhall

Toyota

Audi

BMW

Rover

Nissan

Honda

Renault

0

1

2

3

4

5

6

7

8

Volvo

1

0

1

2

3

4

5

6

7

Vauxhall

2

1

0

1

2

3

4

5

6

Toyoto

3

2

1

0

1

2

3

4

5

Audi

4

3

2

1

0

1

2

3

4

BMW

5

4

3

2

1

0

1

2

3

Rover

6

5

4

3

2

1

0

1

2

Nissan

7

6

5

4

3

2

1

0

1

Honda

8

7

6

5

4

3

2

1

0

The result after 4 iterations of the serial re-ordering procedure in ClustanGraphics is shown above.  Note that the heaviest shading is now much more concentrated close to the diagonal.  The tree from Ward's Method which corresponds to this optimal order has now been re-arranged as follows:

The re-ordered tree can now be more easily interpreted than the original tree.  The algorithm used to optimally re-order a hierarchical cluster analysis was first presented at the Second World Conference of the IASC, Pasadena 1997 and was been published in: Wishart, D. (1997), ClustanGraphics: Interactive Graphics for Cluster Analysis, Computing Science and Statistics, 29, 48-51.  A revised version was later presented at GfKl '98, and published in: Wishart, D. (1999), ClustanGraphics3: Interactive Graphics for Cluster Analysis, in Classification in the Information Age, Gaul, W. and Locarek-Junge, H. (Eds), Springer 1999, 268-275.  The paper can be downloaded here as a zip file, by kind permission of Springer-Verlag (70 Kb).