Unidad 2 PDF - Data Mining - Árboles de decisión

18/10/2024 Instituto Politécnico Nacional Escuela Superior de Cómputo Secretaría Académica Departamento de Ingeniería en Sistemas Computacionales Minería de datos (Data Mining)...

18/10/2024 Instituto Politécnico Nacional Escuela Superior de Cómputo Secretaría Académica Departamento de Ingeniería en Sistemas Computacionales Minería de datos (Data Mining) Árboles de decisión-1ª Parte 1 Profesora: Dra. Fabiola Ocampo Botello 1 Clasificación Han, Kamber & Pei (2012) establecen que la clasificación es una forma de analizar datos para generar modelos que describen importantes clases de datos. Estos modelos se llaman clasificadores, permiten predecir etiquetas de clases 2 categóricas (discretas, desordenadas). Esta foto de Autor desconocido está bajo licencia CC BY-NC-ND Data Mining. ESCOM-IPN. Dra. Fabiola Ocampo Botello 2 1  18/10/2024 Clasificación (Continuación) Por ejemplo, se puede construir un modelo de clasificación para categorizar las solicitudes de préstamos bancarios como seguras o riesgosas. La clasificación tiene numerosas aplicaciones, incluida la detección de fraudes, el marketing de 3 objetivos, la predicción del rendimiento, la fabricación y el diagnóstico médico (Han, Esta foto de Autor desconocido está bajo licencia CC BY-SA Kamber & Pei, 2012). Data Mining. ESCOM-IPN. Dra. Fabiola Ocampo Botello 3 Definición de clasificación: Es la tarea de aprendizaje que 4 considera una función f que asocia cada conjunto de atributos x a una de las clases predefinidas y etiquetas en y. (Tan, Steinbach, Karpatne & Kumar, 2005). Esta foto de Autor desconocido está bajo licencia CC BY-SA Data Mining. ESCOM-IPN. Dra. Fabiola Ocampo Botello 4 2  18/10/2024 Esta función f es conocida de manera informal como modelo de 5 clasificación. Un modelo de clasificación es útil por las siguientes razones (Tan, Steinbach, Karpatne & Kumar, 2005). Modelo descriptivo. Un Modelo de predicción. Un modelo de clasificación puede modelo de clasificación puede servir como una herramienta servir para predecir la para distinguir objetos de etiqueta de clase de un diferentes clases. registro desconocido. Las técnicas de clasificación son más adecuadas para predecir o describir conjuntos de datos de categorías binarias o nominales. Son menos efectivas en categorías ordinales porque no consideran el orden jerárquico de los grupos. Data Mining. ESCOM-IPN. Dra. Fabiola Ocampo Botello 5 Enfoque de la clasificación La clasificación de datos es un proceso de dos pasos (Han, Kamber & Pei, 2012): Un segundo paso El primer paso (clasificación), en el cual (aprendizaje), se el modelo se usa para construye un modelo de 6 predecir etiquetas de clasificación clase para otros datos. Data Mining. ESCOM-IPN. Dra. Fabiola Ocampo Botello 6 3  18/10/2024 Primer paso. Aprendizaje. 7 (Han, Kamber & Pei, 2012) Este es el paso de aprendizaje (o fase de entrenamiento) Un algoritmo de clasificación construye el clasificador analizando o "aprendiendo de" Cada tupla, X, pertenece a una clase un conjunto de entrenamiento compuesto predefinida determinada por otro por tuplas de base de datos y sus etiquetas atributo de base de datos de clase asociadas. denominado atributo de etiqueta de clase. Una tupla, X, está representada por un vector de atributos de n dimensiones, El atributo de etiqueta de clase tiene un valor discreto y no está ordenado. X = {x1, x2, …, xn}, Es categórico (o nominal) en el sentido de que cada valor sirve como que representa las n mediciones realizadas categoría o clase. en la tupla que contiene n atributos de la base de datos, respectivamente, A1, A2, …, An. Data Mining. ESCOM-IPN. Dra. Fabiola Ocampo Botello 7 Primer paso. Aprendizaje (continúa). 8 (Han, Kamber & Pei, 2012) - Debido a que se proporciona la etiqueta de clase de cada tupla de entrenamiento, este paso también se conoce como aprendizaje supervisado. - Supervisado expresa, que la clasificación se "supervisa“, esto es, se le dice a qué clase pertenece cada tupla de entrenamiento. - Contrasta con el aprendizaje no supervisado (o agrupamiento), en el que no se conoce la etiqueta de clase de cada tupla de entrenamiento y es posible que no se conozca de antemano el número o conjunto de clases que se deben aprender. Data Mining. ESCOM-IPN. Dra. Fabiola Ocampo Botello 8 4  18/10/2024 Primer paso. Aprendizaje (continúa). 9 (Han, Kamber & Pei, 2012) Este primer paso del proceso de clasificación también puede verse como el aprendizaje de un mapeo o función, y = f(X) que puede predecir la etiqueta de clase asociada y de una tupla X dada. En esta vista, se desea aprender un mapeo o función que separa las clases de datos. Normalmente, este mapeo se representa en forma de reglas de clasificación, árboles de decisión o fórmulas matemáticas. Las reglas se pueden utilizar para categorizar futuras tuplas de datos, así como para proporcionar una visión más profunda del contenido de los datos. Data Mining. ESCOM-IPN. Dra. Fabiola Ocampo Botello 9 Segundo paso. Clasificación. 10 (Han, Kamber & Pei, 2012) En el segundo paso se considera: - El modelo se utiliza para la clasificación. - Primero, se estima la precisión predictiva del clasificador. - Si se usara el conjunto de entrenamiento para medir la precisión del clasificador, esta estimación probablemente sería optimista. - Por lo tanto, se utiliza un conjunto de prueba, formado por tuplas de prueba y sus etiquetas de clase asociadas. Son independientes de las tuplas de entrenamiento, lo que significa que no se utilizaron para construir el clasificador. Data Mining. ESCOM-IPN. Dra. Fabiola Ocampo Botello 10 5  18/10/2024 Segundo paso. Clasificación (continuación). 11 (Han, Kamber & Pei, 2012) - La precisión de un clasificador en un conjunto de prueba dado es el porcentaje de tuplas de conjuntos de prueba que el clasificador clasifica correctamente. - La etiqueta de clase asociada de cada tupla de prueba se compara con la predicción de clase del clasificador aprendido para esa tupla. - Si la precisión del clasificador se considera aceptable, el clasificador se puede utilizar para clasificar tuplas de datos futuras para las que no se conoce la etiqueta de clase. (Estos datos también se denominan en la literatura sobre aprendizaje automático (machine learning) como datos "desconocidos" o "no vistos anteriormente"). Data Mining. ESCOM-IPN. Dra. Fabiola Ocampo Botello 11 Clasificación La clasificación se refiere a la tarea de asignar objetos a una de varias categorías predefinidas. La entrada de datos para la clasificación se compone de una serie de registros, donde cada registro representa una instancia y se caracteriza por ser una tupla (x, y) donde x es el conjunto de atributos y y es un atributo especial, la etiqueta de la clase. Por ejemplo, suponga que se tiene la clase persona* de la Escuela: 12 profesor, alumnos, paae y administradores. El conjunto de atributos (x) contiene los datos identificados de las personas y la variable y es de tipo discreta que representa las diversas clases o categorías que puede tener x. * Imagine una clase disjunta, total. En el que todos las subclases tienen los mismos atributos. Data Mining. ESCOM-IPN. Dra. Fabiola Ocampo Botello 12 6  18/10/2024 Los árboles de decisión son una de las técnicas de clasificación. Proceso para construir un modelo de clasificación Datos fuente Algo d1 d2 D3 Tipo 12.23 Ta R 12 P Algoritmo 25.6 tu T 15 A de 45.7 po P 47 PAE aprendizaje 88.2 be O 56 Ad 45.9 mi I 91 A Modelo de Fuente: Elaboración propia. aprendizaje Modelo Limpieza, codificación, tratamiento 13 de datos Utilizar el TipoP modelo Algo d1 d2 D3 Tipo 88.2 be O 56 Ad Ad 45.9 mi l 91 A A Banco de datos Data Mining. ESCOM-IPN. Dra. Fabiola Ocampo Botello 13 Rokach, L. & Maimon, O. (2015) establecen que la meta de un algoritmo de clasificación se puede definir formalmente como: Dado un conjunto de entrenamiento S con atributos de entrada A = {a1, a2,... , an} y un atributo nominal y y una distribución desconocida D, la meta es inducir un clasificador óptimo con el mínimo error de generalización. Notación: DT Representa el inductor del árbol de decisión. DT(S) Representa un árbol de clasificación que se generó al 14 ejecutar DT sobre el conjunto de datos S. DT(S)(xq) Es la predicción de xq usando DT(S). Data Mining. ESCOM-IPN. Dra. Fabiola Ocampo Botello 14 7  18/10/2024 La evaluación del desempeño de un modelo de clasificación considera dos aspectos: 1. La cantidad de registros previstos por el modelo de forma adecuada. 2. La cantidad de registros previstos por el modelo de forma inadecuada. Lo anterior se presenta en una matriz de confusión. Clase prevista Ejemplo de una matriz de confusión: Clase 1 Clase 0 Clase actual Clase 1 f11 f10 Clase 0 f01 f00 𝑁ú𝑚𝑒𝑟𝑜 𝑑𝑒 𝑝𝑟𝑒𝑑𝑖𝑐𝑐𝑖𝑜𝑛𝑒𝑠 𝑐𝑜𝑟𝑟𝑒𝑐𝑡𝑎𝑠 15 Exactitud (Accuracy) = 𝑁ú𝑚𝑒𝑟𝑜 𝑡𝑜𝑡𝑎𝑙 𝑑𝑒 𝑝𝑟𝑒𝑑𝑖𝑐𝑐𝑖𝑜𝑛𝑒𝑠 Accuracy = 𝑓11+𝑓00 𝑓11+𝑓10+𝑓01+𝑓00 𝑁ú𝑚𝑒𝑟𝑜 𝑑𝑒 𝑝𝑟𝑒𝑑𝑖𝑐𝑐𝑖𝑜𝑛𝑒𝑠 𝑖𝑛𝑐𝑜𝑟𝑟𝑒𝑐𝑡𝑎𝑠 𝑓10+𝑓01 Tasa de erros (E𝑟𝑟𝑜𝑟 𝑟𝑎𝑡𝑒) = Error rate = 𝑁ú𝑚𝑒𝑟𝑜 𝑡𝑜𝑡𝑎𝑙 𝑑𝑒 𝑝𝑟𝑒𝑑𝑖𝑐𝑐𝑖𝑜𝑛𝑒𝑠 𝑓11+𝑓10+𝑓01+𝑓00 Data Mining. ESCOM-IPN. Dra. Fabiola Ocampo Botello 15 16 Árboles de decisión Han, Kamber & Pei (2012) establecen que Un árbol de decisión es una estructura de árbol similar a un diagrama de flujo, donde cada nodo interno (nodo no hoja) denota una prueba en un atributo, cada rama representa un resultado de la prueba y cada nodo hoja (o nodo terminal) tiene una etiqueta de clase. Los nodos internos se indican con rectángulos y los nodos de hoja se indican con óvalos. Algunos algoritmos de árboles de decisión producen solo árboles binarios (donde cada nodo interno se ramifica exactamente a otros dos nodos), mientras que otros pueden producir árboles no binarios. Data Mining. ESCOM-IPN. Dra. Fabiola Ocampo Botello 16 8  18/10/2024 Referencias bibliográficas Han, Jiawei; Kamber, Micheline & Pei, Jian. (2012). Data Mining: concepts and techniques. Third edition. Morgan Kaufman Series. Rokach, L. & Maimon, O. (2015). Data Mining with decision trees. Theory and Applications. Second Edition. World Scientific Publishing Co. Pte. Ltd. Tan Pang-Ning, Steinbach Michael, Karpatne Anuj, Kumar Vipin. (2005). Introduction to data mining. Second Edition. Pearson 17 Data Mining. ESCOM-IPN. Dra. Fabiola Ocampo Botello 17 9  21/10/2024 Instituto Politécnico Nacional Escuela Superior de Cómputo Secretaría Académica Departamento de Ingeniería en Sistemas Computacionales Minería de datos (Data Mining) Medidas de particionamiento en árboles de decisión 1 Profesora: Dra. Fabiola Ocampo Botello Bhumika, Aditya, Akshay, Arpit & Naresh (2017) diversas medidas para la selección de atributos para dividir las tuplas en un árbol. La medida de selección de atributos determina cómo dividir las tuplas en un nodo dado y, por lo tanto, también se conocen como reglas de división. El nodo de árbol para la partición está etiquetado con el criterio de división, las ramas se generan para cada resultado del criterio y las tuplas se dividen en consecuencia. 2 Las medidas de selección de atributos más populares son: entropía (ganancia de información), relación de ganancia e índice de Gini. Data Mining. ESCOM-IPN. Dra. Fabiola Ocampo Botello 1  21/10/2024 Sancho Capparini, Fernando (2009) indica que el árbol ID3 usa el concepto de Ganancia de Información para seleccionar el atributo más útil en cada paso. Utiliza un método voraz para decidir la pregunta que mayor ganancia proporcione en cada paso, esto es, aquella que permite separar mejor los ejemplos respecto a la clasificación 3 final. Esta foto de Autor desconocido está bajo licencia CC BY-SA La estrategia básica del ID3 es elegir los atributos de particionamiento con la mayor información. Data Mining. ESCOM-IPN. Dra. Fabiola Ocampo Botello Entropía (Entropy) La entropía es una medida de incertidumbre asociada con una variable aleatoria. La entropía aumenta con el aumento de la incertidumbre o aleatoriedad y disminuye con una disminución de la incertidumbre o aleatoriedad. El valor de la entropía varía de 0 a 1. 𝑐 𝐸𝑛𝑡𝑟𝑜𝑝í𝑎 𝐷 = 𝐸(𝐷) = ෍– 𝑝𝑖 𝐿𝑜𝑔2 (𝑝𝑖) 𝑖=1 donde pi es la probabilidad distinta de cero de que una tupla arbitraria en 4 D pertenezca a la clase C y se estima mediante |Ci,D|/|D|. Se utiliza una función de registro de la base 2 porque, como se indicó anteriormente, la entropía está codificada en los bits 0 y 1. (Bhumika et al., 2017) Data Mining. ESCOM-IPN. Dra. Fabiola Ocampo Botello 2  21/10/2024 El concepto usado para cuantificar la información se llama entropía. La entropía es usada para medir la cantidad de incertidumbre en un conjunto de datos. Sancho Capparini, Fernando (2009) presenta dos ejemplos para comprender la incertidumbre: 1. En una muestra totalmente homogénea, en la que todos los elementos se clasifican por igual tiene una incertidumbre mínima, esto es, no se tienen dudas de cuál es la clasificación de cualquiera de sus elementos. En este caso la incertidumbre (entropía) es cero. 2. En una muestra igualmente distribuida en el que se tienen el mismo 5 número de casos en cada posible clasificación tiene una incertidumbre máxima. En este caso, la incertidumbre (entropía) es 1. Data Mining. ESCOM-IPN. Dra. Fabiola Ocampo Botello Ganancia de Información (Information Gain) ID3 utiliza la ganancia de información como su medida de selección de atributos. La ganancia de información es la diferencia entre el requisito de ganancia de información original (es decir, basado solo en la proporción de clases) y el nuevo requisito (es decir, obtenido después de la división de A). (Bhumika, et al., 2017). Dónde, D: una partición de datos dada D se divide en v partición o 6 subconjuntos, {D1, D2,.. Dj} donde A: atributo V: Supongamos que dividimos Dj contiene esas tuplas en D que las tuplas en D en algún tienen el resultado aj de A. atributo A que tiene v valores Se elige el atributo que tiene la distintos mayor ganancia de información. Data Mining. ESCOM-IPN. Dra. Fabiola Ocampo Botello 3  21/10/2024 Cuando todos los elementos pertenecen a la misma clase, la entropía es cero. La intención de un árbol es realizar particiones del conjunto de datos con la finalidad de que todos los elementos del subconjunto final pertenezcan a la misma clase (pureza). La incertidumbre es máxima cuando los dos eventos tienen la misma probabilidad de ocurrencia. ID3 elige el atributo de división con la mayor ganancia de información, donde la ganancia se define como la diferencia entre cuánta información se necesita para hacer una clasificación correcta antes de la división y cuánta información se necesita 7 después de la división (Dunham, 2002). p(0.3, 0.7) p(0.5, 0.5) p(0.2, 0.8) p(0, 1.0) Data Mining. ESCOM-IPN. Dra. Fabiola Ocampo Botello Tan et al., (2005) establecen que para determinar la bondad de una condición de prueba de atributo, necesitamos comparar el grado de impureza del nodo primario (antes de dividir) con el grado ponderado de impureza de los nodos secundarios (después de dividir). Cuanto mayor sea su diferencia, mejor será la condición de la prueba. Esta diferencia, Δ, también denominada ganancia de pureza de una condición de prueba de atributo, se puede definir de la siguiente manera: 8 El algoritmo de aprendizaje del árbol de decisión selecciona la condición de prueba de atributo que muestra la máxima ganancia. Data Mining. ESCOM-IPN. Dra. Fabiola Ocampo Botello 4  21/10/2024 Los pasos a seguir son los siguientes (Sancho Capparini, Fernando (2009)): Paso Descripción Se calcula la entropía total. 𝑐 1 𝐸 𝑠 = ෍– 𝑝𝑖 𝐿𝑜𝑔2 (𝑝𝑖) 𝑖=1 2 Se divide el conjunto de datos en términos de los diversos atributos. Se calcula la entropía de cada rama y se suman proporcionalmente las ramas para calcular la entropía del total 3 𝐸 𝑇, 𝑋 = ෍ 𝑝 𝑐 𝐸(𝑆𝑐) c∈𝑥 9 Se resta este resultado de la entropía original, se obtiene como resultado la 4 Ganancia de Información (descenso de entropía) usando este atributo. 𝐺𝑎𝑖𝑛 𝑇, 𝑋 = 𝐸 𝑇 − 𝐸(𝑇, 𝑋) 5 El atributo con mayor Ganancia se elige como nodo de decisión. Data Mining. ESCOM-IPN. Dra. Fabiola Ocampo Botello Ejemplo de la aplicación de la ganancia de información y entropía (ejemplo tomado de Sancho Capparini, Fernando (2009)). Aplicado al conjunto de datos del juego de Golf. JuegaGolf Panorama Temperatura Humedad Viento No Lluvioso Caliente Alta FALSO Jugar Golf No Lluvioso Caliente Alta VERDADERO SI NO Si Nublado Caliente Alta FALSO 9 5 Si Soleado Templado Alta FALSO Si Soleado Frío Normal FALSO No Soleado Frío Normal VERDADERO Si Nublado Frío Normal VERDADERO No Lluvioso Templado Alta FALSO Si Lluvioso Frío Normal FALSO 10 Si Soleado Templado Normal FALSO Si Lluvioso Templado Normal VERDADERO Si Nublado Templado Alta VERDADERO Si Nublado Caliente Normal FALSO No Soleado Templado Alta VERDADERO Data Mining. ESCOM-IPN. Dra. Fabiola Ocampo Botello 5  21/10/2024 PASO 1. Cálculo de la entropía total 𝑐 𝐸 𝑠 = ෍– 𝑝𝑖 𝐿𝑜𝑔2 (𝑝𝑖) Jugar Golf 𝑖=1 SI NO 9 5 E(Jugar Golf) = E(No, Si) = E(5,9) = (-5/14 Log2 (5/14)) + (-9/14 Log2 (9/14)) = (-0.36 Log2 (0.36)) + (-0.64 Log2 (0.64)) 11 = 0.53 + 0.40 = 0.94 --> Entropía total Data Mining. ESCOM-IPN. Dra. Fabiola Ocampo Botello PASO 2. Dividir el conjunto de datos en los diversos atributos. Atributo Objetivo: Jugar Golf Atributo Dominio Panorama Lluvioso Nublado Soleado Temperatura Caliente Frío Templado 12 Humedad Normal Alta Viento Falso Verdadero Data Mining. ESCOM-IPN. Dra. Fabiola Ocampo Botello 6  21/10/2024 PASO 3. Se calcula la entropía en cada rama y se suman proporcionalmente para calcular la entropía total: Count Panorama Lluvioso JuegaGolf No 3 E(Soleado) = E(No, Si) = E(2,3) = (-2/14 Log2 𝐸 𝑇, 𝑋 = ෍ 𝑝 𝑐 𝐸(𝐶) Si 2 (2/14)) + (-3/14 Log2 (3/14)) Nublado JuegaGolf Si 4 = (-0.14 Log2 (0.14)) + (-0.21 Log2 (0.21)) c∈𝑥 Soleado JuegaGolf No 2 = 0.40 + 0.47 = 0.97 --> Entropía Soleado Si 3 Para panorama: E(Jugar Golf, Panorama) = P(Lluvioso) * E(3,2) + P(Nublado) * E(4,0) + P(Soleado) * E(2,3) -Lluvioso: P(5/14) = 0.36 E(3,2) = 0.44 + 0.53 = 0.971 -Nublado: P(4/14) = 0.29 E(4,0) = 0 -Soleado: P(5/14) = 0.36 E(2,3) = 0.971 13 E(Jugar Golf, Panorama) = 0.36 * 0.971 + 0.29 * 0 + 0.36 * 0.971 = 0.35 + 0 + 0.35 = 0.70 GAIN = 0.94 - 0.70 = 0.247 𝐺𝑎𝑖𝑛 𝑇, 𝑋 = 𝐸 𝑇 − 𝐸(𝑇, 𝑋) PASO 4. Ganancia de información Data Mining. ESCOM-IPN. Dra. Fabiola Ocampo Botello Para temperatura: E(Jugar Golf, Temperatura) = P(Caliente) * E(2,2) + P(Frío) * E(1,3) + P(Templado) * E(2,4) -Caliente: P(4/14) = 0.29 E(2,2) = 0.5 + 0.5 = 1 -Frío: P(4/14) = 0.29 E(1,3) = 0.5 + 0.31 = 0.81 -Templado: P(6/14) = 0.43 E(2,4) = 0.53 + 0.39 = 0.92 E(Jugar Golf, Temperatura) = 0.29 * 1 + 0.29 * 0.81 + 0.43 * 0.92 = 0.29 + 0.2349 + 0.39 = 0.91 GAIN = 0.94 - 0.91 = 0.03 Count PASO 4. Ganancia de información 14 Temp Caliente JuegaGolf No 2 Si 2 Frio JuegaGolf No 1 Si 3 Templado JuegaGolf No 2 Si 4 Data Mining. ESCOM-IPN. Dra. Fabiola Ocampo Botello 7  21/10/2024 Para humedad: E(Jugar Golf, Humedad) = P(Normal) * E(1,6) + P(Alta) * E(4,3) -Normal: P(7/14) = 0.50 E(1,6) = 0.40 + 0.19 = 0.59 -Alta: P(7/14) = 0.50 E(4,3) = 0.46 + 0.52 = 0.98 E(Jugar Golf, Humedad) = 0.50 * 0.59 + 0.50 * 0.98 = 0.295 + 0.49 = 0.785 GAIN = 0.94 - 0.785 = 0.155 PASO 4. Ganancia de información 15 Count Humedad Alta JuegaGolf No 4 Si 3 Normal JuegaGolf No 1 Si 6 Data Mining. ESCOM-IPN. Dra. Fabiola Ocampo Botello Para viento: E(Jugar Golf, viento) = P(Falso) * E(6,2) + P(Verdadero) * E(3,3) -Falso: P(8/14) = 0.57 E(6,2) = 0.31 + 0.50 = 0.81 -Verdadero: P(6/14) = 0.43 E(3,3) = 0.50 + 0.50 = 1 E(Jugar Golf, Viento) = 0.57 * 0.81 + 0.43 * 1 = 0.46 + 0.43 = 0.89 GAIN = 0.94 - 0.89 = 0.05 PASO 4. Ganancia de información Count Viento Falso JuegaGolf No 2 Si 6 16 Verdadero JuegaGolf No 3 Si 3 Data Mining. ESCOM-IPN. Dra. Fabiola Ocampo Botello 8  21/10/2024 PASO 5. Elegir el atributo con mayor Ganancia de información Variable Ganancia (Si, No) Panorama 0.247 Lluvioso = (3,2). Nublado = (4,0). Soleado = (2,3) Temperatura 0.03 Caliente = (2,2). Frío = (1,3). Templado = (2,4) Humedad 0.155 Normal = (1,6). Alta = (4,3) Viento 0.05 Falso = (6,2). Verdadero = (3,3) Panorama es la variable que brinda la mayor ganancia de información, 17 por tal, será la primera en ser elegida. Data Mining. ESCOM-IPN. Dra. Fabiola Ocampo Botello Gain Ratio Bhumika, et al (2017) establece que la medida de ganancia de información está sesgada hacia pruebas con muchos resultados. Es decir, prefiere seleccionar atributos que tengan una gran cantidad de valores. Como cada partición es pura, la ganancia de información por partición es máxima. Pero tal partición no puede usarse para la clasificación. C4.5 (un sucesor de ID3) utiliza esta medida de selección de atributo denominada Gain Ratio, que es una extensión de la ganancia de información (Bhumika, et al., 2017). 18 La relación de ganancia (Gain Ratio) se define entonces como: Data Mining. ESCOM-IPN. Dra. Fabiola Ocampo Botello 9  21/10/2024 Gini Index El índice de Gini es una medida de selección de atributos utilizada por el algoritmo del árbol de decisiones CART. El índice de Gini mide la impureza D, una partición de datos o un conjunto de tuplas de entrenamiento como (Bhumika et al., 2017): Donde pi es la probabilidad de que una tupla en D pertenezca a la clase Ci y se estima mediante |Ci, D|/|D|. La suma se calcula sobre m 19 clases. El atributo que reduce la impureza al nivel máximo (o tiene el índice mínimo de Gini) se selecciona como el atributo de división (Bhumika et al., 2017). Data Mining. ESCOM-IPN. Dra. Fabiola Ocampo Botello Ejemplo propuesto por: Bhumika, et al (2017). Ejemplo de la base de datos de una tienda electrónica para ver si una persona compra una computadora portátil o no. El atributo con etiqueta de clase compra _laptop, tiene dos valores distintos (sí, no). Por lo tanto, hay dos clases distintas y el valor de m es igual a 2. Clase P: buys_laptop = "yes" Clase N: buys_laptop = ”no” Como hay 9 sí y 5 no en el atributo buys_laptop, por lo tanto, 9 tuplas 20 pertenecen a la clase P y 5 tuplas pertenecen a la clase N. Data Mining. ESCOM-IPN. Dra. Fabiola Ocampo Botello 10  21/10/2024 Imagen tomada del artículo: Bhumika Gupta, Aditya Rawat, Akshay Jain, Arpit Arora, Naresh Dhami. (2017). Analysis of Various Decision Tree Algorithms for Classification in Data Mining. International Journal of Computer Applications (0975–8887). Volume 163 – No 8, April 2017. 21 Data Mining. ESCOM-IPN. Dra. Fabiola Ocampo Botello Tan et al. (2005) establece que hay medidas que pueden usarse para determinar la bondad de una condición de prueba de un atributo. Estas medidas intentan dar preferencia a las condiciones de prueba de atributos que dividen las instancias de entrenamiento en subconjuntos puros en los nodos secundarios. La impureza de un nodo mide qué tan diferentes son las etiquetas de clase para las instancias de datos que pertenecen a un nodo común. Las medidas para evaluar la impureza de un nodo: 22 Imagen tomada de Tan et al., (2005) Data Mining. ESCOM-IPN. Dra. Fabiola Ocampo Botello 11  21/10/2024 Ejemplos de cálculo de impureza: 23 Ejemplo tomado de Tan et al., (2005) Data Mining. ESCOM-IPN. Dra. Fabiola Ocampo Botello Rokach & Maimon (2015) establecen los siguientes criterios de detención del crecimiento: - Todas las instancias en el conjunto de entrenamiento pertenecen a un solo valor de y (clase). - Se ha alcanzado la profundidad máxima del árbol. - El número de casos en el nodo terminal es menor que el número mínimo de casos para los nodos principales (padres). Los mismos autores señalan que evaluar el desempeño de un árbol de clasificación es una tarea fundamental en el aprendizaje automático. Algunos de los criterios que presentan son: 24 - La matriz de confusión, la cual presenta la cantidad de elementos que han sido clasificados correcta e incorrectamente. - El coeficiente de determinación. Data Mining. ESCOM-IPN. Dra. Fabiola Ocampo Botello 12  21/10/2024 Poda de árboles Rokach & Maimon (2015) establecen que el empleo de criterios estrictos de detención tiende a crear árboles de decisión pequeños y mal balanceados. Por otro lado, el uso de otros criterios de detención tiende a generar grandes árboles de decisión que están sobreajustados para el conjunto de entrenamiento. Breiman et al. (1984, citado en Rokach & Maimon, 2015) desarrolló una metodología de poda basada en un criterio de detención que permite que el árbol de decisión sobreajuste el conjunto de entrenamiento, en 25 donde el árbol sobreajustado se corta en un árbol más pequeño eliminando las subramas que no contribuyen a la precisión de la generalización. Data Mining. ESCOM-IPN. Dra. Fabiola Ocampo Botello Referencias bibliográficas Bhumika Gupta, Aditya Rawat, Akshay Jain, Arpit Arora, Naresh Dhami. (2017). Analysis of Various Decision Tree Algorithms for Classification in Data Mining. International Journal of Computer Applications (0975–8887). Volume 163 – No 8, April 2017. Dunham, M. H. (2002). Data mining: introductory and advanced topics. Prentice Hall. Rokach, L. & Maimon, O. (2015). Data Mining with decision trees. Theory and Applications. Second Edition. World Scientific Publishing Co. Pte. Ltd. Sancho Capparini, Fernando (2009). Aprendizaje inductivo. Arboles de decisión. Portal Web. Disponible en: http://www.cs.us.es/~fsancho/?e=104 Tan Pang-Ning, Steinbach Michael, Kumar Vipin. (2005). Introduction to data mining. First Edition. Pearson New International Edition. 26 Data Mining. ESCOM-IPN. Dra. Fabiola Ocampo Botello 13  18/10/2024 Instituto Politécnico Nacional Escuela Superior de Cómputo Secretaría Académica Departamento de Ingeniería en Sistemas Computacionales Minería de datos (Data Mining) Tipos de Árboles de decisión 1 Profesora: Dra. Fabiola Ocampo Botello 1 Algoritmo ID3 Rokach & Maimon (2015) y Bhumika, Aditya, Akshay, Arpit & Naresh (2017) establecen que el ID3 tiene las siguientes características: - Es un algoritmo desarrollado por Ross Quinlan. - Sólo acepta atributos categóricos - Usa la ganancia de información como criterio de división. - Deja de crecer cuando: o Todas las instancias pertenecen a un solo 2 valor de una característica objetivo o o Cuando la mejor ganancia de información no es mayor que cero. - No aplica ningún procedimiento de poda. Esta foto de Autor desconocido está bajo licencia CC BY-SA - No maneja atributos numéricos o valores faltantes. Data Mining. ESCOM-IPN. Dra. Fabiola Ocampo Botello 2 1  18/10/2024 Continuación ID3 Rokach & Maimon (2015) mencionan que el ID3 tiene varias desventajas: - No garantiza una solución óptima. ID3 significa algoritmo - Puede sobreajustar los datos de entrenamiento. iterativo de dicotomizador 3 - Está diseñado para atributos nominales. 3 Esta foto de Autor desconocido está bajo licencia CC BY-NC Data Mining. ESCOM-IPN. Dra. Fabiola Ocampo Botello 3 Continuación ID3 Dunham (2002) presenta las siguientes características del algoritmo ID3: - La técnica ID3 para construir un árbol de decisión se basa en la teoría de la información y los intentos de minimizar el número esperado de comparaciones. - La idea básica del algoritmo de inducción es hacer preguntas cuyas respuestas brinden la mayor cantidad de información. - La estrategia básica utilizada por ID3 es elegir primero la división de atributos con la mayor ganancia de información. - La cantidad de información asociada con un valor de atributo está 4 relacionada con la probabilidad de ocurrencia. - El concepto utilizado para cuantificar la información se llama entropía. La entropía se usa para medir la cantidad de incertidumbre o sorpresa o aleatoriedad en un conjunto de datos. Data Mining. ESCOM-IPN. Dra. Fabiola Ocampo Botello 4 2  18/10/2024 Continuación ID3 Ejemplo de un árbol ID3: Tomando como referencia las características climáticas, un modelo que generalice las condiciones necesarias para determinar la posibilidad de ir o no a 5 jugar golf. Esta foto de Autor desconocido está bajo licencia CC BY-SA Data Mining. ESCOM-IPN. Dra. Fabiola Ocampo Botello 5 Continuación ID3 JuegaGolf Panorama Temperatura Humedad Viento No Lluvioso Caliente Alta FALSO No Lluvioso Caliente Alta VERDADERO Si Nublado Caliente Alta FALSO Si Soleado Templado Alta FALSO Si Soleado Frío Normal FALSO No Soleado Frío Normal VERDADERO Si Nublado Frío Normal VERDADERO No Lluvioso Templado Alta FALSO Si Lluvioso Frío Normal FALSO 6 Si Soleado Templado Normal FALSO Si Lluvioso Templado Normal VERDADERO Si Nublado Templado Alta VERDADERO Si Nublado Caliente Normal FALSO No Soleado Templado Alta VERDADERO Data Mining. ESCOM-IPN. Dra. Fabiola Ocampo Botello 6 3  18/10/2024 Continuación ID3 7 Data Mining. ESCOM-IPN. Dra. Fabiola Ocampo Botello 7 8 Algoritmo C4.5 Rokach & Maimon (2015) y Bhumika et al. (2017) establecen que el algoritmo C4.5 tiene las siguientes características: - Es una evolución de ID3. - Fue desarrollado por Ross Quinlan. - Puede manejar atributos numéricos. - Utiliza la relación de ganancia como criterio de división. - Es n-ario con valores discretos y binario con datos continuos. - La poda basada en errores se realiza después de la fase de crecimiento. - La división termina cuando el número de instancias a dividir está por debajo de un cierto umbral. Data Mining. ESCOM-IPN. Dra. Fabiola Ocampo Botello 8 4  18/10/2024 Continuación C4.5 9 El algoritmo C4.5 proporciona varias mejoras para ID3. Las mejoras más importantes según Rokach & Maimon (2015) son: (1) C4.5 utiliza un procedimiento de poda que elimina las ramas que no contribuyen a la precisión y las reemplaza con nodos foliares. (2) C4.5 permite que falten valores de atributos (marcados como ?). (3) C4.5 maneja atributos continuos dividiendo el rango de valores del atributo en dos subconjuntos (división binaria). Específicamente, busca el mejor umbral que maximice el criterio de relación de ganancia. Todos los valores por encima del umbral constituyen el primer subconjunto y todos los demás valores constituyen el segundo subconjunto. Data Mining. ESCOM-IPN. Dra. Fabiola Ocampo Botello 9 Algoritmo C5.0 Rokach & Maimon (2015) expresan que el algoritmo C5.0 es una versión comercial actualizada de C4.5 que ofrece una serie de mejoras: se afirma que C5.0 es mucho más eficiente que C4.5 en términos de memoria y tiempo de cálculo. Además, es compatible con el procedimiento de refuerzo que puede mejorar el rendimiento predictivo. Algoritmo J48 Rokach & Maimon (2015) mencionan que el algoritmo J48 es una implementación Java de código abierto del algoritmo C4.5 en la herramienta de minería de datos Weka. Debido a que el algoritmo J48 es simplemente una reimplementación de C4.5, se 10 espera que funcione de manera similar a C4.5. Sin embargo, un estudio comparativo reciente que compara C4.5 con J48 y C5.0 [Moore et al. (2009)] indica que C4.5 tiene un rendimiento consistentemente mejor (en términos de precisión) que C5.0 y J48 en particular en conjuntos de datos pequeños. Data Mining. ESCOM-IPN. Dra. Fabiola Ocampo Botello 10 5  18/10/2024 ID3 y C4.5 Ejemplo de un árbol J48 (C4.5): Considerando las características descriptivas que tiene una flor de iris, crear un modelo que generalice la identificación de tres tipos de iris: iris versicolor, iris setosa e iris virginica. 11 Esta foto de Autor desconocido está bajo licencia CC BY-SA Data Mining. ESCOM-IPN. Dra. Fabiola Ocampo Botello 11 Ejemplo de un árbol J48 (C4.5): ID3 y C4.5 12 Data Mining. ESCOM-IPN. Dra. Fabiola Ocampo Botello 12 6  18/10/2024 ID3 y C4.5 Dunham (2002) establece que el algoritmo del árbol de decisión C4.5 mejora al ID3 en los siguientes aspectos (se presentan algunos): - Datos faltantes: cuando se crea el árbol de decisión, los datos faltantes simplemente se ignoran. Es decir, la relación de ganancia se calcula considerando sólo los otros registros que tienen un valor para ese atributo. Para clasificar un registro con un valor de atributo faltante, el valor para ese elemento puede predecirse en función de lo que se sabe sobre los valores de atributo para los otros registros. - Datos continuos: la idea básica es dividir los datos en rangos basados 13 en los valores de atributo para ese elemento que se encuentran en la muestra de entrenamiento. Data Mining. ESCOM-IPN. Dra. Fabiola Ocampo Botello 13 ID3 y C4.5 - Poda: hay dos estrategias principales de poda propuestas en C4.5 (Dunham, 2002): - Con el reemplazo del subárbol, un subárbol se reemplaza por un nodo hoja si este reemplazo da como resultado una tasa de error cercana a la del árbol original. - Otra estrategia de poda, llamada elevación de subárbol, la cual reemplaza un subárbol por su subárbol más utilizado. Larose & Larose (2015) establecen que el algoritmo C4.5 es la extensión de Quinlan de su propio algoritmo iterativo de dicotomizador 3 (ID3) para generar árboles de decisión. Al igual que 14 con CART, el algoritmo C4.5 visita recursivamente cada nodo de decisión, seleccionando la división óptima, hasta que no se produzcan más divisiones posibles. Data Mining. ESCOM-IPN. Dra. Fabiola Ocampo Botello 14 7  18/10/2024 ID3 y C4.5 Sin embargo, existen las siguientes diferencias interesantes entre CART y C4.5 (Larose, T. Daniel & Larose, D. Chantal, 2015) : - A diferencia de CART, el algoritmo C4.5 no está restringido a divisiones binarias. Mientras que CART siempre produce un árbol binario, C4.5 produce un árbol de forma más variable. - Para los atributos categóricos, C4.5 por defecto produce una rama separada para cada valor del atributo categórico. Esto puede resultar en más "arbustos" de lo deseado, porque algunos valores pueden tener baja frecuencia o pueden estar asociados naturalmente con otros valores. 15 - El método C4.5 para medir la homogeneidad de los nodos es bastante diferente del método CART y se examina en detalle a continuación. El algoritmo C4.5 utiliza el concepto de ganancia de información o reducción de entropía para seleccionar la división óptima. Data Mining. ESCOM-IPN. Dra. Fabiola Ocampo Botello 15 Árbol CART El árbol CART (Bhumika et al. (2017). - Significa árboles de clasificación y regresión (Classification And Regression Trees). - Fue presentado por Breiman en 1984. - El algoritmo CART construye árboles de clasificación y regresión. - CART construye el árbol de clasificación mediante la división binaria del 16 atributo. - El índice de Gini se usa para seleccionar el atributo de división - Permite datos de atributos continuos y nominales. Data Mining. ESCOM-IPN. Dra. Fabiola Ocampo Botello 16 8  18/10/2024 C4.5 y CART Sin embargo, existen las siguientes diferencias interesantes entre CART y C4.5 (Larose & Larose, 2015) : - A diferencia de CART, el algoritmo C4.5 no está restringido a divisiones binarias. Mientras que CART siempre produce un árbol binario, C4.5 produce un árbol de forma más variable. - Para los atributos categóricos, C4.5 por defecto produce una rama separada para cada valor del atributo categórico. Esto puede resultar en más "arbustos" de lo deseado, porque algunos valores pueden tener baja frecuencia o pueden estar asociados naturalmente con otros 17 valores. Data Mining. ESCOM-IPN. Dra. Fabiola Ocampo Botello 17 Ejemplo de un árbol CART: Ejercicio adaptado con fines educativos de: Portal IBM. SPSS Statistics 23.0.0. Casos de estudio. Disponible en: https://www.ibm.com/support/knowledgecenter/en/SSLVMB_23.0.0/spss/tutorials/trees_scorin g_intro1.html Descripción del enunciado: Considerando un conjunto de datos que contiene información demográfica y el precio de compra del vehículo. Construir un modelo que se puede usar para predecir cuánto es probable que las personas con características demográficas similares gasten en un automóvil nuevo. El modelo creado podrá ser aplicado a otros archivos de datos donde la información 18 demográfica está disponible, pero no la información sobre compras anteriores de vehículos. Data Mining. ESCOM-IPN. Dra. Fabiola Ocampo Botello 18 9  18/10/2024 CART Diccionario de datos: 19 Data Mining. ESCOM-IPN. Dra. Fabiola Ocampo Botello 19 CART 20 Data Mining. ESCOM-IPN. Dra. Fabiola Ocampo Botello 20 10  18/10/2024 Referencias bibliográficas Bhumika Gupta, Aditya Rawat, Akshay Jain, Arpit Arora, Naresh Dhami. (2017). Analysis of Various Decision Tree Algorithms for Classification in Data Mining. International Journal of Computer Applications (0975–8887). Volume 163 – No 8, April 2017. Dunham, M. H. (2002). Data mining: introductory and advanced topics. Prentice Hall. Larose, T. Daniel & Larose, D. Chantal. (2015). Data Mining and Predictive Analytics. Second Edition. Wiley. Rokach, L. & Maimon, O. (2015). Data Mining with decision trees. Theory and Applications. Second Edition. World Scientific Publishing Co. Pte. Ltd. 21 Data Mining. ESCOM-IPN. Dra. Fabiola Ocampo Botello 21 11  Instituto Politécnico Nacional Escuela Superior de Cómputo Secretaría Académica Departamento de Ingeniería en Sistemas Computacionales Minería de datos (Data Mining) Medidas de evaluación en Árboles de decisión 1 Profesora: Dra. Fabiola Ocampo Botello 2 Un algoritmo de inducción, o más concisamente un inductor (también conocido como aprendiz), es una entidad que obtiene un conjunto de entrenamiento y forma un modelo que generaliza la relación entre los atributos de entrada y el atributo objetivo. Por ejemplo, un inductor puede tomar como entrada tuplas de entrenamiento específicas con la etiqueta de clase correspondiente y producir un clasificador (Rokach, L. & Maimon, O., 2015). Los inductores de árboles de decisión son algoritmos que construyen automáticamente un árbol de decisiones a partir de un conjunto de datos determinado (Rokach, L. & Maimon, O., 2015). Data Mining. ESCOM-IPN. Dra. Fabiola Ocampo Botello  Rokach, L. & Maimon, O. (2015) establecen que la meta de un algoritmo de clasificación se puede definir formalmente como: Dado un conjunto de entrenamiento S con atributos de entrada A = {a1, a2,... , an} y un atributo nominal y y una distribución desconocida D, la meta es inducir un clasificador óptimo con el mínimo error de generalización. Notación: DT Representa el inductor del árbol de decisión. DT(S) Representa un árbol de clasificación que se generó al 3 ejecutar DT sobre el conjunto de datos S. DT(S)(xq) Es la predicción de xq usando DT(S). Data Mining. ESCOM-IPN. Dra. Fabiola Ocampo Botello  Rokach, L. & Maimon, O. (2015) establecen que el error de generalización es definido como la tasa de clasificación errónea sobre la distribución D, en caso de atributos nominales puede ser expresado como: Donde es una función cero o uno definido como: 4 Imágenes tomadas de Rokach, L. & Maimon, O. (2015) Data Mining. ESCOM-IPN. Dra. Fabiola Ocampo Botello  Evaluación de árboles de clasificación Rokach, L. & Maimon, O. (2015) establecen los siguientes aspectos de la evaluación de los árboles de clasificación. La exactitud de la clasificación se expresa como uno menos el error de generalización. El error de entrenamiento es definido como el porcentaje de ejemplos en el conjunto de entrenamiento que fueron correctamente clasificados en el árbol de clasificación, lo cual se expresa: 5 Donde se define igual que la expresión 3.2. Existen dos formas de estimar el error de generalización: 1. Teórico 2. Empírico Data Mining. ESCOM-IPN. Dra. Fabiola Ocampo Botello 6 Estimación empírica del error de generalización Uno de los enfoques para estimar el error de generalización es el método de retención (holdout method) en el que el conjunto de datos dado se divide aleatoriamente en dos conjuntos: Conjuntos de entrenamiento y prueba (Rokach, L. & Maimon, O, 2015). Por lo general, dos tercios de los datos se consideran para el conjunto de entrenamiento y los datos restantes se asignan al conjunto de prueba. Imagen: Elaboración propia Data Mining. ESCOM-IPN. Dra. Fabiola Ocampo Botello  El submuestreo aleatorio (Random subsampling) y la validación cruzada n- fold (n-fold cross-validation) son dos métodos comunes de remuestreo (Rokach, L. & Maimon, O, 2015): - En el submuestreo aleatorio, los datos se dividen aleatoriamente varias veces en conjuntos de entrenamiento y pruebas disjuntos. Los errores obtenidos de cada partición se promedian. - En la validación cruzada n-fold, los datos se dividen aleatoriamente en n subconjuntos mutuamente excluyentes de aproximadamente el mismo tamaño. Un inductor es entrenado y probado n veces; cada vez 7 se prueba en uno de los k pliegues (fold) y se entrena utilizando los n-1 pliegues (fold) restantes. Data Mining. ESCOM-IPN. Dra. Fabiola Ocampo Botello  Imagen: Elaboración propia 8 En este caso n vale 5, ya que se dividió el conjunto de datos en 5 partes (fold1, fold2, fold3, fold4, fold5), por citar: Modelo 1: entrenado en fold1+fold2+fold3+fold4 y probado en fold5 Modelo 2: entrenado en fold1+fold2+fold3+fold5 y probado en fold4 Modelo 3: entrenado en fold1+fold2+fold4+fold5 y probado en fold3 Modelo 4: entrenado en fold1+fold3+fold4+fold5 y probado en fold2 Modelo 5: entrenado en fold2+fold3+fold4+fold5 y probado en fold1 Data Mining. ESCOM-IPN. Dra. Fabiola Ocampo Botello 9 Rokach, L. & Maimon, O. (2015:31-60) presentan los siguientes medidas de evaluación en los árboles de decisión. La precisión (Accuracy) no es una medida suficiente para evaluar un modelo con una distribución desbalanceada de las clases. La sensibilidad (Sensitivity) (también conocida como recuerdo (recall)) evalúa qué tan bien el clasificador puede reconocer muestras positivas y se define como: 𝑡𝑟𝑢𝑒_𝑝𝑜𝑠𝑖𝑡𝑖𝑣𝑒 𝑆𝑒𝑛𝑠𝑖𝑡𝑖𝑣𝑖𝑡𝑦 = 𝑝𝑜𝑠𝑖𝑡𝑖𝑣𝑒 Donde true_positive corresponde al número de muestras positivas verdaderas y positive es el número de muestras positivas. Data Mining. ESCOM-IPN. Dra. Fabiola Ocampo Botello  La medida de especificidad (specificity) mide que tan bien el clasificador puede reconocer las muestras negativas. Se define como (Rokach, L. & Maimon, O.,2015) : 𝑡𝑟𝑢𝑒_𝑛𝑒𝑔𝑎𝑡𝑖𝑣𝑒 𝑆𝑝𝑒𝑐𝑖𝑓𝑖𝑐𝑖𝑡𝑦 = 𝑛𝑒𝑔𝑎𝑡𝑖𝑣𝑒 Donde true_negative corresponde al número de ejemplos de verdaderos negativos y negative al número de muestras negativas. Otra medida se llama precisión (Precision). La precisión (Precision) mide cuántos ejemplos clasificados como clase "positiva" son realmente "positivos". Esta medida es útil para evaluar clasificadores nítidos que se utilizan para clasificar un conjunto de datos completo. Formalmente (Rokach, L. & Maimon, O.,2015): 10 Data Mining. ESCOM-IPN. Dra. Fabiola Ocampo Botello  Matriz de confusión La evaluación del desempeño de un modelo de clasificación considera dos aspectos: 1. La cantidad de registros previstos por el modelo de forma adecuada. 2. La cantidad de registros previstos por el modelo de forma inadecuada. Lo anterior se presenta en una matriz de confusión. Clase prevista Clase 1 Clase 0 Ejemplo de una matriz de confusión: Clase actual Clase 1 f11 f10 Clase 0 f01 f00 𝑁ú𝑚𝑒𝑟𝑜 𝑑𝑒 𝑝𝑟𝑒𝑑𝑖𝑐𝑐𝑖𝑜𝑛𝑒𝑠 𝑐𝑜𝑟𝑟𝑒𝑐𝑡𝑎𝑠 𝑓11+𝑓00 11 Exactitud (Accuracy) = Exactitud (Accuracy)= 𝑓11+𝑓10+𝑓01+𝑓00 𝑁ú𝑚𝑒𝑟𝑜 𝑡𝑜𝑡𝑎𝑙 𝑑𝑒 𝑝𝑟𝑒𝑑𝑖𝑐𝑐𝑖𝑜𝑛𝑒𝑠 𝑓10+𝑓01 Tasa de erros (E𝑟𝑟𝑜𝑟 𝑟𝑎𝑡𝑒) = 𝑁ú𝑚𝑒𝑟𝑜 𝑑𝑒 𝑝𝑟𝑒𝑑𝑖𝑐𝑐𝑖𝑜𝑛𝑒𝑠 𝑖𝑛𝑐𝑜𝑟𝑟𝑒𝑐𝑡𝑎𝑠 Error rate = 𝑁ú𝑚𝑒𝑟𝑜 𝑡𝑜𝑡𝑎𝑙 𝑑𝑒 𝑝𝑟𝑒𝑑𝑖𝑐𝑐𝑖𝑜𝑛𝑒𝑠 𝑓11+𝑓10+𝑓01+𝑓00 Data Mining. ESCOM-IPN. Dra. Fabiola Ocampo Botello  Rokach, L. & Maimon, O. (2015:37). 12 Imágenes tomadas de Rokach, L. & Maimon, O. (2015:37). Data Mining. ESCOM-IPN. Dra. Fabiola Ocampo Botello  Comprensibilidad Rokach, L. & Maimon, O. (2015) establece que El criterio de comprensibilidad (también conocido como interpretabilidad) se refiere a qué tan bien los humanos captan el clasificador inducido. Mientras que el error de generalización mide cómo el clasificador se ajusta a los datos, la comprensibilidad mide el "ajuste mental" de ese clasificador. Para dominios como el diagnóstico médico, los usuarios deben comprender cómo el sistema toma sus decisiones para estar seguros del resultado. Rokach, L. & Maimon, O. (2015) expresan que La comprensibilidad puede variar 13 entre diferentes clasificadores creados por el mismo inductor. Por ejemplo, en el caso de los árboles de decisión, el tamaño (número de nodos) de los árboles inducidos también es importante. Se prefieren los árboles más pequeños porque son más fáciles de interpretar. Data Mining. ESCOM-IPN. Dra. Fabiola Ocampo Botello De acuerdo con un principio fundamental en la ciencia, conocido como la navaja de Occam, cuando se busca la explicación de cualquier fenómeno, uno debe hacer la menor cantidad posible de suposiciones y eliminar aquellas que no hacen ninguna diferencia en las predicciones observables de la hipótesis explicativa. 14 Data Mining. ESCOM-IPN. Dra. Fabiola Ocampo Botello  Robustez Rokach, L. & Maimon, O. (2015) expresan que la capacidad del modelo para manejar el ruido o los datos con valores perdidos y hacer predicciones correctas se llama robustez. Además, - Los diferentes algoritmos de árboles de decisión tienen diferentes niveles de robustez. - Para estimar la robustez de un árbol de clasificación, es común entrenar el árbol en un conjunto de entrenamiento limpio y luego entrenar un árbol diferente en un conjunto de entrenamiento ruidoso. - El conjunto de entrenamiento ruidoso suele ser el conjunto de 15 entrenamiento limpio al que se han agregado algunas instancias ruidosas artificiales. El nivel de robustez se mide como la diferencia en la precisión de estas dos situaciones. Data Mining. ESCOM-IPN. Dra. Fabiola Ocampo Botello  Estabilidad Rokach, L. & Maimon, O. (2015) expresan que Formalmente, la estabilidad de un algoritmo de clasificación se define como el grado en que un algoritmo genera resultados repetibles, dados diferentes lotes de datos del mismo proceso. Los usuarios ven el algoritmo de aprendizaje como un oráculo. Obviamente, es difícil confiar en un oráculo que dice algo radicalmente diferente cada vez que realiza un ligero cambio en los datos. 16 Data Mining. ESCOM-IPN. Dra. Fabiola Ocampo Botello  Sobreajuste y Subajuste Rokach, L. & Maimon, O. (2015) mencionan que El concepto de sobreajuste es muy importante en la minería de datos. Se refiere a la situación en la que el algoritmo de inducción genera un clasificador que se ajusta perfectamente a los datos de entrenamiento pero ha perdido la capacidad de generalizar a instancias no presentadas durante el entrenamiento. En otras palabras, en lugar de aprender, el clasificador simplemente memoriza las instancias de entrenamiento. El sobreajuste se reconoce generalmente como una violación del principio de la navaja de Occam. 17 Data Mining. ESCOM-IPN. Dra. Fabiola Ocampo Botello  Imagen tomada de la página web del Ing. Juan Ignacio Bagnato. Dirección Web: https://www.aprendemachinelearning.com/qu e-es-overfitting-y-underfitting-y-como- solucionarlo/ 18 Data Mining. ESCOM-IPN. Dra. Fabiola Ocampo Botello Escalabilidad a grandes bases de datos (Scalability to Large Datasets) Rokach, L. & Maimon, O. (2015) mencionan que La escalabilidad se refiere a la capacidad del método para construir el modelo de clasificación de manera eficiente dada una gran cantidad de datos. Los enfoques para tratar con una gran cantidad de registros incluyen: - Métodos de muestreo: los estadísticos seleccionan registros de una población mediante diferentes técnicas de muestreo. - Agregación: reduce el número de registros al tratar un grupo de registros como uno o al ignorar los subconjuntos de registros "sin importancia". - Procesamiento masivo en paralelo. - Métodos de almacenamiento eficientes: permiten que el algoritmo maneje muchos 19 registros. Por ejemplo una estructura de datos de lista de atributos. - Reducción del espacio de búsqueda del algoritmo: por ejemplo, el algoritmo PUBLIC [Rastogi y Shim (2000)] integra el crecimiento y la poda de los árboles de decisión mediante el uso del enfoque de Longitud mínima de descripción (Minimum Description Length, MDL) para reducir la complejidad computacional. Data Mining. ESCOM-IPN. Dra. Fabiola Ocampo Botello  Referencias bibliográficas Bagnato, Juan Ignacio. (2017). Aprende Machine Learning. Portal Web. Disponible en: https://www.aprendemachinelearning.com/que-es-overfitting-y-underfitting-y-como-solucionarlo/ Bennet, Briggs & Triola (2011). Razonamiento estadístico. Pearson. México. Rokach, L. & Maimon, O. (2015). Data Mining with decision trees. Theory and Applications. Second Edition. World Scientific Publishing Co. Pte. Ltd. 20 Data Mining. ESCOM-IPN. Dra. Fabiola Ocampo Botello