R-17 Árbol de decisión

Es un modelo de predicción, dividido en árbol de decisión de regresión y árbol de decisión de clasificación. Entrena el modelo de árbol en función de muestras conocidas, prediciendo así las variables dependientes de nuevas muestras según el modelo y obteniendo las predichas. valor o clasificación prevista

La ruta desde el nodo raíz al nodo hoja corresponde a una regla. Todo el árbol de decisión corresponde a un conjunto de reglas de expresión. Los nodos hoja representan los valores predichos obtenidos según esta regla. El modelo de árbol de decisión que se muestra en la figura siguiente obtiene las reglas sobre si el préstamo se puede pagar en función de los tres atributos de propiedad, matrimonio e ingresos mensuales.

El núcleo es cómo seleccionar atributos representativos de muchos atributos como nodos de rama del árbol de decisión.

En el nivel más básico, hay tres indicadores que se pueden utilizar para seleccionar atributos

1. Ganancia de información (algoritmo ID3)

Entropía de información

Los símbolos emitidos por la fuente de información son inciertos y pueden medirse según la probabilidad de su ocurrencia. Cuanto mayor es la probabilidad, mayor es la probabilidad de que ocurra y cuanto menor es la incertidumbre, mayor es la incertidumbre; La función de incertidumbre f es una función decreciente de la probabilidad P. La incertidumbre producida por dos símbolos independientes debe ser igual a la suma de sus respectivas incertidumbres, es decir, f(P1,P2)=f(P1) f(P2), esto se llama aditividad. La función f que satisface estas dos condiciones es una función logarítmica, es decir, en la fuente de información lo que se considera no es la incertidumbre de la ocurrencia de un solo símbolo, sino el promedio de todas las posibles ocurrencias de la fuente de información. Por lo tanto, la entropía de la información se define como

Proceso de clasificación del árbol de decisión

2. Tasa de ganancia (algoritmo C4.5)

La desventaja de la ganancia de información es que tiende a elegir Atributos con una gran cantidad de valores, porque los atributos con una gran cantidad de valores corresponden a menos datos por atributo, tienden a tener mayor pureza de información. Por lo tanto, la tasa de ganancia utiliza la relación entre ganancia de información/entropía del sistema y la entropía del sistema que reemplaza el atributo (similar a la relación de entropía del sistema calculada reemplazando la reproducción con este atributo en un intento de superar esta deficiencia).

g(D, A) representa la ganancia de información del atributo A en el conjunto de datos D,

3. Índice de Gini (algoritmo CART)

Índice de Gini:

p>

representa la probabilidad de que una muestra seleccionada al azar del conjunto de muestras esté mal clasificada. Cuanto más pequeño sea, menor será la probabilidad de que una muestra seleccionada al azar del conjunto de muestras se clasifique erróneamente, es decir, más puro será el conjunto de muestras.

Supongamos que hay K categorías en el conjunto:

Explicación:

1. pk representa la probabilidad de que la muestra seleccionada pertenezca a k categorías, luego la la muestra es incorrecta La probabilidad de clasificación es (1-pk)

2. Hay K categorías en el conjunto de muestras Las muestras seleccionadas aleatoriamente pueden pertenecer a cualquiera de estas K categorías, por lo que las categorías se suman

3. Cuando hay K categorías en el conjunto de muestras, la muestra puede pertenecer a cualquiera de las K categorías. p>

3. Cuando es binario, Gini (P) = 2p (1-p)

El índice de Gini es una partición binaria del atributo A, por lo que se obtiene un árbol binario. Si es un atributo discreto, combine las categorías de los atributos discretos en pares para calcular el índice de Gini.

Ejemplo:

Como se muestra en la figura anterior, la temperatura característica tiene tres valores propios: "caliente", "suave", "fría", "suave", "fría",

Cuando se utiliza la característica "educación" para dividir el conjunto de muestra D, cada uno de los tres valores de división tiene tres valores, por lo que puede haber tres grupos de divisiones, y los subconjuntos son los siguientes:

Para cada grupo de divisiones, calcule el valor de una característica que divide el conjunto de muestra D en un subconjunto del conjunto de muestra D de acuerdo con el valor de la característica de división = "caliente", "suave", y "genial".

La pureza de un determinado valor de característica que divide el conjunto de muestra D en dos subconjuntos:

Proceso de clasificación del número de decisión

Poda primero: deje de construir el árbol por adelantado y pode el árbol, mediante ganancia de información y significación estadística El árbol se construye y se detiene la división adicional cuando el resultado de la división del nodo es inferior al umbral predeterminado del indicador anterior. Sin embargo, determinar el umbral es difícil.

Poda posterior: El método más común es obtener primero el árbol completamente desarrollado y luego reemplazar los nudos con las hojas del nudo más bajo de abajo hacia arriba

CART utiliza el Algoritmo de poda de complejidad de costos: Calcule la complejidad de costos de cada nodo después de la poda y antes de la poda. Si el nodo se poda, la complejidad del costo es menor.

Si la complejidad del costo del nodo es pequeña (la complejidad es una función de los nodos del árbol y la tasa de error del árbol (también conocida como tasa de clasificación errónea)), córtela.

C4.5 usa poda pesimista: la complejidad del costo es similar, pero CART usa el conjunto de poda para evaluar la complejidad del costo, mientras que C4.5 usa el conjunto de entrenamiento más penalización para evaluar la tasa de error

Escalabilidad de los árboles de decisión

ID3\C4.5\CART están diseñados para conjuntos de datos más pequeños y todos limitan las primitivas de entrenamiento para que permanezcan en la memoria nuevamente para resolver la escalabilidad. problema, la gente ha propuesto otros algoritmos, como Rainforest: mantenga un conjunto de AVC para cada atributo que describa las primitivas de entrenamiento de ese nodo, por lo que solo necesita mantener el AVC configurado en la memoria.

Algoritmo de optimización de arranque BOAT: utiliza datos estadísticos para crear muestras más pequeñas de los datos de entrenamiento dados, construye un árbol para cada muestra, forma así múltiples árboles y luego usa estos árboles para construir un nuevo árbol. La ventaja es que se puede actualizar de forma incremental cuando se insertan o eliminan datos, el árbol de decisión solo necesita actualizarse sin reconstruirse.

Minería visual de árboles de decisión

El sistema PBC permite a los usuarios especificar múltiples divisiones, produciendo así múltiples ramas, mientras que el atributo numérico del algoritmo tradicional del árbol de decisión es una división binaria. Y se puede lograr la construcción de árboles interactivos.

rpart usa el algoritmo cart, continuo es "anova"; discreto es "clase"

2) Función para realizar la poda: prune()

3 ) Calcule MAE para evaluar el error del modelo de árbol de regresión. Las muestras aquí se dividen en conjuntos de entrenamiento y conjuntos de prueba, y testdata es el conjunto de prueba

rt.mae es el resultado del modelo de árbol de decisión. en el conjunto de entrenamiento. El error absoluto medio entre el valor previsto de la variable dependiente del conjunto de prueba y el valor real de la variable dependiente del conjunto de prueba.