Я хочу выполнить кластеризацию K-средних на имеющихся у меня объектах, но объекты не описываются как точки в пространстве, то есть objects x features
набором данных. Тем не менее, я могу вычислить расстояние между любыми двумя объектами (оно основано на функции подобия). Итак, я избавляюсь от матрицы расстояний objects x objects
.
Я реализовал K-средства раньше, но это было с вводом набора данных точек; и с вводом матрицы расстояний мне не ясно, как обновить кластеры, чтобы они были "центрами" кластеров без представления точек. Как это обычно делается? Существуют ли варианты K-средних или методов, близких к этому, для этого?
Ответы:
Очевидно, что k-means должен уметь вычислять средства .
Тем не менее, существует хорошо известная его вариация, известная как k-medoids или PAM (Partitioning Around Medoids), где medoid - это существующий объект, наиболее центральный для скопления. К-медоидам нужны только попарные расстояния.
источник
Вы точно описываете проблему установки ядра -means; когда вы не можете представить точку данных как евклидов вектор, но если вы все еще можете рассчитать (или определить) внутреннее произведение между двумя точками данных, вы можете сгенерировать алгоритм. Следующая веб-страница содержит краткое описание алгоритма:К
Ядро означает страницуК
Этот трюк с ядром является очень популярной и фундаментальной идеей в статистике и машинном обучении.
Вики-страница о трюке с ядром
Если вам интересно, книга Бернхарда Шёлкопфа и Александра Дж. Смолы « Изучение с ядрами» будет очень хорошим введением.
Эта заметка Макса Веллинга кажется очень хорошей; Кроме того , если вы используете R вы посмотрите на может этого R пакет .
MDS может быть одним из способов решения вашей проблемы, но он напрямую не атакует проблему, которую вы хотите решить; в то время как ядро k-means делает.
источник
@gung абсолютно прав, предлагая вам многомерное масштабирование (MDS) в качестве предварительного инструмента для создания
points X dimensions
данных из матрицы расстояний. Я должен добавить только несколько ударов. К-средняя кластеризация подразумевает евклидовы расстояния . MDS даст вам координаты точек в измерениях, тем самым гарантируя вам евклидовы расстояния. Вы должны использовать метрическую MDS и запрашивать максимально возможное количество измерений, потому что ваша цель - минимизировать ошибку повторного преобразования данных, а не отображать их в 2D или 3D.Что если у вас под рукой нет программного обеспечения MDS, но есть некоторые матричные функции, такие как разложение по собственным значениям или разложение по сингулярным значениям? Тогда вы могли бы сделать простую метрическую MDS самостоятельно - Torgerson MDS, также известную как анализ основных координат (PCoA). Это немного «скрученный» анализ главных компонентов. Я не буду описывать это здесь, хотя это довольно просто. Вы можете прочитать об этом во многих местах, например, здесь .
Наконец, можно напрямую запрограммировать «K-средства для ввода матрицы расстояния» - без вызова или записи функций, выполняющих PCoA или другую метрическую MDS. Мы знаем, что (а) сумма квадратов отклонений от центроида равна сумме попарно возведенных евклидовых расстояний, деленной на количество точек; и (b) знать, как вычислять расстояния между центроидами кластеров из матрицы расстояний ; (c) и мы также знаем, как суммы квадратов взаимосвязаны в K-средних. Все вместе делает написание алгоритма, который вы хотите, простым и не сложным делом. Однако следует помнить, что K-средства предназначены только для евклидовых расстояний / евклидова пространства. Используйте K-medoids или другие методы для неевклидовых расстояний.
Похожий вопрос .
источник
Я, конечно, не знаю, как это «обычно» делается, и, к сведению, я не знаю много о кластерном анализе. Тем не менее, вы знакомы с многомерным масштабированием ? ( Вот еще одна ссылка, вики , и вы можете искать CV по тегу многомерного масштабирования .) Многомерное масштабирование принимает матрицу попарных расстояний, что звучит как ваша ситуация. С помощью MDS вы можете получить расположение объектов в пространстве самого низкого размера, необходимое для их адекватного представления. Я предполагаю, что вы можете использовать эти места для последующего кластерного анализа, например, k-means; в качестве альтернативы, если у вас есть выходные данные, вам может больше не понадобиться ЦС.
Я не знаю, используете ли вы R, но вот представление задач для Psychometrics, которое включает в себя раздел о MDS в R. Надежда, которая помогает.
источник
В вашем случае, что вам в основном нужно сделать, это:
источник
Ваши данные также можно просматривать как сеть, и вы можете использовать один из множества доступных алгоритмов сетевой кластеризации. Для этого вам, вероятно, потребуется применить пороговое значение для веса ребер и преобразовать расстояния в сходства. Это не «статистический» способ ведения дел, но кластерный анализ - это недостаточно конкретная проблема для начала, и, поскольку исследовательские инструменты алгоритмов сетевой кластеризации работают очень хорошо.
источник
Я не знаю, почему это так редко встречается в литературе, однако решение, предложенное @gung и @ttnphns (сначала спроецируйте ваши попарные расстояния в евклидово пространство, используя анализ главных координат, например, через этот пакет, если вы используете R, а затем выполнение K-означает обычный способ) является простым и не требует специализированных алгоритмов. Я лично использовал его здесь, встроенный в каркас оптимизации, и он работал довольно хорошо.
источник
Что касается кластеризации и MDS, я бы предложил следующие ресурсы:
Эти ссылки также красиво охватывают темы функций сходства и расстояния (меры близости) для двоичных и непрерывных данных.
источник