Ejemplos de algoritmos de árboles de decisión en minería de datos

decision tree algorithm examples data mining

Este tutorial detallado explica todo sobre el algoritmo de árbol de decisión en minería de datos. Aprenderá sobre ejemplos, algoritmos y clasificación de árboles de decisión:

Echamos un vistazo a un par de Ejemplos de minería de datos en nuestro tutorial anterior en Serie gratuita de formación sobre minería de datos .

Decision Tree Mining es un tipo de técnica de minería de datos que se utiliza para construir modelos de clasificación. Crea modelos de clasificación en forma de estructura en forma de árbol, como su nombre. Este tipo de minería pertenece al aprendizaje en clase supervisado.

En el aprendizaje supervisado, el resultado objetivo ya se conoce. Los árboles de decisión se pueden utilizar tanto para datos categóricos como numéricos. Los datos categóricos representan sexo, estado civil, etc., mientras que los datos numéricos representan edad, temperatura, etc.

servidores privados de world of warcraft vanilla

A continuación se muestra un ejemplo de un árbol de decisiones con el conjunto de datos.

(imagen fuente )

Lo que vas a aprender:

• ¿Cuál es el uso de un árbol de decisiones?
• Análisis de clasificación
• Análisis de regresión
• ¿Cómo funciona un árbol de decisiones?
• Algoritmo de inducción del árbol de decisión
• Inducción del árbol de decisión
• CARRO
• Inducción del árbol de decisiones para el aprendizaje automático: ID3
• ¿Qué es la división binaria recursiva codiciosa?
• ¿Cómo seleccionar atributos para crear un árbol?
  • # 1) Ganancia de información
  • # 2) Relación de ganancia
  • # 3) Índice de Gini
• Sobreajuste en árboles de decisión
• ¿Qué es la poda de árboles?
• ¿Qué es el modelado predictivo?
• Ventajas de la clasificación del árbol de decisiones
• Desventajas de la clasificación del árbol de decisiones
• Conclusión
• Lectura recomendada

¿Cuál es el uso de un árbol de decisiones?

El árbol de decisiones se utiliza para crear modelos de clasificación y regresión. Se utiliza para crear modelos de datos que predecirán etiquetas de clase o valores para el proceso de toma de decisiones. Los modelos se crean a partir del conjunto de datos de entrenamiento que se alimentan al sistema (aprendizaje supervisado).

Usando un árbol de decisiones, podemos visualizar las decisiones que lo hacen fácil de entender y, por lo tanto, es una técnica de minería de datos popular.

Análisis de clasificación

La clasificación de datos es una forma de análisis que construye un modelo que describe importantes variables de clase.Por ejemplo, un modelo creado para clasificar las solicitudes de préstamos bancarios como seguras o riesgosas. Los métodos de clasificación se utilizan en el aprendizaje automático y el reconocimiento de patrones.

La aplicación de la clasificación incluye detección de fraude, diagnóstico médico, marketing objetivo, etc. La salida del problema de clasificación se toma como “Modo” de todos los valores observados del nodo terminal.

Se sigue un proceso de dos pasos para construir un modelo de clasificación.

1. En el primer paso, es decir, aprendizaje: se construye un modelo de clasificación basado en datos de entrenamiento.
2. En el segundo paso, es decir, Clasificación, se verifica la precisión del modelo y luego se utiliza el modelo para clasificar nuevos datos. Las etiquetas de clase que se presentan aquí tienen la forma de valores discretos como 'sí' o 'no', 'seguro' o 'riesgoso'.

El enfoque general para los modelos de clasificación de edificios se da a continuación:

(imagen fuente )

Análisis de regresión

El análisis de regresión se utiliza para la predicción de atributos numéricos.

Los atributos numéricos también se denominan valores continuos. Un modelo creado para predecir los valores continuos en lugar de las etiquetas de clase se denomina modelo de regresión. El resultado del análisis de regresión es la 'Media' de todos los valores observados del nodo.

¿Cómo funciona un árbol de decisiones?

Un árbol de decisiones es un algoritmo de aprendizaje supervisado que funciona tanto para variables discretas como continuas. Divide el conjunto de datos en subconjuntos sobre la base del atributo más significativo del conjunto de datos. Los algoritmos deciden cómo el árbol de decisión identifica este atributo y cómo se realiza esta división.

