k-means++

Алгоритм:

1. Выбор первого центроида: Случайно выбирается одна точка из данных как первый центроид.
2. Выбор последующих центроидов:

• Для каждой точки данных вычисляется расстояние до ближайшего уже выбранного центроида.
• Вычисляется вероятность выбора каждой точки как следующего центроида, которая пропорциональна квадрату расстояния до ближайшего центроида:
  $$P(x) = \frac{D(x)^2}{\sum_{i} D(x_i)^2}$$
  где D(x) — расстояние точки x до ближайшего центроида.

3. Повторение: Выбираем k центроидов, используя вышеописанную вероятность.
4. После выбора k центроидов запускается обычный алгоритм k-means.
   Почему это работает:

• Выбор точек, которые находятся далеко друг от друга, даёт более “умное” начальное разбиение, что ускоряет сходимость и улучшает итоговую кластеризацию.
• Это снижает риск выбора плохих начальных центроидов, которые могли бы привести к локальному минимуму.