Jak zrozumieć wady K-średnich

K-średnich jest szeroko stosowaną metodą analizy skupień. W moim rozumieniu ta metoda NIE wymaga ŻADNYCH założeń, tj. Podaj mi zbiór danych i wcześniej określoną liczbę klastrów, k, i po prostu stosuję ten algorytm, który minimalizuje sumę błędów kwadratu (SSE), wewnątrz klastra do kwadratu błąd.

Zatem k-średnich jest zasadniczo problemem optymalizacyjnym.

Przeczytałem trochę materiału o wadach k-średnich. Większość z nich mówi, że:

• k-średnich zakłada, że ​​wariancja rozkładu każdego atrybutu (zmiennej) jest sferyczna;
• wszystkie zmienne mają tę samą wariancję;
• wcześniejsze prawdopodobieństwo dla wszystkich k klastrów jest takie samo, tj. każda klaster ma mniej więcej taką samą liczbę obserwacji;

Jeśli którekolwiek z tych 3 założeń zostanie naruszone, wówczas k-średnich zawiedzie.

Nie mogłem zrozumieć logiki tego stwierdzenia. Myślę, że metoda k-średnich zasadniczo nie przyjmuje żadnych założeń, po prostu minimalizuje SSE, więc nie widzę związku między minimalizowaniem SSE a tymi 3 „założeniami”.

Chociaż bardzo podoba mi się odpowiedź Davida Robinsona , oto dodatkowa krytyka k-średnich.

Klastrowanie danych nieklastrowanych

Uruchom k-średnich na jednolitych danych, a nadal będziesz otrzymywać klastry! Nie mówi ci, kiedy dane po prostu się nie klastrują, i może w ten sposób doprowadzić twoje badania do ślepej uliczki.

Wrażliwy na skalę

Przeskalowanie zestawów danych całkowicie zmieni wyniki. Chociaż samo to nie jest złe, nie zdawanie sobie sprawy z tego , że musisz poświęcić dodatkową uwagę skalowaniu danych, jest złe. Współczynniki skalowania są dodatkowe ukryte parametry K-oznacza, że „default” do 1, a zatem są łatwo przeoczyć, ale mają duży wpływ (ale oczywiście dotyczy to wielu innych algorytmów, zbyt).$d$

Prawdopodobnie jest to tak zwane „wszystkie zmienne mają tę samą wariancję”. Poza tym idealnie byłoby, gdybyś rozważał także skalowanie nieliniowe, gdy jest to właściwe.

Pamiętaj również, że skalowanie każdej osi w celu uzyskania wariancji jednostek jest heurystyczne . Nie zapewnia to działania k-średnich. Skalowanie zależy od znaczenia zestawu danych. A jeśli masz więcej niż jeden klaster, chciałbyś, aby każdy klaster (niezależnie) miał taką samą wariancję w każdej zmiennej.

Oto klasyczny kontrprzykład danych, których k-średnich nie może skupić. Obie osie znajdują się w każdej grupie, więc wystarczyłoby to zrobić w 1 wymiarze. Ale klastry mają różne wariancje, a zatem k-średnie dzieli je niepoprawnie.

Nie sądzę, że ten kontrprzykład dla k-średnich jest objęty twoimi punktami:

• Wszystkie gromady są sferyczne (iid Gaussa).
• Wszystkie osie mają taki sam rozkład, a tym samym wariancję.
• Oba klastry mają po 500 elementów.

Jednak k-średnie wciąż zawodzi (i staje się gorzej, jeśli zwiększę wariancję powyżej 0,5 dla większego klastra). Ale: to nie algorytm zawiódł. To założenia, które się nie sprawdzają . K-znaczy działa idealnie, po prostu optymalizuje złe kryterium.

Nawet w przypadku idealnych zestawów danych może utknąć w lokalnym minimum

Poniżej znajduje się najlepsza z 10 serii K-średnich na klasycznym zestawie danych A3. Jest to syntetyczny zestaw danych, zaprojektowany dla k-średnich . 50 klastrów, każdy o kształcie gaussowskim, dość dobrze rozdzielonych. Jednak tylko z k-średnich ++ i 100 iteracjami uzyskałem oczekiwany wynik ... (poniżej jest 10 iteracji zwykłych k-średnich, dla ilustracji).

