Use este identificador para citar o ir al link de este elemento: http://hdl.handle.net/1843/SLSS-8GQJ46
Tipo: Dissertação de Mestrado
Título: GRASP com path-relinking para agrupamento de dados biológicos
Autor(es): Rafael de Magalhaes Dias Frinhani
primer Tutor: Ricardo Martins de Abreu Silva
primer Co-tutor: Geraldo Robson Mateus
primer miembro del tribunal : Maurício Guilherme de Carvalho Resende
Segundo miembro del tribunal: Thiago Ferreira de Noronha
Resumen: O agrupamento é um método não supervisionado de classificação de dados em grupos (clusters). Em problemas de agrupamento, não se sabe previamente quantas e quais as classes necessárias para descrever coerentemente um conjunto de dados. Na biologia computacional, o agrupamento mostrou-se ferramenta útil em problemas de descoberta de padrões em dados como classificação de proteínas, predição da localização de proteínas em unidades celulares e diagnóstico de câncer. Recentemente, técnicas de otimização, como as metaheurísticas, têm sido utilizadas na literatura como método alternativo ou auxiliar para aumentar a eficiência e eficácia das ferramentas clássicas de agrupamento, geralmente baseadas em métodos estatísticos e matemáticos. O objetivo deste trabalho é propor algoritmos híbridos fundamentados nas metaheurísticas Greedy Randomized Adaptative Search Procedure (GRASP) e Path-Relinking para o problema de agrupamento de dados biológicos, com intuito de obter melhores soluções quando considerado unicamente o GRASP na sua forma padrão. Portanto, neste trabalho, considera-se a hipótese que o Path-Relinking como estratégia de intensificação do GRASP, melhora o desempenho e qualidade das soluções. Considera-se a hibridização do GRASP proposto por Nascimento et al. [2010b], com quatro variações do Path-Relinking: Forward, Backward, Mixed, e Greedy Randomized Adaptative. A validação das soluções obtidas dá-se por meio da comparação com os algoritmos clássicos k-means, k-medians, PAM (Partitioning Around Medoids) bem como o GRASP proposto por Nascimento et al. [2010b]. Os experimentos foram realizados com dados reais de 10 instâncias biológicas, e os resultados mostraram que o modelo híbrido melhorou a tarefa de agrupamento. Obteve-se maior exploração do espaço de busca, maior coesão de agrupamentos, aumento da robustez e redução do tempo computacional. As variantes Greedy Randomized Adaptative e Mixed apresentaram os melhores resultados.
Abstract: Clustering is an unsupervised method of classifying data into clusters. In clustering problems, it is not previously known how many and which classes are needed to describe coherently a set of data.In computational biology, data clustering proved to be useful in problems of patterns discovery in data such as protein classification, prediction of protein localization in cell units and cancer diagnosis.Recently, optimization techniques like metaheuristics, have been used frequently in the literature as an alternative or adjunct to increase the efficiency and effectiveness of the classic tools of clustering, usually based on statistical and mathematical methods. In this study we proposed hybrid algorithms based on metaheuristics GRASP and Path-Relinking for the clustering problem of biological data, aiming to obtain better solutions when compared to using only the GRASP in its standard form. Therefore, in this work, we considered the hypothesis that using the Path-Relinking as a strategy for intensifying GRASP, improves performance and quality of solutions. We consider hybridization of the GRASP proposed by Nascimento et al. [2010b], with four variants of Path-Relinking: forward, backward, mixed, and greedy randomized adaptative. The validation of solutions is given by comparing with the classic algorithms k-means, k-medians, PAM (Partitioning Around Medoids) as well as GRASP proposed by Nascimento et al. (2010).The experiments were performed with real data from 10 biological instances, and results showed that the hybrid model improved the clustering task. We obtained further exploration of the search space, more cohesive clusters, increase of robustness and reduction of computational time. Greedy Randomized Adaptive and Mixed showed the best results.
Asunto: Computação
Biologia computacional
Idioma: Português
Editor: Universidade Federal de Minas Gerais
Sigla da Institución: UFMG
Tipo de acceso: Acesso Aberto
URI: http://hdl.handle.net/1843/SLSS-8GQJ46
Fecha del documento: 2-mar-2011
Aparece en las colecciones:Dissertações de Mestrado

archivos asociados a este elemento:
archivo Descripción TamañoFormato 
rafaeldiasfrinhani.pdf2.24 MBAdobe PDFVisualizar/Abrir


Los elementos en el repositorio están protegidos por copyright, con todos los derechos reservados, salvo cuando es indicado lo contrario.