J'ai environ 2 m enregistrements stockés dans une table. Chaque enregistrement a un numéro et environ 5K attributs booléens.
La table ressemble à quelque chose comme ça. et j'ai défini et existe des algorithmes intelligents pour la recherche d'une liste d'attributs Il serait génial s'il ya un moyen de trouver non seulement les listes maximales mais supérieures de n. Modifier
Il semble que ce ne soit pas possible de trouver la réponse sans brute forçage. Si j'ai changé la question pour trouver une "bonne estimation", y aurait-il un bon moyen de le faire?
Ou, si je disais que la cardinalité de L est fixée à quelque chose comme 10, serait-il un moyen de calculer le L?
Je serais heureux avec tout. somme (A, B) < / code> comme la somme des chiffres dans laquelle Ath et BTH attribuent des attributs sont vrais.
Par exemple, à partir des données d'échantillon ci-dessus: Somme (1, 3) = 3 + (-87) Parce que le 1er et les 3RD attributs sont T pour 3 et -87 somme () peut prendre n'importe quel nombre de paramètres: somme (1) et somme (5, 7 , ..., 3455) sont tous possibles. l où somme (L) < / code> rendrait le résultat maximum?
Évidemment, la forçage brute n'est pas réalisable pour ce grand jeu de données.
4 Réponses :
Aucun algorithme polynomial pour résoudre ce problème me vient à l'esprit. Je peux seulement vous suggérer une heuristique gourmande:
pour chaque attribut, calculez son Trier les attributs par en suivant cet ordre, ajoutez-vous gourmainement à Cela ne vous donnera pas l'optimal attendu_score , c'est-à-dire que l'addend apporterait à votre somme, si elle est sélectionnée seul . Dans votre exemple, le score de 1 est 3 - 87 = -84.
attendu_score dans l'ordre non croissant.
l les attributs. Appelez réel_score le score que l'attribut A apportera à votre somme (cela peut être meilleur ou pire que attendu_score , en fonction des attributs que vous déjà avoir dans l ). si réel_score (a) n'est pas strictement positif, jetez A .
l , mais je pense un "assez bon" un.
Vous pouvez essayer une approche d'algorithme génétique, en commençant par un certain nombre (grand) de combinaisons d'attributs aléatoires, laissant le pire x% mourir et la mutation d'un certain pourcentage de la population restante en ajoutant / supprime des attributs.
Il n'y a aucune garantie que vous trouverez la réponse optimale, mais une bonne chance de trouver un bon dans un délai raisonnable.
Il y a un problème avec cela (en fait j'ai mis à jour la réponse). Les colonnes ne cèdent pas toujours le même score. Cela dépend des colonnes que vous avez déjà sélectionnées.
Je vois - j'ai ignoré / mal interprété le petit mot "et"
Édité ma réponse, telle qu'elle était basée sur un malentendu
@Bing comme vous cherchez maintenant activement des moyens de trouver des "bonnes" réponses au lieu d'optimales: y a-t-il des propriétés supplémentaires des chiffres et ou de la matrice booléenne connue? Les chiffres sont-ils également distribués? Sur quelle gamme? La matrice est-elle peu peuplée, ou sont vraies et fausses valeurs également distribuées?
Remarque: voir ci-dessous pourquoi cette approche ne donnera pas les meilleurs résultats. em> Ma première approche serait de commencer avec le cas spécial L = {} (qui devrait donner la somme de tous les entiers) et ajoutez cela à une liste de solutions. De là ajouter des attributs possibles comme restrictions. Dans la première itération, essayez chaque attribut à son tour et rappelez-vous ceux qui ont donné un meilleur résultat. Après cette itération, placez les souvenirs dans une liste de solutions. P> dans la deuxième itération, essayez d'ajouter un autre attribut à chacun des souvenirs. Rappelez-vous tous ceux qui ont amélioré le résultat. Supprimez les doublons des combinaisons d'attribut mémorisées et ajoutez-les à la liste des solutions. Notez que {m, n} est identique à {n, m}, alors sautez des combinaisons redondantes afin de ne pas faire sauter vos ensembles. P> Répétez les secondes itérations jusqu'à ce qu'il n'y ait plus d'attributs possibles être ajouté pour améliorer la somme finale. Si vous commandez ensuite la liste des solutions par sa somme, vous obtenez la solution demandée. P> Notez qu'il existe environ 20 g de méthodes de sélection de trois attributs sur 5k, vous ne pouvez donc pas créer une structure de données contenant. ceux-ci mais vous devez absolument les générer à la demande. Néanmoins, le montant transparent peut produire de nombreuses solutions temporaires. Vous devez donc stocker ces personnes efficacement et peut-être même sur le disque. Vous pouvez exploiter le fait que vous n'avez besoin que des solutions de l'itération précédentes pour les prochaines itérations, pas celles précédentes. P> Une autre restriction est que vous pouvez vous retrouver avec moins de n meilleures solutions, car toutes les personnes ci-dessous L = {} ne sont pas pris en compte. Dans ce cas, j'accepterais toutes les solutions possibles jusqu'à ce que vous soyez des solutions, et une fois que vous n'avez que les N solutions qui ne jettent pas à ceux qui ne donnent pas une amélioration sur le pire. P> Code Python strud>: p> Considérez une solution temporaire composée des trois enregistrements P> -2, T, F
-2, F, T
+3, F, F
Ne fonctionne pas. Il pourrait facilement être le cas que vous devez ajouter un tas d'attributs qui aggravent la somme avant les ajouts ultérieurs les rendent utiles.
Tu as raison. J'ai ajouté une note selon la note et un exemple qui prouve votre réclamation. Merci!
Je pense que je vais essayer une deuxième approche, basée sur le potentiel d'une solution temporaire. Fondamentalement, la meilleure amélioration d'une solution que vous pouvez éventuellement obtenir est délimitée par moins la somme de tous les enregistrements avec un score négatif, si vous parvenez à jeter tous les enregistrements négatifs par un ensemble d'attributs de série. Ainsi, au lieu d'exiger qu'une solution temporaire améliore réellement les choses, vous pouvez jetter la solution lorsque son potentiel n'est pas inférieur à la valeur réelle de la solution actuelle. Besoin de penser à cette première ...
Malheureusement, ce problème est NP-complète . Vos options sont limitées à la recherche d'une solution bonne mais non maximale avec un algorithme d'approximation, ou à l'aide de branches et reliées et en espérant que vous ne frappez pas d'exécution exponentielle.
Preuve de NP-Telopess (Strong>
Pour prouver que votre problème est NP-complet, nous réduisons le Set Cover Cover problème à votre problème. Supposons que nous ayons un ensemble Premièrement, construisez une table avec Le dernier m Les lignes sont "définies", chacun correspondant à un ensemble dans Les valeurs des lignes d'élément sont suffisamment petites que tout choix d'attributs qui exclut toutes les lignes d'élément bat tout le choix d'attributs qui inclut toute ligne d'élément. Depuis que le syndicat de tous les ensembles dans Si nous avions un bon algorithme pour choisir un choix d'attributs qui produit la somme maximale, nous pourrions l'appliquer à ce tableau pour générer la couverture minimale d'un u de n éléments et un ensemble s de m sous-ensets de u , où le syndicat de tous les ensembles dans s est u . Le problème de la couverture définie demande le plus petit sous-ensemble t de s tel que chaque élément de u est contenu dans un élément de t < / code>. Si nous avions un algorithme de temps polynomial pour résoudre votre problème, nous pourrions résoudre le problème de la couverture définie comme suit:
m + n lignes et m attributs. Les premiers lignes n sont des lignes "éléments", chacun correspondant à un élément de u . Celles-ci ont une valeur "suffisamment négative"; -M-1 devrait suffire. Pour l'élément ligne i , l'attribut j TH est vrai si l'élément correspondant est pas dans le j th dans s .
s . Celles-ci ont une valeur 1 . Pour la ligne définie n + i , l'attribut i th est faux et tous les autres sont vrais.
s est u , cueillir tous les attributs exclut toutes les lignes d'élément, le meilleur choix d'attributs est donc celui qui inclut les lignes les plus définies sans y compris des rangées d'élément. Par la construction de la table, un choix d'attributs exclura toutes les lignes d'élément si l'union des ensembles correspondants est u , et si son score sera meilleur, il en va de mieux. Ainsi, le meilleur choix d'attributs correspond directement à une couverture minimale de s .
arbitraire . Ainsi, votre problème est aussi acharné que le problème de la couverture du jeu complet NP-complet, et vous ne devez pas perdre votre temps à essayer de proposer un algorithme efficace pour générer le choix parfait d'attributs.
Merci d'avoir partagé la preuve. Pourrait-on dire que cela ressemble également à une variante du problème de somme sous-ensemble? ( en.wikipedia.org / wiki / sousset_sum_problem # complexité )
@Ioannis: Peut-être. Je n'ai pas marché avec un moyen de réduire la somme des sous-ensembles à ce problème avant de trouver la réduction de la couverture définie.
+1, belle preuve. J'ai corrigé des petites fautes de frappe avec les indices, les rétablir / les réparer si je me suis trompé.
Les numéros d'enregistrement (2,29, ..- 87,98) sont-ils uniques?
Non, les chiffres ne sont pas uniques
Première question: Pouvez-vous faire quelque chose comme Somme (A1, pas A2, A3) et donc gagner le "score" de "pas A2" (c'est-à-dire où A2 est faux)? Deuxième question: Y a-t-il une limite à la cardinalité de L?
Oui, somme (A1, pas A2, A3) peut être fait
C'est vraiment mauvaises nouvelles :)
Il n'y a pas de limite à la cardinalité de L, cela peut être quelque chose entre 1 et 5k
@ gd1 Je voulais dire qu'il peut être fait s'il est nécessaire pour trouver la somme maximale (A1, A3). Je ne suis pas intéressé à trouver quelque chose comme Somme (A1, pas A2)
Euh, ok. C'est ce que je voulais savoir.
Dammit, s'il n'y avait pas de chiffres négatifs, cela ne serait que "retourner la liste vide".
La réponse est non. Il n'y a pas de bon algorithme. Preuve d'une exhaustivité NP à enregistrer sous peu ...
@Bing, ce que vous vouliez dire par
max somme (A1, A3) ? Somme (A1, A3) est déjà numéro@pkuderov Désolé pour la confusion, j'ai dit Max Sum (A1, A3) parce que je voulais dire des A1 et A3 qui céderaient à la somme maximale.
Les nombres négatifs peuvent également être transformés en positif par des attributs inverser (-87 -> 87 avec chaque hache '= pas Ax)
@Bing, trouve-t-il le maximum est une condition stricte dans votre cas ou vous serez ok avec "bon" résultat? Vous pouvez brute la force pour de petites questions et utiliser différentes heuristiques pour les autres. Alors, peut-être que vous devriez vous reformuler et essayer de trouver «de bonne» heuristique au moins?
@pkuderov non, les nombres négatifs ne peuvent pas être transformés en positif par inverse.
Je suis d'accord avec l'utilisateur sur celui-ci. Si vous regardez cela comme un problème de graphique, vous devez trouver des cliques (en fonction des attributs, donc n = 5000) pour déterminer ce qui est résumé. Dans le pire des cas, vous devrez trouver la clique maximale qui est complète NP. Vous pouvez probablement utiliser une branche et un algorithme lié pour limiter les choses un peu, mais étant donné que vous avez un coefficient caché de 2 millions, cela ne va probablement pas aider beaucoup.
Je fais des expériences et je me demande quelle est la distribution des drapeaux T / F et la gamme et la distribution des scores pour les enregistrements. La raison pour laquelle je demande est que d'utiliser un algorithme simple qui ajuste progressivement les solutions existantes, cela a donné le meilleur résultat après très peu de pas (même sur un ensemble de données plus petit), donc je me demande si la distribution n'affecte pas la comportement.