Bosque aleatorio

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

Tras el entrenamiento, los valores de la característica se permutan en las muestras fuera de la bolsa y se vuelve a calcular el error fuera de la bolsa sobre 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 mediante 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 de la variable fue dada y analizada por Zhu et al. ^{[ 25 ].}

Este método para determinar la importancia de las variables tiene algunos inconvenientes:

• Cuando las características tienen diferente número de valores, los bosques aleatorios favorecen las características con más valores. Las soluciones a este problema incluyen permutaciones parciales ^{[ 26 ] [ 27 ] [ 28 ]} y el crecimiento de árboles no sesgados. ^{[ 29 ] [ 30 ]}
• Si los datos contienen grupos de características correlacionadas de relevancia similar, entonces se prefieren los grupos más pequeños a los grupos grandes. ^{[ 31 ]}
• Si existen características colineales, el procedimiento podría no identificar características importantes. Una solución consiste en permutar grupos de características correlacionadas. ^{[ 32 ]}

Este enfoque para la importancia de las características en bosques aleatorios considera importantes las variables que disminuyen mucho la impureza durante la división. ^{[ 33 ]} Se describe en el libro Classification and Regression Trees de Leo Breiman ^{[ 34 ]} y es la implementación predeterminada en scikit learnR. La definición es:$${\displaystyle {\text{importancia promedio no normalizada}}(x)={\frac {1}{n_{T}}}\sum _{i=1}^{n_{T}}\sum _{{\text{nodo }}j\in T_{i}|{\text{variable dividida}}(j)=x}p_{T_{i}}(j)\Delta i_{T_{i}}(j),}$$dónde

• ${\displaystyle x}$es una característica
• ${\displaystyle n_{T}}$es el número de árboles en el bosque
• ${\displaystyle T_{i}}$es árbol${\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 en la impureza en el árbol${\displaystyle i}$en el nodo${\displaystyle j}$.

Como medida de impureza para 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 normalizando todas las características, de modo que la suma de las importancias normalizadas de las características sea 1.

La scikit learnimplementación predeterminada puede informar una importancia de características engañosa: ^{[ 32 ]}

• favorece las características de alta cardinalidad
• utiliza estadísticas de entrenamiento y, por lo tanto, no refleja la utilidad de una característica para predicciones en un conjunto de prueba ^{[ 35 ].}

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

El bosque uniforme ^{[ 48 ]} 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 lado de la celda, a lo largo de la característica preseleccionada.

Dado un ejemplo de entrenamiento ${\displaystyle {\mathcal {D}}_{n}=\{(\mathbf {X} _{i},Y_{i})\}_{i=1}^{n}}$de${\displaystyle [0,1]^{p}\times \mathbb {R} }$variables aleatorias independientes con valor -distribuidas como el par prototipo independiente${\displaystyle (\mathbf {X},Y)}$, dónde${\displaystyle \operatorname {E} [Y^{2}]<\infty }$Nuestro objetivo es predecir la respuesta.${\displaystyle Y}$, asociada con la variable aleatoria${\displaystyle \mathbf {X} }$, estimando la función de regresión${\displaystyle m(\mathbf {x} )=\operatorname {E} [Y\mid \mathbf {X} =\mathbf {x} ]}$. Un bosque de regresión aleatoria es un conjunto de${\displaystyle M}$árboles de regresión aleatorios. Denotemos${\ Displaystyle m_ {n} (\ mathbf {x}, \ mathbf {\ Theta} _ {j})}$el valor previsto en el punto${\displaystyle \mathbf {x} }$por el${\displaystyle j}$-ésimo árbol, donde${\displaystyle \mathbf {\Theta } _{1},\ldots,\mathbf {\Theta } _{M}}$son variables aleatorias independientes, distribuidas como una variable aleatoria genérica${\displaystyle \mathbf {\Theta } }$, independientemente de la muestra${\displaystyle {\mathcal {D}}_{n}}$Esta variable aleatoria puede utilizarse para describir la aleatoriedad inducida por la división de nodos y el procedimiento de muestreo para la construcción del árbol. Los árboles se combinan para formar la estimación del bosque finito.${\displaystyle m_{M,n}(\mathbf {x} ,\Theta _{1},\ldots ,\Theta _{M})={\frac {1}{M}}\sum _{j=1}^{M}m_{n}(\mathbf {x} ,\Theta _{j})}$. Para los árboles de regresión, tenemos${\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})}}}$, dónde${\ Displaystyle A_ {n} (\ mathbf {x}, \ Theta _ {j})}$es la célula que contiene${\displaystyle \mathbf {x} }$diseñado con aleatoriedad${\displaystyle \Theta _{j}}$y conjunto de datos${\displaystyle {\mathcal {D}}_{n}}$, y${\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 bosques aleatorios satisfacen, para todo${\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)}$El bosque de regresión aleatoria tiene dos niveles de promediado, 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 ^{[ 43 ]} definió KeRF mediante $${\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})},}$$ que es igual a la media de la${\displaystyle Y_{i}}$está cayendo en las células que contienen${\displaystyle \mathbf {x} }$en el bosque. Si definimos la función de conexión del${\displaystyle M}$bosque finito como${\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})}}$, es decir, la proporción de células compartidas entre${\displaystyle \mathbf {x} }$y${\displaystyle \mathbf {z} }$, entonces casi con seguridad tenemos${\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 })}}}$, que define el KeRF.

La construcción de KeRF centrado de nivel${\displaystyle k}$es lo mismo que para el bosque centrado, excepto que las predicciones se hacen por${\displaystyle {\tilde {m}}_{M,n}(\mathbf {x} ,\Theta _{1},\ldots ,\Theta _{M})}$, la función kernel correspondiente, o función de conexión, es $${\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}.}$$

Uniform KeRF se construye de la misma manera que Uniform Forest, excepto que las predicciones se hacen mediante...${\displaystyle {\tilde {m}}_{M,n}(\mathbf {x} ,\Theta _{1},\ldots ,\Theta _{M})}$, la función kernel correspondiente, o función de conexión, es $${\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}.}$$

Las predicciones proporcionadas por KeRF y los bosques aleatorios son similares si se controla el número de puntos en cada celda:

Supongamos que existen secuencias${\displaystyle (a_{n}),(b_{n})}$de tal manera que, casi con seguridad, $${\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 con seguridad, $${\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} ).}$$

Cuando el número de árboles${\displaystyle M}$Si tiende a infinito, entonces tenemos un bosque aleatorio infinito y un KeRF infinito. Sus estimaciones son similares si el número de observaciones en cada celda está acotado:

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

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

Siempre que${\displaystyle k\rightarrow \infty }$y${\displaystyle n/2^{k}\rightarrow \infty }$, existe una constante${\displaystyle C_{1}>0}$de tal manera que, para todos${\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}}$.

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