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...
Na minha lista:
Autor principal: | |
---|---|
Outros Autores: | |
Formato: | Dissertação |
Idioma: | por |
Publicado em: |
Brasil
|
Assuntos: | |
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 |