Please use this identifier to cite or link to this item: http://repositorio.ufgd.edu.br/jspui/handle/prefix/4338
metadata.dc.type: Trabalho de Conclusão de Curso
Title: Redução de template aplicado a K-Nearest Neighbor e Floresta de Caminhos Ótimos em problemas de reconhecimento de padrões
Other Titles: Template reduction applied to K-Nearest Neighbor and Optimum-Path Forest in problems pattern recognition
metadata.dc.creator: Lemke, Francisco Samuel
Thiry Neto, Paulo Alberto
metadata.dc.contributor.advisor1: Amorim, Willian Paraguassu
metadata.dc.contributor.referee1: Cruz, Adailton José Alves da
metadata.dc.contributor.referee2: Táparo, Murilo
metadata.dc.description.resumo: Um dos algoritmos clássicos da área de aprendizagem e classicação de dados é o KNN (K Nea- rest Neighbors). O algoritmo KNN é de aprendizado supervisionado, sendo o resultado da consulta de uma nova instância é classicado com base na classe majoritária dos K vizinhos mais próximos. O KNN apresenta algumas desvantagens, como a cada nova consulta será necessário calcular a dis- tância para todas as amostras de treinamento para chegar a uma determinada classicação, exigindo um elevado tempo de processamento. Outra abordagem que vem sendo utilizada na classicação de padrões é o OPF (Floresta de Caminhos Ótimos). OPF é um framework para classicação de dados supervisionados e não supervisionados, particularmente eciente na classicação de imagens, que reduz problemas de classicação de padrões para um problema de particionamento dos vértices de um grafo. Um dos possíveis problemas que pode ser encontrado no uso da técnica OPF, é a classicação de grandes volumes de dados. Para a fase de treinamento é necessário calcular o grafo completo, ou seja, a distância entre todas as amostras, o que em uma base de treinamento muito grande usará grande tempo de processamento. O método Template Reduction (TR), proposto neste trabalho, tem como objetivo obter um modelo menor, um subconjunto extraído do conjunto de treino. A ideia principal do TR é encontrar as regiões de fronteira entre as diferentes classes do conjunto de treino, e descartar os protótipos que estão longe desta região. Neste trabalho, avalia- mos o uso do TR, e após a aplicação ao KNN e OPF. Avaliamos, pelos resultados, que a proposta apresentada TR, obteve resultados satisfatórios, mesmo não conseguindo os melhores resultados de taxa de classicação, ainda se mostra eciente, diminuindo signicativamente o volume de dados, e acelerando o processo de aprendizagem e classicação.
Abstract: An of the classic algorithms in the area of learning and classication of data is the KNN (K Nearest Neighbors). The KNN algorithm is supervised learning, where the consultation result of a new instance is classied based on the dominant class of K nearest neighbors. The KNN has some disadvantages, as each new consultation will need to calculate the distance to all training samples to reach a certain ranking, requiring a high processing time. Another approach that has been used in pattern classication is the OPF (Optimum Path-Forest). OPF is a framework for data classication, supervised and unsupervised, particularly eective in image classication, which reduces problems of pattern classication to a problem of partitioning the vertices of a graph. One of the possible problems that may be encountered in the use of the technique OPF is the classication of large volumes of data. For the training phase is necessary to calculate the complete graph, in other words, the distance between all samples, which in a training base too large will cause a high processing time. The method Template Reduction (TR), the present paper aims to obtain a smaller model, a subset extracted from the training set. The main idea is to nd the TR border regions between dierent classes of the training set, and discard prototypes that are far from this region. In this study, we evaluated the use of TR, and after applying the KNN and OPF. We evaluate the results, the proposal TR, achieved satisfactory results, while not getting the best results of classication rate, yet is ecient, signicantly reducing the volume of data, and accelerating the learning process and classication.
Keywords: Aprendizado de máquina
Machine learning
metadata.dc.subject.cnpq: CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::METODOLOGIA E TECNICAS DA COMPUTACAO::SISTEMAS DE INFORMACAO
metadata.dc.language: por
metadata.dc.publisher.country: Brasil
Publisher: Universidade Federal da Grande Dourados
metadata.dc.publisher.initials: UFGD
metadata.dc.publisher.department: Faculdade de Ciências Exatas e Tecnologia
Citation: LEMKE, Francisco Samuel; THIRY NETO, Paulo Alberto. Redução de template aplicado a K-Nearest Neighbor e Floresta de Caminhos Ótimos em problemas de reconhecimento de padrões. 2013. Trabalho de Conclusão de Curso (Bacharelado em Sistemas de Informação) – Faculdade de Ciências Exatas e Tecnologias, Universidade Federal da Grande Dourados, Dourados, MS, 2013.
metadata.dc.rights: Acesso Restrito
URI: http://repositorio.ufgd.edu.br/jspui/handle/prefix/4338
Issue Date: 9-Apr-2013
Appears in Collections:Sistemas de Informação

Files in This Item:
File Description SizeFormat 
FranciscoSamuelLemke - PauloAlbertoThiryNeto - restrito.pdf344,52 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.