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:
Podaj początkowe przypuszczenie dotyczące \(k\), które można później zmienić. W tym przykładzie wybierzemy \(k = 3\).
losowo wybierać \(k\) centroidy.
Rysunek 1.Metoda k-średnich w momencie inicjalizacji Przypisz każdy punkt do najbliższego centroidu, aby uzyskać \(k\) początkowe klastry.
Ilustracja 2.Początkowe klastry 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. Przypisz każdy punkt do najbliższego nowego centroidu.
Ilustracja 4.Klastry po przypisaniu 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.