Return to search

Reordenação de matrizes de dados quantitativos usando árvores PQR / Using PQR trees for quantitative data matrix reordering

Orientador: Celmar Guimarães da Silva / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Tecnologia / Made available in DSpace on 2018-08-27T09:05:54Z (GMT). No. of bitstreams: 1
Medina_BrunoFigueiredo_M.pdf: 3649814 bytes, checksum: ab007f9e22f1dab1394a99e9b4d80b4f (MD5)
Previous issue date: 2015 / Resumo: Matrizes são estruturas subjacentes a diferentes tipos de visualização de dados, como por exemplo, heatmaps. Diferentes algoritmos possibilitam uma permutação automática de suas linhas e colunas para prover um melhor entendimento visual, procurando agrupar linhas e colunas similares e evidenciar padrões. Trabalhos anteriores testaram e compararam alguns desses algoritmos em matrizes de dados binários, obtendo bons resultados o algoritmo PQR-Sort with Sorted Restrictions, em termos de tempo de execução e qualidade da reordenação em alguns tipos de matrizes. Contudo, este algoritmo não foi estendido para trabalhar com matrizes de dados quantitativos. Dessa forma, como continuidade desses trabalhos, este projeto testa a hipótese de que é possível elaborar variações do algoritmo PQR-Sort with Sorted Restrictions capazes de reordenar matrizes de dados quantitativos, e cuja eficiência de tempo e de qualidade da reordenação supere algoritmos de mesmo propósito. Neste projeto, foram elaborados os algoritmos Smoothed Multiple Binarization (SMB) e Multiple Binarization (MB). Ambos utilizam criação de vetores característicos (para descoberta de padrões canônicos de dados), árvores PQR e binarização de matrizes para sua reordenação. O SMB possui um potencial para prover boas reordernações de matrizes que contenham ruídos, pois faz o tratamento destes ruídos no conjunto de dados. Esses algoritmos foram testados e comparados com o Multidimensional Scaling (MDS) e algoritmo de Sugiyama adaptado (heurística baricêntrica), em termos de qualidade de reordenação e tempo de execução sobre matrizes sintéticas com os padrões canônicos Simplex, Band, Circumplex e Equi. Os resultados obtidos indicaram que os algoritmos SMB e MB destacaram-se dentre os demais pela capacidade de evidenciação do padrão Circumplex, e trouxeram resultados similares aos dos algoritmos testados para os padrões Equi e Band. Os resultados também indicam que SMB e MB são, em média, 3 e 6 vezes mais rápidos que o MDS, respectivamente. Deste modo, o uso de SMB e MB torna-se atrativo para a reordenação de matrizes que evidenciem padrões Circumplex, Equi e Band / Abstract: Matrices are structures underlying different types of data visualization, as heatmap. Different algorithms enable automatic permutation of their rows and columns to provide a better visual understanding, aiming to group similar rows and columns and show patterns. Earlier work tested and compared some of these algorithms on binary data matrices, and revealed that PQR-Sort with Sorted Restrictions algorithm returned good results in terms of runtime and quality of reordered matrix. However, this algorithm was not extended for quantitative data matrices. Thus, as a continuation of these studies, this project aims to test the hypothesis that it is possible to develop variations of the PQR-Sort with Sorted Restrictions algorithm able to reorder quantitative data matrices, and whose quality of results and time efficiency surpasses algorithms that have the same purpose. In this work, it was elaborated the Smoothed Multiple Binarization (SMB) and Multiple Binarization (MB). Both use feature selection (to discovering canonical pattern of data), PQR Tree and binary matrices for their reordering. SMB algorithm has a potential to provide good matrices reordering with noise, because it does the noise treatment in data sets. These algorithms were tested and compared with Multidimensional Scaling (MDS) and Adapted Sugiyama (or Barycentric Heuristic) algorithms, in terms of quality of reordering and runtime on synthetics matrices with the canonical patterns Simplex, Band, Circumplex and Equi. The results indicated that SMB and MB algorithms stood out from the others by capacity of highlight Circumplex pattern, besides showing that may to obtain similar results to MDS and Adapted Sugiyama for Equi and Band patterns. Furthermore, SMB and MB were, on average, 3 and 6 times faster than MDS, respectively. Thus, the use of the SMB and MB algorithms can be attractive for matrices reordering that evidence Circumplex, Equi and Band patterns / Mestrado / Tecnologia e Inovação / Mestre em Tecnologia

Identiferoai:union.ndltd.org:IBICT/oai:repositorio.unicamp.br:REPOSIP/267733
Date27 August 2018
CreatorsMedina, Bruno Figueiredo, 1990-
ContributorsUNIVERSIDADE ESTADUAL DE CAMPINAS, Silva, Celmar Guimarães da, 1978-, Pedronette, Daniel Carlos Guimarães, Nonato, Luís Gustavo
Publisher[s.n.], Universidade Estadual de Campinas. Faculdade de Tecnologia, Programa de Pós-Graduação em Tecnologia
Source SetsIBICT Brazilian ETDs
Detected LanguagePortuguese
Typeinfo:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis
Format77 f. : il., application/pdf
Sourcereponame:Repositório Institucional da Unicamp, instname:Universidade Estadual de Campinas, instacron:UNICAMP
Rightsinfo:eu-repo/semantics/openAccess

Page generated in 0.0022 seconds