Voorbeelden van beslissingsboomalgoritmen in datamining

decision tree algorithm examples data mining

Deze diepgaande zelfstudie legt alles uit over beslissingsboom-algoritme in datamining. U leert over voorbeelden van beslissingsstructuren, algoritmen en classificatie:

We hebben er een paar bekeken Voorbeelden van datamining in onze vorige tutorial in Gratis datamining-trainingsserie ​

Decision Tree Mining is een soort dataminingtechniek die wordt gebruikt om classificatiemodellen te bouwen. Het bouwt classificatiemodellen in de vorm van een boomachtige structuur, net als de naam. Dit type mijnbouw behoort tot leren onder toezicht in de klas.

Bij begeleid leren is het beoogde resultaat al bekend. Beslissingsbomen kunnen worden gebruikt voor zowel categorische als numerieke gegevens. De categorische gegevens vertegenwoordigen geslacht, burgerlijke staat, enz., Terwijl de numerieke gegevens leeftijd, temperatuur, enz. Vertegenwoordigen.

beste gratis optimizer voor Windows 7

Een voorbeeld van een beslissingsboom met de dataset wordt hieronder getoond.

(beeld bron ​

Wat je leert:

• Wat is het nut van een beslissingsboom?
• Classificatieanalyse
• Regressie analyse
• Hoe werkt een beslissingsboom?
• Inductie-algoritme voor beslissingsboom
• Inductie van beslissingsboom
• WINKELWAGEN
• Inductie van beslissingsboom voor machine learning: ID3
• Wat is hebzuchtige recursieve binaire splitsing?
• Hoe kenmerken te selecteren om een ​​boom te maken?
  • # 1) Informatiewinst
  • # 2) Winstverhouding
  • # 3) Gini-index
• Overfitting in beslissingsbomen
• Wat is het snoeien van bomen?
• Wat is voorspellende modellen?
• Voordelen van beslissingsboomclassificatie
• Nadelen van de classificatie van beslissingsbomen
• Gevolgtrekking
• Aanbevolen literatuur

Wat is het nut van een beslissingsboom?

Decision Tree wordt gebruikt om classificatie- en regressiemodellen te bouwen. Het wordt gebruikt om datamodellen te maken die klassenlabels of waarden voor het besluitvormingsproces voorspellen. De modellen worden gebouwd op basis van de trainingsdataset die aan het systeem wordt toegevoerd (supervised learning).

Met behulp van een beslissingsboom kunnen we de beslissingen visualiseren die het gemakkelijk te begrijpen maken en daarom is het een populaire dataminingtechniek.

Classificatieanalyse

Dataclassificatie is een vorm van analyse waarmee een model wordt gebouwd dat belangrijke klassevariabelen beschrijft.Bijvoorbeeld, een model dat is ontwikkeld om aanvragen voor bankleningen als veilig of riskant te classificeren. Classificatiemethoden worden gebruikt bij machine learning en patroonherkenning.

Toepassing van classificatie omvat fraudedetectie, medische diagnose, doelmarketing, enz. De output van het classificatieprobleem wordt beschouwd als 'Modus' van alle waargenomen waarden van het eindknooppunt.

Er wordt een proces in twee stappen gevolgd om een ​​classificatiemodel te bouwen.

1. In de eerste stap, d.w.z. leren: een classificatiemodel op basis van trainingsgegevens wordt gebouwd.
2. In de tweede stap, namelijk classificatie, wordt de nauwkeurigheid van het model gecontroleerd en vervolgens wordt het model gebruikt om nieuwe gegevens te classificeren. De klassenlabels die hier worden gepresenteerd, hebben de vorm van discrete waarden zoals 'ja' of 'nee', 'veilig' of 'riskant'.

De algemene benadering voor classificatiemodellen voor gebouwen wordt hieronder gegeven:

(beeld bron ​

Regressie analyse

Regressieanalyse wordt gebruikt voor het voorspellen van numerieke attributen.

Numerieke attributen worden ook wel continue waarden genoemd. Een model dat is gebouwd om de continue waarden te voorspellen in plaats van klasselabels, wordt het regressiemodel genoemd. De output van regressieanalyse is het 'gemiddelde' van alle waargenomen waarden van het knooppunt.

Hoe werkt een beslissingsboom?

Een beslissingsboom is een leeralgoritme onder supervisie dat werkt voor zowel discrete als continue variabelen. Het splitst de dataset op in subsets op basis van het meest significante attribuut in de dataset. Hoe de beslissingsboom dit attribuut identificeert en hoe deze splitsing wordt gedaan, wordt bepaald door de algoritmen.

De meest significante voorspeller wordt aangeduid als het hoofdknooppunt, splitsen wordt gedaan om subknooppunten te vormen die beslissingsknooppunten worden genoemd, en de knooppunten die niet verder worden gesplitst, zijn terminal- of bladknooppunten.

In de beslissingsboom is de dataset verdeeld in homogene en niet-overlappende regio's. Het volgt een top-down benadering, aangezien het bovenste gebied alle waarnemingen op een enkele plaats presenteert die zich splitst in twee of meer takken die verder opsplitsen. Deze benadering wordt ook wel een hebzuchtige benadering omdat het alleen rekening houdt met het huidige knooppunt tussen de bewerkte knooppunten zonder zich te concentreren op de toekomstige knooppunten.

De beslissingsboomalgoritmen zullen blijven draaien totdat een stopcriterium zoals het minimum aantal waarnemingen etc. is bereikt.

Als een beslissingsboom eenmaal is gebouwd, kunnen veel knooppunten uitschieters of ruisende gegevens vertegenwoordigen. De boomsnoeimethode wordt toegepast om ongewenste gegevens te verwijderen. Dit verbetert op zijn beurt de nauwkeurigheid van het classificatiemodel.

Om de nauwkeurigheid van het model te bepalen, wordt een testset gebruikt die bestaat uit testtupels en klasselabels. De percentages van de testset-tupels worden correct geclassificeerd door het model om de nauwkeurigheid van het model te identificeren. Als het model nauwkeurig blijkt te zijn, wordt het gebruikt om de datatupels te classificeren waarvan de klassenlabels niet bekend zijn.

Enkele van de beslissingsboomalgoritmen zijn onder meer Hunt's Algorithm, ID3, CD4.5 en CART.

Voorbeeld van het maken van een beslissingsboom

(Voorbeeld is afkomstig uit Data Mining Concepts: Han en Kimber)

# 1) Leerstap: De trainingsgegevens worden in het systeem ingevoerd om te worden geanalyseerd door een classificatie-algoritme. In dit voorbeeld is het klassenlabel het attribuut, d.w.z. 'leningsbesluit'. Het model dat uit deze trainingsgegevens is opgebouwd, wordt weergegeven in de vorm van beslissingsregels.

# 2) Classificatie: De testdataset wordt naar het model gestuurd om de nauwkeurigheid van de classificatieregel te controleren. Als het model acceptabele resultaten geeft, wordt het toegepast op een nieuwe dataset met onbekende klassevariabelen.

Inductie-algoritme voor beslissingsboom

Inductie van beslissingsboom

Inductie van beslissingsbomen is de methode om de beslissingsbomen uit de trainingsset te leren. De trainingsset bestaat uit attributen en klasse-labels. Toepassingen van inductie van beslissingsbomen zijn onder meer astronomie, financiële analyse, medische diagnose, fabricage en productie.

Een beslissingsboom is een boomstructuur in de vorm van een stroomschema die is gemaakt van tupels van trainingssets. De dataset is onderverdeeld in kleinere subsets en is aanwezig in de vorm van knooppunten van een boom. De boomstructuur heeft een hoofdknooppunt, interne knooppunten of beslissingsknooppunten, bladknooppunt en vertakkingen.

Het hoofdknooppunt is het bovenste knooppunt. Het vertegenwoordigt het beste kenmerk dat is geselecteerd voor classificatie. Interne knooppunten van de beslissingsknooppunten vertegenwoordigen een test van een attribuut van het datasetbladknooppunt of eindknooppunt dat het classificatie- of beslissingslabel vertegenwoordigt. De takken tonen de uitkomst van de uitgevoerde test.

Sommige beslissingsbomen hebben alleen binaire knooppunten , dat betekent precies twee takken van een knooppunt, terwijl sommige beslissingsbomen niet-binair zijn.

De onderstaande afbeelding toont de beslissingsboom voor de Titanic-dataset om te voorspellen of de passagier het zal overleven of niet.

(beeld bron ​

WINKELWAGEN

CART-model, d.w.z. classificatie- en regressiemodellen, is een beslissingsboomalgoritme voor het bouwen van modellen. Decision Tree-model waarbij de streefwaarden een discreet karakter hebben, worden classificatiemodellen genoemd.

Een discrete waarde is een eindige of aftelbaar oneindige reeks waarden, Bijvoorbeeld, leeftijd, grootte, enz. De modellen waarbij de doelwaarden worden weergegeven door continue waarden zijn meestal getallen die regressiemodellen worden genoemd. Continue variabelen zijn variabelen met een drijvende komma. Deze twee modellen worden samen CART genoemd.

CART gebruikt Gini Index als classificatiematrix.

Inductie van beslissingsboom voor machine learning: ID3

Eind jaren zeventig en begin jaren tachtig was J.Ross Quinlan een onderzoeker die een beslissingsboom-algoritme voor machine learning ontwikkelde. Dit algoritme staat bekend als ID3, iteratieve dichotomiser ​Dit algoritme was een uitbreiding van de conceptleersystemen beschreven door E.B Hunt, J en Marin.

ID3 werd later bekend als C4.5. ID3 en C4.5 volgen een hebzuchtige top-down benadering voor het construeren van beslissingsbomen. Het algoritme begint met een trainingsdataset met klassenlabels die worden opgedeeld in kleinere subsets terwijl de boom wordt geconstrueerd.

# 1) Aanvankelijk zijn er drie parameters, d.w.z. attributenlijst, attribuutselectiemethode en gegevenspartitie ​De attributenlijst beschrijft de attributen van de tupels van de trainingsset.

#twee) De attribuutselectiemethode beschrijft de methode voor het selecteren van het beste attribuut voor onderscheid tussen tupels. De methoden die worden gebruikt voor attribuutselectie kunnen Information Gain of Gini Index zijn.

# 3) De structuur van de boom (binair of niet-binair) wordt bepaald door de attribuutselectiemethode.

# 4) Bij het construeren van een beslissingsboom begint deze als een enkel knooppunt dat de tupels vertegenwoordigt.

# 5) Als de tupels van het rootknooppunt verschillende klassenlabels vertegenwoordigen, roept het een attribuutselectiemethode aan om de tupels te splitsen of te partitioneren. De stap zal leiden tot de vorming van takken en beslissingsknooppunten.

# 6) De splitsingsmethode zal bepalen welk attribuut moet worden geselecteerd om de datatupels te partitioneren. Het bepaalt ook de takken die vanaf het knooppunt moeten worden gekweekt op basis van het testresultaat. Het belangrijkste motief van de splitsingscriteria is dat de partitie op elke tak van de beslissingsboom hetzelfde klasselabel moet vertegenwoordigen.

Een voorbeeld van het splitsen van een attribuut wordt hieronder getoond:

een. Bovenstaande portionering is discreet gewaardeerd.

b. De bovenstaande portionering is voor continu gewaardeerd.

# 7) De bovenstaande partitioneringsstappen worden recursief gevolgd om een ​​beslissingsboom te vormen voor de tupels van de trainingsdataset.

# 8) Het portioneren stopt alleen als alle partities zijn gemaakt of als de resterende tuples niet verder kunnen worden gepartitioneerd.

voorbeeldtestplan voor het testen van software

# 9) De complexiteit van het algoritme wordt beschreven door n * | D | * log | D | waarbij n het aantal attributen is in de trainingsdataset D en | D | is het aantal tuples.

Wat is hebzuchtige recursieve binaire splitsing?

Bij de binaire splitsingsmethode worden de tupels gesplitst en wordt elke gesplitste kostenfunctie berekend. De laagste kostenverdeling is geselecteerd. De splitsingsmethode is binair en wordt gevormd als 2 takken. Het is recursief van aard omdat dezelfde methode (berekening van de kosten) wordt gebruikt voor het splitsen van de andere tupels van de dataset.

Dit algoritme wordt zo hebberig genoemd omdat het zich alleen richt op het huidige knooppunt. Het richt zich op het verlagen van de kosten, terwijl de andere knooppunten worden genegeerd.

Hoe kenmerken te selecteren om een ​​boom te maken?

Attribuutselectiemetingen worden ook wel splitsingsregels genoemd om te beslissen hoe de tuples worden gesplitst. De splitsingscriteria worden gebruikt om de dataset het beste te partitioneren. Deze metingen geven een rangschikking van de attributen voor het partitioneren van de trainingstupels.

De meest populaire methoden om het attribuut te selecteren zijn informatiewinst, Gini-index.

# 1) Informatiewinst

Deze methode is de belangrijkste methode die wordt gebruikt om beslissingsbomen te bouwen. Het vermindert de informatie die nodig is om de tuples te classificeren. Het vermindert het aantal tests dat nodig is om het gegeven tupel te classificeren. Het attribuut met de hoogste informatiewinst wordt geselecteerd.

De originele informatie die nodig is voor de classificatie van een tupel in dataset D wordt gegeven door:

Waar p de kans is dat het tuple tot klasse C behoort. De informatie wordt gecodeerd in bits, daarom wordt log naar basis 2 gebruikt. E (s) staat voor de gemiddelde hoeveelheid informatie die nodig is om het klassenlabel van dataset D te achterhalen. Deze informatiewinst wordt ook wel genoemd Entropie ​

De informatie die nodig is voor een exacte classificatie na portionering wordt gegeven door de formule:

Waar P (c) het gewicht van de partitie is. Deze informatie vertegenwoordigt de informatie die nodig is om de dataset D bij portionering door X te classificeren.

Informatiewinst is het verschil tussen de oorspronkelijke en verwachte informatie die nodig is om de tuples van dataset D te classificeren.

Winst is de reductie van informatie die vereist is door de waarde van X te kennen. Het attribuut met de hoogste informatieversterking wordt gekozen als 'beste'.

# 2) Winstverhouding

Informatiewinst kan er soms toe leiden dat portionering nutteloos is voor classificatie. De gain-ratio splitst de trainingsgegevensset echter op in partities en houdt rekening met het aantal tuples van de uitkomst ten opzichte van het totale tuples. Het attribuut met de maximale versterkingsverhouding wordt gebruikt als een splitsingsattribuut.

# 3) Gini-index

De Gini-index wordt alleen berekend voor binaire variabelen. Het meet de onzuiverheid in trainingstuples van dataset D, zoals

P is de kans dat tuple tot klasse C behoort. De Gini-index die wordt berekend voor binaire gesplitste dataset D door attribuut A wordt gegeven door:

Waarbij n de nde partitie is van de dataset D.

De vermindering van onzuiverheid wordt gegeven door het verschil tussen de Gini-index van de oorspronkelijke dataset D en Gini-index na partitie door attribuut A.

De maximale reductie in onzuiverheid of maximale Gini-index wordt geselecteerd als het beste kenmerk voor splitsing.

Overfitting in beslissingsbomen

Overfitting gebeurt wanneer een beslissingsboom zo perfect mogelijk probeert te zijn door de diepte van tests te vergroten en daardoor de fout te verkleinen. Dit resulteert in zeer complexe bomen en leidt tot overfitting.

Overfitting vermindert de voorspellende aard van de beslissingsboom. De benaderingen om overfitting van de bomen te voorkomen, zijn onder meer snoeien vóór en na het snoeien.

Wat is het snoeien van bomen?

Snoeien is de methode om de ongebruikte takken uit de beslisboom te verwijderen. Sommige takken van de beslissingsboom kunnen uitschieters of gegevens met ruis vertegenwoordigen.

Het snoeien van bomen is de methode om de ongewenste takken van de boom te verminderen. Dit zal de complexiteit van de boom verminderen en helpen bij een effectieve voorspellende analyse. Het vermindert de overfitting omdat het de onbelangrijke takken van de bomen verwijdert.

Er zijn twee manieren om de boom te snoeien:

# 1) Voorsnoeien : Bij deze benadering wordt de constructie van de beslissingsboom vroegtijdig gestopt. Het betekent dat er wordt besloten de takken niet verder te verdelen. Het laatste geconstrueerde knooppunt wordt het bladknooppunt en dit bladknooppunt kan de meest voorkomende klasse onder de tupels bevatten.

De maten voor attribuutselectie worden gebruikt om het gewicht van de splitsing te achterhalen. Er worden drempelwaarden voorgeschreven om te bepalen welke splitsingen als nuttig worden beschouwd. Als het partitioneren van het knooppunt resulteert in een splitsing door onder de drempel te vallen, wordt het proces gestopt.

# 2) Nasnoeien : Deze methode verwijdert de uitbijtertakken van een volgroeide boom. De ongewenste takken worden verwijderd en vervangen door een bladknooppunt dat het meest voorkomende klasselabel aangeeft. Deze techniek vereist meer berekening dan voorruning, maar is betrouwbaarder.

De gesnoeide bomen zijn nauwkeuriger en compacter in vergelijking met niet-gesnoeide bomen, maar ze hebben het nadeel van replicatie en herhaling.

Herhaling vindt plaats wanneer hetzelfde attribuut keer op keer wordt getest langs een tak van een boom. Replicatie treedt op wanneer de dubbele substructuren aanwezig zijn in de boom. Deze problemen kunnen worden opgelost door multivariate splitsingen.

De onderstaande afbeelding toont een ongesnoeide en gesnoeide boom.

Voorbeeld van een beslissingsboomalgoritme

Voorbeeld Bron

Een beslissingsboom construeren

Laten we een voorbeeld nemen van de weergegevensset van de afgelopen 10 dagen met attributen vooruitzichten, temperatuur, wind en vochtigheid. De uitkomstvariabele is cricket spelen of niet. We zullen het ID3-algoritme gebruiken om de beslissingsboom te bouwen.

Stap 1: De eerste stap is het maken van een hoofdknooppunt.

Stap 2: Als alle resultaten ja zijn, wordt het bladknooppunt 'ja' geretourneerd, anders wordt het bladknooppunt 'nee' geretourneerd.

Stap 3: Ontdek de entropie van alle waarnemingen en entropie met attribuut 'x' dat is E (S) en E (S, x).

Stap 4: Ontdek de informatiewinst en selecteer het attribuut met een hoge informatiewinst.

Stap5: Herhaal de bovenstaande stappen totdat alle attributen zijn afgedekt.

Berekening van entropie:

Ja nee

9 5

Als entropie nul is, betekent dit dat alle leden tot dezelfde klasse behoren en als entropie één is, betekent dit dat de helft van de tupels tot één klasse behoort en een van hen tot een andere klasse. 0.94 betekent eerlijke verdeling.

Zoek het kenmerk informatiewinst dat maximale informatiewinst oplevert.

Bijvoorbeeld 'Wind', het heeft twee waarden nodig: Sterk en Zwak, daarom x = {Sterk, Zwak}.

Ontdek H (x), P (x) voor x = zwak en x = sterk. H (S) is hierboven al berekend.

Zwak = 8

Sterk = 8

Bij 'zwakke' wind zeggen 6 van hen 'Ja' om cricket te spelen en 2 van hen 'Nee'. Dus entropie zal zijn:

Bij 'sterke' wind zeiden 3 'Nee' om cricket te spelen en 3 zeiden 'Ja'.

Dit toont een perfecte willekeur, aangezien de helft van items tot één klasse behoort en de resterende helft tot andere.

Bereken de informatiewinst,

Evenzo is de informatiewinst voor andere attributen:

Het kenmerk Outlook heeft de extensie hoogste informatiewinst van 0.246, dus het wordt gekozen als root.

Bewolkt heeft 3 waarden: zonnig, bewolkt en regen. Bewolkt met play cricket is altijd 'Ja'. Het eindigt dus met een bladknooppunt, 'ja'. Voor de andere waarden 'Sunny' en 'Rain'.

Tabel voor Outlook als 'Sunny' zal zijn:

Entropy voor 'Outlook' 'Sunny' is:

gratis realtime malwarebescherming 2017

Informatiewinst voor attributen met betrekking tot Sunny is:

De informatiewinst voor vochtigheid is het hoogst, daarom wordt deze gekozen als het volgende knooppunt. Evenzo wordt Entropy berekend voor regen. Wind geeft de hoogste informatiewinst ​

De beslissingsboom zou er als volgt uitzien:

Wat is voorspellende modellen?

De classificatiemodellen kunnen worden gebruikt om de uitkomsten van een onbekende set attributen te voorspellen.

Wanneer een dataset met onbekende klassenlabels in het model wordt ingevoerd, zal deze automatisch het klassenlabel eraan toewijzen. Deze methode om waarschijnlijkheid toe te passen om uitkomsten te voorspellen, wordt voorspellende modellering genoemd.

Voordelen van beslissingsboomclassificatie

Hieronder staan ​​de verschillende verdiensten van de beslissingsboomclassificatie vermeld:

1. Beslisboomclassificatie vereist geen domeinkennis, daarom is het geschikt voor het kennisontdekkingsproces.
2. De weergave van gegevens in de vorm van de boom is gemakkelijk te begrijpen voor mensen en is intuïtief.
3. Het kan multidimensionale gegevens verwerken.
4. Het is een snel proces met grote nauwkeurigheid.

Nadelen van de classificatie van beslissingsbomen

Hieronder worden de verschillende nadelen van de classificatie van beslissingsbomen weergegeven:

1. Soms worden beslissingsbomen erg complex en worden deze overfitte bomen genoemd.
2. Het beslissingsboomalgoritme is mogelijk geen optimale oplossing.
3. De beslissingsbomen kunnen een bevooroordeelde oplossing retourneren als een klassenlabel het domineert.

Gevolgtrekking

Decision Trees zijn dataminingtechnieken voor classificatie en regressieanalyse.

Deze techniek strekt zich nu uit over vele gebieden, zoals medische diagnose, doelmarketing, enz. Deze bomen worden geconstrueerd door een algoritme te volgen zoals ID3, CART. Deze algoritmen vinden verschillende manieren om de gegevens in partities te splitsen.

Het is de meest bekende begeleide leertechniek die wordt gebruikt bij machine learning en patroonanalyse. De beslissingsbomen voorspellen de waarden van de doelvariabele door modellen te bouwen door te leren van de trainingsset die aan het systeem wordt verstrekt.

We hopen dat je alles over Decision Tree Mining hebt geleerd in deze informatieve tutorial !!

PREV-zelfstudie ​ VOLGENDE zelfstudie

Aanbevolen literatuur

• Voorbeelden van datamining: meest voorkomende toepassingen van datamining 2021
• Technieken voor datamining: algoritme, methoden en toptools voor datamining
• Datamining: proces, technieken en grote problemen bij gegevensanalyse
• B Tree en B + Tree gegevensstructuur in C ++
• Binaire boomgegevensstructuur in C ++
• Dataminingproces: modellen, processtappen en betrokken uitdagingen
• AVL Tree and Heap-gegevensstructuur in C ++
• Datamining versus machine learning versus kunstmatige intelligentie versus diep leren