Submitted by Automa??o e Estat?stica (sst@bczm.ufrn.br) on 2017-10-02T23:37:05Z
No. of bitstreams: 1
ThiagoCorreiaPereira_DISSERT.pdf: 849760 bytes, checksum: 18b8f71b02ed28bbc81789242e6e17b4 (MD5) / Approved for entry into archive by Arlan Eloi Leite Silva (eloihistoriador@yahoo.com.br) on 2017-10-09T19:56:01Z (GMT) No. of bitstreams: 1
ThiagoCorreiaPereira_DISSERT.pdf: 849760 bytes, checksum: 18b8f71b02ed28bbc81789242e6e17b4 (MD5) / Made available in DSpace on 2017-10-09T19:56:01Z (GMT). No. of bitstreams: 1
ThiagoCorreiaPereira_DISSERT.pdf: 849760 bytes, checksum: 18b8f71b02ed28bbc81789242e6e17b4 (MD5)
Previous issue date: 2017-04-12 / 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. / 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.
| Identifer | oai:union.ndltd.org:IBICT/oai:repositorio.ufrn.br:123456789/24010 |
| Date | 12 April 2017 |
| Creators | Pereira, Thiago Correia |
| Contributors | 03553729406, Aloise, D?rio Jos?, 05763088468, Santi, Everton, 01310830070, Aloise, Daniel |
| Publisher | PROGRAMA DE P?S-GRADUA??O EM ENGENHARIA EL?TRICA E DE COMPUTA??O, UFRN, Brasil |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | English |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Source | reponame:Repositório Institucional da UFRN, instname:Universidade Federal do Rio Grande do Norte, instacron:UFRN |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0027 seconds