W tym zestawie danych szybko znajdziesz wiele klastrów, w których k-średnich nie udało się znaleźć właściwej struktury. Na przykład w prawym dolnym rogu klaster został podzielony na trzy części. Ale nie ma mowy, k-średnich przeniesie jedno z tych centroidów w zupełnie inne miejsce zestawu danych - jest uwięzione w lokalnym minimum (a to już był najlepszy z 10 przebiegów!)

W tym zestawie danych znajduje się wiele takich lokalnych minimów. Bardzo często, gdy pobierzesz dwie próbki z tego samego klastra, utknie ono na minimum w miejscu, w którym ten klaster pozostaje podzielony, a zamiast tego łączą się dwa inne klastry. Nie zawsze, ale bardzo często. Potrzebujesz więc wielu iteracji, aby mieć szczęście. Przy 100 iteracjach k-średnich nadal liczyłem 6 błędów, a przy 1000 iteracjach sprowadziłem to do 4 błędów. K-znaczy ++, ponieważ waży przypadkowe próbki, działa znacznie lepiej na tym zestawie danych.

Środki są ciągłe

Chociaż możesz uruchamiać k-średnich na danych binarnych (lub danych kategorialnych zakodowanych jednokrotnie) wyniki nie będą już binarne. Otrzymujesz wynik, ale ostatecznie nie możesz go zinterpretować, ponieważ ma on inny typ danych niż dane pierwotne.

Ukryte założenie: SSE warto zminimalizować

Jest to w zasadzie już obecne w powyższej odpowiedzi, ładnie wykazane za pomocą regresji liniowej. Istnieją przypadki użycia, w których k-średnie ma doskonały sens. Kiedy Lloyd musiał dekodować sygnały PCM, znał liczbę różnych tonów, a błąd najmniejszych kwadratów minimalizuje ryzyko błędów dekodowania. A w kwantyzacji kolorów obrazowanych minimalizujesz również błąd koloru podczas zmniejszania palety. Ale czy na podstawie danych suma kwadratowych odchyleń jest znaczącym kryterium do zminimalizowania?

W powyższym kontrprzykładzie wariancja nie jest warta minimalizacji, ponieważ zależy od klastra. Zamiast tego model mieszanki Gaussa powinien pasować do danych, jak na poniższym rysunku:

(Ale to też nie jest ostateczna metoda. Równie łatwo jest zbudować dane, które nie spełniają założeń „mieszanki rozkładów Gaussa”, np. Przez dodanie dużej ilości szumu tła)

Zbyt łatwy w użyciu źle

Podsumowując, zbyt łatwo jest rzucić k-średnich na swoje dane, a mimo to uzyskać wynik (jest to dość losowe, ale nie zauważysz). Myślę, że lepiej byłoby mieć metodę, która może zawieść, jeśli nie zrozumiesz swoich danych ...

Średnie K jako kwantyzacja

Jeśli chcesz teoretyczny model działania k-średnich, rozważ to podejście kwantyzacyjne , a nie algorytm grupowania.

Cel k-średnich - minimalizacja błędu kwadratu - jest rozsądnym wyborem, jeśli zastąpisz każdy obiekt jego najbliższym środkiem ciężkości. (To ma o wiele mniej sensu, jeśli przeglądasz oryginalne dane grupy IMHO.)

$k$

Ta kwantyzacja jest prawdopodobnie dość podobna do przykładu regresji liniowej. Regresja liniowa znajduje najlepszy model liniowy . A k-średnie znajduje (czasami) najlepszą redukcję do wartości k wielowymiarowego zestawu danych. Gdzie „najlepszy” to błąd najmniejszego kwadratu.

IMHO, k-średnich jest dobrym algorytmem kwantyzacji (zobacz pierwszy obraz w tym poście - jeśli chcesz zbliżyć zestaw danych do dwóch punktów, jest to rozsądny wybór!). Jeśli chcesz przeprowadzić analizę skupień jak w strukturze odkrywczej, to k-średnich jest IMHO nie najlepszym wyborem. Ma tendencję do klastrowania, gdy nie ma klastrów, i nie może rozpoznać różnych struktur, które często widuje się w danych.

