Redução do Tamanho do Conjunto de Treinamento por Floresta de Caminhos Ótimos e sua Aplicação em Máquinas de Vetores de Suporte

Resumo

Classificadores supervisionados de padrões tradicionais, tais como Máquinas de Vetores de Suporte e Redes Neurais Artificiais, possuem um bom desempenho em determinadas aplicações. Entretanto, para atingir taxas de acerto aceitáveis no conjunto de dados de teste, tais abordagens pagam o preço de uma fase de treinamento extremamente custosa. Máquinas de Vetores de Suporte, por exemplo, assumem uma separabilidade linear do espaço de características, mapeando as amostras para um espaço de maior dimensão utilizando funções de núcleo. Usualmente, tais funções possuem parâmetros que necessitam ser escolhidos com muito cuidado, pois influenciam diretamente na taxa de acerto no conjunto de treinamento e, consequentemente, no conjunto de dados de teste. Assim, esses tipos de classificadores são inviáveis em situações nas quais um treinamento dos dados é requerido em tempo real como, por exemplo, aplicativos para classificação interativa de regiões do cérebro utilizando imagens de ressonância magnética, as quais são constituídas por milhões de voxels. Imagine um sistema no qual um médico marca algumas amostras da região a ser classificada. O algoritmo é então treinado com essas amostras e validado com o restante da imagem. O resultado é então mostradoao usuário, o qual pode interagir com o sistema marcando novas amostras com o intuito de refinar o processo de classificação. Assim, um novo treinamento do classificador é requerido. Esse processo repete-se até que o usuário fique satisfeito. Esse contexto torna inviável a utilização das Redes Neurais e Máquinas de Vetores de Suporte, pois é razoável que o usuário espere apenas alguns segundos para visualizaro resultado do processo classificatório e não minutos e, talvez, horas. Recentemente,um novo classificador de padrões baseado em grafos foi proposto na literatura com onome de Floresta de Caminhos Ótimos. A idéia consiste, basicamente, em modelaro problema de classificação de padrões como um problema de particionamento de um grafo em árvores de caminhos ótimos a partir de amostras protótipos. Tal classificador possui, dentre outras vantagens, ser livre de parâmetros, não assumir forma e/ou separabilidade das amostras e ser extremamente rápido (500 vezes mais rápido que Máquinas de Vetores de Suporte, por exemplo), tanto na fase de treinamentoquanto na de teste. Há pouco tempo atrás, foi também proposta na literatura uma abordagem para redução do tamanho do conjunto de treinamento para o classificador Floresta de Caminhos Ótimos a qual consiste, basicamente, em um algoritmo deaprendizagem que consegue identificar as amostras mais relevantes do conjunto de treinamento, descartando as demais. Tal metodologia conseguiu, em algumas bases de dados, aproximadamente 40% de redução no tamanho do conjunto de treinamento com uma sensível intervenção na taxa de acerto no conjunto de teste. Como o classificador Máquinas de Vetores de suporte é bastante conhecido na literatura pelas suas altas taxas de acerto de classificação, o presente projeto de pesquisapropõe a redução do tamanho do conjunto de treinamento pela abordagem Floresta de Caminhos Ótimos e sua posterior utilização para treinamento das Máquinas de Vetores de Suporte. O objetivo seria, então, avaliar o impacto de tal redução do conjunto de treinamento em termos de eficiência e eficácia computacional do classificador Máquinas de Vetores de Suporte, e sua comparação com os resultados obtidos pelopróprio classificador Floresta de Caminhos Ótimos. Assim, o projeto de pesquisa caracteriza-se pelo seu caráter inovador neste sentido, visto que nenhuma pesquisa a respeito foi proposta na literatura.