Complete computation in subquadratic time of a new generic type of bicluster in dense and sparse matrices
Carregando...
Data
Autor(es)
Título da Revista
ISSN da Revista
Título de Volume
Editor
Universidade Federal de Minas Gerais
Descrição
Tipo
Dissertação de mestrado
Título alternativo
Computação completa em tempo subquadrático de um novo tipo de bicluster genérico em matrizes densas e esparsas
Primeiro orientador
Membros da banca
Wagner Meira Júnior
Renato Vimieiro
João Paulo Ataide Martins
Renato Vimieiro
João Paulo Ataide Martins
Resumo
Biclustering is a technique that is defined as a simultaneous clustering of rows and
columns of a data matrix. Given a m-by-n real matrix, this work defines a new type
of bicluster: in any of its columns, the values on the rows of the bicluster must be all
strictly greater than those on the rows absent from it. The rows that form a bicluster
can’t be a subset or superset of the rows contained in a different bicluster of greater
quality. The quality of a bicluster is a real value assigned from any computable function,
making the bicluster definition generic. "Muscly patterns" are biclusters that comply
with this definition.
Biceps is proposed to exhaustively list the muscly patterns in subquadratic time,
by enumerating possible biclusters in a DAG and selecting those with greater qualities.
The algorithm is divided in three phases: During the first phase, a DAG is built where
the vertices represent biclusters and edges represent an inclusion relationship between
the rows of connected biclusters. During the second phase, dynamic programming is
employed to discover biclusters that are better than any of its predecessor or successors,
which necessarily have a subset or superset of rows. Nonetheless, the edges in the graph
do not represent all possible inclusion relationships, thus a third phase is required to
discover only the muscly patterns among the bicluster obtained by the second phase.
The biclusters are listed within O(m²n + mn²) time, plus the time to compute
O(mn) qualities. After some adaptations, the proposed algorithm, Biceps, remains
subquadratic if its complexity is expressed in function of m non-min n, where m non-min
is the maximal number of non-minimal values in a column, i.e., for sparse matrices.
Experiments on three real-world datasets demonstrate the effectiveness of the proposal
in different application contexts. They also show its good theoretical efficiency is
practical as well: two minutes and 5.27 GB of RAM are enough to list the desired
biclusters in a dense 801-by-20,531 matrix; 3.5s and 192 MB of RAM for a sparse
631,532-by-174,559 matrix with 2,575,425 nonzero values.
Abstract
Biclustering é uma técnica definida como a clusterização simultânea de linhas e colunas
de uma matriz de dados. Dada uma matriz real m-por-n, esse trabalho define um
novo tipo de bicluster: em qualquer uma de suas colunas, os valores das linhas do
bicluster devem ser estritamente maiores do que os valores em todas as linhas ausentes
do mesmo. As linhas que formam um bicluster não podem ser um subconjunto ou um
superconjunto das linhas contidas em outro bicluster de maior qualidade. A qualidade
de um bicluster é um valor real dado por qualquer função computável, tornando a
definição genérica. "Muscly patterns" são os biclusters que respeitam a definição dada.
Biceps é proposto para listar exaustivamente os muscly patterns em tempo sub-quadrático,
enumerando os biclusters possíveis em um DAG e selecionando aqueles de
maior qualidade. O algoritmo é dividido em três fases: Durante a primeira fase, o DAG
é construído tal que seus vértices representem biclusters e suas arestas representem uma
relação de inclusão entre as linhas dos biclusters conectados. Durante a segunda fase,
programação dinâmica é utilizada para descobrir biclusters melhores que predecessores
ou sucessores que têm necessariamente um subconjunto ou superconjunto de linhas.
Apesar disso, as arestas do grafo não representam todas as possíveis relações de inclusão,
logo é necessária uma terceira fase para encontrar somente os muscly patterns
entre os biclusters obtidos pela segunda fase.
Os biclusters são listados em tempo O(m²n + mn²), mais o tempo para se computar O(mn) qualidades.
Após algumas adaptações, Biceps permanece subquadrático se sua complexidade é
expressada em função de m non-min n, onde m non-min é o número
máximo de valores não-mínimos em uma coluna (matrizes esparsas). Experimentos
em três datasets do mundo real demonstram a efetividade da proposta em diferentes
aplicações. Também mostram uma boa eficiência prática: 2 min e 5.27 GB de RAM
são suficientes para listar todos os biclusters em uma matriz densa de 801 × 20.531;
3.5s e 192 MB de RAM para uma matriz esparsa de 631.532 × 174.559 com 2.575.425
valores não-nulos.
Assunto
Computação – Teses., Mineração de dados Teses., Programação dinâmica – Teses., Problemas de enumeração combinatória – Teses., Biclustering – Teses.
Palavras-chave
Biclustering, Dynamic programming, Exhaustive enumeration, exclusive-columns biclusters, Subquadratic complexity