Construcción y Validación de Árboles de Decisión para Clasificación

Árboles de Decisión para Clasificación

Un árbol de decisión es un método de clasificación donde todas las variables de la matriz de datos, tanto la dependiente como las independientes, deben ser discretas (categóricas o numéricas discretas de dominio finito).

Entropía

Sea P = {p₁, p₂, …, p_H} la distribución de probabilidad asociada a la variable X. Se llama entropía de la variable X, E(X), a la siguiente expresión:

La entropía de la variable X mide el grado de incertidumbre asociado a la misma. Como caso particular, suponga H = 2, es decir, que X puede tomar solo 2 valores (A y B), entonces, la entropía de X viene dada por E(X) = -p*log₂(p) -(1-p)*log₂(1-p).

Algoritmo ID3 para la Construcción de Árboles de Decisión

• Dada la matriz actual, calcular la ganancia de información sobre la variable dependiente cuando se toma en cuenta la información de cada una de las variables independientes.
• Aquella variable independiente que genere la mayor ganancia de información será asignada al nodo actual. Luego, para cada posible valor de esta variable (llámese A) habrá un arco que conecta con un subárbol.
• Suponga que A posee K posibles valores. Para cada posible valor de A se construye una nueva matriz. Ahora, suponga que se desea construir la matriz correspondiente a A = a_i. Esta matriz se obtiene al eliminar la columna A y las filas asociadas a A != a_i.
• La i-ésima (i=1,...,K) matriz obtenida en el paso anterior pasa a ser la matriz actual que será utilizada para construir, recursivamente, el subárbol que comienza en el i-ésimo arco del nodo correspondiente a la variable A.
• Si G(Clase, A) = E(Clase) o si A es la única variable que forma parte de la matriz actual, entonces los arcos salientes de A conducen a nodos hoja.
• El algoritmo se detiene cuando todos los posibles caminos que se pueden recorrer en el árbol conducen a un nodo hoja.

Validación de un Árbol

La construcción de un árbol de decisión no implica ningún tipo de suposiciones, de manera que su validación se limita simplemente a determinar la exactitud de sus resultados, para lo cual se utiliza la matriz de confusión. Esta matriz debe ser elaborada con los resultados del árbol para patrones no utilizados durante la fase de entrenamiento.