logo

Algorytm grupowania K-średnich

Klastrowanie K-Means to algorytm uczenia się bez nadzoru, który służy do rozwiązywania problemów klastrowania w uczeniu maszynowym lub nauce o danych. W tym temacie dowiemy się, czym jest algorytm grupowania k-średnich, jak działa algorytm, a także implementacja grupowania k-średnich w Pythonie.

Co to jest algorytm K-średnich?

Klastrowanie K-średnich to Algorytm uczenia się bez nadzoru , który grupuje nieoznakowany zbiór danych w różne klastry. Tutaj K określa liczbę predefiniowanych klastrów, które należy utworzyć w procesie, tak jak w przypadku K=2 będą dwa klastry, a dla K=3 będą trzy klastry i tak dalej.

Jest to algorytm iteracyjny, który dzieli nieoznakowany zbiór danych na k różnych klastrów w taki sposób, że każdy zbiór danych należy tylko do jednej grupy o podobnych właściwościach.

Pozwala nam to grupować dane w różne grupy i jest wygodnym sposobem samodzielnego odkrywania kategorii grup w nieoznakowanym zbiorze danych, bez potrzeby jakiegokolwiek szkolenia.

Jest to algorytm oparty na centroidach, w którym każdy klaster jest powiązany z centroidą. Głównym celem tego algorytmu jest minimalizacja sumy odległości pomiędzy punktem danych a odpowiadającymi im klastrami.

znak na ciąg Java

Algorytm bierze nieoznaczony zbiór danych jako dane wejściowe, dzieli zbiór danych na k-liczbę klastrów i powtarza proces, aż nie znajdzie najlepszych klastrów. W algorytmie tym należy z góry określić wartość k.

K-oznacza grupowanie algorytm realizuje głównie dwa zadania:

  • Określa najlepszą wartość K punktów środkowych lub centroid w procesie iteracyjnym.
  • Przypisuje każdy punkt danych do najbliższego k-centrum. Te punkty danych, które są blisko konkretnego k-centrum, tworzą klaster.

Dlatego każdy klaster ma punkty danych o pewnych podobieństwach i jest oddalony od innych klastrów.

Poniższy diagram wyjaśnia działanie algorytmu grupowania K-średnich:

Algorytm grupowania K-średnich

Jak działa algorytm K-średnich?

Działanie algorytmu K-Means wyjaśniono w poniższych krokach:

Krok 1: Wybierz liczbę K, aby określić liczbę skupień.

Krok 2: Wybierz losowe punkty K lub centroidy. (Może być inny niż wejściowy zbiór danych).

Krok 3: Przypisz każdy punkt danych do jego najbliższej centroidy, która utworzy predefiniowane K klastrów.

Krok 4: Oblicz wariancję i umieść nowy środek ciężkości każdego skupienia.

Krok 5: Powtórz trzecie kroki, co oznacza ponowne przypisanie każdego punktu danych do nowego najbliższego środka ciężkości każdego klastra.

Krok 6: Jeśli nastąpi jakiekolwiek ponowne przypisanie, przejdź do kroku 4, w przeciwnym razie przejdź do ZAKOŃCZ.

Krok 7 : Model jest gotowy.

Rozumiemy powyższe kroki, biorąc pod uwagę wykresy wizualne:

Załóżmy, że mamy dwie zmienne M1 i M2. Wykres rozrzutu tych dwóch zmiennych na osi x-y podano poniżej:

Algorytm grupowania K-średnich
  • Weźmy liczbę k skupień, tj. K=2, aby zidentyfikować zbiór danych i umieścić je w różnych skupieniach. Oznacza to, że tutaj spróbujemy pogrupować te zbiory danych w dwa różne klastry.
  • Musimy wybrać losowe k punktów lub środek ciężkości, aby utworzyć klaster. Punkty te mogą być punktami ze zbioru danych lub dowolnym innym punktem. Zatem tutaj wybieramy dwa poniższe punkty jako k punktów, które nie są częścią naszego zbioru danych. Rozważ poniższy obraz:
    Algorytm grupowania K-średnich
  • Teraz przypiszemy każdy punkt danych na wykresie punktowym do najbliższego punktu K lub środka ciężkości. Obliczymy to, stosując poznaną przez nas matematykę do obliczenia odległości między dwoma punktami. Narysujemy więc środkową pomiędzy obydwoma centroidami. Rozważ poniższy obraz:
    Algorytm grupowania K-średnich

Z powyższego obrazu jasno wynika, że ​​punkty po lewej stronie linii znajdują się blisko centroidy K1, czyli niebieskiej, a punkty po prawej stronie linii znajdują się blisko żółtej centroidy. Dla lepszej wizualizacji pokolorujmy je na niebiesko i żółto.

