Agglomerative Hierarchical Clustering

Problem :

Given 6-dimensional categorical samples C = (A, B, A, B, A, A) and

D = (B, B, A, B, B, A). Find:

a)                  Simple Matching Coefficient (SMC) of similarity between samples.

b)                  Jaccard’s Coefficient.

c)                  Rao’s Coefficient.

Answer:

            To find similarity coefficients, a contingency table should be built for the given samples:

            C = ABABAA

            D = BBABBA

Contingency Table				D
			A	B
		A	2	2
	C	B	0	2

            a)  S_smc(C, D) = (a+d)/(a+b+c+d) = (2+2)/(2+2+0+2) = 4/6 = 2/3

           

b)  S_jc(C, D) = a/(a+b+c) = (2)/(2+2+0) = 2/4 = ½

            c)  S_rc(C, D) = a/(a+b+c+d) = 2/(2+2+0+2) = 2/6 = 1/3

Problem :

Given a set of 5-dimensional categorical samples:

                        A = (1, 0, 1, 1, 0)

                        B = (1, 1, 0, 1, 0)

                        C = (0, 0, 1, 1, 0)

                        D = (0, 1, 0, 1, 0)

                        E = (1, 0, 1, 0, 1)

                        F = (0, 1, 1, 0, 0).

Apply agglomerative hierarchical clustering using:

a)                  Single-link similarity measure based on Rao’s coefficient.

b)                  Complete-link similarity measure based on simple matching    coefficient SMC.

c)                  Plot the dendograms for the solutions to part a) and b).

Answer:

a)Step 1: Place each sample in its own cluster. Construct the list of inter-cluster distances for all distinct unordered pairs of samples, and sort this list in ascending order.

The set of 5-dimensional categorical samples have binary feature values. A conventional method for obtaining a distance or similarity measure between two samples is to use the contingency table. The values of the parameters are then introduced as a, b, c, and d. The measures of similarity between points using Rao’s coefficient is computed using the following formula:

Smc(X,Y) = a/(a+b+c+d)

1. A = (1, 0, 1, 1, 0)

B = (1, 1, 0, 1, 0)

Values of the parameters are

a=2, b=1, c=1, d=1

Src(A,B) = 2/(2+1+1+1) = 2/5

= 0.4

2. A = (1, 0, 1, 1, 0)

C = (0, 0, 1, 1, 0)

Values of the parameters are

a=2, b=1, c=0, d=2

Src(A,C) = 2/(2+1+0+2) = 2/5

 = 0.4

3. A = (1, 0, 1, 1, 0)

D = (0, 1, 0, 1, 0)

Values of the parameters are

a=1, b=2, c=1, d=1

Src(A,D) = 1/(1+2+1+1) = 1/5

 = 0.2

4. A = (1, 0, 1, 1, 0)

E = (1, 0, 1, 0, 1)

Values of the parameters are

a=2, b=1, c=1, d=1

Src(A,E) = 2/(2+1+1+1) = 2/5

 = 0.4

5. A = (1, 0, 1, 1, 0)

F = (0, 1, 1, 0, 0)

           

Values of the parameters are

a=1, b=2, c=1, d=1

Src(A,E) = 1/(1+2+1+1) = 1/5

 = 0.2

6. B = (1, 1, 0, 1, 0)

            C = (0, 0, 1, 1, 0)

Values of the parameters are

a=1, b=2, c=1, d=1

Src(B,C) = 1/(1+2+1+1) = 1/5

 = 0.2

7. B = (1, 1, 0, 1, 0)

            D = (0, 1, 0, 1, 0)

Values of the parameters are

a=2, b=1, c=0, d=2

Src(B,D) = 2/(2+1+0+2) = 2/5

 = 0.4

8. B = (1, 1, 0, 1, 0)

            E = (1, 0, 1, 0, 1)

Values of the parameters are

a=1, b=2, c=2, d=0

Src(B,E) = 1/(1+2+2+0) = 1/5

 = 0.2

9. B = (1, 1, 0, 1, 0)

            F = (0, 1, 1, 0, 0)

Values of the parameters are

a=1, b=2, c=1, d=1

