Как упоминалось ранее, многие алгоритмы кластеризации не масштабируются для наборов данных, используемых в машинном обучении, которые часто имеют миллионы примеров. Например, алгоритмы агломеративной или разделительной иерархической кластеризации рассматривают все пары точек и имеют сложность и соответственно.
В этом курсе основное внимание уделяется k-средним, поскольку они масштабируются как , где — это количество кластеров, выбранных пользователем. Этот алгоритм группирует точки в кластеры , минимизируя расстояния между каждой точкой и центроидом ее кластера (см. рисунок 1).
В результате k-средние эффективно рассматривают данные как состоящие из ряда примерно круговых распределений и пытаются найти кластеры, соответствующие этим распределениям. Но реальные данные содержат выбросы и кластеры на основе плотности и могут не соответствовать предположениям, лежащим в основе k-средних.
алгоритм кластеризации k-средних
Алгоритм состоит из следующих шагов:
Укажите первоначальное предположение для , которое можно будет изменить позже. В этом примере мы выбираем .
Случайным образом выберите центроиды .
Рисунок 1: k-средние при инициализации. Назначьте каждую точку ближайшему центроиду, чтобы получить начальные кластеры .
Рисунок 2: Начальные кластеры. Для каждого кластера вычислите новый центроид, взяв среднее положение всех точек в кластере. Стрелки на рисунке 4 показывают изменение положения центроидов.
Рисунок 3: Пересчитанные центроиды. Переназначьте каждую точку ближайшему новому центроиду.
Рисунок 4: Кластеры после переназначения. Повторяйте шаги 4 и 5, пересчитывая центроиды и членство в кластере, пока точки не перестанут изменять кластеры. В случае больших наборов данных вы можете остановить алгоритм до сходимости по другим критериям.
Поскольку позиции центроидов изначально выбираются случайным образом, k-средние могут возвращать существенно разные результаты при последующих запусках. Чтобы решить эту проблему, запустите k-means несколько раз и выберите результат с метриками наилучшего качества. (Показатели качества мы опишем позже в этом курсе.) Вам понадобится расширенная версия k-средних, чтобы выбрать лучшие начальные положения центроидов.
Хотя глубокое понимание математики не требуется, для любопытных: k-средние — это частный случай алгоритма максимизации ожидания . См. конспекты лекций по этой теме от UPenn.