Algorytm grupowania K-średnich
  • Ponieważ musimy znaleźć najbliższy klaster, dlatego powtórzymy proces, wybierając nowy centroid . Aby wybrać nowe centroidy, obliczymy środek ciężkości tych centroid i znajdziemy nowe centroidy, jak poniżej:
    Algorytm grupowania K-średnich
  • Następnie ponownie przypiszemy każdy punkt danych do nowej centroidy. W tym celu powtórzymy ten sam proces znajdowania linii środkowej. Mediana będzie wyglądać jak na obrazku poniżej:
    Algorytm grupowania K-średnich

Na powyższym obrazku widać, że jeden żółty punkt znajduje się po lewej stronie linii, a dwa niebieskie punkty tuż przy linii. Zatem te trzy punkty zostaną przypisane do nowych centroidów.

Algorytm grupowania K-średnich

Ponieważ nastąpiło ponowne przypisanie, ponownie przejdziemy do kroku 4, czyli znalezienia nowych centroid lub punktów K.

  • Powtórzymy proces, znajdując środek ciężkości centroidów, dzięki czemu nowe centroidy będą wyglądać tak, jak pokazano na poniższym obrazku:
    Algorytm grupowania K-średnich
  • Gdy otrzymamy nowe centroidy, ponownie narysujemy linię środkową i ponownie przypiszemy punkty danych. Zatem obraz będzie:
    Algorytm grupowania K-średnich
  • Widzimy na powyższym obrazku; po obu stronach linii nie ma odmiennych punktów danych, co oznacza, że ​​nasz model został utworzony. Rozważ poniższy obraz:
    Algorytm grupowania K-średnich

Ponieważ nasz model jest już gotowy, możemy teraz usunąć przyjęte centroidy, a dwa końcowe skupienia będą wyglądać tak, jak pokazano na poniższym obrazku:

Algorytm grupowania K-średnich

Jak wybrać wartość „K liczby klastrów” w klastrowaniu K-średnich?

Wydajność algorytmu grupowania K-średnich zależy od wysoce wydajnych klastrów, które tworzy. Jednak wybór optymalnej liczby klastrów jest dużym zadaniem. Istnieje kilka różnych sposobów znalezienia optymalnej liczby skupień, ale tutaj omawiamy najbardziej odpowiednią metodę znalezienia liczby skupień lub wartości K. Metodę podano poniżej:

Metoda łokciowa

Metoda Elbow jest jednym z najpopularniejszych sposobów znajdowania optymalnej liczby skupień. Metoda ta wykorzystuje koncepcję wartości WCSS. WCSS oznacza W obrębie skupienia Suma kwadratów , który definiuje całkowite zróżnicowanie w obrębie klastra. Poniżej podano wzór na obliczenie wartości WCSS (dla 3 skupień):

WCSS= ∑Pi w klastrze 1odległość (strIC1)2+∑Pi w Klastrze 2odległość (strIC2)2+∑Pi w CLuster3odległość (strIC3)2

W powyższym wzorze WCSS,

programowanie w tablicach C

Pi w klastrze 1odległość (strIC1)2: Jest to suma kwadratów odległości pomiędzy każdym punktem danych a jego środkiem ciężkości w obrębie klastra1 i taka sama dla pozostałych dwóch składników.

Aby zmierzyć odległość między punktami danych a środkiem ciężkości, możemy zastosować dowolną metodę, taką jak odległość euklidesowa lub odległość Manhattanu.

Aby znaleźć optymalną wartość skupień, metoda łokcia wykonuje poniższe kroki:

  • Wykonuje grupowanie K-średnich na danym zbiorze danych dla różnych wartości K (zakresy od 1-10).
  • Dla każdej wartości K oblicza wartość WCSS.
  • Rysuje krzywą pomiędzy obliczonymi wartościami WCSS a liczbą skupień K.
  • Ostry punkt zagięcia lub punkt działki wygląda jak ramię, wtedy ten punkt jest uważany za najlepszą wartość K.

Ponieważ wykres pokazuje ostry zakręt, który wygląda jak łokieć, stąd nazywa się to metodą łokcia. Wykres metody łokciowej wygląda jak na poniższym obrazku:

Algorytm grupowania K-średnich

Uwaga: Możemy wybrać liczbę skupień równą danym punktom danych. Jeśli wybierzemy liczbę skupień równą punktom danych, wówczas wartość WCSS wyniesie zero i będzie to punkt końcowy wykresu.

Implementacja w Pythonie algorytmu grupowania K-średnich

W powyższej sekcji omówiliśmy algorytm K-średnich, teraz zobaczmy, jak można go zaimplementować za pomocą Pyton .

Przed wdrożeniem zastanówmy się, jaki rodzaj problemu tutaj rozwiążemy. Mamy zatem zbiór danych Centrum handlowe_Klienci , czyli dane klientów, którzy odwiedzają centrum handlowe i dokonują w nim zakupów.

