Пошаговое объединение

Часть раздела Обучение без учителя путешествия по Machine Learning на Coddy. Урок 16 из 51.

В этой главе мы построим генеалогическое дерево ваших данных, а затем разделим его на группы. Вот десять спортивных мячей, упорядоченных по размеру и весу:

Древовидная диаграмма десяти спортивных мячей. Маленькие мячи, такие как мяч для гольфа, теннисный мяч и бейсбольный мяч, объединяются внизу с одной стороны, большие мячи, такие как футбольный и баскетбольный, — с другой, а пунктирная линия разделяет дерево на эти две группы

Дерево растёт снизу вверх. Начни с того, что каждая точка находится отдельно, объедини две ближайшие группы и повторяй:

Пять палаток вдоль реки на отметках 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]]. Слияние за слиянием — это агломеративная кластеризация.

Задание

Средне

Семьи ставят пляжные зонтики близко друг к другу. Объединяй 10 зонтиков из spots, пока не останется 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())

# Напишите свой код ниже