Определение лучшего k для k ближайшего соседа

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

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

Существуют и другие методы иерархической кластеризации (см. Статью, предложенную в комментариях Имрана).

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

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

Следует сказать, что кластеризация - это больше метод визуализации и исследования данных. Может быть трудно с уверенностью объяснить, что одна кластеризация правильно объясняет данные, выше всех остальных. Лучше всего объединить ваши кластеры с другой важной информацией. Есть ли в ваших данных что-то функциональное или информативное, что вы знаете, что некоторые кластеры невозможны? Это может значительно сократить пространство для решения.

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

На вашем месте я бы сделал PCA, в конечном итоге на полиномиальном пространстве (позаботьтесь о вашем доступном времени) в зависимости от того, что вы знаете о своем вводе, и сгруппировал бы по большинству репрезентативных компонентов.

] Дополнительная информация о вашем наборе данных будет очень полезна для более точного ответа.

В предыдущем ответе я объяснил, как Самоорганизующиеся карты (SOM) могут использоваться в визуальной кластеризации.

В противном случае, там существует вариант алгоритма K-средних, называемый X-Means , который может определять количество кластеров путем оптимизации байесовского информационного критерия (BIC) в дополнение к решению проблемы масштабируемости за счет использования KD-деревьев .
Weka включает реализацию X-Means вместе со многими другими алгоритмами кластеризации, и все это в простом в использовании инструменте с графическим интерфейсом.

Наконец, вы можете для ссылки на эту страницу , на которой обсуждается Метод локтя среди других методов определения количества кластеров в наборе данных.

Вот мое приблизительное решение:

1. Начните с k = 2.
2. Для нескольких попыток:
   1. Запустите алгоритм k-средних, чтобы найти k кластеров.
   2. Найдите среднеквадратичное расстояние от начала координат до центроидов кластера.
3. Повторите 2-3, чтобы найти стандартное отклонение расстояний. Это показатель стабильности кластеров.
4. Если стабильность кластеров для k <стабильность кластеров для k - 1 , то верните ] k - 1
5. Увеличение k на 1.

Тезис, лежащий в основе этого алгоритма, состоит в том, что количество наборов k кластеров мало для "хороших" значений к .

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

Из вашей ссылки на википедию:

Что касается вычислительной сложности, проблема кластеризации k-средних:

• NP-сложная в общем евклидова пространство d даже для 2 кластеров
• NP-жесткий для общего числа кластеры k даже в плоскости
• Если k и d фиксированы, проблема может быть точно решено за время O (ndk + 1 log n), где n - количество сущностей для быть кластеризованными

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

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

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

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

Выбор наилучшего K можно рассматривать как проблему Выбор модели . Один из возможных подходов - Минимальная длина описания , что в данном контексте означает: вы можете сохранить таблицу со всеми точками (в этом случае K = N). С другой стороны, у вас K = 1, и все точки сохраняются как их расстояния от одного центроида. В этом разделе из «Введение в поиск информации» Мэннинга и Шутце предлагается минимизировать информационный критерий Акаике в качестве эвристики для оптимального K.