Beslissingsboomregressie vanaf nul: theorie en praktijk

Home » Python » Beslissingsboomregressie vanaf nul: theorie en praktijk

Het helemaal zelf ontwikkelen van een beslissingsboomregressie is een van de meest verhelderende oefeningen die je kunt doen als je echt wilt begrijpen hoe op bomen gebaseerde modellen denken en waarom ze zo populair zijn in machine learning. In plaats van de boom als een mysterieuze zwarte doos te beschouwen, zie je hoe elke splitsing wordt gekozen, hoe onzuiverheid wordt gemeten en hoe numerieke voorspellingen worden gegenereerd bij de bladeren, zowel voor regressie- als classificatieproblemen.

In deze handleiding bespreken we de kernideeën achter beslissingsbomen, de kostenfuncties die ze gebruiken, hoe ze zoeken naar de beste splitsingen en hoe je een eenvoudige boom kunt coderen die zowel regressie als classificatie ondersteunt, met behulp van alleen fundamentele concepten zoals lussen, voorwaarden en eenvoudige statistieken. Gaandeweg vergelijken we regressie- en classificatiebomen, verbinden we de theorie met praktische implementaties in tools zoals Python en R (bijvoorbeeld met rpart en tree), en plaatsen we beslissingsbomen kort binnen grotere ensembles zoals random forests.

Wat is een beslissingsboom en waarom is deze zo intuïtief?

Een beslissingsboom is in wezen een reeks ja/nee-vragen (of eenvoudige regels) die je van een basisbeslissing naar een uiteindelijke voorspelling in een bladknooppunt leidt. In een typische setting voor supervised learning is het doel om een ​​doelvariabele te voorspellen. Y Door gebruik te maken van meerdere voorspellers (kenmerken, covariaten), leert de beslissingsboom een ​​reeks vragen zoals "is het gewicht ≤ 103?" of "ligt het land in {VS, VK, CA}?" die de gegevens geleidelijk in meer homogene groepen verdelen.

Om een ​​beter beeld te krijgen, stel je voor dat je wilt voorspellen of iemand zwaarlijvig is, alleen op basis van lengte en gewicht, en je hebt een gelabelde dataset die aangeeft wie zwaarlijvig is en wie niet. Een beslissingsboom kan een regel ontdekken zoals "als het gewicht > 100 kg is, voorspel dan obesitas", maar die regel zal niet perfect zijn: sommige mensen boven de 100 kg zullen geen obesitas hebben, en sommige mensen onder die drempel wel. De boom blijft vervolgens meer vragen (sub-splits) toevoegen, bijvoorbeeld over lengte of een verfijndere gewichtsdrempel, om die eerste ruwe voorspellingen te "verfijnen".

Elk intern knooppunt in de boom komt overeen met een beslissingsregel, elke tak komt overeen met een uitkomst van die regel, en elk bladknooppunt komt overeen met een gebied in de kenmerkenruimte waar de voorspellingen constant zijn. Bij classificatie geeft een blad een klasselabel terug (of een waarschijnlijkheidsverdeling over labels); bij regressie geeft een blad doorgaans het gemiddelde terug van de doelwaarden die binnen dat gebied vallen.

Een van de belangrijkste sterke punten van beslissingsbomen is dat ze zowel regressie als classificatie op een natuurlijke manier afhandelen, gemakkelijk te interpreteren zijn en werken met zowel kwantitatieve als kwalitatieve (categorische) voorspellers zonder dat er veel voorbewerking nodig is. Je hoeft geen specifieke verdeling aan te nemen voor je kenmerken of je doelvariabele, wat beslissingsbomen erg aantrekkelijk maakt in praktijksituaties waar klassieke lineaire aannames vaak niet opgaan.

Classificatiebomen versus regressiebomen

Hoewel de structuur van classificatie- en regressiebomen hetzelfde is, verschillen de aard van de responsvariabele Y en de kostenfunctie die voor de splitsing wordt gebruikt tussen deze twee typen. Wanneer Y kwantitatief is (bijvoorbeeld omzet, levensverwachting, brandstofverbruik), spreken we van een regressieboom; wanneer Y kwalitatief of categorisch is (bijvoorbeeld overleefd versus niet overleefd, zwaarlijvig versus niet zwaarlijvig), spreken we van een classificatieboom.

