CARRITO (algoritmo)

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 2 de agosto de 2020; las comprobaciones requieren 2 ediciones .

El algoritmo CART (Classification and Regression Tree) , como su nombre indica, resuelve problemas de clasificación y regresión mediante la construcción de un árbol de decisión. Fue desarrollado en 1974-1984 por cuatro profesores de estadística: Leo Breiman ( Berkeley ), Jerome Friedman( Stanford ), Charles Stone (Charles Stone, Berkeley ) y Richard Olshen (Richard A. Olshen, Stanford ).

A la fecha, existe una gran cantidad de algoritmos que implementan árboles de decisión: CART , C4.5 , CHAID, CN2, NewId , ITrule y otros [1] .

El significado básico del algoritmo

El algoritmo CART está diseñado para construir un árbol de decisión binario. Los árboles binarios (binarios) son árboles, cada nodo de los cuales, cuando se divide, tiene solo dos hijos. Para el algoritmo CART, el "comportamiento" de los objetos del grupo seleccionado significa la proporción del valor modal (más frecuente) de la característica de salida. Los grupos seleccionados son aquellos para los que esta proporción es bastante alta. En cada paso de la construcción del árbol, la regla formada en el nodo divide el conjunto dado de ejemplos en dos partes: la parte donde la regla es verdadera (hijo: derecha) y la parte donde la regla no es verdadera (hijo: izquierda). [2]

La ventaja del algoritmo CART es una cierta garantía de que si existen las determinaciones deseadas en la población estudiada, entonces se revelarán. Además, CART le permite no "cerrar" en un solo valor de la función de salida, sino buscar todos esos valores para los que puede encontrar la expresión explicativa correspondiente. [3]

El método CART se utiliza para variables predictoras nominales (generalmente de dos niveles) y ordinales . En este método, se enumeran todas las opciones de ramificación posibles para cada nodo y se selecciona la variable predictora para la cual el estimador otorga la mejor puntuación.

Reglas de particionamiento

Para una variable predictora nominal que toma k valores en un nodo dado, hay exactamente 2 (k-1) −1 opciones para dividir el conjunto de sus valores en dos partes.

Para un predictor ordinal que tiene k niveles diferentes en un nodo dado, hay k-1 puntos que separan los diferentes niveles. La cantidad de opciones de bifurcación diferentes que deben verse será muy grande: si hay muchos predictores en el problema, entonces tienen muchos niveles de valores, lo que significa que hay muchos vértices terminales en el árbol. Además, este método tiende a optar por ramificar aquellas variables predictoras que tienen más niveles, por lo que se necesita un indicador que permita evaluar la calidad del modelo construido. [cuatro]

Evaluación de la calidad del modelo

La función de evaluación que utiliza el algoritmo CART se basa en la idea intuitiva de reducir la incertidumbre (heterogeneidad) en un nodo. Como ejemplo, considere un problema con dos clases y un nodo que tiene 50 instancias de cada clase. El nodo tiene máxima incertidumbre. Si se encuentra una partición que divide los datos en dos subgrupos de 40:5 ejemplos en uno y 10:45 en el otro, intuitivamente la heterogeneidad disminuirá. Desaparecerá por completo cuando se encuentre una división que creará los subgrupos 50:0 y 0:50. En el algoritmo CART, la idea de incertidumbre se formaliza en el índice de Gini . Si el conjunto de datos T contiene n datos de clase, entonces el índice de Gini se define de la siguiente manera [5]

Gini(T)=1-\sum_{{i=1}}^{n}p_{i}^{2}

, donde pi es la probabilidad (frecuencia relativa) de clase i en T . Si el conjunto T se divide en dos partes T1 y T2 con el número de ejemplos en cada una N1 y N2 , respectivamente, entonces el índice de calidad de división será igual a:

Gini_{{\text{dividir}}}(T)={\frac {N_{1}}{N}}\cdot Gini(T_{1})+{\frac {N_{2}}{N}} \cdot Gini(T_{2})

La mejor partición es aquella para la que Ginisplit(T) es mínimo. Sea N el número de ejemplos en el nodo ancestro, L , R son el número de ejemplos en los hijos izquierdo y derecho, respectivamente, li y ri son el número de instancias de la i -ésima clase en los hijos izquierdo/derecho. Luego, la calidad de la partición se estima mediante la siguiente fórmula:

Gini_{{\text{dividir}}}={\frac {L}{N}}\cdot \left(1-\sum_{{i=1}}^{n}\left({\frac {l_ {i}}{L}}\right)^{2}\right)+{\frac {R}{N}}\cdot \left(1-\sum_{{i=1}}^{n} \left({\frac {r_{i}}{R}}\right)^{2}\right)\a \min

Para reducir la cantidad de cálculos, la fórmula se puede transformar:

