Grupowanie za pomocą macierzy odległości

Mam (symetryczną) macierz, Mktóra reprezentuje odległość między każdą parą węzłów. Na przykład,

    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
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 120140 140 140 80 60 80 80 20 20 0 20
L 120 140 140 140 80 60 80 80 20 20 20 0

Czy istnieje metoda wyodrębniania klastrów M(w razie potrzeby można ustalić liczbę klastrów), tak aby każdy klaster zawierał węzły o niewielkich odległościach między nimi. Na przykład, klastry byłoby (A, B, C, D), (E, F, G, H)i (I, J, K, L).

Próbowałem już UPGMA i k-means, ale powstałe klastry są bardzo złe.

Odległości są średnimi krokami, które wykonałby przypadkowy chodzik, aby przejść od węzła Ado węzła B( != A) i wrócić do węzła A. Jest gwarantowane, że M^1/2to metryka. Aby uruchomić k-means, nie używam centroidu. Definiuję odległość między nskupieniem węzłów cjako średnią odległość między nwszystkimi węzłami i c.

Wielkie dzięki :)

Istnieje wiele opcji.

Grupowanie k-medoidów

Po pierwsze, możesz spróbować podzielić na partycje wokół medoidów (pam) zamiast używać klastrowania k-średnich. Ten jest bardziej solidny i może dawać lepsze wyniki. Van der Laan przerobił algorytm. Jeśli zamierzasz wdrożyć go sam, jego artykuł jest wart przeczytania.

Istnieje specjalny algorytm grupowania k-medoidów dla dużych zestawów danych. Algorytm nazywa się Clara w R i jest opisany w rozdziale 3 Znajdowanie grup w danych: Wprowadzenie do analizy skupień. autorzy: Kaufman, L i Rousseeuw, PJ (1990).

grupowanie hierarchiczne

Zamiast UPGMA możesz wypróbować inne hierarchiczne opcje klastrowania. Przede wszystkim, gdy korzystasz z hierarchicznego klastrowania, upewnij się, że poprawnie zdefiniowałeś metodę partycjonowania. Ta metoda podziału jest zasadniczo sposobem obliczania odległości między obserwacjami a skupieniami. Najczęściej używam metody Warda lub pełnego powiązania, ale inne opcje mogą być dla ciebie wyborem.

Nie wiem, czy już go wypróbowałeś, ale w aplikacjach filogenetycznych często preferowana jest metoda pojedynczego łączenia lub łączenie sąsiadów nad UPGMA. Jeśli jeszcze tego nie wypróbowałeś, możesz również spróbować, ponieważ często daje to wyjątkowo dobre wyniki.

---

W R możesz spojrzeć na klaster pakietów . Wszystkie opisane algorytmy są tam zaimplementowane. Zobacz? Pam,? Clara,? Hclust, ... Sprawdź także inną implementację algorytmu w? Kmeans. Czasami wybranie innego algorytmu może znacznie poprawić klastrowanie.

---

EDYCJA: Pomyślałem o czymś: jeśli pracujesz z wykresami i węzłami oraz polubieniami, powinieneś również przyjrzeć się algorytmowi klastrowania markowa. Ten jest używany na przykład w grupowaniu sekwencji na podstawie podobieństwa wybuchu i działa niesamowicie dobrze. Może zrobić dla Ciebie grupowanie lub dać kilka pomysłów na rozwiązanie problemu badawczego, na którym się koncentrujesz. Nie wiedząc nic na ten temat, sądzę, że zdecydowanie warto przyjrzeć się jego wynikom. Jeśli mogę tak powiedzieć, nadal uważam tę metodę Stijn van Dongen za jeden z najładniejszych wyników w grupowaniu, jakie kiedykolwiek spotkałem.

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

Jednym ze sposobów wyróżnienia klastrów w macierzy odległości jest skalowanie wielowymiarowe . Podczas projekcji osób (tutaj, jak to nazywacie waszymi węzłami) w przestrzeni 2D, zapewnia porównywalne rozwiązanie do PCA. Nie jest to nadzorowane, więc nie będziesz mógł z góry określić liczby klastrów, ale myślę, że może to pomóc w szybkim podsumowaniu danej macierzy odległości lub podobieństwa.

Oto, co możesz uzyskać ze swoimi danymi:

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")

Dodałem małe drgania na współrzędnych xiy, aby umożliwić rozróżnianie przypadków. Zamień tmpna, 1-tmpjeśli wolisz pracować z odmiennościami, ale daje to zasadniczo ten sam obraz. Oto jednak hierarchiczne rozwiązanie klastrowe z kryteriami pojedynczej aglomeracji:

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

Możesz dodatkowo udoskonalić wybór klastrów w oparciu o dendrogram lub bardziej niezawodne metody, patrz np. To powiązane pytanie: Jakie kryteria stop dla aglomeracyjnego hierarchicznego klastrowania są stosowane w praktyce?

Grupowanie widmowe [1] wymaga macierzy powinowactwa, grupowanie jest zdefiniowane przez pierwszych funkcji własnych rozkładu$K$

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

Gdy jest macierzą powinowactwa danych, a jest macierzą diagonalną zdefiniowaną jako (edytuj: przepraszam za niejasność, ale możesz wygenerować macierz powinowactwa z macierzy odległości pod warunkiem, że znasz maksimum możliwe / rozsądna odległość jako , chociaż istnieją również inne schematy)$\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.$$

Ponieważ jest składową elektroniczną , z funkcjami własnymi ułożonymi jako kolumny, zachowując tylko największych wektorów własnych w , definiujemy macierz znormalizowaną$\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}}$$