Bij een regressieboom is het gebruikelijke doel om de kenmerkenruimte op te delen in gebieden waar de respons kan worden benaderd door een constante, vaak het gemiddelde van de waarnemingen in dat gebied. Typische beslissingsregels hebben de vorm "is x_k ≤ c?”, waarbij x_k is een van de covariaten en c is een drempelwaarde; deze regels verdelen de ruimte herhaaldelijk in hyperrechthoeken, en alle punten in dezelfde hyperrechthoek delen dezelfde voorspelde waarde ŷ.

In een classificatieboom zijn de splitsingen nog steeds "kenmerk ≤ drempelwaarde?" of "categorie in verzameling S?", maar de kwaliteit van een splitsing wordt gemeten aan de hand van hoe zuiver de resulterende kindknoppen zijn wat betreft klasselabels. De bladvoorspelling is meestal de meest voorkomende klasse binnen dat knooppunt, en het model probeert bladeren te creëren die zo dicht mogelijk bij een knooppunt met slechts één klasse liggen.

Ondanks deze verschillen in het doeltype, kun je vanuit programmeerperspectief een enkele generieke boomstructuur implementeren en eenvoudigweg verschillende onzuiverheids- of verliesmaatregelen toevoegen, afhankelijk van of je regressie of classificatie uitvoert. Later, wanneer we de informatiewinst berekenen, zult u zien dat de formules voor classificatie (gebaseerd op entropie) en regressie (gebaseerd op variantie) in principe parallel lopen.

Onzuiverheids- en kostenfuncties in beslissingsbomen

De kern van elk beslissingsboomalgoritme wordt gevormd door een kostenfunctie die evalueert hoe goed een bepaalde splitsing de gegevens in zinvolle groepen verdeelt. Deze kostenfunctie wordt uitgedrukt in termen van onzuiverheid: een knooppunt wordt als zuiver beschouwd als al zijn monsters tot dezelfde klasse behoren (voor classificatie) of vrijwel dezelfde numerieke waarde hebben (voor regressie).

Wanneer je een kandidaat-splitsing selecteert op basis van een kenmerk, bekijkt het algoritme de kindknooppunten die het produceert en vraagt ​​zich af: "Hoe gemengd zijn de labels (of waarden) in elk kindknooppunt?" Een goede splitsing produceert kindknooppunten die veel minder onzuiver zijn dan het ouderknooppunt, wat betekent dat de gegevens binnen elk kindknooppunt homogener zijn ten opzichte van het doel.

In classificatiebomen wordt onzuiverheid meestal gemeten aan de hand van criteria zoals de Gini-index of entropie. Beide geven aan hoe waarschijnlijk het is dat een willekeurig gekozen waarneming in dat knooppunt verkeerd geclassificeerd zou worden als we simpelweg de meerderheidsklasse zouden voorspellen. In regressiebomen wordt onzuiverheid doorgaans gemeten met de kwadratische fout of variantie, wat aangeeft hoe verspreid de doelwaarden binnen het knooppunt zijn.

Gini-index: het meten van onzuiverheden in classificatiebomen

De Gini-index is een van de meest gebruikte onzuiverheidsmaten voor classificatiebomen, omdat deze eenvoudig te berekenen is en in de praktijk goed werkt. Conceptueel meet het de waarschijnlijkheid dat een willekeurig geselecteerde waarneming uit het knooppunt onjuist geclassificeerd zou worden als het label ervan voorspeld zou worden op basis van de labelverdeling in dat knooppunt.

Als een knooppunt klassen bevat met waarschijnlijkheden P₁, P₂, … , P_nDe Gini-index wordt berekend als Gini = 1 − Σ (P_i)². Wanneer een knooppunt volkomen zuiver is (alle waarnemingen behoren tot dezelfde klasse), is één van de waarschijnlijkheden 1 en de rest 0, waardoor de som van de kwadraten 1 is en de Gini-coëfficiënt 0, wat duidt op volledige zuiverheid.

