Как понять недостатки К-средних

K-means - широко используемый метод в кластерном анализе. В моем понимании, этот метод НЕ требует ЛЮБЫХ предположений, т. Е. Дает мне набор данных и заранее определенное количество кластеров, k, и я просто применяю этот алгоритм, который минимизирует сумму квадратов ошибок (SSE), в квадрате внутри кластера ошибка.

Таким образом, k-means - это, по сути, проблема оптимизации.

Я прочитал некоторые материалы о недостатках k-средних. Большинство из них говорят, что:

• k-означает, что дисперсия распределения каждого атрибута (переменной) является сферической;
• все переменные имеют одинаковую дисперсию;
• предыдущая вероятность для всех k кластеров одинакова, т. е. каждый кластер имеет примерно одинаковое количество наблюдений;

Если какое-либо из этих 3 допущений будет нарушено, то k-means потерпит неудачу.

Я не мог понять логику этого утверждения. Я думаю, что метод k-средних по существу не делает никаких предположений, он просто минимизирует SSE, поэтому я не вижу связи между минимизацией SSE и этими 3 «предположениями».

Хотя мне здесь очень нравится ответ Дэвида Робинсона, здесь приведена дополнительная критика k-средних.

Кластеризация некластеризованных данных

Запустите k-means для единых данных, и вы все равно получите кластеры! Он не сообщает вам, когда данные просто не кластеризуются, и может таким образом завести ваше исследование в тупик.

Чувствителен к масштабу

Масштабирование ваших наборов данных полностью изменит результаты. Хотя это само по себе неплохо, не очень важно осознавать, что вам нужно уделять дополнительное внимание масштабированию ваших данных . Коэффициенты масштабирования - это дополнительные скрытых параметров в k-означает, что «по умолчанию» равно 1, и, следовательно, их легко пропустить, но они оказывают значительное влияние (но, конечно, это относится и ко многим другим алгоритмам).$d$

Вероятно, это то, что вы назвали «все переменные имеют одинаковую дисперсию». Кроме того, в идеале, вы также можете рассмотреть нелинейное масштабирование, когда это уместно.

Также имейте в виду, что масштабирование каждой оси для получения единичной дисперсии - это только эвристика . Это не гарантирует, что k-means работает. Масштабирование зависит от значения вашего набора данных. И если у вас более одного кластера, вы бы хотели, чтобы каждый кластер (независимо) имел одинаковую дисперсию в каждой переменной.

Вот классический контрпример из наборов данных, которые k-means не может кластеризовать. Обе оси находятся в каждом кластере, поэтому было бы достаточно сделать это в одном измерении. Но кластеры имеют различную дисперсию, и k-means расщепляет их некорректно.

Я не думаю, что этот контрпример для k-средних покрыт вашими пунктами:

• Все кластеры сферические (например, гауссовские).
• Все оси имеют одинаковое распределение и, следовательно, дисперсию.
• Оба кластера имеют 500 элементов каждый.

Тем не менее, k-средних по-прежнему плохо терпит неудачу (и становится еще хуже, если я увеличу дисперсию больше 0,5 для более крупного кластера) Но: это не алгоритм, который потерпел неудачу. Это предположения, которые не верны . K-means отлично работает, просто оптимизирует неправильный критерий.

Даже на совершенных наборах данных он может застрять в локальном минимуме

Ниже представлен лучший из 10 прогонов k-средних в классическом наборе данных A3. Это синтетический набор данных, разработанный для k-средних . 50 кластеров, каждая из которых имеет гауссову форму, достаточно хорошо разделены. Тем не менее, только с помощью k-средних ++ и 100 итераций я получил ожидаемый результат ... (для иллюстрации ниже приведены 10 итераций обычных k-средних).

В этом наборе данных вы быстро найдете много кластеров, где k-means не смог найти правильную структуру. Например, в правом нижнем углу кластер был разбит на три части. Но нет никакого способа, k-means собирается переместить один из этих центроидов в совершенно другое место набора данных - он пойман в ловушку локального минимума (и это уже был лучший из 10 запусков!)

