Resumo
O classificador Floresta de Caminhos Ótimos (Optimum Path Forest, OPF), baseado em grafocompleto,temsidoaplicadodeformaefetivaemdiversosproblemasdereconhecimento de padrões. Esse classificador é baseado em um subconjunto de protótipos e numa função de custo de caminho em um grafo representado pelo conjunto de treinamento, onde esses dados são particionados em uma coleção de árvores de caminhos ótimos (Optimum Path Trees, OPTs), cada qual formada por nós mais fortemente conectados. Essa abordagem resulta em um classificador livre de parâmetros que não faz suposições sobre a dispersão ou separabilidade das classes, lida com múltiplas classes sem modificações ou extensões e não apresenta erro de classificação no conjunto de treinamento. Apesar de possuir tais vantagens, uma limitação do OPF é que o tempo necessário para executar o seu estágio de classificação cresce proporcionalmente ao tamanho do conjunto de treinamento, visto que, para classificar uma nova amostra, é necessário conectá-la com todos os nós do grafo de treinamento. Dessa forma, o uso de técnicas de poda no grafo do classificador OPF torna-se uma alternativa atraente para reduzir o custo computacional na tarefa de classificação. Nesse contexto, são propostas três técnicas de poda para o classificador OPF utilizando algoritmos genéticos (Genetic Algorithms, GAs) neste trabalho: (i) GAP-OPF, que utiliza GAs para selecionar e remover amostras menos representativas do conjunto de treinamento do OPF que seriam utilizadas em sua fase de classificação; (ii) FSGAP-OPF, que assim como o GAP-OPF, visa gerar um conjunto de treinamento mais compacto e representativo, ao utilizar uma modelagem de poda de tamanho fixo; e por último, (iii) MOGAP-OPF que utiliza otimização multiobjetivo guiada não só pela taxa de erro na classificação, mas também pelo número de OPTs. O desempenho obtido pelos métodos propostos é avaliado por aplicá-los em bases de dados obtidas de experimentos reais, e compará-los com outras técnicas de poda presentes na literatura. As principais métricas utilizadas para comparação foram: acurácia medida sobre o conjunto de teste, percentual de redução no conjunto de treinamento (taxa de poda) e tempo de classificação necessário para classificar todas as amostras de teste. Com base nos experimentos, pode-se afirmar que GAP-OPF, FSGAP-OPF e MOGAP-OPF são alternativas válidas para tarefas de classificação