Fast algorithms for the optimum-path forest-based classifier

Simple item page
dc.contributor.advisorOchoa Luna, José Eduardo
dc.contributor.advisorCastelo Fernández, César Christian
dc.contributor.authorCulquicondor Ruiz, Aldo Paolo
dc.date.accessioned2018-05-07T17:21:40Z
dc.date.available2018-05-07T17:21:40Z
dc.date.issued2018
dc.description.abstractPattern Recognition applications deal with ever increasing datasets, both in size and complexity. In this work, we propose and analyze efficient algorithms for the Optimum-Path Forest (OPF) supervised classifier. This classifier has proven to provide results comparable to most well-know pattern recognition techniques, but with a much faster training phase. However, there is still room for improvement. The contribution of this work is the introduction of spatial indexing and parallel algorithms on the training and classification phases of the OPF supervised classifier. First, we propose a simple parallelization approach for the training phase. Following the traditional sequential training for the OPF, it maintains a priority queue to compute best samples at each iteration. Later on, we replace this priority queue by an array and a linear search, in the aim of using a more parallel-friendly data structure. We show that this approach leads to more temporal and spatial locality than the former, providing better speedups. Additionally, we show how the use of vectorization on distance calculations affects the overall speedup and we provide directions on when to use it. For the classification phase, we first aim to reduce the number of distance calculations against the classifier samples and, then, we also introduce parallelization. For this purpose, we elaborate a novel theory to index the OPF classifier in a metric space. Then, we use it to build an efficient data structure that allows us to reduce the number of comparison with classifier samples. Finally, we propose its parallelization, leading to a very fast classification for new samples.es_PE
dc.description.uriTesises_PE
dc.formatapplication/pdfes_PE
dc.identifier.other1060274
dc.identifier.urihttps://hdl.handle.net/20.500.12590/15589
dc.language.isospaes_PE
dc.publisherUniversidad Católica San Pabloes_PE
dc.publisher.countryPEes_PE
dc.rightsinfo:eu-repo/semantics/openAccesses_PE
dc.rights.urihttps://creativecommons.org/licenses/by/4.0/es_PE
dc.sourceUniversidad Católica San Pabloes_PE
dc.sourceRepositorio Institucional - UCSPes_PE
dc.subjectAlgorithmes_PE
dc.subjectOptimun Path Forest (OPF)es_PE
dc.subjectImage Foresting Transformes_PE
dc.subject.ocdehttp://purl.org/pe-repo/ocde/ford#1.02.01es_PE
dc.titleFast algorithms for the optimum-path forest-based classifieres_PE
dc.typeinfo:eu-repo/semantics/bachelorThesis
thesis.degree.disciplineCiencia de la Computaciónes_PE
thesis.degree.grantorUniversidad Católica San Pablo. Facultad de Ingeniería y Computaciónes_PE
thesis.degree.levelTítulo Profesionales_PE
thesis.degree.nameLicenciado en Ciencia de la Computaciónes_PE
thesis.degree.programEscuela Profesional de Ciencia de la Computaciónes_PE
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
CULQUICONDOR_RUIZ_ALD_FAS.pdf
Size:
738.39 KB
Format:
Adobe Portable Document Format
Download
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
1.71 KB
Format:
Item-specific license agreed upon to submission
Description:
Download
Collections
Tesis - Ciencias de la Computación