bosque aleatorio

Método de aprendizaje automático conjunto basado en árbol de búsqueda binaria

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.

Historia

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:

1. Uso del error fuera de bolsa como estimación del error de generalización .
2. Medición de la importancia de la variable 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 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.

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, los resultados de los n árboles se agregan para producir una decisión 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 ₁ , ..., x _n con respuestas Y = y ₁ , ..., y _n , embolsar repetidamente ( B veces) selecciona una muestra aleatoria con reemplazo del conjunto de entrenamiento y ajusta los árboles a estos muestras:

Para b = 1, ..., B :

1. Muestra, con reemplazo, n ejemplos de entrenamiento de X , Y ; llámelos X _b , Y _b .
2. Entrene un árbol de clasificación o regresión f _b en X _b , Y _b .

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' :

$${\displaystyle {\hat {f}}={\frac {1}{B}}\sum _{b=1}^{B}f_{b}(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′ :

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

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.

Del embolsado a los bosques aleatorios

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}

árboles adicionales

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] ${\displaystyle {\sqrt {p}}}$ ${\displaystyle p}$ ${\displaystyle p}$

Bosques aleatorios para datos de alta dimensión

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: elimine las 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]}

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

Importancia de la permutación

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). ${\displaystyle {\mathcal {D}}_{n}=\{(X_{i},Y_{i})\}_{i=1}^{n}}$

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. ${\displaystyle j}$ ${\displaystyle j}$ ${\displaystyle j}$

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.

• Para datos que incluyen variables categóricas con diferente número de niveles, los bosques aleatorios están sesgados a favor de aquellos atributos con más niveles. Para resolver el problema se pueden utilizar métodos como las permutaciones parciales ^{[23] [24] [25]} y el cultivo de árboles imparciales ^{[26] [27] .}
• Si los datos contienen grupos de características correlacionadas de relevancia similar para el resultado, entonces se prefieren los grupos más pequeños a los más grandes. ^[28]
• Además, es posible que el procedimiento de permutación no identifique características importantes cuando hay características colineales. En este caso, la solución es permutar grupos de características correlacionadas. ^[29]

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

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]

$${\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}$ ${\displaystyle n_{T}}$ ${\displaystyle T_{i}}$ ${\displaystyle i}$ ${\displaystyle p_{T_{i}}(j)={\frac {n_{j}}{n}}}$ ${\displaystyle j}$ ${\displaystyle \Delta i_{T_{i}}(j)}$ ${\displaystyle t}$ ${\displaystyle j}$

• entropía
• coeficiente GINI
• Error medio cuadrado

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]

• la medida de importancia prefiere características de alta cardinalidad
• utiliza estadísticas de entrenamiento y por lo tanto no "refleja la capacidad de la característica de ser útil para hacer predicciones que se generalicen al conjunto de pruebas" ^[32]

Relación con los vecinos más cercanos

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 : ${\displaystyle \{(x_{i},y_{i})\}_{i=1}^{n}}$ ${\displaystyle {\hat {y}}}$

$${\displaystyle {\hat {y}}=\sum _{i=1}^{n}W(x_{i},x')\,y_{i}.}$$

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: ${\displaystyle W(x_{i},x')}$ ${\displaystyle x_{i}}$

• En k -NN, los pesos son 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 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] ${\displaystyle x_{i}}$ ${\displaystyle j}$

Aprendizaje no supervisado con bosques aleatorios.

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 aleatorio 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]

Variantes

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]}

Bosque aleatorio del núcleo

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]

Historia

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.

Notaciones y definiciones

Preliminares: Bosques centrados

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. ${\displaystyle k}$ ${\displaystyle k\in \mathbb {N} }$

Bosque uniforme

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.

