Método de bosque aleatorio

El método del bosque aleatorio es un algoritmo de aprendizaje automático propuesto por Leo Breiman [1] [2] y Adele Cutler , que consiste en utilizar un comité (conjunto) de árboles de decisión . El algoritmo combina dos ideas principales: el método de ensacado de Breiman y el método del subespacio aleatorio .propuesto por Tin Kam Ho. El algoritmo se utiliza para problemas de clasificación, regresión y agrupamiento. La idea principal es utilizar un gran conjunto de árboles de decisión , cada uno de los cuales en sí mismo da una calidad de clasificación muy baja, pero debido a su gran número, el resultado es bueno.

Algoritmo de aprendizaje del clasificador

Deje que el conjunto de entrenamiento consista en N muestras, la dimensión del espacio de características es M y el parámetro m (generalmente en problemas de clasificación ) se da como un número incompleto de características para el entrenamiento. $m\aproximado {\sqrt {M}}$

La forma más común de construir árboles de conjunto - embolsado ( eng. bagging , abreviatura de eng. bootstrap aggregation) - se realiza de la siguiente manera:

Generemos una submuestra aleatoria repetida de tamaño a partir de la muestra de entrenamiento. Algunas muestras caerán dos o más veces, mientras que en promedio (para aproximadamente grandes , donde es la base del logaritmo natural ) las muestras no se incluyen en el conjunto o no se seleccionan ( inglés fuera de bolsa ). $norte$ ${\ estilo de visualización N (1-1/N) ^ {N))$ $norte$ ${\ estilo de visualización norte}$ $mi$
Construyamos un árbol de decisión que clasifique las muestras de esta submuestra y, en el transcurso de la creación del siguiente nodo del árbol, elegiremos un conjunto de características sobre la base de las cuales se realiza la división (no de todas las M características , pero solo de m seleccionados al azar). La elección de la mejor de estas m características se puede realizar de varias formas. El método original de Breiman usa el criterio de Gini , que también se usa en el algoritmo del árbol de decisión CART . En algunas implementaciones del algoritmo, se utiliza en su lugar el criterio de ganancia de información . [3]
El árbol se construye hasta que el submuestreo se agota por completo y no se somete al procedimiento de poda ( ing. pruning - cortar ramas), en contraste con los árboles de decisión de algoritmos como CART o C4.5 .

La clasificación de los objetos se realiza mediante votación: cada árbol del comité asigna el objeto que se clasifica a una de las clases, y gana la clase que tenga el mayor número de árboles votados.

El número óptimo de árboles se selecciona de tal manera que se minimice el error del clasificador en la muestra de prueba. Si está ausente, la estimación del error se minimiza en muestras no incluidas en el conjunto.

Evaluación de la importancia de las variables

Los bosques aleatorios obtenidos por los métodos descritos anteriormente pueden usarse naturalmente para evaluar la importancia de las variables en problemas de regresión y clasificación . Breiman describió el modo siguiente de tal estimación.

El primer paso para evaluar la importancia de una variable en un conjunto de entrenamiento es entrenar un bosque aleatorio en ese conjunto. Durante el proceso de construcción del modelo, se registra el llamado error out-of-bag para cada elemento del conjunto de entrenamiento. ${\mathcal {D}}_{n}=\{(X_{i},Y_{i})\}_{i=1}^{n}$ (error de elementos no seleccionados). Luego, para cada entidad, este error se promedia sobre todo el bosque aleatorio.

Para evaluar la importancia del parámetro -ésimo después del entrenamiento, los valores del parámetro -ésimo se mezclan para todos los registros del conjunto de entrenamiento y se calcula nuevamente el error fuera de bolsa. La importancia del parámetro se estima promediando la diferencia en las tasas de error fuera de bolsa sobre todos los árboles antes y después de mezclar los valores. En este caso, los valores de dichos errores se normalizan a la desviación estándar . $j$ $j$

Los parámetros de muestra que producen valores más grandes se consideran más importantes para el conjunto de entrenamiento. El método tiene una desventaja potencial: para variables categóricas con una gran cantidad de valores, el método tiende a considerar tales variables más importantes. La mezcla parcial de valores en este caso puede reducir la influencia de este efecto. [4] [5] De los grupos de parámetros correlacionados, cuya importancia resulta ser la misma, se seleccionan los grupos más pequeños. [6]

Ventajas

La capacidad de procesar datos de manera eficiente con una gran cantidad de características y clases.
Insensibilidad a la escala (y en general a cualquier transformación monótona) de los valores de las características.
Tanto las características continuas como las discretas se procesan igualmente bien. Existen métodos para construir árboles a partir de datos a los que les faltan valores de características.
Hay métodos para estimar la importancia de las características individuales en un modelo.
Evaluación interna de la capacidad de generalización del modelo (test sobre muestras no seleccionadas).
Alta paralelización y escalabilidad .

Desventajas

El gran tamaño de los modelos resultantes. Se requiere memoria para almacenar el modelo, donde está el número de árboles. ${\ estilo de visualización O (K)}$ $k$

Uso en artículos científicos

El algoritmo se utiliza en artículos científicos, por ejemplo, para evaluar la calidad de los artículos de Wikipedia [7] [8] [9] .