El predictor más significativo se designa como nodo raíz, la división se realiza para formar subnodos denominados nodos de decisión, y los nodos que no se dividen más son nodos terminales o de hoja.

En el árbol de decisiones, el conjunto de datos se divide en regiones homogéneas y no superpuestas. Sigue un enfoque de arriba hacia abajo, ya que la región superior presenta todas las observaciones en un solo lugar que se divide en dos o más ramas que se dividen aún más. Este enfoque también se llama enfoque codicioso ya que solo considera el nodo actual entre los trabajados sin centrarse en los nodos futuros.

Los algoritmos del árbol de decisión continuarán ejecutándose hasta que se alcance un criterio de parada, como el número mínimo de observaciones, etc.

Una vez que se construye un árbol de decisión, muchos nodos pueden representar valores atípicos o datos ruidosos. El método de poda de árboles se aplica para eliminar datos no deseados. Esto, a su vez, mejora la precisión del modelo de clasificación.

Para encontrar la precisión del modelo, se utiliza un conjunto de prueba que consta de tuplas de prueba y etiquetas de clase. Los porcentajes de las tuplas de conjuntos de prueba están clasificados correctamente por el modelo para identificar la precisión del modelo. Si se determina que el modelo es preciso, se utiliza para clasificar las tuplas de datos para las que no se conocen las etiquetas de clase.

Algunos de los algoritmos del árbol de decisión incluyen el algoritmo de Hunt, ID3, CD4.5 y CART.

Ejemplo de creación de un árbol de decisiones

(El ejemplo está tomado de Conceptos de minería de datos: Han y Kimber)

# 1) Paso de aprendizaje: Los datos de entrenamiento se introducen en el sistema para ser analizados por un algoritmo de clasificación. En este ejemplo, la etiqueta de clase es el atributo, es decir, 'decisión de préstamo'. El modelo construido a partir de estos datos de entrenamiento se representa en forma de reglas de decisión.

# 2) Clasificación: El conjunto de datos de prueba se alimenta al modelo para verificar la precisión de la regla de clasificación. Si el modelo da resultados aceptables, se aplica a un nuevo conjunto de datos con variables de clase desconocidas.

Algoritmo de inducción del árbol de decisión

Inducción del árbol de decisión

La inducción de árboles de decisión es el método para aprender los árboles de decisión del conjunto de entrenamiento. El conjunto de entrenamiento consta de atributos y etiquetas de clase. Las aplicaciones de la inducción del árbol de decisiones incluyen astronomía, análisis financiero, diagnóstico médico, fabricación y producción.

Un árbol de decisión es una estructura similar a un árbol de diagrama de flujo que se crea a partir de tuplas de conjuntos de entrenamiento. El conjunto de datos se divide en subconjuntos más pequeños y está presente en forma de nodos de un árbol. La estructura de árbol tiene un nodo raíz, nodos internos o nodos de decisión, nodo hoja y ramas.

El nodo raíz es el nodo superior. Representa el mejor atributo seleccionado para la clasificación. Los nodos internos de los nodos de decisión representan una prueba de un atributo del nodo hoja del conjunto de datos o del nodo terminal que representa la clasificación o etiqueta de decisión. Las ramas muestran el resultado de la prueba realizada.

Algunos árboles de decisión solo tienen nodos binarios , eso significa exactamente dos ramas de un nodo, mientras que algunos árboles de decisión no son binarios.

La imagen a continuación muestra el árbol de decisiones del conjunto de datos del Titanic para predecir si el pasajero sobrevivirá o no.

(imagen fuente )

CARRO

El modelo CART, es decir, modelos de clasificación y regresión, es un algoritmo de árbol de decisión para construir modelos. El modelo de árbol de decisión en el que los valores objetivo tienen una naturaleza discreta se denomina modelos de clasificación.

Un valor discreto es un conjunto de valores finito o numerablemente infinito, Por ejemplo, edad, tamaño, etc. Los modelos donde los valores objetivo están representados por valores continuos suelen ser números que se denominan Modelos de regresión. Las variables continuas son variables de punto flotante. Estos dos modelos juntos se denominan CART.

CART utiliza el índice de Gini como matriz de clasificación.

Inducción del árbol de decisiones para el aprendizaje automático: ID3

