Encontre o “maior” sub matriz densa em uma grande matriz esparsa

StackOverflow https://stackoverflow.com/questions/1217355

Pergunta

Dada a grande matriz esparsa (dizer 10k + por 1M +) Eu preciso encontrar um subconjunto, não necessariamente contínua, das linhas e colunas que formam uma matriz densa (todos os não-zero elementos). Quero que este sub matriz para ser tão grande quanto possível (não a maior soma, mas o maior número de elementos) dentro de alguns constrangimentos relação de aspecto.

Existem soluções conhecidas exatas ou aproxamate para este problema?

Uma verificação rápida no Google parece dar um monte de resultados perto-mas-não-exatamente. Que termos eu deveria estar procurando?

edit: Só para esclarecer; o sub matriz não precisa ser contínua . Na verdade, a fim de linha e coluna é completamente arbitrária assim adjacência é completamente irrelevante.

Um pensamento baseado na idéia de Chad Okere

  1. Despacho as linhas de maior contagem a menor contagem (não necessário, mas poderia ajudar perf)
  2. Selecione duas linhas que têm um "grande" sobreposição
  3. Adicionar todas as outras linhas que não vai reduzir a sobreposição
  4. Gravar esse conjunto
  5. Adicione o que linha reduz a sobreposição pelo menos
  6. Repita a posição # 3 até que o resultado chega a pequena
  7. Iniciar mais em # 2 com um par de partida diferente
  8. Continue até que você decida o resultado é bom o suficiente
Foi útil?

Solução

Eu suponho que você quer algo como isto. Você tem uma matriz como 

1100101
1110101
0100101

Você quer colunas 1,2,5,7 e linhas 1 e 2, certo? Isso submatrix seria 4x2 com 8 elementos. Ou você poderia ir com colunas 1,5,7 com linhas 1,2,3 o que seria uma matriz 3x3.

Se você quer um método 'aproximado', você poderia começar com um único elemento diferente de zero, em seguida, vá para encontrar um outro elemento diferente de zero e adicioná-lo à sua lista de linhas e colunas. Em algum momento você vai correr em um elemento diferente de zero que, se é linhas e colunas foram adicionadas à sua coleção, sua coleção já não seria inteiramente diferente de zero.

Assim, para a matriz acima, se você adicionou 1,1 e 2,2 você teria linhas 1,2 e colunas 1,2 em sua coleção. Se você tentou adicionar 3,7 causaria um problema porque 1,3 é zero. Então você não pode adicioná-lo. Você poderia adicionar 2,5 e 2,7 embora. Criando o submatrix 4x2.

Você seria basicamente iterate até que você não pode encontrar nenhum mais novas linhas e colunas para adicionar. Que iria ficar você também um mínimo local. Você poderia armazenar o resultado e começar de novo com mais um ponto (talvez um que não se encaixam em sua solução atual) começo.

Em seguida, basta parar quando você não consegue encontrar qualquer mais depois de um tempo.

Isso, obviamente, levaria um longo tempo, mas eu não sei se você vai ser capaz de fazê-lo mais rapidamente.

Outras dicas

É este um Netflix problema ?

MATLAB ou algumas outras bibliotecas escassas da matriz pode ter formas de lidar com isso.

É sua intenção de escrever o seu próprio?

Talvez a abordagem 1D para cada linha iria ajudá-lo. O algoritmo pode ter esta aparência:

  1. loop sobre cada linha
  2. Encontre o índice da primeira diferente de zero elemento
  3. Encontre o índice do elemento de linha diferente de zero com o maior vão entre diferentes de zero colunas em cada linha e armazenar ambos.
  4. Classificar as linhas da maior para a menor extensão entre diferentes de zero colunas.

Neste momento eu começar a ficar difusa (desculpe, não um designer de algoritmo). Eu tentaria fazer loop para cada linha, alinhando os índices do ponto de partida, procurando o máximo diferente de zero série de índices de colunas que eu podia.

