Algoritmo ID3

Algoritmo de árbol de decisión

Árbol de decisión potencial generado con ID3. Los atributos se organizan como nodos según la capacidad para clasificar los ejemplos. Los valores de los atributos se representan mediante ramas.

En el aprendizaje de árboles de decisión , ID3 ( Iterative Dichotomiser 3 ) es un algoritmo inventado por Ross Quinlan ^[1] que se utiliza para generar un árbol de decisión a partir de un conjunto de datos. ID3 es el precursor del algoritmo C4.5 y se utiliza normalmente en los dominios del aprendizaje automático y el procesamiento del lenguaje natural .

Algoritmo

El algoritmo ID3 comienza con el conjunto original como nodo raíz . En cada iteración del algoritmo, itera a través de cada atributo no utilizado del conjunto y calcula la entropía o la ganancia de información de ese atributo. Luego, selecciona el atributo que tiene el valor de entropía (o ganancia de información más grande) más pequeño. Luego, el conjunto se divide o particiona según el atributo seleccionado para producir subconjuntos de los datos. (Por ejemplo, un nodo se puede dividir en nodos secundarios según los subconjuntos de la población cuyas edades sean menores de 50, entre 50 y 100 y mayores de 100). El algoritmo continúa recursivamente en cada subconjunto, considerando solo los atributos que nunca se seleccionaron antes. ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle \mathrm {H} {(S)}}$ ${\displaystyle IG(S)}$ ${\displaystyle S}$

La recursión en un subconjunto puede detenerse en uno de estos casos:

• Cada elemento del subconjunto pertenece a la misma clase; en cuyo caso el nodo se convierte en un nodo hoja y se etiqueta con la clase de los ejemplos.
• No hay más atributos para seleccionar, pero los ejemplos aún no pertenecen a la misma clase. En este caso, el nodo se convierte en un nodo hoja y se etiqueta con la clase más común de los ejemplos en el subconjunto.
• No hay ejemplos en el subconjunto , lo que sucede cuando no se encontró ningún ejemplo en el conjunto principal que coincida con un valor específico del atributo seleccionado. Un ejemplo podría ser la ausencia de una persona entre la población con una edad superior a los 100 años. Luego, se crea un nodo hoja y se etiqueta con la clase más común de los ejemplos en el conjunto del nodo principal.

A lo largo del algoritmo, el árbol de decisión se construye con cada nodo no terminal ( nodo interno ) que representa el atributo seleccionado en el que se dividieron los datos, y nodos terminales (nodos hoja) que representan la etiqueta de clase del subconjunto final de esta rama.

Resumen

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

Propiedades

Árbol de decisión generado por ID3 que se utiliza para determinar si un par de nucleótidos particular dentro de una secuencia de pre-ARNm corresponde a un sitio de empalme de ARNm. Se ha demostrado que este árbol tiene una tasa de predicción correcta del 95 %. ^[2]

ID3 no garantiza una solución óptima. Puede converger en óptimos locales . Utiliza una estrategia voraz al seleccionar el mejor atributo local para dividir el conjunto de datos en cada iteración. La optimalidad del algoritmo se puede mejorar utilizando el retroceso durante la búsqueda del árbol de decisión óptimo, a costa de posiblemente demorar más tiempo.

ID3 puede sobreajustar los datos de entrenamiento. Para evitarlo, se deben preferir árboles de decisión más pequeños en lugar de los más grandes. ^{[ se necesita más explicación ]} Este algoritmo suele producir á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 en datos continuos que en datos factorizados (los datos factorizados tienen una cantidad discreta de valores posibles, lo que reduce los posibles puntos de ramificación). Si los valores de cualquier atributo dado son continuos , entonces hay muchos más lugares para dividir los datos en este atributo, y buscar el mejor valor por el cual dividir puede llevar mucho tiempo.

Uso

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

Las métricas ID3

Entropía

La entropía es una medida de la cantidad de incertidumbre en el conjunto (de datos) (es decir, la entropía caracteriza el conjunto (de datos) ). ${\displaystyle \mathrm {H} {(S)}}$ ${\displaystyle S}$ ${\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 que se calcula la entropía
  • Esto cambia en cada paso del algoritmo ID3, ya sea a un subconjunto del conjunto anterior en el caso de división por 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 entre el número de elementos de la clase y el número de elementos del conjunto ${\displaystyle x}$ ${\displaystyle S}$

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

En ID3, la entropía se calcula para cada atributo restante. El atributo con la entropía más pequeña se utiliza para dividir el conjunto 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 ; como tal, también se puede utilizar para cuantificar la cantidad en la que se desconoce la distribución de los valores de la cantidad. Una cantidad constante tiene entropía cero, ya que su distribución es perfectamente conocida . Por el contrario, una variable aleatoria distribuida uniformemente ( discreta o continuamente uniforme) 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 lo tanto, mayor será el potencial para mejorar la clasificación aquí. ${\displaystyle S}$

Como tal, ID3 es una heurística voraz que realiza una búsqueda de los mejores valores de entropía óptimos a nivel local . Su precisión se puede mejorar mediante el preprocesamiento de los datos.

Ganancia de información

La ganancia de información es la medida de la diferencia de entropía entre antes y después de dividir el conjunto en un atributo . En otras palabras, cuánta incertidumbre se redujo después de dividir el conjunto en un atributo . ${\displaystyle IG(A)}$ ${\displaystyle S}$ ${\displaystyle A}$ ${\displaystyle S}$ ${\displaystyle S}$ ${\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 a partir de la división del conjunto por atributo de manera que ${\displaystyle S}$ ${\displaystyle A}$ ${\displaystyle S=\bigcup _{t\in T}t}$
• ${\displaystyle p(t)}$– La proporción del número de elementos en el número de elementos del conjunto ${\displaystyle t}$ ${\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 en esta iteración. ${\displaystyle S}$

Véase también

• Árbol de clasificación y regresión (CART)
• Algoritmo C4.5
• Aprendizaje mediante árboles de decisión
  • Modelo de árbol de decisión

Referencias

1. Quinlan, JR 1986. Inducción de árboles de decisión. Mach. Learn. 1, 1 (marzo de 1986), 81–106
2. Taggart, Allison J; DeSimone, Alec M; Shih, Janice S; Filloux, Madeleine E; Fairbrother, William G (17 de junio de 2012). "Mapeo a gran escala de puntos de ramificación en transcripciones de pre-ARNm humano in vivo". Nature Structural & Molecular Biology . 19 (7): 719–721. doi :10.1038/nsmb.2327. ISSN  1545-9993. PMC  3465671 . PMID  22705790.

Lectura adicional

• Mitchell, Tom Michael (1997). Machine Learning . Nueva York, NY: McGraw-Hill. Págs. 55-58. ISBN. 0070428077.OCLC 36417892  .
• Grzymala-Busse, Jerzy W. (febrero de 1993). "Algoritmos seleccionados de aprendizaje automático a partir de ejemplos" (PDF) . Fundamenta Informaticae . 18 (2): 193–207 – vía ResearchGate.

Enlaces externos

• Seminarios – http://www2.cs.uregina.ca/
• Descripción y ejemplos – http://www.cise.ufl.edu/
• Descripción y ejemplos – http://www.cis.temple.edu/
• Árboles de decisión y clasificación de partidos políticos