Как упоминалось ранее, многие алгоритмы кластеризации не масштабируются для наборов данных, используемых в машинном обучении, которые часто имеют миллионы примеров. Например, алгоритмы агломеративной или разделительной иерархической кластеризации рассматривают все пары точек и имеют сложность \(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.