Análisis de algoritmo clásico de big data (1) -Algoritmo C4.5

Introducción a la vaca integrada:

C4.5, como algoritmo clásico para procesar big data, es un algoritmo común que debemos comprender al aprender. grandes datos en Internet.

Niubi integrado: Introducción al algoritmo clásico de big data C4.5

Niubi integrado preguntó: ¿Qué tipo de algoritmo es C4.5 y cómo se implementa su mecanismo de toma de decisiones?

Texto de vaca en mosaico:

Modelo de árbol de decisión:

El árbol de decisión es una estructura de árbol que clasifica muestras clasificando atributos de características, incluidos los bordes dirigidos y tres tipos de nodos:

El nodo raíz representa el primer atributo de característica, con solo bordes y sin bordes;

El nodo interno que representa el atributo de característica tiene un borde interno y al menos dos bordes exteriores.

El nodo hoja que representa una categoría tiene solo un borde entrante y ningún borde saliente.

La figura anterior muestra un ejemplo de un árbol de decisión (binario). Los árboles de decisión tienen las siguientes características:

Para los árboles de decisión binarios, pueden considerarse como un conjunto de reglas si-entonces. Los nodos raíz a hoja del árbol de decisión corresponden a una regla de clasificación;

p>

Las reglas de clasificación son mutuamente excluyentes y completas. La llamada exclusión mutua significa que cada registro de muestra no coincidirá con las dos últimas reglas de clasificación al mismo tiempo. La llamada integridad significa que cada registro de muestra puede coincidir con la última regla del árbol de decisión.

La esencia de la clasificación es la división del espacio de características, como se muestra en la siguiente figura.

Aprendizaje del árbol de decisiones:

La esencia del aprendizaje del árbol de decisión es inducir un conjunto de reglas de clasificación a partir del conjunto de datos de entrenamiento [2]. Sin embargo, como el orden de división de los atributos es diferente, el árbol de decisión resultante también será diferente. ¿Cómo conseguir un árbol de decisiones que pueda ajustarse bien a los datos de entrenamiento y predecir bien los datos desconocidos?

Primero, necesitamos resolver dos problemas:

¿Cómo elegir mejores atributos de características para dividir? Cada división de atributos de características equivale a una repartición del conjunto de datos de entrenamiento y corresponde al crecimiento de un árbol de decisión. El algoritmo ID3 define la función objetivo de selección de características.

¿Cuándo debemos dejar de dividirnos? Hay dos situaciones naturales en las que la división debería cesar. Una es que todos los registros de muestra correspondientes al nodo pertenecen a la misma categoría y la otra es que los valores de los atributos característicos de todas las muestras correspondientes al nodo son iguales. Pero más allá de eso, ¿existen otras circunstancias en las que debería detenerse la división?

2. Algoritmo de árbol de decisión

Selección de características

La selección de características se refiere a seleccionar características que maximicen la función objetivo definida. Los siguientes son tres ejemplos de segmentación de características (género, tipo de automóvil, ID de cliente):

Hay dos categorías (C0, C1) en la figura, C0: 6 es el recuento de la categoría C0. Intuitivamente, las características del modelo de vehículo deben seleccionarse para dividir, porque la probabilidad de distribución de su categoría es más inclinada y la incertidumbre de la categoría es menor.

Para medir la inclinación de la probabilidad de distribución de categorías, se define la impureza del nodo tt del árbol de decisión, que cumple con los siguientes requisitos: cuanto menor es la impureza, más inclinada es la probabilidad de distribución de categorías; Los métodos de medición de impurezas se detallan a continuación:

Donde p(ck|t)p(ck|t) representa la probabilidad ckck de la clase tt del nodo del árbol de decisión. Estas tres medidas de impureza son equivalentes y alcanzan su valor máximo en una distribución equiprobable.

Para juzgar el cambio de impureza del nodo antes y después de la división, la función objetivo se define como ganancia de información:

i(?)i(?) corresponde a la impureza de el nodo del árbol de decisión, parentparent representa el nodo principal antes de la división, nn representa el número de registros de muestra contenidos en el nodo principal, aaiai representa los nodos secundarios después de dividir el nodo principal, N (ai) N (ai) es su recuento y NN es el número de nodos secundarios después de la división.

Específicamente, el algoritmo ID3 selecciona el valor de entropía como la impureza I(?)I(?), luego

Cc se refiere a la categoría de todos los registros de muestra correspondientes al nodo principal. ; AA representa los atributos característicos seleccionados, es decir, la colección de aiai.

