logo

K-Means Clustering Algorithm

K-Means Clustering je algoritmus učení bez dozoru, který se používá k řešení problémů se shlukováním ve strojovém učení nebo vědě o datech. V tomto tématu se naučíme, co je to algoritmus shlukování K-means, jak tento algoritmus funguje, spolu s implementací k-means clusteringu v Pythonu.

Co je K-Means Algorithm?

K-Means Clustering je Algoritmus učení bez dozoru , který seskupuje neoznačenou datovou sadu do různých shluků. Zde K definuje počet předdefinovaných shluků, které je třeba v procesu vytvořit, jako když K=2, budou dva shluky a pro K=3 budou tři shluky a tak dále.

Jedná se o iterativní algoritmus, který rozděluje neoznačenou datovou sadu do k různých shluků takovým způsobem, že každá datová sada patří pouze do jedné skupiny, která má podobné vlastnosti.

Umožňuje nám seskupovat data do různých skupin a je to pohodlný způsob, jak samostatně zjišťovat kategorie skupin v neoznačené sadě dat bez nutnosti jakéhokoli školení.

Je to algoritmus založený na centroidech, kde je každý shluk spojen s těžištěm. Hlavním cílem tohoto algoritmu je minimalizovat součet vzdáleností mezi datovým bodem a jejich odpovídajícími shluky.

Algoritmus vezme neoznačenou datovou sadu jako vstup, rozdělí datovou sadu na k-počet shluků a opakuje proces, dokud nenajde nejlepší shluky. Hodnota k by měla být v tomto algoritmu předem určena.

K-prostředky shlukování Algoritmus plní hlavně dva úkoly:

  • Určuje nejlepší hodnotu pro K středových bodů nebo těžišť iterativním procesem.
  • Přiřadí každý datový bod jeho nejbližšímu k-centru. Datové body, které jsou blízko konkrétního k-centra, vytvářejí shluk.

Každý cluster má tedy datové body s některými společnými znaky a je vzdálený od ostatních clusterů.

Níže uvedený diagram vysvětluje fungování K-means Clustering Algorithm:

K-Means Clustering Algorithm

Jak funguje algoritmus K-Means?

Fungování algoritmu K-Means je vysvětleno v následujících krocích:

Krok 1: Výběrem čísla K určíte počet shluků.

Krok 2: Vyberte náhodných K bodů nebo těžišť. (Může to být jiné ze vstupní datové sady).

Krok 3: Přiřaďte každý datový bod jejich nejbližšímu těžišti, které bude tvořit předdefinované K shluky.

Krok 4: Vypočítejte rozptyl a umístěte nové těžiště každého shluku.

Krok 5: Opakujte třetí kroky, což znamená, že každý datový bod znovu přiřadíte k novému nejbližšímu těžišti každého clusteru.

Krok 6: Pokud dojde k nějaké změně přiřazení, přejděte ke kroku 4, jinak přejděte na FINISH.

java tutoriály

Krok-7 : Model je připraven.

Pojďme porozumět výše uvedeným krokům s ohledem na vizuální grafy:

Předpokládejme, že máme dvě proměnné M1 a M2. Bodový graf na ose x-y těchto dvou proměnných je uveden níže:

K-Means Clustering Algorithm
  • Vezměme počet k shluků, tj. K=2, abychom identifikovali datovou sadu a rozdělili je do různých shluků. To znamená, že se zde pokusíme seskupit tyto datové sady do dvou různých shluků.
  • K vytvoření shluku potřebujeme vybrat několik náhodných k bodů nebo těžišť. Těmito body mohou být buď body z datové sady, nebo jakýkoli jiný bod. Zde tedy vybíráme níže uvedené dva body jako k bodů, které nejsou součástí naší datové sady. Zvažte následující obrázek:
    K-Means Clustering Algorithm
  • Nyní přiřadíme každý datový bod bodového grafu jeho nejbližšímu K-bodu nebo těžišti. Vypočítáme to použitím nějaké matematiky, kterou jsme studovali, abychom vypočítali vzdálenost mezi dvěma body. Nakreslíme tedy medián mezi oběma těžišti. Zvažte následující obrázek:
    K-Means Clustering Algorithm

