Use este identificador para citar ou linkar para este item: http://repositorio.ufc.br/handle/riufc/45070
Tipo: TCC
Título: Uma heurística gulosa para o problema de classificação geodésica
Autor(es): Vieira, Marcelo Pereira
Orientador: Araújo, Paulo Henrique Macêdo de
Palavras-chave: Geodésicas - classificação;Outlier;Teoria dos grafos
Data do documento: 2019
Citação: VIEIRA, Marcelo Pereira. Uma heurística gulosa para o problema de classificação geodésica. 2019. 39 f. Trabalho de Conclusão de Curso (Graduação em Ciência da Computação)-Universidade Federal do Ceará, Campus de Quixadá, Quixadá, 2019.
Resumo: Este trabalho propõe uma heurística gulosa com objetivo de gerar uma boa solução viável para o problema de Classificação Geodésica (CG). Esse problema foi introduzido em (ARAÚJO et al., 2019), onde os autores também apresentaram um modelo de programação linear inteira para resolvê-lo. O problema consiste em classificar informações, de acordo com dados préestabelecidos e representados por um grafo de similaridades. Para isso, é realizada a identificação de padrões definidos por convexidade geodésica. Neste trabalho, abordamos uma versão do problema CG com múltiplos grupos com o objetivo de identificar padrões de convexidade geodésica em grafos com maior acurácia. Analisamos a performance da heurística proposta utilizando experimentos computacionais tanto com instâncias realistas como aleatórias.
Abstract: This work proposes a greedy heuristic with the goal of generating a good feasible solution for the Geodesic Classification (GC) problem. This problem was introduced in (ARAÚJO et al., 2019), where the authors also presented an integer linear programming model to solve it. The GC problem consists to classify new data, according to pre-established data represented by a graph of similarities. To do so, we must identify patterns defined by geodesic convexity. In this work, we deal with the multi-groups version of the GC problem in order to identify geodesic convexity patterns on graphs with better accuracy. We analyze the performance of the proposed heuristic using computational experiments considering realistic and random instances.
URI: http://www.repositorio.ufc.br/handle/riufc/45070
Aparece nas coleções:CIÊNCIA DA COMPUTAÇÃO-QUIXADÁ - Monografias

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
2019_tcc_mpvieira.pdf568,27 kBAdobe PDFVisualizar/Abrir


Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.