W danym zbiorze danych mamy Customer_Id, płeć, wiek, roczny dochód ($) i wynik wydatków (czyli obliczona wartość tego, ile klient wydał w centrum handlowym, im większa wartość, tym więcej wydał). Na podstawie tego zbioru danych musimy obliczyć pewne wzorce, ponieważ jest to metoda nienadzorowana, więc nie wiemy, co dokładnie obliczyć.

Poniżej przedstawiono kroki, które należy wykonać w celu wdrożenia:

    Wstępne przetwarzanie danych Znalezienie optymalnej liczby skupień metodą łokcia Uczenie algorytmu K-średnich na zbiorze danych uczących Wizualizacja klastrów

Krok 1: Wstępne przetwarzanie danych Krok

Pierwszym krokiem będzie wstępne przetwarzanie danych, tak jak to zrobiliśmy w naszych wcześniejszych tematach Regresja i Klasyfikacja. Jednak w przypadku problemu grupowania będzie się on różnić od innych modeli. Omówmy to:

    Importowanie bibliotek
    Podobnie jak to robiliśmy w poprzednich tematach, najpierw zaimportujemy biblioteki dla naszego modelu, co jest częścią wstępnego przetwarzania danych. Kod podano poniżej:
 # importing libraries import numpy as nm import matplotlib.pyplot as mtp import pandas as pd 

W powyższym kodzie tępy zaimportowaliśmy do wykonania obliczeń matematycznych, matplotlib służy do wykreślania wykresu, oraz pandy służą do zarządzania zbiorem danych.

    Importowanie zbioru danych:
    Następnie zaimportujemy zbiór danych, którego potrzebujemy. Zatem tutaj używamy zbioru danych Mall_Customer_data.csv. Można go zaimportować za pomocą poniższego kodu:
 # Importing the dataset dataset = pd.read_csv('Mall_Customers_data.csv') 

Wykonując powyższe linie kodu, otrzymamy nasz zbiór danych w Spyder IDE. Zbiór danych wygląda jak na poniższym obrazku:

Algorytm grupowania K-średnich

Z powyższego zbioru danych musimy znaleźć w nim pewne wzorce.

    Wyodrębnianie zmiennych niezależnych

Tutaj nie potrzebujemy żadnej zmiennej zależnej na etapie wstępnego przetwarzania danych, ponieważ jest to problem grupowania i nie mamy pojęcia, co określić. Dodamy więc po prostu linię kodu dla macierzy funkcji.

 x = dataset.iloc[:, [3, 4]].values 

Jak widzimy, wyodrębniamy tylko 3r & Di 4tfunkcja. Dzieje się tak dlatego, że do wizualizacji modelu potrzebujemy wykresu 2D, a niektóre funkcje, takie jak identyfikator_klienta, nie są wymagane.

Krok 2: Znalezienie optymalnej liczby skupień metodą łokcia

W drugim kroku spróbujemy znaleźć optymalną liczbę skupień dla naszego problemu grupowania. Zatem, jak omówiono powyżej, w tym celu użyjemy metody łokcia.

Jak wiemy, metoda łokcia wykorzystuje koncepcję WCSS do narysowania wykresu poprzez wykreślenie wartości WCSS na osi Y i liczby skupień na osi X. Zatem obliczymy wartość WCSS dla różnych wartości k z zakresu od 1 do 10. Poniżej znajduje się kod:

myflixer
 #finding optimal number of clusters using the elbow method from sklearn.cluster import KMeans wcss_list= [] #Initializing the list for the values of WCSS #Using for loop for iterations from 1 to 10. for i in range(1, 11): kmeans = KMeans(n_clusters=i, init='k-means++', random_state= 42) kmeans.fit(x) wcss_list.append(kmeans.inertia_) mtp.plot(range(1, 11), wcss_list) mtp.title('The Elobw Method Graph') mtp.xlabel('Number of clusters(k)') mtp.ylabel('wcss_list') mtp.show() 

Jak widać w powyższym kodzie, użyliśmy KMeans klasa sklear. bibliotekę klastrów do tworzenia klastrów.

Następnie stworzyliśmy lista_wcss zmienna inicjująca pustą listę, która jest używana do przechowywania wartości wcss obliczonej dla różnych wartości k z zakresu od 1 do 10.

Następnie zainicjowaliśmy pętlę for dla iteracji na innej wartości k z zakresu od 1 do 10; ponieważ pętla for w Pythonie wyklucza limit ruchu wychodzącego, więc przyjmuje się, że 11 obejmuje 10twartość.

Pozostała część kodu jest podobna jak w poprzednich tematach, ponieważ dopasowaliśmy model do macierzy cech, a następnie wykreśliliśmy wykres pomiędzy liczbą klastrów i WCSS.

Wyjście: Po wykonaniu powyższego kodu otrzymamy poniższe dane wyjściowe:

