Что такое кластеризация k-средних?

Как упоминалось ранее, многие алгоритмы кластеризации не масштабируются для наборов данных, используемых в машинном обучении, которые часто имеют миллионы примеров. Например, алгоритмы агломеративной или разделительной иерархической кластеризации рассматривают все пары точек и имеют сложность O(n2log(n)) и O(n2)соответственно.

В этом курсе основное внимание уделяется k-средним, поскольку они масштабируются как O(nk), где k— это количество кластеров, выбранных пользователем. Этот алгоритм группирует точки в кластерыk , минимизируя расстояния между каждой точкой и центроидом ее кластера (см. рисунок 1).

В результате k-средние эффективно рассматривают данные как состоящие из ряда примерно круговых распределений и пытаются найти кластеры, соответствующие этим распределениям. Но реальные данные содержат выбросы и кластеры на основе плотности и могут не соответствовать предположениям, лежащим в основе k-средних.

алгоритм кластеризации k-средних

Алгоритм состоит из следующих шагов:

  1. Укажите первоначальное предположение для k, которое можно будет изменить позже. В этом примере мы выбираем k=3.

  2. Случайным образом выберите центроиды k .

    График k-средних при инициализации, показывающий три случайно выбранных центроида
    Рисунок 1: k-средние при инициализации.

  3. Назначьте каждую точку ближайшему центроиду, чтобы получить начальные кластеры k .

    Каждой точке присвоен цвет ближайшего к ней центроида.
    Рисунок 2: Начальные кластеры.

  4. Для каждого кластера вычислите новый центроид, взяв среднее положение всех точек в кластере. Стрелки на рисунке 4 показывают изменение положения центроидов.

    Показывает новые центроиды ближе к центру каждого цветного кластера.
    Рисунок 3: Пересчитанные центроиды.

  5. Переназначьте каждую точку ближайшему новому центроиду.

    Скорректированные кластеры после переназначения на новые центроиды.
    Рисунок 4: Кластеры после переназначения.

  6. Повторяйте шаги 4 и 5, пересчитывая центроиды и членство в кластере, пока точки не перестанут изменять кластеры. В случае больших наборов данных вы можете остановить алгоритм до сходимости по другим критериям.

Поскольку позиции центроидов изначально выбираются случайным образом, k-средние могут возвращать существенно разные результаты при последующих запусках. Чтобы решить эту проблему, запустите k-means несколько раз и выберите результат с метриками наилучшего качества. (Показатели качества мы опишем позже в этом курсе.) Вам понадобится расширенная версия k-средних, чтобы выбрать лучшие начальные положения центроидов.

Хотя глубокое понимание математики не требуется, для любопытных: k-средние — это частный случай алгоритма максимизации ожидания . См. конспекты лекций по этой теме от UPenn.