Центр кластера

Какую точку кластера считать его центром?

Центр — одна из точек самого кластера: та, у которой сумма расстояний до остальных точек наименьшая. Найти её можно перебором — проверить каждую точку как кандидата. Кандидат — точка, которую сейчас проверяем: «а что, если центр — она?»

Возьмём кластер из пяти точек на прямой: (0; 0), (1; 0), (2; 0), (3; 0) и (100; 0). На одной горизонтали расстояние — модуль разности x. Для (0; 0) сумма до остальных 1 + 2 + 3 + 100 = 106, для (1; 0) — 1 + 1 + 2 + 99 = 103. Пройди так всех пятерых:

Центр — (2; 0) с суммой 102. У соседней (3; 0) сумма 103, у далёкой (100; 0) — 394.

Как записать перебор кандидатов программой?

Двумя вложенными циклами: внешний перебирает кандидатов, внутренний складывает расстояния от кандидата до всех точек кластера. Лучшую сумму и её кандидата запоминают.

from math import dist  def center_sum(cluster):    best_point = cluster[0]    best_sum = float("inf")    for candidate in cluster:        total = 0.0        for point in cluster:            total += dist(candidate, point)        if total < best_sum:            best_sum = total            best_point = candidate    return best_point  cluster = [(0, 0), (1, 0), (2, 0), (3, 0), (100, 0)]print(center_sum(cluster))

• float("inf") — бесконечность: любая настоящая сумма меньше, поэтому первый кандидат сразу становится лучшим.
• total = 0.0 стоит внутри внешнего цикла: у каждого кандидата своя сумма. Поставь её до цикла — и суммы разных кандидатов сложатся вместе.
• total += … — сокращённое присваивание, то же, что total = total + ….
• Сравнивать с лучшей суммой можно только после внутреннего цикла, когда сумма кандидата посчитана целиком.

Функция находит центр наверняка: она проверяет всех кандидатов и для каждого считает ровно ту величину, что стоит в условии. Угадывать центр по рисунку не нужно.

Нельзя ли вместо перебора просто взять среднюю точку кластера?

Нет: средняя точка обычно не совпадает ни с одной точкой кластера, и даже ближайшая к ней точка не обязательно центр. Средняя точка наших пяти — x̄ = (0 + 1 + 2 + 3 + 100) / 5 = 21,2, ȳ = 0: далёкая точка (100; 0) сильно её смещает. Ближайшая к (21,2; 0) точка кластера — (3; 0). Проверим её сумму:

mean = (sum(p[0] for p in cluster) / 5, 0)print(mean) nearest = cluster[0]for p in cluster:    if dist(p, mean) < dist(nearest, mean):        nearest = p best = center_sum(cluster)print(nearest, sum(dist(nearest, p) for p in cluster))print(best, sum(dist(best, p) for p in cluster))

У (3; 0) сумма 103, у настоящего центра (2; 0) — 102. Один пример опровергает сразу оба соблазнительных правила: и «центр — средняя точка», и «центр — ближайшая к средней».

А если ради скорости убрать корень и сравнивать суммы квадратов расстояний?

Нельзя: сумма квадратов — другая величина, и её минимум бывает у другой точки. Сравним кандидатов 2 и 3 из нашего кластера:

for c in [(2, 0), (3, 0)]:    plain = sum(dist(c, p) for p in cluster)    squares = sum(dist(c, p) ** 2 for p in cluster)    print(c, plain, squares)

По сумме расстояний лучше кандидат 2, по сумме квадратов — 3: 2² + 1² + 0² + 1² + 98² = 9610, а 3² + 2² + 1² + 0² + 97² = 9423. Квадрат сильнее раздувает большие расстояния, и сократить одно большое выгоднее, чем несколько маленьких.

Сравнивать квадраты можно, когда сравниваешь одно расстояние с порогом (подтема 1), но не суммы. Центр по сумме квадратов встречается в редких задачах — он разобран в дополнительном уроке.

Что меняется, если в условии своя формула расстояния?

Только функция расстояния — перебор кандидатов остаётся прежним. Добавим в center_sum параметр d — функцию расстояния; по умолчанию это обычная dist:

def center_sum(cluster, d=dist):    best_point = cluster[0]    best_sum = float("inf")    for candidate in cluster:        total = 0.0        for point in cluster:            total += d(candidate, point)        if total < best_sum:            best_sum = total            best_point = candidate    return best_point

Например, манхэттенское расстояние d(A, B) = |x₁ − x₂| + |y₁ − y₂| — длина пути, если ходить только по горизонтали и вертикали. Для (1; 2) и (4; 6) это 3 + 4 = 7, а не 5. abs — модуль числа:

def manhattan(a, b):    return abs(a[0] - b[0]) + abs(a[1] - b[1])  group = [(0, 3), (3, 0), (1, 6), (1, 0)]print(center_sum(group), center_sum(group, manhattan))

Для одних и тех же четырёх точек евклидов центр — (0; 3), а манхэттенский — (1; 0): формула расстояния меняет ответ.

Так устроена и задача темы: «расстояние» между частицами — модуль разности их энергий |E₁ − E₂|, а координаты в выборе центра не участвуют. Функции read_particles, energy и energy_groups — из подтем 1 и 2:

def energy_gap(a, b):    return abs(energy(a) - energy(b))  particles = read_particles("27-4.txt")groups = energy_groups(particles, [3.5, 7, 10.5])for g in groups:    c = center_sum(g, energy_gap)    print(len(g), c[5], round(energy(c), 3))

У центров четырёх кластеров энергии 2,028, 5,362, 8,964 и 12,503. Q₂ задачи темы — наибольшая из них; ответ соберём в подтеме 5.

Как найти центр, если точки неравноценны — например, деревья разной высоты?

Каждое расстояние умножают на вес той точки, до которой его считают; в остальном перебор прежний. Такая задача есть в подборках: деревья свозят к точке сбора, «сложность» доставки дерева — расстояние, умноженное на его высоту, а точка сбора — дерево с наименьшей суммарной сложностью.

Пять деревьев у дороги: (0; 0) высотой 2, (1; 0), (2; 0) и (3; 0) высотой 1 и (8; 0) высотой 4. Сравним обычную и взвешенную суммы каждого кандидата:

Без весов центр — (2; 0), с весами — (3; 0): высокое дерево (8; 0) тянет точку сбора к себе. В программе меняется одна строка — к расстоянию добавляется множитель:

trees = [(0, 0, 2), (1, 0, 1), (2, 0, 1), (3, 0, 1), (8, 0, 4)]  def center_weighted(trees):    best, best_sum = None, float("inf")    for c in trees:        total = 0.0        for t in trees:            total += dist(c[:2], t[:2]) * t[2]        if total < best_sum:            best, best_sum = c, total    return best, best_sum  print(center_weighted(trees))

Множитель — t[2], высота дерева, которое везут, а не кандидата c. Перепутать их — значит решить другую задачу.

• Центродна из точек кластера, наименьшая сумма расстояний
• Переборвнешний цикл — кандидаты, внутренний — сумма
• totalобнуляется для каждого кандидата
• Средняя точкане центр; ближайшая к ней — тоже не обязательно
• Своя формуламеняется только функция d, перебор тот же
• Весрасстояние × вес точки, до которой считаем