Inleiding: Decision Bomen and the Need for Purity

Beslissing bomen zijn een van de meest intuïtieve en veelgebruikte algoritmen onder toezicht leren in machine learning. Ze modelliseren beslissingen als een boom structuur, waar interne knooppunten testen op functies vertegenwoordigen, branches vertegenwoordigen resultaten van die tests, en bladknooppunten vertegenwoordigen definitieve voorspellingen. Of u nu classificeren of een e-mail is spam of het voorspellen van huizenprijzen, beslissing bomen bieden een transparante, menselijk leesbare aanpak.

De kern uitdaging bij het bouwen van een beslissingsboom is de beslissing waar de gegevens bij elke knoop te splitsen. Het algoritme moet de functie en de splitwaarde kiezen die de doelklassen het beste scheidt. Dit is waar entropie[] komt. Entropie, ontleend aan informatietheorie, levert een wiskundige maatstaf van onzekerheid of onzuiverheid in een dataset. Door entropie na elke splitsing te minimaliseren, creëren besluitbomen steeds homogenere subgroepen, wat leidt tot nauwkeurige en efficiënte modellen.

Wat is Entropie? Een maatregel van stoornis

In de dagelijkse taal verwijst entropie naar willekeurigheid of chaos. In de context van beslissingsbomen, kwantificeert entropie de hoeveelheid onvoorspelbaarheid in een dataset met betrekking tot de doelvariabele. Als alle voorbeelden in een knooppunt tot dezelfde klasse behoren, is het knooppunt pure en zijn entropie nul. Omgekeerd bereikt entropie, als de klassen gelijkmatig gemengd zijn, zijn maximum.

Voor een binair classificatieprobleem (bv. positief vs. negatief) wordt entropie gedefinieerd als:

Entropie =

waarbij p+ het aandeel positieve voorbeelden is en p− = 1

Entropie =

De resulterende waarde varieert van 0 (perfect zuiver) tot log2(k) voor k klassen (maximale onzuiverheid). Voor een binair geval is maximale entropie 1,0 wanneer p+ = p− = 0,5.

Een snel voorbeeld

Beschouw een verzameling van 10 monsters met 5 positieven en 5 negatieven. Entropie =

Waarom Basis 2?

De keuze van basis 2 is geworteld in de informatietheorie van Claude Shannon. Een beetje is de fundamentele eenheid van informatie, die een binaire keuze vertegenwoordigt. Met basis 2 betekent entropie geeft het gemiddelde aantal bits die nodig zijn om de klasse van een willekeurige steekproef te coderen. Als je de distributie al kent, betekent lagere entropie minder bits nodig om de uitkomst te communiceren.

Informatie Gain: Hoe Entropy Guides Splits

Het berekenen van entropie is niet genoeg; het doel is om het te verminderen na het splitsen. Informatiewinst (IG) meet de verwachte vermindering van entropie veroorzaakt door het partitioneren van de gegevens volgens een functie. De functie en split waarde die de hoogste informatiewinst oplevert worden gekozen voor het knooppunt.

De formule voor informatiewinst is:

Informatie Gain = Entropy(parent)

Waar S de ouderset is, zijn Si de kindset na de splitsing, en .. .. duidt op het aantal monsters. De som is een gewogen gemiddelde van de kinderen .

Voorbeeld

Stel je een ouderknooppunt voor met 30 monsters: 16 klasse A en 14 klasse B. Entropy(ouder) =

Denk nu aan een splitsing op Feature X die twee kinderen creëert: Child1 heeft 20 monsters (15 A, 5 B) → entropie =

Als een andere split hogere IG oplevert, dan wordt die split de voorkeur gegeven. Het algoritme evalueert alle functies en mogelijke splitdrempels om de beste te vinden.

Beperkingen van informatievergaring

