Есть ли конкретная цель с точки зрения эффективности или функциональности, почему алгоритм k-средних не использует, например, косинусное (дис) сходство в качестве метрики расстояния, а может использовать только евклидову норму? В целом, будет ли метод K-средних соответствовать и быть правильным, когда другие расстояния, кроме евклидовых, рассматриваются или используются?
[Дополнение от @ttnphns. Вопрос двоякий. «(Не) евклидово расстояние» может относиться к расстоянию между двумя точками данных или расстоянию между точкой данных и центром кластера. До сих пор в ответах предпринимались попытки обоих способов.]
clustering
k-means
distance-functions
euclidean
любопытный
источник
источник
Ответы:
Процедура K-средних - метод векторного квантования, часто используемый в качестве метода кластеризации, - вообще не использует попарно расстояния ч / б точек данных (в отличие от иерархической и некоторых других кластеризаций, которые допускают произвольную меру близости). Это означает многократное присвоение точек ближайшему центроиду, таким образом, используя евклидово расстояние от точек данных до центроида . Тем не менее, K- средние значения неявно основаны на попарных евклидовых расстояниях ч / б точек данных, потому что сумма квадратов отклонений от центроида равна сумме попарно возведенных в квадрат евклидовых расстояний, деленной на количество точек, Термин «центроид» сам по себе из евклидовой геометрии. Это многомерное среднее в евклидовом пространстве. Евклидово пространство - это евклидовы расстояния. Неевклидовы расстояния обычно не охватывают евклидово пространство. Вот почему K-Means предназначен только для евклидовых расстояний.
Но евклидово расстояние ч / б двух точек данных может быть представлено несколькими альтернативными способами . Например, оно тесно связано с косинусом или скалярным произведением ч / б точек. Если у вас есть косинус, или ковариация, или корреляция, вы всегда можете (1) преобразовать его в (квадрат) евклидово расстояние, а затем (2) создать данные для этой матрицы евклидовых расстояний (с помощью главных координат или других форм метрики). Многомерное масштабирование) для (3) ввода этих данных в кластеризацию K-средних. Следовательно, можно заставить K-средние «работать» с парными косинусами или чем-то подобным; на самом деле такие реализации кластеризации K-Means существуют. Смотрите также о реализации "K-средних для матрицы расстояний".
Конечно, можно запрограммировать K-средства так, чтобы они непосредственно вычисляли на квадратной матрице попарно евклидовых расстояний. Но это будет работать медленно, и поэтому более эффективным способом является создание данных для этой матрицы расстояний (преобразование расстояний в скалярные произведения и т. Д. - проход, описанный в предыдущем абзаце) - и затем применение стандартной процедуры K-средних к этому набору данных.
Обратите внимание, что я обсуждал тему, совместимо ли евклидово или неевклидово различие между точками данных с K-средних. Это связано, но не совсем с тем же вопросом, может ли неуклидные отклонения от центроида (в широком смысле, центра или квазицентроида) быть включены в K-средства или модифицированные «K-средства».
См. Связанный вопрос K-означает: почему минимизация WCSS максимизирует расстояние между кластерами? ,
источник
But a Euclidean distance b/w two data points can be represented in a number of alternative ways. For example, it is closely tied with cosine or scalar product b/w the points. If you have cosine, or covariance, or correlation, you can always (1) transform it to (squared) Euclidean distance
вами символов вы могли бы написать так же легко:distance(x,y) = 1 - cosine_sim(x,y)
или что-то столь же содержательное и информативное.См. Также ответ @ttnphns для интерпретации k-средних, которая фактически включает поточечные евклидовы расстояния.
Способ построения k-средних не основан на расстояниях .
K-means минимизирует дисперсию внутри кластера. Теперь, если вы посмотрите на определение дисперсии, оно идентично сумме квадратов евклидовых расстояний от центра. (Ответ @ttnphns относится к парным евклидовым расстояниям!)
Основная идея k-средних состоит в том, чтобы минимизировать квадратные ошибки . Здесь нет «расстояния».
Почему не правильно использовать произвольные расстояния: потому что k-means может перестать сходиться с другими функциями расстояния . Общее доказательство сходимости, как это: шаг назначения и средний шаг обновления и оптимизация же критерий. Существует ограниченное количество возможных назначений. Следовательно, оно должно сходиться после конечного числа улучшений. Чтобы использовать это доказательство для других функций расстояния, вы должны показать, что среднее значение (примечание: k- означает ) также минимизирует ваши расстояния.
Если вы ищете манхэттенский вариант k-средних, то есть k-медианы. Потому что медиана - известная лучшая оценка L1.
Если вам нужны произвольные функции расстояния, взгляните на k-medoids (иначе: PAM, разбиение вокруг medoids). Медоид минимизирует произвольные расстояния (потому что он определен как минимум), и существует только конечное число возможных медоидов. Хотя это намного дороже, чем среднее.
источник
@ttnphns answer refers to pairwise Euclidean distances!
В своем ответе, 1-й абзац, я четко ссылаюсь как на «ошибки SS» (прямые), так и на «парные d ^ 2» (неявные) интерпретации.k-means may stop converging with other distance functions
гомологичен моему теоретическомуNon-euclidean distances will generally not span euclidean space
.Я мог бы быть немного педантичным здесь, но K-means - это имя, данное конкретному алгоритму, который присваивает метки точкам данных таким образом, чтобы в пределах кластера отклонения были сведены к минимуму, и это не название для «общего метода».
Алгоритм K-средних был независимо предложен из нескольких областей с сильными интерпретациями, применимыми к области. Просто получается, что это также евклидово расстояние до центра. Для краткой истории K-средних, пожалуйста, прочитайте Кластеризация данных: 50 лет после K-средних
Существует множество других алгоритмов кластеризации, которые используют метрики, отличные от евклидовых. Самый общий случай, который я знаю, - это использование расхождений Брегмана для кластеризации, из которых евклидова является частным случаем.
источник
Поскольку это, по-видимому, теперь канонический вопрос, и он еще не упоминался здесь:
Одним естественным расширением k-средства для использования метрик расстояния, отличных от стандартного евклидова расстояния в является использование трюка с ядром . Это относится к идее неявного отображения входных данных в гильбертовом пространстве с высокой или бесконечной размерностью, где расстояния соответствуют функции расстояния, которую мы хотим использовать, и запускаем алгоритм там. То есть, позволяя быть некоторой характеристической картой, такой, что желаемая метрика может быть записана в виде , мы запускаем k-средних в точках . Во многих случаях мы не можем вычислить карту явно, но мы можемRd φ:Rp→H d d(x,y)=∥φ(x)−φ(y)∥H {φ(xi)} φ вычислить ядро . Не все метрики расстояния соответствуют этой модели, но многие из них подходят, и есть такие функции, определенные для строк, графиков, изображений, распределений вероятностей и т. Д.k(x,y)=⟨φ(x),φ(y)⟩H
В этой ситуации в стандартном (ллойдовском) алгоритме k-средних мы можем легко назначать точки для их кластеров, но мы представляем центры кластеров неявно (как линейные комбинации входных точек в гильбертовом пространстве). Нахождение лучшего представления в пространстве ввода потребовало бы нахождения среднего значения Фреше , что довольно дорого. Таким образом, легко получить кластерные назначения с ядром, труднее получить средства.
Следующая статья обсуждает этот алгоритм и связывает его со спектральной кластеризацией:
источник
Я прочитал много интересных комментариев здесь, но позвольте мне добавить, что «персональная» реализация k-средних в Matlab поддерживает 4 неевклидовых расстояния [между точками данных и центрами кластеров]. Единственный комментарий из документации, которую я вижу по этому поводу:
Затем список функций
c
иx
следует. Таким образом, учитывая, чтоp
это размерность входных данных, кажется, что евклидово вложение не выполняется заранее.Кстати, в прошлом я использовал k-средства Матлаба с корреляционным расстоянием, и он (неудивительно) сделал то, что должен был сделать.
источник
cosine
(это просто евклидово расстояние на нормированных входных точках),correlation
(евклидовы на стандартизированных входах),cityblock
( , в этом случае используется медиана, а не среднее) и (что является только для двоичных входов).hamming
cityblock
От сюда :
источник