Drobny druk: wszystkie obrazy zostały wygenerowane za pomocą ELKI . Dane zostały wygenerowane przy użyciu .xmlformatu generowania danych, ale są tak podstawowe, że nie warto ich udostępniać.

Cóż za wspaniałe pytanie - jest to okazja, aby pokazać, jak można sprawdzić wady i założenia dowolnej metody statystycznej. Mianowicie: uzupełnij dane i wypróbuj algorytm!

Rozważymy dwa z twoich założeń i zobaczymy, co stanie się z algorytmem k-średnich, gdy te założenia zostaną złamane. Będziemy trzymać się danych dwuwymiarowych, ponieważ jest łatwa do wizualizacji. (Dzięki przekleństwu wymiarowości dodanie dodatkowych wymiarów może sprawić, że problemy te będą poważniejsze, a nie mniej). Będziemy pracować z statystycznym językiem programowania R: pełny kod znajdziesz tutaj (i post w formie bloga tutaj ).

Dywersja: Kwartet Anscombe

Po pierwsze, analogia. Wyobraź sobie, że ktoś argumentował:

Przeczytałem trochę materiału o wadach regresji liniowej - że oczekuje ona liniowego trendu, że reszty są normalnie rozmieszczone i że nie ma żadnych wartości odstających. Ale regresja liniowa minimalizuje sumę błędów kwadratu (SSE) z przewidywanej linii. Jest to problem optymalizacji, który można rozwiązać bez względu na kształt krzywej lub rozkład reszt. Zatem regresja liniowa nie wymaga żadnych założeń do działania.

Cóż, tak, regresja liniowa działa poprzez minimalizację sumy kwadratów reszt. Ale to samo w sobie nie jest celem regresji: staramy się narysować linię, która służy jako wiarygodny, bezstronny predyktor y na podstawie x . Twierdzenie Gaussa-Markowa mówi nam, że minimalizacja SSE osiąga ten cel - ale to twierdzenie opiera się na pewnych bardzo szczegółowych założeniach. Jeśli te założenia zostaną złamane, nadal możesz zminimalizować SSE, ale może się to nie udaćbyle co. Wyobraź sobie, mówiąc: „Prowadzisz samochód, naciskając pedał: jazda jest zasadniczo„ procesem pchania pedału ”. Pedał można naciskać bez względu na ilość gazu w zbiorniku. Dlatego nawet jeśli zbiornik jest pusty, nadal można naciskać pedał i prowadzić samochód. ”

Ale rozmowa jest tania. Spójrzmy na zimne, twarde dane. A właściwie skompilowane dane.

$R^2$

Można powiedzieć: „Regresja liniowa nadal działa w tych przypadkach, ponieważ minimalizuje sumę kwadratów reszt”. Ale cóż za pirackie zwycięstwo ! Regresja liniowa zawsze rysuje linię, ale jeśli jest to linia bez znaczenia, kogo to obchodzi?

Teraz widzimy, że fakt, że można przeprowadzić optymalizację, nie oznacza, że ​​osiągamy nasz cel. Widzimy, że tworzenie danych i ich wizualizacja to dobry sposób na sprawdzenie założeń modelu. Trzymaj się tej intuicji, za chwilę jej potrzebujemy.

Zerwane założenie: dane niesferyczne

Argumentujesz, że algorytm k-średnich będzie działał dobrze na klastrach niesferycznych. Gromady niesferyczne, takie jak ... te?

Może nie tego się spodziewałeś, ale jest to całkowicie rozsądny sposób na tworzenie klastrów. Patrząc na ten obraz, my, ludzie, natychmiast rozpoznajemy dwie naturalne grupy punktów - nie można ich pomylić. Zobaczmy więc, jak działa k-średnia: przypisania są pokazane w kolorze, przypisane centra są pokazane jako X-y.

Cóż, to nie w porządku. K-znaczy próbował wpasować kwadratowy kołek w okrągły otwór - próbując znaleźć ładne centra z czystymi kulkami wokół nich - i to się nie udało. Tak, wciąż minimalizuje sumę kwadratów wewnątrz klastra - ale tak jak w powyższym Kwartecie Anscombe, jest to zwycięstwo Pyrrhic!