Z obrázku výše je zřejmé, že body na levé straně čáry jsou blízko K1 nebo modrého těžiště a body napravo od čáry jsou blízko žlutého těžiště. Vybarvíme je jako modrou a žlutou pro jasnou vizualizaci.

K-Means Clustering Algorithm
  • Jelikož potřebujeme najít nejbližší shluk, tak výběr zopakujeme nový centroid . Chcete-li vybrat nová těžiště, vypočítáme těžiště těchto těžišť a najdeme nová těžiště, jak je uvedeno níže:
    K-Means Clustering Algorithm
  • Dále přiřadíme každý datový bod novému těžišti. K tomu zopakujeme stejný proces hledání střední čáry. Medián bude vypadat jako na obrázku níže:
    K-Means Clustering Algorithm

Z obrázku výše vidíme, že jeden žlutý bod je na levé straně čáry a dva modré body jsou vpravo od čáry. Takže tyto tři body budou přiřazeny novým centroidům.

K-Means Clustering Algorithm

Protože došlo k přeřazení, přejdeme opět ke kroku 4, kterým je hledání nových centroidů nebo K-bodů.

  • Proces zopakujeme nalezením těžiště těžišť, takže nová těžiště budou vypadat jako na obrázku níže:
    K-Means Clustering Algorithm
  • Když jsme dostali nové těžiště, znovu nakreslíme střední čáru a znovu přiřadíme datové body. Obrázek tedy bude:
    K-Means Clustering Algorithm
  • Můžeme vidět na obrázku výše; na žádné straně čáry nejsou žádné odlišné datové body, což znamená, že je vytvořen náš model. Zvažte následující obrázek:
    K-Means Clustering Algorithm

Protože je náš model připraven, můžeme nyní odstranit předpokládaná těžiště a dva poslední shluky budou vypadat jako na obrázku níže:

K-Means Clustering Algorithm

Jak zvolit hodnotu 'K počtu shluků' v K-means Clustering?

Výkon algoritmu shlukování K-means závisí na vysoce účinných shlucích, které tvoří. Ale vybrat optimální počet shluků je velký úkol. Existuje několik různých způsobů, jak najít optimální počet shluků, ale zde diskutujeme o nejvhodnější metodě, jak zjistit počet shluků nebo hodnotu K. Metoda je uvedena níže:

Metoda loktů

Metoda Elbow je jedním z nejoblíbenějších způsobů, jak najít optimální počet shluků. Tato metoda využívá koncept hodnoty WCSS. WCSS znamená V rámci klastrového součtu čtverců , který definuje celkové variace v rámci shluku. Vzorec pro výpočet hodnoty WCSS (pro 3 clustery) je uveden níže:

WCSS= ∑Pi v Clusteru1vzdálenost (PiC1)2+∑Pi v Clusteru2vzdálenost (PiC2)2+∑Pi v CLusteru3vzdálenost (PiC3)2

Ve výše uvedeném vzorci WCSS,

Pi v Clusteru1vzdálenost (PiC1)2: Je součtem druhé mocniny vzdáleností mezi každým datovým bodem a jeho těžištěm v rámci clusteru1 a stejný pro další dva členy.

K měření vzdálenosti mezi datovými body a těžištěm můžeme použít jakoukoli metodu, jako je euklidovská vzdálenost nebo vzdálenost na Manhattanu.

Chcete-li najít optimální hodnotu shluků, metoda kolena se řídí následujícími kroky:

  • Provádí shlukování K-means na dané datové sadě pro různé hodnoty K (rozsahy od 1 do 10).
  • Pro každou hodnotu K vypočítá hodnotu WCSS.
  • Vynese křivku mezi vypočtenými hodnotami WCSS a počtem shluků K.
  • Ostrý bod ohybu nebo bod grafu vypadá jako paže, pak je tento bod považován za nejlepší hodnotu K.

