Medoid

Medoidy są reprezentatywnymi obiektami zbioru danych lub klastra w zbiorze danych, którego suma różnic w stosunku do wszystkich obiektów w klastrze jest minimalna. Medoidy są podobne w koncepcji do średnich lub centroidów , ale medoidy są zawsze ograniczone do członków zbioru danych. Medoidy są najczęściej używane w przypadku danych, gdy nie można zdefiniować średniej lub środka ciężkości, takich jak wykresy. Są również używane w kontekstach, w których środek ciężkości nie jest reprezentatywny dla zbioru danych, jak na obrazach, trójwymiarowych trajektoriach i ekspresji genów (gdzie podczas gdy dane są rzadkie, medoid nie musi być). Są one również interesujące, gdy chcemy znaleźć przedstawiciela przy użyciu innej odległości niż kwadrat odległości euklidesowej (na przykład w ocenach filmów).

W przypadku niektórych zestawów danych może istnieć więcej niż jeden medoid, jak w przypadku median. Powszechnym zastosowaniem medoidy jest k-medoidów , który jest podobny do algorytmu k-średnich , ale działa, gdy nie można zdefiniować średniej lub środka ciężkości. Algorytm ten zasadniczo działa w następujący sposób. Najpierw losowo wybierany jest zestaw medoidów. Po drugie, obliczane są odległości do innych punktów. Po trzecie, dane są grupowane według medoidu, do którego są najbardziej podobne. Po czwarte, zestaw medoidów jest optymalizowany w procesie iteracyjnym.

Należy zauważyć, że medoid nie jest odpowiednikiem mediany , mediany geometrycznej ani środka ciężkości . Mediana jest definiowana tylko na podstawie danych jednowymiarowych i minimalizuje jedynie odmienność do innych punktów dla metryk indukowanych przez normę ( taką jak odległość Manhattanu lub odległość euklidesowa ). Mediana geometryczna jest zdefiniowana w dowolnym wymiarze, ale niekoniecznie jest punktem z oryginalnego zbioru danych.

Definicja

Niech ${\ textstyle {\ mathcal {X}}: = \ {x_ {1}, x_ {2}, \ kropki, x_ {n} \}}$ być zbiorem $przestrzeni$ z funkcją odległości d . Medoid jest zdefiniowany jako

${\ Displaystyle x _ {\ text {medoid}} = \ arg \ min _ {y \ in {\ mathcal {X}}} \ suma _ {i = 1} ^ {n} d (y, x_ {i}) .}$

Klastrowanie z Medoidami

Główny artykuł: k-medoidy

Medoidy są popularnym zamiennikiem średniej klastra, gdy funkcja odległości nie jest (podniesiona do kwadratu) odległością euklidesową, a nawet nie jest metryką ( ponieważ medoid nie wymaga nierówności trójkąta). Podczas partycjonowania zestawu danych na klastry, medoid każdego klastra może być używany jako reprezentatywny dla każdego klastra.

Algorytmy grupowania oparte na idei medoidów obejmują:

• Partycjonowanie wokół Medoidów (PAM), standardowy algorytm k-medoidów
• Hierarchical Clustering Around Medoids (HACAM), który wykorzystuje medoidy w hierarchicznym grupowaniu

Algorytmy obliczania medoid zbioru

$,$ że ​​medoid zbioru można obliczyć po wszystkich par odległości między punktami w zespole. Wymagałoby to $}$ odległości (z ${\ Displaystyle n = | {\ mathcal {$ ). W najgorszym przypadku nie można obliczyć medoidu przy mniejszej liczbie ocen odległości. Istnieje jednak wiele podejść, które pozwalają nam obliczyć medoidy dokładnie lub w przybliżeniu w czasie subkwadratowym w różnych modelach statystycznych.

$rzeczywistej$ mediany, co można zrobić za pomocą algorytmu szybkiego wyboru Jednak w rzeczywistych przestrzeniach o wyższych wymiarach nie jest znany żaden algorytm czasu liniowego. RAND to algorytm, który szacuje średnią odległość każdego punktu do wszystkich pozostałych punktów poprzez próbkowanie losowego podzbioru innych punktów. Zajmuje w sumie ${\textstyle O\left({\frac {n\log n}{\epsilon ^{2}}}\right)}$ Obliczenia odległości w celu przybliżenia medoidy w ramach współczynnika ${\textstyle (1 +\epsilon \Delta )}$ z dużym prawdopodobieństwem, gdzie ${\textstyle \Delta}$ jest maksymalną odległością między dwoma punktami w zespole. Zauważ, że $RAND$ jest algorytmem aproksymacyjnym, a ponadto może nie znany a priori.

RAND został wykorzystany przez TOPRANK , który wykorzystuje szacunki uzyskane przez RAND , aby skupić się na małym podzbiorze kandydujących punktów, dokładnie ocenia średnią odległość tych punktów i wybiera ich minimum. TOPRANK potrzebuje ${\ textstyle O (n ^ {\ Frac {5} {3}} \ log ^ {\ Frac {4} {3}} n)}$ obliczeń odległości do znalezienia dokładny _ medoid z dużym prawdopodobieństwem przy założeniu rozkładu na średnich odległościach.

trimed przedstawia algorytm znajdowania medoidu z ocenami odległości ${\ textstyle O (n ^ {\ Frac {3} {2}} 2 ^ {\ Theta (d)})}$ przy założeniu dystrybucji punktów. Algorytm wykorzystuje nierówność trójkąta, aby zmniejszyć przestrzeń wyszukiwania.

Meddit wykorzystuje połączenie obliczeń medoidów z wielorękimi bandytami i wykorzystuje algorytm typu górnej granicy ufności, aby uzyskać algorytm, który bierze oceny odległości ${\ textstyle O (n \ log n)}$ przy założeniach statystycznych dotyczących punktów.

Skorelowany Sekwencyjny Halving również wykorzystuje techniki wielorękich bandytów, udoskonalając Meddit . Wykorzystując strukturę korelacji w problemie, algorytm jest w stanie zapewnić drastyczną poprawę (zwykle około 1-2 rzędów wielkości) zarówno pod względem liczby potrzebnych obliczeń odległości, jak i czasu zegara ściennego.

Implementacje

Implementację RAND , TOPRANK i trimed można znaleźć tutaj . Implementację Meddita można znaleźć tutaj i tutaj . Implementację skorelowanego sekwencyjnego zmniejszania o połowę można znaleźć tutaj .