"Ciências Básicas para o Desenvolvimento Sustentável"

24 a 26 de outubro de 2023

Trabalho 19148

ISSN 2237-9045
Instituição Universidade Federal de Viçosa
Nível Graduação
Modalidade Pesquisa
Área de conhecimento Ciências Exatas e Tecnológicas
Área temática Ciência da computação
Setor Departamento de Informática
Bolsa FAPEMIG
Conclusão de bolsa Sim
Apoio financeiro FAPEMIG
Primeiro autor Olavo Alves Barros Silva
Orientador RICARDO DOS SANTOS FERREIRA
Outros membros Caio Von Rondow Morais
Título Uso de Diagrama de Decisão Binária como acelerador para Random Forest
Resumo Uma Random Forest pode ser definida como um classificador composto por uma coleção de árvores de decisão, na qual, dada uma amostra, cada uma dessas árvores irá classificá-la e, posteriormente, uma votação é feita para que seja escolhida a classe predominante, usando, por exemplo, um modelo de agregação como o majority vote. Um modelo como este, apesar de possuir um fácil entendimento, ainda é considerado um modelo de caixa preta, devido ao elevado nível de paralelismo, uma vez que o resultado da classificação final é definido pela agregação de inúmeras árvores de decisão. Um Diagrama de Decisão Binária, no inglês, Binary Decision Diagram (BDD), pode ser definido como um grafo acíclico constituído por dois tipos de nós: terminais e não terminais. Nós terminais são identificados por 0(ZERO) e 1(UM) e não terminais como expressões booleanas, tendo esses últimos sempre dois nós filhos, que representam o resultado positivo e negativo da expressão. Uma das características mais atrativas de um BDD é a sua capacidade de representação de uma função booleanas em tamanho polinomial. Uma variação do BDD básico é aquela composta por arestas complementares (além das duas arestas básicas), que possuem a função de negar a expressão contida no nó subsequente. Essa nova representação produz um grafo deveras mais compacto, pois agora haverá somente um nó terminal. Sendo assim, como Random Forest é um modelo de aprendizagem de máquina baseada em lógica, o uso de BDD se torna um caminho intuitivo, mas que ainda possui desafios: O principal deles é o pipeline de construção do grafo, que deve conseguir representar todas as árvores presentes no modelo e ainda realizar o processo de agregação e votação. Outro ponto a ser tratado é como a ordem das variáveis irá ser estabelecida, já que essa condição é basilar para que o BDD se torne reduzido e eficiente. Este trabalho tem como objetivo apresentar um gerador de Diagramas de Decisão Binária que representem uma Random Forest e que sejam capazes de acelerar o processo de classificação e tornar o modelo mais próximo de uma caixa branca. Para alcançar tal feito, foi usado estratégias de geração de códigos, como expressões lógicas para construção de operadores e padrões de projeto, juntamente com bibliotecas na linguagem de programação C++ e Python já amplamente conhecidas para manipulações de BDD, sendo elas a Colorado University Binary Decision Diagram (CUDD) e DD, e, assim, foi modelado todo o caminho de construção para o BDD: a formação da Random Forest usando a biblioteca em python Sklearn; a construção de um BDD inicial com as variáveis sendo as comparações das árvores; um segundo BDD com a soma das votações para cada classe; um terceiro para a votação; e um último para fazer a redução, no qual a saída já classifica em qual classe os dados de entrada são enquadrados. Como resultados, é possível destacar que o BDD se mostra uma estrutura de dados mais rápida para ser percorrida.
Palavras-chave Diagrama de Decisão Binária, Random Forets, acelerador
Forma de apresentação..... Painel
Link para apresentação Painel
Gerado em 0,64 segundos.