Abstracto

Minería de datos 2016: extensiones de programación dinámica para el estudio de árboles de decisión - Mikhail Moshkov - Universidad de Ciencia y Tecnología Rey Abdullah

Mijail Moshkov

En la presentación, consideramos extensiones del enfoque de programación dinámica para el estudio de árboles de decisión como algoritmos para la resolución de problemas; como una forma de extracción y representación de conocimiento, y como clasificadores que para un nuevo objeto dado por valores de atributos condicionales, definen un valor del atributo de decisión. Estas extensiones nos permiten: (i) Describir el conjunto de árboles de decisión óptimos; (ii) Contar el número de estos árboles; (iii) Realizar optimización secuencial de árboles de decisión en relación con diferentes criterios; (iv) Encontrar el conjunto de puntos óptimos de Pareto para dos criterios; y (v) Describir relaciones entre dos criterios. Los resultados incluyen la minimización de la profundidad promedio para árboles de decisión que ordenan ocho elementos (esta pregunta estaba abierta desde 1968), mejora de los límites superiores en la profundidad de los árboles de decisión para el diagnóstico de fallas 0-1 en circuitos combinatorios de lectura única; existencia de árboles de decisión totalmente óptimos (con profundidad mínima y número mínimo de nodos) para funciones booleanas; estudio del compromiso tiempo-memoria para árboles de decisión para detección de puntos de esquina; estudio de las relaciones entre el número y la longitud máxima de las reglas de decisión derivadas de árboles de decisión; estudio del equilibrio entre precisión y tamaño de los árboles de decisión que nos permite construir árboles de decisión lo suficientemente pequeños y precisos para la representación del conocimiento; y árboles de decisión que, como clasificadores, superan a menudo a los árboles de decisión construidos por CART. El final de la presentación está dedicado a la introducción a KAUST. Esta tesis está dedicada al desarrollo de extensiones de programación dinámica para el estudio de árboles de decisión. Las extensiones consideradas nos permiten realizar una optimización de múltiples etapas de árboles de decisión en relación con una secuencia de funciones de costo, contar el número de árboles óptimos y estudiar las relaciones: costo vs costo y costo vs incertidumbre para árboles de decisión mediante la construcción del conjunto de puntos Pareto-óptimos para el problema de optimización bicriterio correspondiente. Las aplicaciones incluyen el estudio de árboles de decisión totalmente óptimos (simultáneamente óptimos en relación con un número de funciones de costo) para funciones booleanas, mejora de los límites de complejidad de los árboles de decisión para el diagnóstico de circuitos, estudio del equilibrio entre tiempo y memoria para la detección de puntos de esquina, estudio de reglas de decisión derivadas de árboles de decisión, creación de nuevos procedimientos (poda múltiple) para la construcción de clasificadores y comparación de heurísticas para la construcción de árboles de decisión. Parte de estas extensiones (optimización de múltiples etapas) se generalizó a problemas de optimización combinatoria bien conocidos: multiplicación de cadenas de matrices, árboles de búsqueda binaria, alineación de secuencia global y caminos óptimos en gráficos dirigidos. Los árboles de decisión se utilizan ampliamente como predictores, como una forma de representación del conocimiento y como algoritmos para la resolución de problemas. Para tener árboles de decisión más comprensibles, necesitamos minimizar el número de nodos en un árbol.Para tener árboles de decisión más rápidos, necesitamos minimizar la profundidad o la profundidad promedio de un árbol. En muchos casos, necesitamos minimizar la cantidad de clasificaciones erróneas para un árbol bajo ciertas restricciones en la complejidad temporal o espacial del árbol. Si quisiéramos minimizar la cantidad de reglas de decisión derivadas del árbol, necesitamos minimizar la cantidad de nodos terminales en el árbol. Desafortunadamente, casi todos los problemas relacionados con la optimización de árboles de decisión son NP-hard.  

Biografía :

Mikhail Moshkov es profesor de la División CEMSE de la Universidad de Ciencia y Tecnología Rey Abdullah, en Arabia Saudita. Obtuvo su maestría en la Universidad Estatal de Nizhni Novgorod, su doctorado en la Universidad Estatal de Saratov y su habilitación en la Universidad Estatal de Moscú. En 2003 trabajó en el Instituto de Ciencias de la Computación de la Universidad de Silesia, en Polonia. Sus principales áreas de investigación son la complejidad de los algoritmos, la optimización combinatoria y el aprendizaje automático. Ha publicado cinco artículos de investigación en Springer.