И есть много таких локальных минимумов в этом наборе данных. Очень часто, когда вы получаете два образца из одного кластера, он застревает в минимуме, где этот кластер остается разделенным, и вместо этого объединяются два других кластера. Не всегда, но очень часто. Так что вам нужно много итераций, чтобы сделать удачный выбор. С 100 итерациями k-средних я все еще насчитал 6 ошибок, а с 1000 итерациями я сократил до 4 ошибок. K-означает ++, поскольку он взвешивает случайные выборки, работает намного лучше на этом наборе данных.

Средства сплошные

Хотя вы можете запустить k-means для двоичных данных (или однозначно закодированных категориальных данных), результаты больше не будут двоичными. Таким образом, вы получаете результат, но, возможно, вам не удастся его интерпретировать в конце, потому что он имеет другой тип данных, чем ваши исходные данные.

Скрытое предположение: SSE стоит минимизировать

По сути, это уже присутствует в ответе выше, хорошо продемонстрированном с помощью линейной регрессии. В некоторых случаях использование k-средних имеет смысл. Когда Ллойду пришлось декодировать сигналы PCM, он знал количество разных тонов, а наименьшая квадратная ошибка сводит к минимуму вероятность ошибок декодирования. И в цветовом квантовании изображения вы также минимизируете цветовую ошибку при уменьшении палитры. Но по вашим данным, является ли сумма квадратов отклонений значимым критерием для минимизации?

В приведенном контрпримере дисперсию не стоит минимизировать, поскольку она зависит от кластера. Вместо этого модель данных Гауссовой смеси должна соответствовать данным, как показано на рисунке ниже:

(Но это также не окончательный метод. Так же просто построить данные, которые не удовлетворяют предположениям о «смеси k гауссовых распределений», например, добавляя много фонового шума)

Слишком легко использовать плохо

В общем, слишком легко бросить k-средства в ваши данные и, тем не менее, получить результат (это довольно случайно, но вы этого не заметите). Я думаю, что было бы лучше иметь метод, который может потерпеть неудачу, если вы не поняли свои данные ...

К-значит как квантование

Если вам нужна теоретическая модель того, что делает k-means, рассмотрите ее как подход квантования , а не алгоритм кластеризации.

Цель k-средних - минимизация квадратичной ошибки - разумный выбор, если вы заменяете каждый объект ближайшим центроидом. (Это имеет гораздо меньше смысла, если вы проверяете исходные данные групп ИМХО.)

$k$

Это квантование, вероятно, очень похоже на пример линейной регрессии. Линейная регрессия находит лучшую линейную модель . И k-means находит (иногда) наилучшее сокращение до значений k многомерного набора данных. Где «лучший» - это наименьший квадрат ошибки.

ИМХО, k-means - это хороший алгоритм квантования (см. Первое изображение в этом посте - если вы хотите приблизить набор данных к двум точкам, это разумный выбор!). Если вы хотите выполнить кластерный анализ, как в структуре обнаружения, тогда k-means - не самый лучший выбор. Он имеет тенденцию к кластеризации, когда нет кластеров, и он не может распознавать различные структуры, которые вы часто видите в данных.

Fine print: все изображения были созданы с помощью ELKI . Данные были сгенерированы с использованием .xmlформата генерации данных, но они настолько просты, что ими не стоит делиться.

Какой замечательный вопрос - это шанс показать, как можно проверить недостатки и допущения любого статистического метода. А именно: составьте некоторые данные и попробуйте алгоритм на них!

Мы рассмотрим два ваших предположения и посмотрим, что происходит с алгоритмом k-средних, когда эти предположения нарушаются. Мы будем придерживаться двумерных данных, поскольку их легко визуализировать. (Благодаря проклятию размерности , добавление дополнительных измерений может сделать эти проблемы более серьезными, а не меньшими). Мы будем работать со статистическим языком программирования R: вы можете найти полный код здесь (и пост в форме блога здесь ).

Диверсия: квартет Анскомба

Сначала аналогия. Представьте, что кто-то утверждал следующее:

Я прочитал некоторый материал о недостатках линейной регрессии - что она ожидает линейную тенденцию, что остатки обычно распределены, и что нет никаких выбросов. Но все, что делает линейная регрессия - это минимизирует сумму квадратов ошибок (SSE) от предсказанной линии. Это проблема оптимизации, которая может быть решена независимо от формы кривой или распределения остатков. Таким образом, линейная регрессия не требует никаких предположений для работы.