Src(B,F) = 1/(1+2+1+1) = 1/5

 = 0.2

10. C = (0, 0, 1, 1, 0)

            D = (0, 1, 0, 1, 0)

Values of the parameters are

a=1, b=1, c=1, d=2

Src(C,D) = 1/(1+1+1+2) = 1/5

 = 0.2

11. C = (0, 0, 1, 1, 0)

            E = (1, 0, 1, 0, 1)

Values of the parameters are

a=1, b=1, c=2, d=1

Src(C,E) = 1/(1+1+2+1) = 1/5

 = 0.2

12. C = (0, 0, 1, 1, 0)

            F = (0, 1, 1, 0, 0)

Values of the parameters are

a=1, b=1, c=1, d=2

Src(C,F) = 1/(1+1+1+2) = 1/5

 = 0.2

13. D = (0, 1, 0, 1, 0)

            E = (1, 0, 1, 0, 1)

Values of the parameters are

a=0, b=2, c=3, d=0

Src(D,E) = 0/(0+2+3+0) = 0/5

 = 0

14. D = (0, 1, 0, 1, 0)

            F = (0, 1, 1, 0, 0)

Values of the parameters are

a=1, b=1, c=1, d=2

Src(D,F) = 1/(1+1+1+2) = 1/5

 = 0.5

15. E = (1, 0, 1, 0, 1)

            F = (0, 1, 1, 0, 0)

           

Values of the parameters are

a=1, b=2, c=1, d=1

Src(E,F) = 1/(1+2+1+1) = 1/5

 = 0.2

Src(A,D) = 0.2   Src(A,F) = 0.2   Src(A,B) = 0.4   Src(A,C) = 0.4   Src(A,E) = 0.4

Src(B,C) = 0.2   Src(B,E) = 0.2   Src(B,F) = 0.2   Src(B,D) = 0.4

Src(C,D) = 0.2   Src(C,E) = 0.2   Src(C,F) = 0.2

Src(D,E) = 0      Src(D,F) = 0.2

Src(E,F) = 0.2

Step 2:

First, D and E samples are merged and a cluster {D,E} is generated with a minimum distance equal to 0. Second, F is merged into cluster {D,E} with a higher merging level of 0.2. At the same time, the minimum single-link distance between clusters {D,F}, {C,F}, {C,E}, {C,D}, {B,C}, {B,E}, {B,F}, {A,D}, {A,F},  and, is also 0.2. So, these clusters merge into {D,E} with same merging level of 0.2 . Finally, there is only one cluster {D,E,F,C,B,A}.

Step 3:

The output of the algorithm is a nested hierarchy of graphs, which can be cut at the desired dissimilarity level forming a partition (clusters) identified by simple connected components in the corresponding subgraph.

b)Apply agglomerative hierarchical clustering using

                      I.    Complete link similarity measure based on simple matching coefficient SMC

Step 1: Place each sample in its own cluster. Construct the list of inter-cluster distances for all distinct unordered pairs of samples, and sort this list in ascending order.

The set of 5-dimensional categorical samples have binary feature values. A conventional method for obtaining a distance or similarity measure between two samples is to use the contingency table. The values of the parameters are then introduced as a, b, c, and d. The measures of similarity between points using SMC(Simple Matching Coefficient) is computed using the following formula:

Smc(X,Y) = (a+d)/(a+b+c+d)

16. A = (1, 0, 1, 1, 0)

B = (1, 1, 0, 1, 0)

Values of the parameters are

a=2, b=1, c=1, d=1

Smc(A,B) = 2+1/(2+1+1+1) = 3/5

= 0.6

17. A = (1, 0, 1, 1, 0)

C = (0, 0, 1, 1, 0)

Values of the parameters are

a=2, b=1, c=0, d=2

Smc(A,C) = 2+2/(2+1+0+2) = 4/5

 = 0.8

18. A = (1, 0, 1, 1, 0)

D = (0, 1, 0, 1, 0)

Values of the parameters are

a=1, b=2, c=1, d=1

Smc(A,D) = 1+1/(1+2+1+1) = 2/5

 = 0.4

19. A = (1, 0, 1, 1, 0)

E = (1, 0, 1, 0, 1)

