6CCS3AIN, Tutorial 06 Answers (Version 1.0)
3 4 1 1 1
1. Performk-Medianonthefollowinginput: x1 = 4 x2 = 2 x3 = 2 x4 = 1 x5 = 3 . Assume that k=2 and the initial clusters location of the clusters are
1 2 μ1= 1 andμ2= 4 .
Recall, that the distance between two points is the sum of the absolute values. E.g., the distance between x1 and x2 is |3−4|+|4−2| = 3. In case of a tie, assign the data point to the cluster with the smaller ID. Solution:
(a) Assignment 1: S1 = {x2, x3, x4, x5} and S2 = {x1}. 7/4 3
(b)Update1:μ1= 2 andμ2= 4 .
(c) Assignment 2: S1 = {x2, x3, x4, x5} and S2 = {x1}.
(d) Nothing changes, so the algorithm terminates
2. How would the first assignment and update step look if we used k-Means instead?
Solution:
(a) Assignment 1: S1 = {x3, x4} and S2 = {x1, x2, x5}. 1 8/3
(b) Update1: μ1 = 1.5 andμ2 = 3 .
3. Perform complete linkage on the following similarity graph. Note that the similarity of all edges that aren’t present is 0! Also note that sim(f,g) = 6, sim(g,h) = 11 and sim(f,i) = 8. Recall that in case of a tie always pick the cluster with the smallest ID and then merge it with the cluster that has the smallest ID among the ties. The smallest ID here is given by the alphabetical order. E.g., say you have S1 = {a, c}, S2 = {b,f}, S3 = {d,h} with sim(S1,S2) = 4, sim(S1,S3) = 5 and sim(S2,S3) = 5. So we have a tie here: dowemergeS1 withS3 orS2 andS3? TheIDofS1 isa,theIDofS2 isbandtheIDofS3 isd. So we pick S1 and then we merge it with the set having the smallest ID among all ties. In this case there is only S3. So we merge S1 and S3.
Here is the graph, good luck!
Solution:
• Round 1:
b1 10f h 2d
61185 7i
g
b1 10f h 2d
a43 2
9e c
a43 2
9e c
1
61185 7i
g
• Round 2:
b1 10f h 2d
a43 2
9e c
61185 7i
g
2
• Round 3:
b1 10f h 2d
61185 7i
g
• Round 4:
Note that an edge that is not present has a value of 0. sim({d, f }, {i}) = 0 for complete linkage. The same holds for sim({c, e}, {g}), sim({d, f }, {g, h}), sim({h, g}, {i}) and for all other edges until we reach the edge between a and b.
• Round 5:
• Round 6:
• Round 7:
• Round 8:
b1 2d
a 43 2
9e c
b1 2d
a 43 2
9e c
b1 2d
a 43 2
9e c
b1 2d
a 43 2
9e c
3
10f h 611 8 5
7i g
10f h 611 8 5
7i g
10f h 611 8 5
7i g
10f h 611 8 5
7i g
a43 2
9e c
b1 10f h 2d
a43 2
9e c
61185 7i
g
4