Novas heurísticas para o agrupamento de dados pela soma mínima de distâncias quadráticas

Due to the large volume of data generated by the growth of applications that provide new information, both in volume and variety, more efficient techniques are required to classify and processes them. A widely used technique is data grouping whose aim is to extract characteristics of the entities...

ver descrição completa

Na minha lista:
Detalhes bibliográficos
Autor principal: Pereira, Thiago Correia
Outros Autores: Aloise, Daniel
Formato: Dissertação
Idioma:por
Publicado em: Brasil
Assuntos:
Heurística
VNS
MSSC
Agrupamento de dados
CNPQ::ENGENHARIAS::ENGENHARIA ELETRICA E DE COMPUTAÇÃO
Endereço do item:https://repositorio.ufrn.br/jspui/handle/123456789/24010
Tags: Adicionar Tag
Sem tags, seja o primeiro a adicionar uma tag!
id ri-123456789-24010
record_format dspace
spelling ri-123456789-240102022-04-01T19:40:55Z Novas heurísticas para o agrupamento de dados pela soma mínima de distâncias quadráticas Pereira, Thiago Correia Aloise, Daniel http://lattes.cnpq.br/8859180721390841 http://lattes.cnpq.br/5093210888872414 Aloise, Dário José Santi, Everton http://lattes.cnpq.br/1704949855287036 Heurística VNS MSSC Agrupamento de dados CNPQ::ENGENHARIAS::ENGENHARIA ELETRICA E DE COMPUTAÇÃO Due to the large volume of data generated by the growth of applications that provide new information, both in volume and variety, more efficient techniques are required to classify and processes them. A widely used technique is data grouping whose aim is to extract characteristics of the entities dividing them into homogeneous and/or well separated subsets. Many different criteria can be used to express the data classification. Among them, a commonly used criteria is the minimun sum-of-squares clustering (MSSC). In this criterion, entities are elements in n-dimensional Euclidean space. The data clustering problem by MSSC is NP-hard, then heuristics are extremely useful techniques for this type of problem. This work proposes new heuristics, based on the general variable neighborhood search (GVNS). Also proposed in this work is the adaptation of the heuristic reformulation descent (RD) to the MSSC problem, in the form of two variants, unapplied to this problem before in literature. The computational experiments show that the GVNS variants proposed in this work present better results, in large instances, than the current state of the art. Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) Devido ao grande volume de dados gerados pelo crescimento de aplicações que provêm novas informações, tanto em volume quanto em variedade, técnicas cada vez mais eficientes são exigidas para classificá-los e processá-los. Uma técnica muito utilizada é o agrupamento de dados, cujo objetivo é extrair conhecimento dos dados através da divisão de entidades em subconjuntos homogêneos e/ou bem separados. Critérios podem ser utilizados para expressar a classificação dos dados. Dentre eles, um critério frequentemente utilizado é a soma mínima das distâncias euclidianas quadráticas, do inglês, minimun sum-of-squares clustering (MSSC). Neste critério, entidades são elementos no espaço n-dimensional. O problema de agrupamento de dados pelo MSSC é NP-árduo, logo heurísticas são técnicas extremamente úteis para este tipo de problema. Este trabalho propõe novas heurísticas, baseadas na busca de vizinhanças variáveis gerais, do inglês, general variable neighborhood search (GVNS). Também é proposto neste trabalho, a adaptação da heurística reformulation descent (RD) para o problema MSSC, na forma de duas variantes, de forma inédita na literatura. Os experimentos computacionais mostram que as variantes GVNS propostas neste trabalho apresentam melhores resultados, para instâncias grandes. 2017-10-09T19:56:01Z 2017-10-09T19:56:01Z 2017-04-12 masterThesis PEREIRA, Thiago Correia. Novas heurísticas para o agrupamento de dados pela soma mínima de distâncias quadráticas. 2017. 99f. Dissertação (Mestrado em Engenharia Elétrica e de Computação) - Centro de Tecnologia, Universidade Federal do Rio Grande do Norte, Natal, 2017. https://repositorio.ufrn.br/jspui/handle/123456789/24010 por Acesso Aberto application/pdf Brasil UFRN PROGRAMA DE PÓS-GRADUAÇÃO EM ENGENHARIA ELÉTRICA E DE COMPUTAÇÃO
institution Repositório Institucional
collection RI - UFRN
language por
topic Heurística
VNS
MSSC
Agrupamento de dados
CNPQ::ENGENHARIAS::ENGENHARIA ELETRICA E DE COMPUTAÇÃO
spellingShingle Heurística
VNS
MSSC
Agrupamento de dados
CNPQ::ENGENHARIAS::ENGENHARIA ELETRICA E DE COMPUTAÇÃO
Pereira, Thiago Correia
Novas heurísticas para o agrupamento de dados pela soma mínima de distâncias quadráticas
description Due to the large volume of data generated by the growth of applications that provide new information, both in volume and variety, more efficient techniques are required to classify and processes them. A widely used technique is data grouping whose aim is to extract characteristics of the entities dividing them into homogeneous and/or well separated subsets. Many different criteria can be used to express the data classification. Among them, a commonly used criteria is the minimun sum-of-squares clustering (MSSC). In this criterion, entities are elements in n-dimensional Euclidean space. The data clustering problem by MSSC is NP-hard, then heuristics are extremely useful techniques for this type of problem. This work proposes new heuristics, based on the general variable neighborhood search (GVNS). Also proposed in this work is the adaptation of the heuristic reformulation descent (RD) to the MSSC problem, in the form of two variants, unapplied to this problem before in literature. The computational experiments show that the GVNS variants proposed in this work present better results, in large instances, than the current state of the art.
author2 Aloise, Daniel
author_facet Aloise, Daniel
Pereira, Thiago Correia
format masterThesis
author Pereira, Thiago Correia
author_sort Pereira, Thiago Correia
title Novas heurísticas para o agrupamento de dados pela soma mínima de distâncias quadráticas
title_short Novas heurísticas para o agrupamento de dados pela soma mínima de distâncias quadráticas
title_full Novas heurísticas para o agrupamento de dados pela soma mínima de distâncias quadráticas
title_fullStr Novas heurísticas para o agrupamento de dados pela soma mínima de distâncias quadráticas
title_full_unstemmed Novas heurísticas para o agrupamento de dados pela soma mínima de distâncias quadráticas
title_sort novas heurísticas para o agrupamento de dados pela soma mínima de distâncias quadráticas
publisher Brasil
publishDate 2017
url https://repositorio.ufrn.br/jspui/handle/123456789/24010
work_keys_str_mv AT pereirathiagocorreia novasheuristicasparaoagrupamentodedadospelasomaminimadedistanciasquadraticas
_version_ 1773964093684711424

Registros relacionados