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)=i|xiyi|

i=1,,nn150

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

(j||cjmean(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.)

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

Odpowiedzi:

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:

  1. Średnia wektorów, która (dla wektorów numerycznych) jest na ogół obliczana przez uśrednienie dla każdego wymiaru osobno.
  2. 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

111

Suresh Venkatasubramanian
źródło