decision tree algorithm examples data mining
Aquest tutorial en profunditat explica tot sobre l'algorisme de l'arbre de decisions en la mineria de dades. Coneixeu els exemples, l'algorisme i la classificació de l'arbre de decisions:
Vam fer una ullada a un parell de Exemples de mineria de dades al nostre anterior tutorial a Sèrie de formació gratuïta sobre mineria de dades .
La mineria d’arbres de decisions és un tipus de tècnica de mineria de dades que s’utilitza per crear models de classificació. Construeix models de classificació en forma d’arbre, com el seu nom. Aquest tipus de mineria pertany a l’aprenentatge a classe supervisat.
En l’aprenentatge supervisat, ja es coneix el resultat objectiu. Els arbres de decisió es poden utilitzar tant per a dades numèriques com per categories. Les dades categòriques representen el gènere, l’estat civil, etc. mentre que les dades numèriques representen l’edat, la temperatura, etc.
plantilla de cas de prova excel descàrrega gratuïta
A continuació es mostra un exemple d’un arbre de decisions amb el conjunt de dades.
[imatge font ]
Què aprendreu:
- Per a què serveix un arbre de decisions?
- Anàlisi de classificació
- Anàlisi de regressió
- Com funciona un arbre de decisions?
- Algorisme d'inducció de l'arbre de decisions
- Inducció de l'arbre de decisions
- CARRET
- Inducció de l'arbre de decisions per a l'aprenentatge automàtic: ID3
- Què és la divisió binària recursiva llaminera?
- Com es poden seleccionar els atributs per crear un arbre?
- Abastament excessiu en arbres de decisió
- Què és la poda d'arbres?
- Què és el modelatge predictiu?
- Avantatges de la classificació de l'arbre de decisions
- Desavantatges de la classificació de l'arbre de decisions
- Conclusió
- Lectura recomanada
Per a què serveix un arbre de decisions?
L’arbre de decisions s’utilitza per construir models de classificació i regressió. S'utilitza per crear models de dades que prediran etiquetes de classe o valors per al procés de presa de decisions. Els models es construeixen a partir del conjunt de dades de formació alimentat al sistema (aprenentatge supervisat).
Mitjançant un arbre de decisions, podem visualitzar les decisions que faciliten la seva comprensió i, per tant, és una tècnica popular de mineria de dades.
Anàlisi de classificació
La classificació de dades és una forma d’anàlisi que construeix un model que descriu variables de classe importants.Per exemple, un model creat per classificar les sol·licituds de préstecs bancaris com a segures o arriscades. Els mètodes de classificació s’utilitzen en l’aprenentatge automàtic i en el reconeixement de patrons.
L’aplicació de la classificació inclou la detecció de fraus, el diagnòstic mèdic, la comercialització d’objectius, etc. La sortida del problema de classificació es pren com a “Mode” de tots els valors observats del node terminal.
Es segueix un procés de dos passos per construir un model de classificació.
- En el primer pas, és a dir, l’aprenentatge: es construeix un model de classificació basat en dades de formació.
- En el segon pas, és a dir, Classificació, es comprova la precisió del model i, a continuació, s’utilitza el model per classificar dades noves. Les etiquetes de classes que es presenten aquí tenen la forma de valors discrets com ara 'sí' o 'no', 'segur' o 'arriscat'.
A continuació es presenta l'enfocament general dels models de classificació dels edificis:
[imatge font ]
Anàlisi de regressió
L’anàlisi de regressió s’utilitza per a la predicció d’atributs numèrics.
Els atributs numèrics també s’anomenen valors continus. Un model construït per predir els valors continus en lloc d’etiquetes de classe s’anomena model de regressió. La sortida de l'anàlisi de regressió és la 'mitjana' de tots els valors observats del node.
Com funciona un arbre de decisions?
Un arbre de decisions és un algorisme d’aprenentatge supervisat que funciona tant per a variables discretes com per a variables contínues. Divideix el conjunt de dades en subconjunts sobre la base de l'atribut més significatiu del conjunt de dades. Els algoritmes decideixen com l’arbre de decisions identifica aquest atribut i com es fa aquesta divisió.
El predictor més significatiu es designa com a node arrel, la divisió es fa per formar subnodes anomenats nodes de decisió i els nodes que no es divideixen més són nodes terminals o fulls.
A l'arbre de decisions, el conjunt de dades es divideix en regions homogènies i no superposades. Segueix un enfocament de dalt a baix ja que la regió superior presenta totes les observacions en un sol lloc que es divideix en dues o més branques que es divideixen més. Aquest enfocament també s’anomena a enfocament cobdiciós ja que només considera el node actual entre el treballat sense centrar-se en els futurs nodes.
Els algoritmes de l'arbre de decisions continuaran executant-se fins que s'assoleixi un criteri d'aturada, com ara el nombre mínim d'observacions, etc.
Un cop es crea un arbre de decisions, molts nodes poden representar dades atípiques o sorolloses. S’aplica el mètode de poda d’arbres per eliminar dades no desitjades. Això, al seu torn, millora la precisió del model de classificació.
Per trobar la precisió del model, s’utilitza un conjunt de proves format per tuples de prova i etiquetes de classe. Els percentatges de les tuples del conjunt de proves es classifiquen correctament pel model per identificar la precisió del model. Si es troba que el model és precís, s'utilitza per classificar les tuples de dades per a les quals no es coneixen les etiquetes de classe.
Alguns dels algoritmes de l’arbre de decisions inclouen l’algorisme de Hunt, ID3, CD4.5 i CART.
Exemple de creació d'un arbre de decisions
(L'exemple és extret de Data Mining Concepts: Han i Kimber)
# 1) Pas d'aprenentatge: Les dades de formació s’introdueixen al sistema per analitzar-les mitjançant un algorisme de classificació. En aquest exemple, l'etiqueta de classe és l'atribut, és a dir, 'decisió de préstec'. El model construït a partir d’aquestes dades de formació es representa en forma de regles de decisió.
# 2) Classificació: El conjunt de dades de prova s’alimenta al model per comprovar la precisió de la regla de classificació. Si el model dóna resultats acceptables, s'aplica a un conjunt de dades nou amb variables de classe desconegudes.
Algorisme d'inducció de l'arbre de decisions
Inducció de l'arbre de decisions
La inducció d’arbres de decisions és el mètode per aprendre els arbres de decisions a partir del conjunt d’entrenament. El conjunt de formació consisteix en atributs i etiquetes de classe. Les aplicacions de la inducció d’arbres de decisions inclouen astronomia, anàlisi financera, diagnòstic mèdic, fabricació i producció.
Un arbre de decisions és una estructura en forma d’arbre de diagrames de flux que es fa a partir de tuples de conjunt d’entrenament. El conjunt de dades es divideix en subconjunts més petits i està present en forma de nodes d’un arbre. L’estructura de l’arbre té un node arrel, nodes interns o nodes de decisió, node de fulla i branques.
El node arrel és el node superior. Representa el millor atribut seleccionat per a la classificació. Els nodes interns dels nodes de decisió representen una prova d'un atribut del node full de dades o del node terminal que representa l'etiqueta de classificació o de decisió. Les branques mostren el resultat de la prova realitzada.
Alguns arbres de decisió només tenen nodes binaris , això significa exactament dues branques d'un node, mentre que alguns arbres de decisió no són binaris.
La imatge següent mostra l'arbre de decisió del conjunt de dades Titanic per predir si el passatger sobreviurà o no.
[imatge font ]
CARRET
El model CART, és a dir, els models de classificació i regressió, és un algorisme d’arbre de decisions per construir models. El model de l'arbre de decisions en què els valors objectiu tenen una naturalesa discreta s'anomena models de classificació.
Un valor discret és un conjunt de valors finits o infinitament infinits, Per exemple, edat, mida, etc. Els models on els valors objectius es representen amb valors continus solen ser números que s’anomenen models de regressió. Les variables contínues són variables de coma flotant. Aquests dos models junts s’anomenen CART.
CART utilitza l’índex Gini com a matriu de classificació.
Inducció de l'arbre de decisions per a l'aprenentatge automàtic: ID3
A finals dels anys setanta i principis dels vuitanta, J.Ross Quinlan va ser un investigador que va construir un algorisme d’arbres de decisions per a l’aprenentatge automàtic. Aquest algorisme es coneix com ID3, dicotomitzador iteratiu . Aquest algorisme era una extensió dels sistemes d'aprenentatge conceptuals descrits per E.B Hunt, J i Marin.
ID3 més tard es va conèixer com C4.5. ID3 i C4.5 segueixen un cobejant enfocament de dalt a baix per construir arbres de decisió. L’algoritme comença amb un conjunt de dades d’entrenament amb etiquetes de classes que es divideixen en subconjunts més petits a mesura que es construeix l’arbre.
# 1) Inicialment, hi ha tres paràmetres, és a dir, llista d’atributs, mètode de selecció d’atributs i partició de dades . La llista d'atributs descriu els atributs de les tuples del conjunt d'entrenament.
# 2) El mètode de selecció d’atributs descriu el mètode per seleccionar el millor atribut per a la discriminació entre les tuples. Els mètodes utilitzats per a la selecció d’atributs poden ser Information Gain o Gini Index.
# 3) L’estructura de l’arbre (binària o no binària) es decideix pel mètode de selecció d’atributs.
# 4) Quan es construeix un arbre de decisions, comença com un únic node que representa les tuples.
# 5) Si les tuples de nodes arrel representen etiquetes de classe diferents, llavors crida a un mètode de selecció d'atributs per dividir o particionar les tuples. El pas conduirà a la formació de branques i nodes de decisió.
# 6) El mètode de divisió determinarà quin atribut s’ha de seleccionar per particionar les tuples de dades. També determina les branques a cultivar des del node segons el resultat de la prova. El motiu principal dels criteris de divisió és que la partició de cada branca de l'arbre de decisions ha de representar la mateixa etiqueta de classe.
A continuació es mostra un exemple d’atribut de divisió:
a. La porció anterior té un valor discret.
b. La porció anterior és de valor continu.
# 7) Els passos de particionament anteriors es segueixen recursivament per formar un arbre de decisió per a les tuples del conjunt de dades de formació.
# 8) El porcionament només s'atura quan es fan totes les particions o quan no es poden particionar les restants tuples.
# 9) La complexitat de l'algorisme és descrita per n * | D | * registre | D | on n és el nombre d'atributs del conjunt de dades d'entrenament D i | D | és el nombre de tuples.
Què és la divisió binària recursiva llaminera?
En el mètode de divisió binària, les tuples es divideixen i es calcula cada funció de cost dividit. Se selecciona la divisió de cost més baixa. El mètode de divisió és binari que es forma en 2 branques. És de naturalesa recursiva ja que s’utilitza el mateix mètode (càlcul del cost) per dividir les altres tuples del conjunt de dades.
Aquest algorisme es diu tan llaminer ja que només se centra en el node actual. Se centra a reduir el seu cost, mentre que la resta de nodes són ignorats.
Com es poden seleccionar els atributs per crear un arbre?
Les mesures de selecció d’atributs també s’anomenen regles de divisió per decidir com es dividiran les tuples. Els criteris de divisió s’utilitzen per particionar millor el conjunt de dades. Aquestes mesures proporcionen una classificació dels atributs per a la partició de les tuples de formació.
Els mètodes més populars per seleccionar l'atribut són el guany d'informació, índex Gini.
# 1) Guany d'informació
Aquest mètode és el mètode principal que s’utilitza per construir arbres de decisió. Redueix la informació necessària per classificar les tuples. Redueix el nombre de proves necessàries per classificar la tupla donada. Es selecciona l'atribut amb el guany d'informació més alt.
La informació original necessària per classificar una tupla al conjunt de dades D ve donada per:
On p és la probabilitat que la tupla pertanyi a la classe C. La informació es codifica en bits, per tant, s'utilitza el registre a la base 2. E (s) representa la quantitat mitjana d'informació necessària per esbrinar l'etiqueta de classe del conjunt de dades D. Aquest guany d'informació també s'anomena Entropia .
La informació necessària per a la classificació exacta després del porcionament ve donada per la fórmula:
On P (c) és el pes de la partició. Aquesta informació representa la informació necessària per classificar el conjunt de dades D en el porcionament per X.
El guany d'informació és la diferència entre la informació original i esperada que es requereix per classificar les tuples del conjunt de dades D.
converteix char a cadena c ++
El guany és la reducció de la informació que es requereix per conèixer el valor de X. L’atribut amb el guany d’informació més alt s’escull com a “millor”.
# 2) Relació de guanys
El guany d'informació de vegades pot resultar en una porció inútil per a la classificació. No obstant això, la ràtio de guany divideix el conjunt de dades de formació en particions i considera el nombre de tuples del resultat respecte al total de tuples. L'atribut amb la proporció de guany màxim s'utilitza com a atribut de divisió.
# 3) Índex de Gini
L'índex Gini es calcula només per a variables binàries. Mesura la impuresa en la formació de tuples del conjunt de dades D, com
P és la probabilitat que la tupla pertanyi a la classe C. L'índex de Gini que es calcula per al conjunt de dades binari dividit D per l'atribut A ve donat per:
On n és la enèsima partició del conjunt de dades D.
La reducció de la impuresa ve donada per la diferència de l’índex Gini del conjunt de dades original D i de l’índex Gini després de la partició per l’atribut A.
La reducció màxima de la impuresa o índex màxim de Gini se selecciona com el millor atribut per dividir.
Abastament excessiu en arbres de decisió
L’adequació excessiva passa quan un arbre de decisions intenta ser el més perfecte possible augmentant la profunditat de les proves i, per tant, redueix l’error. Això provoca arbres molt complexos i comporta un excés d’adequació.
L’adequació excessiva redueix la naturalesa predictiva de l’arbre de decisions. Els enfocaments per evitar l’adequació excessiva dels arbres inclouen la poda prèvia i posterior.
Què és la poda d'arbres?
La poda és el mètode per eliminar les branques no utilitzades de l'arbre de decisions. Algunes branques de l'arbre de decisions poden representar dades atípiques o sorolloses.
La poda d’arbres és el mètode per reduir les branques no desitjades de l’arbre. D’aquesta manera es reduirà la complexitat de l’arbre i es contribuirà en una anàlisi predictiva eficaç. Redueix l'adequació, ja que elimina les branques sense importància dels arbres.
Hi ha dues maneres de podar l’arbre:
# 1) Poda prèvia : En aquest enfocament, la construcció de l'arbre de decisió es deté aviat. Vol dir que es decideix no particionar més les branques. L'últim node construït es converteix en el node de fulla i aquest node de fulla pot tenir la classe més freqüent entre les tuples.
Les mesures de selecció d’atributs s’utilitzen per conèixer el pes de la divisió. Es prescriuen valors llindars per decidir quins fraccions es consideren útils. Si la porció del node resulta en la divisió caient per sota del llindar, el procés s'aturarà.
# 2) Post poda : Aquest mètode elimina les branques externes d'un arbre completament cultivat. Les branques no desitjades s’eliminen i se substitueixen per un node de fulla que indica l’etiqueta de classe més freqüent. Aquesta tècnica requereix més càlcul que prèvia podada, però és més fiable.
Els arbres podats són més precisos i compactes en comparació amb els arbres no podats, però presenten un desavantatge de replicació i repetició.
La repetició es produeix quan el mateix atribut es prova una i altra vegada al llarg d'una branca d'un arbre. Replicació es produeix quan els subarbres duplicats estan presents a l'arbre. Aquests problemes es poden resoldre mitjançant desdoblaments multivariants.
La imatge següent mostra un arbre no podat i podat.
Exemple d'algorisme de l'arbre de decisions
Exemple Font
Construint un arbre de decisions
Prenguem un exemple del conjunt de dades meteorològiques dels darrers 10 dies amb atributs de perspectiva, temperatura, vent i humitat. La variable de resultat serà jugar al cricket o no. Utilitzarem l’algorisme ID3 per construir l’arbre de decisions.
| Dia | Perspectiva | Temperatura | Humitat | Vent | Jugar al grillo |
|---|---|---|---|---|---|
| 7 | Encapotat | Guai | Normal | Fort | Sí |
| 1 | Assolellat | Calent | Alt | Debil | no |
| 2 | Assolellat | Calent | Alt | Fort | no |
| 3 | Encapotat | Calent | Alt | Debil | Sí |
| 4 | Pluja | Lleu | Alt | Debil | Sí |
| 5 | Pluja | Guai | Normal | Debil | Sí |
| 6 | Pluja | Guai | Normal | Fort | no |
| 8 | Assolellat | Lleu | Alt | Debil | no |
| 9 | Assolellat | Guai | Normal | Debil | Sí |
| 10 | Pluja | Lleu | Normal | Debil | Sí |
| 11 | Assolellat | Lleu | Normal | Fort | Sí |
| 12 | Encapotat | Lleu | Alt | Fort | Sí |
| 13 | Encapotat | Calent | Normal | Debil | Sí |
| 14 | Pluja | Lleu | Alt | Fort | no |
Pas 1: El primer pas serà crear un node arrel.
Pas 2: Si tots els resultats són afirmatius, es retornarà el node full 'sí', en cas contrari es retornarà el node full 'no'.
Pas 3: Esbrineu l’entropia de totes les observacions i entropia amb l’atribut “x” que és E (S) i E (S, x).
Pas 4: Esbrineu el guany d'informació i seleccioneu l'atribut amb un guany d'informació elevat.
Pas 5: Repetiu els passos anteriors fins que es cobreixin tots els atributs.
Càlcul de l'entropia:
Sí, no
setembre 5
Si l'entropia és zero, significa que tots els membres pertanyen a la mateixa classe i si l'entropia és un, significa que la meitat de les tuples pertanyen a una classe i un d'ells pertany a una altra classe. 0,94 significa distribució justa.
Cerqueu l’atribut de guany d’informació que proporciona el màxim guany d’informació.
Per exemple 'Vent', pren dos valors: fort i feble, per tant, x = {fort, feble}.
Esbrineu H (x), P (x) per a x = feble i x = fort. H (S) ja es calcula més amunt.
Debil = 8
Fort = 8
Per al vent 'feble', 6 d'ells diuen 'Sí' per jugar al criquet i 2 d'ells diuen 'No'. Així doncs, l’entropia serà:
Per a un vent 'fort', 3 van dir 'No' per jugar al criquet i 3 van dir 'Sí'.
Això mostra una aleatorietat perfecta ja que la meitat dels ítems pertanyen a una classe i la meitat restant pertanyen a altres.
Calculeu el guany d'informació,
De la mateixa manera, el guany d'informació per a altres atributs és:
La perspectiva de l'atribut té guany d'informació més alt de 0,246, per tant, es tria com a arrel.
El cobert té 3 valors: assolellat, cobert i pluja. Ennuvolat amb el joc de cricket sempre és 'Sí'. Per tant, acaba amb un node de fulla, 'sí'. Per als altres valors 'Assolellat' i 'Pluja'.
La taula per a Outlook com a 'assolellat' serà:
| Temperatura | Humitat | Vent | golf |
|---|---|---|---|
| Calent | Alt | Debil | no |
| Calent | Alt | Fort | no |
| Lleu | Alt | Debil | no |
| Guai | Normal | Debil | Sí |
| Lleu | Normal | Fort | Sí |
L'entropia per a 'Outlook' 'Sunny' és:
El guany d'informació sobre atributs respecte a Sunny és:
El guany d'informació per a la humitat és més elevat, per tant, es tria com a node següent. De la mateixa manera, l'entropia es calcula per a pluja. Wind proporciona el major guany d’informació .
eines per al desplegament continu en devops
L’arbre de decisions seria el següent:
Què és el modelatge predictiu?
Els models de classificació es poden utilitzar per predir els resultats d’un conjunt desconegut d’atributs.
Quan s'inclou al model un conjunt de dades amb etiquetes de classe desconegudes, se li assignarà automàticament l'etiqueta de classe. Aquest mètode d’aplicació de la probabilitat per predir els resultats s’anomena modelatge predictiu.
Avantatges de la classificació de l'arbre de decisions
A continuació es detallen els diversos mèrits de la classificació de l’arbre de decisions:
- La classificació de l’arbre de decisions no requereix cap coneixement del domini, per tant, és adequat per al procés de descoberta del coneixement.
- La representació de les dades en forma d’arbre és fàcil d’entendre pels humans i és intuïtiva.
- Pot gestionar dades multidimensionals.
- És un procés ràpid amb gran precisió.
Desavantatges de la classificació de l'arbre de decisions
A continuació es detallen els diversos desavantatges de la classificació de l'arbre de decisions:
- De vegades, els arbres de decisió esdevenen molt complexos i s’anomenen arbres sobrealimentats.
- És possible que l'algorisme de l'arbre de decisions no sigui una solució òptima.
- Els arbres de decisió poden retornar una solució esbiaixada si alguna etiqueta de classe la domina.
Conclusió
Els arbres de decisió són tècniques de mineria de dades per a la classificació i l’anàlisi de regressió.
Aquesta tècnica s’estén ara a moltes àrees com el diagnòstic mèdic, la comercialització d’objectius, etc. Aquests arbres es construeixen seguint un algorisme com ID3, CART. Aquests algorismes troben diferents maneres de dividir les dades en particions.
És la tècnica d’aprenentatge supervisat més àmpliament coneguda que s’utilitza en l’aprenentatge automàtic i l’anàlisi de patrons. Els arbres de decisió prediuen els valors de la variable objectiu mitjançant la creació de models mitjançant l'aprenentatge del conjunt de formació proporcionat al sistema.
Esperem que hagueu après tot sobre la mineria de l'arbre de decisions d'aquest tutorial informatiu.
Lectura recomanada
- Exemples de mineria de dades: aplicacions més habituals de mineria de dades 2021
- Tècniques de mineria de dades: algorisme, mètodes i eines principals de mineria de dades
- Mineria de dades: procés, tècniques i grans qüestions en l’anàlisi de dades
- Estructura de dades d’arbre B i arbre B + en C ++
- Estructura de dades de l'arbre binari en C ++
- Procés de mineria de dades: models, passos de procés i reptes implicats
- Arbre AVL i estructura de dades Heap a C ++
- Mineria de dades contra aprenentatge automàtic contra intel·ligència artificial contra aprenentatge profund