Los bosques aleatorios o bosques de decisión aleatoria son un método de aprendizaje conjunto para clasificación , regresión y otras tareas que opera mediante la construcción de una multitud de árboles de decisión en el momento del entrenamiento. Para las tareas de clasificación, la salida del bosque aleatorio es la clase seleccionada por la mayoría de los árboles. Para tareas de regresión, se devuelve la predicción media o promedio de los árboles individuales. [1] [2] Los bosques de decisiones aleatorias corrigen el hábito de los árboles de decisión de sobreadaptarse a su conjunto de entrenamiento . [3] : 587–588
El primer algoritmo para bosques de decisión aleatoria fue creado en 1995 por Tin Kam Ho [1] utilizando el método del subespacio aleatorio , [2] que, en la formulación de Ho, es una forma de implementar el enfoque de clasificación de "discriminación estocástica" propuesto por Eugene Kleinberg. . [4] [5] [6]
Leo Breiman [7] y Adele Cutler , [8] desarrollaron una extensión del algoritmo , quienes registraron [9] "Random Forests" como marca comercial en 2006 (a partir de 2019 [update], propiedad de Minitab, Inc. ). [10] La extensión combina la idea de " embolsado " de Breiman y la selección aleatoria de características, introducida primero por Ho [1] y luego de forma independiente por Amit y Geman [11] para construir una colección de árboles de decisión con varianza controlada.
El método general de bosques de decisión aleatoria fue propuesto por primera vez por Ho en 1995. [1] Ho estableció que los bosques de árboles que se dividen con hiperplanos oblicuos pueden ganar precisión a medida que crecen sin sufrir sobreentrenamiento, siempre y cuando los bosques estén restringidos aleatoriamente para ser sensibles. solo a dimensiones de entidades seleccionadas . Un trabajo posterior en la misma línea [2] concluyó que otros métodos de división se comportan de manera similar, siempre que se les obligue aleatoriamente a ser insensibles a algunas dimensiones de características. Tenga en cuenta que esta observación de un clasificador más complejo (un bosque más grande) que se vuelve más preciso de manera casi monótona contrasta fuertemente con la creencia común de que la complejidad de un clasificador solo puede crecer hasta un cierto nivel de precisión antes de verse perjudicada por el sobreajuste. La explicación de la resistencia del método forestal al sobreentrenamiento se puede encontrar en la teoría de la discriminación estocástica de Kleinberg. [4] [5] [6]
El desarrollo inicial de la noción de bosques aleatorios de Breiman estuvo influenciado por el trabajo de Amit y Geman [11] , quienes introdujeron la idea de buscar en un subconjunto aleatorio de las decisiones disponibles al dividir un nodo, en el contexto del crecimiento de un solo árbol . La idea de selección aleatoria de subespacios de Ho [2] también influyó en el diseño de bosques aleatorios. En este método se cultiva un bosque de árboles y se introduce variación entre los árboles proyectando los datos de entrenamiento en un subespacio elegido al azar antes de ajustar cada árbol o cada nodo. Finalmente, Thomas G. Dietterich introdujo por primera vez la idea de optimización de nodos aleatorios, donde la decisión en cada nodo se selecciona mediante un procedimiento aleatorio, en lugar de una optimización determinista . [12]
La introducción adecuada de bosques aleatorios se realizó en un artículo de Leo Breiman . [7] Este artículo describe un método para construir un bosque de árboles no correlacionados utilizando un procedimiento similar a CART , combinado con optimización de nodos aleatorios y embolsado . Además, este artículo combina varios ingredientes, algunos previamente conocidos y otros novedosos, que forman la base de la práctica moderna de los bosques aleatorios, en particular:
El informe también ofrece el primer resultado teórico para bosques aleatorios en forma de un límite en el error de generalización que depende de la fuerza de los árboles en el bosque y su correlación .
Los árboles de decisión son un método popular para diversas tareas de aprendizaje automático. El aprendizaje de árboles "es lo que más se acerca a cumplir los requisitos para servir como un procedimiento estándar para la extracción de datos", dicen Hastie et al. , "porque es invariante bajo escala y varias otras transformaciones de valores de características, es resistente a la inclusión de características irrelevantes y produce modelos inspeccionables. Sin embargo, rara vez son precisos". [3] : 352
En particular, los árboles que crecen a mucha profundidad tienden a aprender patrones muy irregulares: se adaptan demasiado a sus conjuntos de entrenamiento, es decir, tienen un sesgo bajo, pero una varianza muy alta . Los bosques aleatorios son una forma de promediar múltiples árboles de decisión profundos, entrenados en diferentes partes del mismo conjunto de entrenamiento, con el objetivo de reducir la varianza. [3] : 587–588 Esto se produce a expensas de un pequeño aumento en el sesgo y cierta pérdida de interpretabilidad, pero en general aumenta en gran medida el rendimiento en el modelo final.
El algoritmo de entrenamiento para bosques aleatorios aplica la técnica general de agregación bootstrap , o embolsado, a los estudiantes de árboles. Dado un conjunto de entrenamiento X = x 1 , ..., x n con respuestas Y = y 1 , ..., y n , embolsar repetidamente ( B veces) selecciona una muestra aleatoria con reemplazo del conjunto de entrenamiento y ajusta los árboles a estos muestras:
Después del entrenamiento, se pueden hacer predicciones para muestras no vistas x' promediando las predicciones de todos los árboles de regresión individuales en x' :
o mediante votación plural en el caso de árboles de clasificación.
Este procedimiento de arranque conduce a un mejor rendimiento del modelo porque disminuye la varianza del modelo, sin aumentar el sesgo. Esto significa que, si bien las predicciones de un solo árbol son muy sensibles al ruido en su conjunto de entrenamiento, el promedio de muchos árboles no lo es, siempre que los árboles no estén correlacionados. Simplemente entrenar muchos árboles en un único conjunto de entrenamiento daría árboles fuertemente correlacionados (o incluso el mismo árbol muchas veces, si el algoritmo de entrenamiento es determinista); El muestreo bootstrap es una forma de descorrelacionar los árboles mostrándoles diferentes conjuntos de entrenamiento.
Además, se puede hacer una estimación de la incertidumbre de la predicción como la desviación estándar de las predicciones de todos los árboles de regresión individuales en x' :
El número de muestras/árboles, B , es un parámetro libre. Normalmente, se utilizan entre unos cientos y varios miles de árboles, según el tamaño y la naturaleza del conjunto de entrenamiento. Se puede encontrar un número óptimo de árboles B mediante validación cruzada o observando el error fuera de la bolsa : el error de predicción medio en cada muestra de entrenamiento xi , utilizando solo los árboles que no tenían xi en su muestra de arranque . . [13] El error de entrenamiento y prueba tiende a estabilizarse después de que se haya adaptado una cierta cantidad de árboles.
El procedimiento anterior describe el algoritmo de embolsado original para árboles. Los bosques aleatorios también incluyen otro tipo de esquema de embolsado: utilizan un algoritmo de aprendizaje de árbol modificado que selecciona, en cada división candidata en el proceso de aprendizaje, un subconjunto aleatorio de características . Este proceso a veces se denomina "embolsado de funciones". La razón para hacer esto es la correlación de los árboles en una muestra de arranque ordinaria: si una o varias características son predictores muy sólidos para la variable de respuesta (salida objetivo), estas características se seleccionarán en muchos de los árboles B , lo que provocará que para correlacionarse. Ho ofrece un análisis de cómo el ensacado y la proyección subespacial aleatoria contribuyen a mejorar la precisión en diferentes condiciones. [14]
Normalmente, para un problema de clasificación con p características, se utilizan características √ p (redondeadas hacia abajo) en cada división. [3] : 592 Para problemas de regresión, los inventores recomiendan p/3 (redondeado hacia abajo) con un tamaño de nodo mínimo de 5 como valor predeterminado. [3] : 592 En la práctica, los mejores valores para estos parámetros deben ajustarse caso por caso para cada problema. [3] : 592
Agregar un paso más de aleatorización produce árboles extremadamente aleatorios , o ExtraTrees. Si bien son similares a los bosques aleatorios ordinarios en el sentido de que son un conjunto de árboles individuales, existen dos diferencias principales: en primer lugar, cada árbol se entrena utilizando la muestra de aprendizaje completa (en lugar de una muestra de arranque) y, en segundo lugar, la división de arriba hacia abajo en el alumno del árbol es aleatorio. En lugar de calcular el punto de corte localmente óptimo para cada característica considerada (basándose, por ejemplo, en la ganancia de información o la impureza de Gini ), se selecciona un punto de corte aleatorio . Este valor se selecciona de una distribución uniforme dentro del rango empírico de la característica (en el conjunto de entrenamiento del árbol). Luego, de todas las divisiones generadas aleatoriamente, se elige la división que produce la puntuación más alta para dividir el nodo. De manera similar a los bosques aleatorios ordinarios, se puede especificar el número de características seleccionadas aleatoriamente que se considerarán en cada nodo. Los valores predeterminados para este parámetro son para clasificación y regresión, donde es el número de características en el modelo. [15]
Es posible que el procedimiento básico de Random Forest no funcione bien en situaciones en las que hay una gran cantidad de características pero solo una pequeña proporción de estas características son informativas con respecto a la clasificación de la muestra. Esto se puede solucionar fomentando que el procedimiento se centre principalmente en características y árboles que sean informativos. Algunos métodos para lograr esto son:
- Prefiltrado: elimina funciones que en su mayoría son solo ruido. [16] [17]
- Bosque aleatorio enriquecido (ERF): utilice muestreo aleatorio ponderado en lugar de muestreo aleatorio simple en cada nodo de cada árbol, dando mayor peso a las características que parecen ser más informativas.[18] [19]
- Bosque aleatorio ponderado por árboles (TWRF): pondera los árboles para que a los que muestran una mayor precisión se les asignen pesos más altos.[20] [21]
Los bosques aleatorios se pueden utilizar para clasificar la importancia de las variables en un problema de regresión o clasificación de forma natural. La siguiente técnica se describió en el artículo original de Breiman [7] y se implementa en el paquete R randomForest . [8]
El primer paso para medir la importancia de la variable en un conjunto de datos es ajustar un bosque aleatorio a los datos. Durante el proceso de ajuste, el error de salida de la bolsa para cada punto de datos se registra y se promedia en todo el bosque (los errores en un conjunto de prueba independiente se pueden sustituir si no se utiliza la bolsa durante el entrenamiento).
Para medir la importancia de la característica -ésima después del entrenamiento, los valores de la característica -ésima se permutan en las muestras fuera de bolsa y el error fuera de bolsa se calcula nuevamente en este conjunto de datos perturbados. La puntuación de importancia para la característica -ésima se calcula promediando la diferencia en el error fuera de la bolsa antes y después de la permutación en todos los árboles. La puntuación se normaliza por la desviación estándar de estas diferencias.
Las características que producen valores grandes para esta puntuación se clasifican como más importantes que las características que producen valores pequeños. La definición estadística de la medida de importancia de la variable fue dada y analizada por Zhu et al. [22]
Este método de determinar la importancia de la variable tiene algunos inconvenientes.
Esta característica importante para los bosques aleatorios es la implementación predeterminada en sci-kit learn y R. Se describe en el libro "Árboles de clasificación y regresión" de Leo Breiman. [30] Las variables que disminuyen mucho la impureza durante las divisiones se consideran importantes: [31]
donde indica una característica, es la cantidad de árboles en el bosque, indica árbol , es la fracción de muestras que llegan al nodo , es el cambio en la impureza en el árbol en el nodo . Como medida de impureza para muestras que caen en un nodo, se pueden utilizar, por ejemplo, las siguientes estadísticas:
La importancia normalizada se obtiene luego normalizando todas las características, de modo que la suma de las importancias de las características normalizadas sea 1.
La implementación predeterminada de aprendizaje del kit de ciencia de la disminución media de la importancia de las características de impurezas es susceptible a importancias de características engañosas: [29]
Lin y Jeon señalaron una relación entre los bosques aleatorios y el algoritmo k- vecino más cercano ( k -NN) en 2002. [33] Resulta que ambos pueden verse como los llamados esquemas de vecindades ponderadas . Estos son modelos construidos a partir de un conjunto de entrenamiento que hace predicciones para nuevos puntos x' observando la "vecindad" del punto, formalizada por una función de peso W :
Aquí, está el peso no negativo del i 'ésimo punto de entrenamiento en relación con el nuevo punto x' en el mismo árbol. Para cualquier x' particular , los pesos de los puntos deben sumar uno. Las funciones de peso se dan de la siguiente manera:
Dado que un bosque promedia las predicciones de un conjunto de m árboles con funciones de peso individuales , sus predicciones son
Esto muestra que todo el bosque es nuevamente un esquema de vecindad ponderado, con pesos que promedian los de los árboles individuales. Los vecinos de x' en esta interpretación son los puntos que comparten la misma hoja en cualquier árbol . De esta manera, la vecindad de x' depende de forma compleja de la estructura de los árboles y, por tanto, de la estructura del conjunto de entrenamiento. Lin y Jeon muestran que la forma del vecindario utilizado por un bosque aleatorio se adapta a la importancia local de cada característica. [33]
Como parte de su construcción, los predictores forestales aleatorios naturalmente conducen a una medida de disimilitud entre las observaciones. También se puede definir una medida de disimilitud de bosque aleatoria entre datos no etiquetados: la idea es construir un predictor de bosque aleatorio que distinga los datos "observados" de los datos sintéticos generados adecuadamente. [7] [34] Los datos observados son los datos originales sin etiquetar y los datos sintéticos se extraen de una distribución de referencia. Una disimilitud de bosque aleatoria puede ser atractiva porque maneja muy bien tipos de variables mixtas, es invariante a transformaciones monótonas de las variables de entrada y es robusta a observaciones periféricas. La disimilitud aleatoria del bosque maneja fácilmente una gran cantidad de variables semicontinuas debido a su selección de variables intrínsecas; por ejemplo, la disimilitud del bosque aleatorio "Addcl 1" pesa la contribución de cada variable según su dependencia de otras variables. La disimilitud del bosque aleatorio se ha utilizado en una variedad de aplicaciones, por ejemplo, para encontrar grupos de pacientes basándose en datos de marcadores tisulares. [35]
En lugar de árboles de decisión, se han propuesto y evaluado modelos lineales como estimadores base en bosques aleatorios, en particular la regresión logística multinomial y los clasificadores ingenuos de Bayes . [36] [37] [38] En los casos en que la relación entre los predictores y la variable objetivo es lineal, los alumnos base pueden tener una precisión igualmente alta que el alumno conjunto. [39] [36]
En el aprendizaje automático, los bosques aleatorios del kernel (KeRF) establecen la conexión entre los bosques aleatorios y los métodos del kernel . Modificando ligeramente su definición, los bosques aleatorios se pueden reescribir como métodos del núcleo , que son más interpretables y fáciles de analizar. [40]
Leo Breiman [41] fue la primera persona en notar el vínculo entre los métodos de bosque aleatorio y kernel . Señaló que los bosques aleatorios que se cultivan utilizando vectores aleatorios iid en la construcción del árbol son equivalentes a un núcleo que actúa en el margen real. Lin y Jeon [42] establecieron la conexión entre los bosques aleatorios y el vecino más cercano adaptativo, lo que implica que los bosques aleatorios pueden verse como estimaciones de núcleo adaptativo. Davies y Ghahramani [43] propusieron Random Forest Kernel y demostraron que empíricamente puede superar a los métodos de kernel más modernos. Scornet [40] fue el primero en definir las estimaciones de KeRF y proporcionó el vínculo explícito entre las estimaciones de KeRF y el bosque aleatorio. También dio expresiones explícitas para núcleos basadas en bosque aleatorio centrado [44] y bosque aleatorio uniforme, [45] dos modelos simplificados de bosque aleatorio. Llamó a estos dos KeRF KeRF centrado y KeRF uniforme, y demostró límites superiores en sus tasas de consistencia.
El bosque centrado [44] es un modelo simplificado para el bosque aleatorio original de Breiman, que selecciona uniformemente un atributo entre todos los atributos y realiza divisiones en el centro de la celda a lo largo del atributo preseleccionado. El algoritmo se detiene cuando se construye un árbol de niveles completamente binario , donde es un parámetro del algoritmo.
El bosque uniforme [45] es otro modelo simplificado para el bosque aleatorio original de Breiman, que selecciona uniformemente una característica entre todas las características y realiza divisiones en un punto dibujado uniformemente en el costado de la celda, a lo largo de la característica preseleccionada.
Dada una muestra de entrenamiento de variables aleatorias independientes valoradas distribuidas como el par de prototipos independientes , donde . Nuestro objetivo es predecir la respuesta asociada a la variable aleatoria mediante la estimación de la función de regresión . Un bosque de regresión aleatoria es un conjunto de árboles de regresión aleatoria. Denote el valor predicho en el punto del árbol -ésimo, donde están las variables aleatorias independientes, distribuidas como una variable aleatoria genérica , independiente de la muestra . Esta variable aleatoria se puede utilizar para describir la aleatoriedad inducida por la división de nodos y el procedimiento de muestreo para la construcción de árboles. Los árboles se combinan para formar la estimación forestal finita . Para los árboles de regresión, tenemos dónde está la celda que contiene , diseñada con aleatoriedad y conjunto de datos , y .
Por tanto, las estimaciones forestales aleatorias satisfacen, para todos , . El bosque de regresión aleatoria tiene dos niveles de promedio, primero sobre las muestras en la celda objetivo de un árbol y luego sobre todos los árboles. Por tanto, las contribuciones de las observaciones que se encuentran en celdas con una alta densidad de puntos de datos son menores que las de las observaciones que pertenecen a celdas menos pobladas. Para mejorar los métodos forestales aleatorios y compensar la estimación errónea, Scornet [40] definió KeRF por
que es igual a la media de la caída de las celdas que contienen el bosque. Si definimos la función de conexión del bosque finito como , es decir, la proporción de celdas compartidas entre y , entonces casi seguramente tenemos , que define el KeRF.
La construcción de KeRF centrado de nivel es la misma que para el bosque centrado, excepto que las predicciones las realiza , la función del núcleo correspondiente o la función de conexión es
KeRF uniforme se construye de la misma manera que el bosque uniforme, excepto que las predicciones se realizan mediante , la función del núcleo correspondiente o la función de conexión.
Las predicciones dadas por KeRF y bosques aleatorios son cercanas si se controla el número de puntos en cada celda:
Supongamos que existen secuencias tales que, casi con seguridad,
Entonces casi seguramente,
Cuando el número de árboles llega al infinito, entonces tenemos un bosque aleatorio infinito y un KeRF infinito. Sus estimaciones son cercanas si el número de observaciones en cada celda está acotado:
Supongamos que existen secuencias tales que, casi con seguridad
Entonces casi seguramente,
Supongamos que , donde es un ruido gaussiano centrado, independiente de , con varianza finita . Además, se distribuye uniformemente en Lipschitz y es . Scornet [40] demostró límites superiores en las tasas de consistencia para KeRF centrado y KeRF uniforme.
Proporcionando y , existe una constante tal que, para todos , .
Proporcionando y , existe una constante tal que ,.
Si bien los bosques aleatorios a menudo logran una mayor precisión que un único árbol de decisión, sacrifican la interpretabilidad intrínseca presente en los árboles de decisión. Los árboles de decisión pertenecen a una familia bastante pequeña de modelos de aprendizaje automático que son fácilmente interpretables junto con los modelos lineales, los modelos basados en reglas y los modelos basados en la atención . Esta interpretabilidad es una de las cualidades más deseables de los árboles de decisión. Permite a los desarrolladores confirmar que el modelo ha aprendido información realista de los datos y permite a los usuarios finales tener confianza en las decisiones tomadas por el modelo. [36] [3] Por ejemplo, seguir el camino que sigue un árbol de decisión para tomar su decisión es bastante trivial, pero seguir los caminos de decenas o cientos de árboles es mucho más difícil. Para lograr tanto rendimiento como interpretabilidad, algunas técnicas de compresión de modelos permiten transformar un bosque aleatorio en un árbol de decisión mínimo "renacido" que reproduce fielmente la misma función de decisión. [36] [46] [47] Si se establece que los atributos predictivos están correlacionados linealmente con la variable objetivo, el uso de bosque aleatorio puede no mejorar la precisión del alumno base. [36] [39] Además, en problemas con múltiples variables categóricas, es posible que el bosque aleatorio no pueda aumentar la precisión del alumno base. [48]
{{cite journal}}
: Citar diario requiere |journal=
( ayuda )