Aan de andere kant bereikt de Gini-index zijn maximum wanneer de klassen gelijkmatig verdeeld zijn binnen het knooppunt, bijvoorbeeld in een binair probleem met P.₁ = P₂ = 0.5, wat Gini oplevert = 1 − (0.5² + 0.5²) = 0.5. In die situatie is het voorspellen van de meerderheidsklasse zo slecht mogelijk voor die verdeling, omdat het knooppunt de helft van elke klasse bevat.

Wanneer je Gini in code implementeert, neem je doorgaans de labelvector voor het knooppunt, bereken je de frequentie van elke klasse, zet je de frequenties om in waarschijnlijkheden en pas je vervolgens de formule 1 − Σ p² toe. Als je dit voor meerdere mogelijke splitsingen doet, kun je vergelijken welke splitsing kinderen oplevert met een lagere gewogen gemiddelde Gini-onzuiverheid. Dat is precies wat de boom nodig heeft om de beste splitsing te bepalen.

Entropie: een andere kijk op classificatieonzuiverheid

Entropie is een alternatieve maat voor onzuiverheid die veel gebruikt wordt in de informatietheorie en in vroege boomalgoritmen zoals ID3 en C4.5. Het geeft de mate van willekeurigheid of onzekerheid weer in de klassenverdeling van de knooppunten. Terwijl Gini zich richt op de kans op verkeerde classificatie, kwantificeert entropie de "verrassing" die gepaard gaat met het waarnemen van een bepaalde klasse wanneer de verdeling gemengd is.

Gegeven klassewaarschijnlijkheden p₁, … , P_c Voor een knooppunt S wordt de entropie gedefinieerd als E(S) = − Σ p_i log₂(p_i). Als het knooppunt zuiver is, is één van de waarschijnlijkheden 1 en alle andere 0, waardoor de som nul is (omdat log₂(1) = 0), dus de entropie is 0, wat aangeeft dat er geen onzekerheid is.

Wanneer het knooppunt een uniforme verdeling van klassen bevat, wordt de entropie gemaximaliseerd; voor een binair probleem met p₁ =p₂ = 0.5, de entropie is 1 bit, wat de hoogst mogelijke waarde is voor twee klassen. Deze waarde komt overeen met maximale onzekerheid, wat betekent dat het knooppunt zo onzuiver mogelijk is onder die verdeling.

Hoewel Gini en entropie verschillende formules gebruiken en verschillende numerieke bereiken hebben (Gini tussen 0 en 0.5 voor twee klassen, entropie tussen 0 en 1), meten ze in wezen hetzelfde concept, waardoor ze in de praktijk meestal tot zeer vergelijkbare beslissingsbomen leiden. Als je beide op dezelfde node berekent, zul je merken dat een hoge Gini-coëfficiënt overeenkomt met een hoge entropie en omgekeerd. Daarom laten veel bibliotheken je kiezen tussen beide zonder dat de prestaties drastisch veranderen.

Informatievergaring en het kiezen van de beste splitsingen

Om de beste splitsing uit vele kandidaten te kiezen, gebruikt het boomalgoritme een metriek genaamd informatiewinst, die meet hoeveel de onzuiverheid afneemt wanneer we een knooppunt opsplitsen in zijn kinderen. Intuïtief gezien heeft een splitsing een hoge informatiewinst als de kinderen veel zuiverder zijn dan de ouder, wat betekent dat de regel de gegevens met succes in meer betekenisvolle groepen heeft gescheiden.

Voor classificatiebomen die gebruikmaken van entropie, wordt de informatiewinst van een splitsing gedefinieerd als IG._{classificatie} = E(ouder) − Σ (|S_kind| / |S_ouder|) · E(S_kind). Je berekent eerst de entropie van het bovenliggende knooppunt en trekt daar vervolgens de gewogen gemiddelde entropie van de onderliggende knooppunten vanaf, waarbij de gewichten hun relatieve groottes zijn.

Voor regressiebomen wordt een analoog concept gebruikt waarbij de variantie of de gemiddelde kwadratische fout als maatstaf voor onzuiverheid wordt gebruikt, wat resulteert in IG._regressie = Var(ouder) − Σ (|S_kind| / |S_ouder|) · Var(S_kind). In deze context is een goede splitsing er een die de variabiliteit van de doelwaarden binnen elk kind aanzienlijk vermindert.

