Abstrato

Data mining 2016:Extensões de programação dinâmica para o estudo de árvores de decisão - Mikhail Moshkov - King Abdullah University of Science and Technology

Mikhail Moshkov

Na apresentação, considerámos extensões da abordagem de programação dinâmica ao estudo de árvores de decisão como algoritmos para a resolução de problemas; como forma de extração e representação de conhecimento, e como classificadores que, para um novo objeto dado por valores de atributos condicionais, definem um valor do atributo de decisão. Estas extensões permitem-nos: (i) Descrever o conjunto de árvores de decisão ótimas; (ii) Contar o número dessas árvores; (iii) Fazer optimização sequencial de árvores de decisão relativamente a diferentes critérios; (iv) Encontrar o conjunto de pontos ótimos de Pareto para dois critérios; e (v) Descrever as relações entre dois critérios. Os resultados incluem a minimização da profundidade média para árvores de decisão ordenando oito elementos (esta questão estava em aberto desde 1968), melhoria dos limites superiores da profundidade das árvores de decisão para diagnóstico de falhas 0-1 em circuitos combinatórios de leitura única; existência de árvores de decisão totalmente ótimas (com profundidade mínima e número mínimo de nós) para funções booleanas; estudo de compensação tempo-memória para árvores de decisão para deteção de pontos de canto; estudo das relações entre o número e o comprimento máximo de regras de decisão derivadas de árvores de decisão; estudo da compensação entre precisão e tamanho para árvores de decisão, o que nos permite construir árvores de decisão suficientemente pequenas e precisas para a representação do conhecimento; e árvores de decisão que, como classificadores, muitas vezes superam as árvores de decisão construídas pelo CART. O final da apresentação é dedicado à introdução ao KAUST. As extensões consideradas permitem-nos fazer optimização em vários estágios de árvores de decisão em relação a uma sequência de funções de custo, contar o número de árvores óptimas e estudar relações: custo vs custo e custo vs incerteza para árvores de decisão por construção do conjunto de pontos ótimos de Pareto para o problema de otimização bicritério correspondente. As aplicações incluem o estudo de árvores de decisão totalmente ótimas (simultaneamente ótimas em relação a uma série de funções de custo) para funções booleanas, melhoria dos limites de complexidade das árvores de decisão para diagnóstico de circuitos, estudo de compensação de tempo e memória para deteção de pontos de canto, estudo de regras de decisão derivadas de árvores de decisão, criação de um novo procedimento (multi-pruning) para construção de classificadores e comparação de heurísticas para construção de árvores de decisão. Parte destas extensões (otimização em vários estágios) foram generalizadas para problemas de otimização combinatória bem conhecidos: multiplicação de cadeias de matrizes, árvores de pesquisa binária, alinhamento de sequências globais e caminhos ótimos em grafos direcionados. de problemas. Para termos árvores de decisão mais compreensíveis, precisamos de minimizar o número de nós numa árvore.Para termos árvores de decisão mais rápidas, precisamos de minimizar a profundidade ou a profundidade média de uma árvore. Em muitos casos, precisamos de minimizar o número de classificações erradas de uma árvore sob algumas restrições de complexidade de tempo ou espaço da árvore. Se quisermos minimizar o número de regras de decisão derivadas da árvore, precisamos de minimizar o número de nós terminais na árvore. Infelizmente, quase todos os problemas relacionados com a otimização de árvores de decisão são NP-difíceis.  

Biografia:

Mikhail Moshkov é professor na Divisão CEMSE da Universidade de Ciência e Tecnologia King Abdullah, na Arábia Saudita. Obteve o seu mestrado pela Universidade Estatal de Nizhni Novgorod, obteve o seu doutoramento pela Universidade Estatal de Saratov e a sua habilitação pela Universidade Estatal de Moscovo. Em 2003, trabalhou no Instituto de Ciência da Computação da Universidade da Silésia, na Polónia. As suas principais áreas de investigação são a Complexidade de Algoritmos, a Otimização Combinatória e a Aprendizagem Automática. Publicou 5 artigos de investigação na Springer.