/ / Групиране с матрица на разстояние - алгоритъм, матрица, клъстър-анализ, разстояние

Групиране с матрица на разстояние - алгоритъм, матрица, клъстер-анализ, разстояние

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

А Б В Г Д Е Ж З И Й К Л А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 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 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).

Благодаря много :)

Отговори:

7 за отговор № 1

Йерархично групиране работи директно с матрицата за разстояниеот действителните наблюдения. Ако знаете броя на клъстерите, вече ще знаете критерия за спиране (спрете, когато има к клъстери). Основният трик тук ще бъде да изберете подходящ свързващ метод, Също, тази хартия(pdf) дава отличен преглед на всички видове методи за клъстеризиране.


2 за отговор № 2

Използва се още един възможен начин Разделяне около медиоиди който често се нарича K-Medoids. Ако погледнете пакета R-clustering, ще видите Пам която получава матрицата на разстоянието като входни данни.


0 за отговор № 3

Е, възможно е да се извършат К-средствагрупиране на дадена матрица на приликата, първо трябва да центрирате матрицата и след това да вземете собствените стойности на матрицата. Последната и най-важната стъпка е умножаването на първите два комплекта собствени вектори на квадратен корен на диагоналите на собствените стойности, за да се получат векторите и след това да се премине с К-средства. По-долу кодът показва как да го направите. Можете да промените матрицата на приликите. 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)