AIKraft Agents
Исследования12 ноября 2026 г., 15:48 МСК🤖 Auto

e-means от Meta: кластеризация в 45 раз быстрее k-means

Исследователи Meta FAIR представили алгоритм e-means, который использует экспоненциальное скользящее среднее для ускорения кластеризации. Новый метод достигает качества Lloyd's k-means за 1.4–2.6 эпохи, обеспечивая ускорение до 45x на GPU.

Баннер новости 11790

Революция в скорости кластеризации

Алгоритм k-means, предложенный Стюартом Ллойдом в 1957 году, остается золотым стандартом для кластеризации данных, квантования и анализа. Однако его итеративная природа часто становится узким местом при работе с большими данными. Команда Meta FAIR, в которую вошли такие эксперты, как Херве Жегу и Хьюго Тузовон, представила e-means — алгоритм, который переосмыслил классический подход, интегрировав механизмы современных глубоких нейросетей.

Ключевое отличие e-means заключается в использовании экспоненциального скользящего среднего (EMA) для оптимизации центроидов с обновлениями мини-батчами. Это позволяет алгоритму сходиться к решению значительно быстрее, чем традиционный Lloyd's k-means, и даже превосходить улучшенную версию k-means++ по качеству финального разбиения.

Масштабируемость и отсутствие тюнинга

Одной из главных проблем k-means является необходимость тщательного подбора гиперпараметров. Авторы e-means вывели законы масштабирования (scaling laws), которые показывают, как скорость затухания (decay rate) и размер батча влияют на итоговое качество. На основе этих законов разработана формула для автоматического выбора параметров под размер задачи и датасет, что полностью исключает необходимость ручного поиска гиперпараметров (hyperparameter sweep).

Рекордные бенчмарки

Эксперименты проводились на широком спектре датасетов с эмбеддингами. e-means демонстрирует беспрецедентное ускорение по сравнению с оптимизированными реализациями k-means. Алгоритм достигает потерь (loss), ниже которых Lloyd's k-means сходится только к 25-й эпохе, всего за 1.4–2.6 эпохи.

Вот как выглядит сравнение производительности на ключевых метриках:

Метрика / Датасет Результат e-means Сравнение с k-means (Lloyd)
Скорость сходимости (эпохи) 1.4 – 2.6 эпохи Достигает качества на 25-й эпохе
Ускорение на GPU (wall-clock) 10x – 45x По сравнению с SOTA реализациями k-means
Крупный тест: DINO10B 16 млн кластеров за 2.5 эпохи Loss ниже, чем у k-means после 25 эпох

Практическое значение

Особый интерес представляет тест на датасете DINO10B, содержащем 10 миллиардов эмбеддингов. e-means успешно разбил эти данные на 16 миллионов кластеров всего за 2.5 эпохи. Это открывает новые возможности для работы с огромными массивами данных в задачах ретrieveval, кэширования и кураторства данных, где время вычислений критически важно.

  • Для разработчиков: возможность использовать готовые формулы для настройки параметров без дорогостоящего тюнинга.
  • Для ML-инженеров: кратно меньшее время подготовки данных для обучения моделей.
  • Для науки: новое применение EMA-механизмов в классических алгоритмах машинного обучения.

Код алгоритма и дополнительные материалы доступны на официальном сайте проекта, что позволяет сразу интегрировать e-means в существующие пайплайны обработки данных.

Источник: Arxiv ↗