Het algoritme voor het trainen van de beslissingsboom evalueert deze informatiewinst voor elke mogelijke kandidaat-splitsing op elk kenmerk en kiest vervolgens de splitsing met de hoogste winst, mits deze een bepaalde minimumdrempel overschrijdt om te voorkomen dat er nutteloze, kleine verbeteringen worden gecreëerd. Dit proces wordt vervolgens recursief herhaald op elk kindknooppunt totdat aan bepaalde stopcriteria is voldaan.

Hoe vind je de beste verdeling voor elk onderdeel?

Het vinden van de beste splitsing op basis van een enkel kenmerk hangt af van of het kenmerk numeriek of categorisch is, maar het onderliggende idee is altijd hetzelfde: inventariseer mogelijke partities en bereken hun informatiewinst. Voor numerieke kenmerken wordt een indeling gedefinieerd door een drempelwaarde; voor categorische kenmerken wordt deze gedefinieerd door niveaus in subsets te groeperen.

Bij een numerieke voorspeller is de gebruikelijke strategie om alle unieke waarden die de betreffende eigenschap in het huidige knooppunt aanneemt te bekijken, deze te sorteren en vervolgens mogelijke drempelwaarden tussen opeenvolgende waarden te overwegen. Voor elke kandidaatdrempelwaarde c maak je twee groepen (x ≤ c en x > c), bereken je de onzuiverheid van elke groep en vervolgens de informatiewinst; de drempelwaarde die de hoogste winst oplevert, is de beste numerieke splitsing voor dat kenmerk.

Bij het werken met categorische voorspellers is de zoekruimte complexer, omdat in principe elke subset van categorieën de ene kant van de splitsing kan vormen, met het complement aan de andere kant. In een kenmerk met K categorieën zijn er veel mogelijke subsets (2^K−1 − 1 niet-triviale partities), dus in de praktijk beperken implementaties deze zoektocht vaak of maken ze gebruik van heuristieken, vooral wanneer K groot is.

Nadat je de beste splitsing voor elk kenmerk hebt berekend, vergelijk je hun informatiewinst en selecteer je het kenmerk en de drempelwaarde (of subset van categorieën) die overeenkomen met de maximale winst. Deze gekozen splitsing wordt de beslissing bij het huidige knooppunt, waarna het trainingsproces recursief wordt herhaald voor elk kindknooppunt met de bijbehorende subset van waarnemingen.

Boomgroei beheersen met hyperparameters

Als je een beslissingsboom zonder enige beperking laat groeien, zal deze zich blijven vertakken totdat elk blad ofwel volkomen zuiver is ofwel zeer weinig waarnemingen bevat, wat bijna altijd leidt tot ernstige overfitting.overfitting versus underfitting). Om dit te voorkomen, stelt u een reeks hyperparameters in die de diepte en complexiteit van de boom bepalen.

Een veelgebruikte hyperparameter is max_depth, die het maximale aantal niveaus begrenst dat de boom kan bereiken vanaf de wortel tot een willekeurig blad. Als max_depth is ingesteld op None (of een zeer groot getal), kan de boom blijven groeien zolang aan andere beperkingen wordt voldaan; als het klein is, blijft de boom ondiep en beter interpreteerbaar, maar kan deze onderfitten.

Een andere belangrijke hyperparameter is min_samples_split, die het minimale aantal waarnemingen aangeeft dat een knooppunt moet bevatten voordat het mag worden gesplitst. Als een knooppunt minder gegevenspunten heeft dan deze drempelwaarde, wordt het een bladknooppunt. Dit voorkomt dat het model ruis in zeer kleine deelverzamelingen van gegevens probeert te detecteren.

Je kunt ook een minimale informatiewinst (min_information_gain) afdwingen, zodat het algoritme alleen een splitsing uitvoert als dit een significante verbetering in de vermindering van onzuiverheden oplevert. Dit voorkomt het creëren van onnodige vertakkingen die de voorspellingen nauwelijks veranderen en de boomstructuur alleen maar ingewikkelder maken.

