Please post your solutions to the Nov 30 In-Class Exercise to this thread.

Best,

Chris

Our initial forests are the three vectors (1,2,3), (4,5,6), (5,6,7)

And we want the k=2 most important clusters

We will cycle through each pairs of the trees and compute the square euclidean distance.

The pairs are as follows

((1,2,3), (4,5,6)) ((1,2,3), (5,6,7)) ((4,5,6), (5,6,7))

The square euclidean distances are 27, 48, and 3

Pairs ((4,5,6), (5,6,7)) are nearest.

We delete these two trees from the forest. Let E' = (4.5, 5.5, 6.5).

We make a new tree T' with root label E' and subtrees (4,5,6) and (5,6,7)

Our new forest have two trees: (1,2,3) and (4.5, 5.5, 6.5)

We have exactly 2 trees in the forest, which

is equal to k. Our output is (1,2,3) and (4.5, 5.5, 6.5)

a = (1,2,3) , b = (4,5,6), c = (5, 6, 7)

d_ab = 3^2 + 3^2 + 3^ 2 = 27

d_bc = 1^2 + 1^2 + 1^2 = 3

d_ac = 4^2 + 4^2 + 4^2 = 48

nearest distance = d_bc

so cluster1:

(4,5,6) , (5,6,7)

cluster 2:

(1,2,3)

T1 = (1,2,3), T2 = (4,5,6), T3 = (5,6,7)

T4 = T2 - T1 = ((4-1)^2, (5-2)^2, (6-3)^2) = (3^2,3^2,3^2) = (9,9,9)

Now we have 2 trees in our forest, T4 and T3, where T4 has subtrees T1 and T2, T3 doesn't have any subtrees.

The 2 clusters we output are from T4 and T3 which are (9,9,9) and (5,6,7)

initial = (1,2,3)(4,5,6)(5,6,7) The closest pair of trees is (4,5,6)(5,6,7) because the euclidean distance is the smallest so we delete both from the forest Add (4+5/2, 5+6/2, 6+7/2) = (4.5,5.5,6.5) tree to the forest (1,2,3)(4.5,5.5,6.5) and stop because we have 2 clusters to output in the forest

Forest: {(1,2,3), (4,5,6), (5,6,7)}

Pair 1: {(1,2,3), (4,5,6)} Euclidean distance sum = 9 + 9 + 9 = 27 Pair 2: {(1,2,3), (5,6,7)} Euclidean distance sum = 16 + 16 + 16 = 48 Pair 3: {(4,5,6), (5,6,7)} Euclidean distance sum = 1 + 1 + 1 = 3

Pair 3 is the closest to each other, so remove those two trees from the forest Take the average of those values and make a new tree T' = (4.5, 5.5, 6.5)

Add T' to the forest Only two trees in the forest now Output is {(1,2,3), (4.5, 5.5, 6.5)}

Let A = (1,2,3), B = (4,5,6), C = (5,6,7)

K = 2

Compute square euclidean distances for (A, B), (A, C), (B, C)

The value for the first pair is (4 - 1)^2 + (5 - 2)^2 + (6 - 3)^2 = 27

Second pair is (5 - 1)^2 + (6 - 2)^2 + (7 - 3)^2 = 48

Third pair is (5 - 4)^2 + (6 - 5)^2 + (7 - 6)^2 = 3

We delete B and C because it's the nearest.

Let E' = (4.5, 5.5, 6.5)

The new tree has the root E'and subtrees of A and C

The new forest has two trees: A and E'

Since K = 2 the program terminates and outputs the forest.

Initial: (1,2,3), (4,5,6), (5,6,7) Possible Pairs: [(1,2,3), (4,5,6)], [(1,2,3), (5,6,7)], [(4,5,6), (5,6,7)] Euclidean Distance Pair: 27, 48, 3 Chosen Pair: [(4,5,6), (5,6,7)] Remove Pairs from Forest Find E': [(4+5)/2, (5+6)/2, (6+7)/2] = (4.5, 5.5, 6.5) Output Clusters: (1,2,3), (4.5, 5.5, 6.5)

Initial: a = (1,2,3), b = (4,5,6), c = (5,6,7) Distances: [a, b] = 27, [b, c] = 3, [a, c] = 48 Closest: [b, c] Output: [(1,2,3), (4.5,5.5,6.5)]