Кластеризация с матрицей расстояний

52

У меня есть (симметричная) матрица, Mкоторая представляет расстояние между каждой парой узлов. Например,

    ABCDEFGHIJKL
A 0 20 20 20 40 60 60 60 100 120 120 120
B 20 0 20 20 60 80 80 80 120 140 140 140
C 20 20 0 20 60 80 80 80 120 140 140 140
Д 20 20 20 0 60 80 80 80 120 140 140 140
E 40 60 60 60 0 20 20 20 60 80 80 80
F 60 80 80 80 20 0 20 20 40 60 60 60
G 60 80 80 80 20 20 0 20 60 80 80 80
H 60 80 80 80 20 20 20 0 60 80 80 80
Я 100 120 120 120 60 40 60 60 0 20 20 20
J 120 140 140 140 80 60 80 80 20 0 20 20
К 120 140 140 140 80 60 80 80 20 20 0 20
L 120 140 140 140 80 60 80 80 20 20 20 0

Существует ли какой-либо метод для извлечения кластеров M(при необходимости, количество кластеров можно фиксировать), чтобы каждый кластер содержал узлы с небольшими расстояниями между ними. В примере, кластеры бы (A, B, C, D), (E, F, G, H)и (I, J, K, L).

Я уже пробовал UPGMA и k-means, но получающиеся кластеры очень плохие.

Расстояния - это средние шаги, которые должен сделать случайный ходок, чтобы пройти от узла Aк узлу B( != A) и вернуться к узлу A. Гарантируется, что M^1/2это показатель. Для запуска k-значений я не использую центроид. Я определяю расстояние между nкластерами узлов cкак среднее расстояние между nвсеми узлами в c.

Большое спасибо :)

Ясин
источник
1
Вы должны рассмотреть возможность добавления информации, которую вы уже пробовали UPGMA (и других, которые вы, возможно, пробовали) :)
Björn Pollex
1
У меня есть вопрос. Почему вы сказали, что k-means плохо работает? Я передал вашу Матрицу k-means, и она отлично сгруппировалась. Разве вы не передали значение k (количество кластеров) в k-means?
3
@ user12023 Я думаю, вы неправильно поняли вопрос. Матрица - это не серия точек, а попарные расстояния между ними. Вы не можете вычислить центр тяжести набора точек, когда вы только расстояния между ними (а не их фактические координаты), по крайней мере, не очевидным образом.
Stumpy Джо Пит
7
k-means не поддерживает дистанционные матрицы . Он никогда не использует расстояния от точки к точке. Так что я могу только предположить, что он, должно быть, переосмыслил вашу матрицу как векторы и работал на этих векторах ... возможно, то же самое произошло с другими алгоритмами, которые вы пробовали: они ожидали необработанные данные , а вы пропустили матрицу расстояний.
Anony-Mousse

Ответы:

38

Есть несколько вариантов.

К-медоиды кластеризации

Во-первых, вы можете попробовать разделить медоиды (pam) вместо использования кластеризации k-средних. Этот более надежный и может дать лучшие результаты. Ван дер Лаан переработал алгоритм. Если вы собираетесь реализовать это самостоятельно, его статью стоит прочитать.

Существует специальный алгоритм кластеризации k-medoids для больших наборов данных. Алгоритм называется «Клара в R» и описан в главе 3 « Поиск групп в данных: введение в кластерный анализ». Кауфман, L и Руссеув, PJ (1990).

иерархическая кластеризация

Вместо UPGMA вы можете попробовать другие варианты иерархической кластеризации. Прежде всего, когда вы используете иерархическую кластеризацию, убедитесь, что вы правильно определили метод разделения. Этот метод разделения по сути является тем, как рассчитываются расстояния между наблюдениями и кластерами. Я в основном использую метод Уорда или полную связь, но другие варианты могут быть выбором для вас.

Не знаю, пытались ли вы это сделать, но метод одиночной связи или соседнего соединения часто предпочтительнее UPGMA в филогенетических приложениях. Если вы еще не попробовали, вы могли бы также попробовать, так как это часто дает удивительно хорошие результаты.


В R вы можете взглянуть на кластер пакетов . Все описанные алгоритмы реализованы там. Смотрите «pam», «clara», «hclust, ...». Проверьте также другую реализацию алгоритма в «kmeans». Иногда выбор другого алгоритма может существенно улучшить кластеризацию.


