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 | Tamanho | Formato | |
|---|---|---|---|---|
| 2019_tcc_mpvieira.pdf | 568,27 kB | Adobe PDF | Visualizar/Abrir |
Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.