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