algoritmo ID3

1. Calcula la entropía de cada atributo .${\displaystyle a}$del conjunto de datos${\displaystyle S}$.
2. Particionar ("dividir") el conjunto${\displaystyle S}$en subconjuntos utilizando el atributo para el cual la entropía resultante después de la división es mínima ; o, equivalentemente, la ganancia de información es máxima .
3. Crea un nodo de árbol de decisión que contenga ese atributo.
4. Realizar recursión en subconjuntos utilizando los atributos restantes.

ID3 no garantiza una solución óptima. Puede converger hacia óptimos locales . Utiliza una estrategia voraz , seleccionando el mejor atributo local para dividir el conjunto de datos en cada iteración. La optimalidad del algoritmo puede mejorarse mediante el uso de retroceso durante la búsqueda del árbol de decisión óptimo, aunque esto podría aumentar el tiempo de ejecución.

ID3 puede sobreajustarse a los datos de entrenamiento. Para evitar el sobreajuste, se deben preferir árboles de decisión pequeños a árboles grandes. Este algoritmo suele generar árboles pequeños, pero no siempre produce el árbol de decisión más pequeño posible.

ID3 es más difícil de usar con datos continuos que con datos factorizados (los datos factorizados tienen un número discreto de valores posibles, lo que reduce los posibles puntos de ramificación). Si los valores de un atributo son continuos , existen muchos más puntos para dividir los datos según ese atributo, y buscar el mejor valor para la división puede llevar mucho tiempo.

El algoritmo ID3 se utiliza entrenándolo en un conjunto de datos.${\displaystyle S}$para generar un árbol de decisión que se almacena en memoria . En tiempo de ejecución , este árbol de decisión se utiliza para clasificar nuevos casos de prueba ( vectores de características ) recorriendo el árbol de decisión utilizando las características del dato para llegar a un nodo hoja.

Entropía${\displaystyle \mathrm {H} {(S)}}$es una medida de la cantidad de incertidumbre en el conjunto (de datos)${\displaystyle S}$(es decir, la entropía caracteriza el conjunto (de datos)${\displaystyle S}$).

${\displaystyle \mathrm {H} {(S)}=\sum _{x\in X}{-p(x)\log _{2}p(x)}}$

Dónde,

• ${\displaystyle S}$– El conjunto de datos actual para el cual se está calculando la entropía
  • Esto cambia en cada paso del algoritmo ID3, ya sea a un subconjunto del conjunto anterior en el caso de dividir por un atributo o a una partición "hermana" del padre en caso de que la recursión haya terminado previamente.
• ${\displaystyle X}$– El conjunto de clases en${\displaystyle S}$
• ${\displaystyle p(x)}$– La proporción del número de elementos en la clase${\displaystyle x}$al número de elementos en el conjunto${\displaystyle S}$

Cuando${\displaystyle \mathrm {H} {(S)}=0}$, el conjunto${\displaystyle S}$está perfectamente clasificado (es decir, todos los elementos en${\displaystyle S}$son de la misma clase).

En ID3, se calcula la entropía para cada atributo restante. El atributo con la entropía más pequeña se utiliza para dividir el conjunto.${\displaystyle S}$En esta iteración, la entropía en la teoría de la información mide cuánta información se espera obtener al medir una variable aleatoria ; por lo tanto, también se puede usar para cuantificar hasta qué punto se desconoce la distribución de los valores de la cantidad. Una cantidad constante tiene entropía cero, ya que su distribución se conoce perfectamente . En cambio, una variable aleatoria con distribución uniforme ( discreta o continua ) maximiza la entropía. Por lo tanto, cuanto mayor sea la entropía en un nodo, menos información se conoce sobre la clasificación de los datos en esta etapa del árbol; y, por consiguiente, mayor será el potencial para mejorar la clasificación en este punto.

Por lo tanto, ID3 es una heurística voraz que realiza una búsqueda primero del mejor para encontrar valores de entropía óptimos locales . Su precisión puede mejorarse mediante el preprocesamiento de los datos.

Obtención de información${\displaystyle IG(A)}$es la medida de la diferencia de entropía de antes a después del conjunto${\displaystyle S}$está dividido por un atributo${\displaystyle A}$. En otras palabras, ¿cuánta incertidumbre en${\displaystyle S}$se redujo después de dividir el conjunto${\displaystyle S}$sobre el atributo${\displaystyle A}$.

${\displaystyle IG(S,A)=\mathrm {H} {(S)}-\sum _{t\in T}p(t)\mathrm {H} {(t)}=\mathrm {H} {(S)}-\mathrm {H} {(S|A)}.}$

Dónde,

• ${\displaystyle \mathrm {H} (S)}$– Entropía del conjunto${\displaystyle S}$
• ${\displaystyle T}$– Los subconjuntos creados al dividir el conjunto${\displaystyle S}$por atributo${\displaystyle A}$de tal manera que${\displaystyle S=\bigcup _{t\in T}t}$
• ${\displaystyle p(t)}$– La proporción del número de elementos en${\displaystyle t}$al número de elementos en el conjunto${\displaystyle S}$
• ${\displaystyle \mathrm {H} (t)}$– Entropía del subconjunto${\displaystyle t}$

En ID3, se puede calcular la ganancia de información (en lugar de la entropía) para cada atributo restante. El atributo con la mayor ganancia de información se utiliza para dividir el conjunto.${\displaystyle S}$en esta iteración.