Algoritmo de ID3

En el aprendizaje del árbol de decisión, ID3 (Dichotomiser Iterativo 3) es un algoritmo usado para generar un árbol de decisión inventado por Ross Quinlan. ID3 es el precursor al algoritmo C4.5.

Algoritmo

El algoritmo ID3 se puede resumir así:

  1. Tome todos los atributos no usados y cuente su entropía acerca de muestras de prueba
  2. Elija el atributo para el cual la entropía es mínima (o, equivalentemente, la ganancia de información es máxima)
  3. Haga el nodo que contiene ese atributo

El algoritmo es así:

ID3 (ejemplos, Target_Attribute, atributos)

La métrica ID3

Para evitar la sobreformación, los árboles de decisión más pequeños se deberían preferir sobre más grande. Este algoritmo por lo general produce pequeños árboles, pero no siempre produce el árbol más pequeño posible.

El paso de optimización hace el uso de la entropía de información:

Entropía

:

Donde:

Una entropía de 0 identifica un juego absolutamente secreto.

La entropía es usada para determinar que nodo dividirse después en el algoritmo. Más alto la entropía, más alto el potencial para mejorar la clasificación aquí.

Ganancia

La ganancia se calcula para estimar la ganancia producida por una hendidura en un atributo:

:

Donde:

La ganancia cuantifica la mejora de la entropía dividiéndose en un atributo: más alto es mejor.

Véase también

Enlaces externos

C#

Buscar