A finales de la década de 1970 y principios de la de 1980, J. Ross Quinlan era un investigador que construyó un algoritmo de árbol de decisiones para el aprendizaje automático. Este algoritmo se conoce como ID3, dicotomizador iterativo . Este algoritmo fue una extensión de los sistemas de aprendizaje de conceptos descritos por E.B Hunt, J y Marin.

ID3 más tarde llegó a conocerse como C4.5. ID3 y C4.5 siguen un enfoque codicioso de arriba hacia abajo para construir árboles de decisión. El algoritmo comienza con un conjunto de datos de entrenamiento con etiquetas de clase que se dividen en subconjuntos más pequeños a medida que se construye el árbol.

#1) Inicialmente, hay tres parámetros, es decir lista de atributos, método de selección de atributos y partición de datos . La lista de atributos describe los atributos de las tuplas del conjunto de entrenamiento.

#2) El método de selección de atributos describe el método para seleccionar el mejor atributo para la discriminación entre tuplas. Los métodos utilizados para la selección de atributos pueden ser Ganancia de información o Índice de Gini.

#3) La estructura del árbol (binario o no binario) se decide mediante el método de selección de atributos.

#4) Al construir un árbol de decisión, comienza como un solo nodo que representa las tuplas.

#5) Si las tuplas del nodo raíz representan diferentes etiquetas de clase, entonces llama a un método de selección de atributos para dividir o particionar las tuplas. El paso conducirá a la formación de ramas y nodos de decisión.

#6) El método de división determinará qué atributo debe seleccionarse para particionar las tuplas de datos. También determina las ramas que se cultivarán desde el nodo de acuerdo con el resultado de la prueba. El motivo principal de los criterios de división es que la partición en cada rama del árbol de decisión debe representar la misma etiqueta de clase.

A continuación se muestra un ejemplo de atributo de división:

una. Las porciones anteriores se valoran de forma discreta.

B. La porción anterior es para valores continuos.

#7) Los pasos de particionamiento anteriores se siguen de forma recursiva para formar un árbol de decisión para las tuplas del conjunto de datos de entrenamiento.

#8) La división se detiene solo cuando se realizan todas las particiones o cuando las tuplas restantes no se pueden dividir más.

#9) La complejidad del algoritmo se describe mediante n * | D | * registro | D | donde n es el número de atributos en el conjunto de datos de entrenamiento D y | D | es el número de tuplas.

¿Qué es la división binaria recursiva codiciosa?

En el método de división binaria, las tuplas se dividen y se calcula cada función de costo de división. Se selecciona la división de costo más baja. El método de división es binario y está formado por 2 ramas. Es de naturaleza recursiva, ya que se utiliza el mismo método (calcular el costo) para dividir las otras tuplas del conjunto de datos.

Este algoritmo se llama tan codicioso ya que se centra solo en el nodo actual. Se centra en reducir su coste, mientras que los demás nodos se ignoran.

¿Cómo seleccionar atributos para crear un árbol?

Las medidas de selección de atributos también se denominan reglas de división para decidir cómo se dividirán las tuplas. Los criterios de división se utilizan para particionar mejor el conjunto de datos. Estas medidas proporcionan una clasificación a los atributos para dividir las tuplas de entrenamiento.

Los métodos más populares para seleccionar el atributo son la ganancia de información, el índice de Gini.

# 1) Ganancia de información

Este método es el método principal que se utiliza para construir árboles de decisión. Reduce la información que se requiere para clasificar las tuplas. Reduce el número de pruebas necesarias para clasificar la tupla dada. Se selecciona el atributo con la mayor ganancia de información.

La información original necesaria para la clasificación de una tupla en el conjunto de datos D viene dada por:

Donde p es la probabilidad de que la tupla pertenezca a la clase C. La información está codificada en bits, por lo tanto, se usa el registro en base 2. E (s) representa la cantidad promedio de información requerida para encontrar la etiqueta de clase del conjunto de datos D. Esta ganancia de información también se llama Entropía .

La información requerida para la clasificación exacta después del porcionado viene dada por la fórmula:

Donde P (c) es el peso de la partición. Esta información representa la información necesaria para clasificar el conjunto de datos D sobre la división por X.

La ganancia de información es la diferencia entre la información original y esperada que se requiere para clasificar las tuplas del conjunto de datos D.

La ganancia es la reducción de información que se requiere al conocer el valor de X. El atributo con la mayor ganancia de información se elige como 'mejor'.

# 2) Relación de ganancia