Każdy wiersz jest punktem w i może być grupowany za pomocą zwykłego algorytmu grupowania (np. K-średnich).$\textbf{Y}$$\mathbb{R}^{k}$

Spójrz na moją odpowiedź tutaj, aby zobaczyć przykład: https://stackoverflow.com/a/37933688/2874779

---

_{[1] Ng, AY, Jordan, MI i Weiss, Y. (2002). Na temat grupowania widmowego: analiza i algorytm. Postępy w neuronowych systemach przetwarzania informacji, 2, 849–856. Str.2}

Próbujesz zgromadzić razem węzły wykresu lub sieci, które są blisko siebie. Istnieje cała dziedzina badań poświęcona temu problemowi, która jest czasami nazywana wykrywaniem społeczności w sieciach . Patrząc na problem z tego punktu widzenia, prawdopodobnie można to wyjaśnić.

Znajdziesz wiele algorytmów poświęconych temu problemowi, a niektóre z nich opierają się na tej samej idei, którą miałeś, a mianowicie na pomiarze odległości między węzłami za pomocą losowych spacerów.

Problem jest często formułowany jako optymalizacja modułowości [1], w której modułowość klastra mierzy, jak dobrze klaster dzieli sieć w gęsto połączonych klastrach (tj. Klastrach, w których węzły są blisko siebie).

W rzeczywistości możesz pokazać, że modułowość jest równa prawdopodobieństwu, że losowy walker pozostaje, po jednym kroku, w tych samych klastrach, niż początkowo minus to samo prawdopodobieństwo dla dwóch niezależnych walkerów [2].

Jeśli zezwolisz na więcej kroków losowych spacerowiczów, szukasz bardziej zgrubnego grupowania sieci. Liczba kroków losowego przejścia odgrywa zatem rolę parametru rozdzielczości, który pozwala odzyskać hierarchię klastrów. W tym przypadku ilość wyrażająca tendencję losowych spacerowiczów do pozostania w początkowej grupie po t krokach nazywa się stabilnością Markowa podziału w czasie t [2] i jest równoważna modułowości, gdy t = 1 .

Możesz zatem rozwiązać swój problem, znajdując klaster wykresu, który optymalizuje stabilność w danym czasie t , gdzie t jest parametrem rozdzielczości (większe t da większe klastry). Jedną z najczęściej stosowanych metod optymalizacji stabilności (lub modułowości z parametrem rozdzielczości) jest algorytm Louvaina [3]. Implementację można znaleźć tutaj: https://github.com/michaelschaub/generalizedLouvain .

[1] Newman, MEJ i Girvan, M. Znajdowanie i ocena struktury społeczności w sieciach. Phys. Rev. E 69, 026113 (2004).

[2] Delvenne, J.-C., Yaliraki, SN i Barahona, M. Stabilność społeczności grafów w różnych skalach czasowych. Proc. Natl. Acad Sci. 107, 12755–12760 (2010).

[3] Blondel, VD, Guillaume, J.-L., Lambiotte, R. & Lefebvre, E. Szybki rozwój społeczności w dużych sieciach. J. Stat. Mech Teoria Exp. 2008, P10008 (2008).

Cóż, możliwe jest wykonanie grupowania K-środków na danej macierzy podobieństwa, najpierw trzeba wyśrodkować macierz, a następnie wziąć wartości własne macierzy. Ostatnim i najważniejszym krokiem jest pomnożenie dwóch pierwszych zestawów wektorów własnych przez pierwiastek kwadratowy przekątnych wartości własnych, aby uzyskać wektory, a następnie przejść dalej za pomocą średnich K. Poniżej kod pokazuje, jak to zrobić. Możesz zmienić macierz podobieństwa. fpdist jest macierzą podobieństwa.

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)

Zanim spróbujesz uruchomić grupowanie na macierzy, możesz spróbować wykonać jedną z technik analizy czynnikowej i zachować tylko najważniejsze zmienne do obliczenia macierzy odległości. Inną rzeczą, którą możesz zrobić, to spróbować użyć metod rozmytych, które zwykle działają lepiej (przynajmniej z mojego doświadczenia) w tego rodzaju przypadkach, spróbuj najpierw Cmeans, Fuzzy K-medoidów i Specjalnie GKCmeans.

Myślę, że ko-klastrowanie jest jedną z odpowiedzi. Ale nie jestem tutaj ekspertem. Wspólne tworzenie klastrów nie jest metodą nowonarodzoną, więc możesz znaleźć trochę alg w R, wiki pokazuje te koncepcje w dobry sposób. Inną metodą, o której nie wspomniano, jest podział na wykresy (ale widzę, że wykres nie byłby rzadki, podział na wykresy byłby przydatny, gdyby w macierzy dominowały wartości oznaczające = maksymalna odległość = brak podobieństwa między węzłami).

Spójrz na PROPAGACJĘ AFFINITY, Ta technika przyjmuje jako dane wejściowe macierz podobieństwa i tworzy optymalną liczbę klastrów wraz z reprezentatywnym przykładem dla każdego klastra.

Najpierw przekonwertuj macierz odległości na macierz współrzędnych za pośrednictwem https://math.stackexchange.com/a/423898, a następnie będziesz w stanie z łatwością skutecznie wykorzystać dowolny istniejący algorytm grupowania.

Możesz także użyć algorytmu Kruskala do znalezienia drzew o minimalnej rozpiętości, ale kończącego się, gdy tylko zdobędziesz trzy klastry. Próbowałem w ten sposób, aby uzyskać klastry, o których wspomniałeś: {ABCD}, {EFGH} i {IJKL}.