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

Question

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

    A   B   C   D   E   F   G   H   I   J   K   L
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
D  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
I 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
K 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).

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

Answer 1

Иерархическая кластеризация работает непосредственно с матрицей расстояний, а не с фактическими наблюдениями. Если вы знаете количество кластеров, вы уже знаете свой критерий остановки (остановитесь, когда есть k кластеров). Основным трюком здесь будет выбор подходящего метода связи . Кроме того, эта статья (pdf) дает превосходный обзор всех видов методов кластеризации.

Answer 2

Еще один возможный способ - использование Разделение вокруг медоидов , которое часто называют K-Medoids.Если вы посмотрите на пакет R-кластеризации, вы увидите функцию pam , которая получает матрицу расстояний в качестве входных данных.

Answer 3

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