Ну, да, линейная регрессия работает путем минимизации суммы квадратов невязок. Но это само по себе не является целью регрессии: мы пытаемся провести линию, которая служит надежным, непредвзятым предиктором y на основе x . Теорема Гаусса-Маркова говорит нам, что минимизация SSE достигает этой цели, но эта теорема основывается на некоторых очень специфических предположениях. Если эти предположения нарушены, вы все равно можете минимизировать SSE, но это может не сработатьчто-нибудь. Представьте себе, что вы говорите: «Вы водите автомобиль, нажимая на педаль: вождение - это, по сути,« процесс нажатия на педаль ». Педаль можно нажимать независимо от количества газа в баке. Поэтому, даже если бак пуст, вы все равно можете нажать на педаль и вести машину ».

Но говорить дешево. Давайте посмотрим на холодные, жесткие данные. Или на самом деле, выдуманные данные.

$R^2$

Можно сказать: «Линейная регрессия все еще работает в тех случаях, потому что она минимизирует сумму квадратов невязок». Но какая пиррова победа ! Линейная регрессия всегда будет рисовать линию, но если это бессмысленная линия, кого это волнует?

Итак, теперь мы видим, что то, что оптимизация может быть выполнена, не означает, что мы достигаем нашей цели. И мы видим, что составление данных и их визуализация - это хороший способ проверить предположения модели. Держитесь за эту интуицию, она нам понадобится через минуту.

Неправильное предположение: несферические данные

Вы утверждаете, что алгоритм k-средних будет отлично работать на несферических кластерах. Несферические кластеры, как ... эти?

Может быть, это не то, что вы ожидали, но это вполне разумный способ построения кластеров. Глядя на это изображение, мы, люди, сразу распознаем две естественные группы точек - их нельзя ошибиться. Итак, давайте посмотрим, как это делает k-means: назначения показаны в цвете, вмененные центры показаны в виде X.

Ну, это не правильно. К-значит пытался втиснуть квадратный колышек в круглое отверстие - пытаясь найти красивые центры с аккуратными сферами вокруг них - и это не удалось. Да, он по-прежнему сводит к минимуму сумму квадратов внутри кластера - но, как и в четвертом квартале Анскомба, это пиррова победа!

Вы можете сказать: «Это неверный пример ... ни один метод кластеризации не может правильно найти такие странные кластеры». Не правда! Попробуйте иерархическую кластеризацию с одной связью :

Успешно справился! Это связано с тем, что иерархическая кластеризация с одной связью делает правильные предположения для этого набора данных. (Есть целый другой класс ситуаций, когда он терпит неудачу).

Вы можете сказать: «Это единственный, крайний, патологический случай». Но это не так! Например, вы можете сделать внешнюю группу полукругом вместо круга, и вы увидите, что k-means по-прежнему работает ужасно (а иерархическая кластеризация по-прежнему хороша). Я мог бы легко придумать другие проблемные ситуации, и это только в двух измерениях. Когда вы кластеризуете 16-мерные данные, могут возникнуть различные виды патологий.

Наконец, я должен отметить, что k-means все еще можно восстановить! Если вы начнете с преобразования ваших данных в полярные координаты , кластеризация теперь работает:

Вот почему важно понимать предположения, лежащие в основе метода: он не просто сообщает вам, когда у метода есть недостатки, но и объясняет, как их исправить.

Неправильное предположение: неоднородные кластеры

Что если кластеры имеют неодинаковое количество точек - это также нарушает кластеризацию k-средних? Хорошо, рассмотрим этот набор кластеров размером 20, 100, 500. Я создал каждый из многомерного гауссиана:

Похоже, что k-means может найти эти кластеры, верно? Кажется, все сгруппировано в аккуратные и аккуратные группы. Итак, давайте попробуем k-means:

