Jak już wspomnieliśmy, wiele algorytmów grupowania nie skaluje się do zbiorów danych. wykorzystywanych w uczeniu maszynowym, które często mają miliony przykładów. Przykład: aglomeracyjne lub dzielnikowe algorytmy grupowania hierarchicznego biorą pod uwagę wszystkie pary punktów i trudności \(O(n^2 log(n))\) oraz \(O(n^2)\)
Ten kurs koncentruje się na k-średnich, ponieważ skaluje się jako \(O(nk)\), gdzie \(k\) to liczba klastrów wybranych przez użytkownika. Ten algorytm grupuje punkty \(k\) klastrów przez zminimalizowanie odległości między każdym punktem a jego środek pomieszczeń klastra (zobacz ilustrację 1).
W efekcie funkcja k-średnich efektywnie traktuje dane składające się z pewnej liczby w dystrybucjach kołowych i próbuje znaleźć odpowiadające im klastry. rozkłady. Rzeczywiste dane zawierają jednak wartości odstające i klastry oparte na gęstości i mogą odbiegać od założeń związanych z wartościami k-średnich.
Algorytm grupowania k-średnich
Ten algorytm wykonuje te czynności:
Podaj początkową definicję wartości \(k\), którą można później zmienić. Do tego celu przykładowy wybór \(k = 3\).
Losowo wybierz \(k\) centroidy.
Rys. 1: Średnie k podczas inicjowania. Przypisz każdy punkt do najbliższego centroidu, aby uzyskać \(k\) klastry początkowe.
Rys. 2: Początkowe klastry. Oblicz dla każdego klastra nowy centroid, przyjmując średnią pozycję wszystkich punktów w klastrze. Strzałki na rys. 4 pokazują zmianę w pozycji centroidu.
Rys. 3. Przeliczone centroidy. Przypisz każdy punkt do najbliższego nowego centroidu.
Rys. 4. Klastry po ponownym przypisaniu. Powtórz kroki 4 i 5, ponownie obliczając centroidy i przynależność do klastra, aż do punkty nie zmieniają już klastrów. W przypadku dużych zbiorów danych można: zatrzymuje algorytm przed zbieżnością na podstawie innych kryteriów.
Ponieważ położenie centroidu jest początkowo wybierane losowo, k-średnie mogą zwracają znacznie inne wyniki przy kolejnych uruchomieniach. Aby rozwiązać ten problem , użyj funkcji k-średnich wiele razy i wybierz wynik o najlepszej jakości danych. Dane dotyczące jakości omówimy w dalszej części tego kursu. Potrzebujesz zaawansowanej wersji k-średnich, aby wybrać lepsze początkowe pozycje centroidu.
Dogłębne zrozumienie matematyki nie jest konieczne, Ciekawe jest to, że „k-średnie” są specjalnym przypadkiem algorytmem maksymalizacji oczekiwań i maksymalizacji. Zobacz notatki na ten temat przygotowane przez UPenn.