Как определиться с правильным количеством кластеров?

54

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

Я использую MATLAB для научных вычислений, где рассмотрение силуэтов дается в качестве способа выбора k, обсуждаемого здесь . Однако меня больше интересовали бы байесовские подходы. Любые предложения приветствуются.

Petrichor
источник
2
Хороший вопрос ...
Под визуализацией для кластеризации есть (хм) способ изобразить k-кластеры и увидеть эффект различных k в одном кадре, используя MST.
Денис
Я ответил на этот вопрос с полдюжины методов в Rтечение здесь
Бен
1
Выбор «лучшего» числа k кластеров подразумевает сравнение кластерных решений с разными k - какое решение «лучше». В этом отношении задача выглядит аналогично тому, как сравнивать методы кластеризации - что «лучше» для ваших данных. Общие рекомендации здесь .
ttnphns

Ответы:

28

Об этом пару раз спрашивали на stackoverflow: здесь , здесь и здесь . Вы можете посмотреть, что толпа там думает по этому вопросу (или его небольшой вариант).

Позвольте мне также скопировать мой собственный ответ на этот вопрос на stackoverflow.com:

К сожалению, нет никакого способа автоматически установить «правильное» K и нет определения того, что такое «правильное». Не существует принципиального статистического метода, простого или сложного, который может установить «правильное К». Есть эвристика, эмпирические правила, которые иногда работают, иногда нет.

Ситуация более общая, так как многие методы кластеризации имеют параметры такого типа, и я думаю, что это большая открытая проблема в сообществе исследователей кластеризации / обучения без учителя.

carlosdc
источник
+1 После прочтения этого - мне это кажется настолько интуитивным ... но я должен сказать, что никогда раньше не думал об этом. что на самом деле проблема выбора количества компьютеров в PCA эквивалентна проблеме выбора количества кластеров в K-средних ...
Дов
2
@ Дов эти две вещи не совсем эквивалентны. Существуют конкретные меры, которые можно использовать для проверки качества решения PCA (в частности, ошибки реконструкции, но также% выявленных отклонений и т. Д.), И они, как правило, (в основном) согласованы. Однако в кластеризации часто не существует одного «правильного ответа» - одна кластеризация может быть лучше другой по одной метрике, а обратная может быть верной при использовании другой метрики. А в некоторых ситуациях две разные кластеризации могут быть одинаково вероятными по одной и той же метрике.
TDC
@tdc, но не так ли en.wikipedia.org/wiki/… более или менее так улучшен outcomes.com/docs/WebSiteDocs/PCA/… ?
Дов
2
@Dov Да, они «более или менее» похожи друг на друга, но я просто говорил, что проблема выбора количества кластеров намного сложнее, чем выбор количества компьютеров, то есть они не «эквивалентны».
tdc
1
+1 Ты прав. Мы как бы вводим какую-то другую модель или предположение, чтобы выбрать лучшее k, но тогда возникает вопрос, почему эта модель или предположение лучшая ...
petrichor
19

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

Сказав это, вы можете взглянуть на процессы Дирихле . Также см. Этот учебник .

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

Обратите внимание, что вам все еще нужно указать параметр концентрации процесса Дирихле. При малых значениях образцы из ДП могут состоять из небольшого числа атомных мер с большими весами. При больших значениях большинство образцов, вероятно, будут различаться (концентрироваться). Вы можете использовать гиперприоритет для параметра концентрации, а затем вывести его значение из данных, и этот гиперприоритет может быть достаточно расплывчатым, чтобы разрешить множество различных возможных значений. Однако, учитывая достаточное количество данных, параметр концентрации перестанет быть таким важным, и этот гиперприоритет может быть отброшен.ααα

TDC
источник
1
Процесс Дирихле при каком параметре концентрации? Это отчасти эквивалентно тому же самому оригинальному вопросу, k-означает, под каким k? Хотя я согласен с тем, что мы лучше понимаем распределение Direchlet, чем поведение какого-то сложного алгоритма на реальных данных.
Carlosdc
@carlosdc хорошая идея, я обновил ответ, включив в него небольшую дискуссию о параметре концентрации
tdc
1
По моему опыту, гораздо легче выучить непрерывный параметр концентрации, такой как альфа, чем определить количество кластеров в модели конечной смеси. Если вы хотите придерживаться модели конечной смеси и взять байесовский тэкс, есть обратимый скачок MCMC ( onlinelibrary.wiley.com/doi/10.1111/1467-9868.00095/abstract )
1
Отличный ответ. Я бы добавил статью « Пересмотр K-средних: новые алгоритмы с помощью байесовской непараметрики» . Что дает простой «непрерывный» подход к K-Means. Тогда с помощью оптимизации легко найти оптимальное значение.
Рой
9

Я использую метод локтя :

  • Начните с K = 2 и продолжайте увеличивать его на каждом шаге на 1, вычисляя свои кластеры и затраты, которые идут с обучением. При некотором значении для K стоимость резко падает, и после этого она достигает плато, когда вы увеличиваете ее. Это значение К, которое вы хотите.

Обоснование состоит в том, что после этого вы увеличиваете количество кластеров, но новый кластер очень близок к некоторым из существующих.

vonPetrushev
источник
Похоже, это принцип, который оценивает метод L (см. Мой ответ).
winwaed
6

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

Если вам нужно его автоматизировать, вы можете добавить штраф к увеличению k и таким образом рассчитать оптимальный кластер. И тогда вы просто весите k в зависимости от того, хотите ли вы тонну кластеров или хотите очень мало.

нейрон
источник
5

Мне удалось использовать «метод L», чтобы определить количество кластеров в географическом приложении (т. Е., В сущности, двумерная проблема, хотя технически неевклидова).

Метод L описан здесь: Определение количества кластеров / сегментов в алгоритмах иерархической кластеризации / сегментации Стэн Сальвадор и Филипп Чан

По сути, это оценивает соответствие для различных значений k. График в форме буквы "L" виден с оптимальным значением k, представленным коленом на графике. Простой расчет подгонки наименьших квадратов по двум линиям используется для определения точки перегиба.

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

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

winwaed
источник
4

k

Но что, если ваш набор данных не вписывается в схему Вороного?

kk

k

Anony-Мус
источник
3
Хотя описание K-средних в первом абзаце не является ошибочным, некоторые люди могут ввести в заблуждение некоторых людей приравниванием этого метода к разбиению Вороного на основе исходных данных. Это не так: раздел основан на расположении кластерного средства, которое может не совпадать (и обычно не будет) с любыми исходными данными.
whuber
3

В целом, вы можете выбрать количество кластеров в двух разных направлениях.

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

  2. На основе данных: большее количество кластеров является слишком подходящим, а меньшее количество кластеров - недостаточным. Вы всегда можете разделить данные пополам и выполнить перекрестную проверку, чтобы увидеть, сколько хороших кластеров. Обратите внимание, что при кластеризации у вас все еще есть функция потерь, аналогичная контролируемой настройке.

Наконец, вы должны всегда объединять знания и данные в реальном мире.

Haitao Du
источник
2

Поскольку никто еще не указал это, я думал, что поделюсь этим. Существует метод, называемый X-means ( см. Эту ссылку ), который оценивает надлежащее количество кластеров, используя байесовский информационный критерий (BIC). По сути, это все равно, что пытаться использовать K с разными Ks, рассчитывать BIC для каждого K и выбирать лучший K. Этот алгоритм делает это эффективно.

Существует также реализация weka , подробности о которой можно найти здесь .

rivu
источник
0

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

Эта статья объясняет алгоритм.

felipeduque
источник