Informatiewinst heeft de neiging om functies met vele verschillende waarden (bijvoorbeeld een unieke ID kolom) te bevorderen omdat het splitsen op een dergelijke functie veel pure kinderen creëert, waardoor hoge IG wordt verkregen. Dit kan leiden tot overpassen. Om dat tegen te gaan, varianten zoals Gain Ratio[ (gebruikt in C4.5) normaliseren IG door de intrinsieke informatie van de splitsing. Een andere benadering is het gebruik van de Gini onzuiverheid, die computerverdient goedkoper is en vaak vergelijkbare resultaten oplevert.

Vergelijken van Entropie met Gini Impurity

Gini onzuiverheid is een alternatief splijtcriterium dat wordt gebruikt in het CART-algoritme (Classification and Regression Trees). Het meet de kans op een verkeerde indeling van een willekeurig gekozen monster als het willekeurig werd geëtiketteerd volgens de klasseverdeling in het knooppunt. De formule:

Gini = 1

Voor een binair geval is Gini = 2p+(1

Zowel entropie als Gini onzuiverheid zijn convexe functies, wat betekent dat ze zich in de praktijk op dezelfde manier gedragen. De keuze tussen hen komt vaak neer op computationele efficiëntie: Gini heeft geen logaritmen nodig, dus het kan iets sneller zijn. Echter, entropie heeft een sterkere informatie-theoretische rechtvaardiging. Veel bibliotheken, waaronder scikit-learn, kunt u kiezen; empirisch, verschillen zijn klein.

Entropie in Regressie Bomen

Beslissingsbomen kunnen ook regressieproblemen oplossen (voorspelling van continue waarden). In regressie is entropie niet geschikt omdat het doel niet categorisch is. In plaats daarvan gebruikt het algoritme variatiereductie of gemiddelde kwadraatfout (MSE) als het splitsingscriterium. Het idee is analoog: bij elke knoop splitsen we om de gewogen som van verschillen van de kindknooppunten te minimaliseren. Dit maximaliseert de homogeniteit van de doelwaarden in elke regio.

Voor regressie wordt de hoeveelheid vaak gemiddelde kwadraatfoutreductie of totale variatiereductie genoemd. Het principe is precies hetzelfde als informatiewinst: meet de onzuiverheid (variatie) van de ouder, dan het gewogen gemiddelde van kinderen, en maximaliseert het verschil.

Bouwen van een complete beslissingsboom: van wortel tot blad

Nu we entropie en informatiewinst begrijpen, laten we doornemen hoe een typische beslissingsboom leeralgoritme (zoals ID3, C4.5, of CART) een boom bouwt:

  1. Begin met de volledige dataset op de root knooppunt.
  2. Bereken de onzuiverheid van de wortel met entropie (voor classificatie) of variantie (voor regressie).
  3. Voor elke functie, evalueer elk mogelijk splitpunt (voor numerieke kenmerken, sorteer waarden en bekijk tussen opeenvolgende afzonderlijke waarden; voor categorische kenmerken, overwegen deelgroepen of één-hot codering).
  4. Bereken informatiewinst (of winstverhouding, Gini-reductie, enz.) voor elke splitsing.
  5. Kies de split die de hoogste winst oplevert.
  6. Deel de gegevens en herhaal stap 2
  7. Stopcriteria voorkomen oneindige groei: maximale diepte, minimummonsters per blad, minimale onzuiverheidsafname, of wanneer alle monsters in een knoop tot één klasse behoren.
  8. Prune de boom (vooraflopend via hyperparameters of naafdrukken door af te snijden takken die niet verbeteren prestaties op een validatieset) om overpassen te bestrijden.

Behandeling van categorische en numerieke kenmerken

Entropie gebaseerde splitsing werkt voor beide soorten functies, maar de aanpak verschilt:

  • Numerieke kenmerken: Het algoritme sorteert de unieke waarden en test elke mogelijke drempel. Voor efficiëntie wordt vaak alleen rekening gehouden met drempels tussen opeenvolgende gesorteerde waarden waar het klasselabel verandert.
  • Categorische kenmerken: Voor binaire splitsingen kan het algoritme categorieën in twee deelgroepen groeperen. Voor multi-way splits (zoals in ID3) wordt elke categorie een tak. Echter, multi-way splitst gegevens snel en zijn gevoelig voor overfitting, dus de meeste moderne implementaties gebruiken binaire splits, zelfs voor categorische functies.

Afhandeling van ontbrekende waarden

De datasets in de echte wereld bevatten vaak ontbrekende waarden. Beslissingsbomen kunnen deze op verschillende manieren aanpakken:

  • Surrogaatsplits: Wanneer een functie wordt gesplitst, wordt een back-upfunctie gebruikt die de split het beste nabootst voor samples die de primaire functie missen.
  • Fractionele gevallen: Een monster toewijzen aan meerdere kinderen met gewichten die evenredig zijn aan de waarschijnlijkheid van elk kind op basis van niet-missende gegevens.
  • Eenvoudige toerekening: ontbrekende waarden vervangen door de modus of mediaan voordat de boom wordt gebouwd.

Veel bibliotheken, zoals scikit-leer, behandelen ontbrekende waarden intern niet en verwachten dat ze vooraf worden toegerekend. XGBoost en LightGBM leren echter de beste richting voor ontbrekende waarden tijdens de training.

Overpassen en snoeien

Een beslissing boom die tot maximale diepte zal perfect onthouden van de training gegevens, waaronder lawaai, leiden tot slechte generalisatie. Entropie reductie blijft totdat elk blad is zuiver, maar dit zelden voordelen test prestaties. Twee belangrijkste strategieën controleren overpassen:

Vooraf draaien (vroeg stoppen)

Stop de boomgroei voordat deze overfit is door beperkingen toe te passen: limiet de maximale diepte, vereist een minimum aantal monsters per blad, of vereist een minimale vermindering van onzuiverheid (bijvoorbeeld entropiedaling moet > 0,01 zijn). Deze hyperparameters worden afgestemd met behulp van kruisvalidatie.

Na het afdrukken (cost-complexiteit snoeien)

Groei de boom volledig, verwijder vervolgens takken die weinig waarde toevoegen. Het algoritme beschouwt een trade-off tussen boom complexiteit (aantal bladeren) en trainingsfout. Een complexiteitsparameter (alpha) bestraft extra bladeren. Scikit-learn

Beide snoeitechnieken zorgen ervoor dat entropie-gedreven splits niet te korrelig zijn en dat de boom interpreteerbaar blijft terwijl ze goed generaliseren.

Entropie in Ensemble Methoden

Hoewel één enkele beslissingsboom instabiel kan zijn (kleine veranderingen in gegevens kunnen leiden tot een heel andere boom), blijft entropie een fundamenteel concept in ensemble methoden:

  • Random Forests: Bouw veel bomen met behulp van bootstrap-monsters en random feature subsets. Elke boom gebruikt meestal entropie of Gini om te splitsen. De bosgemiddelden voorspellingen, waardoor de variatie.
  • Gradient Boosting: Bomen worden sequentiële gebouwd om fouten van vorige bomen te corrigeren. Entropie wordt gebruikt als doel (via kruis-entropie verlies) voor classificatie bossen in bibliotheken zoals XGBoost.

Het begrijpen van entropie helpt te interpreteren waarom een bepaalde split werd gekozen in elke individuele boom, die essentieel is voor model debugging en functie belangrijk analyse.

Praktische overwegingen bij het gebruik van Entropie

Ten eerste, reken entropie met behulp van logaritmen zorgvuldig . . Vermijd ongedefinieerd log(0) door 0 log2(0) te definiëren als 0. Ten tweede, wees je ervan bewust dat entropie berekeningen gevoelig zijn voor klassen onbalans; een knooppunt met 99% een klasse en 1% een andere heeft lage entropie maar kan niet aangeven een goede verdeling als de minderheid klasse is belangrijk. In dat geval, weging klassen of het gebruik van alternatieve metrics (bijv., F1) voor evaluatie is aan te raden.

Ook kunnen beslissingsbomen met entropie geheugen-intensief zijn voor grote datasets omdat ze alle functies en splitpunten evalueren. Bibliotheken gebruiken algoritmes als sort-and-scan om entropie te berekenen voor numerieke functies in O(n log n) tijd.

Externe referenties voor diepere lezing:

Voorbij classificatie: Entropie en informatie Gain in functieselectie

Entropie wordt niet alleen gebruikt binnen beslissing bomen . . het geeft ook functies selectie technieken. Wekelijkse informatie tussen functie en doel is direct gerelateerd aan informatie gain. U kunt kenmerken rangschikken door hun wederzijdse informatie om dimensionaliteit te verminderen voordat andere modellen worden getraind. Dit is een niet-lineair alternatief voor correlatie analyse.

Bijvoorbeeld, als functie X hoge wederzijdse informatie met doel Y heeft, vermindert X de onzekerheid over Y aanzienlijk. Dit is precies de vermindering in entropie die wordt bereikt door het splitsen op X. Bibliotheken zoals scikit-learn bieden en .

Beperkingen van de op de entropie gebaseerde besluitvormingsbomen

Ondanks hun macht hebben beslissingsbomen gebouwd met entropie een aantal nadelen:

  • Instabiliteit: Kleine gegevensverzamelingsvariaties kunnen de structuur van de boom drastisch veranderen. Ensembles verzachten dit.
  • Bezienswaardigheden naar functies met vele niveaus: Informatie gain is gunstig voor functies met hogecardinaliteit. Gain ratio of het gebruik van alleen binaire splits helpt.
  • Arme behandeling van additieve structuur: Bomen zijn stuksgewijze constante modellen, dus ze worstelen om lineaire relaties te leren.
  • Greedy nature: Het algoritme maakt lokaal optimale splitsingen, die mogelijk niet wereldwijd optimaal zijn.

In de praktijk levert het combineren van entropie-gebaseerde beslissingsbomen met de juiste hyperparameter tuning en ensemble methoden robuuste modellen op voor veel tabeldatasets.

Conclusie: Entropie als Stichting voor Inzichtelijke Splitsen

Entropie biedt een principiële, informatie-theoretische manier om de kwaliteit van een splitsing te evalueren bij het bouwen van een beslissingsboom. Door de aandoening in een dataset te meten en te streven naar het verminderen bij elke stap, kunnen we bomen bouwen die de functieruimte efficiënt en nauwkeurig verdelen. Of je nu een student leermachine leert of een beoefenaar die modellen inzet, begrip entropie verdiept je begrip van hoe beslissing bomen . . . .Het verbindt ook met bredere concepten zoals wederzijdse informatie, functie selectie, en zelfs data compressie.

Als u besluit bomen toepassen, onthoud dat entropie is een hulpmiddel . . Geen einde. Paar het met de juiste validatie, snoeien, en ensemble technieken om het volledige potentieel te ontgrendelen. En als u het beheren van data pijpleidingen voor machine learning, tools zoals Directus kan u helpen verzamelen, organiseren en dienen van de hoge kwaliteit datasets die beslissing bomen afhankelijk van.