grupowanie k -mediany
W statystyce grupowanie k - median jest algorytmem analizy skupień . Jest to odmiana grupowania k -średnich , w której zamiast obliczania średniej dla każdego skupienia w celu określenia jego środka ciężkości, zamiast tego oblicza się medianę . Ma to wpływ na zminimalizowanie błędu we wszystkich skupieniach w odniesieniu do metryki odległości 1- normowej , w przeciwieństwie do kwadratu metryki odległości 2-normowej (która oznacza k ).
Wiąże się to bezpośrednio z problemem k -mediany w odniesieniu do 1-normy, czyli problemem znalezienia k centrów takich, aby utworzone przez nie skupienia były najbardziej zwarte. Formalnie, biorąc pod uwagę zbiór punktów danych x , k centrów ci należy wybrać tak, aby zminimalizować sumę odległości od każdego x do najbliższego ci .
Sformułowana w ten sposób funkcja kryterium jest czasem lepszym kryterium niż zastosowana w algorytmie grupowania k - średnich, w którym wykorzystuje się sumę kwadratów odległości. Suma odległości jest szeroko stosowana w zastosowaniach takich jak problem lokalizacji obiektu .
Proponowany algorytm wykorzystuje iterację w stylu Lloyda, która zmienia się między krokiem oczekiwania (E) a krokiem maksymalizacji (M), co czyni go algorytmem maksymalizacji oczekiwań . W kroku E wszystkie obiekty są przypisywane do najbliższej mediany. W kroku M mediany są ponownie obliczane przy użyciu mediany w każdym pojedynczym wymiarze.
Mediany i medoidy
Mediana jest obliczana w każdym pojedynczym wymiarze w sformułowaniu problemu k -median na odległość Manhattan , więc poszczególne atrybuty będą pochodzić ze zbioru danych (lub będą średnią dwóch wartości ze zbioru danych). Dzięki temu algorytm jest bardziej niezawodny w przypadku dyskretnych, a nawet binarnych zestawów danych. Natomiast użycie środków lub odległości euklidesowej mediany niekoniecznie dadzą indywidualne atrybuty ze zbioru danych. Nawet przy sformułowaniu odległości Manhattanu poszczególne atrybuty mogą pochodzić z różnych instancji w zbiorze danych; w związku z tym wynikowa mediana może nie należeć do wejściowego zestawu danych.
Algorytm ten jest często mylony z algorytmem k -medoids . Jednak medoid musi być rzeczywistą instancją ze zbioru danych, podczas gdy w przypadku wielowymiarowej mediany odległości Manhattanu dotyczy to tylko wartości pojedynczych atrybutów. Rzeczywista mediana może zatem być kombinacją wielu wystąpień. Na przykład, biorąc pod uwagę wektory (0,1), (1,0) i (2,2), mediana odległości Manhattanu wynosi (1,1), co nie istnieje w oryginalnych danych, a zatem nie może być medoidalny.
Oprogramowanie
- ELKI obejmuje różne warianty k-średnich, w tym k-mediany.
- Kmediany FORTRAŃSKIE
- GNU R zawiera k-mediany w pakiecie „flexclust”.
- Mediany stanu