Czy odległość musi być „metryką”, aby hierarchiczna klastracja była na niej ważna?

9

Powiedzmy, że definiujemy odległość, która nie jest miarą , między N elementami.

Na podstawie tej odległości stosujemy następnie aglomeracyjne hierarchiczne grupowanie .

Czy możemy zastosować każdy ze znanych algorytmów (połączenie pojedyncze / maksymalne / średnie itp.), Aby uzyskać znaczące wyniki? Lub inaczej: jaki jest problem z ich użyciem, jeśli odległość nie jest metryką?

— Tal Galili
źródło

Jakie są „przedmioty” w twoim przypadku? (Pytam, czy to ma coś wspólnego z psychometrią, ponieważ w takim przypadku poleciłbym przyjrzenie się grupowaniu przedmiotów lub Revelle, W. Hierarchiczna analiza skupień i ich wewnętrzna struktura testów , MBR (1979) 14 : 57.)

— chl.

7

Wymagania dotyczące odległości zależą od metody hierarchicznego grupowania. Pojedyncze, kompletne, średnie metody wymagają odległości, aby nie były ujemne i symetryczne. Metody totemów, centroidów i median potrzebują (kwadratowych) euklidesowych (które są nawet węższe definicji niż metryki) odległości, aby uzyskać geometrycznie znaczące wyniki.

(Można sprawdzić, czy jego macierz odległości jest euklidesowa, podwójnie centrując ją [patrz moja odpowiedź tutaj ] i patrząc na wartości własne; jeśli nie znaleziono ujemnych wartości własnych, odległości zbiegają się w przestrzeni euklidesowej.)

— ttnphns
źródło

Dzięki. Dalsze pytanie: czy nierówność trójkąta musi dotyczyć pojedynczych, pełnych, średnich metod? a jeśli pewna odległość nie jest (na przykład) niesymetryczna, jaki problem stwarza dla tych metod? (Dzięki!)

— Tal Galili

1

Klasyczne hierarchiczne metody grupowania mogą przyjmować wyłącznie macierz symetryczną: odległość od A do B = od B do A. Istnieją inne specjalne metody radzenia sobie z asymetryczną (możesz google). Jeśli chodzi o nierówności trójkątne - nie jest to warunek konieczny dla wymienionych metod. (Jednak powszechna mądrość uważa „odległość” za coś z nierównością, dlatego warto rozważyć nałożenie go, jeśli go brakuje. Aby to zrobić, dodaj iteracyjnie małą stałą do odległości i sprawdź. A jeśli będziesz dalej dodawać po osiągnięciu to niedługo przybędziesz na odległości euklidesowe)

— ttnphns

5

Nie, odległość nie musi być metryką. Może to być na przykład ultrametryczny:

d (A, B) \leq max (d (A, C), d (B, C))

$d(A, B) \le \max(d(A, C), d(B, C))$

Odległości ultradźwiękowe uzyskane z kolejnych kroków w algorytmie grupowania można przedstawić za pomocą dendrogramów, które mogłeś zobaczyć w tym kontekście.

— Hong Ooi
źródło

Dziękuję Hong. Pamiętam, że metody przekształcania niektórych obiektów w hclust wymagają, aby dendrogram był ultrametryczny - zraszam, jeśli ma to związek z tym, co napisałeś. W każdym razie dziękuję za odpowiedź.

— Tal Galili