Ta strona została przetłumaczona przez Cloud Translation API.

Uruchamianie algorytmu grupowania

W systemach uczących się czasami występują zbiory danych, które mogą zawierać miliony przykładów. Algorytmy systemów uczących się muszą skutecznie skalować się do tych dużych zbiorów danych. Wiele algorytmów grupowania nie jest jednak skalowanych, ponieważ muszą one obliczać podobieństwo między wszystkimi parami punktów. To oznacza, że ich środowiska wykonawcze zwiększają się jako kwadrat liczby punktów, co oznaczy jako $O(n^2)$. Na przykład algorytmy agresywne lub hierarchiczne klastry grupujące analizują wszystkie pary punktów i mają złożoność $O(n^2 log(n))$ i $O(n^2)$.

Ten kurs skupia się na k-meanach, ponieważ skaluje się on $O(nk)$, gdzie $k$to liczba klastrów. K-means grupuje $k$ klastry przez minimalizowanie odległości między punktami a centroidem klastra (jak widać na rysunku 1 poniżej). centroid klastra to średnia wszystkich punktów w klastrze.

Jak widać, funkcja k-średnia znajduje około okrągłych klastrów. Konkretnie oznacza to, że dane k-średnia skutecznie traktują dane jako składające się z szeregu mniej więcej okrągłych rozkładów oraz próbują znaleźć klastry odpowiadające tym rozkładom. W rzeczywistości dane zawierają wartości odstające i mogą nie pasować do takiego modelu.

Przed uruchomieniem k-średnich musisz wybrać liczbę klastrów: $k$. Najpierw zgaduj $k$. Później omówimy sposoby zawężania tej liczby.

Algorytm grupowania K

Aby połączyć dane w $k$ klastry, oznacza to, że:

Wykres k-średnich przy inicjowaniu — **Ilustracja 1: k-means przy inicjowaniu zapytania.**

Krok 1

Algorytm losowo wybiera Centroid dla każdego klastra. W tym przykładzie wybieramy $k$ z 3, dzięki czemu algorytm losowo wybiera 3 centymetry.

Krok 2

Algorytm przypisuje każdy punkt do najbliższego centroida, aby otrzymać $k$ początkowe klastry.

Obliczenie centroidów — **Ilustracja 3. Ponowne obliczanie centroidów**

Krok 3

W przypadku każdego klastra algorytm ponownie oblicza centroid, określając średnią wszystkich punktów w klastrze. Zmiany w centroidach są widoczne na rysunku 3 za pomocą strzałek. Ponieważ zmienia się centroid, algorytm ponownie przypisuje punkty do najbliższego Centroida. Rysunek 4 przedstawia nowe klastry po ponownym przypisaniu.

Klastry po ponownej zmianie — **Ilustracja 4. Klastry po zmianie przypisania.**

Krok 4

Algorytm powtarza obliczenia centroidów i przypisywania punktów, aż punkty przestaną zmieniać klastry. W przypadku grupowania dużych zbiorów danych zatrzymujesz algorytm, zanim nastąpi dopasowanie, korzystając z innych kryteriów.

Nie musisz znać zagadnień matematycznych stojących za k-średnimi kursami. Jeśli jednak chcesz dowiedzieć się więcej, zwróć uwagę na poniższe potwierdzenie.

Kliknij ikonę plusa, aby potwierdzić wynik.

Biorąc pod uwagę $n$ przykłady przypisane $k$ klasto, ogranicz sumę odległości przykładów do centroidów. Gdzie:

$A_{nk} = 1$ gdy $n$jest przypisany do $k$klastra, a 0 w innym przypadku.
$\theta_k$ jest centylowym klastrem $k$

Chcemy zminimalizować to wyrażenie: $$\min_{A,\theta} \sum_{n=1}^N \sum_{k=1}^{K} A_{nk} ||\theta_k - x_n ||^2$$ podlega: $$A_{nk} \in \{0,1\} \forall n,k$$ i $$\sum^{K}_{k=1}A_{nk}=1 \forall n$$ Aby zminimalizować wyrażenie w odniesieniu do centroidów klastra $\theta_k$, pojmij pochodną $\theta_k$ i równaj ją do 0. $$f(\theta) = \sum^{N}_{n=1} \sum_{k=1}^{K} A_{nk} ||\theta_k - x_n||^2$$ $$\frac{\partial f}{\partial \theta_k} = 2 \sum_{n=1}^{N} A_{nk}(\theta_k - x_n) = 0$$ $$\implies \sum_{n=1}^{N} A_{nk}\theta_{k} = \sum^N_{n=1} A_{nk}x_{n}$$ $$\theta_k \sum_{n=1}^{N} A_{nk} = \sum_{n=1}^{N} A_{nk} x_n$$ $$\theta_k = \frac{\sum^N_{n=1} A_{nk} x_n}{\sum^N_{n=1} A_{nk}}$$ Licznik to suma wszystkich przykładowych odległości w klastrze. Nominalny to liczba przykładów w klastrze. Stąd Centodid klastrowy$\theta_k$ jest średnią wielkością odległości od centroidu w klastrze. To udowodnione.

Pozycje centroidu są początkowo wybierane losowo, dlatego w przypadku kolejnych cykli pracy znaki k-średnie mogą zwracać znacznie inne wyniki. Aby rozwiązać ten problem, uruchom wielokrotnie k-średnia i wybierz wynik z najlepszymi danymi. Wskaźniki jakości omówimy w dalszej części tego kursu. Aby wybrać lepsze początkowe pozycje środkowych, musisz mieć zaawansowaną wersję k-średnich.