Выполнять K-средние (или их близкие родственники) кластеризацию только с матрицей расстояний, а не с данными по точкам

22

Я хочу выполнить кластеризацию K-средних на имеющихся у меня объектах, но объекты не описываются как точки в пространстве, то есть objects x featuresнабором данных. Тем не менее, я могу вычислить расстояние между любыми двумя объектами (оно основано на функции подобия). Итак, я избавляюсь от матрицы расстояний objects x objects.

Я реализовал K-средства раньше, но это было с вводом набора данных точек; и с вводом матрицы расстояний мне не ясно, как обновить кластеры, чтобы они были "центрами" кластеров без представления точек. Как это обычно делается? Существуют ли варианты K-средних или методов, близких к этому, для этого?

мышь
источник
Что ты имеешь в виду там, которые не описаны как точки?
любопытно
См. Также stats.stackexchange.com/q/12495/3277
ttnphns

Ответы:

24

Очевидно, что k-means должен уметь вычислять средства .

Тем не менее, существует хорошо известная его вариация, известная как k-medoids или PAM (Partitioning Around Medoids), где medoid - это существующий объект, наиболее центральный для скопления. К-медоидам нужны только попарные расстояния.

Аноним-Мусс-Восстановить Монику
источник
21

Вы точно описываете проблему установки ядра -means; когда вы не можете представить точку данных как евклидов вектор, но если вы все еще можете рассчитать (или определить) внутреннее произведение между двумя точками данных, вы можете сгенерировать алгоритм. Следующая веб-страница содержит краткое описание алгоритма:К

Ядро означает страницуК

Этот трюк с ядром является очень популярной и фундаментальной идеей в статистике и машинном обучении.

Вики-страница о трюке с ядром

Если вам интересно, книга Бернхарда Шёлкопфа и Александра Дж. Смолы « Изучение с ядрами» будет очень хорошим введением.

Эта заметка Макса Веллинга кажется очень хорошей; Кроме того , если вы используете R вы посмотрите на может этого R пакет .

MDS может быть одним из способов решения вашей проблемы, но он напрямую не атакует проблему, которую вы хотите решить; в то время как ядро ​​k-means делает.

d_ijk_stra
источник
Я хотел включить больше ссылок, но не смог из-за низкой репутации. Это примечание от Max Welling примечания кажется очень хорошо; Кроме того, если вы используете R, вы можете взглянуть на этот пакет R
d_ijk_stra
(+1) Добро пожаловать на сайт. Я добавил ссылки в вашем комментарии к основной части поста, а также одну ссылку на тексты Schölkopf и Smola.
кардинал
9

@gung абсолютно прав, предлагая вам многомерное масштабирование (MDS) в качестве предварительного инструмента для создания points X dimensions данных из матрицы расстояний. Я должен добавить только несколько ударов. К-средняя кластеризация подразумевает евклидовы расстояния . MDS даст вам координаты точек в измерениях, тем самым гарантируя вам евклидовы расстояния. Вы должны использовать метрическую MDS и запрашивать максимально возможное количество измерений, потому что ваша цель - минимизировать ошибку повторного преобразования данных, а не отображать их в 2D или 3D.

Что если у вас под рукой нет программного обеспечения MDS, но есть некоторые матричные функции, такие как разложение по собственным значениям или разложение по сингулярным значениям? Тогда вы могли бы сделать простую метрическую MDS самостоятельно - Torgerson MDS, также известную как анализ основных координат (PCoA). Это немного «скрученный» анализ главных компонентов. Я не буду описывать это здесь, хотя это довольно просто. Вы можете прочитать об этом во многих местах, например, здесь .

Наконец, можно напрямую запрограммировать «K-средства для ввода матрицы расстояния» - без вызова или записи функций, выполняющих PCoA или другую метрическую MDS. Мы знаем, что (а) сумма квадратов отклонений от центроида равна сумме попарно возведенных евклидовых расстояний, деленной на количество точек; и (b) знать, как вычислять расстояния между центроидами кластеров из матрицы расстояний ; (c) и мы также знаем, как суммы квадратов взаимосвязаны в K-средних. Все вместе делает написание алгоритма, который вы хотите, простым и не сложным делом. Однако следует помнить, что K-средства предназначены только для евклидовых расстояний / евклидова пространства. Используйте K-medoids или другие методы для неевклидовых расстояний.

Похожий вопрос .

ttnphns
источник
7

Я, конечно, не знаю, как это «обычно» делается, и, к сведению, я не знаю много о кластерном анализе. Тем не менее, вы знакомы с многомерным масштабированием ? ( Вот еще одна ссылка, вики , и вы можете искать CV по тегу .) Многомерное масштабирование принимает матрицу попарных расстояний, что звучит как ваша ситуация. С помощью MDS вы можете получить расположение объектов в пространстве самого низкого размера, необходимое для их адекватного представления. Я предполагаю, что вы можете использовать эти места для последующего кластерного анализа, например, k-means; в качестве альтернативы, если у вас есть выходные данные, вам может больше не понадобиться ЦС.

Я не знаю, используете ли вы R, но вот представление задач для Psychometrics, которое включает в себя раздел о MDS в R. Надежда, которая помогает.

Gung - Восстановить Монику
источник
4

К

В вашем случае, что вам в основном нужно сделать, это:

  1. D
  2. DяJDJя
  3. Dс
  4. Sсзнак равно-12Dс
  5. SсSсS~с
  6. S~сзнак равноВΛВ
  7. N-1Иксзнак равноВΛ1/2

N

blubb
источник
Описанные шаги - не что иное, как Анализ основных координат, который я упоминаю в своем ответе.
ttnphns
Пожалуйста, проиллюстрируйте ваш шаг 5. Вычитание последнего (отрицательного) собственного значения из S элементов матрицы, похоже, не помогает сделать S положительным полуопределенным.
ttnphns
@ttnphns: Да, в основном это PCA, но для этого не требуется, чтобы расстояния были метрическими. Описание шага 5 было неудачным, спасибо, что заметили его. Теперь понятно?
blubb
Вычитание суммы отрицательных собственных значений из всех собственных значений, а затем восстановление матрицы S эквивалентно вычитанию этой суммы из диагональных элементов S. Это endeed делает S положительным (полу) определенным, но ...
ttnphns
... но этот способ очень плох в том смысле, что полученные в результате евклидовы данные X дают евклидовы расстояния D_new, которые очень далеки от первоначальных различий D. Итак, я бы не рекомендовал ваш шаг 5. Кажется, гораздо лучше просто установить отрицательное Собственные значения равны 0 и переходите к шагу 7. Или, немного более точный подход: установите отрицательные собственные значения равными 0, измените масштаб положительных собственных значений, чтобы их сумма была оригинальной (= trace (S)), а затем перейдите к шагу 7. Вот как это выглядит мне.
ttnphns
2

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

micans
источник
2

Я не знаю, почему это так редко встречается в литературе, однако решение, предложенное @gung и @ttnphns (сначала спроецируйте ваши попарные расстояния в евклидово пространство, используя анализ главных координат, например, через этот пакет, если вы используете R, а затем выполнение K-означает обычный способ) является простым и не требует специализированных алгоритмов. Я лично использовал его здесь, встроенный в каркас оптимизации, и он работал довольно хорошо.

Франческо Наполитано
источник
1

Что касается кластеризации и MDS, я бы предложил следующие ресурсы:

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

user1137731
источник