Merging Step by Step

Part of the Unsupervised Learning section of Coddy's Machine Learning journey. Lesson 16 of 51.

This chapter grows a family tree of your data, then cuts it into groups. Here are ten sports balls, by size and weight:

A tree diagram over ten sports balls. Small balls like golf, tennis and baseball join low down on one side, big balls like football and basketball on the other, and a dashed line cuts the tree into these two groups

The tree grows from the bottom up. Start with every point alone, merge the two closest groups, and repeat:

Five tents along a river at 2, 7, 15, 19 and 33 meters, drawn in five rows. Step 1 merges 15 and 19, step 2 merges 2 and 7, step 3 joins those two groups, step 4 adds 33

The gap between two groups is the gap between their means. A merge, as lists:

groups = [[2], [7], [15, 19], [33]]
groups[0] = groups[0] + groups[1]  # join the lists
groups.pop(1)  # remove [7], now in group 0
print(groups)

This prints [[2, 7], [15, 19], [33]]. Merge after merge, that is agglomerative clustering.

Challenge

Medium

Families plant their beach umbrellas close together. Group the 10 umbrellas in spots by merging, until wanted groups are left. closest_pair(groups) returns the positions i, j of the two closest groups.

Start with each umbrella alone, in a list of one.
While there are more groups than wanted: print the merge, join the pair, remove the second.
Print the groups left.

For other umbrellas and wanted 3:

Merge [33] and [35]
Merge [30] and [33, 35]
Merge [3] and [8]
3 groups: [[3, 8], [30, 33, 35], [70]]

Try it yourself

import numpy as np

# Where 10 beach umbrellas stand, in meters from the lifeguard tower
spots = [2, 9, 11, 31, 45, 46, 69, 74, 92, 96]


# Returns i, j (i < j): the positions of the two groups whose means are closest
def closest_pair(groups):
    best_i, best_j = 0, 1
    best_gap = abs(np.mean(groups[0]) - np.mean(groups[1]))
    for i in range(len(groups)):
        for j in range(i + 1, len(groups)):
            gap = abs(np.mean(groups[i]) - np.mean(groups[j]))
            if gap < best_gap:
                best_i, best_j, best_gap = i, j, gap
    return best_i, best_j


wanted = int(input())

# Write your code below