Matroids Matheplanet Forum Index
Moderiert von matroid
Mathematik » Numerik & Optimierung » Optimierung Standardabweichung
Autor
Universität/Hochschule Optimierung Standardabweichung
Typhon1982
Junior Letzter Besuch: im letzten Quartal
Dabei seit: 29.10.2022
Mitteilungen: 5
  Themenstart: 2022-10-29

Hallo zusammen, Ich habe 50 Vektoren mit je 20.000 Zeilen. Jeder dieser Vektoren hat eine Standardabweichung und Summe. Ich soll nun 5 Pakete aus diesen 50 Vektoren schnüren (1Paket ist die Summe mehrerer Vektoren), so dass die Pakete wiederum eine minimale Standardabweichung besitzen. Ausser reinem Ausprobieren habe ich keine Idee wie das funktionieren soll. Mit meinem Schulwissen über Extremwertaufgaben komme ich hier auch nicht weiter. Kann mir jemand helfen? Danke und Gruß aus Hamburg Oliver


   Profil
lula
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 17.12.2007
Mitteilungen: 11429
Wohnort: Sankt Augustin NRW
  Beitrag No.1, eingetragen 2022-10-29

Hallo Für was die Standardabweichung, pro Zelle oder nur für die Summe? Lula


   Profil
Typhon1982
Junior Letzter Besuch: im letzten Quartal
Dabei seit: 29.10.2022
Mitteilungen: 5
  Beitrag No.2, vom Themenstarter, eingetragen 2022-10-30

Hallo zusammen Ich zeige es mal mit einem Beispiel. Ich habe 4 Vektoren (A-D) mit je 6 Elementen. A B C D 1 2 5 1 3 4 4 5 5 2 3 4 2 3 2 2 3 1 1 3 1 2 2 1 Wenn ich daraus 2 Pakete bilden will, dann habe ich drei Kombinationsmöglichkeiten Möglichkeit Paket 1 Paket 2 1. Möglichkeit A+B C+D 2. Möglichkeit A+C B+D 3. Möglichkeit A+D B+C mit den Standardabweichungen Möglichkeit Paket 1 Paket 2 SUMME 1. Möglichkeit 1.67 2.06 3.74 2. Möglichkeit 1.80 2.08 3.88 3. Möglichkeit 2.73 1.95 4.68 Somit würde ich sagen, dass die 1.Möglichkeit diejenige mit der niedrigsten "Gesamtstandardabweichung" ist. Jetzt brauche ich "nur" einen Weg diese Lösung bei 50 Vektoren und 5 Paketen mathematisch zu bestimmen ohne alles durchkombinieren zu müssen. Besten Dank und Gruß Oliver


   Profil
N-man
Senior Letzter Besuch: im letzten Quartal
Dabei seit: 15.10.2002
Mitteilungen: 2579
Wohnort: Zürich
  Beitrag No.3, eingetragen 2022-10-30

Hallo Typhon Deine Frage ist mir noch nicht komplett klar. Aber so wie ich es verstehe, kann man einfach ausnutzen, dass sich bei der Summe unabhängiger Zufallsgrössen die Varianzen der Zufallsgrössen auch einfach addieren. Die kleinste Varianz und damit die kleinste Standardabweichung solltest du deswegen dann bekommen, wenn du die fünf Vektoren mit den fünf kleinsten Standardabweichungen addierst. Grüsse Manuel


   Profil
Typhon1982
Junior Letzter Besuch: im letzten Quartal
Dabei seit: 29.10.2022
Mitteilungen: 5
  Beitrag No.4, vom Themenstarter, eingetragen 2022-10-30

Hallo Manuel, in meinem Beispiel sind das die Standardabweichungen der Vektoren Vektor A B C D STD 1.38 0.94 1.34 1.49 Wenn ich dich richtig verstanden habe, müsste man durch Addition der Vektoren B+C (, da B und C kleinste Stdev haben) die kleinste "Gesamtstandardabweichung" bekommen. Zwei Probleme: Erstens: das ist nicht der Fall A+B die kleinste "Gesamtstandardabweichung" hat. Zweitens: Da ich alle Vektoren einem Paket zuordnen muss, hätte ich dann auch ein Paket der schlechtesten Standardabweichungen. Ich will aber, dass die Gesamtstandardabweichung klein wird. Ich finde es schwer das Problem zu beschreiben, aber ich hoffe ihr habt es verstanden.


   Profil
N-man
Senior Letzter Besuch: im letzten Quartal
Dabei seit: 15.10.2002
Mitteilungen: 2579
Wohnort: Zürich
  Beitrag No.5, eingetragen 2022-10-30

Hallo Typhon Ja, da war ich zu vorschnell. Für "Stichproben" funktioniert das Argument über die Summe der Varianzen nicht. Ich habe mir einmal wieder genauer in Erinnerung gerufen, wie die Situation für die Summe zweier Vektoren Z=X+Y aussehen würde. \[ s_Z^2=\frac{1}{n}\sum_i\left(z_i-\bar{z}\right)^2=\frac{1}{n}\sum_i\left(x_i-\bar{x}+z_i-\bar{z}\right)^2=s_x^2+s_y^2-\frac{2}{n}\sum_i\left(x_i-\bar{x}\right)\left(y_i-\bar{y}\right)\] Die Varianz des Summenvektors Z ist also die Summe der Varianzen der Vektoren X und Y abzüglich der doppelten empirischen Kovarianz von X und Y. Im Falle von Stichproben ist die empirische Kovarianz ja aber nicht null, selbst wenn die Vektoren dahinter unabhängig voneinander erzeugt werden. Für fünf Summanden wird die Situation entsprechend noch deutlich unübersichtlicher. Mir kommt jetzt keine andere Idee, als das wirklich per Bruteforce durchzuprobieren. Es gibt 2'118'760 Möglichkeiten aus den 50 Vektoren 5 Vektoren auszuwählen. Das wäre beherrschbar, wenn auch kein eleganter Lösungsweg. Vielleicht kann dir jemand anderes kompetenter weiterhelfen. Grüsse, Manuel


   Profil
