En el aprendizaje del árbol de decisiones , ID3 ( dicotomizador iterativo 3 ) es un algoritmo inventado por Ross Quinlan [1] que se utiliza para generar un árbol de decisiones a partir de un conjunto de datos. ID3 es el precursor del algoritmo C4.5 y normalmente se utiliza en los dominios de aprendizaje automático y procesamiento del lenguaje natural .
Algoritmo
El algoritmo ID3 comienza con el conjunto original. como nodo raíz . En cada iteración del algoritmo, recorre todos los atributos no utilizados del conjunto.y calcula la entropía o la ganancia de información de ese atributo. A continuación, selecciona el atributo que tiene el valor de entropía más pequeño (o la mayor ganancia de información). El conjuntoluego se divide o particiona por el atributo seleccionado para producir subconjuntos de los datos. (Por ejemplo, un nodo se puede dividir en nodos secundarios en función de los subconjuntos de la población cuyas edades son menores de 50, entre 50 y 100 y mayores de 100). El algoritmo continúa recurriendo en cada subconjunto, considerando solo los atributos nunca seleccionado antes.
La recursividad en un subconjunto puede detenerse en uno de estos casos:
- todos los elementos del subconjunto pertenecen 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 del subconjunto.
- no hay ejemplos en el subconjunto , lo que ocurre 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 más de 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 los nodos terminales (nodos hoja) que representan la etiqueta de clase del subconjunto final de esta rama.
Resumen
- Calcule la entropía de cada atributo del conjunto de datos .
- Particionar ("dividir") el conjunto en subconjuntos utilizando el atributo para el que se minimiza la entropía resultante después de la división ; o, de manera equivalente, la ganancia de información es máxima .
- Cree un nodo de árbol de decisión que contenga ese atributo.
- Recurrir en subconjuntos utilizando los atributos restantes.
Pseudocódigo
ID3 (Ejemplos, Target_Attribute, Atributos) Crea un nodo raíz para el árbol Si todos los ejemplos son positivos, devuelve la raíz del árbol de un solo nodo, con etiqueta = +. Si todos los ejemplos son negativos, devuelve la raíz del árbol de un solo nodo, con etiqueta = -. Si el número de atributos de predicción está vacío, devuelva la raíz del árbol de un solo nodo, con etiqueta = valor más común del atributo de destino en los ejemplos. De lo contrario, comience A ← El atributo que mejor clasifica los ejemplos. Atributo de árbol de decisión para Raíz = A. Para cada valor posible, v i , de A, Agregue una nueva rama de árbol debajo de Root, correspondiente a la prueba A = v i . Sea Ejemplos ( v i ) el subconjunto de ejemplos que tienen el valor v i para A Si Ejemplos ( v i ) está vacío Luego, debajo de esta nueva rama, agregue un nodo hoja con la etiqueta = valor objetivo más común en los ejemplos De lo contrario, debajo de esta nueva rama agregue el subárbol ID3 (Ejemplos ( v i ), Target_Attribute, Attributes - {A}) Final Raíz de retorno
Propiedades
ID3 no garantiza una solución óptima. Puede converger en óptimos locales . Utiliza una estrategia codiciosa al seleccionar el mejor atributo localmente para dividir el conjunto de datos en cada iteración. La optimización del algoritmo se puede mejorar mediante el retroceso durante la búsqueda del árbol de decisión óptimo a costa de posiblemente tomar más tiempo.
ID3 puede sobreajustar los datos de entrenamiento. Para evitar el sobreajuste, los árboles de decisión más pequeños deben preferirse a los más grandes. [ se necesita más explicación ] Este algoritmo generalmente produce á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 un número discreto de valores posibles, lo que reduce los posibles puntos de bifurcació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 para dividir puede llevar mucho tiempo.
Uso
El algoritmo ID3 se utiliza al entrenar en un conjunto de datos. para producir un árbol de decisiones que se almacena en la memoria . En tiempo de ejecución , este árbol de decisión se usa para clasificar nuevos casos de prueba ( vectores de características ) atravesando el árbol de decisión usando las características del datum para llegar a un nodo hoja. La clase de este nodo terminal es la clase en la que se clasifica el caso de prueba.
Las métricas ID3
Entropía
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) ).
Dónde,
- - 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 dividir en un atributo o a una partición "hermana" del padre en caso de que la recursión haya terminado previamente.
- - El conjunto de clases en
- - La proporción del número de elementos en clase. al número de elementos del conjunto
Cuándo , el conjunto está perfectamente clasificado (es decir, todos los elementos en son de la misma clase).
En ID3, la entropía se calcula para cada atributo restante. El atributo con la entropía más pequeña se usa para dividir el conjuntoen 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 a 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 se conoce perfectamente . En contraste, una variable aleatoria distribuida uniformemente ( discreta o continuamente uniforme) maximiza la entropía. Por lo tanto, cuanto mayor es 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 es el potencial para mejorar la clasificación aquí.
Como tal, ID3 es una heurística codiciosa que realiza una búsqueda del mejor primero para los valores de entropía óptimos localmente . Su precisión se puede mejorar procesando previamente los datos.
Ganancia de información
Ganancia de información es la medida de la diferencia en entropía desde antes hasta después del conjunto se divide en un atributo . En otras palabras, ¿cuánta incertidumbre en se redujo después de dividir el conjunto en atributo .
Dónde,
- - Entropía de conjunto
- - Los subconjuntos creados a partir del conjunto de división por atributo tal que
- - La proporción del número de elementos en al número de elementos del conjunto
- - Entropía de subconjunto
En ID3, la ganancia de información se puede calcular (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.
Ver también
- Árbol de clasificación y regresión (CART)
- Algoritmo C4.5
- Aprendizaje del árbol de decisiones
- Modelo de árbol de decisión
Referencias
- ^ Quinlan, JR 1986. Inducción de árboles de decisión. Mach. Aprender. 1, 1 (marzo de 1986), 81–106
- ^ 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" . Naturaleza Biología Molecular y Estructural . 19 (7): 719–721. doi : 10.1038 / nsmb.2327 . ISSN 1545-9993 . PMC 3465671 . PMID 22705790 .
Otras lecturas
- Mitchell, Tom Michael (1997). Aprendizaje automático . Nueva York, NY: McGraw-Hill. pp. 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 - a través de 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