Abstrait

Data Mining 2016 : Extensions de la programmation dynamique pour l'étude des arbres de décision - Mikhail Moshkov - Université des sciences et technologies du roi Abdallah

Mikhaïl Moshkov

Dans la présentation, nous considérons des extensions de l'approche de programmation dynamique à l'étude des arbres de décision comme algorithmes de résolution de problèmes ; comme moyen d'extraction et de représentation de connaissances, et comme classificateurs qui pour un nouvel objet donné par des valeurs d'attributs conditionnels, définissent une valeur de l'attribut de décision. Ces extensions nous permettent : (i) de décrire l'ensemble des arbres de décision optimaux ; (ii) de compter le nombre de ces arbres ; (iii) de faire une optimisation séquentielle des arbres de décision par rapport à différents critères ; (iv) de trouver l'ensemble des points optimaux de Pareto pour deux critères ; et (v) de décrire les relations entre deux critères. Les résultats comprennent la minimisation de la profondeur moyenne pour les arbres de décision triant huit éléments (cette question était ouverte depuis 1968), l'amélioration des bornes supérieures de la profondeur des arbres de décision pour le diagnostic des défauts 0-1 dans les circuits combinatoires à lecture unique ; l'existence d'arbres de décision totalement optimaux (avec une profondeur minimale et un nombre minimal de nœuds) pour les fonctions booléennes ; l'étude du compromis temps-mémoire pour les arbres de décision pour la détection des points d'angle ; étude des relations entre nombre et longueur maximale des règles de décision dérivées des arbres de décision ; étude du compromis précision-taille pour les arbres de décision qui nous permet de construire des arbres de décision suffisamment petits et précis pour la représentation des connaissances ; et des arbres de décision qui, en tant que classificateurs, surpassent souvent les arbres de décision construits par CART. La fin de la présentation est consacrée à l'introduction à KAUST. Cette thèse est consacrée au développement d'extensions de la programmation dynamique à l'étude des arbres de décision. Les extensions considérées nous permettent de faire de l'optimisation multi-étapes d'arbres de décision par rapport à une séquence de fonctions de coût, de compter le nombre d'arbres optimaux et d'étudier les relations : coût vs coût et coût vs incertitude pour les arbres de décision par construction de l'ensemble des points Pareto-optimaux pour le problème d'optimisation bi-critère correspondant. Les applications comprennent l'étude d'arbres de décision totalement optimaux (simultanément optimaux par rapport à un certain nombre de fonctions de coût) pour les fonctions booléennes, l'amélioration des limites de complexité des arbres de décision pour le diagnostic des circuits, l'étude du compromis temps/mémoire pour la détection des points d'angle, l'étude des règles de décision dérivées des arbres de décision, la création de nouvelles procédures (multi-élagage) pour la construction de classificateurs et la comparaison d'heuristiques pour la construction d'arbres de décision. Une partie de ces extensions (optimisation multi-étapes) a été généralisée à des problèmes d'optimisation combinatoire bien connus : multiplication de chaînes de matrices, arbres de recherche binaire, alignement de séquences globales et chemins optimaux dans les graphes orientés. Les arbres de décision sont largement utilisés comme prédicteurs, comme moyen de représentation des connaissances et comme algorithmes de résolution de problèmes. Pour avoir des arbres de décision plus compréhensibles, nous devons minimiser le nombre de nœuds dans un arbre.Pour obtenir des arbres de décision plus rapides, nous devons minimiser la profondeur ou la profondeur moyenne d'un arbre. Dans de nombreux cas, nous devons minimiser le nombre d'erreurs de classification pour un arbre sous certaines restrictions de complexité temporelle ou spatiale de l'arbre. Si nous voulons minimiser le nombre de règles de décision dérivées de l'arbre, nous devons minimiser le nombre de nœuds terminaux dans l'arbre. Malheureusement, presque tous les problèmes liés à l'optimisation des arbres de décision sont NP-difficiles.  

Biographie :

Mikhail Moshkov est professeur à la division CEMSE de l'Université des sciences et technologies du roi Abdallah, en Arabie saoudite. Il a obtenu sa maîtrise à l'Université d'État de Nijni Novgorod, son doctorat à l'Université d'État de Saratov et son habilitation à l'Université d'État de Moscou. En 2003, il a travaillé à l'Institut d'informatique de l'Université de Silésie, en Pologne. Ses principaux domaines de recherche sont la complexité des algorithmes, l'optimisation combinatoire et l'apprentissage automatique. Il a publié 5 articles de recherche dans Springer.