Você não especificar se a matriz densa tem de ser quadrado. Vou não assume.

Eu não sei o quão eficiente este é ou o que seu comportamento Big-O seria. Mas é um método de força bruta para começar.

EDIT. Este não é o mesmo que o problema abaixo .. Meu mau ...

Mas com base no último comentário abaixo, pode ser equivilent com o seguinte:

  1. Encontre o mais distante par de zero pontos que não têm nenhum ponto zero entre eles separados verticalmente.
  2. Encontre o mais distante par de zero pontos que não têm zeros entre eles horizontalmente separados?

  3. Em seguida, a região horizontal que você está procurando é o retângulo que se encaixa entre esses dois pares de pontos?

    Este problema exato é discutido em uma jóia de um livro chamado "Programação Pearls" por Jon Bentley, e, se bem me lembro, embora não haja uma solução em uma dimensão, não há uma resposta fácil para o 2-d ou superior variantes dimensionais ...

O 1 = D problema é, de forma eficaz, encontrar a maior soma de um subconjunto contíguo de um conjunto de números:

percorrer os elementos, mantendo o controle de um total de execução de um elemento anterior específico, eo subtotal máximo visto até agora (eo elemnt início e fim que generateds TI) ... Em cada elemento, se o subtotal maxrunning é maior do que o total máximo visto até agora, o máximo visto até agora e endelemnt são repostas ... Se o total em execução max vai abaixo de zero, o elemento inicial é redefinido para o elemento atual e a execução total é reposto a zero ...

O problema 2-D veio de uma tentativa de gerar um algoritmo de processamento de imagem visual, que estava a tentar encontrar, dentro de um fluxo de valores brightnesss representando pixels em uma imagem de 2 cores, encontrar o "mais brilhante" área retangular dentro da imagem. isto é, encontrar o continha 2-D de sub-matriz com a maior soma de valores de brilho, em que "Brilho" foi medida pela diferença entre o valor brighness do pixel e o brilho médio global de toda a imagem (tantos elementos tinham valores negativos)

EDIT: Para procurar a solução 1-D I dragado minha cópia da 2ª edição deste livro, e nele, Jon Bentley diz ", a versão mantém-se 2-D por resolver como esta edição vai para imprimir ... "que era em 1999.

Eu sei que você não está trabalhando em mais isso, mas eu pensei que alguém pode ter a mesma pergunta que me no futuro.

Assim, depois de perceber que este é um problema NP-hard (por redução ao MAX-CLIQUE) eu decidi vir para cima com uma heurística que tem funcionado bem para mim até agora:

Dado um N x M binário / boolean matriz, encontrar um grande densa submatrix:

Parte I : Gerar candidato razoável submatrizes

  1. Considere cada uma das fortes <> N fortes linhas a ser um M -dimensional vector binário, v_i , onde i = 1 a N
  2. Computar uma matriz de distâncias para o N fortes vectores utilizando a distância de Hamming
  3. Uso do UPGMA (não ponderada Método Grupo Par com Média Aritmética) algoritmo para agrupar vectores

Inicialmente, cada um dos v_i fortes vectores é um cluster Singleton. Passo 3 acima (cluster) dá a ordem em que os vectores devem ser combinados em submatrizes. Assim, cada nó interno na árvore de agrupamento hierárquico é uma submatriz candidato.

Parte II : Pontuação e classificação candidato submatrizes

  1. Para cada submatriz, calcule D , o número de elementos no subconjunto denso dos vectores para a submatriz por eliminação de qualquer coluna com um ou mais zeros.
  2. Selecione a submatriz que maximiza D

Eu também tive algumas considerações sobre o número min de linhas que precisava ser preservada a partir da matriz completa inicial, e gostaria de descartar quaisquer submatrizes candidatos que não cumprem estes critérios antes de selecionar uma submatriz com max D valor.

Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top