La obtención de información puede resultar en ocasiones en que la porciones sea inútil para la clasificación. Sin embargo, la relación de ganancia divide el conjunto de datos de entrenamiento en particiones y considera el número de tuplas del resultado con respecto a las tuplas totales. El atributo con la relación de ganancia máxima se utiliza como atributo de división.

# 3) Índice de Gini

El índice de Gini se calcula solo para variables binarias. Mide la impureza en el entrenamiento de tuplas del conjunto de datos D, como

P es la probabilidad de que la tupla pertenezca a la clase C. El índice de Gini que se calcula para el conjunto de datos dividido binario D por el atributo A viene dado por:

Donde n es la enésima partición del conjunto de datos D.

La reducción de la impureza viene dada por la diferencia del índice de Gini del conjunto de datos original D y el índice de Gini después de la partición por el atributo A.

La máxima reducción de impurezas o índice de Gini máximo se selecciona como el mejor atributo para la división.

Sobreajuste en árboles de decisión

El sobreajuste ocurre cuando un árbol de decisiones intenta ser lo más perfecto posible aumentando la profundidad de las pruebas y, por lo tanto, reduce el error. Esto da como resultado árboles muy complejos y conduce a un sobreajuste.

El sobreajuste reduce la naturaleza predictiva del árbol de decisiones. Los enfoques para evitar el sobreajuste de los árboles incluyen la poda previa y posterior.

¿Qué es la poda de árboles?

La poda es el método para eliminar las ramas no utilizadas del árbol de decisiones. Algunas ramas del árbol de decisiones pueden representar valores atípicos o datos ruidosos.

La poda de árboles es el método para reducir las ramas no deseadas del árbol. Esto reducirá la complejidad del árbol y ayudará en un análisis predictivo eficaz. Reduce el sobreajuste ya que elimina las ramas sin importancia de los árboles.

Hay dos formas de podar el árbol:

mejor software de copia de seguridad de imagen gratuito 2017

# 1) Poda previa : En este enfoque, la construcción del árbol de decisiones se detiene antes. Significa que se decidió no dividir más las ramas. El último nodo construido se convierte en el nodo hoja y este nodo hoja puede contener la clase más frecuente entre las tuplas.

Las medidas de selección de atributos se utilizan para averiguar el peso de la división. Los valores de umbral se prescriben para decidir qué divisiones se consideran útiles. Si la división del nodo da como resultado una división al caer por debajo del umbral, el proceso se detiene.

# 2) Postpoda : Este método elimina las ramas atípicas de un árbol completamente desarrollado. Las ramas no deseadas se eliminan y se reemplazan por un nodo hoja que indica la etiqueta de clase más frecuente. Esta técnica requiere más cálculos que la poda previa, sin embargo, es más confiable.

Los árboles podados son más precisos y compactos en comparación con los árboles sin podar, pero tienen una desventaja de replicación y repetición.

La repetición ocurre cuando el mismo atributo se prueba una y otra vez a lo largo de una rama de un árbol. Replicación ocurre cuando los subárboles duplicados están presentes dentro del árbol. Estos problemas pueden resolverse mediante divisiones multivariadas.

La siguiente imagen muestra un árbol podado y sin podar.

Ejemplo de algoritmo de árbol de decisión

Ejemplo Fuente

Construcción de un árbol de decisiones

Tomemos un ejemplo del conjunto de datos meteorológicos de los últimos 10 días con los atributos perspectiva, temperatura, viento y humedad. La variable de resultado será jugar al cricket o no. Usaremos el algoritmo ID3 para construir el árbol de decisiones.

Paso 1: El primer paso será crear un nodo raíz.

Paso 2: Si todos los resultados son sí, entonces se devolverá el nodo hoja 'sí'; de lo contrario, se devolverá el nodo hoja 'no'.

Paso 3: Descubra la entropía de todas las observaciones y la entropía con el atributo 'x' que es E (S) y E (S, x).

Paso 4: Descubra la ganancia de información y seleccione el atributo con alta ganancia de información.

Paso 5: Repita los pasos anteriores hasta que se cubran todos los atributos.

Cálculo de entropía:

sí No

9 5

Si la entropía es cero, significa que todos los miembros pertenecen a la misma clase y si la entropía es uno, significa que la mitad de las tuplas pertenecen a una clase y una de ellas pertenece a otra clase. 0,94 significa distribución justa.

