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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

$k$

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

$k$$k$

$k$

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

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

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

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

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

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

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

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