Matemáticas detrás de los árboles de clasificación y regresión.

¿Alguien puede ayudar a explicar algunas de las matemáticas detrás de la clasificación en CART? Estoy buscando entender cómo ocurren dos etapas principales. Por ejemplo, entrené a un clasificador CART en un conjunto de datos y usé un conjunto de datos de prueba para marcar su rendimiento predictivo pero:

1. ¿Cómo se elige la raíz inicial del árbol?

2. ¿Por qué y cómo se forma cada rama?

Mi conjunto de datos de 400 mil registros con 15 columnas y 23 clases logra una precisión del 100% de una matriz de confusión, utilizo la validación cruzada 10 veces en el conjunto de datos. Estaría realmente agradecido si alguien pudiera ayudar a explicar las etapas de la clasificación CART.

Los árboles CART y de decisión, como los algoritmos, funcionan mediante la partición recursiva del conjunto de entrenamiento para obtener subconjuntos que sean lo más puros posible para una clase objetivo determinada. Cada nodo del árbol está asociado a un conjunto particular de registros que se divide por una prueba específica en una característica. Por ejemplo, una división en un atributo continuo A puede ser inducida por la prueba A ≤ x . El conjunto de registros T se divide en dos subconjuntos que conducen a la rama izquierda del árbol y la derecha.$T$$A$$A \le x$$T$

$T_l = \{ t \in T: t(A) \le x \}$

y

$T_r = \{ t \in T: t(A) > x \}$

De manera similar, una característica categórica puede usarse para inducir divisiones de acuerdo con sus valores. Por ejemplo, si B = { b 1 , ... , b k } cada rama i puede ser inducida por la prueba B = b i .$B$$B = \{b_1, \dots, b_k\}$$i$$B = b_i$

El paso de división del algoritmo recursivo para inducir el árbol de decisión tiene en cuenta todas las divisiones posibles para cada característica e intenta encontrar la mejor según una medida de calidad elegida: el criterio de división. Si su conjunto de datos se induce en el siguiente esquema

$$A_1, \dots, A_m, C$$

donde son atributos y C es la clase objetivo, todas las divisiones de candidatos se generan y evalúan mediante el criterio de división. Las divisiones en atributos continuos y categóricos se generan como se describe anteriormente. La selección de la mejor división generalmente se lleva a cabo mediante medidas de impureza. La impureza del nodo padre tiene que ser disminuida por la división . Sea ( E 1 , E 2 , ... , E k ) una división inducida en el conjunto de registros E , un criterio de división que utiliza la medida de impureza I ( ⋅ ) es:$A_j$$C$$(E_1, E_2, \dots, E_k)$$E$$I(\cdot)$

$$\Delta = I(E) - \sum_{i=1}^{k}\frac{|E_i|}{|E|}I(E_i)$$

Las medidas estándar de impurezas son la entropía de Shannon o el índice de Gini. Más específicamente, CART usa el índice de Gini que se define para el conjunto siguiente manera. Sea p j la fracción de registros en E de la clase c j p j = | { t ∈ E : t [ C ] = c j } $E$$p_j$$E$$c_j$ entonces Gini(E)=1- Q ∑ j=1p 2 j dondeQes el número de clases.

$$p_j = \frac{|\{t \in E:t[C] = c_j\}|}{|E|}$$ $$\mathit{Gini}(E) = 1 - \sum_{j=1}^{Q}p_j^2$$ $Q$

Conduce a una impureza 0 cuando todos los registros pertenecen a la misma clase.

A modo de ejemplo, supongamos que tenemos un conjunto de clases binaria de registros , donde la distribución de clases es ( 1 / 2 , 1 / 2 ) - Lo que sigue es un buen partido para $T$$(1/2, 1/2)$$T$

$T_l$$(1,0)$$T_r$$(0,1)$$T_l$$T_r$$|T_l|/|T| = |T_r|/|T| = 1/2$$\Delta$

$$\Delta = 1 - 1/2^2 - 1/2^2 - 0 - 0 = 1/2$$

$\Delta$

$$\Delta = 1 - 1/2^2 - 1/2^2 - 1/2 \bigg( 1 - (3/4)^2 - (1/4)^2 \bigg) - 1/2 \bigg( 1 - (1/4)^2 - (3/4)^2 \bigg) = 1/2 - 1/2(3/8) - 1/2(3/8) = 1/8$$

La primera división se seleccionará como la mejor división y luego el algoritmo continuará de manera recursiva.

Es fácil clasificar una nueva instancia con un árbol de decisión, de hecho, es suficiente seguir la ruta desde el nodo raíz hasta una hoja. Un registro se clasifica con la clase mayoritaria de la hoja que alcanza.

Digamos que queremos clasificar el cuadrado en esta figura

esa es la representación gráfica de un conjunto de entrenamiento inducido en el esquema $A,B,C$$C$$A$$B$

Un posible árbol de decisión inducido podría ser el siguiente:

Está claro que el cuadrado de registro será clasificado por el árbol de decisión como un círculo dado que el registro cae en una hoja etiquetada con círculos.

En este ejemplo de juguete, la precisión en el conjunto de entrenamiento es del 100% porque el árbol no clasifica incorrectamente ningún registro. En la representación gráfica del conjunto de entrenamiento anterior, podemos ver los límites (líneas discontinuas grises) que el árbol usa para clasificar nuevas instancias.

Hay mucha literatura sobre árboles de decisión, solo quería escribir una introducción incompleta. Otra implementación famosa es C4.5.

No soy un experto en CART, pero puede probar el libro "Elementos de aprendizaje estadístico", que está disponible gratuitamente en línea (consulte el capítulo 9 para CART). Creo que el libro fue escrito por uno de los creadores del algoritmo CART (Friedman).