Я изучал кластеризацию k-средних , и одна вещь, которая не совсем ясна, это то, как вы выбираете значение k. Это просто вопрос проб и ошибок, или есть что-то еще?
cluster-analysis
k-means
Джейсон Бейкер
источник
источник
R
) здесь: stackoverflow.com/a/15376462/1036500Ответы:
Вы можете максимально увеличить Байесовский информационный критерий (BIC):
где
L(X | C)
- логарифмическая вероятность набора данных вX
соответствии с модельюC
,p
это число параметров в моделиC
иn
количество точек в наборе данных. См. «X-means: расширение K- средних с эффективной оценкой числа кластеров» Дана Пеллега и Эндрю Мура в ICML 2000.Другой подход заключается в том, чтобы начать с большого значения
k
и продолжать удалять центроиды (уменьшая k) до тех пор, пока оно не уменьшит длину описания. См. «Принцип MDL для надежного векторного квантования» Хорста Бишофа, Алеся Леонардиса и Александра Селба в « Анализ образцов и приложения», вып. 2, стр. 59-72, 1999.Наконец, вы можете начать с одного кластера, а затем продолжать разбивать кластеры, пока точки, назначенные каждому кластеру, не будут иметь гауссово распределение. В «Изучение k в k- средних» (NIPS 2003) Грег Хамерли и Чарльз Элкан показывают некоторые доказательства того, что это работает лучше, чем BIC, и что BIC недостаточно сильно наказывает за сложность модели.
источник
По сути, вы хотите найти баланс между двумя переменными: количеством кластеров ( k ) и средней дисперсией кластеров. Вы хотите минимизировать первое, а также минимизировать второе. Конечно, с увеличением количества кластеров средняя дисперсия уменьшается (вплоть до тривиального случая k = n и дисперсии = 0).
Как всегда в анализе данных, не существует единственного правильного подхода, который работал бы лучше всех остальных во всех случаях. В конце концов, вы должны принять собственное суждение. Для этого полезно построить график зависимости числа кластеров от средней дисперсии (что предполагает, что вы уже запустили алгоритм для нескольких значений k ). Тогда вы можете использовать количество кластеров в колене кривой.
источник
Да, вы можете найти наилучшее количество кластеров, используя метод Elbow, но я обнаружил, что найти значение кластеров по графу колен с помощью скрипта проблематично. Вы можете наблюдать за графиком локтя и найти точку локтя самостоятельно, но было очень сложно найти его по сценарию.
Так что другой вариант - использовать Silhouette Method, чтобы найти его. Результат от Silhouette полностью соответствует результату метода Elbow в R.
Вот что я сделал.
Надеюсь, поможет!!
источник
Может быть кто-то вроде меня, начинающий, ищет пример кода. информация для Silhouette_score доступна здесь.
источник
Посмотрите на эту статью Грега Хамерли, Чарльза Элкана «Изучение k в k-средних». Он использует тест Гаусса, чтобы определить правильное количество кластеров. Кроме того, авторы утверждают, что этот метод лучше, чем BIC, который упоминается в принятом ответе.
источник
Есть нечто, называемое «Правило большого пальца». Это говорит о том, что количество кластеров может быть рассчитано
k = (n/2)^0.5
где n - общее количество элементов в вашем образце. Вы можете проверить достоверность этой информации на следующей бумаге:
http://www.ijarcsms.com/docs/paper/volume1/issue6/V1I6-0015.pdf
Существует также другой метод, называемый G-means, где ваше распределение следует распределению по Гауссу или нормальному распределению. Он состоит из увеличения k до тех пор, пока все ваши k групп не будут следовать распределению Гаусса. Это требует много статистики, но может быть сделано. Вот источник:
http://papers.nips.cc/paper/2526-learning-the-k-in-k-means.pdf
Надеюсь, это поможет!
источник
Сначала создайте минимальное связующее дерево ваших данных. Удаление K-1 самых дорогих ребер разделяет дерево на K кластеров,
так что вы можете построить MST один раз, посмотреть на расстояния / метрики кластеров для различных K и взять колено кривой.
Это работает только для Single-linkage_clustering , но для этого это быстро и просто. Кроме того, MST делают хорошие визуальные эффекты.
См., Например, график MST в разделе stats.stackexchange для визуализации программного обеспечения для кластеризации .
источник
Я удивлен, что никто не упомянул эту прекрасную статью: http://www.ee.columbia.edu/~dpwe/papers/PhamDN05-kmeans.pdf
После нескольких предложений я наконец наткнулся на эту статью, читая этот блог: https://datasciencelab.wordpress.com/2014/01/21/selection-of-k-in-k-means-clustering-reloaded/
После этого я реализовал это в Scala, реализации, которая для моих сценариев использования дает действительно хорошие результаты. Вот код:
источник
Если вы используете MATLAB, любую версию начиная с 2013b, то есть вы можете использовать функцию,
evalclusters
чтобы выяснить, какой должнаk
быть оптимальность для данного набора данных.Эта функция позволяет выбрать один из 3 -х алгоритмов кластеризации -
kmeans
,linkage
иgmdistribution
.Она также позволяет выбрать один из 4 кластеризации критериев оценки -
CalinskiHarabasz
,DaviesBouldin
,gap
иsilhouette
.источник
Если вы не знаете номера кластеров k, которые должны быть представлены в качестве параметра для k-средних, есть четыре способа найти его автоматически:
Алгоритм G-средних: он обнаруживает количество кластеров автоматически, используя статистический тест, чтобы решить, следует ли разбивать центр k-средних на два. Этот алгоритм использует иерархический подход для определения количества кластеров, основанный на статистическом тесте для гипотезы о том, что подмножество данных следует гауссову распределению (непрерывная функция, которая приближается к точному биномиальному распределению событий), и, если нет, разделяет кластер. , Он начинается с небольшого числа центров, скажем, только один кластер (k = 1), затем алгоритм разбивает его на два центра (k = 2) и снова разбивает каждый из этих двух центров (k = 4), имея четыре центра в общее количество. Если G-среднее не принимает эти четыре центра, то ответом является предыдущий шаг: два центра в этом случае (k = 2). Это количество кластеров, на которые будет разделен ваш набор данных. G-means очень полезен, когда у вас нет оценки количества кластеров, которые вы получите после группировки ваших экземпляров. Обратите внимание, что неудобный выбор параметра «k» может привести к неверным результатам. Параллельная версия g-средних называетсяр-значит . Источники G-средних: источник 1, источник 2, источник 3
x-означает : новый алгоритм, который эффективно ищет пространство местоположений кластеров и количество кластеров для оптимизации байесовского критерия информации (BIC) или показателя информационного критерия Акаике (AIC). Эта версия k-средних находит число k, а также ускоряет k-средние.
K-средства онлайн или потоковые k-средства: он позволяет выполнить k-средства путем сканирования всех данных один раз и автоматически находит оптимальное число k. Spark реализует это.
Алгоритм MeanShift : это непараметрическая методика кластеризации, которая не требует предварительного знания количества кластеров и не ограничивает форму кластеров. Кластеризация по среднему сдвигу направлена на обнаружение «пятен» в гладкой плотности образцов. Это алгоритм, основанный на центроидах, который работает, обновляя кандидатов на центроиды, чтобы они были средними точками в данном регионе. Эти кандидаты затем фильтруются на этапе последующей обработки, чтобы исключить почти дубликаты, чтобы сформировать окончательный набор центроидов. Источники: источник1 , источник2 , источник3
источник
Я использовал решение, которое нашел здесь: http://efavdb.com/mean-shift/, и оно мне очень помогло:
источник
Моя идея состоит в том, чтобы использовать Силуэт Коэффициент, чтобы найти оптимальный номер кластера (K). Подробности объяснения здесь .
источник
Предполагая, что у вас есть названная матрица данных
DATA
, вы можете выполнить разбиение по медоидам с оценкой количества кластеров (с помощью анализа силуэтов) следующим образом:источник
Один из возможных ответов - использовать метаэвристический алгоритм, такой как генетический алгоритм, чтобы найти k. Это просто Вы можете использовать случайный K (в некотором диапазоне) и оценить функцию подбора Генетического алгоритма с помощью некоторого измерения, такого как Silhouette And Find best K, основанного на функции подбора.
https://en.wikipedia.org/wiki/Silhouette_(clustering)
источник
источник
Другой подход заключается в использовании самоорганизующихся карт (SOP) для нахождения оптимального количества кластеров. SOM (самоорганизующаяся карта) - это методология нейронной сети без надзора, для которой требуется только вход, используемый для кластеризации для решения проблем. Этот подход используется в статье о сегментации клиентов.
Ссылка на статью
Абделла Амин и др., Модель сегментации клиентов в электронной торговле с использованием методов кластеризации и модели LRFM: пример интернет-магазинов в Марокко, Всемирная академия наук, инженерии и технологии Международный журнал по вычислительной технике и информатике, том 9, № 8 , 2015, 1999 - 2010
источник
Привет, я сделаю это просто и понятно, мне нравится определять кластеры, используя библиотеку 'NbClust'.
Теперь, как использовать функцию «NbClust» для определения правильного количества кластеров: вы можете проверить фактический проект в Github с фактическими данными и кластерами - расширение этого алгоритма «kmeans» также выполняется с использованием правильного количества «центров».
Ссылка на проект Github: https://github.com/RutvijBhutaiya/Thailand-Customer-Engagement-Facebook
источник
Вы можете выбрать количество кластеров, визуально осмотрев свои точки данных, но вскоре вы поймете, что в этом процессе много неопределенности для всех, кроме самых простых наборов данных. Это не всегда плохо, потому что вы занимаетесь обучением без присмотра, и в процессе маркировки есть некоторая внутренняя субъективность. Здесь, имея предыдущий опыт решения этой конкретной проблемы или чего-то подобного, вы сможете выбрать правильное значение.
Если вы хотите получить некоторую подсказку о количестве кластеров, которые вам следует использовать, вы можете применить метод Elbow:
Прежде всего, вычислите сумму квадратов ошибок (SSE) для некоторых значений k (например, 2, 4, 6, 8 и т. Д.). SSE определяется как сумма квадратов расстояния между каждым членом кластера и его центроидом. Математически:
SSE = ΣKi = 1Σx∈cidist (х, CI) 2
Если вы построите график k по отношению к SSE, вы увидите, что ошибка уменьшается с увеличением k; Это связано с тем, что когда количество кластеров увеличивается, они должны быть меньше, поэтому искажения также меньше. Идея метода локтя состоит в том, чтобы выбрать k, при котором SSE резко уменьшается. Это создает «эффект локтя» на графике, как вы можете видеть на следующем рисунке:
В этом случае k = 6 - это значение, выбранное методом Elbow. Примите во внимание, что метод Elbow является эвристическим и, как таковой, он может или не может хорошо работать в вашем конкретном случае. Иногда бывает больше одного локтя или совсем нет локтя. В этих ситуациях вы обычно заканчиваете тем, что вычисляете наилучшее k, оценивая, насколько хорошо k-means работает в контексте конкретной проблемы кластеризации, которую вы пытаетесь решить.
источник
Я работал над пакетным пакетом Python (алгоритм Kneedle). Он находит номер кластера динамически как точку, где кривая начинает выравниваться. При заданном наборе значений x и y, колено вернет точку перегиба функции. Точка перегиба - это точка максимальной кривизны. Вот пример кода.
у = [+7342,1301373073857, 6881,7109460930769, 6531,1657905495022,
6356,2255554679778, +6209,8382535595829, +6094,9052166741121, 5980,0191582610196, 5880,1869867848218, 5779,8957906367368, +5691,1879324562778, 5617,5153566271356, 5532,2613232619951, +5467,352265375117, +5395,4493783888756, 5345,3459908298091, +5290,6769823693812, +5243,5271656371888, +5207,2501206569532, 5164,9617535255456]
х = диапазон (1, лен (у) +1)
из коленного импорта KneeLocator kn = KneeLocator (x, y, кривая = «выпуклая», направление = «убывающая»)
печать (kn.knee)
источник