Alle Herausforderungen
Mittel 0 gelöst 0% Erfolgsquote

Einfache lineare Regression (kleinste Quadrate)

Lege mit den Formeln der kleinsten Quadrate die bestpassende Gerade durch Datenpunkte.

Das lernst du

  • Eine Gerade mit geschlossenen Formeln anpassen
  • Steigung und Achsenabschnitt berechnen
  • Verstehen, was beste Anpassung bedeutet

Problem

Die lineare Regression findet die Gerade y = slope × x + intercept, die am besten zu den Daten passt, also die Summe der quadrierten Fehler minimiert. Für eine Eingangsvariable gibt es eine exakte Formel:

  • slope = Σ(x - x̄)(y - ȳ) / Σ(x - x̄)²
  • intercept = ȳ - slope × x̄

wobei x̄ und ȳ die Mittelwerte von xs und ys sind. Sind alle xs gleich, gib slope 0 und intercept ȳ zurück.

Implementiere linear_regression(xs, ys).

Eingabe

xs, ys: Die x- und y-Werte der Datenpunkte (gleiche Länge).

Ausgabe

Gib [slope, intercept] zurück.

Einschränkungen

1 ≤ Anzahl der Punkte ≤ 10.000

-10.000 ≤ jeder Wert ≤ 10.000

Beispiele

Beispiel 1
Eingabe:
xs = [1.0, 2.0, 3.0, 4.0]
ys = [3.0, 5.0, 7.0, 9.0]

Erwartete Ausgabe:
expected = [2.0, 1.0]
Eingabe:
std::vector<double> xs = {1.0, 2.0, 3.0, 4.0};
std::vector<double> ys = {3.0, 5.0, 7.0, 9.0};

Erwartete Ausgabe:
std::vector<double> expected = {2.0, 1.0};
Eingabe:
double[] xs = new double[] {1.0, 2.0, 3.0, 4.0};
double[] ys = new double[] {3.0, 5.0, 7.0, 9.0};

Erwartete Ausgabe:
double[] expected = new double[] {2.0, 1.0};

Erläuterung

Die Punkte liegen genau auf y = 2x + 1. x̄ = 2.5, ȳ = 6, Σ(x - x̄)(y - ȳ) = 10 und Σ(x - x̄)² = 5, also slope = 2 und intercept = 6 - 2 × 2.5 = 1.

Beispiel 2
Eingabe:
xs = [0.0, 1.0, 2.0]
ys = [1.0, 3.0, 2.0]

Erwartete Ausgabe:
expected = [0.5, 1.5]
Eingabe:
std::vector<double> xs = {0.0, 1.0, 2.0};
std::vector<double> ys = {1.0, 3.0, 2.0};

Erwartete Ausgabe:
std::vector<double> expected = {0.5, 1.5};
Eingabe:
double[] xs = new double[] {0.0, 1.0, 2.0};
double[] ys = new double[] {1.0, 3.0, 2.0};

Erwartete Ausgabe:
double[] expected = new double[] {0.5, 1.5};

Erläuterung

x̄ = 1 und ȳ = 2. Σ(x - x̄)(y - ȳ) = (-1)(-1) + 0 + (1)(0) = 1 und Σ(x - x̄)² = 2, also slope = 0.5 und intercept = 2 - 0.5 × 1 = 1.5.

So gehst du vor

Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.

Hinweis 1

Die beste Gerade ergibt sich daraus, wie x und y gemeinsam um ihre Mittelwerte schwanken.

Hinweis 2

Berechne zuerst die Mittelwerte und sammle dann Zähler und Nenner für die Steigungsformel.

Hinweis 3

Wenn alle x-Werte gleich sind, ist die Steigung undefiniert, also gib eine horizontale Linie durch den durchschnittlichen y-Wert zurück.

Erwartete Komplexität

Zeit O(n), zusätzlicher Speicher O(1)

Referenzen

Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.

Die beste bestandene Lösung jedes Coders. Schnellere, sparsamere und besser bewertete Lösungen stehen weiter oben.

Noch keine bestandene Lösung. Löse sie und hol dir Platz eins.

Von anderen lernen

Community-Lösungen

Noch keine veröffentlichten Lösungen. Löse die Aufgabe und teile als Erster eine Lösung.