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ą?

clustering multilevel-analysis metric hierarchical-clustering 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.

Odpowiedzi:

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