Bosque aleatorio

Método de aprendizaje automático por conjuntos basado en árboles

Los bosques aleatorios o bosques de decisión aleatorios son un método de aprendizaje conjunto para tareas de clasificación , regresión y otras tareas que funciona creando una multitud de árboles de decisión durante el entrenamiento. Para las tareas de clasificación, la salida del bosque aleatorio es la clase seleccionada por la mayoría de los árboles. Para las tareas de regresión, la salida es el promedio de las predicciones de los árboles. ^{[1] [2]} Los bosques aleatorios corrigen el hábito de los árboles de decisión de sobreajustarse a su conjunto de entrenamiento . ^{[3] : 587–588}

El primer algoritmo para bosques de decisión aleatorios fue creado en 1995 por Tin Kam Ho ^[1] utilizando el método de subespacio aleatorio , ^[2] que, en la formulación de Ho, es una forma de implementar el enfoque de "discriminación estocástica" para la clasificación propuesto por Eugene Kleinberg. ^{[4] [5] [6]}

Una extensión del algoritmo fue desarrollada por Leo Breiman ^[7] y Adele Cutler ^[8] , quienes registraron ^[9] "Random Forests" como marca registrada en 2006 (a partir de 2019 ^[update], propiedad de Minitab, Inc. ). ^[10] La extensión combina la idea de " bagging " de Breiman y la selección aleatoria de características, introducidas 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.

Historia

El método general de los bosques de decisión aleatorios fue propuesto por primera vez por Salzberg y Heath en 1993 ^[12] , con un método que utilizaba un algoritmo de árbol de decisión aleatorio para crear múltiples árboles y luego combinarlos mediante votación por mayoría. Esta idea fue desarrollada más a fondo 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 que los bosques se restrinjan aleatoriamente para que sean sensibles solo a dimensiones de características 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 los fuerce aleatoriamente a ser insensibles a algunas dimensiones de características. Esta observación de que un clasificador más complejo (un bosque más grande) se vuelve más preciso casi monótonamente contrasta marcadamente 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 afectada por el sobreajuste. La explicación de la resistencia del método de bosque al sobreentrenamiento se puede encontrar en la teoría de discriminación estocástica de Kleinberg ^{[4] [5] [6]}

El desarrollo temprano 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. Este método hace crecer un bosque de árboles e introduce variación entre los árboles proyectando los datos de entrenamiento en un subespacio elegido aleatoriamente antes de ajustar cada árbol o cada nodo. Finalmente, la idea de optimización aleatoria de nodos, donde la decisión en cada nodo se selecciona mediante un procedimiento aleatorio, en lugar de una optimización determinista, fue introducida por primera vez por Thomas G. Dietterich . ^[13]

La introducción adecuada de los 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 bagging . Además, este artículo combina varios ingredientes, algunos ya conocidos y otros novedosos, que forman la base de la práctica moderna de los bosques aleatorios, en particular:

1. Utilizando el error fuera de la bolsa como estimación del error de generalización .
2. Medición de la importancia de las variables mediante permutación.

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 .

Algoritmo

Preliminares: aprendizaje del árbol de decisiones

Los árboles de decisión son un método popular para diversas tareas de aprendizaje automático. El aprendizaje de árboles es casi "un procedimiento estándar para la minería de datos", afirman Hastie et al. , "porque es invariable ante el escalamiento y otras transformaciones de valores de características, es robusto ante 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 muy profundamente tienden a aprender patrones altamente irregulares: sobreajustan 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 generalmente aumenta en gran medida el rendimiento en el modelo final.

Harpillera

Ilustración del entrenamiento de un modelo de Bosque aleatorio. El conjunto de datos de entrenamiento (en este caso, de 250 filas y 100 columnas) se muestrea aleatoriamente con reemplazo n veces. Luego, se entrena un árbol de decisión en cada muestra. Finalmente, para la predicción, se agregan los resultados de todos los n árboles para producir una decisión final.

El algoritmo de entrenamiento para bosques aleatorios aplica la técnica general de agregación bootstrap , o bagging, a los árboles que aprenden. Dado un conjunto de entrenamiento X = x ₁ , ..., x _n con respuestas Y = y ₁ , ..., y _n , bagging repetidamente ( B veces) selecciona una muestra aleatoria con reemplazo del conjunto de entrenamiento y ajusta los árboles a estas muestras:

Para b = 1, ..., B :

1. Muestra, con reemplazo, n ejemplos de entrenamiento de X , Y ; llamémoslos X _b , Y _b .
2. Entrenar un árbol de clasificación o regresión f _b en X _b , Y _b .

Después del entrenamiento, se pueden realizar predicciones para muestras no vistas x' promediando las predicciones de todos los árboles de regresión individuales en x' :