Możesz powiedzieć: „To nie jest uczciwy przykład ... żadna metoda klastrowania nie mogłaby poprawnie znaleźć tak dziwnych klastrów”. Nie prawda! Wypróbuj hierarchiczne grupowanie z jednym łączeniem :

Przybiłam to! Wynika to z faktu, że hierarchiczne grupowanie z jednym łączeniem przyjmuje właściwe założenia dla tego zestawu danych. (Istnieje cała inna klasa sytuacji, w których zawodzi).

Możesz powiedzieć „To pojedynczy, ekstremalny, patologiczny przypadek”. Ale nie jest! Na przykład, możesz zmienić zewnętrzną grupę w półkole zamiast koła, a zobaczysz, że k-średnie nadal działa strasznie (a hierarchiczne grupowanie nadal dobrze). Z łatwością mogłem wymyślić inne problematyczne sytuacje, i to tylko w dwóch wymiarach. Gdy grupujesz dane 16-wymiarowe, mogą pojawić się wszelkiego rodzaju patologie.

Na koniec powinienem zauważyć, że k-średnich wciąż można uratować! Jeśli zaczniesz od przekształcenia danych we współrzędne biegunowe , teraz klastrowanie działa:

Dlatego zrozumienie założeń leżących u podstaw metody jest bardzo ważne: nie tylko informuje, kiedy metoda ma wady, ale także jak je naprawić.

Złamane założenie: klastry o nierównomiernych rozmiarach

Co się stanie, jeśli klastry mają nierówną liczbę punktów - czy to również łamie k-oznacza klastry? Rozważmy ten zestaw klastrów o rozmiarach 20, 100, 500. Wygenerowałem każdy z wielowymiarowego Gaussa:

Wygląda na to, że k-znaczy prawdopodobnie mógłby znaleźć te klastry, prawda? Wszystko wydaje się być generowane w schludne i uporządkowane grupy. Spróbujmy więc k-znaczy:

Ojej. To, co się tu stało, jest nieco subtelniejsze. W dążeniu do zminimalizowania sumy kwadratów wewnątrz klastra, algorytm k-średnich nadaje większą „wagę” większym klastrom. W praktyce oznacza to, że z przyjemnością pozwala małej gromadzie skończyć z dala od jakiegokolwiek centrum, podczas gdy używa tych centrów do „podziału” znacznie większej gromady.

Jeśli trochę zagrasz z tymi przykładami ( tutaj kod R! ), Zobaczysz, że możesz skonstruować znacznie więcej scenariuszy, w których k-znaczy sprawia, że ​​krępowanie jest błędne.

Wniosek: brak darmowego lunchu

W folklorze matematycznym jest urocza konstrukcja sformalizowana przez Wolperta i Macready'ego , zwana „Twierdzeniem o braku obiadu”. Jest to prawdopodobnie moje ulubione twierdzenie w filozofii uczenia maszynowego i cieszę się, że mogę je przywołać (czy wspominałem, że uwielbiam to pytanie?) Podstawowa idea jest sformułowana (nie rygorystycznie) w następujący sposób: „Po uśrednieniu we wszystkich możliwych sytuacjach, każdy algorytm działa równie dobrze ”.

Brzmi sprzecznie z intuicją? Weź pod uwagę, że w każdym przypadku, w którym działa algorytm, mógłbym stworzyć sytuację, w której okropnie zawodzi. Regresja liniowa zakłada, że ​​dane spadają wzdłuż linii - ale co jeśli podąży za falą sinusoidalną? Test t zakłada, że ​​każda próbka pochodzi z rozkładu normalnego: co jeśli wrzucisz wartość odstającą? Każdy algorytm wynurzania gradientowego może zostać uwięziony w lokalnych maksimach, a każda nadzorowana klasyfikacja może zostać oszukana w celu nadmiernego dopasowania.

Co to znaczy? Oznacza to, że założenia są źródłem twojej mocy!Kiedy Netflix poleca ci filmy, zakłada się, że jeśli podoba ci się jeden film, spodoba ci się podobny (i odwrotnie). Wyobraź sobie świat, w którym to nie było prawdą, a twoje gusta są przypadkowo rozproszone przypadkowo między gatunkami, aktorami i reżyserami. Ich algorytm rekomendacji okropnie zawiódłby. Czy miałoby sens powiedzenie „Cóż, wciąż minimalizuje oczekiwany błąd w kwadracie, więc algorytm nadal działa”? Nie można stworzyć algorytmu rekomendacji bez pewnych założeń dotyczących gustów użytkowników - podobnie jak nie można stworzyć algorytmu klastrowania bez przyjęcia pewnych założeń dotyczących natury tych klastrów.

