Un algorithme en ligne est un algorithme qui peut être calculé même lorsque les données arrivent séquentiellement. Ceci est appelé contrairement à l'algorithme par lots (hors ligne) qui calcule après avoir vu toutes les données.
Les algorithmes en ligne sont souvent utilisés pour traiter de grandes quantités de données où il est difficile de conserver toutes les données en mémoire. Vous pouvez souvent le voir dans le contexte de l'apprentissage automatique. Dans le contexte de l'apprentissage automatique, il y a beaucoup de choses qui sont théoriquement difficiles, mais comme la moyenne, la dispersion, l'échantillonnage, etc. sont utilisés relativement souvent lors de la création d'un système simple, le traitement peut être écrit même si les données sont séquentielles. Vous pourriez être heureux si vous devenez.
Cette fois, je n'écrirai que la méthode de calcul séquentiel de la valeur moyenne.
«Moyenne» est la valeur moyenne que vous voulez trouver, «total» est le nombre de données traitées jusqu'à présent. Le but est de pouvoir décrire sous la forme suivante.
ruby/python
average += x
total += y
Bien sûr, pour être valide en tant qu'algorithme en ligne, la forme «moyenne * = z» peut être définie comme cible, mais dans le cas de la valeur moyenne (additive), la solution peut être obtenue si la forme ci-dessus est utilisée.
Premièrement, «y = 1» car «total» représente le nombre de fois.
Ensuite, puisque «la moyenne» n'est pas évidente, elle est calculée en développant la formule comme suit. Ici, la valeur est une valeur de données pour laquelle une nouvelle moyenne doit être obtenue.
math
average[new] = (average[old] * total[old] + value) / (total[old] + 1)
average[new] = average[old] + x
Que
average[old] + x = (average[old] * total[old] + value) / (total[old] + 1)
Si vous résolvez ce problème
average[old] + average[old] * total[old] + x * (total[old]+1) = average[old] * total[old] + value
average[old] + x * (total[old]+1) = value
Par conséquent
x = (value - average[old]) / (total[old] + 1)
Avoir
À la suite de l'écriture dans le programme
ruby/python
average += (value - average) / (total + 1)
total += 1
Sera. ici,
math
total[new] = total[old] + 1
Compte tenu de cela, par programme
ruby/python
total += 1
average += (value - average) / total
Peut-être plus frais.
Il y a 3 données et la valeur est
20 -> 30 -> 40
Supposons que ce soit le cas.
À ce moment, la moyenne finale est
30
Et la moyenne à ce moment-là est
20 -> 25 -> 30
Cela suffit si cela change.
Je vais vraiment l'essayer.
math
x = (20 - ?) / 1 = 20 - ?
average = ? + 20 - ? = 20
math
x = (30 - 20) / 2 = 5
average = 20 + 5 = 25
math
x = (40 - 25) / 3 = 5
average = 25 + 5 = 30
Et vous pouvez voir que cela fonctionne.
À propos, le premier ? Est la valeur initiale moyenne, et n'importe quelle valeur peut être saisie.
En fait, c'est "0", ou si la valeur moyenne peut être estimée à l'avance, il est préférable de saisir la valeur estimée.
math
V(X) = E(X*X) - E(X)*E(X)
utilisation. Ici, «V» représente la dispersion et «E» représente la moyenne. En d'autres termes, il peut être calculé en tenant la valeur moyenne des valeurs au carré des données.
Par exemple, lorsque vous souhaitez échantillonner une seule valeur à partir d'une grande quantité de données Laissez ces données être «échantillonnées», et laissez le nombre de données vues jusqu'à présent être «total».
En ce moment,
Ensuite, le résultat échantillonné peut être obtenu avec une probabilité égale.
Bien sûr, si vous appliquez cela, vous ne pouvez en échantillonner que trois.