$${\displaystyle {\hat {f}}={\frac {1}{B}}\sum _{b=1}^{B}f_{b}(x')}$$

o mediante el voto de pluralidad en el caso de árboles de clasificación.

Este procedimiento de bootstrap mejora el 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. El simple hecho de entrenar muchos árboles en un solo conjunto de entrenamiento daría como resultado á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 al mostrarles diferentes conjuntos de entrenamiento.

Además, se puede realizar 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′ : $${\displaystyle \sigma ={\sqrt {\frac {\sum _{b=1}^{B}(f_{b}(x')-{\hat {f}})^{2}}{B-1}}}.}$$

El número B de muestras (equivalentemente, de árboles) es un parámetro libre. Normalmente, se utilizan unos pocos cientos a varios miles de árboles, según el tamaño y la naturaleza del conjunto de entrenamiento. B se puede optimizar utilizando validación cruzada o observando el error out-of-bag : el error de predicción medio en cada muestra de entrenamiento x _i , utilizando solo los árboles que no tenían x _i en su muestra de arranque. ^[14]

Los errores de entrenamiento y prueba tienden a estabilizarse después de que se hayan ajustado una cierta cantidad de árboles.

Del embolsado a los bosques aleatorios

El procedimiento anterior describe el algoritmo de bagging original para árboles. Los bosques aleatorios también incluyen otro tipo de esquema de bagging: utilizan un algoritmo de aprendizaje de árboles modificado que selecciona, en cada división de candidatos en el proceso de aprendizaje, un subconjunto aleatorio de las características . Este proceso a veces se denomina "bagging de características". La razón para hacer esto es la correlación de los árboles en una muestra de bootstrap ordinaria: si una o algunas características son predictores muy fuertes para la variable de respuesta (salida objetivo), estas características se seleccionarán en muchos de los árboles B , lo que hará que se correlacionen. Ho ofrece un análisis de cómo el bagging y la proyección de subespacios aleatorios contribuyen a las ganancias de precisión en diferentes condiciones. ^[15]

Por lo general, para un problema de clasificación con características p , se utilizan √ p ^{(redondeado hacia abajo) características 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 se deben ajustar caso por caso para cada problema. ^{[3] : 592}

Árboles adicionales

Si se añade un paso más de aleatorización se obtienen árboles extremadamente aleatorios o ExtraTrees. Al igual que los bosques aleatorios ordinarios, son un conjunto de árboles individuales, pero hay dos diferencias principales: (1) cada árbol se entrena utilizando toda la muestra de aprendizaje (en lugar de una muestra de arranque) y (2) la división de arriba hacia abajo es aleatoria: para cada característica en consideración, se seleccionan varios puntos de corte aleatorios , en lugar de calcular el punto de corte localmente óptimo (basado, por ejemplo, en la ganancia de información o la impureza de Gini ). Los valores se eligen 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 elegidas 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 comunes, se puede especificar la cantidad de características seleccionadas aleatoriamente que se considerarán en cada nodo. Los valores predeterminados para este parámetro son para la clasificación y para la regresión, donde es la cantidad de características en el modelo. ^[16] ${\displaystyle {\sqrt {p}}}$ ${\displaystyle p}$ ${\displaystyle p}$

Bosques aleatorios para datos de alta dimensión

El procedimiento básico de bosque aleatorio puede no funcionar 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 las características y los árboles que son informativos. Algunos métodos para lograr esto son:

• Prefiltrado: eliminar características que en su mayoría son solo ruido. ^{[17] [18]}
• Bosque aleatorio enriquecido (ERF): utiliza un muestreo aleatorio ponderado en lugar de un muestreo aleatorio simple en cada nodo de cada árbol, dando mayor peso a las características que parecen ser más informativas. ^{[19] [20]}
• Bosque aleatorio ponderado por árboles (TWRF): otorga más peso a los árboles más precisos. ^{[21] [22]}

Propiedades

Importancia variable

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. ^[8]randomForest

Importancia de la permutación

Para medir la importancia de una característica en un conjunto de datos , primero se entrena un bosque aleatorio con los datos. Durante el entrenamiento, se registra el error out-of-bag para cada punto de datos y se promedia en el bosque. (Si no se utiliza bagging durante el entrenamiento, podemos calcular los errores en un conjunto de prueba independiente). ${\displaystyle {\mathcal {D}}_{n}=\{(X_{i},Y_{i})\}_{i=1}^{n}}$

Después del entrenamiento, los valores de la característica se permutan en las muestras fuera de la bolsa y el error fuera de la bolsa se calcula nuevamente en este conjunto de datos perturbado. La importancia de la característica 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 altos para esta puntuación se clasifican como más importantes que las características que producen valores bajos. La definición estadística de la medida de importancia variable fue proporcionada y analizada por Zhu et al. ^[23].

Este método para determinar la importancia de las variables tiene algunas desventajas:

• Cuando las características tienen diferentes cantidades de valores, los bosques aleatorios favorecen las características con más valores. Las soluciones a este problema incluyen permutaciones parciales ^{[24] [25] [26]} y árboles de crecimiento imparcial. ^{[27] [28]}
• Si los datos contienen grupos de características correlacionadas de relevancia similar, entonces se favorecen los grupos más pequeños sobre los grupos grandes. ^[29]
• Si existen características colineales, el procedimiento puede no identificar características importantes. Una solución es permutar grupos de características correlacionadas. ^[30]

Disminución media de la importancia de las características de impureza

Este enfoque de la importancia de las características para bosques aleatorios considera importantes las variables que reducen mucho la impureza durante la división. ^[31] Se describe en el libro Classification and Regression Trees de Leo Breiman ^[32] y es la implementación predeterminada en sci-kit learny R. La definición es: donde $${\displaystyle {\text{unormalized average importance}}(x)={\frac {1}{n_{T}}}\sum _{i=1}^{n_{T}}\sum _{{\text{node }}j\in T_{i}|{\text{split variable}}(j)=x}p_{T_{i}}(j)\Delta i_{T_{i}}(j),}$$

• ${\displaystyle x}$es una característica
• ${\displaystyle n_{T}}$es el número de árboles en el bosque
• ${\displaystyle T_{i}}$es arbol ${\displaystyle i}$
• ${\displaystyle p_{T_{i}}(j)={\frac {n_{j}}{n}}}$es la fracción de muestras que llegan al nodo ${\displaystyle j}$
• ${\displaystyle \Delta i_{T_{i}}(j)}$es el cambio de impureza en el árbol en el nodo . ${\displaystyle t}$ ${\displaystyle j}$

Como medida de impurezas para las muestras que caen en un nodo, por ejemplo, se pueden utilizar las siguientes estadísticas:

• Entropía
• Coeficiente de Gini
• Error cuadrático medio

La importancia normalizada se obtiene entonces normalizando todas las características, de modo que la suma de las importancias de las características normalizadas sea 1.

La sci-kit learnimplementación predeterminada puede informar una importancia de características engañosa: ^[30]

• Favorece características de alta cardinalidad.
• Utiliza estadísticas de entrenamiento y, por lo tanto, no refleja la utilidad de una característica para realizar predicciones en un conjunto de pruebas ^[33]

Relación con los vecinos más cercanos

En 2002, Lin y Jeon señalaron una relación entre los bosques aleatorios y el algoritmo del k -vecino más cercano ( k -NN) ^{. [34]} Ambos pueden considerarse como los denominados esquemas de vecindad ponderada . Se trata de modelos construidos a partir de un conjunto de entrenamiento que realizan predicciones para los nuevos puntos x' observando la "vecindad" del punto, formalizada por una función de peso W : Aquí, es 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' , los pesos de los puntos deben sumar 1. Las funciones de peso son las siguientes: ${\displaystyle \{(x_{i},y_{i})\}_{i=1}^{n}}$ ${\displaystyle {\hat {y}}}$ $${\displaystyle {\hat {y}}=\sum _{i=1}^{n}W(x_{i},x')\,y_{i}.}$$ ${\displaystyle W(x_{i},x')}$ ${\displaystyle x_{i}}$

• En k -NN, si x _i es uno de los k puntos más cercanos a x' , y cero en caso contrario. ${\displaystyle W(x_{i},x')={\frac {1}{k}}}$
• En un árbol, si x _i es uno de los k' puntos en la misma hoja que x' , y cero en caso contrario. ${\displaystyle W(x_{i},x')={\frac {1}{k'}}}$

Dado que un bosque promedia las predicciones de un conjunto de m árboles con funciones de peso individuales , sus predicciones son ${\displaystyle W_{j}}$ $${\displaystyle {\hat {y}}={\frac {1}{m}}\sum _{j=1}^{m}\sum _{i=1}^{n}W_{j}(x_{i},x')\,y_{i}=\sum _{i=1}^{n}\left({\frac {1}{m}}\sum _{j=1}^{m}W_{j}(x_{i},x')\right)\,y_{i}.}$$

Esto demuestra que todo el bosque es nuevamente un esquema de vecindad ponderada, con ponderaciones que promedian las 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 una manera compleja de la estructura de los árboles y, por lo tanto, de la estructura del conjunto de entrenamiento. Lin y Jeon muestran que la forma de la vecindad utilizada por un bosque aleatorio se adapta a la importancia local de cada característica. ^[34] ${\displaystyle x_{i}}$ ${\displaystyle j}$

Aprendizaje no supervisado

Como parte de su construcción, los predictores de bosque aleatorio conducen naturalmente a una medida de disimilitud entre las observaciones. Se puede definir de forma análoga la disimilitud entre datos no etiquetados, entrenando un bosque para distinguir los datos "observados" originales de los datos sintéticos generados adecuadamente extraídos de una distribución de referencia. ^{[7] [35]} Una disimilitud de bosque aleatorio es atractiva porque maneja muy bien los tipos de variables mixtas, es invariante a las transformaciones monótonas de las variables de entrada y es robusta a las observaciones atípicas. La disimilitud de bosque aleatorio se ocupa fácilmente de una gran cantidad de variables semicontinuas debido a su selección de variables intrínseca; por ejemplo, la disimilitud de bosque aleatorio "Addcl 1" pondera la contribución de cada variable según su dependencia de otras variables. La disimilitud de bosque aleatorio se ha utilizado en una variedad de aplicaciones, por ejemplo, para encontrar grupos de pacientes basados ​​en datos de marcadores de tejido. ^[36]

Variantes

En lugar de árboles de decisión, se han propuesto y evaluado modelos lineales como estimadores base en bosques aleatorios, en particular regresión logística multinomial y clasificadores Bayes ingenuos . ^{[37] [38] [39]} En los casos en que la relación entre los predictores y la variable objetivo es lineal, los aprendices base pueden tener una precisión igualmente alta que el aprendiz de conjunto. ^{[40] [37]}

Bosque aleatorio del núcleo

En el aprendizaje automático, los bosques aleatorios de núcleo (KeRF) establecen la conexión entre los bosques aleatorios y los métodos de núcleo . Al modificar ligeramente su definición, los bosques aleatorios se pueden reescribir como métodos de núcleo , que son más interpretables y fáciles de analizar. ^[41]

Historia

Leo Breiman ^[42] fue la primera persona en notar el vínculo entre los métodos de kernel y de bosque aleatorio . Señaló que los bosques aleatorios entrenados usando vectores aleatorios iid en la construcción del árbol son equivalentes a un kernel que actúa sobre el margen verdadero. Lin y Jeon ^[43] 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 kernel adaptativas. Davies y Ghahramani ^[44] propusieron Kernel Random Forest (KeRF) y demostraron que puede superar empíricamente a los métodos de kernel de última generación. Scornet ^[41] definió por primera vez las estimaciones de KeRF y dio el vínculo explícito entre las estimaciones de KeRF y el bosque aleatorio. También dio expresiones explícitas para kernels basados ​​en el bosque aleatorio centrado ^[45] y el bosque aleatorio uniforme ^[46] , dos modelos simplificados de bosque aleatorio. Nombró a estos dos KeRF KeRF centrado y KeRF uniforme, y demostró límites superiores en sus tasas de consistencia.

Notaciones y definiciones

Preliminares: Bosques centrados

El bosque centrado ^[45] es un modelo simplificado del 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 binario completo de nivel, donde es un parámetro del algoritmo. ${\displaystyle k}$ ${\displaystyle k\in \mathbb {N} }$

Bosque uniforme

El bosque uniforme ^[46] es otro modelo simplificado del 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.

Del bosque aleatorio a KeRF

Dada una muestra de entrenamiento de variables aleatorias independientes con valores distribuidos como el par de prototipos independientes , donde . Nuestro objetivo es predecir la respuesta , asociada con 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 aleatorios. Denote el valor predicho en el punto por el -ésimo árbol, donde son 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 del bosque finito . Para los árboles de regresión, tenemos , donde es la celda que contiene , diseñado con aleatoriedad y conjunto de datos , y . ${\displaystyle {\mathcal {D}}_{n}=\{(\mathbf {X} _{i},Y_{i})\}_{i=1}^{n}}$ ${\displaystyle [0,1]^{p}\times \mathbb {R} }$ ${\displaystyle (\mathbf {X} ,Y)}$ ${\displaystyle \operatorname {E} [Y^{2}]<\infty }$ ${\displaystyle Y}$ ${\displaystyle \mathbf {X} }$ ${\displaystyle m(\mathbf {x} )=\operatorname {E} [Y\mid \mathbf {X} =\mathbf {x} ]}$ ${\displaystyle M}$ ${\displaystyle m_{n}(\mathbf {x} ,\mathbf {\Theta } _{j})}$ ${\displaystyle \mathbf {x} }$ ${\displaystyle j}$ ${\displaystyle \mathbf {\Theta } _{1},\ldots ,\mathbf {\Theta } _{M}}$ ${\displaystyle \mathbf {\Theta } }$ ${\displaystyle {\mathcal {D}}_{n}}$ ${\displaystyle m_{M,n}(\mathbf {x} ,\Theta _{1},\ldots ,\Theta _{M})={\frac {1}{M}}\sum _{j=1}^{M}m_{n}(\mathbf {x} ,\Theta _{j})}$ ${\displaystyle m_{n}=\sum _{i=1}^{n}{\frac {Y_{i}\mathbf {1} _{\mathbf {X} _{i}\in A_{n}(\mathbf {x} ,\Theta _{j})}}{N_{n}(\mathbf {x} ,\Theta _{j})}}}$ ${\displaystyle A_{n}(\mathbf {x} ,\Theta _{j})}$ ${\displaystyle \mathbf {x} }$ ${\displaystyle \Theta _{j}}$ ${\displaystyle {\mathcal {D}}_{n}}$ ${\displaystyle N_{n}(\mathbf {x} ,\Theta _{j})=\sum _{i=1}^{n}\mathbf {1} _{\mathbf {X} _{i}\in A_{n}(\mathbf {x} ,\Theta _{j})}}$

Por lo tanto, las estimaciones de bosque aleatorio 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, luego sobre todos los árboles. Por lo tanto, las contribuciones de las observaciones que están 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 de bosque aleatorio y compensar la estimación errónea, Scornet ^[41] definió KeRF por el cual es igual a la media de los que caen en las celdas que contienen en 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 con seguridad tenemos , que define el KeRF. ${\displaystyle \mathbf {x} \in [0,1]^{d}}$ ${\displaystyle m_{M,n}(\mathbf {x} ,\Theta _{1},\ldots ,\Theta _{M})={\frac {1}{M}}\sum _{j=1}^{M}\left(\sum _{i=1}^{n}{\frac {Y_{i}\mathbf {1} _{\mathbf {X} _{i}\in A_{n}(\mathbf {x} ,\Theta _{j})}}{N_{n}(\mathbf {x} ,\Theta _{j})}}\right)}$ $${\displaystyle {\tilde {m}}_{M,n}(\mathbf {x} ,\Theta _{1},\ldots ,\Theta _{M})={\frac {1}{\sum _{j=1}^{M}N_{n}(\mathbf {x} ,\Theta _{j})}}\sum _{j=1}^{M}\sum _{i=1}^{n}Y_{i}\mathbf {1} _{\mathbf {X} _{i}\in A_{n}(\mathbf {x} ,\Theta _{j})},}$$ ${\displaystyle Y_{i}}$ ${\displaystyle \mathbf {x} }$ ${\displaystyle M}$ ${\displaystyle K_{M,n}(\mathbf {x} ,\mathbf {z} )={\frac {1}{M}}\sum _{j=1}^{M}\mathbf {1} _{\mathbf {z} \in A_{n}(\mathbf {x} ,\Theta _{j})}}$ ${\displaystyle \mathbf {x} }$ ${\displaystyle \mathbf {z} }$ ${\displaystyle {\tilde {m}}_{M,n}(\mathbf {x} ,\Theta _{1},\ldots ,\Theta _{M})={\frac {\sum _{i=1}^{n}Y_{i}K_{M,n}(\mathbf {x} ,\mathbf {x} _{i})}{\sum _{\ell =1}^{n}K_{M,n}(\mathbf {x} ,\mathbf {x} _{\ell })}}}$

KeRF centrado

La construcción de un KeRF centrado de nivel es la misma que para un bosque centrado, excepto que las predicciones se realizan mediante , la función kernel correspondiente o la función de conexión. ${\displaystyle k}$ ${\displaystyle {\tilde {m}}_{M,n}(\mathbf {x} ,\Theta _{1},\ldots ,\Theta _{M})}$ $${\displaystyle K_{k}^{cc}(\mathbf {x} ,\mathbf {z} )=\sum _{k_{1},\ldots ,k_{d},\sum _{j=1}^{d}k_{j}=k}{\frac {k!}{k_{1}!\cdots k_{d}!}}\left({\frac {1}{d}}\right)^{k}\prod _{j=1}^{d}\mathbf {1} _{\lceil 2^{k_{j}}x_{j}\rceil =\lceil 2^{k_{j}}z_{j}\rceil },\qquad {\text{ for all }}\mathbf {x} ,\mathbf {z} \in [0,1]^{d}.}$$

KeRF uniforme

El KeRF uniforme se construye de la misma manera que el bosque uniforme, excepto que las predicciones se realizan mediante , la función de kernel correspondiente o la función de conexión. ${\displaystyle {\tilde {m}}_{M,n}(\mathbf {x} ,\Theta _{1},\ldots ,\Theta _{M})}$ $${\displaystyle K_{k}^{uf}(\mathbf {0} ,\mathbf {x} )=\sum _{k_{1},\ldots ,k_{d},\sum _{j=1}^{d}k_{j}=k}{\frac {k!}{k_{1}!\ldots k_{d}!}}\left({\frac {1}{d}}\right)^{k}\prod _{m=1}^{d}\left(1-|x_{m}|\sum _{j=0}^{k_{m}-1}{\frac {\left(-\ln |x_{m}|\right)^{j}}{j!}}\right){\text{ for all }}\mathbf {x} \in [0,1]^{d}.}$$

Propiedades

Relación entre KeRF y bosque aleatorio

Las predicciones dadas por KeRF y los 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 con seguridad, ${\displaystyle (a_{n}),(b_{n})}$ $${\displaystyle a_{n}\leq N_{n}(\mathbf {x} ,\Theta )\leq b_{n}{\text{ and }}a_{n}\leq {\frac {1}{M}}\sum _{m=1}^{M}N_{n}{\mathbf {x} ,\Theta _{m}}\leq b_{n}.}$$ $${\displaystyle |m_{M,n}(\mathbf {x} )-{\tilde {m}}_{M,n}(\mathbf {x} )|\leq {\frac {b_{n}-a_{n}}{a_{n}}}{\tilde {m}}_{M,n}(\mathbf {x} ).}$$

Relación entre KeRF infinito y bosque aleatorio infinito

Cuando el número de árboles tiende 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á limitado: ${\displaystyle M}$

Supongamos que existen secuencias tales que, casi con seguridad ${\displaystyle (\varepsilon _{n}),(a_{n}),(b_{n})}$

• ${\displaystyle \operatorname {E} [N_{n}(\mathbf {x} ,\Theta )]\geq 1,}$
• ${\displaystyle \operatorname {P} [a_{n}\leq N_{n}(\mathbf {x} ,\Theta )\leq b_{n}\mid {\mathcal {D}}_{n}]\geq 1-\varepsilon _{n}/2,}$
• ${\displaystyle \operatorname {P} [a_{n}\leq \operatorname {E} _{\Theta }[N_{n}(\mathbf {x} ,\Theta )]\leq b_{n}\mid {\mathcal {D}}_{n}]\geq 1-\varepsilon _{n}/2,}$

Entonces casi con seguridad, $${\displaystyle |m_{\infty ,n}(\mathbf {x} )-{\tilde {m}}_{\infty ,n}(\mathbf {x} )|\leq {\frac {b_{n}-a_{n}}{a_{n}}}{\tilde {m}}_{\infty ,n}(\mathbf {x} )+n\varepsilon _{n}\left(\max _{1\leq i\leq n}Y_{i}\right).}$$

Resultados de consistencia

Supongamos que , donde es un ruido gaussiano centrado, independiente de , con varianza finita . Además, se distribuye uniformemente en y es Lipschitz . Scornet ^[41] demostró límites superiores en las tasas de consistencia para KeRF centrado y KeRF uniforme. ${\displaystyle Y=m(\mathbf {X} )+\varepsilon }$ ${\displaystyle \varepsilon }$ ${\displaystyle \mathbf {X} }$ ${\displaystyle \sigma ^{2}<\infty }$ ${\displaystyle \mathbf {X} }$ ${\displaystyle [0,1]^{d}}$ ${\displaystyle m}$

Consistencia de KeRF centrada

Suponiendo que y , existe una constante tal que, para todo , . ${\displaystyle k\rightarrow \infty }$ ${\displaystyle n/2^{k}\rightarrow \infty }$ ${\displaystyle C_{1}>0}$ ${\displaystyle n}$ ${\displaystyle \mathbb {E} [{\tilde {m}}_{n}^{cc}(\mathbf {X} )-m(\mathbf {X} )]^{2}\leq C_{1}n^{-1/(3+d\log 2)}(\log n)^{2}}$

Consistencia de KeRF uniforme

Suponiendo que y , existe una constante tal que, . ${\displaystyle k\rightarrow \infty }$ ${\displaystyle n/2^{k}\rightarrow \infty }$ ${\displaystyle C>0}$ ${\displaystyle \mathbb {E} [{\tilde {m}}_{n}^{uf}(\mathbf {X} )-m(\mathbf {X} )]^{2}\leq Cn^{-2/(6+3d\log 2)}(\log n)^{2}}$

Desventajas

Si bien los bosques aleatorios suelen lograr una mayor precisión que un solo árbol de decisión, sacrifican la interpretabilidad intrínseca de los árboles de decisión. Los árboles de decisión forman parte de 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 principales ventajas 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. ^{[37] [3]} Por ejemplo, seguir el camino que toma 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 "nacido de nuevo" que reproduce fielmente la misma función de decisión. ^{[37] [47] [48]}

Otra limitación de los bosques aleatorios es que si las características están correlacionadas linealmente con el objetivo, el bosque aleatorio puede no mejorar la precisión del aprendiz base. ^{[37] [40]} Lo mismo ocurre en problemas con múltiples variables categóricas. ^[49]

Véase también

• Boosting  – Método en el aprendizaje automático
• Aprendizaje de árboles de decisión  : algoritmo de aprendizaje automático
• Aprendizaje conjunto  : técnicas de estadística y aprendizaje automático
• Aumento de gradiente  : técnica de aprendizaje automático
• Estadísticas no paramétricas  – Tipo de análisis estadísticoPages displaying short descriptions of redirect targets
• Algoritmo aleatorio  : algoritmo que emplea un grado de aleatoriedad como parte de su lógica o procedimiento.

Referencias

1. Ho, Tin Kam (1995). Bosques de decisiones aleatorias (PDF) . Actas de la 3.ª Conferencia internacional sobre análisis y reconocimiento de documentos, Montreal, QC, 14-16 de agosto de 1995. pp. 278-282. Archivado desde el original (PDF) el 17 de abril de 2016. Consultado el 5 de junio de 2016 .
2. Ho TK (1998). "El método del subespacio aleatorio para construir bosques de decisión" (PDF) . IEEE Transactions on Pattern Analysis and Machine Intelligence . 20 (8): 832–844. doi :10.1109/34.709601. S2CID  206420153.
3. Hastie, Trevor ; Tibshirani, Robert ; Friedman, Jerome (2008). Los elementos del aprendizaje estadístico (2.ª ed.). Springer. ISBN 0-387-95284-5.
4. Kleinberg E (1990). "Discriminación estocástica" (PDF) . Anales de matemáticas e inteligencia artificial . 1 (1–4): 207–239. CiteSeerX 10.1.1.25.6750 . doi :10.1007/BF01531079. S2CID  206795835. Archivado desde el original (PDF) el 18 de enero de 2018. 
5. Kleinberg E (1996). "Un método de modelado estocástico resistente al sobreentrenamiento para el reconocimiento de patrones". Anales de estadística . 24 (6): 2319–2349. doi : 10.1214/aos/1032181157 . MR  1425956.
6. Kleinberg E (2000). "Sobre la implementación algorítmica de la discriminación estocástica" (PDF) . IEEE Transactions on Pattern Analysis and Machine Intelligence . 22 (5): 473–490. CiteSeerX 10.1.1.33.4131 . doi :10.1109/34.857004. S2CID  3563126. Archivado desde el original (PDF) el 18 de enero de 2018. 
7. Breiman L (2001). "Bosques aleatorios". Aprendizaje automático . 45 (1): 5–32. Código Bibliográfico :2001MachL..45....5B. doi : 10.1023/A:1010933404324 .
8. Liaw A (16 de octubre de 2012). "Documentación para el paquete R randomForest" (PDF) . Consultado el 15 de marzo de 2013 .
9. Número de registro de marca estadounidense 3185828, registrada el 19/12/2006.
10. "RANDOM FORESTS Marca registrada de Health Care Productivity, Inc. - Número de registro 3185828 - Número de serie 78642027 :: Justia Trademarks".
11. Amit Y, Geman D (1997). "Cuantización de formas y reconocimiento con árboles aleatorios" (PDF) . Neural Computation . 9 (7): 1545–1588. CiteSeerX 10.1.1.57.6069 . doi :10.1162/neco.1997.9.7.1545. S2CID  12470146. Archivado desde el original (PDF) el 2018-02-05 . Consultado el 2008-04-01 . 
12. Heath, D., Kasif, S. y Salzberg, S. (1993). k-DT: Un método de aprendizaje de múltiples árboles. En Actas del Segundo Taller Internacional sobre Aprendizaje Multiestrategia , págs. 138-149.
13. Dietterich, Thomas (2000). "Una comparación experimental de tres métodos para construir conjuntos de árboles de decisión: bagging, boosting y randomización". Aprendizaje automático . 40 (2): 139–157. doi : 10.1023/A:1007607513941 .
14. Gareth James; Daniela Witten; Trevor Hastie; Robert Tibshirani (2013). Introducción al aprendizaje estadístico. Springer. págs. 316–321.
15. Ho, Tin Kam (2002). "Un análisis de la complejidad de los datos de las ventajas comparativas de los constructores de bosques de decisión" (PDF) . Análisis de patrones y aplicaciones . 5 (2): 102–112. doi :10.1007/s100440200009. S2CID  7415435. Archivado desde el original (PDF) el 2016-04-17 . Consultado el 2015-11-13 .
16. Geurts P, Ernst D, Wehenkel L (2006). "Árboles extremadamente aleatorios" (PDF) . Aprendizaje automático . 63 : 3–42. doi : 10.1007/s10994-006-6226-1 .
17. Dessi, N. y Milia, G. y Pes, B. (2013). Mejora del rendimiento de los bosques aleatorios en la clasificación de datos de microarrays. Artículo de conferencia, 99-103. 10.1007/978-3-642-38326-7_15.
18. Ye, Y., Li, H., Deng, X. y Huang, J. (2008) Bosque aleatorio de ponderación de características para la detección de interfaces de búsqueda web ocultas. Journal of Computational Linguistics and Chinese Language Processing, 13, 387–404.
19. Amaratunga, D., Cabrera, J., Lee, YS (2008) Bosque aleatorio enriquecido. Bioinformática, 24, 2010-2014.
20. Ghosh D, Cabrera J. (2022) Bosque aleatorio enriquecido para datos genómicos de alta dimensión. IEEE/ACM Trans Comput Biol Bioinform. 19(5):2817-2828. doi:10.1109/TCBB.2021.3089417.
21. Winham, Stacey y Freimuth, Robert y Biernacka, Joanna. (2013). Un enfoque de bosques aleatorios ponderados para mejorar el rendimiento predictivo. Análisis estadístico y minería de datos. 6. 10.1002/sam.11196.
22. Li, HB, Wang, W., Ding, HW y Dong, J. (10-12 de noviembre de 2010). Método de bosque aleatorio con ponderación de árboles para clasificar datos ruidosos de alta dimensión. Documento presentado en la 7.ª Conferencia Internacional sobre Ingeniería de Comercio Electrónico del IEEE de 2010.
23. Zhu R, Zeng D, Kosorok MR (2015). "Árboles de aprendizaje por refuerzo". Revista de la Asociación Estadounidense de Estadística . 110 (512): 1770–1784. doi :10.1080/01621459.2015.1036994. PMC 4760114. PMID  26903687 . 
24. Deng, H.; Runger, G.; Tuv, E. (2011). Medidas de sesgo de importancia para atributos y soluciones multivaluados. Actas de la 21.ª Conferencia Internacional sobre Redes Neuronales Artificiales (ICANN). págs. 293–300.
25. Altmann A, Toloşi L, Sander O, Lengauer T (mayo de 2010). "Importancia de la permutación: una medida corregida de la importancia de las características". Bioinformática . 26 (10): 1340–7. doi : 10.1093/bioinformatics/btq134 . PMID  20385727.
26. Piryonesi S. Madeh; El-Diraby Tamer E. (1 de junio de 2020). "El papel del análisis de datos en la gestión de activos de infraestructura: cómo superar los problemas de tamaño y calidad de los datos". Journal of Transportation Engineering, Parte B: Pavements . 146 (2): 04020022. doi :10.1061/JPEODX.0000175. S2CID  216485629.
27. Strobl C, Boulesteix AL, Augustin T (2007). "Selección dividida imparcial para árboles de clasificación basados ​​en el índice de Gini" (PDF) . Computational Statistics & Data Analysis . 52 : 483–501. CiteSeerX 10.1.1.525.3178 . doi :10.1016/j.csda.2006.12.030. 
28. Painsky A, Rosset S (2017). "La selección de variables con validación cruzada en métodos basados ​​en árboles mejora el rendimiento predictivo". IEEE Transactions on Pattern Analysis and Machine Intelligence . 39 (11): 2142–2153. arXiv : 1512.03444 . doi :10.1109/tpami.2016.2636831. PMID  28114007. S2CID  5381516.
29. Tolosi L, Lengauer T (julio de 2011). "Clasificación con características correlacionadas: falta de fiabilidad de la clasificación de características y soluciones". Bioinformática . 27 (14): 1986–94. doi : 10.1093/bioinformatics/btr300 . PMID  21576180.
30. "Cuidado con la importancia de los bosques aleatorios predeterminados". explained.ai . Consultado el 25 de octubre de 2023 .
31. Ortiz-Posadas, Martha Refugio (2020-02-29). Técnicas de reconocimiento de patrones aplicadas a problemas biomédicos. Springer Nature. ISBN 978-3-030-38021-2.
32. Breiman, Leo (25 de octubre de 2017). Árboles de clasificación y regresión. Nueva York: Routledge. doi :10.1201/9781315139470. ISBN 978-1-315-13947-0.
33. https://scikit-learn.org/stable/auto_examples/inspection/plot_permutation_importance.html 31 de agosto de 2023
34. Lin, Yi; Jeon, Yongho (2002). Bosques aleatorios y vecinos más cercanos adaptativos (informe técnico). Informe técnico n.º 1055. Universidad de Wisconsin. CiteSeerX 10.1.1.153.9168 . 
35. Shi, T.; Horvath, S. (2006). "Aprendizaje no supervisado con predictores de bosque aleatorio". Revista de estadística computacional y gráfica . 15 (1): 118–138. CiteSeerX 10.1.1.698.2365 . doi :10.1198/106186006X94072. JSTOR  27594168. S2CID  245216. 
36. Shi T, Seligson D, Belldegrun AS, Palotie A, Horvath S (abril de 2005). "Clasificación tumoral mediante perfil de microarray de tejido: agrupamiento aleatorio aplicado al carcinoma de células renales". Patología moderna . 18 (4): 547–57. doi : 10.1038/modpathol.3800322 . PMID  15529185.
37. Piryonesi, S. Madeh; El-Diraby, Tamer E. (1 de febrero de 2021). "Uso del aprendizaje automático para examinar el impacto del tipo de indicador de rendimiento en el modelado del deterioro del pavimento flexible". Revista de sistemas de infraestructura . 27 (2): 04021005. doi :10.1061/(ASCE)IS.1943-555X.0000602. ISSN  1076-0342. S2CID  233550030.
38. Prinzie, A.; Van den Poel, D. (2008). "Bosques aleatorios para clasificación multiclase: Logit multinominal aleatorio". Sistemas expertos con aplicaciones . 34 (3): 1721–1732. doi :10.1016/j.eswa.2007.01.029.
39. Prinzie, Anita (2007). "Clasificación multiclase aleatoria: generalización de bosques aleatorios a MNL aleatorio y NB aleatorio". En Roland Wagner; Norman Revell; Günther Pernul (eds.). Aplicaciones de sistemas expertos y bases de datos: 18.ª conferencia internacional, DEXA 2007, Regensburg, Alemania, 3-7 de septiembre de 2007, Actas . Notas de clase en informática. Vol. 4653. págs. 349–358. doi :10.1007/978-3-540-74469-6_35. ISBN 978-3-540-74467-2.
40. Smith, Paul F.; Ganesh, Siva; Liu, Ping (1 de octubre de 2013). "Una comparación de la regresión de bosque aleatorio y la regresión lineal múltiple para la predicción en neurociencia". Journal of Neuroscience Methods . 220 (1): 85–91. doi :10.1016/j.jneumeth.2013.08.024. PMID  24012917. S2CID  13195700.
41. Scornet, Erwan (2015). "Bosques aleatorios y métodos kernel". arXiv : 1502.03836 [math.ST].
42. Breiman, Leo (2000). "Alguna teoría del infinito para conjuntos de predictores". Informe técnico 579, Departamento de Estadística de la UCB. {{cite journal}}: Requiere citar revista |journal=( ayuda )
43. Lin, Yi; Jeon, Yongho (2006). "Bosques aleatorios y vecinos adaptativos más próximos". Revista de la Asociación Estadounidense de Estadística . 101 (474): 578–590. CiteSeerX 10.1.1.153.9168 . doi :10.1198/016214505000001230. S2CID  2469856. 
44. Davies, Alex; Ghahramani, Zoubin (2014). "El kernel de bosque aleatorio y otros kernels para big data a partir de particiones aleatorias". arXiv : 1402.4293 [stat.ML].
45. Breiman L, Ghahramani Z (2004). "Consistencia para un modelo simple de bosques aleatorios". Departamento de Estadística, Universidad de California en Berkeley. Informe técnico (670). CiteSeerX 10.1.1.618.90 . 
46. Arlot S, Genuer R (2014). "Análisis del sesgo de los bosques puramente aleatorios". arXiv : 1407.3939 [math.ST].
47. Sagi, Omer; Rokach, Lior (2020). "Bosque de decisiones explicable: transformación de un bosque de decisiones en un árbol interpretable". Fusión de información . 61 : 124–138. doi :10.1016/j.inffus.2020.03.013. S2CID  216444882.
48. Vidal, Thibaut; Schiffer, Maximilian (2020). "Conjuntos de árboles renacidos". Conferencia internacional sobre aprendizaje automático . 119 . PMLR: 9743–9753. arXiv : 2003.11132 .
49. Piryonesi, Sayed Madeh (noviembre de 2019). La aplicación del análisis de datos a la gestión de activos: deterioro y adaptación al cambio climático en las carreteras de Ontario (tesis doctoral) (tesis).

Lectura adicional

• Prinzie A, Poel D (2007). "Clasificación aleatoria multiclase: generalización de bosques aleatorios a MNL aleatorio y NB aleatorio". Aplicaciones de bases de datos y sistemas expertos . Apuntes de clase en informática . Vol. 4653. pág. 349. doi :10.1007/978-3-540-74469-6_35. ISBN 978-3-540-74467-2.
• Denisko D, Hoffman MM (febrero de 2018). «Clasificación e interacción en bosques aleatorios». Actas de la Academia Nacional de Ciencias de los Estados Unidos de América . 115 (8): 1690–1692. Bibcode :2018PNAS..115.1690D. doi : 10.1073/pnas.1800256115 . PMC  5828645 . PMID  29440440.

Enlaces externos

• Descripción del clasificador de bosques aleatorios (sitio de Leo Breiman)
• Liaw, Andy y Wiener, Matthew "Clasificación y regresión mediante randomForest" R News (2002) Vol. 2/3 p. 18 (Discusión sobre el uso del paquete random forest para R )