Więc nie akceptuj tylko tych wad. Poznaj je, aby mogli poinformować Cię o wyborze algorytmów. Zrozum je, abyś mógł ulepszyć algorytm i przekształcić dane, aby je rozwiązać. I kochaj ich, ponieważ jeśli twój model nigdy nie będzie w błędzie, oznacza to, że nigdy nie będzie odpowiedni.

Chciałbym tylko dodać do odpowiedzi @ DavidRobinson, że skupianie się do minimalnej całkowitej wariancji klastrowej jest w rzeczywistości kombinatorycznym problemem optymalizacyjnym , którego k-Means jest tylko jedną techniką - i biorąc pod uwagę jego „jeden strzał”, lokalny „stromy zjazd”, też całkiem zły . Również próba znacznej poprawy k-średnich „gołych kości” poprzez jakoś (ale szybko!) Ustalenie, gdzie powinny znajdować się nasiona klastra, jest od samego początku skazana na porażkę: ponieważ nasiona wpływają (drastycznie!) Na końcowe gromady, ich ilość „wiedzieć”, co jest optymalne ... przed faktycznym obliczeniem.

Jednak, ponieważ większość problemów związanych z optymalizacją może być dla niektórych podatna poważne techniki optymalizacji . Jeden z nich bardzo ściśle pasuje do struktury problemu (jak wymaga NFL!), A na pewno pokazuje to w jego wynikach. Nie chcę tutaj zamieszczać żadnych reklam (byłoby to - i słusznie - wbrew etykiecie), więc jeśli jesteś zainteresowany, po prostu przeczytaj go tutaj i dokonaj własnego osądu.

Biorąc to pod uwagę, zgadzam się z @ttnphns, że k-Means z pewnością nie identyfikuje mieszanki gaussowskiej - funkcje kosztów tych dwóch problemów są zupełnie inne. Okazuje się, że znalezienie najlepiej dopasowanego (pod względem prawdopodobieństwa modelu na podstawie danych) Mikstury Gaussa jest także kombinatorycznym problemem optymalizacji - i dla którego istnieje również poważna technika optymalizacji . Po raz kolejny brak reklam: możesz dojść do własnych wniosków , tj. Punktów danych, które nie należą do żadnego z klastrów, ponieważ są one po prostu całkowicie losowe (notorycznie, całkowicie wykasowują na przykład k-Means ). Odbywa się to poprzez jeden dodatkowy, równomierny rozkład tutaj - Powiem tylko, że algorytm omówiono nie może, rzeczywiście, jak prawidłowo zidentyfikować klastry ostatniego obrazu w poście użytkownika @ David Robinson . To nawet poprawnie (tj. W matematycznie dobrze zdefiniowany sposób) rozwiązuje odwieczny problem wartości odstających konkurować z Gaussianami ... a wspaniały wynik jest taki, że w przypadku równomiernie rozłożonych danych, to rzeczywiście raport że nic tam nie ma (nigdzie indziej tego nie widziałem).

Teraz, oczywiście, zgodnie z NFL i jako twoje słusznie zauważyłeś , nawet globalnie optymalne Mieszaniny Gaussa z identyfikacją wartości odstających opierają się na wcześniejszym założeniu - mianowicie, że dane są rzeczywiście rozprowadzane normalnie. Na szczęście jednak dzięki Prawu Dużych Liczb liczne zjawiska naturalne są zgodne z tym założeniem.

ZASTRZEŻENIE: z najgłębszymi przeprosinami napisałem oba powyższe artykuły i omówione przez nich algorytmy.

PS Raz spotkałem Macreadyego na konferencji - niezwykle bystry i miły facet!

Logicznie rzecz biorąc, wady K-średnich to:

