Algortimos Paralelos de Indução de Árvores de Decisão

Nuno Reis Amado

Mestrado em Inteligência Artificial e Computação
Universidade do Porto

Janeiro 2002

---

Resumo

Actualmente, nos campos da Extracção do Conhecimento e da Aprendizagem Automática a quantidade de dados disponível para a construção de procedimentos de classificação está a crescer a um ritmo bastante rápido. Para a construção de um procedimento de classificação, uma maior quantidade de dados aumenta a possibilidade de se obterem procedimentos com maior precisão de classificação. Contudo, também implica um custo maior no tempo e na complexidade de obtenção de tais classificadores. Desta forma, existe uma grande necessidade de algoritmos capazes de construir classificadores a partir de conjuntos de dados bastante grandes e, simultaneamente, serem computacionalmente eficientes e escalonáveis. Uma possível solução é a utilização de algoritmos paralelos de forma a reduzir a quantidade de tempo utilizada na construção de procedimentos de classificação a partir de conjuntos de dados bastante grandes e, desta forma, manter a precisão de classificação.

Neste trabalho, são apenas considerados os procedimentos de classificação baseados em árvores de decisão dado que estas têm sido extensamente utilizadas em diversas áreas e têm sido consideradas como os modelos mais adequados para a extracção do conhecimento e para a Aprendizagem Automática. São descritas algumas das estratégias utilizadas para a implementação de algoritmos de indução de árvores de decisão em paralelo baseados em técnicas como o paralelismo de controlo, paralelismo nos dados e paralelismo híbrido.

Algumas das ideias e estratégias apresentadas, assim como o algoritmo de indução de árvores de decisão do sistema C4.5, serviram como suporte para o desenvolvimento de um novo algoritmo paralelo de construção de árvores de decisão, à sua implementação usando MPI e análise de desempenho num cluster de memória distribuída.

---