逐步合并

本课属于 Coddy Machine Learning 学习旅程的“无监督学习”单元。第 16 课，共 51 课。

这一章会为你的数据构建一棵家族树，然后把它切分成几组。下面是 10 种运动球，按大小和重量排列：

一张包含 10 种运动球的树状图。高尔夫球、网球和棒球等小球在一侧较低的位置汇合，足球和篮球等大球在另一侧汇合，一条虚线将这棵树切分成两组

这棵树从底部向上生长。从每个点各自独立开始，合并距离最近的两个组，然后重复这个过程：

河边有五顶帐篷，分别位于 2、7、15、19 和 33 米处，分五行绘制。第 1 步合并 15 和 19，第 2 步合并 2 和 7，第 3 步连接这两个组，第 4 步加入 33

两组之间的差距就是它们均值之间的差距。以列表的形式合并：

groups = [[2], [7], [15, 19], [33]]
groups[0] = groups[0] + groups[1]  # 合并列表
groups.pop(1)  # 移除 [7]，它现在位于第 0 组
print(groups)

这会打印 [[2, 7], [15, 19], [33]]。一次次合并，这就是凝聚聚类。

挑战

中等

各个家庭把沙滩伞挨着摆放。通过合并 spots 中的 10 把伞，将它们分组，直到剩下 wanted 组。closest_pair(groups) 返回距离最近的两组的位置 i、j。

先把每把伞单独放成一组。
当组数多于 wanted 时：打印合并信息，合并这两组，移除第二组。
打印剩下的各组。

如果有其他伞，并且 wanted 为 3：

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

亲手试试

import numpy as np

# 10 把沙滩伞的位置，以到救生员瞭望塔的距离表示，单位为米
spots = [2, 9, 11, 31, 45, 46, 69, 74, 92, 96]


# 返回 i、j（i < j）：平均值最接近的两组的位置
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())

# 在下方编写你的代码