• wymaga liniowej separacji klastrów
• musisz określić liczbę klastrów
• Algorytmika: procedura Loyds nie jest zbieżna z prawdziwym globalnym maksimum, nawet przy dobrej inicjalizacji, gdy jest wiele punktów lub wymiarów

Ale K-znaczy jest lepszy, niż nam się zwykle wydaje. Jestem bardzo entuzjastycznie nastawiony do tego po przetestowaniu go w porównaniu z innymi metodami grupowania (spektrum, gęstość ...) i LDA w prawdziwej klasyfikacji tekstu miliona tekstów: K-średnie miało znacznie lepszą dokładność niż na przykład LDA (88% vs 59%). Niektóre inne metody grupowania były dobre, ale średnie K były blisko szczytu ... i były bardziej przystępne pod względem złożoności.

Nigdy nie czytałem o metodzie klastrowania, która jest ogólnie lepsza w szerokim zakresie problemów. Nie twierdzenie, że K-znaczy jest też ogólnie lepsze, po prostu to, że o ile mi wiadomo, nie ma uniwersalnego superbohatera grupującego. Wiele artykułów, wiele metod, nie prawdziwa rewolucja (z mojego osobistego ograniczonego doświadczenia w testowaniu niektórych z nich).

Głównym powodem, dla którego logiczne wady środków K są często tylko pozorne, jest to, że punkty skupiania w płaszczyźnie 2D są rzadkie w uczeniu maszynowym. Wiele rzeczy z intuicji geometrycznej, które są prawdziwe w 2D, 3D ... są nieistotne w raczej dużych wymiarach lub abstrakcyjnych przestrzeniach wektorowych (jak worek słów, wektor zmiennych ...)

Liniowa separacja: rzadko masz do czynienia z okrągłymi klastrami w rzeczywistych danych. Jeszcze lepiej jest założyć, że w takich przypadkach nie istnieją. Pozwolenie algorytmowi na ich wyszukiwanie pozwoliłoby mu znaleźć dziwne okrągłe skupiska w hałasie. Liniowe założenie w środkach K sprawia, że ​​jest ono często bardziej niezawodne.

Liczba klastrów: często nie ma prawdziwej idealnej liczby klastrów, które chcesz zobaczyć. Na przykład w przypadku klasyfikacji tekstu może istnieć 100 kategorii, 105, 110 ... to wszystko jest raczej subiektywne. Określenie liczby klastrów staje się równoważne z określeniem globalnej ziarnistości. Wszystkie metody klastrowania i tak wymagają specyfikacji szczegółowości.

$10^{\text{a lot}}$ powtórzeń mieć małą szansę na znalezienie prawdziwego minimum. Inne metody, takie jak „zakończ to chciwym wyszukiwaniem” (zaproponowane w Matlabie) są astronomicznie kosztowne w dużych zestawach danych.

Ale wszystkie algorytmy klastrowania mają takie ograniczenia. Na przykład w klastrze spektralnym: nie można znaleźć prawdziwych wektorów własnych, a jedynie przybliżenia.

W tym samym czasie obliczeń całkiem zoptymalizowana biblioteka LDA działała mniej dobrze niż nasze domowe (nie idealnie zoptymalizowane) środki K. Od tego czasu myślę trochę inaczej.

Aby zrozumieć wady K-środków, lubię myśleć o tym, co kryje się za tym modelem.

$K$$K$

$K$$\sigma^2 \mathbf{I}$$\sigma^2$$K$$\sigma^2 \rightarrow 0$ wtedy otrzymujemy K-średnie.

Co to mówi nam o wadach K-średnich?

1. Środki K prowadzą do klastrów, które wyglądają na wiele odmian Gaussa.
2. Ponieważ wariancja między zmiennymi jest taka sama, K-średnie prowadzi do klastrów, które wyglądają sferycznie.
3. $K$ grup, K-means prowadzi do klastrów, które wyglądają jak tej samej sfery.
4. Średnie K zmierza w kierunku grup o jednakowej wielkości.

K-średnich jest w rzeczywistości dość restrykcyjnym algorytmem. Zaletą jest to, że przy powyższych założeniach algorytm można wykonać dość szybko. Ale jeśli najważniejszą sprawą jest wydajność klastrowania, w rzeczywistych sytuacjach współczynnik K jest zwykle zbyt restrykcyjny.