Een beslissingsboom helemaal zelf bouwen in code.

Het implementeren van een beslissingsboom vanaf nul draait meestal om een ​​kleine set kernfuncties die recursief worden aangeroepen. Hoewel bibliotheken zoals scikit-learn of rpart dit allemaal automatisch afhandelen, maakt het zelf coderen van deze stappen de logica veel duidelijker.programmeerlogica) en geeft je volledige controle over het gedrag.

Allereerst heb je een routine nodig die, gegeven de huidige gegevens op een knooppunt, elke feature en elke kandidaat-split evalueert om de split met de hoogste informatiewinst te vinden. Deze functie retourneert het gekozen kenmerk, de splitsingsregel (drempelwaarde of subset van categorieën), de versterkingswaarde en de booleaanse maskering of indexsets die aangeven welke samples naar links en welke naar rechts gaan.

Ten tweede heb je een voorspellingsfunctie nodig voor de bladknooppunten, die de set doelwaarden in dat knooppunt omzet in één enkele voorspelling. Bij regressie is dit doorgaans het gemiddelde van y in dat knooppunt; bij classificatie neem je meestal de modus (de meest voorkomende klasse), waarbij je eventueel ook de klassewaarschijnlijkheden opslaat als je probabilistische resultaten wilt.

Ten derde creëer je een recursieve trainingsfunctie die de stopcriteria controleert, de beste splitsing zoekt indien toegestaan, en vervolgens kindknooppunten bouwt door zichzelf aan te roepen op de linker- en rechterdeelverzamelingen. Als niet aan de voorwaarden voor minimale steekproefomvang, maximale diepte of minimale versterking wordt voldaan, stopt de functie met splitsen en slaat in plaats van verdere vertakkingen een bladvoorspelling op.

Hoe voorspellingen werken in een getrainde beslissingsboom.

Zodra uw boom is getraind en u alle splitsingsregels en bladvoorspellingen hebt opgeslagen, is het maken van een voorspelling voor een nieuwe observatie een kwestie van de boom af te lopen van de wortel naar een blad. Bij elk intern knooppunt inspecteer je de vereiste eigenschap en test je of de waarneming voldoet aan de voorwaarde van het knooppunt.

Als de splitsingsregel numeriek is, controleer je of de kenmerkwaarde kleiner dan of gelijk aan de drempelwaarde is; als de splitsingsregel categorisch is, controleer je of de categorie zich in een bepaalde subset bevindt. Afhankelijk van de uitkomst volg je de juiste tak (bijvoorbeeld "ja" naar links, "nee" naar rechts) en herhaal je dit proces bij het volgende knooppunt.

Je blijft de boom afdalen tot je een knooppunt zonder kinderen bereikt, een bladknooppunt dat een constante uitvoerwaarde of een klasselabel opslaat. Bij een regressieboom is de voorspelling een getal, zoals een geschatte levensverwachting of brandstofefficiëntie; bij een classificatieboom is de uitvoer een voorspelde categorie, zoals 'overleefd' of 'niet overleefd'.

Als je deze aanpak test op dezelfde data die je voor de training hebt gebruikt, zul je vaak een vrij hoge nauwkeurigheid zien bij de classificatie (bijvoorbeeld rond de 85% in sommige eenvoudige voorbeelden zoals obesitas of de Titanic-ramp), maar die prestatie kan dalen op onbekende data als je beslissingsboom te diep is. Dit is precies de reden waarom het beheersen van de diepte en grootte van bomen zo belangrijk is, en waarom ensemblemodellen zoals random forests zijn ontwikkeld om boomvoorspellingen te stabiliseren.

Praktische toepassing van regressiebomen

Regressiebomen zijn met name handig wanneer de relatie tussen voorspellende variabelen en de respons sterk niet-lineair is en interacties omvat die moeilijk te modelleren zijn met klassieke lineaire regressie. In plaats van te proberen één enkele globale vergelijking toe te passen, verdeelt de boom de kenmerkenruimte in regio's en past binnen elke regio een eenvoudig constant model toe.