РЕДАКТИРОВАТЬ: Просто подумал о чем-то: если вы работаете с графиками и узлами и тому подобное, вы должны взглянуть на алгоритм кластеризации Маркова. Этот используется, например, в группировке последовательностей, основанных на сходстве взрыва, и работает невероятно хорошо. Он может сделать кластеризацию для вас, или дать вам некоторые идеи о том, как решить проблему исследования, на которой вы сосредоточены. На самом деле, ничего не зная об этом, я думаю, его результаты определенно стоит посмотреть. Если можно так сказать, я все еще считаю этот метод Стийна ван Донгена одним из самых приятных результатов в кластеризации, с которыми я когда-либо сталкивался.

http://www.micans.org/mcl/

Йорис Мейс
источник
22

Одним из способов выделения кластеров в матрице расстояний является многомерное масштабирование . При проецировании отдельных лиц (в данном случае вы называете ваши узлы) в 2D-пространство, оно обеспечивает сопоставимое решение с PCA. Это не контролируется, поэтому вы не сможете указать априори количество кластеров, но я думаю, что это может помочь быстро суммировать заданное расстояние или матрицу сходства.

Вот что вы получите с вашими данными:

tmp <- matrix(c(0,20,20,20,40,60,60,60,100,120,120,120,
                20,0,20,20,60,80,80,80,120,140,140,140,
                20,20,0,20,60,80,80,80,120,140,140,140,
                20,20,20,0,60,80,80,80,120,140,140,140,
                40,60,60,60,0,20,20,20,60,80,80,80,
                60,80,80,80,20,0,20,20,40,60,60,60,
                60,80,80,80,20,20,0,20,60,80,80,80,
                60,80,80,80,20,20,20,0,60,80,80,80,
                100,120,120,120,60,40,60,60,0,20,20,20,
                120,140,140,140,80,60,80,80,20,0,20,20,
                120,140,140,140,80,60,80,80,20,20,0,20,
                120,140,140,140,80,60,80,80,20,20,20,0),
              nr=12, dimnames=list(LETTERS[1:12], LETTERS[1:12]))
d <- as.dist(tmp)
mds.coor <- cmdscale(d)
plot(mds.coor[,1], mds.coor[,2], type="n", xlab="", ylab="")
text(jitter(mds.coor[,1]), jitter(mds.coor[,2]),
     rownames(mds.coor), cex=0.8)
abline(h=0,v=0,col="gray75")

МДС

Я добавил небольшое дрожание в координатах x и y, чтобы можно было различать случаи. Замените tmpна, 1-tmpесли вы предпочитаете работать с различиями, но это дает по существу ту же картину. Однако, здесь есть иерархическая кластерное решение, с отдельными критериями агломерационных:

plot(hclust(dist(1-tmp), method="single"))

Нс

Вы могли бы дополнительно уточнить выбор кластеров на основе дендрограммы или более надежных методов, см., Например, этот связанный вопрос: Какие стоп-критерии для агломерационной иерархической кластеризации используются на практике?

хл
источник
2

K

L=D1/2AD1/2

ADAij=1dij/max(d)

