Recherchez le & # 8220; plus grand & # 8221; sous-matrice dense dans une grande matrice clairsemée

Question

Étant donné une grande matrice éparse (disons 10k + sur 1M +), il me faut trouver un sous-ensemble, pas nécessairement continu, de lignes et de colonnes qui forment une matrice dense (tous les éléments non nuls). Je veux que cette sous-matrice soit aussi grande que possible (pas la somme la plus grande, mais le plus grand nombre d’éléments) avec certaines contraintes de format.

Existe-t-il des solutions exactes ou aproxamates connues à ce problème?

Une analyse rapide de Google semble donner beaucoup de résultats proches mais pas exactement. Quels termes devrais-je rechercher?

modifier: Juste pour clarifier; la sous-matrice n'a pas besoin d'être continue . En fait, l'ordre des lignes et des colonnes est complètement arbitraire et la contiguïté n'a donc aucune pertinence.

Une pensée basée sur l’idée de Chad Okere

1. Ordonnez les lignes du plus grand nombre au plus petit (non nécessaire, mais peut aider perf)
2. Sélectionnez deux lignes comportant un " grand " chevauchement
3. Ajouter toutes les autres lignes qui ne réduiront pas le chevauchement
4. Enregistrer cet ensemble
5. Ajouter n'importe quelle ligne pour réduire le chevauchement au minimum
6. Répétez l'opération à l'étape 3 jusqu'à ce que le résultat soit trop petit
7. Recommencez à l'étape 2 avec une paire de départ différente
8. Continuez jusqu'à ce que vous décidiez que le résultat est assez bon

Answer 1

Je suppose que vous voulez quelque chose comme ça. Vous avez une matrice comme

1100101
1110101
0100101

Vous voulez les colonnes 1,2,5,7 et les lignes 1 et 2, n'est-ce pas? Cette sous-matrice serait 4x2 avec 8 éléments. Ou vous pouvez aller avec les colonnes 1,5,7 avec les lignes 1,2,3 qui serait une matrice 3x3.

Si vous souhaitez une méthode "approximative", vous pouvez commencer par un seul élément non nul, puis rechercher un autre élément non nul et l'ajouter à votre liste de lignes et de colonnes. À un moment donné, vous rencontrerez un élément non nul qui, si des lignes et des colonnes étaient ajoutées à votre collection, votre collection ne serait plus entièrement non nulle.

Donc, pour la matrice ci-dessus, si vous ajoutez 1,1 et 2,2, vous aurez les lignes 1,2 et les colonnes 1,2 dans votre collection. Si vous essayez d’ajouter 3,7, vous rencontrerez un problème car 1,3 est égal à zéro. Donc, vous ne pouvez pas l'ajouter. Vous pouvez cependant ajouter 2,5 et 2,7. Création de la sous-matrice 4x2.

En gros, il vous suffira d’itérer jusqu’à ce que vous ne trouviez plus de nouvelles lignes et colonnes à ajouter. Cela vous donnerait aussi un minimum local. Vous pouvez stocker le résultat et recommencer avec un autre point de départ (peut-être un point qui ne rentre pas dans votre solution actuelle).

Puis arrêtez-vous quand vous ne trouvez plus rien après un moment.

Cela prendrait évidemment beaucoup de temps, mais je ne sais pas si vous pourrez le faire plus rapidement.

Answer 2

S'agit-il d'un problème de Netflix ?

MATLAB ou d'autres bibliothèques matricielles éparses pourraient avoir des moyens de manipulez-le.

Votre intention est-elle d'écrire la vôtre?

Peut-être que l'approche 1D pour chaque rangée pourrait vous aider. L'algorithme pourrait ressembler à ceci:

1. Boucle sur chaque ligne
2. Trouver l'index du premier élément non nul
3. Recherchez l'index de l'élément de ligne différent de zéro avec la plus grande plage entre les colonnes non nulles de chaque ligne et stockez les deux.
4. Triez les lignes de la plus grande à la plus petite des colonnes non nulles.

