4 in 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 we bepalen de output van de dichtstbijzijnde punten of dichtstbijzijnde centra.
Vandaag blijven we in dezelfde familie van ideeën. Maar we gebruiken de 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 Nearest Centroid-classificator?
En als je het je herinnert, was er voor alle modellen die we tot nu toe hebben gezien niet echt een ‘trainingsfase’ of afstemming van hyperparameters.
- Voor k-NN is er helemaal geen opleiding.
- Voor LDA, QDA of GNB berekent training alleen gemiddelden en varianties. En er zijn ook geen echte hyperparameters.
Nu moeten we met k-means een trainingsalgoritme implementeren dat er eindelijk uitziet als ‘echt’ machinaal leren.
We beginnen met een klein 1D-voorbeeld. Dan gaan we naar 2D.
Maatregel voor k-middelen
In de trainingsdataset is er geen initiële labels.
Het doel van k-means is om creëren betekenisvolle labels door punten te groeperen die dicht bij elkaar liggen.
Laten we naar de onderstaande illustratie kijken. Je kunt duidelijk twee groepen punten zien. 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 geeft een zeer intuïtief beeld van hoe k-means structuur detecteert met behulp van alleen afstanden.
En hier betekent k het aantal centra dat we proberen te vinden.
Laten we nu de vraag beantwoorden: Welk algoritme is k-means dichterbij, de k-NN-classificator of de Nearest Centroid-classificator?
Laat je niet misleiden k in k-NN en k-middelen.
Ze bedoelen niet hetzelfde:
- in k-NN, k is het aantal buren, niet het aantal klassen;
- in k-betekent, k is het aantal zwaartepunten.
K-betekent is veel dichterbij Dichtstbijzijnde Centroid-classificator.
Beide modellen worden vertegenwoordigd door zwaartepuntenen voor een nieuwe waarneming berekenen we eenvoudigweg de afstand tot elk zwaartepunt om te beslissen tot welk zwaartepunt het behoort.
Het verschil is natuurlijk dat in Dichtstbijzijnde Centroid-classificatorwij al weten de zwaartepunten omdat ze uit gelabelde klassen komen.
IN k-betekentwe kennen de zwaartepunten niet. Het hele doel van het algoritme is om ontdekken direct uit de data te halen.
Het zakelijke probleem is compleet anders: in plaats van labels te voorspellen, proberen we dat te doen creëren Jij.
En in k betekent de waarde van k (aantal zwaartepunten) is onbekend. Het zal er dus één zijn hyperparameter dat we kunnen afstemmen.
k-betekent met slechts één functie
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 meteen de twee zwaartepunten kunnen zien.
1, 2, 3, 11, 12, 13
Ja, 2 en 12.
Maar hoe zou de computer dat weten? De machine zal “leren” door stap voor stap te raden.
Hier komt het algoritme genaamd Lloyd’s algoritme.
We implementeren het in Excel met de volgende lus:
- selecteer 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. Selecteer de initiële zwaartepunten
Selecteer twee initiële centra, bijvoorbeeld:
Ze moeten binnen het gegevensbereik liggen (tussen 1 en 13).
2. Bereken afstanden
Voor elk gegevenspunt x:
- bereken de afstand tot c_1,
- bereken de afstand tot c_2.
Meestal gebruiken we absolute afstand in 1D.
We hebben nu voor elk punt twee afstandswaarden.
3. Clusters toewijzen
Voor elk punt:
- vergelijk de twee afstanden,
- wijs het cluster van de kleinste toe (1 of 2).
In Excel is dit eenvoudig IF of MIN gebaseerde logica.
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 dit tot convergentie
Nu in Excel, dankzij de formules, kunnen we dat gewoon voeg de nieuwe zwaartepuntwaarden in in de cellen van de initiële zwaartepunten.
De update vindt onmiddellijk plaats en nadat je dit een paar keer hebt gedaan, zul je zien dat de waarden niet meer veranderen. Dit is wanneer het algoritme wordt geconvergeerd.
Ook kunnen we elke stap in Excel vastleggen, zodat we kunnen zien hoe de zwaartepunten en clusters zich in de loop van de tijd ontwikkelen.
k-betekent met twee functies
Laten we nu twee functies gebruiken. Het proces is precies hetzelfde, we gebruiken alleen de Euclidische afstand in 2D.
Je kunt het allebei doen kopieer en plak de nieuwe zwaartepunten als waarden (met slechts een paar cellen om bij te werken),
of je kunt het laten zien alle tussenstappen om de volledige ontwikkeling van het algoritme te zien.
Visualisatie van de bewegende zwaartepunten 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 visualisaties, en de gegevenstabellen worden al snel een beetje ingewikkeld om te organiseren.
Als je een volledig voorbeeld met gedetailleerde grafieken wilt zien, kun je dit artikel lezen dat ik bijna drie jaar geleden schreef, waarin elke stap van de beweging van het zwaartepunt duidelijk wordt weergegeven.
Zoals u in deze afbeelding kunt zien, werd het werkblad behoorlijk ongeorganiseerd, vooral vergeleken met de vorige tabel, die erg eenvoudig was.
De optimale k kiezen: de elleboogmethode
Dus nu is het mogelijk om het te proberen k = 2 En k = 3 in ons geval, en bereken de traagheid voor elk ervan. Dan vergelijken we eenvoudigweg de waarden.
We kunnen zelfs beginnen met k=1.
Voor elke waarde van k:
- we voeren k-Means uit tot convergentie,
- berekenen luiheiddat is de som van de kwadratische afstanden tussen elk punt en het toegewezen zwaartepunt.
In Excel:
- Neem voor elk punt de afstand tot het zwaartepunt en maak het vierkant.
- Tel al deze kwadratische afstanden bij elkaar op.
- Dit geeft de traagheid voor deze k.
Bijvoorbeeld:
- voor k = 1 is het zwaartepunt slechts het gecombineerde gemiddelde van x1 en x2,
- voor k = 2 en k = 3 nemen we de geconvergeerde zwaartepunten van de bladen waarop u het algoritme hebt uitgevoerd.
Dan 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 veel af,
- van 2 naar 3 is de verbetering veel minder.
De “elleboog” is de waarde van k waarna 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 naar het artikel van morgen: de versie zonder toezicht van Dichtstbijzijnde Centroid-classificator is waar k-betekent.
Dus wat zou de onbeheerde versie zijn van LDA of QDA? Daar zullen we in het volgende artikel antwoord op geven.
.png "Voguing of Noguing? Het Ballroom-discours, uitgelegd")
