Résoudre un système d'équations avec des données clairsemées

J'essaie de résoudre un ensemble d'équations qui a 40 variables indépendantes (x1, ..., x40) et une variable dépendante (y). Le nombre total d'équations (nombre de lignes) est ~ 300, et je veux résoudre pour l'ensemble des 40 coefficients qui minimise l'erreur totale de somme des carrés entre y et la valeur prédite.

Mon problème est que la matrice est très clairsemée et je ne connais pas la meilleure façon de résoudre le système d'équations avec des données clairsemées. Un exemple de l'ensemble de données est illustré ci-dessous:

   y    x1  x2 x3 x4 x5 x6 ... x40
87169   14  0  1  0  0  2  ... 0 
46449   0   0  4  0  1  4  ... 12
846449  0   0  0  0  0  3  ... 0
....

J'utilise actuellement un algorithme génétique pour résoudre ce problème et les résultats sortent avec environ un facteur de différence de deux entre observé et attendu.

Quelqu'un peut-il suggérer différentes méthodes ou techniques capables de résoudre un ensemble d'équations avec des données rares.

Si je vous comprends bien, c'est le cas de la régression linéaire multiple avec des données clairsemées ( régression clairsemée ). En supposant cela, j'espère que vous trouverez les ressources suivantes utiles.

1) Diapositives de conférence du NCSU sur la régression clairsemée avec aperçu des algorithmes, notes, formules, graphiques et références à la littérature: http://www.stat.ncsu.edu/people/zhou/courses/st810/notes/lect23sparse.pdf

2) l' Récosystème propose de nombreux packages , utiles pour l'analyse de régression clairsemée, notamment:

• Matrice ( http://cran.r-project.org/web/packages/Matrix )
• SparseM ( http://cran.r-project.org/web/packages/SparseM )
• MatrixModels ( http://cran.r-project.org/web/packages/MatrixModels )
• glmnet ( http://cran.r-project.org/web/packages/glmnet )
• flare ( http://cran.r-project.org/web/packages/flare )

3) Un article de blog avec un exemple de solution de régression clairsemée , basé sur SparseM: http://aleph-nought.blogspot.com/2012/03/multiple-linear-regression-with-sparse.html

4) Un article de blog sur l'utilisation de matrices clairsemées dans R , qui comprend une introduction à l'utilisation glmnet: http://www.johnmyleswhite.com/notebook/2011/10/31/using-sparse-matrices-in-r

5) Plus d'exemples et quelques discussions sur le sujet peuvent être trouvés sur StackOverflow : /programming/3169371/large-scale-regression-in-r-with-a-sparse-feature-matrix

MISE À JOUR (basée sur votre commentaire):

Si vous essayez de résoudre un problème LP avec des contraintes, vous pouvez trouver cet article théorique utile: http://web.stanford.edu/group/SOL/papers/gmsw84.pdf .

Vérifiez également le package R limSolve : http://cran.r-project.org/web/packages/limSolve . Et, en général, vérifiez les packages dans la vue des tâches CRAN "Optimisation et programmation mathématique" : http://cran.r-project.org/web/views/Optimization.html .

Enfin, consultez le livre "Utilisation de R pour l'analyse numérique en science et en génie" (par Victor A. Bloomfield). Il contient une section sur la résolution de systèmes d'équations, représentés par des matrices clairsemées (section 5.7, pages 99-104), qui comprend des exemples, basés sur certains des packages mentionnés ci-dessus: http://books.google.com/books? id = 9ph_AwAAQBAJ & pg = PA99 & lpg = PA99 & dq = r + limsolve + clairsemée + matrice & source = bl & ots = PHDE8nXljQ & sig = sPi4n5Wk0M02ywkubq7R7KD_b04 & hl = fr & sa = X & ei = FZjiU-ioIcjmsATGkYDAAg & ved = 0CDUQ6AEwAw # v = OnePage & q = r% 20limsolve% 20sparse% 20matrix & f = false .

La réponse d'Aleksandr est tout à fait correcte.

Cependant, la façon dont la question est posée implique qu'il s'agit d'une question de régression des moindres carrés ordinaires simple: minimiser la somme des résidus au carré entre une variable dépendante et une combinaison linéaire de prédicteurs.

Maintenant, bien qu'il puisse y avoir de nombreux zéros dans votre matrice de conception, votre système en tant que tel n'est pas trop volumineux: 300 observations sur 40 prédicteurs ne sont que de taille moyenne. Vous pouvez exécuter une telle régression à l'aide de R sans efforts particuliers pour les données éparses. Utilisez simplement la lm()commande (pour "modèle linéaire"). Utilisez ?lmpour voir la page d'aide. Et notez que lmpar défaut, vous ajouterez silencieusement une colonne constante de ceux à votre matrice de conception (l'interception) - incluez un -1sur le côté droit de votre formule pour supprimer cela. Dans l'ensemble, en supposant que toutes vos données (et rien d'autre) se trouvent dans un data.frameappelé foo, vous pouvez le faire:

model <- lm(y~.-1,data=foo)

Et puis vous pouvez regarder des estimations de paramètres, etc. comme ceci:

summary(model)
residuals(model)

Si votre système est beaucoup plus volumineux, disons de l'ordre de 10 000 observations et de centaines de prédicteurs, il peut sembler judicieux d' examiner des solveurs clairsemés spécialisés selon la réponse d'Aleksandr .

Enfin, dans votre commentaire à la réponse d' Aleksandr , vous mentionnez des contraintes sur votre équation. Si c'est réellement votre problème principal, il existe des moyens de calculer les moindres carrés contraints dans R. J'aime personnellement pcls()dans le mgcvpackage. Peut-être souhaitez-vous éditer votre question pour inclure le type de contraintes (contraintes box, contraintes de non-négativité, contraintes d'intégralité, contraintes linéaires, ...) auxquelles vous êtes confronté?