Values of the parameters are

a=2, b=1, c=1, d=1

Smc(A,E) = 2+1/(2+1+1+1) = 3/5

 = 0.6

20. A = (1, 0, 1, 1, 0)

F = (0, 1, 1, 0, 0)

           

Values of the parameters are

a=1, b=2, c=1, d=1

Smc(A,E) = 1+1/(1+2+1+1) = 2/5

 = 0.4

21. B = (1, 1, 0, 1, 0)

            C = (0, 0, 1, 1, 0)

Values of the parameters are

a=1, b=2, c=1, d=1

Smc(B,C) = 1+1/(1+2+1+1) = 2/5

 = 0.4

22. B = (1, 1, 0, 1, 0)

            D = (0, 1, 0, 1, 0)

Values of the parameters are

a=2, b=1, c=0, d=2

Smc(B,D) = 2+2/(2+1+0+2) = 4/5

 = 0.8

23. B = (1, 1, 0, 1, 0)

            E = (1, 0, 1, 0, 1)

Values of the parameters are

a=1, b=2, c=2, d=0

Smc(B,E) = 1+0/(1+2+2+0) = 1/5

 = 0.2

24. B = (1, 1, 0, 1, 0)

            F = (0, 1, 1, 0, 0)

Values of the parameters are

a=1, b=2, c=1, d=1

Smc(B,F) = 1+1/(1+2+1+1) = 2/5

 = 0.4

25. C = (0, 0, 1, 1, 0)

            D = (0, 1, 0, 1, 0)

Values of the parameters are

a=1, b=1, c=1, d=2

Smc(C,D) = 1+2/(1+1+1+2) = 3/5

 = 0.6

26. C = (0, 0, 1, 1, 0)

            E = (1, 0, 1, 0, 1)

Values of the parameters are

a=1, b=1, c=2, d=1

Smc(C,E) = 1+1/(1+1+2+1) = 2/5

 = 0.4

27. C = (0, 0, 1, 1, 0)

            F = (0, 1, 1, 0, 0)

Values of the parameters are

a=1, b=1, c=1, d=2

Smc(C,F) = 1+2/(1+1+1+2) = 3/5

 = 0.6

28. D = (0, 1, 0, 1, 0)

            E = (1, 0, 1, 0, 1)

Values of the parameters are

a=0, b=2, c=3, d=0

Smc(D,E) = 0/(0+2+3+0) = 0/5

 = 0

29. D = (0, 1, 0, 1, 0)

            F = (0, 1, 1, 0, 0)

Values of the parameters are

a=1, b=1, c=1, d=2

Smc(D,F) = 1+2/(1+1+1+2) = 3/5

 = 0.6

30. E = (1, 0, 1, 0, 1)

            F = (0, 1, 1, 0, 0)

           

Values of the parameters are

a=1, b=2, c=1, d=1

Smc(E,F) = 1+1/(1+2+1+1) = 2/5

 = 0.4

Smc(A,D) = 0.4             Smc(A,F) = 0.4  Smc(A,B) = 0.6 Smc(A,E) = 0.4 Smc(A,C) = 0.8

Smc(B,E) = 0.2 Smc(B,C) = 0.4 Smc(B,F) = 0.4 Smc(B,D) = 0.8

Smc(C,E) = 0.4 Smc(C,D) = 0.6 Smc(C,F) = 0.6

Smc(D,E) = 0    Smc(D,F) = 0.6

Smc(E,F) = 0.4

Step 2:

First, D and E samples are merged and a cluster {D,E} is generated with a minimum distance equal to 0. Second, B and C are merged into a new cluster {B,C} with a higher merging level of 0.4 . At the same time, A and F are merged into a new cluster {A,F} with the same merging level of 0.4. {B,C} is merged with {A,F} into a new cluster {B,C,A,F} with a higher merging level of 0.6. Finally, {D,E} is merged with cluster {B,C,A,F} into a single cluster {D,E,B,C,A,F} with a higher merging level of 0.8.

Step 3:

The output of the algorithm is a nested hierarchy of graphs, which can be cut at the desired dissimilarity level forming a partition (clusters) identified by simple connected components in the corresponding subgraph.