El árbol de decisiones de aprendizaje es un método basado en el uso de un árbol de decisiones como modelo predictivo. Se utiliza en particular en la minería de datos y en el aprendizaje automático .
En estas estructuras de árbol, las hojas representan los valores de la variable objetivo y las ramas corresponden a combinaciones de variables de entrada que conducen a estos valores. En el análisis de decisiones, se puede utilizar un árbol de decisiones para representar explícitamente las decisiones tomadas y los procesos que conducen a ellas. En el aprendizaje y la minería de datos, un árbol de decisiones describe los datos pero no las decisiones en sí, el árbol se utilizaría como punto de partida para el proceso de decisión.
Es una técnica de aprendizaje supervisado : utilizamos un conjunto de datos para los que conocemos el valor de la variable objetivo para construir el árbol (los llamados datos etiquetados), luego extrapolamos los resultados al conjunto de datos de prueba. Los árboles de decisión se encuentran entre los algoritmos más populares en el aprendizaje automático .
El aprendizaje del árbol de decisiones es un método clásico en el aprendizaje automático . Su propósito es crear un modelo que predice el valor de una variable objetivo a partir del valor de varias variables de entrada.
Una de las variables de entrada se selecciona en cada nodo interior (o nodo interno que no es terminal) del árbol de acuerdo con un método que depende del algoritmo y que se discutirá más adelante. Cada borde de un nodo secundario corresponde a un conjunto de valores de una variable de entrada, de modo que el conjunto de bordes de los nodos secundarios cubre todos los valores posibles de la variable de entrada.
Cada hoja (o nodo terminal del árbol) representa un valor de la variable objetivo o una distribución de probabilidad de los diversos valores posibles de la variable objetivo. La combinación de los valores de las variables de entrada está representada por la ruta desde la raíz hasta la hoja.
El árbol generalmente se construye separando el conjunto de datos en subconjuntos según el valor de una característica de entrada. Este proceso se repite en cada subconjunto obtenido de forma recursiva, por lo que es una partición recursiva.
La recursividad se completa en un nodo cuando todos los subconjuntos tienen el mismo valor de la característica de destino o cuando la separación ya no mejora la predicción. Este proceso se denomina inducción de árboles de decisión de arriba hacia abajo (TDIDT), es un algoritmo codicioso ya que buscamos en cada nodo del árbol el reparto óptimo, con el fin de obtener el mejor reparto posible en todo el árbol de decisión. Esta es la estrategia más común para aprender árboles de decisiones a partir de datos.
En la minería de datos, los árboles de decisión pueden ayudar en la descripción, categorización o generalización de un conjunto de datos fijo.
El conjunto de entrenamiento generalmente se proporciona en forma de registros del tipo:
La variable designa la variable objetivo que se busca predecir, clasificar o generalizar. El vector está formado por variables de entrada, etc. que se utilizan para este propósito.
Hay dos tipos principales de árboles de decisión en la minería de datos:
El término Análisis de árbol de clasificación y regresión ( CART , después del acrónimo) es un término genérico que hace referencia a los procedimientos previamente descritos e introducidos por Breiman et al.Los árboles utilizados en el caso de regresión y en el caso de clasificación presentan similitudes pero también diferencias , especialmente en lo que respecta al procedimiento utilizado para determinar las separaciones de ramas.
El aprendizaje del árbol de decisiones consiste en construir un árbol a partir de un conjunto de aprendizaje formado por tuplas etiquetadas. Un árbol de decisión se puede describir como un diagrama de flujo de datos (o diagrama de flujo ) donde cada nodo interno describe una prueba en una variable de aprendizaje, cada rama representa un resultado de prueba y cada hoja contiene el valor de la variable objetivo. (Una etiqueta de clase para árboles de clasificación, un valor numérico para árboles de regresión).
Por lo general, los algoritmos para construir los árboles de decisión se construyen dividiendo el árbol desde la parte superior hasta las hojas eligiendo en cada paso una variable de entrada que logra la mejor distribución del conjunto de objetos, como se describió anteriormente. Para elegir la variable de separación en un nodo, los algoritmos prueban las diferentes variables de entrada posibles y seleccionan la que maximiza un criterio dado.
Caso de árboles de clasificaciónEn el caso de los árboles de clasificación, este es un problema de clasificación automática . El criterio de evaluación de la partición caracteriza la homogeneidad (o la ganancia en homogeneidad) de los subconjuntos obtenidos por división del conjunto. Estas métricas se aplican a cada subconjunto candidato y los resultados se combinan (por ejemplo, promediados) para producir una medida de la calidad de la separación.
Existe una gran cantidad de tales criterios, los más utilizados son la entropía de Shannon , el índice de diversidad de Gini y sus variantes.
Caso de árboles de regresión
En el caso de los árboles de regresión , se puede aplicar el mismo esquema de separación, pero en lugar de minimizar la tasa de error de clasificación, buscamos maximizar la varianza entre clases (para tener subconjuntos cuyos valores de la variable objetivo estén tan dispersos como posible). En general, el criterio utiliza la prueba de chi-cuadrado .
ObservacionesCiertos criterios permiten tener en cuenta el hecho de que la variable objetivo toma valores ordenados, utilizando medidas o heurísticas adecuadas.
Cada conjunto de valores de la variable de segmentación produce un nodo hijo. Los algoritmos de aprendizaje pueden diferir en el número de nodos hijos producidos: algunos (como CART ) producen sistemáticamente árboles binarios y, por lo tanto, buscan la partición binaria que optimiza el criterio de segmentación. Otros (como CHAID ) buscan hacer las agrupaciones más relevantes en base a criterios estadísticos. Dependiendo de la técnica obtendremos árboles más o menos anchos. Para que el método sea eficaz, se debe tener cuidado de no dividir demasiado los datos para no producir grupos de personal demasiado reducidos, que no se corresponden con ninguna realidad estadística.
En el caso de las variables de segmentación continua, el criterio de segmentación elegido debe ser el adecuado. En general, los datos se ordenan según la variable a procesar, luego se prueban los diferentes puntos de corte posibles evaluando el criterio para cada caso, el punto de corte óptimo será el que maximice el criterio de segmentación.
En la práctica, no siempre es deseable construir un árbol cuyas hojas correspondan a subconjuntos perfectamente homogéneos desde el punto de vista de la variable objetivo. De hecho, la formación se realiza sobre una muestra que se espera sea representativa de una población. El desafío de cualquier técnica de aprendizaje es capturar información útil sobre la estructura estadística de la población, excluyendo las características específicas del conjunto de datos estudiado. Cuanto más complejo es el modelo (cuanto más alto es el árbol, más ramas tiene, más hojas tiene), más corremos el riesgo de que este modelo no se pueda extrapolar a nuevos datos. Es decir, dar cuenta. de la realidad que se busca aprehender.
En particular, en el caso extremo en el que el árbol tiene tantas hojas como individuos hay en la población (de registros en el conjunto de datos), el árbol no comete ningún error en esta muestra ya que combina todas sus características, pero no puede ser generalizado a otra muestra. Este problema, llamado sobreentrenamiento o rebasamiento ( overfitting ), es un tema clásico de aprendizaje automático y minería de datos.
Por lo tanto, buscamos construir un árbol lo más pequeño posible al tiempo que garantizamos el mejor rendimiento posible. Siguiendo el principio de parsimonia , cuanto más pequeño sea un árbol, más estable será en sus previsiones futuras. Es necesario hacer un compromiso entre rendimiento y complejidad en los modelos utilizados. Para un rendimiento comparable, siempre preferiremos el modelo más simple, si queremos poder utilizar este modelo en nuevas muestras.
El problema del sobreajuste de modelosPara realizar el arbitraje de rendimiento / complejidad de los modelos utilizados, el rendimiento de uno o más modelos se evalúa sobre los datos utilizados para su construcción (las muestras de entrenamiento), pero también sobre una (o más) muestras de validación. : datos etiquetados disponibles pero que voluntariamente se decide no utilizar en la construcción de los modelos.
Estos datos se tratan como los datos de prueba, la estabilidad del rendimiento de los modelos en estos dos tipos de muestra permitirá juzgar su sobreajuste y por lo tanto su capacidad para ser utilizados con un riesgo controlado de error en condiciones reales donde los datos no se conoce de antemano.
En el gráfico opuesto, observamos la evolución del error de ajuste de un árbol de decisión en función del número de hojas del árbol (que aquí mide la complejidad). Observamos que si el error disminuye constantemente en la muestra de aprendizaje, a partir de un cierto nivel de complejidad, el modelo se aleja de la realidad, una realidad que buscamos estimar en la muestra de validación (denominada muestra de prueba en el gráfico). .
En el caso de los árboles de decisión, se han considerado varios tipos de soluciones algorítmicas para intentar evitar en la medida de lo posible el sobreaprendizaje de los modelos: las técnicas de pre o post poda de árboles.
Algunas teorías estadísticas buscan encontrar el óptimo entre el error cometido en la muestra de entrenamiento y el cometido en la muestra de prueba. La teoría de Minimización de Riesgo Estructurado de Vapnik-Chervonenkis (o SRM), utiliza una variable llamada dimensión VC, para determinar el óptimo de un modelo. Por tanto, se puede utilizar para generar modelos que aseguren el mejor compromiso entre calidad y robustez del modelo.
Estas soluciones algorítmicas son complementarias a los análisis comparativos de rendimiento y estabilidad realizados en las muestras de entrenamiento y validación.
Poda previaLa primera estrategia que se puede utilizar para evitar el sobreaprendizaje de árboles de decisión consiste en proponer criterios de parada durante la fase de expansión. Este es el principio de la poda previa. Cuando el tamaño del grupo es demasiado pequeño, o cuando la homogeneidad de un subconjunto ha alcanzado un nivel suficiente, se considera que ya no es necesario separar la muestra. Otro criterio que se encuentra a menudo en este contexto es el uso de una prueba estadística para evaluar si la segmentación introduce una entrada significativa de información para la predicción de la variable objetivo.
Post-podaLa segunda estrategia consiste en construir el árbol en dos etapas: primero producimos el árbol cuyas hojas son lo más homogéneas posible en una fase de expansión, utilizando una primera fracción de la muestra de datos (muestra d 'aprendizaje que no debe confundirse con la totalidad de la muestra, llamada en inglés conjunto de cultivo para eliminar la ambigüedad), luego el árbol se reduce, confiando en otra fracción de los datos para optimizar el rendimiento del árbol es la fase posterior a la poda. Dependiendo del caso, esta segunda parte de los datos se designa con el término muestra de validación o muestra de prueba, lo que introduce confusión con la muestra utilizada para medir el desempeño de los modelos. El término muestra de poda se utiliza para designarlo sin ambigüedad, es la traducción directa del nombre conjunto de poda en inglés .
Los datos disponibles suelen estar incompletos, en el sentido de que solo una parte de las variables de entrada están disponibles para un registro. En este caso, son posibles varias posibilidades:
En el caso de árboles de clasificación, la regla de asignación debe especificarse en las hojas una vez construido el árbol. Si las hojas son homogéneas, no hay ambigüedad. De no ser así, una regla sencilla es decidir la clase de la hoja según la clase mayoritaria, la que está más representada.
Esta técnica muy simple es óptima en el caso de que los datos provengan de una selección aleatoria no sesgada en la población; la matriz de costos de asignación incorrecta es unitaria (simétrica): asignación adecuada a costo cero y asignación incorrecta de costos 1 independientemente del caso. Fuera de este marco, la regla de la mayoría no está necesariamente justificada, pero es fácil de usar en la práctica.
Algunas técnicas, llamadas métodos de conjuntos ( todos los métodos ), mejoran la calidad o confiabilidad de la predicción al construir varios árboles de decisión a partir de los datos:
Los árboles de decisión a veces se combinan entre sí o con otras técnicas de aprendizaje: análisis discriminante, regresiones logísticas, regresiones lineales, redes neuronales ( perceptrón multicapa , red de función de base radial ) u otras.
Se establecen procedimientos de agregación del desempeño de los diferentes modelos utilizados (como decisiones por consenso) para obtener el máximo rendimiento, controlando el nivel de complejidad de los modelos utilizados.
En comparación con otros métodos de minería de datos, los árboles de decisión tienen varias ventajas:
Por otro lado, tiene ciertos inconvenientes:
En un árbol de decisión, todas las rutas desde la raíz hasta las hojas utilizan el conector AND . En un gráfico de decisión, también podemos usar el conector OR para conectar múltiples rutas usando la Longitud mínima del mensaje (MML). En general, los gráficos de decisión producen gráficos con menos hojas que los árboles de decisión.
De los algoritmos evolutivos se utilizan para evitar la separación conduce al óptimo local.
También se puede muestrear el árbol utilizando métodos MCMC en un paradigma bayesiano .
El árbol se puede construir usando un enfoque de abajo hacia arriba (de abajo hacia arriba).
Hay varios algoritmos para construir árboles de decisión, que incluyen:
ID3 y CART se inventaron de forma independiente en las décadas 1970-1980, pero utilizan enfoques similares para aprender árboles de decisión del conjunto de aprendizaje.
Todos estos algoritmos se distinguen por los criterios de segmentación utilizados, por los métodos de poda implementados, por su forma de manejar los datos faltantes en los predictores.
Muchos software de minería de datos ofrecen bibliotecas para implementar uno o más algoritmos de aprendizaje de árboles de decisión. Por ejemplo, el software Open Source R contiene varias implementaciones de CART, como rpart, party y randomForest, el software gratuito Weka y Orange (y su módulo orngTree) o la biblioteca gratuita de Python scikit-learn ; pero también Salford Systems CART, IBM SPSS Modeler, RapidMiner, SAS Enterprise Miner, KNIME, Microsoft SQL Server [1] .