Novos algoritmos de aprendizado para classificação de padrões utilizando floresta de caminhos ótimos

O Reconhecimento de Padroes pode ser definido como a capacidade de identificar a classe de algum objeto dentre um dado conjunto de classes, baseando-se na informacao fornecida por amostras conhecidas (conjunto de treinamento). Nesta dissertacao, o foco de estudo e o paradigma de classificacao supervisionada, no qual se conhece a classe de todas as amostras utilizadas para o projeto do classificador. Especificamente, estuda-se o Classificador baseado em Floresta de Caminhos Otimos (Optimum-Path Forest - OPF) e propoem tres novos algoritmos de aprendizado, os quais representam melhorias em comparacao com o Classificador OPF tradicional. Primeiramente, e desenvolvida uma metodologia simples, porem efetiva, para deteccao de outliers no conjunto de treinamento. O metodo visa uma melhoria na acuracia do Classificador OPF tradicional atraves da troca desses outliers por novas amostras do conjunto de avaliacao e sua exclusao do processo de aprendizagem. Os outliers sao detectados computando uma penalidade para cada amostra baseada nos seus acertos e erros na classificacao, o qual pode ser medido atraves do numero de falsos positivos/negativos e verdadeiros positivos/negativos obtidos por cada amostra. O metodo obteve uma melhoria na acuracia em comparacao com o OPF tradicional, com apenas um pequeno aumento no tempo de treinamento. Em seguida, e proposto um aprimoramento ao primeiro algoritmo, que permite detectar com maior precisao os outliers presentes na base de dados. Neste caso, utiliza-se a informacao de falsos positivos/negativos e verdadeiros positivos/negativos de cada amostra para explorar intrinsecamente as relacoes de adjacencia de cada amostra e determinar se e outlier. Uma inovacao do metodo e que nao existe necessidade de se computar explicitamente tal adjacencia, como e feito nas tecnicas tradicionais, o qual pode ser inviavel para grandes bases de dados. O metodo obteve uma boa taxa de deteccao de outliers e um tempo de treinamento muito baixo em vista do tamanho das bases de dados utilizadas. Finalmente, e abordado o problema de se selecionar um umero tao pequeno quanto possivel de amostras de treinamento e se obter a maior acuracia possivel sobre o conjunto de teste. Propoe-se uma metodologia que se inicia com um pequeno conjunto de treinamento e, atraves da classificacao de um conjunto bem maior de avaliacao, aprende quais amostras sao as mais representativas para o conjunto de treinamento. Os resultados mostram que e possivel obter uma melhor acuracia que o Classificador OPF tradicional ao custo de um pequeno incremento no tempo de treinamento, mantendo, no entanto, o conjunto de treinamento menor que o conjunto inicial, o que significa um tempo de teste reduzido Abstract