Algoritme ID3

El algoritme ID3 és un generador d'arbres de decisió creat per Ross Quinlan.^[1] Predecessor de l'algoritme C4.5. Els seus usos típics s'engloben en l'àrea de l'aprenentage automàtic.

Algoritme

El seu us s'engloba en la busca d'hipòtesis o regles en ell, donat un conjunt d'eixemples. El conjunt d'eixemples deurà estar conformat per una série de tuplas de valors, denominats atributs, en el que un d'ells (l'atribut a classificar) és l'objectiu, el qual és de tipo binario (positiu o negatiu, sí o no, vàlit o inválido, etc.).

D'esta forma l'algoritme tracta d'obtindre les hipòtesis que classifiquen davant noves instàncies, si dit eixemple va a ser positiu o negatiu.

ID3 realisa esta llabor per mig de la construcció d'un arbre de decisió.

Els elements són:

Nodos: Els quals contindran atributs.
Arcs: Els quals contenen valors possibles del nodo pare.
Fulls: Nodos que classifiquen l'eixemple com a positiu o negatiu.

L'algoritme

Aneu3(Eixemples, Atribut-objectiu, Atributs )
   Si tots els eixemples són positius tornar un nodo positiu
   Si tots els eixemples són negatius tornar un nodo negatiu
   Si Atributs està buit tornar el vot majoritari del valor de l'atribut objectiu en
                                                                                  Eixemples
   En un atre cas
        Siga A Atribut el MEJOR d'atributs
        Per a cada v valor de l'atribut fer
              Siga Eixemples(v) el subconjunt d'eixemples el valor dels quals d'atribut A és v
              Si Eixemples(v) està buit tornar un nodo en el vot majoritari de l'Atribut
                                                              objectiu d'Eixemples
              Sino Tornar Aneu3(Eixemples(v), Atribut-objectiu, Atributs/{A})

Observe's que la construcció de l'arbre es fa forma recursiva, sent les tres primeres llínees i la penúltima els casos base que construïxen els nodos fulls.

Vore també

Referències

↑ Machine Learning.1(1)
81–106.ISSN 0885-6125.doi:10.1007/bf00116251.Consultat el 2025-03-30.

Bibliografia

Mitchell, T.M. Machine Learning (McGraw-Hill, 1997)

Referències

Este artícul conté una traducció derivada de «Algoritmo ID3» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.

[1] Machine Learning.1(1)
81–106.ISSN 0885-6125.doi:10.1007/bf00116251.Consultat el 2025-03-30.

[1]