26
Я пытаюсь понять, можно ли сравнить производительность обоих на основе целевых функций, над которыми они работают?В чем разница между объектами «k означает» и «нечеткие c средства»?
A
ответ
22
BTW, алгоритм кластеризации Fuzzy-C-Means (FCM) также известен как Soft K-Means.
Целевые функции практически идентичны, единственное отличие состоит в том, что вектор, выражающий процент принадлежности данной точки к каждому из кластеров. Этот вектор представлен экспоненте «жесткости», направленной на то, чтобы придать большее значение более сильным связям (и, наоборот, минимизировать вес более слабых); случайно, когда коэффициент жесткости стремится к бесконечности, результирующий вектор становится двоичной матрицей, что делает модель FCM идентичной модели K-Means.
Я думаю, что, за исключением некоторой возможной проблемы с кластерами, у которых нет назначенных им точек, можно эмулировать алгоритм K-Means с алгоритмом FCM, путем моделирования бесконечного коэффициента жесткости (= путем введения функция, которая меняет наибольшее значение в векторе на 1 и выравнивает другие значения вместо экспоненциации вектора). Это, конечно, очень неэффективный способ запуска K-Means, потому что тогда алгоритм должен выполнять столько операций, сколько с истинным FCM (если только с 1 и 0 значениями, что упрощает арифметику, но не сложность)
Что касается производительности, ТСМ, следовательно, должен выполнить к (т.е. количество кластеров) умножений для каждой точки, для каждого измерения (не считая также возведение в степень принять во внимание жесткость). Это, а также накладные расходы, необходимые для вычисления и управления вектором близости, объясняют, почему FCM довольно медленнее, чем обычные K-средства.
Но FCM/Soft-K-Means менее «глупый», чем Hard-K-Means, когда он приходит, например, в удлиненные кластеры (когда точки, в противном случае согласованные в других измерениях, разбросаны по определенному размеру или два) и поэтому он все еще вокруг ;-)
Кроме того, я просто подумал об этом, но не придал ему никакой «математической» мысли, FCM может сходиться быстрее, чем жесткий K-Means, что несколько компенсирует большее вычислительное требование от FCM.
+0
Почему FCM сходится быстрее? Это совсем не сходится, вы должны остановиться на определенном пороге, когда относительные назначения больше не меняются «достаточно»; так же, как кластер GMM-EM. –
+0
@ Anony-Mousse: как в FCM, так и в K-Means _converge_, в математическом смысле это очень то, что вы описываете с помощью «когда относительные назначения больше не изменяются» достаточно ». Другими словами, решение кластеризации, предоставляемое последовательными итерации этих алгоритмов сильно меняются, сначала, от одной итерации к следующей, но в конечном итоге изменения становятся все меньше и меньше по мере приближения функции к ее пределу. Безопасно прекратить итерацию после достижения практического порога изменения, потому что функция сходится: итерация больше не приведет к значительному другому результату ... – mjv
+0
... Что я еще не пытался изучить, является ли FCM фактически сходится быстрее, чем жесткие K-средства. Другими словами, если для достижения желаемого «стабильного» решения требуется меньшее количество итераций с FCM (чем с обычными K-Means). – mjv
16
K-Means clustering и Fuzzy-C Means Clustering очень похожи в подходах. Основное различие заключается в том, что в кластеризации Fuzzy-C Me каждая точка имеет взвешивание, связанное с конкретным кластером, поэтому точка не сидит «в кластере» так сильно, как слабая или сильная связь с кластером, что определяется обратным расстоянием до центра кластера.
Средство Fuzzy-C будет иметь тенденцию работать медленнее, чем означает K, поскольку на самом деле это делает больше работы. Каждая точка оценивается с каждым кластером, и в каждой оценке задействовано больше операций. K-Means просто нужно сделать расчет расстояния, в то время как нечеткие c-средства должны выполнять полный взвешивание с обратным расстоянием.
1
люди написали технически, и каждый ответ хорошо написан. Но то, что я хочу сказать, одинаково на языке непрофессионалов. K означает кластерный кластер весь набор данных в K-номер кластера, где данные должны принадлежать только одному кластеру. Нечеткие c-средства создают k чисел кластеров, а затем назначают каждый данные каждому кластеру, но их будет фактором, который определит, насколько сильно данные принадлежат этому кластеру.
Да ладно! Не закрывайте ... кластеризацию программирования IS, на том же уровне, который говорит алгоритмы сортировки или вопросы о формальной грамматике! – mjv