Уч. То, что произошло здесь, немного сложнее. В стремлении минимизировать сумму квадратов внутри кластера алгоритм k-средних дает больший «вес» более крупным кластерам. На практике это означает, что он счастлив позволить этому небольшому кластеру оказаться далеко от любого центра, в то время как он использует эти центры, чтобы «разделить» гораздо больший кластер.

Если вы немного поиграете с этими примерами ( код R здесь! ), Вы увидите, что вы можете создать гораздо больше сценариев, в которых k-means делает это смущающей ошибкой.

Вывод: нет бесплатного обеда

В математическом фольклоре есть очаровательная конструкция, формализованная Вулпертом и Макриди , которая называется «Теорема об отсутствии бесплатного обеда». Вероятно, это моя любимая теорема в философии машинного обучения, и я с удовольствием могу поднять ее (я упоминал, что мне нравится этот вопрос?) Основная идея сформулирована (не строго) так: «При усреднении по всем возможным ситуациям, каждый алгоритм работает одинаково хорошо. "

Звучит нелогично? Учтите, что для каждого случая, когда алгоритм работает, я мог бы создать ситуацию, когда он ужасно выходит из строя. Линейная регрессия предполагает, что ваши данные располагаются вдоль линии, но что, если она следует за синусоидальной волной? T-критерий предполагает, что каждый образец взят из нормального распределения: что если вы добавите выброс? Любой алгоритм градиентного всплытия может попасть в локальные максимумы, а любая контролируемая классификация может быть обманута.

Что это значит? Это означает, что ваши предположения - источник вашей силы! Когда Netflix рекомендует фильмы для вас, предполагается, что если вам нравится один фильм, вам понравятся похожие (и наоборот). Представьте себе мир, в котором это не было правдой, и ваши вкусы совершенно случайно разбросаны по жанрам, актерам и режиссерам. Их алгоритм рекомендаций ужасно потерпит неудачу. Имеет ли смысл говорить: «Ну, это все еще сводит к минимуму некоторую ожидаемую квадратичную ошибку, поэтому алгоритм все еще работает»? Вы не можете создать алгоритм рекомендаций, не сделав некоторых предположений о вкусах пользователей, так же, как вы не можете создать алгоритм кластеризации, не делая некоторых предположений о природе этих кластеров.

Так что не просто примите эти недостатки. Знайте их, чтобы они могли сообщить ваш выбор алгоритмов. Поймите их, чтобы вы могли настроить свой алгоритм и преобразовать данные для их решения. И любите их, потому что если ваша модель никогда не ошибется, это означает, что она никогда не будет правильной.

Я просто хотел бы добавить к ответу @ DavidRobinson, что кластеризация с минимальной общей дисперсией кластера на самом деле является задачей комбинаторной оптимизации , из которых k-Means является всего лишь одним методом - и учитывая последний «один выстрел», локальный характер «наискорейшего спуска», очень плохо тоже. Кроме того, попытка существенно улучшить k-средние «голые кости», каким-то образом (но быстро!) Выяснить, где должны быть семена кластера, обречена с самого начала: так как семена воздействуют (радикально!) На конечные кластеры, это составляет «зная», что такое оптимум ... прежде чем вычислять его.

Однако, как и большинство проблем оптимизации, он, тем не менее, может быть подвержен серьезным методам оптимизации . Один из них очень близко соответствует структуре проблемы (как того требует НФЛ!), И это, безусловно, отражается в ее результатах. Я не хочу делать какие-либо объявления здесь (это было бы - и это правильно - против этикета), поэтому, если вам интересно, просто прочитайте это здесь и сделайте свое собственное суждение.

При этом я согласен с @ttnphns, что k-Means определенно не идентифицирует гауссову смесь - функции стоимости двух задач совершенно разные. Оказывается, что нахождение наиболее подходящей (с точки зрения вероятности модели на основе данных) гауссовой смеси также является задачей комбинаторной оптимизации - и для которой также существует серьезная методика оптимизации . Еще раз, без рекламы: вы можете прийти к собственному заключению здесь - я просто скажу, что обсуждаемый там алгоритм действительно может правильно идентифицировать кластеры, подобные последнему изображению в посте @ DavidRobinson . Он даже правильно (т.е. математически четко определенным образом) решает извечную проблему выбросов , то есть точки данных, которые не принадлежат ни к одному из кластеров, потому что они просто абсолютно случайны (к счастью, они полностью срывают, например, k-Means ). Это достигается за счет того, что одно дополнительное, равномерное распределение конкурирует с гауссианами ... и великолепный результат заключается в том, что на равномерно распределенных данных он действительно сообщает, что там ничего нет (я никогда такого не видел).