Gini_{{\text{dividir}}}={\frac {1}{N}}\cdot \left(L\cdot \left(1-{\frac {1}{L^{2}}}\cdot \sum _{{i=1}}^{n}l_{i}^{2}\right)+R\cdot \left(1-{\frac {1}{R^{2}}}\cdot \sum _{{i=1}}^{n}r_{i}^{2}\right)\right)\to \min

Dado que la multiplicación por una constante no juega un papel en la minimización:

{\begin{matriz}{l}\displaystyle Gini_{{\text{dividir}}}=L-{\frac {1}{L}}\cdot \sum_{{i=1}}^{n} l_{i}^{2}+R-{\frac {1}{R}}\cdot \sum_{{i=1}}^{n}r_{i}^{2}\to \min \ \\displaystyle Gini_{{\text{dividir}}}=N-\left({\frac {1}{L}}\cdot \sum_{{i=1}}^{n}l_{i}^ {2}+{\frac {1}{R}}\cdot \sum_{{i=1}}^{n}r_{i}^{2}\right)\to \min \\\displaystyle { \tilde {G}}_{{\text{dividir}}}={\frac {1}{L}}\cdot \sum_{{i=1}}^{n}l_{i}^{2 }+{\frac {1}{R}}\cdot \sum_{{i=1}}^{n}r_{i}^{2}\to \max \end{matriz}}

Como resultado, la mejor partición será aquella para la que el valor sea máximo. Por lo tanto, al construir un “árbol de decisión” utilizando el método CART, se busca una opción de ramificación en la que el valor del indicador Ginisplit(T) disminuya lo más posible .

Mecanismo de recorte

Este mecanismo, llamado poda de árboles de complejidad de costo mínimo (consulte el artículo Poda en la Wikipedia en inglés), el algoritmo CART es fundamentalmente diferente de algunos otros algoritmos de construcción de árboles de decisión. En el algoritmo bajo consideración, la poda es una compensación entre obtener el árbol del "tamaño correcto" y obtener la estimación de clasificación más precisa. La poda (raleo) es importante no solo para simplificar los árboles, sino también para evitar el sobreajuste . El método consiste en obtener una secuencia de árboles decrecientes, pero no se consideran todos los árboles, sino sólo los "mejores representantes". [una]

Validación cruzada

La validación cruzada es la parte más compleja y al mismo tiempo original del algoritmo CART. Es una forma de seleccionar el árbol final, siempre que el conjunto de datos sea pequeño o los registros del conjunto de datos sean tan específicos que no sea posible dividir el conjunto en conjuntos de entrenamiento y prueba [1] .

Ventajas y desventajas del método

ventajas:

Este método es no paramétrico , lo que significa que para su aplicación no es necesario calcular varios parámetros de la distribución de probabilidad.
Para aplicar el algoritmo CART, no es necesario preseleccionar las variables que participarán en el análisis: las variables se seleccionan directamente durante el análisis en función del valor del índice de Gini .
CART combate fácilmente los valores atípicos: el mecanismo de "división" (del inglés Splitting), integrado en el algoritmo, simplemente coloca las "emisiones" en un nodo separado, lo que le permite borrar los datos disponibles del ruido.
Para aplicar este algoritmo, no es necesario tener en cuenta suposiciones o supuestos antes del análisis.
La gran ventaja es la velocidad del algoritmo.

Defectos:

Los árboles de decisión que propone el algoritmo no son estables: el resultado obtenido en una muestra no es reproducible en otra (el árbol puede crecer, encogerse, incluir otros predictores, etc.)
En el caso de que sea necesario construir un árbol con una estructura más compleja, es mejor utilizar otros algoritmos, ya que CART puede no identificar la estructura de datos correcta.

Notas

↑ 1 2 3 Chubukova I. A. Minería de datos. M.: Binom, 2008
↑ Breiman L., Friedman JH, Olshen RA y Stone CJ Clasificación y árboles de regresión. Monterey, CA: Libros y software avanzados de Wadsworth & Brooks/Cole, 1984
↑ Tolstova Yu.N. Análisis de datos sociológicos. M.: Mundo científico, 2000
↑ Árboles de decisión - Aparato matemático CART. Parte #1 // http://www.basegroup.ru/trees/math_cart_part1.htm Archivado el 22 de enero de 2008 en Wayback Machine .
↑ Libro de texto electrónico "Statistica" // http://www.statsoft.ru/home/textbook.htm (enlace inaccesible)

Literatura

Paklin N.B., Oreshkov V.I. Capítulo 9. // Business Analytics: De los Datos al Conocimiento (+CD): Tutorial. 2ª ed.- San Petersburgo. : Pedro, 2013. - S. 459-465. - ISBN 978-5-459-00717-6 .