Notas

↑ Breiman, Leo . Bosques aleatorios // Aprendizaje automático : diario. - 2001. - vol. 45 , núm. 1 . - Pág. 5-32 . -doi : 10.1023/A : 1010933404324 . (Inglés) (Fecha de acceso: 7 de junio de 2009)
↑ Descripción del algoritmo en el sitio web de Leo Breiman. Archivado el 22 de junio de 2008. (Inglés) (Fecha de acceso: 7 de junio de 2009)
↑ Una descripción del procedimiento de creación de árboles utilizado en Apache Mahout . Archivado el 13 de mayo de 2012 en Wayback Machine ( consultado el 7 de junio de 2009).
↑ Deng, H.; Runger, G.; Tuv, E. (2011). Sesgo de medidas de importancia para atributos y soluciones de valores múltiples . Actas de la 21.ª Conferencia Internacional sobre Redes Neuronales Artificiales (ICANN). páginas. 293-300.
↑ Altmann A., Tolosi L., Sander O., Lengauer T. Importancia de la permutación: una medida de importancia de característica corregida (inglés) // Bioinformatics: journal. - 2010. - doi : 10.1093/bioinformatics/btq134 .
↑ Tolosi L., Lengauer T. Clasificación con características correlacionadas: falta de confiabilidad en la clasificación de características y soluciones. (Inglés) // Bioinformática: revista. - 2011. - doi : 10.1093/bioinformatics/btr300 .
↑ Węcel K., Lewoniewski W. Modelado de la calidad de los atributos en los cuadros de información de Wikipedia // Apuntes de clase sobre el procesamiento de información empresarial: revista. - 2015. - 2 de diciembre ( vol. 228 ). - P. 308-320 . -doi : 10.1007 / 978-3-319-26762-3_27 .
↑ Lewoniewski W., Węcel K., Abramowicz W. Calidad e importancia de los artículos de Wikipedia en diferentes idiomas // Tecnologías de la información y el software. ICIST 2016. Comunicaciones en Informática y Ciencias de la Información: revista. - 2016. - 22 de septiembre ( vol. 639 ). - Pág. 613-624 . -doi : 10.1007 / 978-3-319-46254-7_50 .
↑ Warncke-Wang M., Cosley D., Riedl J. Cuéntame más: un modelo de calidad accionable para wikipedia // Actas de WikiSym '13 del 9º Simposio Internacional sobre Colaboración Abierta: revista. - 2013. - doi : 10.1145/2491055.2491063 .

Literatura

Hastie, T., Tibshirani R., Friedman J. Capítulo 15. Bosques aleatorios // Los elementos del aprendizaje estadístico: minería de datos, inferencia y predicción . — 2ª ed. - Springer-Verlag, 2009. - 746 p. - ISBN 978-0-387-84857-0 . .

Enlaces

Implementaciones

Implementación del autor de Breiman y Cutler en Fortran 77
El paquete randomForest para R es una versión portada del código del autor original en R
El paquete party para R contiene una modificación del algoritmo .
Implementación de la modificación del algoritmo en alglib.sources.ru
rápidoaleatoriobosque
Apache Mahout Archivado el 2 de abril de 2015 en Wayback Machine .

Aprendizaje automático y minería de datos
Tareas	Problema de clasificación Aprender sin un maestro Aprendizaje asistido por profesores Análisis de regresión AutoML reglas de asociación Extracción de características entrenamiento de rasgos Entrenamiento de clasificación Derivación gramatical Aprender en línea
Aprendiendo con un maestro	método del k-vecino más cercano Clasificador bayesiano ingenuo árbol de decisión Máquinas de vectores soporte Regresión lineal Regresión logística perceptrón conjuntos de modelos Harpillera impulsar bosque aleatorio Método de vector relevante
análisis de conglomerados	método k-medias método de agrupamiento difuso Agrupación jerárquica algoritmo EM ABEDUL CURAR DBSCAN ÓPTICA Desplazamiento medio
Reducción de dimensionalidad	Análisis factorial Método de componentes principales CCA ACI LDA Expansión de matriz no negativa t-SNE
Pronóstico estructural	Graficar modelo probabilístico red bayesiana Modelo oculto de Markov FRC
Detección de anomalías	método del k-vecino más cercano Nivel de emisión local
Graficar modelos probabilísticos	red bayesiana Red de Markov Modelo oculto de Markov
Redes neuronales	Máquina Boltzmann limitada mapa autoorganizado Función de activación Sigmoideo softmax Funcion de base radial Método de propagación hacia atrás Aprendizaje profundo perceptrón multicapa Red neuronal recurrente memoria a corto plazo Bloque recurrente controlado Red neuronal convolucional U-red Codificador automático
Aprendizaje reforzado	proceso de Markov Ecuación de Bellman Algoritmo codicioso Q-aprendizaje SARAS Diferencia temporal (DT)
Teoría	Teoría de Vapnik-Chervonenkis Dilema de dispersión de sesgo Teoría del aprendizaje computacional Minimización empírica del riesgo El aprendizaje de Occam aprendizaje PAC Teoría del aprendizaje estadístico
revistas y congresos	NeurIPS ICML ML JMLR ArXiv:cs.LG