C4.5

Extracte alemà de l'arbre de decisió C4.5.

C4.5 és un algoritme usat per a generar un arbre de decisió desenrollat per Ross Quinlan. C4.5 és una extensió del algoritme ID3 desenrollat anteriorment per Quinlan. Els arbres de decisió generats per C4.5 poden ser usats per a classificació, i per esta raó, C4.5 està casi sempre referit com un classificador estadístic.

Algoritme

C4.5 construïx arbres de decisió des d'un grup de senyes d'entrenament de la mateixa forma en que ho fa ID3, usant el concepte d'entropía d'informació. Les senyes d'entrenament són un grup $S=s_1,s_2,\mathrm{...}$ d'eixemples ya classificats. Cada eixemple $s_i=x_1,x_2,\mathrm{...}$ és un vector a on $x_1,x_2,\mathrm{...}$ representen els atributs o característiques de l'eixemple. Les senyes d'entrenament són aumentats en un vector $C=c_1,c_2,\mathrm{...}$ a on $c_1,c_2,\mathrm{...}$ representen la classe a la que pertany cada mostra.

En cada nodo de l'arbre, C4.5 elegix un atribut de les senyes que més eficaçment dividixen el conjunt de mostres en subconjunts enriquits en una classe o una atra. El seu criteri és el normalisat para guany d'informació (diferència d'entropía) que resulta en l'elecció d'un atribut per a dividir les senyes. L'atribut en el major guany d'informació normalisada s'elegix com a paràmetro de decisió. L'algoritme C4.5 dividix recursivamente en sublistas més menudes.

Este algoritme té uns pocs casos base.

• Totes les mostres en la llista pertanyen a la mateixa classe. Quan açò succeïx, simplement crea un nodo de full per al arbre de decisió dient que elegixca eixa classe.
• Cap de les característiques proporciona cap guany d'informació. En este cas, C4.5 crea un nodo de decisió més dalt de l'arbre utilisant el valor esperat de la classe.
• Instància de la classe prèviament no vista trobada. Una volta més, C4.5 crea un nodo de decisió més dalt en l'arbre en el valor esperat.

Pseudocódigo

En pseudocódigo, l'algoritme general per a construir arbres de decisió és:

1. Comprovar els casos base
2. Per a cada atribut a
   1. Trobar el guany d'informació normalisada de la divisió de a
3. Deixar que a_best siga l'atribut en el guany d'informació normalisada més alta
4. Crear un nodo de decisió que dividixca a_best
5. Repetir en les sublistas obtingudes per divisió de a_best, i agregar estos nodos com a fills de nodo

Implementacions

J48 és una implementació open source en llenguage de programació Java de l'algoritme C4.5 en la ferramenta weka de mineria de senyes.

Vore també

• Algoritme ID3