4 van de Machine Learning Adventskalender.
De eerste drie dagen gingen we op verkenning op afstand gebaseerde modellen voor begeleid leren:
In al deze modellen was het idee hetzelfde: we meten afstanden en bepalen de output op basis van de dichtstbijzijnde punten of centra.
Vandaag de dag bevinden we ons nog steeds in dezelfde familie van ideeën. Maar we gebruiken afstanden op een onbewaakte manier: k-betekent.
Nu een vraag voor degenen die dit algoritme al kennen: k-means lijkt meer op welk model, de k-NN-classificator of de dichtstbijzijnde centroid-classificator?
En als je het je herinnert, was er voor alle modellen die we tot nu toe hebben gezien geen echte ’trainingsfase’ of afstemming van hyperparameters.
- Voor k-NN is er geen opleiding.
- Voor LDA, QDA of GNB omvat training eenvoudigweg het berekenen van gemiddelden en varianties. En er zijn niet eens echte hyperparameters.
Nu zullen we met k-means een trainingsalgoritme implementeren dat eindelijk op ‘echt’ machinaal leren zal lijken.
Laten we beginnen met een klein 1D-voorbeeld. Dan gaan we verder met 2D.
k-betekent objectief
In de trainingsdataset zijn aanwezig geen eerste label.
Het doel van k-means is om creëren betekenisvolle labels door punten dicht bij elkaar te groeperen.
Laten we de onderstaande illustratie eens bekijken. Je ziet duidelijk twee groepen stippen. Elk zwaartepunt (het rode vierkant en het groene vierkant) bevindt zich in het midden van zijn cluster en elk punt wordt toegewezen aan het dichtstbijzijnde punt.
Dit levert een zeer intuïtief beeld op van hoe k-means structuur ontdekt met behulp van alleen afstanden.
En hier geeft k het aantal centra aan dat we proberen te vinden.
Laten we nu de vraag beantwoorden: Welk algoritme is k-betekent het dichtst bij: de k-NN-classificator of de dichtstbijzijnde zwaartepuntclassificator?
Laat u niet misleiden door de k in k-NN’s en k-middelen.
Ze bedoelen niet hetzelfde:
- In k-NN, k het is het aantal buren, niet het aantal klassen;
- In k-betekent, k is het aantal zwaartepunten.
K-betekent dat het veel dichterbij is Dichtstbijzijnde zwaartepuntclassificator.
Beide modellen worden vertegenwoordigd door zwaartepuntenen voor een nieuwe waarneming berekenen we eenvoudigweg de afstand van elk zwaartepunt om te beslissen tot welk zwaartepunt het behoort.
Het verschil is natuurlijk dat in Dichtstbijzijnde zwaartepuntclassificatorwij hebben het al Weten zwaartepunten omdat ze uit gelabelde klassen komen.
In k-betekentwe kennen de zwaartepunten niet. Het hele doel van het algoritme is om ontdekken geschikte direct uit de data.
Het zakelijke probleem is compleet anders: in plaats van labels te voorspellen, proberen we het creëren Zij.
En in k-betekent de waarde van k (het aantal zwaartepunten) is onbekend. Het wordt dus een hyperparameter dat we kunnen afstemmen.
k-betekent met slechts één functie
Laten we beginnen met een klein 1D-voorbeeld zodat alles op één as zichtbaar is. En we zullen de waarden op zo’n triviale manier kiezen dat we onmiddellijk de twee zwaartepunten kunnen zien.
1, 2, 3, 11, 12, 13
Ja, 2 en 12.
Maar hoe zou de computer dat weten? De machine ‘leert’ door stap voor stap te raden.
Hier wordt het algoritme genoemd Lloyd’s algoritme.
We zullen het in Excel implementeren met de volgende lus:
- kies de initiële zwaartepunten
- bereken de afstand van elk punt tot elk zwaartepunt
- wijs elk punt toe aan het dichtstbijzijnde zwaartepunt
- bereken de zwaartepunten opnieuw als het gemiddelde van de punten in elk cluster
- herhaal stap 2 tot en met 4 totdat de zwaartepunten niet meer bewegen
1. Kies initiële zwaartepunten
Kies twee startcentra, bijvoorbeeld:
Ze moeten binnen het gegevensbereik vallen (tussen 1 en 13).
2. Bereken afstanden
Voor elk gegevenspunt x:
- bereken de afstand vanaf c_1,
- bereken de afstand vanaf c_2.
Meestal gebruiken we absolute afstand in 1D.
Nu hebben we voor elk punt twee afstandswaarden.
3. Clusters toewijzen
Voor elk punt:
- vergelijk de twee afstanden
- wijs het cluster van de kleinere toe (1 of 2).
In Excel is dit eenvoudig IF OF MIN logica gebaseerd.
4. Bereken de nieuwe zwaartepunten
Voor elk cluster:
- neem de punten die aan dat cluster zijn toegewezen,
- bereken hun gemiddelde,
- dit gemiddelde wordt het nieuwe zwaartepunt.
5. Herhaal totdat convergentie is bereikt
Nu kunnen we in Excel, dankzij formules, eenvoudigweg plak de nieuwe zwaartepuntwaarden in de cellen van de initiële zwaartepunten.
De update is onmiddellijk en na een paar keer uitvoeren zul je zien dat de waarden niet meer veranderen. Dit is het moment waarop het algoritme convergeert.
We kunnen elke stap ook in Excel vastleggen, zodat we kunnen zien hoe de zwaartepunten en clusters in de loop van de tijd evolueren.
k-betekent met twee kenmerken
Laten we nu twee functies gebruiken. Het proces is precies hetzelfde, we gebruiken eenvoudigweg de Euclidische afstand in 2D.
Je kunt de kopieer en plak de nieuwe zwaartepunten als waarden (met slechts een paar cellen om bij te werken),
of u kunt bekijken allemaal tussenstappen om de volledige evolutie van het algoritme te zien.
Bewegende zwaartepunten bekijken in Excel
Om het proces intuïtiever te maken, is het handig om grafieken te maken die laten zien hoe de zwaartepunten bewegen.
Helaas zijn Excel of Google Spreadsheets niet ideaal voor dit soort visualisatie, en gegevenstabellen worden al snel een beetje ingewikkeld om te organiseren.
Als je een compleet voorbeeld met gedetailleerde grafieken wilt zien, kun je dit artikel lezen dat ik bijna drie jaar geleden schreef, waarin elke stap van de zwaartepuntbeweging duidelijk wordt weergegeven.
Zoals u in deze afbeelding kunt zien, is het werkblad behoorlijk ongeorganiseerd geworden, vooral vergeleken met de vorige tabel, die heel eenvoudig was.
Keuze van de optimale k: de elleboogmethode
Dus nu kun je het proberen k = 2 EN k = 3 in ons geval, en bereken de traagheid voor elk. Dus laten we de waarden gewoon vergelijken.
We kunnen ook beginnen met k=1.
Voor elke waarde van k:
- we voeren k-Means uit tot convergentie,
- bereken de luiheiddat is de som van de kwadratische afstanden tussen elk punt en het toegewezen zwaartepunt.
In Excel:
- Neem voor elk punt de afstand vanaf het zwaartepunt en kwadraat deze.
- Voeg al deze vierkante afstanden toe.
- Dit geeft de traagheid voor deze k.
Bijvoorbeeld:
- voor k = 1 is het zwaartepunt slechts het algemene gemiddelde van x1 en x2,
- voor k = 2 en k = 3 nemen we de convergente zwaartepunten van de bladen waarop u het algoritme hebt uitgevoerd.
Vervolgens kunnen we de traagheid uitzetten als functie van k, bijvoorbeeld voor (k = 1, 2, 3).
Voor deze dataset
- van 1 naar 2 neemt de traagheid aanzienlijk af,
- van 2 naar 3 is de verbetering veel beperkter.
De “elleboog” is de waarde van k waarboven de afname van de traagheid marginaal wordt. In het voorbeeld suggereert dit dat k = 2 voldoende is.
Conclusie
K-means is een zeer intuïtief algoritme als je het stap voor stap in Excel ziet.
We beginnen met eenvoudige zwaartepunten, berekenen afstanden, wijzen punten toe, werken de zwaartepunten bij en herhalen. Nu kunnen we zien hoe “machines leren”, toch?
Welnu, dit is nog maar het begin, we zullen zien dat verschillende modellen op heel verschillende manieren ‘leren’.
En hier is de overgang voor het artikel van morgen: de versie zonder toezicht van de Dichtstbijzijnde zwaartepuntclassificator het is echt zo k-betekent.
Dus wat zou de versie zonder toezicht zijn van LDA OF QDA? Wij zullen dit in het volgende artikel beantwoorden.
