4 van de Machine Learning Adventskalender.
De eerste drie dagen hebben we de omgeving verkend op afstand gebaseerd model voor begeleid leren:
In al deze modellen is het idee hetzelfde: we meten de afstand en bepalen de uitvoer op basis van het dichtstbijzijnde punt of het dichtstbijzijnde centrum.
Vandaag de dag blijven we in dezelfde ideeëngroep. We gebruiken afstand echter 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 u het zich herinnert: voor alle modellen die we tot nu toe hebben bekeken, is er eigenlijk geen fase van ‘training’ of afstemming van hyperparameters.
- Voor k-NN is er helemaal geen opleiding.
- Voor LDA, QDA of GNB is training eenvoudigweg een middel voor computergebruik en variantie. En er zijn ook geen echte hyperparameters.
Nu zullen we met k-means een trainingsalgoritme implementeren dat er uiteindelijk uitziet als ‘echt’ machine learning.
We beginnen met een klein 1D-voorbeeld. Dan gaan we naar 2D.
Doel van k-middelen
In de trainingsgegevensset zijn er geen eerste label.
Het doel van k-means is om maken 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 (rode doos en groene doos) bevindt zich in het midden van de cluster en elk punt wordt op het dichtstbijzijnde punt geplaatst.
Dit levert een zeer intuïtief beeld op van hoe k-means structuur vindt met alleen afstanden.
En hier betekent k het aantal centra dat we proberen te vinden.
Laten we nu de vraag beantwoorden: Welk algoritme ligt dichter bij k-means, k-NN-classificator of Nearest Centroid-classificator?
Laat u niet misleiden door k in k-NN en k-middelen.
De betekenis is niet hetzelfde:
- in de k-NN, k is het aantal buren, niet het aantal klassen;
- in de k-betekent, k is het aantal zwaartepunten.
K-betekent is dichter bij Dichtstbijzijnde Centroid-classificator.
Beide modellen worden vertegenwoordigd door zwaartepunten voor nieuwe waarnemingen berekenen we eenvoudigweg de afstand tot elk massamiddelpunt om te bepalen welk massamiddelpunt het is.
Het verschil zit hem uiteraard in de onderdelen Dichtstbijzijnde Centroid-classificatorwij al weten zwaartepunt omdat het afkomstig is van de gelabelde klasse.
In de k-betekentwe kennen het zwaartepunt niet. Het algemene doel van dit algoritme is om vinden die rechtstreeks uit de data past.
Het zakelijke probleem is compleet anders: in plaats van labels te voorspellen, proberen we ze te doen maken zij.
En in k-betekent: waarde k (aantal zwaartepunten) is onbekend. Het wordt dus een hyperparameters die wij kunnen aanpassen.
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 zo kiezen dat we beide zwaartepunten direct kunnen zien.
1, 2, 3, 11, 12, 13
Ja, 2 en 12.
Maar hoe weet een computer dat? De machine zal “leren” door stap voor stap te raden.
Dit is het zogenaamde algoritme Lloyds algoritme.
We zullen het in Excel implementeren met de volgende lus:
- selecteer het startzwaartepunt
- Bereken de afstand van elk punt tot elk massamiddelpunt
- wijs elk punt toe aan het dichtstbijzijnde zwaartepunt
- herberekent het zwaartepunt als het gemiddelde van de punten in elk cluster
- Herhaal stap 2 tot en met 4 totdat het zwaartepunt niet meer beweegt
1. Selecteer het startzwaartepunt
Selecteer twee startcentra, bijvoorbeeld:
Ze moeten binnen het gegevensbereik liggen (tussen 1 en 13).
2. Bereken de afstand
Voor elk gegevenspunt x:
- bereken de afstand tot c_1,
- bereken de afstand tot c_2.
Meestal gebruiken we absolute afstanden in 1D.
We hebben nu voor elk punt twee afstandswaarden.
3. Clusters definiëren
Voor elk punt:
- vergelijk de twee afstanden,
- wijs het kleinste cluster toe (1 of 2).
In Excel is dit eenvoudig IF of MIN gebaseerd op logica.
4. Bereken het nieuwe zwaartepunt
Voor elk cluster:
- neem de punten die aan dat cluster zijn toegewezen,
- bereken het gemiddelde,
- Dit gemiddelde wordt het nieuwe massamiddelpunt.
5. Herhaal dit totdat convergentie is bereikt
Dankzij de formules kunnen we het nu in Excel eenvoudig doen plak de nieuwe zwaartepuntwaarde in de initiële zwaartepuntcellen.
De update wordt onmiddellijk uitgevoerd en nadat je dit een paar keer hebt gedaan, zul je merken dat de waarden niet meer veranderen. Dat is het moment waarop het algoritme samenkomt.
We kunnen ook elke stap in Excel registreren, 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 alleen de Euclidische afstand in 2D.
Dat kun je doen kopieer en plak het nieuwe zwaartepunt als waarde (met slechts een paar cellen om bij te werken),
of je kunt het weergeven allemaal tussenstappen om de volledige evolutie van het algoritme te zien.
Visualiseren van bewegende zwaartepunten in Excel
Om het proces intuïtiever te maken, is het handig om een grafiek te maken die laat zien hoe de zwaartepunten bewegen.
Helaas zijn Excel of Google Spreadsheets niet ideaal voor dit soort visualisaties, en worden gegevenstabellen al snel nogal ingewikkeld om te organiseren.
Als je een compleet voorbeeld met een gedetailleerd plot 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, raakt het werkblad ongeorganiseerd, vooral in vergelijking met de vorige tabel, die heel duidelijk is.
De optimale k kiezen: de elleboogmethode
Dus nu, misschien een poging wagen k = 2 En k = 3 in ons geval, en bereken de traagheid van elk. Dan vergelijken we gewoon de waarden.
We kunnen zelfs beginnen met k=1.
Voor elke waarde van k:
- we voeren k-Means uit tot convergentie,
- graaf luiheiddat is de som van de kwadraten van de afstanden tussen elk punt en het opgegeven massamiddelpunt.
In Excel:
- Neem voor elk punt de afstand tot het massamiddelpunt en kwadraat dit.
- Tel al deze kwadratische afstanden bij elkaar op.
- Dit zorgt voor traagheid voor deze k.
Bijvoorbeeld:
- voor k = 1 is het massamiddelpunt eenvoudigweg het algehele gemiddelde van x1 en x2,
- voor k = 2 en k = 3 nemen we het geconvergeerde zwaartepunt van het blad waarop u het algoritme uitvoert.
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 drastisch af,
- van 2 naar 3 is de stijging veel kleiner.
“Elleboog” is de waarde van k waarna de afname van de traagheid marginaal wordt. In dit voorbeeld is k = 2 voldoende.
Conclusie
K-means is een zeer intuïtief algoritme als je het stap voor stap in Excel ziet.
We beginnen met een eenvoudig zwaartepunt, berekenen de afstand, wijzen een punt toe, werken het zwaartepunt bij en herhalen. Nu kunnen we zien hoe “machine learning” werkt, toch?
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 Dichtstbijzijnde Centroid-classificator Het is waar k-betekent.
Dus, wat is de versie zonder toezicht LDA of QDA? Daar zullen we in het volgende artikel antwoord op geven.