Vzhledem k tomu, že graf ukazuje ostrý ohyb, který vypadá jako loket, je znám jako metoda lokte. Graf pro metodu lokte vypadá jako na obrázku níže:

K-Means Clustering Algorithm

Poznámka: Můžeme zvolit počet shluků rovný daným datovým bodům. Pokud zvolíme počet shluků rovný datovým bodům, pak bude hodnota WCSS nulová a to bude konečný bod grafu.

Implementace K-means Clustering Algorithm v Pythonu

Ve výše uvedené části jsme diskutovali o algoritmu K-means, nyní se podívejme, jak jej lze implementovat pomocí Krajta .

Před implementací si ujasněme, jaký typ problému zde budeme řešit. Máme tedy datovou sadu Mall_Customers , což jsou data zákazníků, kteří obchodní centrum navštíví a utratí tam.

V daném datovém souboru máme Customer_Id, Gender, Age, Roční příjem ($) a Spending Score (což je vypočítaná hodnota toho, kolik zákazník utratil v nákupním centru, čím vyšší hodnota, tím více utratí). Z této datové sady potřebujeme vypočítat nějaké vzory, protože je to metoda bez dozoru, takže nevíme, co přesně vypočítat.

Kroky, které je třeba dodržet při implementaci, jsou uvedeny níže:

    Předzpracování dat Nalezení optimálního počtu shluků metodou lokte Trénink algoritmu K-means na trénovací datové sadě Vizualizace shluků

Krok 1: Předzpracování dat Krok

Prvním krokem bude předběžné zpracování dat, jak jsme to dělali v našich dřívějších tématech Regrese a klasifikace. Ale pro problém shlukování se bude lišit od ostatních modelů. Pojďme o tom diskutovat:

    Import knihoven
    Stejně jako v předchozích tématech nejprve naimportujeme knihovny pro náš model, který je součástí předzpracování dat. Kód je uveden níže:
 # importing libraries import numpy as nm import matplotlib.pyplot as mtp import pandas as pd 

Ve výše uvedeném kódu je nemotorný importovali jsme pro provádění matematického výpočtu, matplotlib slouží k vykreslení grafu a pandy slouží ke správě datové sady.

    Import datové sady:
    Dále importujeme datovou sadu, kterou potřebujeme použít. Zde tedy používáme datovou sadu Mall_Customer_data.csv. Lze jej importovat pomocí níže uvedeného kódu:
 # Importing the dataset dataset = pd.read_csv('Mall_Customers_data.csv') 

Spuštěním výše uvedených řádků kódu získáme naši datovou sadu v Spyder IDE. Dataset vypadá jako na obrázku níže:

K-Means Clustering Algorithm

Z výše uvedeného datasetu v něm musíme najít nějaké vzory.

    Extrahování nezávislých proměnných

Zde nepotřebujeme žádnou závislou proměnnou pro krok předběžného zpracování dat, protože jde o problém shlukování a nemáme ponětí o tom, co určit. Takže jen přidáme řádek kódu pro matici funkcí.

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

Jak vidíme, extrahujeme pouze 3rda 4čtVlastnosti. Je to proto, že k vizualizaci modelu potřebujeme 2D graf a některé funkce nejsou vyžadovány, například customer_id.

Krok 2: Nalezení optimálního počtu shluků pomocí metody kolen

Ve druhém kroku se pokusíme najít optimální počet shluků pro náš shlukovací problém. Takže, jak bylo diskutováno výše, zde pro tento účel použijeme metodu lokte.

Jak víme, kolenová metoda používá koncept WCSS k vykreslení grafu vynesením hodnot WCSS na osu Y a počtu shluků na ose X. Vypočítáme tedy hodnotu pro WCSS pro různé hodnoty k v rozmezí od 1 do 10. Níže je uveden její kód:

 #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 můžeme vidět ve výše uvedeném kódu, použili jsme KMeans třída sklearn. klastrovou knihovnu k vytvoření klastrů.