À ce stade, je commence à être confus (désolé, pas un concepteur d'algorithmes). J'essayais de faire une boucle sur chaque ligne, en alignant les index du point de départ, en recherchant le maximum d'index de colonnes d'exécution non nuls que je pouvais.

Vous ne spécifiez pas si la matrice dense doit être carrée ou non. Je suppose que non.

Je ne sais pas à quel point c'est efficace ou quel serait son comportement. Mais c’est une méthode de force brute pour commencer.

Answer 3

EDIT. Ce n'est pas la même chose que le problème ci-dessous .. Mon mal ...

Mais sur la base du dernier commentaire ci-dessous, cela pourrait être équivalent à ce qui suit:

1. Trouvez la paire de points zéro la plus éloignée, séparée verticalement, sans aucun point zéro entre eux.
2. Trouvez la paire de points zéro la plus éloignée horizontalement qui ne comporte pas de zéros?

3. La région horizontale que vous recherchez est donc le rectangle qui se situe entre ces deux paires de points?

   Ce problème exact est décrit dans un bijou d'un livre intitulé "Programmation des perles". de Jon Bentley, et, si je me souviens bien, même s’il existe une solution dans une seule dimension, il n’existe pas de réponse simple aux variantes à deux dimensions ou plus ...

Le problème 1 = D consiste à trouver la plus grande somme d’un sous-ensemble contigu d’un ensemble de nombres:

parcourir les éléments, en gardant la trace du total cumulé d'un élément précédent spécifique, et du sous-total maximum vu jusqu'ici (et du début et de la fin qui l'a généré) ... A chaque élément, si le sous-total maxrunning est plus grand que le total maximum vu jusqu'ici, le maximum vu jusqu'ici et endelemnt sont réinitialisés ... Si le total cumulé maximum passe en dessous de zéro, l'élément de départ est réinitialisé sur l'élément actuel et le total cumulé est réinitialisé à zéro ...

Le problème 2D vient d’une tentative de génération d’un algorithme de traitement d’image, qui tentait de trouver, dans un flux de valeurs de luminosité représentant des pixels dans une image à 2 couleurs, le "plus lumineux". zone rectangulaire dans l'image. c'est-à-dire trouver la sous-matrice bidimensionnelle contenant la somme la plus élevée de valeurs de luminosité, où "Luminosité". a été mesurée par la différence entre la valeur de luminosité du pixel et la luminosité moyenne globale de l’ensemble de l’image (autant d’éléments avaient des valeurs négatives)

EDIT: Pour rechercher la solution 1-D, j’ai récupéré ma copie de la 2e édition de ce livre, et dans celle-ci, Jon Bentley a déclaré: "La version 2-D reste non résolue au moment où cette édition est imprimée." . " qui était en 1999.

Answer 4

Je sais que vous ne travaillez plus là-dessus, mais je pensais que quelqu'un pourrait avoir la même question que moi à l'avenir.

Donc, après avoir réalisé que c’était un problème difficile à résoudre (par réduction à MAX-CLIQUE), j’ai décidé de proposer une heuristique qui m’a bien fonctionné jusqu’à présent:

Avec une N x M matrice binaire / booléenne, trouvez une grande sous-matrice dense:

Partie I : Générez des sous-matrices candidates raisonnables

1. Considérez chacune des N lignes comme un vecteur binaire de M , v_i , où i = 1 à N
2. Calculez une matrice de distance pour les vecteurs N à l'aide de la distance de Hamming
3. Utilisez l'algorithme UPGMA (méthode de groupe de paires non pondérée avec moyenne arithmétique) pour regrouper des vecteurs

Initialement, chacun des vecteurs v_i est un cluster singleton. L'étape 3 ci-dessus (clustering) donne l'ordre dans lequel les vecteurs doivent être combinés en sous-matrices. Ainsi, chaque nœud interne de l’arbre de classification hiérarchique est une sous-matrice candidate.

Partie II : Marquez et classez les candidats sous-matrices

1. Pour chaque sous-matrice, calculez D , le nombre d'éléments dans le sous-ensemble dense des vecteurs de la sous-matrice en éliminant toute colonne avec un ou plusieurs zéros.
2. Sélectionnez la sous-matrice qui optimise D

J'ai également pris en compte le nombre minimal de lignes à conserver de la matrice complète initiale. Je supprime les sous-matrices candidates qui ne répondent pas à ce critère avant de sélectionner une sous-matrice avec max D valeur.