In R maken populaire pakketten zoals rpart en tree het eenvoudig om regressiebomen te bouwen met één enkele functieaanroep, door een formule op te geven zoals y ~ x1 + x2 + … + x11. Deze pakketten zijn beïnvloed door de oorspronkelijke CART-methodologie die door Breiman en collega's is beschreven, en ze implementeren veel van de ideeën voor het splitsen en snoeien die standaard zijn in moderne boomgebaseerde modellering.

Je kunt bijvoorbeeld het rpart-pakket gebruiken om een ​​respons y te modelleren op basis van elf covariaten x1 tot en met x11, de gegevens opschonen van ontbrekende waarden en vervolgens de resulterende boom visualiseren met behulp van hulpfuncties zoals prp uit het rpart.plot-pakket. De eindpunten tonen de voorspelde y-waarde voor elke regio, die je direct kunt gebruiken voor nieuwe waarnemingen.

Gegeven een getrainde regressieboom, kunt u nieuwe covariabele waarden zoals x9 = 70, x2 = 100 of x9 = 60, x2 = 150 invoeren in de predict-functie om geschatte waarden ŷ te verkrijgen (bijvoorbeeld rond de 20 of 28 in een voorbeeld met brandstofverbruik). Door deze voorspellingen te vergelijken met waargenomen waarden, bijvoorbeeld via de correlatie tussen y en ŷ, krijg je snel een idee van hoe goed de beslissingsboom het onderliggende patroon vastlegt, zelfs als de dataset relatief klein is.

Van individuele bomen tot willekeurige bossen

Een enkele beslissingsboom is krachtig, maar staat er ook om bekend dat hij zeer gevoelig is voor de bijzonderheden van de trainingsgegevens, wat kan leiden tot een hoge variantie (vooringenomenheid en variantie) en overfitting. Om dit te verhelpen, bouwen random forests veel bomen op basis van gebootstrapte steekproeven van de gegevens en aggregeren ze hun voorspellingen, wat resulteert in een stabieler en meestal nauwkeuriger model.

In een random forest wordt elke boom getraind op een bootstrap-steekproef, wat betekent dat een nieuwe dataset van dezelfde grootte met terugplaatsing wordt getrokken uit de oorspronkelijke trainingsset. Door dit steekproefproces ziet elke boom een ​​iets andere dataset, waardoor hun fouten minder gecorreleerd zijn en elkaar kunnen opheffen wanneer ze worden samengevoegd.

Bovendien introduceren random forests willekeurigheid in het selectieproces van kenmerken door bij elke splitsing slechts een willekeurige subset van voorspellers te overwegen in plaats van alle voorspellers. Dit vermindert de correlatie tussen bomen verder, vergroot de diversiteit in het bos en vermindert de variantie zonder de vertekening te veel te vergroten.

De combinatie van bootstrapping en het samenvoegen van voorspellingen staat bekend als bagging. Bij random forests krijg je bovendien een interne schatting van de modelfout door elke boom te evalueren op de datapunten die niet in de bootstrap-steekproef waren opgenomen (de zogenaamde out-of-bag-waarnemingen). Deze fout bij de eerste meting biedt een handige manier om de prestaties te beoordelen zonder dat een aparte validatieset nodig is.

Hoewel dit artikel zich richt op het helemaal vanaf nul opbouwen van een enkele boom, maakt het begrijpen van de werking van dit basiselement het veel gemakkelijker om te begrijpen hoe ensembles zoals random forests, gradient boosting en andere op bomen gebaseerde methoden voortbouwen op dezelfde principes om state-of-the-art resultaten te behalen in veel toegepaste problemen.

Alles bij elkaar genomen, laat beslissingsboomregressie vanaf nul zien hoe een eenvoudige set regels, kostenfuncties en recursieve splitsingen complexe relaties kunnen modelleren, of je nu een binaire uitkomst voorspelt zoals overleving, een categorisch label zoals obesitasstatus, of een numerieke waarde zoals levensverwachting of brandstofverbruik. Dit diepgaande begrip vormt een solide basis voor het gebruik van meer geavanceerde boomgebaseerde technieken in de praktijk.

Gerelateerd artikel:

Overfitting versus onderfitting: het wordt compleet met señales, oorzaken en oplossingen