Clustering + classification

Minimum distance d min(Ci, Cj) = min pÎCi, p' ÎCj    |􀀀p-p'|

Suppose that the samples are clustered into two clusters:

                        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).

            C1 = {A, B, E} and C2 = {C, D, F}.

 Using K-nearest neighbor algorithm / farthest-neighbor clustering algorithm , find the classification for the following samples:

a)      Y = {1 ,1 ,0 ,1 ,1} using K = 1.

b)      Y = {1 ,1 ,0 ,1 ,1} using K = 3.

c)      Z = {0, 1, 0, 0, 0} using K = 1.

d)      Z = {0, 1, 0, 0, 0} using K = 5.

Answer:

a)      and b)

Similarities of Y  with elements in C1:

SMC (Y, A) = 3/5 = 0.6         

SMC (Y, B) = 4/5 = 0.8         

SMC (Y, C) = 2/5 = 0.4         

Similarities of Y with elements in C2:

SMC (Y, C) = 1/5 = 0.2         

SMC (Y, D) = 3/5 = 0.6         

SMC (Y, F) = 1/5 = 0.2         

The sorted SMC list for C1 is à {0.4, 0.6, 0.8}

The sorted SMC list for C2 is à {0.2, 0.2, 0.6}

a)         Using K=1, the highest SMC value, 0.8, is in C1; hence, Y Î C1.

b)         Using K=3, out of the highest three SMC values, {0.8, 0.6, 0.6}, two values {0.8, 0.6} belong to is in C1; hence, Y Î C1.

c) and d)

Similarities of Z with elements in C1:

SMC (Z, A) = 1/5 = 0.2         

SMC (Z, B) = 3/5 = 0.6         

SMC (Z, C) = 1/5 = 0.2         

Similarities with elements in C2:

SMC (Z, C) = 2/5 = 0.4         

SMC (Z, D) = 4/5 = 0.8         

SMC (Z, F) = 4/5 = 0.8          

The sorted SMC list for C1 is à {0.2, 0.2, 0.6}

The sorted SMC list for C2 is à {0.4, 0.8, 0.8}

c)         Using K=1, the highest SMC value, 0.8, is in C2; hence, Y Î C2.

d)         Using K=3, out of the highest three SMC values, {0.8, 0.8, 0.6}, two values {0.8, 0.8} belong to is in C2; hence, Y Î C2.

Clustering K-means

Given the samples X1 = {1, 0}, X2 = {0, 1}, X3 = {2, 1}, and X4 = {3, 3}. 

Suppose that samples are randomly clustered into two clusters C1 = {X1, X3} and C2 = {X2, X4}.

a)      Apply one iteration of K-means partitional clustering algorithm, and find a new distribution of samples in clusters. What are the new centroids? How you can prove that the new distribution of samples is better than the initial one?

b)      What is the change in a total square error?

c)      Apply the second iteration of K-means algorithm and discuss the changes in clusters.

Answer:

a)         M1 = { (1+2)/2, (0+1)/2} = {1.33, 0.5}

            M2 = { (0+3)/2,(1+3)/2} = { 1.33, 2}

within cluster variation after initial random distribution of samples

e₁^{2 =}  =.33² + .5² + .66² + .5² = 1.0445

e₂² =1.33² + 1² + 1.66² + 1² = 6.5245

E² = e₁²  + e₂²    = 7.569

Redistribution :-

d(M1,X1) = {( 1-1.33)2 + (.5)2 } ½  = .599 

d(M2,X1)= {(1-1.33)2 + (2)2 } ½ = 2.02

d(M1,X2) = {( 1.33)2 + (.5)2 } ½  = 1.42 

d(M2,X2)= {(1.33)2 + (1)2 } ½ = 1.66

d(M1,X3) = {( 2-1.33)2 + (.5)2 } ½  = .6828 

d(M2,X3)= {(.66)2 + (1)2 } ½ = 1.198

d(M1,X4) = {( 3-1.33)2 + (3-.5)2 } ½ = 3.00 

d(M2,X4)={(3-1.33)2 + (3-2)2 }1/2 =1.937

implies:            X1 Î C1

                                    X2 Î C1

                                    X3 Î C1

                                    X4 Î C2

New cluster are: C1 = { X1, X2, X3} and C2 = {X4}

And  new centroid s are:

M1 = (1, 0.66)

M2 = (3, 3)

b)         e₁²= [0²+ .66²+ 1²+ .33² + 1²+ .33²] = 2.65                

e₂² = 0

E² = e₁² + e₂²    = 2.65

Total error is significantly smaller than the one in the first iteration. We may conclude that the distribution of samples is better than initial one.

c)         After second iteration there are no changes in clusters and their centroids. Therefore, we may conclude that C1 = {X1, X2, X3} and C2 = {X4} is the final clustering result.

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.

Cluster distance

Given 5-dimensional numerical samples A= (1, 0, 2, 5, 3) and B = (2, 1, 0, 3, -1).

Find:

1. Eucledian distance between points.
2. City-block distance.
3. Minkowski distance for p=3.
4. Cosine-correlation distance.

Answer:

a) the Euclidean distance:

d2(A, B) =

 =

 = 5.1

b) the city-block distance:

d1(A, B) =

 =

 = 10

c) the Minkowski distance for p=3:

d3(A, B) =

 =

 = 4.34

d) the cosine-correlation distance:

scos(A, B) =

   =

   = 0.58