Понятие кластера и центроида

Зачем это в ЕГЭ.
Задание 27 в ЕГЭ по информатике проверяет умение работать с алгоритмами кластеризации и вычисления центроидов. Это задача высокого уровня сложности, оценивается в 2 первичных балла. Встречается в каждом третьем варианте ФИПИ.

Главная идея.
Кластеризация — это группировка объектов по схожести. Центроид — это «центр тяжести» кластера, вычисляемый как среднее значение координат всех объектов в кластере. Основная задача — правильно распределить объекты по кластерам и вычислить их центроиды.

Алгоритм (чеклист).
1. Запишите координаты всех объектов.
2. Выберите начальные центроиды (например, первые два объекта).
3. Распределите объекты по кластерам, основываясь на минимальном расстоянии до центроидов.
4. Пересчитайте центроиды как среднее значение координат объектов в каждом кластере.
5. Повторяйте шаги 3-4, пока центроиды не перестанут изменяться.
6. Проверьте корректность распределения объектов по кластерам.

Опоры (кратко).
- Формула расстояния между точками: $d = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}$.
- Формула центроида: $C = \left(\frac{\sum x_i}{n}, \frac{\sum y_i}{n}\right)$.
- Количество кластеров обычно задано в условии задачи.

Пример 1 (базовый подтип)
Даны точки: A(1, 2), B(2, 3), C(4, 5), D(5, 6). Разделите их на два кластера.

Шаг 1. Выберем начальные центроиды: A(1, 2) и B(2, 3).
Шаг 2. Вычислим расстояния от каждой точки до центроидов:
- A до A: 0, A до B: $\sqrt{2}$.
- B до A: $\sqrt{2}$, B до B: 0.
- C до A: $\sqrt{18}$, C до B: $\sqrt{8}$.
- D до A: $\sqrt{32}$, D до B: $\sqrt{18}$.
Шаг 3. Распределим точки: Кластер 1: A, B. Кластер 2: C, D.
Шаг 4. Пересчитаем центроиды:
Кластер 1: $\left(\frac{1+2}{2}, \frac{2+3}{2}\right) = (1.5, 2.5)$.
Кластер 2: $\left(\frac{4+5}{2}, \frac{5+6}{2}\right) = (4.5, 5.5)$.
Шаг 5. Повторяем шаги 2-4, пока центроиды не стабилизируются.

Пример 2 (сложный подтип)
Даны точки: A(1, 1), B(2, 2), C(3, 3), D(4, 4). Разделите их на три кластера.

Шаг 1. Выберем начальные центроиды: A(1, 1), B(2, 2), C(3, 3).
Шаг 2. Вычислим расстояния от каждой точки до центроидов:
- A до A: 0, A до B: $\sqrt{2}$, A до C: $\sqrt{8}$.
- B до A: $\sqrt{2}$, B до B: 0, B до C: $\sqrt{2}$.
- C до A: $\sqrt{8}$, C до B: $\sqrt{2}$, C до C: 0.
- D до A: $\sqrt{18}$, D до B: $\sqrt{8}$, D до C: $\sqrt{2}$.
Шаг 3. Распределим точки: Кластер 1: A. Кластер 2: B. Кластер 3: C, D.
Шаг 4. Пересчитаем центроиды:
Кластер 1: (1, 1).
Кластер 2: (2, 2).
Кластер 3: $\left(\frac{3+4}{2}, \frac{3+4}{2}\right) = (3.5, 3.5)$.
Шаг 5. Повторяем шаги 2-4, пока центроиды не стабилизируются.

Типичные ошибки.
1. Неправильный выбор начальных центроидов. Это приводит к некорректному распределению объектов.
2. Ошибка в вычислении расстояний. Неправильно применяется формула расстояния между точками.
3. Неправильный пересчёт центроидов. Забывают разделить сумму координат на количество объектов.
4. Недостаточное количество итераций. Прекращают алгоритм до стабилизации центроидов.
5. Путаница в количестве кластеров. Не учитывают условие задачи.

Дальше.
Потренируйтесь на задачах с большим количеством точек и кластеров.