{Di,i=jAi,jDij=0

Поскольку является собственным разложением , а собственные функции располагаются в виде столбцов, сохраняя только самых больших собственных векторов в , мы определяем матрицу нормализованную строкуL K XXLKX

Yij=Xij(j(Xij)2)1/2

Каждая строка является точкой в и может быть сгруппирована с помощью обычного алгоритма кластеризации (например, K-средних).R kYRk

Посмотрите на мой ответ здесь, чтобы увидеть пример: https://stackoverflow.com/a/37933688/2874779


[1] Ng, AY, Jordan, MI & Weiss, Y. (2002). О спектральной кластеризации: анализ и алгоритм. Достижения в нейронных системах обработки информации, 2, 849-856. Pg.2

поджигатель
источник
2

Вы пытаетесь объединить узлы графа или сети, которые расположены близко друг к другу. Существует целая область исследований, посвященная этой проблеме, которую иногда называют обнаружением сообщества в сетях . Глядя на вашу проблему с этой точки зрения, возможно, можно прояснить ситуацию.

Вы найдете много алгоритмов, посвященных этой проблеме, и на самом деле некоторые из них основаны на той же идее, что и у вас, а именно на измерении расстояний между узлами при случайных блужданиях.

Проблема часто формулируется как оптимизация модульности [1], где модульность кластеризации измеряет, насколько хорошо кластеризация разделяет сеть на плотно связанные кластеры (то есть кластеры, где узлы расположены близко друг к другу).

Фактически, вы можете показать, что модульность равна вероятности того, что случайный бродяга останется после одного шага в одних и тех же кластерах, чем изначально, минус одинаковая вероятность для двух независимых случайных бродяг [2].

Если вы допускаете больше шагов случайных бродяг, вы ищете более грубую кластеризацию сети. Следовательно, число шагов случайного обхода играет роль параметра разрешения, который позволяет восстановить иерархию кластеров. В этом случае величина, которая выражает тенденцию случайных бродяг оставаться в своем начальном кластере после t шагов, называется марковской устойчивостью разбиения в момент времени t [2], и она эквивалентна модульности при t = 1 .

Поэтому вы можете решить вашу проблему, найдя кластеризацию вашего графа, которая оптимизирует стабильность в данный момент времени t , где t - параметр разрешения (большее t даст вам большие кластеры). Одним из наиболее часто используемых методов оптимизации стабильности (или модульности с параметром разрешения) является алгоритм Лувена [3]. Вы можете найти реализацию здесь: https://github.com/michaelschaub/generalizedLouvain .

[1] Newman, MEJ & Girvan, M. Поиск и оценка структуры сообщества в сетях. Phys. Rev. E 69, 026113 (2004).

[2] Delvenne, J.-C., Yaliraki, SN & Barahona, M. Устойчивость графовых сообществ в масштабах времени. Proc. Natl. Акад. Sci. 107, 12755–12760 (2010).

[3] Blondel, VD, Guillaume, J.-L., Lambiotte, R. & Lefebvre, E. Быстрое развертывание сообществ в больших сетях. J. Stat. Мех. Теория Эксп. 2008, P10008 (2008).

Алекс Б
источник
1

Что ж, можно выполнить кластеризацию K-средних на заданной матрице подобия, сначала вам нужно отцентрировать матрицу, а затем взять собственные значения матрицы. Последний и самый важный шаг - это умножение первых двух наборов собственных векторов на квадратный корень из диагоналей собственных значений, чтобы получить векторы, а затем двигаться дальше с помощью K-средних. Ниже код показывает, как это сделать. Вы можете изменить матрицу сходства. fpdist - это матрица сходства.

mds.tau <- function(H)
{
  n <- nrow(H)
   P <- diag(n) - 1/n
   return(-0.5 * P %*% H %*% P)
  }
  B<-mds.tau(fpdist)
  eig <- eigen(B, symmetric = TRUE)
  v <- eig$values[1:2]
#convert negative values to 0.
v[v < 0] <- 0
X <- eig$vectors[, 1:2] %*% diag(sqrt(v))
library(vegan)
km <- kmeans(X,centers= 5, iter.max=1000, nstart=10000) .
#embedding using MDS
cmd<-cmdscale(fpdist)
user4959
источник
0

Прежде чем вы попытаетесь запустить кластеризацию на матрице, вы можете попробовать применить один из методов факторного анализа и сохранить только самые важные переменные для вычисления матрицы расстояний. Другая вещь, которую вы можете сделать, это попробовать использовать нечеткие методы, которые, как правило, работают лучше (по крайней мере, по моему опыту) в таких случаях, попробуйте сначала Cmeans, Fuzzy K-medoids и Special GKCmeans.

Мариана Софер
источник
0

Совместная кластеризация является одним из ответов, я думаю. Но я не эксперт здесь. Совместная кластеризация не является методом новорожденного, поэтому вы можете найти некоторые алгоритмы в R, вики показывает, что концепции в хорошем смысле. Другой метод, который не подразумевается, - это разбиение графа (но я вижу, что граф не будет разреженным, разбиение графа было бы полезно, если в вашей матрице преобладают значения, означающие = максимальное расстояние = нет сходства между узлами).

Qbik
источник
0

Посмотрите на РАСПРЕДЕЛЕНИЕ AFFINITY. Этот метод использует в качестве входных данных матрицу сходства и создает оптимальное количество кластеров вместе с характерным примером для каждого кластера.

Джавад Тайюб
источник
2
Не могли бы вы рассказать об этом и объяснить, как этот метод помогает в этом случае?
Энди
0

Сначала преобразуйте матрицу расстояний в матрицу координат через https://math.stackexchange.com/a/423898, после чего вы сможете легко и эффективно использовать любой существующий алгоритм кластеризации.

Майкл Эйвери
источник
0

Вы также можете использовать алгоритм Крускала для нахождения минимальных остовных деревьев, но заканчивая, как только вы получите три кластера. Я пробовал таким образом, и он производит кластеры, которые вы упомянули: {ABCD}, {EFGH} и {IJKL}.

Луис Паргас Кармона
источник