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

У меня есть (симметричная) матрица, 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.

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

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

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

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

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

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

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

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

---

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

---

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

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

Одним из способов выделения кластеров в матрице расстояний является многомерное масштабирование . При проецировании отдельных лиц (в данном случае вы называете ваши узлы) в 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"))

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

$K$

$$\textbf{L} = \textbf{D}^{-1/2} \textbf{A} \textbf{D}^{-1/2}$$

$\textbf{A}$$\textbf{D}$$A_{ij}=1-d_{ij}/\max(d)$

$$\left\{\begin{matrix}\begin{align}&\textbf{D}_{i,i}=\sum_{j}{\textbf{A}_{i,j}}\\ &\textbf{D}_{i \neq j}=0\end{align}\end{matrix}\right.$$

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

$$\textbf{Y}_{ij}=\frac{\textbf{X}_{ij}}{\left(\sum_{j}{\left( \textbf{X}_{ij} \right)^{2}}\right)^{1/2}}$$

Каждая строка является точкой в и может быть сгруппирована с помощью обычного алгоритма кластеризации (например, K-средних).R $\textbf{Y}$$\mathbb{R}^{k}$

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

---

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

Что ж, можно выполнить кластеризацию 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)

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

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

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

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

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