Co to jest grupowanie k-średnich?

Jak już wspomnieliśmy, wiele algorytmów grupowania nie skaluje się do zbiorów danych używanych w uczeniu maszynowym, które często zawierają miliony przykładów. Na przykład algorytmy klastrowania hierarchicznego z aglomeracją lub podziałem analizują wszystkie pary punktów i mają odpowiednio złożoność $O(n^2 log(n))$ i  $O(n^2)$.

Ten kurs koncentruje się na metodzie k-średnich, ponieważ skaluje się ona jako $O(nk)$, gdzie $k$jest liczbą klasterów wybranych przez użytkownika. Ten algorytm grupował punkty w grupy$k$ , minimalizując odległości między każdym punktem a środkiem ciężkości danego klastra (patrz rys. 1).

W rezultacie metoda k-średnich traktuje dane jako składające się z liczby rozkładów zbliżonych do kołowych i próbuje znaleźć klastry odpowiadające tym rozkładom. Dane rzeczywiste zawierają jednak wartości odstające i grupy oparte na gęstości, które mogą nie odpowiadać założeniom metody k-średnich.

algorytm klastrowania k-średnich,

Algorytm wykonuje te czynności:

1. Podaj początkowe przypuszczenie dotyczące $k$, które można później zmienić. W tym przykładzie wybierzemy $k = 3$.

2. losowo wybierać $k$ centroidy.

   

   Rysunek 1.Metoda k-średnich w momencie inicjalizacji

3. Przypisz każdy punkt do najbliższego centroidu, aby uzyskać $k$ początkowe klastry.

   

   Ilustracja 2.Początkowe klastry

4. Dla każdego klastra oblicz nowy centroid, biorąc pod uwagę średnią pozycję wszystkich punktów w klastrze. Strzałki na rysunku 4 pokazują zmianę pozycji środka ciężkości.

   

   Rysunek 3. Ponownie obliczone środki ciężkości.

5. Przypisz każdy punkt do najbliższego nowego centroidu.

   

   Ilustracja 4.Klastry po przypisaniu

6. Powtarzaj kroki 4 i 5, ponownie obliczając centroidy i przynależność do klastra, aż punkty nie będą już zmieniać klastrów. W przypadku dużych zbiorów danych możesz zatrzymać algorytm przed konwergencją na podstawie innych kryteriów.

Ponieważ pozycje centroidów są wybierane losowo, metoda k-średnich może zwracać znacznie różne wyniki w kolejnych przebiegach. Aby rozwiązać ten problem, wykonaj k-średnie kilka razy i wybierz wynik z najlepszymi metrykami jakości. (wskaźniki jakości omówimy w późniejszych częściach tego kursu). Aby wybrać lepsze początkowe pozycje centroidów, musisz użyć zaawansowanej wersji algorytmu k-średnich.

Chociaż dogłębna znajomość matematyki nie jest konieczna, dla ciekawskich użytkowników powiemy, że metoda k-średnich jest szczególnym przypadkiem algorytmu maksymalizacji oczekiwanej wartości. Zobacz notatki z wykładów na ten temat z Uniwersytetu Pensylwanii.