Теперь, очевидно, согласно НФЛ, и, как вы правильно заметили , даже глобально оптимальные гауссовы смеси с идентификацией выбросов основаны на предварительном предположении, а именно на том, что данные действительно распределены нормально. К счастью , хотя, благодаря Закону больших чисел, многочисленные природные явления делают соответствуют этому условию.

ОТКАЗ ОТ ОТВЕТСТВЕННОСТИ: с моими глубочайшими извинениями я написал обе статьи выше и алгоритмы, которые они обсуждают.

PS Однажды я встретил Macready на конференции - очень яркий и приятный парень!

Логически говоря, недостатками K-средних являются:

• нужна линейная отделимость кластеров
• нужно указать количество кластеров
• Алгоритмика: процедура Лойдса не сходится к истинному глобальному максимуму даже при хорошей инициализации, когда имеется много точек или измерений

Но К-значит лучше, чем мы обычно думаем. Я с энтузиазмом отнесся к этому после того, как проверил его на других методах кластеризации (спектральный, плотность ...) и LDA в реальной классификации текстов одного миллиона текстов: точность K-средних была намного лучше, чем, например, у LDA (88% против 59%). Некоторые другие методы кластеризации были хорошими, но K-means был близок к вершине ... и более доступным с точки зрения сложности.

Я никогда не читал о методе кластеризации, который лучше всего подходит для широкого круга проблем. Не сказать, что K-означает универсально лучше, просто, насколько я знаю, универсального кластерного супергероя не существует. Много статей, много методов, а не настоящая революция (по моему личному ограниченному опыту тестирования некоторых из них).

Основная причина, по которой логические недостатки K-средних часто очевидны, состоит в том, что точки кластеризации в 2D-плоскости - это то, что вы редко делаете в машинном обучении. Многие вещи из геометрической интуиции, которые верны в 2D, 3D ... не имеют значения в довольно больших измерениях или абстрактных векторных пространствах (например, мешок слов, вектор переменных ...)

Линейная разделимость: вам редко приходится иметь дело с круговыми кластерами в реальных данных. Еще лучше предположить, что они не существуют в этих случаях. Разрешение вашего алгоритма на их поиск позволит ему находить странные круглые скопления в шуме. Линейное предположение в K-средних делает его часто более устойчивым.

Количество кластеров: часто нет идеального идеального количества кластеров, которое вы хотите увидеть. Например, для классификации текста может быть 100 категорий, 105, 110 ... все это довольно субъективно. Указание количества кластеров становится эквивалентным указанию глобальной гранулярности. В любом случае все методы кластеризации требуют спецификации гранулярности.

$10^{\text{a lot}}$

Но все алгоритмы кластеризации имеют такие ограничения. Например, в спектральной кластеризации: вы не можете найти истинные собственные векторы, только приближения.

За то же время вычислений довольно оптимизированная библиотека LDA работала хуже, чем наши самодельные (не полностью оптимизированные) K-средства. С тех пор я думаю немного по-другому.

Чтобы понять недостатки K-средних, мне нравится думать о том, что за модель стоит за ней.

$K$$K$

$K$$\sigma^2 \mathbf{I}$$\sigma^2$$K$$\sigma^2 \rightarrow 0$

Итак, что это говорит нам о недостатках K-средних?

1. К-среднее приводит к кластерам, которые выглядят многомерными гауссовскими.
2. Поскольку дисперсия между переменными одинакова, K-средних приводит к кластерам, которые выглядят сферическими.
3. $K$
4. K-означает стремление к группам одинакового размера.

K-means - это довольно ограничительный алгоритм. Преимущество заключается в том, что с учетом предположений, приведенных выше, вы можете выполнить алгоритм довольно быстро. Но если производительность кластеризации является вашей главной задачей, K-means обычно слишком ограничен в реальных ситуациях.