Der beste Weg, um eine Rate für eine Kostenfunktion zu finden

Question

Ich habe 2 Arrays: das erste Array enthält Bereiche von Wohnungen und der zweite seine Preise. Die Werte von Arrays bilden ein Diagramm und werden zur Berechnung der Ergebnisse einer Kostenfunktion verwendet. Die Hauptaufgabe besteht darin, den besten Parameter der Kostenfunktion zu finden, um das Ergebnis zu minimieren. Dies ist, wie die Kostenfunktion wie folgt aussieht:

Es wurde vorgeschlagen, eine Schleife von 1 bis 10 000 und finden Sie die besten Parameter zu schaffen, die weniger Ergebnis hat. Die Komplexität dieses Algorithmus beträgt 10 000 * Größe der Arrays.

Ich schlug eine Idee vor, Unterschiede zwischen entsprechenden Elementen der Arrays zu berechnen und Ergebnisse in ein Array zu setzen. Dann finden Sie einen Durchschnitt aller Elemente dieses Arrays. Der erhaltene Durchschnittswert ist der Parameter, der ein besseres Ergebnis für unsere Kostenfunktion liefern sollte. Der Algorithmus ist viel effizienter als der vorherige und kann genauere Ergebnisse liefern.

Ich frage mich, ob mein Algorithmus anwendbar ist oder nicht?

Answer 1

Die Kostenfunktion, die Sie vorschlagen, ist der mittlere quadratische Fehler beim Anpassen einer linearen Funktion an eine Sammlung von Datenpunkten. Dies ist ein gut untersuchtes Problem, und tatsächlich gibt es eine geschlossene Lösung, die Ihnen den mathematisch optimalen Wert von a sagt, den Sie auswählen sollten. In diesem Sinne würde ich empfehlen, nicht entweder der hier vorgeschlagenen Lösungen zu verwenden und stattdessen nur Dinge direkt zu lösen.

Die Kostenfunktion, die Sie haben, ist eine Funktion rein von der Variable a, also die Ableitung in Bezug auf a nehmend, setzendiese Ableitung auf Null, und das Lösen sollte Ihnen die optimale Wahl von a geben.

Cost (a) = (1/2 M) Σ _{i = 0} (ax _i - y _i)

Cost '(a) = (1/2m) Σ _{i = 0} 2 (ax i - y i ) x _i

Cost '(a) = (1/2 M) Σ _{i = 0} (2ax _i - 2x _i y _i)

Festlegen dieser Ausdruck auf 0 gesetzt und die Vereinfachung sagt uns, dass

0 = (1/2m) Σ _{i = 0} (2ax _i - 2x _i y _i)

0 = Σ _{i = 0} (2ax _i - 2x _i y _i)

0 = 2a Σ _{i = 0} x _i -2 Σ _{i = 0} x _i y _i

a Σ _{i = 0} x _i = Σ _{i = 0} x _i y _i

a = (Σ _{i = 0} x _i y _i)/(Σ _{i = 0} x _i)

Sie sollten in der Lage sein, diese ziemlich leicht in O zu berechnen (n) durch eine Herstellung Einfacher Durchlauf über das Array und Berechnung des Zählers und Nenners