La meilleure façon de trouver un taux pour une fonction de coût

Question

J'ai 2 tableaux: le premier tableau contient des zones d'appartements et le second ses prix. Les valeurs des tableaux forment un graphique et seront utilisées pour calculer les résultats d'une fonction de coût. La tâche principale est de trouver le meilleur paramètre de la fonction de coût pour minimiser son résultat. Voici comment la fonction de coût ressemble:

Il a été suggéré de créer une boucle de 1 à 10 000 et trouver le meilleur paramètre qui a moins de résultat. La complexité de cet algorithme est de 10 000 * la taille des tableaux.

J'ai proposé une idée pour calculer les différences entre les éléments correspondants des tableaux et mettre les résultats dans un tableau. Ensuite, trouvez une moyenne de tous les éléments de ce tableau. La valeur moyenne obtenue est le paramètre qui devrait fournir un meilleur résultat pour notre fonction de coût. L'algorithme est beaucoup plus efficace que le précédent et peut fournir des résultats plus précis.

Je me demande si mon algorithme est applicable ou pas?

Answer 1

La fonction de coût que vous proposez est l'erreur quadratique moyenne de l'ajustement d'une fonction linéaire à une collection de points de données. C'est un problème bien étudié, et en fait, il existe une solution fermée qui vous dira la valeur mathématiquement optimale d'un que vous devriez choisir. En ce sens, je recommande de ne pas utiliser soit des solutions qui sont proposées ici et de résoudre simplement les choses directement. La fonction de coût que vous avez est une fonction purement de la variable a, donc prendre la dérivée par rapport à a, mettre cette dérivée à zéro, et résoudre devrait vous donner le choix optimal de a.

Coût (a) = (1/2m) Σ _{i = 0} (ax _i - y _i)

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

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

La définition de cette expression à 0 et la simplification nous dit que

0 = (1/2 m) Σ _{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

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

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

Vous devriez pouvoir calculer ce assez facilement dans le temps O (n) en faisant un passez en un seul passage sur le tableau et calculez le numérateur et le dénominateur.