Empirische Analyse
Inhaltsverzeichnis |
Weiß man zu wenig über den Entwurf eines (z.B. als ausführbares Programm) vorliegenden Algorithmus', so ist es oft nicht möglich, dessen Aufwand mit analytischen Methoden zu bestimmen. Dann hilft eine empirische Analyse. Dabei misst man, wie lange der Algorithmus zur Berechnung der gesuchten Resultate benötigt, und versucht einen funktionalen Zusammenhang T: n\mapsto T(n) herauszufinden.
Die empirische Analyse macht es notwendig, k Messungen mit unterschiedlichen Eingaben gleicher Größe n durchzuführen. Man betrachtet verschiedene Probleminstanzen, z.B. k=10, für jeden betrachteten Wert ein und derselben Problemgröße, z.B. n=100,1000,10000,100000,1000000.
Zur Auswertung kann man für jedes n das arithmetische Mittel der k vorlegenden Messwerte, nehmen. Dies liefert den Aufwand im mittleren Fall (average case). Nimmt man den jeweils größten/kleinsten Wert, ergibt sich der Aufwand im schlechtesten bzw. besten Fall (worst/best case).
Zur grafischen Darstellung kann man die gemittelten Werte in einem Streudiagramm (scatter plot) eintragen.
Regression
Ein solches Streudiagramm lässt den funktionalen Zusammenhang oft schon erahnen. Besser ist es, wenn wir objektiv(!), d.h. mit mathematischen Mitteln, eine Funktion bestimmen, die den Zusammenhang zwischen n und T(n) ausdrückt. Dies entspricht dem Hineinlegen einer Kurve, die dem Punkteverlauf möglichst gut folgt und Ausreißer geeignet verarbeitet.
Diese Technik wird Regression genannt. Am besten ist es, wenn man eine Gerade verwenden kann. Man spricht von linearer Regression. Dies gilt zunächst natürlich nur für lineare Zusammenhänge zwischen n und T(n). Vermutet man eine Polynom- oder Exponentialfunktion, so kann man die Messwerte in vielen Fällen so aufbereiten (umrechnen), dass die daraus gewonnenen Daten durch eine lineare Funktion approximiert werden können. Eine entsprechende Rückrechnung liefert dann die konkreten Koeffizienten der gesuchten Funktion.
Lineare Regression
Wie oben angekündigt, suchen wir eine lineare Funktion, die als Gerade die Punkte möglichst gut annähert.
Eine lineare Funktion f ist wie folgt definiert:
f(x) = a \cdot x + b \text{ mit $a, b \in \mathbb{R}$}Nun geht es darum, a und b so zu wählen, dass der Verlauf der Gerade möglichst gut mit dem Verlauf der Punkte übereinstimmt. Hierfür wird die Methode der kleinsten Quadrate (nach Gauss) angewandt: Die Summe der Abstandsquadrate aller Punkte von der Geraden soll möglichst klein sein (Optimierungsziel). Dass dabei die einzelnen Abstandswerte quadriert werden müssen, liegt daran, dass zur Bestimmung des Minimums die erste Ableitung der Betragsfunktion gebildet wird. Diese ist an der Stelle x=0 nicht differenzierbar, was man in dem folgenden Graph an der "Spitze" erkennt. Wie soll da eine Tangente angelegt werden?
Nimmt man die Abstandsquadrate, so kann das Minimum der resultierenden Funktion berechnet werden.
- x_i : x-Wert des i-ten Punktes
- y_i : y-Wert des i-ten Punktes
Das Minimum lässt sich analytisch bestimmen, indem man die partiellen Ableitungen von e(a, b) bildet und diese gleich 0 setzt.
\begin{align*} e(a, b) & = \sum_{i=1}^n \left((a x_i + b)^2 - 2 \cdot (a x_i + b) \cdot y_i + y_i^2\right) \\ & = \sum_{i=1}^n \left(a^2 x_i^2 + 2 a x_i b + b^2 - 2 a x_i y_i - 2 b y_i + y_i^2\right) \\ \frac{\partial e(a, b)}{\partial a} & = \sum_{i=1}^n \left(2 x_i^2 a + 2 x_i b - 2 x_i y_i\right) \\ & = 2 \sum_{i=1}^n \left(x_i^2 a + x_i b - x_i y_i\right) \\ & = 2 \left( \sum_{i=1}^n x_i^2 a + \sum_{i=1}^n x_i b - \sum_{i=1}^n x_i y_i \right) \\ & = 2 a \sum_{i=1}^n \left(x_i^2 + b \sum_{i=1}^n x_i - \sum_{i=1}^n x_i y_i \right) \\ \frac{\partial e(a, b)}{\partial b} & = \sum_{i=1}^n \left(2 a x_i + 2 b - 2 y_i\right) \\ & = 2 \sum_{i=1}^n \left(a x_i + b - y_i\right) \\ & = 2 \left( \sum_{i=1}^n a x_i + \sum_{i=1}^n b - \sum_{i=1}^n y_i \right) \\ & = 2 \left( a \sum_{i=1}^n x_i + n b - \sum_{i=1}^n y_i \right) \\ \end{align*}Nun müssen die partiellen Ableitungen gleich 0 gesetzt werden.
Im folgenden werden \overline{x} als das arithmetische Mittel von x : \overline{x} = \frac{\sum_{i=1}^n x_i}{n} und \overline{y} als das arithmetische Mittel von y : \overline{y} = \frac{\sum_{i=1}^n y_i}{n} bezeichnet.
\left\{ \begin{array}{c} \begin{align*} 2 \left( a \sum_{i=1}^n x_i^2 + b \sum_{i=1}^n x_i - \sum_{i=1}^n x_i y_i \right) & = 0 \\ 2 \left( a \sum_{i=1}^n x_i + n b - \sum_{i=1}^n y_i \right) & = 0 \end{align*} \end{array} \right. \left\{ \begin{array}{c} \begin{align*} a \sum_{i=1}^n x_i^2 + b \sum_{i=1}^n x_i - \sum_{i=1}^n x_i y_i & = 0 \\ a \sum_{i=1}^n x_i + n b - \sum_{i=1}^n y_i & = 0 \end{align*} \end{array} \right. \left\{ \begin{array}{c} \begin{align*} a \sum_{i=1}^n x_i^2 + b \sum_{i=1}^n x_i & = \sum_{i=1}^n x_i y_i \\ a \sum_{i=1}^n x_i + nb & = \sum_{i=1}^n y_i \end{align*} \end{array} \right. a \sum_{i=1}^n x_i + nb = \sum_{i=1}^n y_i \iff b = \frac{\sum_{i=1}^n y_i - a \sum_{i=1}^n x_i}{n} \iff b = \overline{y} - a \overline{x} \implies a \sum_{i=1}^n x_i^2 + \frac{\sum_{i=1}^n y_i - a \sum_{i=1}^n x_i}{n} \sum_{i=1}^n x_i = \sum_{i=1}^n x_i y_i \iff a \sum_{i=1}^n x_i^2 + \frac{\sum_{i=1}^n x_i \sum_{i=1}^n y_i}{n} - a \frac{\left( \sum_{i=1}^n x_i \right)^2}{n} = \sum_{i=1}^n x_i y_i \iff a \sum_{i=1}^n x_i^2 - a \frac{\left( \sum_{i=1}^n x_i \right)^2}{n} = \sum_{i=1}^n x_i y_i - \frac{\sum_{i=1}^n x_i \sum_{i=1}^n y_i}{n} \iff a \left( \sum_{i=1}^n x_i^2 - \frac{\left( \sum_{i=1}^n x_i \right)^2}{n} \right) = \sum_{i=1}^n x_i y_i - \frac{\sum_{i=1}^n x_i \sum_{i=1}^n y_i}{n} \iff a = \frac{\sum_{i=1}^n x_i y_i - \frac{\sum_{i=1}^n x_i \sum_{i=1}^n y_i}{n}}{\sum_{i=1}^n x_i^2 - \frac{\left( \sum_{i=1}^n x_i \right)^2}{n}} \iff a = \frac{\sum_{i=1}^n x_i y_i - \frac{n \cdot \overline{x} \cdot n \cdot \overline{y}}{n}}{\sum_{i=1}^n x_i^2 - \frac{n \cdot \overline{x} \cdot n \cdot \overline{x}}{n}} \iff a = \frac{\sum_{i=1}^n x_i y_i - n \cdot \overline{x} \cdot \overline{y}}{\sum_{i=1}^n x_i^2 - n \cdot \overline{x}^2}
Nun hat man mit
a = \frac{\sum_{i=1}^n x_i y_i - n \cdot \overline{x} \cdot \overline{y}}{\sum_{i=1}^n x_i^2 - n \cdot \overline{x}^2}und
b = \overline{y} - a \overline{x}Formeln, mit denen man die beiden Koeffizienten der linearen Funktion bestimmen kann.
Exponentielle Regression
Bei der exponentiellen Regression möchte man eine Exponentialfunktion finden, die sich möglichst gut an die gegebenen Punkte anschmiegt. Dieses Problem lässt sich auf lineare Regression zurückführen, indem man die y-Achse logarithmisch anlegt. Wir bezeichnen diese als y'-Achse. Eine Exponentialfunktion wird hier durch eine Gerade dargestellt. Deshalb lässt sich das bereits bekannte Verfahren der linearen Regression anwenden.
Wählt man als Basis 2, so möchte man eine Funktion der Form f(x) = a \cdot 2^{bx} finden. Logarithmiert man den Funktionwert, so erhält man:
\begin{align*} \log_2 \left(f(x) \right) & = \log_2 \left(a \cdot 2^{bx} \right) \\ & = \log_2 a + \log_2 2^{bx} \\ & = \log_2 a + bx \end{align*}Es handelt sich um eine lineare Funktion, deren Anstieg b und Schnittpunkt mit der y'-Achse \log_2 a lassen sich wie oben beschrieben bestimmen.
Polynomielle Regression
Bei der polynomiellen Regression möchte man eine Funktion der Form f(x) = a \cdot x^k finden, die die Punkte möglichst gut annähert. Deshalb müssen Konstanten a und k gefunden werden, für die der Fehler minimal ist.
Hierfür wird wieder das Logarithmieren der Achsen benutzt. Jedoch wird hier nicht nur die y-Achse, sondern auch die x-Achse logarithmiert. Die Basis des Logarithmus ist frei wählbar, es muss sich jedoch bei der x'- und y'-Achse um die gleiche Basis handeln.
Beispiele:
Durch Logarithmieren der y-Achse erhält man y':
\begin{align*} f(x) &= a \cdot x^k \\ \implies \log(f(x)) &= \log(a \cdot x^k) \\ \implies \log(f(x)) &= k \log(x) + \log(a) \end{align*}Setzt man nun die x-Achse (mit x' gekennzeichnet) x' = \log(x), so erhält man eine Gerade. \log(a) gibt den y-Achsenschnittpunkt und k den Anstieg der Geraden an.
\begin{align*} f(x) &= a \cdot x^k \\ \implies \log(f(x)) &= \log(a \cdot x^k) \\ \implies \log(f(x)) &= k \log(x) + \log(a)\\ \implies y' &= k x' + \log(a) \end{align*}Nun kann man wie bei der linearen Regression vorgehen und k und \log(a) bestimmen.
Korrelationskoeffizient
Der Pearson-Korrelationskoeffizient r ist ein Maß für die Beziehung zwischen zwei Variablen. Im Zusammenhang der linearen Regression kann er genutzt werden, um die Qualität der Regressiongerade zu bestimmen.
r = \frac{cov(X, Y)}{\sigma_X \sigma_Y}cov(X, Y) ist die Kovarianz von X und Y und wird folgendermaßen bestimmt:
cov(X, Y) = \frac{1}{n} \sum_{i=1}^n (x_i - \overline{x}) (y_i - \overline{y})Eingesetzt ergibt sich für r folgende Formel:
r = \frac{\frac{1}{n} \sum_{i=1}^n (x_i - \overline{x}) (y_i - \overline{y})}{\sqrt{\frac{1}{n} \sum_{i=1}^n (x_i - \overline{x})^2} \sqrt{\frac{1}{n} \sum_{i=1}^n (y_i - \overline{y})^2}} r = \frac{\sum_{i=1}^n (x_i - \overline{x}) (y_i - \overline{y})}{\sqrt{\sum_{i=1}^n (x_i - \overline{x})^2} \sqrt{\sum_{i=1}^n (y_i - \overline{y})^2}}Laut der Cauchy-Schwartz-Ungleichung gilt:
\left| \sum_{i=1}^n (x_i - \overline{x}) (y_i - \overline{y}) \right|^2 \leqslant \sum_{i=1}^n (x_i - \overline{x})^2 \sum_{i=1}^n (y_i - \overline{y})^2 \implies \sum_{i=1}^n (x_i - \overline{x}) (y_i - \overline{y}) \leqslant \sqrt{\sum_{i=1}^n (x_i - \overline{x})^2} \sqrt{\sum_{i=1}^n (y_i - \overline{y})^2} \implies \left| r \right| \leqslant 1 \implies -1 \leqslant r \leqslant 1