Algorytm grupowania K-średnich

Z powyższego wykresu widać, że punkt łokcia znajduje się w punkcie 5. Zatem liczba skupień tutaj będzie wynosić 5.

Algorytm grupowania K-średnich

Krok 3: Uczenie algorytmu K-średnich na zbiorze danych uczących

Ponieważ mamy już liczbę klastrów, możemy teraz trenować model na zbiorze danych.

Aby wytrenować model, użyjemy tych samych dwóch linii kodu, co w powyższej sekcji, ale tutaj zamiast używać i, użyjemy 5, ponieważ wiemy, że należy utworzyć 5 klastrów. Kod podano poniżej:

 #training the K-means model on a dataset kmeans = KMeans(n_clusters=5, init='k-means++', random_state= 42) y_predict= kmeans.fit_predict(x) 

Pierwsza linia jest taka sama jak powyżej przy tworzeniu obiektu klasy KMeans.

W drugiej linii kodu utworzyliśmy zmienną zależną y_predict do trenowania modelu.

Wykonując powyższe linie kodu otrzymamy zmienną y_predict. Możemy to sprawdzić pod eksplorator zmiennych opcja w Spyder IDE. Możemy teraz porównać wartości y_predict z naszym oryginalnym zbiorem danych. Rozważ poniższy obraz:

Algorytm grupowania K-średnich

Z powyższego obrazu możemy teraz stwierdzić, że identyfikator klienta 1 należy do klastra

3 (ponieważ indeks zaczyna się od 0, zatem 2 będzie traktowane jako 3), a 2 należy do skupienia 4 i tak dalej.

Krok 4: Wizualizacja klastrów

Ostatnim krokiem jest wizualizacja klastrów. Ponieważ w naszym modelu mamy 5 skupień, dlatego będziemy wizualizować każdy klaster jeden po drugim.

Do wizualizacji klastrów zostanie użyty wykres punktowy przy użyciu funkcji mtp.scatter() biblioteki matplotlib.

 #visulaizing the clusters mtp.scatter(x[y_predict == 0, 0], x[y_predict == 0, 1], s = 100, c = 'blue', label = 'Cluster 1') #for first cluster mtp.scatter(x[y_predict == 1, 0], x[y_predict == 1, 1], s = 100, c = 'green', label = 'Cluster 2') #for second cluster mtp.scatter(x[y_predict== 2, 0], x[y_predict == 2, 1], s = 100, c = 'red', label = 'Cluster 3') #for third cluster mtp.scatter(x[y_predict == 3, 0], x[y_predict == 3, 1], s = 100, c = 'cyan', label = 'Cluster 4') #for fourth cluster mtp.scatter(x[y_predict == 4, 0], x[y_predict == 4, 1], s = 100, c = 'magenta', label = 'Cluster 5') #for fifth cluster mtp.scatter(kmeans.cluster_centers_[:, 0], kmeans.cluster_centers_[:, 1], s = 300, c = 'yellow', label = 'Centroid') mtp.title('Clusters of customers') mtp.xlabel('Annual Income (k$)') mtp.ylabel('Spending Score (1-100)') mtp.legend() mtp.show() 

W powyższych linijkach kodu napisaliśmy kod dla poszczególnych klastrów w zakresie od 1 do 5. Pierwsza współrzędna mtp.scatter, czyli x[y_predict == 0, 0] zawierająca wartość x służącą do przedstawienia macierzy funkcje wartości, a y_predict mieści się w zakresie od 0 do 1.

Wyjście:

Algorytm grupowania K-średnich

Obraz wyjściowy wyraźnie pokazuje pięć różnych klastrów w różnych kolorach. Klastry powstają pomiędzy dwoma parametrami zbioru danych; Roczny dochód klienta i wydatki. Możemy zmienić kolory i etykiety zgodnie z wymaganiami lub wyborem. Możemy również zaobserwować pewne punkty z powyższych wzorców, które podano poniżej:

    Klaster 1pokazuje klientów ze średnim wynagrodzeniem i średnimi wydatkami, dzięki czemu możemy sklasyfikować tych klientów jako
  • Klaster 2 pokazuje, że klient ma wysokie dochody, ale niskie wydatki, więc możemy go sklasyfikować jako ostrożny .
  • Skupienie 3 pokazuje niskie dochody, a także niskie wydatki, więc można je sklasyfikować jako rozsądne.
  • Klaster 4 pokazuje klientów o niskich dochodach i bardzo wysokich wydatkach, dzięki czemu można ich sklasyfikować jako niedbały .
  • Skupienie 5 pokazuje klientów o wysokich dochodach i wysokich wydatkach, dzięki czemu można ich zaklasyfikować jako docelowych, a ci klienci mogą być klientami najbardziej dochodowymi dla właściciela centrum handlowego.