Dále jsme vytvořili wcss_list proměnnou pro inicializaci prázdného seznamu, který se používá k uložení hodnoty wcss vypočítané pro různé hodnoty k v rozmezí od 1 do 10.

Poté jsme inicializovali cyklus for pro iteraci na jinou hodnotu k v rozsahu od 1 do 10; protože for smyčka v Pythonu vylučte odchozí limit, takže se bere jako 11, aby zahrnovalo 10čthodnota.

Zbývající část kódu je podobná jako v předchozích tématech, protože jsme model přizpůsobili matici funkcí a poté vykreslili graf mezi počtem shluků a WCSS.

Výstup: Po provedení výše uvedeného kódu získáme níže uvedený výstup:

K-Means Clustering Algorithm

Z výše uvedeného grafu můžeme vidět, že bod lokte je v 5. Takže počet shluků zde bude 5.

K-Means Clustering Algorithm

Krok 3: Trénink algoritmu K-means na trénovací datové sadě

Protože máme počet shluků, můžeme nyní model trénovat na datové sadě.

K trénování modelu použijeme stejné dva řádky kódu, jaké jsme použili ve výše uvedené části, ale zde místo použití i použijeme 5, protože víme, že je třeba vytvořit 5 shluků. Kód je uveden níže:

 #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) 

První řádek je stejný jako výše pro vytvoření objektu třídy KMeans.

Na druhém řádku kódu jsme vytvořili závislou proměnnou y_předpovědět trénovat modelku.

Spuštěním výše uvedených řádků kódu získáme proměnnou y_predict. Můžeme to zkontrolovat níže proměnný průzkumník možnost v Spyder IDE. Nyní můžeme porovnat hodnoty y_predict s naší původní datovou sadou. Zvažte následující obrázek:

K-Means Clustering Algorithm

Z výše uvedeného obrázku nyní můžeme zjistit, že CustomerID 1 patří do clusteru

3 (protože index začíná od 0, proto 2 bude považováno za 3) a 2 patří do shluku 4 a tak dále.

Krok 4: Vizualizace klastrů

Posledním krokem je vizualizace shluků. Protože máme pro náš model 5 shluků, budeme každý shluk vizualizovat jeden po druhém.

K vizualizaci shluků použijeme bodový graf pomocí funkce mtp.scatter() 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() 

Ve výše uvedených řádcích kódu jsme napsali kód pro každý shluky v rozsahu od 1 do 5. První souřadnice mtp.scatter, tj. x[y_predict == 0, 0] obsahující hodnotu x pro zobrazení matice obsahuje hodnoty a y_predict je v rozsahu od 0 do 1.

Výstup:

K-Means Clustering Algorithm

Výstupní obrázek jasně ukazuje pět různých shluků s různými barvami. Shluky jsou tvořeny mezi dvěma parametry datové sady; Roční příjem zákazníka a útrata. Můžeme změnit barvy a štítky podle požadavku nebo výběru. Můžeme také pozorovat některé body z výše uvedených vzorů, které jsou uvedeny níže:

    Shluk1zobrazuje zákazníky s průměrnou mzdou a průměrnou útratou, abychom je mohli kategorizovat jako
  • Cluster2 ukazuje, že zákazník má vysoký příjem, ale nízké výdaje, takže je můžeme kategorizovat jako opatrný .
  • Cluster3 ukazuje nízké příjmy a také nízké výdaje, takže je lze kategorizovat jako rozumné.
  • Cluster4 ukazuje zákazníky s nízkými příjmy s velmi vysokými výdaji, takže je lze zařadit do kategorií neopatrný .
  • Cluster5 ukazuje zákazníky s vysokými příjmy a vysokými výdaji, takže je lze zařadit do kategorie cílových, a tito zákazníci mohou být pro majitele obchodního centra těmi nejziskovějšími zákazníky.