K-средние полезны и эффективны во многих контекстах машинного обучения, но имеют некоторые явные недостатки.
Преимущества k-средних
Относительно просто реализовать.
Масштабируется до больших наборов данных.
Всегда сходится.
Позволяет осуществлять теплый запуск положений центроидов.
Плавно адаптируется к новым примерам.
Может быть обобщено на кластеры разных форм и размеров, например эллиптические кластеры.
Обобщение k-средних
Простая реализация k-средних может привести к проблемам с кластерами разной плотности и размера. В левой части рисунка 1 показаны кластеры, которые мы ожидаем увидеть, а в правой части показаны кластеры, предложенные k-средними.
Для повышения производительности на несбалансированных кластерах, подобных показанным на рисунке 1, вы можете обобщить, то есть адаптировать, k-средние. На рисунке 2 показаны три разных набора данных, сгруппированных с двумя разными обобщениями. Первый набор данных показывает k-средние без обобщения, а второй и третий допускают разную ширину кластеров.
В этом курсе не рассматривается, как обобщать k-средние, но заинтересованным следует посмотреть «Кластеризация – модели гауссовой смеси k-средних » Карлоса Гестрина из Университета Карнеги-Меллона.
Недостатки k-средних
\(k\) необходимо выбирать вручную.
Результаты зависят от начальных значений.
Для низкого \(k\)вы можете смягчить эту зависимость, запустив k-means несколько раз с разными начальными значениями и выбрав лучший результат. По мере увеличения \(k\)вам понадобится засев k-средних , чтобы выбрать лучшие начальные центроиды. Полное обсуждение засева k-средних см. в «Сравнительном исследовании эффективных методов инициализации для алгоритма кластеризации K-средних», автор М. Эмре Селеби. , Хасан А. Кинграви и Патрисио А. Вела.
Сложность кластеризации данных разного размера и плотности без обобщения.
Сложность кластеризации выбросов.
Центроиды можно перетаскивать за выбросы, или выбросы могут получить собственный кластер вместо того, чтобы игнорироваться. Перед кластеризацией рассмотрите возможность удаления или обрезки выбросов.
Сложность масштабирования с учетом количества измерений.
По мере увеличения количества измерений в данных мера сходства, основанная на расстоянии, сходится к постоянному значению между любыми данными примерами. Уменьшите размерность либо с помощью PCA для данных объектов, либо с помощью спектральной кластеризации для изменения алгоритма кластеризации.
Проклятие размерности и спектральная кластеризация
Обратите внимание, что на этих трех графиках по мере увеличения размеров стандартное отклонение расстояния между примерами уменьшается по сравнению со средним расстоянием между примерами. Эта конвергенция означает, что k-средние становятся менее эффективными при различении примеров по мере увеличения размерности данных. Это называется проклятием размерности .
Этого снижения производительности можно избежать с помощью спектральной кластеризации , которая добавляет в алгоритм этапы предварительной кластеризации. Чтобы выполнить спектральную кластеризацию:
- Уменьшите размерность данных объектов с помощью PCA.
- Спроецируйте все точки данных в подпространство более низкой размерности.
- Кластеризируйте данные в этом подпространстве, используя выбранный вами алгоритм.
См. Учебное пособие по спектральной кластеризации Ульрики фон Люксбург для получения дополнительной информации о спектральной кластеризации.