Czy można używać odległości Manhattan z połączeniem między klastrami Warda w hierarchicznym klastrowaniu?

15

Korzystam z hierarchicznego grupowania do analizy danych szeregów czasowych. Mój kod jest implementowany za pomocą funkcji MathematicaDirectAgglomerate[...] , która generuje hierarchiczne klastry przy następujących danych wejściowych:

macierz odległości D
nazwa metody zastosowanej do ustalenia powiązania między klastrami.

Obliczyłem macierz odległości D na podstawie odległości Manhattan:

d (x, y) = \sum_{i} | x_{i} - y_{i} |

$d(x,y) = \sum_i|x_i - y_i|$

$i = 1,\cdots, n$ $n \approx 150$

Moje pytanie brzmi: czy można używać połączenia między klastrami Warda z macierzą odległości Manhattanu? Niektóre źródła sugerują, że powiązanie Totemu powinno być używane tylko z odległością euklidesową.

DirectAgglomerate[...] $c$

(\sum_{j} | | c_{j} - m e a n (c) | |_{2})^{2}

$(\sum_j||c_j - mean(c)||_2)^2$

(Inne narzędzia programowe, takie jak Matlab i R, również implementują grupowanie Warda za pomocą tylko macierzy odległości, więc pytanie nie jest specyficzne dla Mathematica.)

clustering distance-functions ward

— Rachel
źródło

Niedawno przeanalizowałem dość duży zestaw danych przy użyciu metody Warda. W moim konkretnym przypadku odległość Manatthana dawała zasadniczo takie samo skupienie jak odległość euklidesowa. Nie mogę podać żadnego matematycznego dowodu na korzyść jakiejkolwiek kombinacji metod, ale - przynajmniej w moim przypadku

— nico

Wszystkie funkcje R niekoniecznie czekają na macierz odległości. Zobacz np. Pomoc online agnesw pakiecie klastra .

— chl

Właściwie można używać dowolnej odległości. Sprawdź vlado.fmf.uni-lj.si/pub/preprint/ward.pdf Jedynym haczykiem jest to, że środek, o którym mówimy, nie jest już średnią arytmetyczną, ale średnią Frecheta.

— Randy Lai

ale czy możemy użyć dystansu manhattan do pełnego połączenia?

— Payel Banerjee

8

Algorytm grupowania totemów jest hierarchiczną metodą grupowania, która minimalizuje kryteria „bezwładności” na każdym etapie. Ta bezwładność określa ilościowo sumę kwadratów reszt pomiędzy sygnałem zredukowanym a sygnałem początkowym: jest to miara wariancji błędu w sensie l2 (euklidesowym). Właściwie nawet wspominasz o tym w swoim pytaniu. Dlatego uważam, że nie ma sensu stosować go do macierzy odległości, która nie jest odległością euklidesową 12.

Z drugiej strony przeciętne połączenie lub hierarchiczne grupowanie pojedynczego połączenia byłoby idealnie odpowiednie dla innych odległości.

— Gael Varoquaux
źródło

2

Dzięki za komentarz; Myślę że masz rację. Jednak w praktyce wydaje się, że powiązanie Warda jest często stosowane przy odległościach innych niż euklidesowe. Nadal nie jestem pewien, jakie mogą być tego konsekwencje.

— Rachel

Prawdopodobnie pochodzi od osób używających Totem tylko dlatego, że jest dobrze znany. Powiedziałbym, że Ward nie przynosi żadnego zysku w porównaniu do przeciętnego powiązania w tych ustawieniach. Jest to jednak bardziej kosztowne obliczeniowo (musisz obliczyć pierwsze dwa momenty dla każdego scalenia lub je wstępnie obliczyć). Zatem z pragmatycznego punktu widzenia po prostu wybrałbym przeciętne powiązanie.

— Gael Varoquaux,

1

W rzeczywistości bezwładność byłaby określona za pomocą sumy do kwadratu odległości (nie musi być euklidesowe) patrz vlado.fmf.uni-lj.si/pub/preprint/ward.pdf

— Randy Lai

5

Nie mogę wymyślić żadnego powodu, dla którego Totem powinien faworyzować jakąkolwiek metrykę. Metoda Totemu jest kolejną opcją, która decyduje, które klastry zostaną połączone podczas aglomeracji. Osiąga się to poprzez znalezienie dwóch klastrów, których połączenie zminimalizuje pewien błąd ( przykładowe źródło formuły ).

Dlatego opiera się na dwóch koncepcjach:

Średnia wektorów, która (dla wektorów numerycznych) jest na ogół obliczana przez uśrednienie dla każdego wymiaru osobno.
Sama metryka odległości, tj. Pojęcie podobieństwa wyrażone przez tę metrykę.

Tak więc: dopóki właściwości wybranej metryki (takie jak np. Rotacja, tłumaczenie lub niezmienność skali) zaspokoją twoje potrzeby (a metryka pasuje do sposobu obliczania średniej klastra), nie widzę powodu, aby z niej nie korzystać .

Podejrzewam, że większość ludzi sugeruje metrykę euklidesową, ponieważ oni

chcą zwiększyć wagę różnic między średnią skupień a pojedynczym wektorem obserwacji (co odbywa się za pomocą kwadratu)
lub ponieważ okazało się, że jest to najlepszy wskaźnik w sprawdzaniu poprawności na podstawie ich danych
lub ponieważ jest używany ogólnie.

— steffen
źródło

Dzięki za twoją odpowiedź. Wyjaśniłem trochę moje pytanie, aby podkreślić, że algorytm „DirectAgglomerate [...]” przyjmuje tylko macierz odległości. Biorąc to pod uwagę, czy zmodyfikowana implementacja powiązania Warda byłaby oparta na założeniu, że Macierz odległości jest euklidesowa? Na przykład implementacja powiązania Warda przez Matlaba zauważa, że jest on odpowiedni tylko dla odległości euklidesowych ( mathworks.com/help/toolbox/stats/linkage.html ).

— Rachel

1

@Rachel: aaah, rozumiem. Każda implementacja totemu musi obliczyć odległość między członami klastra a środkiem ciężkości. Intuicyjnie jasne jest, że metryka zastosowana do tego celu powinna być równoważna metryki zastosowanej do obliczenia odległości między obserwacjami ... stąd Matlab wymaga Distymrix euklidesowej. Ale teraz pojawia się pytanie, dlaczego implementacje nie żądają funkcji zamiast macierzy odległości? Ile szkód wyrządza się, gdy do obu zadań używa się różnych mierników? Przyznaję, nie wiem tego dobrze wiem.

— steffen

cześć przykład usunięty. jakaś inna strona internetowa?

— MonsterMMORPG,

2

$\ell_1$ $\ell_1$ $\ell_1$

— Suresh Venkatasubramanian
źródło