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.