Encuentre el atributo de ganancia de información que proporciona la máxima ganancia de información.

Por ejemplo “Viento”, toma dos valores: Fuerte y Débil, por lo tanto, x = {Fuerte, Débil}.

Averigüe H (x), P (x) para x = débil y x = fuerte. H (S) ya se ha calculado anteriormente.

Débil = 8

Fuerte = 8

Para el viento 'débil', 6 de ellos dicen 'Sí' para jugar al cricket y 2 de ellos dicen 'No'. Entonces la entropía será:

Para viento 'fuerte', 3 dijeron 'No' para jugar al cricket y 3 dijeron 'Sí'.

Esto muestra una aleatoriedad perfecta ya que la mitad de los elementos pertenecen a una clase y la mitad restante pertenece a otras.

Calcule la ganancia de información,

De manera similar, la ganancia de información para otros atributos es:

El atributo outlook tiene el mayor ganancia de información de 0,246, por lo que se elige como raíz.

Cubierto tiene 3 valores: Soleado, Cubierto y Lluvia. Overcast with play cricket siempre es 'Sí'. Entonces termina con un nodo hoja, 'sí'. Para los demás valores “Soleado” y “Lluvia”.

La tabla para Outlook como 'Soleado' será:

La entropía de 'Outlook' 'Sunny' es:

La ganancia de información para los atributos con respecto a Sunny es:

La ganancia de información para la humedad es más alta, por lo que se elige como el siguiente nodo. De manera similar, la entropía se calcula para Rain. El viento proporciona la mayor ganancia de información .

El árbol de decisiones se vería a continuación:

¿Qué es el modelado predictivo?

Los modelos de clasificación se pueden utilizar para predecir los resultados de un conjunto desconocido de atributos.

Cuando se introduce un conjunto de datos con etiquetas de clase desconocidas en el modelo, le asignará automáticamente la etiqueta de clase. Este método de aplicar la probabilidad para predecir resultados se denomina modelado predictivo.

Ventajas de la clasificación del árbol de decisiones

A continuación se enumeran los diversos méritos de la clasificación del árbol de decisiones:

1. La clasificación del árbol de decisiones no requiere ningún conocimiento de dominio, por lo tanto, es apropiada para el proceso de descubrimiento de conocimiento.
2. La representación de datos en forma de árbol es fácilmente comprensible para los humanos y es intuitiva.
3. Puede manejar datos multidimensionales.
4. Es un proceso rápido con gran precisión.

Desventajas de la clasificación del árbol de decisiones

A continuación se muestran los diversos deméritos de la clasificación del árbol de decisiones:

cómo inicializar una matriz genérica en java

1. A veces, los árboles de decisión se vuelven muy complejos y se denominan árboles sobreajustados.
2. Es posible que el algoritmo del árbol de decisiones no sea una solución óptima.
3. Los árboles de decisión pueden devolver una solución sesgada si alguna etiqueta de clase la domina.

Conclusión

Los árboles de decisión son técnicas de extracción de datos para el análisis de clasificación y regresión.

Esta técnica ahora se extiende a muchas áreas como diagnóstico médico, marketing objetivo, etc. Estos árboles se construyen siguiendo un algoritmo como ID3, CART. Estos algoritmos encuentran diferentes formas de dividir los datos en particiones.

Es la técnica de aprendizaje supervisado más conocida que se utiliza en el aprendizaje automático y el análisis de patrones. Los árboles de decisión predicen los valores de la variable objetivo mediante la construcción de modelos a través del aprendizaje del conjunto de capacitación proporcionado al sistema.

¡Esperamos que haya aprendido todo sobre Decision Tree Mining con este tutorial informativo!

PREV Tutorial | SIGUIENTE Tutorial

Lectura recomendada

• Ejemplos de minería de datos: aplicaciones más comunes de minería de datos 2021
• Técnicas de minería de datos: algoritmos, métodos y principales herramientas de minería de datos
• Minería de datos: procesos, técnicas y problemas principales en el análisis de datos
• Estructura de datos de árbol B y árbol B + en C ++
• Estructura de datos de árbol binario en C ++
• Proceso de minería de datos: modelos, pasos del proceso y desafíos involucrados
• Estructura de datos de montón y árbol AVL en C ++
• Minería de datos Vs Aprendizaje automático Vs Inteligencia artificial Vs Aprendizaje profundo