Typhon1982
Junior Letzter Besuch: im letzten Quartal
Dabei seit: 29.10.2022
Mitteilungen: 5
  Beitrag No.6, vom Themenstarter, eingetragen 2022-10-30

Moin Daniel, danke schonmal für s Problem verstehen. Ich muss über deine Antwort allerdings mal nachdenken. Schönen Gruß Oliver


   Profil
Bozzo
Senior Letzter Besuch: im letzten Monat
Dabei seit: 11.04.2011
Mitteilungen: 2286
Wohnort: Franken
  Beitrag No.7, eingetragen 2022-10-30

Der Mittelwert des Vektors \(x\) ist \(\mu = \frac1n \mathbf{1}^T x\) mit dem Vektor \(\mathbf{1}\) dessen Komponenten alle 1 sind. Der mittelwertfreie Vektor ist dann \(y = x - \mu \mathbf{1} = x - \frac1n \mathbf{1} \mathbf{1}^T x = (I - \frac1n \mathbf{1} \mathbf{1}^T) x = Px\) mit der Einheitsmatrix \(I\) und der Orthogonalprojektion \(P = I - \frac1n \mathbf{1} \mathbf{1}^T\) auf den Orthogonalraum zum Vektor \(\mathbf{1}\). Die Varianz von \(x\) ist dann \(\sigma^2 = \frac1n \|y\|^2\) oder die empirische Varianz ist \(s^2 = \frac1{n-1} \|y\|^2\) und sieht man von dem konstanten Vorfaktor ab, gilt es nun also \(\|y\|^2 = \|Px\|^2 = x^T P^T P x = x^T P x\) zu optimieren, wobei für Orthogonalprojektionen im allgemeinen \(P^T = P\) und \(P^2 = P\) gelten. \(x\) hat hier die Form \(x = M z\) wobei \(M\) die 20000 x 50 Matrix mit den Daten ist und \(z \in \mathbb R^{50}\) ein Vektor mit Nullern und Einern, der die entsprechenden Spalten aus M für die Summe auswählt. Es gilt dann \(z^T A z\) mit der 50 x 50 Matrix \(A = M^T P M\) zu optimieren, was schon einmal ein deutlich reduziertes Problem ist. \(A\) kann effizient als \(A = M^T M - m m^T\) ausgerechnet werden, mit \(m = \frac1{20000}M^T \mathbf{1}\) und dem Vektor \(\mathbf{1}\) bestehend aus 20000 Einern. Von \(A\) kann die Cholesky-Zerlegung \(A = L^T L\) angelegt werden, so dass es jetzt \(\|y\|^2 = z^T L^T L z = \|Lz\|^2\) zu optimieren gilt. D. h. aus \(L\) sind nun Spalten so auszuwählen, dass die euklidische Länge deren Summe minimal wird. Weiter ist mir nicht klar geworden, was es mit den fünf Päckchen genau auf sich hat und unter welchen Bedingungen die genau gebildet werden, so dass ich hier nicht weitermachen kann. Aber so scheint mir das schon mal ein numerisch deutlich reduziertes Problem geworden zu sein, das leicht brute-forcebar sein sollte und alle weiteren Details können in den Algorithmus dazu gepackt werden. Die Standardabweichung der Lösung ist dann \(\sigma = \frac1{\sqrt n}\|Lz\|\) oder die empirische Standardabweichung ist \(s = \frac1{\sqrt{n-1}}\|Lz\|\).


   Profil
Typhon1982
Junior Letzter Besuch: im letzten Quartal
Dabei seit: 29.10.2022
Mitteilungen: 5
  Beitrag No.8, vom Themenstarter, eingetragen 2022-10-31

Hi Bozzo, das klingt schlau und richtig und nach dem Weg, den ich suchte. Allerdings ist auch so schwer, dass ich ihn erst mal verstehen muss. Danke euch. Gruß Oliver


   Profil
Bozzo
Senior Letzter Besuch: im letzten Monat
Dabei seit: 11.04.2011
Mitteilungen: 2286
Wohnort: Franken
  Beitrag No.9, eingetragen 2022-10-31

Nochmal in geringfügig veränderter Form verkürzt als Rezept: 1) Nimm jeden der 20000-zeiligen Vektoren \(x\) und berechne dessen Mittelwert \(\mu\) und ziehe diesen von jeder Zeile aus \(x\) ab um den mittelwertfreien Vektor \(y\) zu bekommen. 2) Packe alle 50 mittelwertfreien Vektoren \(y\) in eine 20000 x 50 Matrix \(M_0\) (die 0 im Index steht für "mittelwertfrei") und berechne damit \(A = M_0^T M_0\). \(A\) ist proportional zur Kovarianzmatrix der 50 Vektoren und enthält bereits alle für die Aufgabe notwendigen Daten in reduzierter Form. Gesucht sind nun 0-1 Vektoren \(z\), so dass \(z^T A z\) minimal wird. Ein Möglichkeit ist es, so weiter vorzugehen: 3) Bestimme die Cholesky-Zerlegung \(A = L^T L\) und suche davon Spalten heraus, die sich zu Vektoren mit möglichst geringer Norm addieren: \(\|Lz\| \to \min\) mit 0-1 Vektoren \(z\).


   Profil
Typhon1982 hat die Antworten auf ihre/seine Frage gesehen.

Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2023 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]