Please use this identifier to cite or link to this item: https://repositorio.ufrn.br/jspui/handle/123456789/24010
Title: Novas heurísticas para o agrupamento de dados pela soma mínima de distâncias quadráticas
Authors: Pereira, Thiago Correia
Keywords: Heurística;VNS;MSSC;Agrupamento de dados
Issue Date: 12-Apr-2017
Citation: 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.
Portuguese Abstract: 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.
Abstract: 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.
URI: https://repositorio.ufrn.br/jspui/handle/123456789/24010
Appears in Collections:PPGEE - Mestrado em Engenharia Elétrica e de Computação

Files in This Item:
File Description SizeFormat 
ThiagoCorreiaPereira_DISSERT.pdf841,48 kBAdobe PDFThumbnail
View/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.