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 uitkomst op basis van de dichtstbijzijnde punten of dichtstbijzijnde middelpunten.
Tegenwoordig 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 training.
- Voor LDA, QDA of GNB is training slechts het berekenen van gemiddelden en varianties. En er zijn ook geen echte hyperparameters.
Nu gaan 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.
Doel van k-middelen
In de trainingsgegevensset zijn 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 ontdekt 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 ligt k-betekent dichter bij: de k-NN-classificator of de dichtstbijzijnde Centroid-classificator?
Laat u niet misleiden door de 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 ligt veel dichter bij de 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 de 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 geschikte direct uit de data.
Het zakelijke probleem is compleet anders: in plaats van labels te voorspellen, proberen we dat te doen creëren hen.
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 kenmerk
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 zal “leren” door stap voor stap te raden.
Hier komt het algoritme genoemd Lloyd’s algoritme.
We zullen het in Excel implementeren met de volgende lus:
- kies 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 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 twee afstandswaarden voor elk punt.
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 totdat convergentie is bereikt
Nu kunnen we in Excel, dankzij de formules, eenvoudig plak de nieuwe zwaartepuntwaarden in de cellen van de initiële zwaartepunten.
De update vindt onmiddellijk plaats en nadat u dit een paar keer hebt gedaan, zult u zien dat de waarden niet meer veranderen. Dat is wanneer het algoritme is geconvergeerd.
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 kenmerken gebruiken. Het proces is precies hetzelfde, we gebruiken eenvoudigweg de Euclidische afstand in 2D.
Je kunt ofwel de kopieer en plak de nieuwe zwaartepunten als waarden (met slechts een paar cellen om bij te werken),
of u kunt weergeven alle tussenstappen om de volledige evolutie 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 plots 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 op deze afbeelding kunt zien, werd het werkblad behoorlijk ongeorganiseerd, vooral vergeleken met de eerdere 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,
- bereken de luiheidwat de som is 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 algemene 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 kleiner.
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 voor het artikel van morgen: de versie zonder toezicht van de Dichtstbijzijnde Centroid-classificator is inderdaad k-betekent.
Dus wat zou de versie zonder toezicht zijn van LDA of QDA? Wij zullen dit in het volgende artikel beantwoorden.