Del bosque aleatorio a KeRF

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 . ${\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 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 ${\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 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 ${\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

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. ${\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 bosques aleatorios son cercanas si se controla el número de puntos en cada celda:

Supongamos que existen secuencias tales que, 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}.}$$

Entonces casi seguramente,

$${\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 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: ${\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 seguramente,

$${\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 Lipschitz y es . Scornet ^[40] 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 del KeRF centrado

Proporcionando y , existe una constante tal que, para todos , . ${\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 del KeRF uniforme

Proporcionando 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 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 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 "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]

Ver también

• Boosting  – Método en aprendizaje automático
• Aprendizaje del árbol de decisiones  : algoritmo de aprendizaje automático
• Aprendizaje conjunto  : estadística y técnica de aprendizaje automático
• Aumento de gradiente  : técnica de aprendizaje automático
• Estadísticas no paramétricas  : rama de la estadística que no se basa únicamente en familias parametrizadas de distribuciones de probabilidad.Pages displaying short descriptions of redirect targets
• Algoritmo aleatorio  : algoritmo que emplea cierto grado de aleatoriedad como parte de su lógica o procedimiento.

Referencias

1. Ho, Tin Kam (1995). Bosques de decisión aleatoria (PDF) . Actas de la Tercera Conferencia Internacional sobre Análisis y Reconocimiento de Documentos, Montreal, QC, 14 a 16 de agosto de 1995, págs. 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) . Transacciones IEEE sobre análisis de patrones e inteligencia artificial . 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.). Saltador. 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 . SEÑOR  1425956.
6. Kleinberg E (2000). "Sobre la implementación algorítmica de la discriminación estocástica" (PDF) . Transacciones IEEE sobre análisis de patrones e inteligencia artificial . 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 Bib : 2001 MachL..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, registrado el 19/12/2006.
10. "RANDOM FORESTS Marca comercial de Health Care Productivity, Inc. - Número de registro 3185828 - Número de serie 78642027 :: Marcas comerciales de Justia".
11. Amit Y, Geman D (1997). "Cuantización y reconocimiento de formas con árboles aleatorios" (PDF) . Computación neuronal . 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 5 de febrero de 2018 . Consultado el 1 de abril de 2008 . 
12. Dietterich, Thomas (2000). "Una comparación experimental de tres métodos para construir conjuntos de árboles de decisión: embolsado, impulso y aleatorización". Aprendizaje automático . 40 (2): 139-157. doi : 10.1023/A:1007607513941 .
13. Gareth James; Daniela Witten; Trevor Hastie; Robert Tibshirani (2013). Una introducción al aprendizaje estadístico. Saltador. págs. 316–321.
14. 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 y aplicaciones de patrones . 5 (2): 102–112. doi :10.1007/s100440200009. S2CID  7415435. Archivado desde el original (PDF) el 17 de abril de 2016 . Consultado el 13 de noviembre de 2015 .
15. Geurts P, Ernst D, Wehenkel L (2006). "Árboles extremadamente aleatorios" (PDF) . Aprendizaje automático . 63 : 3–42. doi : 10.1007/s10994-006-6226-1 .
16. Dessi, N. y Milia, G. y Pes, B. (2013). Mejora del rendimiento de los bosques aleatorios en la clasificación de datos de microarrays. Documento de conferencia, 99-103. 10.1007/978-3-642-38326-7_15.
17. Ye, Y., Li, H., Deng, X. y Huang, J. (2008) Bosque aleatorio de ponderación de funciones para la detección de interfaces de búsqueda web ocultas. Revista de lingüística computacional y procesamiento del idioma chino, 13, 387–404.
18. Amaratunga, D., Cabrera, J., Lee, YS (2008) Bosque aleatorio enriquecido. Bioinformática, 24, 2010-2014.
19. 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.
20. 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.
21. Li, HB, Wang, W., Ding, HW y Dong, J. (2010, 10 a 12 de noviembre de 2010). Método de bosque aleatorio de ponderación de árboles para clasificar datos ruidosos de alta dimensión. Trabajo presentado en la Séptima Conferencia Internacional IEEE 2010 sobre Ingeniería de Negocios Electrónicos.
22. 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. 
23. 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.
24. Altmann A, Toloşi L, Sander O, Lengauer T (mayo de 2010). "Importancia de la permutación: una medida de importancia de característica corregida". Bioinformática . 26 (10): 1340–7. doi : 10.1093/bioinformática/btq134 . PMID  20385727.
25. Piryonesi S. Madeh; El-Diraby Tamer E. (1 de junio de 2020). "Papel del análisis de datos en la gestión de activos de infraestructura: superar los problemas de calidad y tamaño de los datos". Revista de Ingeniería del Transporte, Parte B: Pavimentos . 146 (2): 04020022. doi : 10.1061/JPEODX.0000175. S2CID  216485629.
26. Strobl C, Boulesteix AL, Augustin T (2007). "Selección dividida imparcial para árboles de clasificación basada en el índice de Gini" (PDF) . Estadística computacional y análisis de datos . 52 : 483–501. CiteSeerX 10.1.1.525.3178 . doi :10.1016/j.csda.2006.12.030. 
27. Painsky A, Rosset S (2017). "La selección de variables con validación cruzada en métodos basados ​​en árboles mejora el rendimiento predictivo". Transacciones IEEE sobre análisis de patrones e inteligencia artificial . 39 (11): 2142-2153. arXiv : 1512.03444 . doi :10.1109/tpami.2016.2636831. PMID  28114007. S2CID  5381516.
28. Tolosi L, Lengauer T (julio de 2011). "Clasificación con características correlacionadas: falta de confiabilidad de la clasificación de características y las soluciones". Bioinformática . 27 (14): 1986–94. doi : 10.1093/bioinformática/btr300 . PMID  21576180.
29. "Cuidado con las importancias forestales aleatorias predeterminadas". explicado.ai . Consultado el 25 de octubre de 2023 .
30. 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.
31. Ortiz-Posadas, Martha Refugio (29 de febrero de 2020). Técnicas de reconocimiento de patrones aplicadas a problemas biomédicos. Naturaleza Springer. ISBN 978-3-030-38021-2.
32. https://scikit-learn.org/stable/auto_examples/inspection/plot_permutation_importance.html 31 de agosto de 2023
33. 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 . 
34. Shi, T.; Horvath, S. (2006). "Aprendizaje no supervisado con predictores forestales aleatorios". 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. 
35. Shi T, Seligson D, Belldegrun AS, Palotie A, Horvath S (abril de 2005). "Clasificación de tumores mediante perfiles de microarrays de tejidos: agrupación de bosques aleatoria aplicada al carcinoma de células renales". Patología Moderna . 18 (4): 547–57. doi : 10.1038/modpathol.3800322 . PMID  15529185.
36. 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 desempeño en el modelado de deterioro de pavimentos flexibles". Revista de sistemas de infraestructura . 27 (2): 04021005. doi :10.1061/(ASCE)IS.1943-555X.0000602. ISSN  1076-0342. S2CID  233550030.
37. Prinzie, A.; Van den Poel, D. (2008). "Bosques aleatorios para clasificación multiclase: Logit multinomial aleatorio". Sistemas Expertos con Aplicaciones . 34 (3): 1721-1732. doi :10.1016/j.eswa.2007.01.029.
38. Prinzie, Anita (2007). "Clasificación aleatoria multiclase: 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, Ratisbona, Alemania, 3 al 7 de septiembre de 2007, Actas . Apuntes de conferencias sobre informática. vol. 4653, págs. 349–358. doi :10.1007/978-3-540-74469-6_35. ISBN 978-3-540-74467-2.
39. Smith, Paul F.; Ganesh, Siva; Liu, Ping (1 de octubre de 2013). "Una comparación de regresión forestal aleatoria y regresión lineal múltiple para la predicción en neurociencia". Revista de métodos de neurociencia . 220 (1): 85–91. doi :10.1016/j.jneumeth.2013.08.024. PMID  24012917. S2CID  13195700.
40. Scornet, Erwan (2015). "Bosques aleatorios y métodos de kernel". arXiv : 1502.03836 [matemáticas.ST].
41. Breiman, Leo (2000). "Alguna teoría del infinito para conjuntos de predictores". Informe Técnico 579, Dpto. Estadística UCB. {{cite journal}}: Citar diario requiere |journal=( ayuda )
42. Lin, Yi; Jeon, Yongho (2006). "Bosques aleatorios y vecinos más cercanos adaptativos". 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. 
43. Davies, Alex; Ghahramani, Zoubin (2014). "El Random Forest Kernel y otros kernels para big data de particiones aleatorias". arXiv : 1402.4293 [estad.ML].
44. 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 . 
45. Arlot S, Genuer R (2014). "Análisis del sesgo de bosques puramente aleatorio". arXiv : 1407.3939 [matemáticas.ST].
46. 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.
47. Vidal, Thibaut; Schiffer, Maximiliano (2020). "Conjuntos de árboles nacidos de nuevo". Congreso Internacional sobre Aprendizaje Automático . 119 . PMLR: 9743–9753. arXiv : 2003.11132 .
48. 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).

Otras lecturas

• 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 conferencias sobre 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. Código Bib : 2018PNAS..115.1690D. doi : 10.1073/pnas.1800256115 . PMC  5828645 . PMID  29440440.

enlaces externos

• Descripción del clasificador Random Forests (sitio de Leo Breiman)
• Liaw, Andy & Wiener, Matthew "Clasificación y regresión por bosque aleatorio" R News (2002) vol. 2/3p. 18 (Discusión sobre el uso del paquete de bosque aleatorio para R )