ID3 (algoritmo)

El algoritmo ID3 es uno de los algoritmos para construir un árbol de decisión . Diseñado por John R. Quinlan John R. Quinlan . Posteriormente, Quinlan creó una versión mejorada: el algoritmo C4.5 .

Algoritmo

Tome todas las características no utilizadas y calcule su entropía en relación con las muestras de prueba
Elija una característica para la que la entropía sea mínima (y la ganancia de información, respectivamente, sea máxima)
Haz un nodo de árbol que contenga este rasgo

El algoritmo es el siguiente:

ID3 (Tabla de ejemplos, Característica de destino, Características)

Si todos los ejemplos son positivos, devuelva el nodo con la etiqueta "+".
Si todos los ejemplos son negativos, devuelva el nodo con la etiqueta "-".
Si el conjunto de características está vacío, devuelva el nodo con la etiqueta que aparece más en los valores de características de destino en los ejemplos.
De lo contrario:
1. A es la característica que mejor clasifica los ejemplos (con el máximo beneficio informativo).
2. Crear una raíz de árbol de decisión; el signo en la raíz será . $A$
3. Para cada valor posible ( ): $A$ $v_{i}$
  1. Agregue una nueva rama de árbol debajo de la raíz con un nodo con valor $A=v_{yo}$
  2. Seleccione un subconjunto de ejemplos que tengan . $Ejemplos(v_{i})$ $A=v_{yo}$
  3. Si el subconjunto de ejemplos está vacío, debajo de esta nueva rama, agregue un nodo con la etiqueta que aparece más en los valores de la función de destino en los ejemplos.
  4. De lo contrario, debajo de esta nueva rama, agregue un subárbol llamando recursivamente a ID3( , Target Feature, Features) $Ejemplos(v_{i})$
Devolver raíz.

Literatura

Paklin N.B., Oreshkov V.I. Capítulo 9. // Business Analytics: De los Datos al Conocimiento (+CD): Tutorial. 2ª ed.- San Petersburgo. : Pedro, 2013. - S. 444-459. - ISBN 978-5-459-00717-6 .