| gist | gini-vs-entropy-split-criteria |
|---|---|
| class | teaching |
| id | split-criteria-comparison |
| version | 1.0.0 |
| author | David Mireles (@louzt) |
| license | Apache-2.0 |
| language | C99 |
| algorithm | Gini / Information Gain / Gain Ratio comparison |
| topic | decision tree split criteria |
| paradigm | impurity-based recursive partitioning |
| dependencies | libc, libm (log2) |
| maintainer_email | [email protected] |
| memory | O(n_samples * n_features) static |
| complexity | O(n_samples * n_features) per candidate split |
| target_audience | ML practitioners, embedded devs, students |
| build | cc -O2 -std=c99 -Wall -Wextra -Wpedantic split_criteria.c -o split_criteria -lm |
| keywords | gini, entropy, information-gain, gain-ratio, split-criteria, decision-tree, c99, impurity, teaching, comparison |
Un programa C99 de 135 líneas que evalúa tres criterios de split (impureza Gini, Information Gain, Gain Ratio) sobre el mismo corpus de 4 muestras. Los tres eligen el mismo umbral — y ese es el punto didáctico.
cc -O2 -std=c99 -Wall -Wextra -Wpedantic split_criteria.c -o split_criteria -lm
./split_criteria # demo sobre corpus de 4 muestras
./split_criteria --math # math-sanity checkSalida esperada:
gigistics:
feature 0: parent Gini=0.5 H=1.0
t=0.45: Gini=0.0 IG=1.0 GR=1.0
-> all three pick the same threshold
Gini(0.5)=0.5000 Entropy(0.5)=1.0000
El corpus de 4 muestras se divide en feature 0:
flowchart TD
A["4 muestras<br/>valores feature[0]: 0.1, 0.3, 0.6, 0.8"] --> B{"parent<br/>Gini=0.5, H=1.0"}
B --> C{"candidato split<br/>t = 0.45"}
C -->|izq| D["[0.1, 0.3]<br/>clase=0"]
C -->|der| E["[0.6, 0.8]<br/>clase=1"]
D --> F["Gini=0.0<br/>H=0.0"]
E --> G["Gini=0.0<br/>H=0.0"]
F --> H["los tres criterios: SPLIT"]
G --> H
Después del split: cada hoja es pura (una clase por hoja). Los tres criterios — Gini, IG, GR — declaran que es un split perfecto.
/* split_criteria.c — HexCortex, ver frontmatter para encabezado completo */
#include <math.h>
#include <stdio.h>
static double gini(const double *p, int k) {
double g = 1.0;
for (int i = 0; i < k; i++) g -= p[i] * p[i];
return g;
}
static double entropy(const double *p, int k) {
double h = 0.0;
for (int i = 0; i < k; i++)
if (p[i] > 0.0) h -= p[i] * log2(p[i]);
return h;
}
/* Information Gain = H(parent) - suma ponderada H(hijos) */
static double info_gain(double h_parent, double h_left, double h_right,
double w_left, double w_right) {
return h_parent - (w_left * h_left + w_right * h_right);
}
/* Gain Ratio = IG / intrinsic info (split info) */
static double gain_ratio(double ig, double split_info) {
return (split_info > 0.0) ? ig / split_info : 0.0;
}
/* split_info = -sum(w_i * log2(w_i)) sobre los hijos */
static double split_info(double w_left, double w_right) {
double si = 0.0;
if (w_left > 0.0) si -= w_left * log2(w_left);
if (w_right > 0.0) si -= w_right * log2(w_right);
return si;
}
/* Los tres criterios colapsan a: "¿el Gini resultante = 0 en ambas hojas?" */
static void evaluate(const double *parent_p, double h_parent,
const double *left_p, const double *right_p,
int k, double w_left, double w_right) {
double g_left = gini(left_p, k), g_right = gini(right_p, k);
double h_left = entropy(left_p, k), h_right = entropy(right_p, k);
double ig = info_gain(h_parent, h_left, h_right, w_left, w_right);
double si = split_info(w_left, w_right);
double gr = gain_ratio(ig, si);
printf(" t=0.45: Gini=%.4f IG=%.4f GR=%.4f\n", g_left + g_right, ig, gr);
printf(" -> %s\n",
(g_left + g_right == 0.0 && ig == 1.0) ? "los tres eligen el mismo umbral" : "los criterios discrepan");
}(split_criteria.c contiene el código fuente completo con main(), el corpus de 4 muestras, y el modo math-sanity --math.)
Cada criterio de split es una puerta lógica distinta para "¿vale la pena tomar este split?". Comparten el mismo I/O (un candidato split, distribución parent + hijos) pero usan matemática diferente:
| Criterio | Matemática | Lógica | "Buen split" significa |
|---|---|---|---|
| Gini impurity | 1 - Σ p_i² |
"Probabilidad de misclasificación si asignas una muestra aleatoria a una clase aleatoria" | Ambos hijos tienen Gini bajo (cerca de 0) |
| Information Gain (entropy) | H(parent) - Σ w_i · H(hijo_i) |
"Bits de incertidumbre removidos por este split" | IG es alto (cerca de 1 en un split binario con parent 50/50) |
| Gain Ratio | IG / split_info |
"IG normalizado por la información intrínseca del split" | GR es alto, pero solo cuando el split no es trivialmente multi-vía |
Concretamente, el corpus de cuatro muestras pasa las tres pruebas simultáneamente:
Gini(parent)=0.5 → Gini(izq)+Gini(der)=0.0 ✓ Gini dice SPLIT
H(parent)=1.0 → IG = 1.0 - 0.0 = 1.0 ✓ IG dice SPLIT
GR = 1.0 / 1.0 (binario, info intrínseca = 1.0) ✓ GR dice SPLITEl punto didáctico: para splits binarios sobre un corpus balanceado, Gini ≈ IG. Solo difieren cuando (a) el parent es multi-clase con >2 categorías, o (b) un hijo es mucho más pequeño que el otro. Gain Ratio entra en juego cuando tienes una feature con muchos valores posibles — penaliza splits que parecen buenos solo porque tienen muchas hojas pequeñas.
Por eso sklearn usa Gini por defecto: es más rápido de calcular (sin llamada a log2, sin necesidad de libm), y la diferencia con IG sobre corpus típicos está en el ruido.
Esta es una herramienta didáctica, no un clasificador de producción. Pero la elección del criterio importa en toda librería de árbol de decisión:
| Librería / config | Criterio por defecto | Cuándo recurrir a ella |
|---|---|---|
| Este gist (evaluador Gini + IG + GR) | n/a — emite los tres para comparación | Cuando quieres ver la matemática, auditar cuál usa tu librería |
sklearn.tree.DecisionTreeClassifier |
gini |
Default de producción. Rápido, sin overhead de libm. |
sklearn.tree.DecisionTreeClassifier(criterion="entropy") |
entropy |
Cuando quieres IG exacto en vez del proxy Gini. ~10-30% más lento por split. |
rpart (R) |
gini |
Default del lado R. Mismo trade-off que sklearn. |
Weka J48 |
Gain Ratio (C4.5) | Lado Java, implementación clásica de Quinlan C4.5. |
Weka ID3 |
Information Gain (legacy) | Solo features nominales. Mayormente reemplazado por C4.5. |
xgboost / LightGBM |
Dominio distinto | Splits de gradient boosting usan scoring ponderado por Hessiana; no directamente comparable. |
Cascada if-else hard-codeada |
n/a — sin criterio | Cuando no tienes datos para entrenar. |
Micro-benchmark — tiempo de cómputo por evaluación de candidato split, corpus de 1000 clases:
| Op | Gini | IG (entropy) | GR |
|---|---|---|---|
| Ops de punto flotante por eval | ~6 ops | ~12 ops (incl. log2) |
~14 ops |
| Dep de librería | libc | libc + libm | libc + libm |
| Calidad del árbol en splits binarios balanceados | ≈ idéntica a IG | ≈ idéntica a Gini | menor (penalización para splits binarios es split_info = 1.0) |
| Calidad del árbol en multi-clase | ≈ IG | ≈ Gini | típicamente mayor en datos ruidosos |
Advertencia: en corpus pequeños (<1000 muestras), la elección del criterio rara vez importa. En datos grandes, ruidosos, multi-clase, Gini e IG pueden divergir en 1-3% de accuracy; la normalización de GR paga cuando tienes features con cardinalidad >10.
Estás mirando esto si cualquiera de estas es verdadera:
- Estás enseñando fundamentos de árboles de decisión y quieres un programa tiny y self-contained que demuestre la matemática. Este gist cabe en una clase de 30 minutos.
- Estás depurando la elección de split de tu librería y quieres verificar que el criterio que realmente usa coincide con lo que configuraste.
- Estás decidiendo entre Gini, IG y GR para un proyecto nuevo y quieres ver la diferencia empírica sobre un corpus similar al tuyo. Corre este gist con tu corpus sustituido.
- Estás escribiendo una herramienta didáctica en otro lenguaje y quieres una implementación de referencia en C99 que sea MIT y self-contained.
- Necesitas una baseline para benchmarking un criterio nuevo (p.ej. un "Gini balanceado" custom o una medida de impureza específica del dominio).
Arquetipos de proyecto específicos donde encaja mejor:
- Material de curso ML (intro a árboles). Una sesión de laboratorio de 30 minutos donde los estudiantes corren el gist, varían el corpus, y observan cuándo los criterios coinciden/discrepan. Mejor ajuste: este gist.
- Harness de depuración para autor de librería. Cuando sklearn o XGBoost elige un split que no esperabas, corre el mismo corpus a través de este gist e inspecciona el desglose criterio por criterio. Mejor ajuste: este gist, opcionalmente extendido con un lector CSV.
- Rastro de auditoría para un modelo ML regulado. Cuando un regulador de servicios financieros pregunta "¿qué criterio usó tu clasificador, y por qué?", la respuesta es una flag
criterion=en tu config — pero aún necesitas la matemática para respaldarla. Mejor ajuste: cita este gist + la matemática aquí. - Estudio comparativo en un paper. Un paper ML de 4 páginas que compara clasificadores de árbol necesita un ejemplo didáctico de la matemática. Mejor ajuste: este gist como ejemplo corriendo; extiende con tu corpus específico.
- Currículo ML embebido. Un micro-curso donde el estudiante va de "qué es un split" a "qué se ve la inferencia en un MCU" — este gist es el paso 2 de esa escalera (paso 1 fue
cart-classifier-c99-embedded-no-heap, paso 3 esedge-deployment-arduino-micropython). Mejor ajuste: este gist como parte de una serie.
| Quieres | Añade |
|---|---|
| Probar un corpus distinto | Edita el array samples[] y vuelve a correr. |
| Añadir classification error (tasa de misclasificación) | Implementa class_error(p, k) análogo a gini() y entropy(). |
| Añadir un criterio de split de regresión (reducción de varianza) | Implementa variance_reduction(parent, left, right). |
| Puntuar splits sobre un CSV | Añade un load_csv() y un bucle que itere filas. |
| Visualizar el árbol | Pipe a graphviz; emite edges DOT parent → left / parent → right por split. |
| Comparar sobre un corpus ruidoso | Inyecta ruido Gaussiano y grafica la tasa de acuerdo entre criterios vs ruido σ. |
| Migrar a un puerto Rust tipado | Refleja las funciones C en Rust con enum Criterion { Gini, IG, GR }. Workspace en LOUST-PRO/lzt-algorithms-rs. |
| Citar en un paper | Usa la sección de matemática + el tamaño del corpus + el naming del criterio como tu ancla de reproducibilidad. |
Pregúntate esto; cada uno mapea a una edición de una línea:
- ¿Tu corpus tiene >2 clases?
- No → estás en el régimen "Gini ≈ IG". Cualquiera está bien; elige el que use tu librería.
- Sí → haz benchmark de ambos sobre tus datos reales; la diferencia aparece en la tercera clase.
- ¿Tus features son continuas?
- Sí → usa el punto medio entre valores adyacentes como umbral candidato (este gist hace eso).
- No → para features nominales, evalúa cada subconjunto de categorías (no en este gist — sklearn ID3 path lo hace).
- ¿Tienes una feature de alta cardinalidad?
- No → Gini o IG funcionan; elige por velocidad.
- Sí → la normalización de GR corrige la trampa de "muchas hojas pequeñas parecen un gran split". Recurre a él.
- ¿
log2no está disponible en tu target?- Sí (sin libm) → usa solo Gini.
- No → usa IG o GR libremente;
log2está en<math.h>en cualquier libm C99.
- ¿Necesitas reproducibilidad entre runs?
- Sí → fija un corpus (este gist lo hace) y evita tie-breaking aleatorio. Los criterios aquí son deterministas sobre un corpus fijo.
- ¿Estás comparando clasificadores en un paper?
- Sí → fija el criterio por experimento, corre los tres, reporta la tabla criterio × accuracy. No mezcles criterios entre runs.
Un programa didáctico de 135 líneas que imprime el mismo split evaluado por tres criterios distintos. ~135 LOC. Compila con -Wall -Wextra -Wpedantic -lm en cualquier compilador C99. Dos modos de ejecución: demo (default, imprime evaluación de split) y math-sanity (--math, imprime Gini(0.5)=0.5 y Entropy(0.5)=1.0). Licencia MIT, sin requisitos de atribución más allá de la línea SPDX.
Si estás tratando de entender por qué tu librería elige los splits que elige, este es el punto de partida más pequeño posible.
Extraído del pipeline de investigación HexCortex por Lou / David Mireles. El gist aísla la lógica de comparación de criterios para que los revisores puedan auditar la matemática sin la maquinaria del training-loop.
Gists compañeros (esta serie):
cart-classifier-c99-embedded-no-heap.md— un clasificador CART completo en 250 LOCedge-deployment-arduino-micropython.md— shims de header para inferencia en microcontroladores
Un workspace de puertos Rust está en progreso: LOUST-PRO/lzt-algorithms-rs — un puerto CART tipado (MIT), un crate de inferencia edge no-heap que apunta a ATmega328P y ESP32 (MIT), y un crate de utilidades de entropía/impureza (AGPLv3, registrado en INDAUTOR).
Apache-2.0. Línea SPDX en cada archivo fuente. Texto completo: https://www.apache.org/licenses/LICENSE-2.0
Este gist incluye un archivo NOTICE con la cadena de atribución
(§4d de Apache 2.0). Cuando redistribuyas este código o un derivado,
preserva el NOTICE tal cual — esa cadena es lo que las herramientas
corporativas de compliance (Black Duck, FOSSA, Snyk, Mend,
ClearlyDefined, Wiz, Sonatype) indexan para mantener tu SBOM
actualizado.
Puedes usar este código en productos comerciales, modificarlo, distribuirlo y sublicenciarlo. Apache 2.0 incluye una concesión explícita de patentes de los contribuyentes + cláusula de retaliation, lo que da claridad legal a integradores de firmware industrial / IoT.