Complete computation in subquadratic time of a new generic type of bicluster in dense and sparse matrices

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.