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