Entonces, la ganancia de información δ en el aprendizaje del árbol de decisión es equivalente a la información mutua entre clases y características en el conjunto de datos de entrenamiento, lo que indica el grado en que se reduce la incertidumbre del conjunto de datos de entrenamiento cc debido al conocimiento de la información de la característica AA.

Después de la división de características, la cantidad de registros de algunos subnodos puede reducirse, lo que afecta los resultados de la clasificación. Para resolver este problema, el algoritmo CART propone solo la división binaria de características, es decir, el árbol de decisión es un árbol binario. El algoritmo C4.5 mejora la función objetivo de división y utiliza la relación de ganancia de información para seleccionar características:

Por lo tanto, la característica El proceso de selección es equivalente a calcular la ganancia de información de cada característica y seleccionar la característica con la mayor ganancia de información para dividir. Esta es la respuesta a la primera pregunta (elija mejores funciones). El algoritmo ID3 establece un umbral. Cuando la ganancia máxima de información es menor que el umbral, se considera que no se ha encontrado ninguna característica con mejor capacidad de clasificación y no es necesario continuar dividiendo. Según el principio de votación máxima, la categoría con más recuentos se utiliza como este nodo hoja. Esto es para responder a la segunda pregunta planteada anteriormente (las condiciones para detener la división).

Generación de árbol de decisión:

El núcleo del algoritmo ID3 es construir recursivamente un árbol de decisión basado en el criterio de máxima ganancia de información. El flujo del algoritmo es el siguiente:

Si el nodo cumple las condiciones para detener la división (todos los registros pertenecen a la misma categoría o la ganancia máxima de información es menor que el umbral), se establece como un nodo hoja. ;

Seleccione el nodo con la máxima ganancia de información. Las características están segmentadas;

Repita los pasos 1-2 hasta completar la clasificación.

El flujo del algoritmo de C4.5 es similar al de ID3, excepto que la ganancia de información se cambia a la relación de ganancia de información.

3. Poda del árbol de decisión

Sobreajuste

El árbol de decisión generado tendrá un buen efecto de clasificación en los datos de entrenamiento, pero es posible que no funcione bien en datos desconocidos. datos La predicción es inexacta, es decir, el modelo de árbol de decisión se ha sobreajustado: el error de entrenamiento es pequeño y el error de generalización es grande. La siguiente figura muestra cómo el error de entrenamiento y el error de prueba cambian con el número de nodos del árbol de decisión:

Se puede observar que cuando el número de nodos es pequeño, tanto el error de entrenamiento como el error de prueba son grandes. , es decir, se produce un desajuste. Cuando la cantidad de nodos es grande, el error de entrenamiento es pequeño, pero el error de prueba es grande, es decir, se produce un sobreajuste. Solo cuando el número de nodos es moderado, el error de entrenamiento está en el medio y el error de prueba es pequeño, se ajusta bien a los datos de entrenamiento y tiene buena precisión de clasificación para datos desconocidos;

La causa principal del sobreajuste es que el modelo de clasificación es demasiado complejo. Las posibles razones son las siguientes:

Hay puntos de muestra de ruido en el conjunto de datos de entrenamiento, y el ruido también lo hará. se ajustará al ajustar los datos de entrenamiento, lo que afectará el efecto de clasificación;

La falta de registros de muestra con valores de clasificación en los nodos de hoja del árbol de decisión significa que este nodo de hoja debe cortarse.

Estrategia de poda

Para resolver el problema de sobreajuste, C4.5 reduce la complejidad del modelo mediante poda. La literatura [2] propuso una estrategia de poda simple, que se implementa minimizando la función de pérdida general o la función de costo del árbol de decisión. La función de pérdida del árbol de decisión TT es:

donde C(T)C(T) representa el error de entrenamiento del árbol de decisión, α α es el parámetro de ajuste y |T||T| complejidad del modelo. Cuanto más complejo sea el modelo, menor será el error de entrenamiento. La pérdida definida anteriormente es simplemente una compensación entre los dos.

Si la función de pérdida disminuye después de la poda, significa que se trata de una poda eficaz. El algoritmo de poda específico se puede implementar mediante programación dinámica.

4. Referencias

[1] Pang-Tanning, Michael Stanback, Vipin Kumar, "Introducción a la minería de datos".

[2]Li Hang, métodos de aprendizaje estadístico.

[3] Naren Ramakrishnan, Los diez mejores algoritmos en minería de datos.