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

Question

Мне нужно провести кластерный анализ набора двухмерных данных (я могу добавить дополнительные измерения по пути).

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

С этой целью я хотел бы найти набор кластеров, которые в основном "выглядят правильно", а не объясняют некоторые скрытые паттерны.

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

Проблема, к которой я подхожу, заключается в следующем:

Как определить «лучшее» значение для k , чтобы сформированные кластеры были стабильными и визуально проверяемыми ?

Вопросы:

• Если предположить, что это не NP-завершено, какова сложность времени для поиска товара k . (вероятно, сообщается в количестве раз, чтобы запустить алгоритм k-средних).
• k-означает хорошую отправную точку для этого типа проблемы? Если да, то какие другие подходы вы бы порекомендовали. Конкретный пример, подкрепленный анекдотом / опытом, будет макси-бон.
• Какие короткие сокращения / приближения вы бы порекомендовали для увеличения производительности.

Answer 1

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

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

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

Answer 2

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

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

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

Answer 3

Вот мое примерное решение:

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

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

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

Answer 4

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

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

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

Answer 5

Эта проблема относится к классу «внутренней оценки» «проблем оптимизации кластеризации», в котором в современном решении используется коэффициент ** Силуэт *, как указано здесь

https://en.wikipedia.org/wiki/Cluster_analysis#Applications

и здесь :

https://en.wikipedia.org/wiki/Silhouette_(clustering):

«Графики и средние силуэты могут использоваться для определения натурального числа кластеров в наборе данных»

scikit-learn предоставляет пример использования методологии использования здесь * * -learn.org тысячи двадцать-одина / стабильный / auto_examples / кластер / plot_kmeans_silhouette_analysis.html * ** +1023 тысяча двадцать-дв *

Answer 6

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

Answer 7

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

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

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

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

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

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

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

Answer 8

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

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

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