Bagaimana cara menghitung rata-rata bergerak tanpa menyimpan hitungan dan total data?

118

Saya mencoba menemukan cara untuk menghitung rata-rata kumulatif bergerak tanpa menyimpan jumlah dan total data yang diterima sejauh ini.

Saya menemukan dua algoritme tetapi keduanya perlu menyimpan hitungan:

  • rata-rata baru = ((hitungan lama * data lama) + data berikutnya) / hitungan berikutnya
  • rata-rata baru = rata-rata lama + (data berikutnya - rata-rata lama) / hitungan berikutnya

Masalah dengan metode ini adalah bahwa hitungan semakin besar dan mengakibatkan hilangnya presisi dalam rata-rata yang dihasilkan.

Cara pertama menggunakan hitungan lama dan hitungan berikutnya yang jelas terpisah 1. Ini membuat saya berpikir bahwa mungkin ada cara untuk menghapus hitungan tetapi sayangnya saya belum menemukannya. Itu membuat saya sedikit lebih jauh, menghasilkan metode kedua tetapi masih ada hitungan.

Apakah itu mungkin, atau apakah saya hanya mencari yang tidak mungkin?

pengguna1705674
sumber
1
NB yang secara numerik, menyimpan jumlah total dan arus saat ini adalah cara yang paling stabil. Jika tidak, untuk hitungan yang lebih tinggi berikutnya / (hitungan berikutnya) akan mulai berkurang. Jadi jika Anda benar-benar khawatir kehilangan presisi, pertahankan jumlah totalnya!
AlexR
1
Lihat Wikipedia en.wikipedia.org/wiki/Moving_average
xmedeko

Jawaban:

91

Anda cukup melakukan:

double approxRollingAverage (double avg, double new_sample) {

    avg -= avg / N;
    avg += new_sample / N;

    return avg;
}

Di mana Njumlah sampel yang ingin Anda ratakan. Perhatikan bahwa perkiraan ini setara dengan rata-rata bergerak eksponensial. Lihat: Hitung rolling / moving average dalam C ++

Muis
sumber
3
Tidakkah Anda harus menambahkan 1 ke N sebelum baris ini? rata-rata + = sampel_baru / N;
Damian
20
Ini tidak sepenuhnya benar. Apa yang dijelaskan oleh @Muis adalah moving averge berbobot eksponensial, yang terkadang sesuai tetapi tidak persis seperti yang diminta OP. Sebagai contoh, pertimbangkan perilaku yang Anda harapkan ketika sebagian besar poin berada dalam kisaran 2 hingga 4 tetapi satu nilai di atas satu juta. Sebuah EWMA (di sini) akan menyimpan jejak jutaan itu untuk beberapa waktu. Sebuah konvolusi terbatas, seperti yang ditunjukkan oleh OP, akan hilang segera setelah N langkah. Itu memang memiliki keuntungan dari penyimpanan konstan.
jma
9
Itu bukan rata-rata bergerak. Yang Anda jelaskan adalah filter satu kutub yang menciptakan respons eksponensial untuk lompatan dalam sinyal. Rata-rata bergerak menciptakan respons linier dengan panjang N.
ruhig brauner
3
Berhati-hatilah karena ini cukup jauh dari definisi umum tentang rata-rata. Jika Anda menetapkan N = 5 dan memasukkan 5 5sampel, rata-rata akan menjadi 0,67.
Dan Dascalescu
2
@DanDascalescu Meskipun Anda benar bahwa ini sebenarnya bukan rata-rata penggiliran, nilai yang Anda nyatakan tidak sesuai dengan urutan besarnya. Dengan avgdiinisialisasi ke 0, Anda berakhir dengan 3.36setelah 5 5detik, dan 4.46setelah 10: cpp.sh/2ryql Untuk rata-rata panjang, ini tentu saja merupakan perkiraan yang berguna.
cincodenada
80
New average = old average * (n-1)/n + new value /n

Ini mengasumsikan hitungan hanya diubah oleh satu nilai. Jika diubah oleh nilai M maka:

new average = old average * (n-len(M))/n + (sum of values in M)/n).

Ini adalah rumus matematika (saya yakin yang paling efisien), percayalah Anda dapat membuat kode lebih lanjut sendiri

Abdullah Al-Ageel
sumber
Berapa jumlah nilai baru? apakah itu berbeda dari "nilai baru" dalam rumus asli Anda?
Mikhail
@Mikhail di contoh kedua, ada mnilai-nilai baru yang dimasukkan ke dalam rata-rata baru. Saya percaya bahwa di sum of new valuesini dimaksudkan untuk menjumlahkan nilai m-nilai baru yang digunakan untuk menghitung rata-rata baru.
Patrick Goley
9
Sedikit lebih efisien untuk yang pertama: new_average = (old_average * (n-1) + new_value) / n- Menghapus salah satu pemisah.
Pixelstix
Bagaimana jika menjalankan rata-rata 3 elemen dengan 6,0,0,9?
Roshan Mehta
1
Ketika saya menerapkan persamaan ini, nilai atau rata-rata berjalan selalu meningkat secara perlahan. Itu tidak pernah turun - hanya naik.
anon58192932
30

Dari blog tentang menjalankan penghitungan varians sampel, di mana mean juga dihitung menggunakan metode Welford :

masukkan deskripsi gambar di sini

Sayang sekali kami tidak dapat mengunggah gambar SVG.

Balik
sumber
3
Ini mirip dengan yang diterapkan Muis, kecuali bahwa pembagian menggunakan faktor persekutuan. Jadi hanya satu divisi.
Balik
Ini sebenarnya lebih dekat dengan @ Abdullah-Al-Ageel (pada dasarnya matematika komutatif) karena Muis tidak memperhitungkan kenaikan N; referensi rumus salin-tempel: [Rata-rata pada n] = [Rata-rata pada n-1] + (x - [Rata-rata pada n-1]) / n
drzaus
2
@Flip & drwaus: Bukankah solusi Muis dan Abdullah Al-Ageel persis sama? Perhitungannya sama, hanya ditulis secara berbeda. Bagi saya, 3 jawaban itu adalah identik, yang ini lebih visual (sayang sekali kita tidak bisa menggunakan MathJax di SO).
pengguna276648
21

Berikut lagi jawabannya korban komentar tentang bagaimana Muis , Abdullah Al-Ageel dan flip jawaban 's adalah semua matematis hal yang sama kecuali ditulis berbeda.

Tentu, kami memiliki analisis José Manuel Ramos yang menjelaskan bagaimana kesalahan pembulatan memengaruhi masing-masing sedikit berbeda, tetapi itu bergantung pada penerapan dan akan berubah berdasarkan bagaimana setiap jawaban diterapkan ke kode.

Namun ada perbedaan yang cukup besar

Ada di Muis 's N, Flip 's k, dan Abdullah Al-Ageel 's n. Abdullah Al-Ageel tidak cukup menjelaskan apa yang nseharusnya, tetapi Ndan kperbedaannya Nadalah " jumlah sampel di mana Anda ingin rata-rata lebih " sedangkan kjumlah nilai sampel. (Meskipun saya ragu apakah memanggil N jumlah sampel itu akurat.)

Dan inilah jawabannya di bawah ini. Ini pada dasarnya adalah rata-rata bergerak tertimbang eksponensial lama yang sama dengan yang lain, jadi jika Anda mencari alternatif, berhentilah di sini.

Rata-rata bergerak tertimbang eksponensial

Mulanya:

average = 0
counter = 0

Untuk setiap nilai:

counter += 1
average = average + (value - average) / min(counter, FACTOR)

Perbedaannya adalah min(counter, FACTOR)bagiannya. Ini sama dengan mengatakanmin(Flip's k, Muis's N) .

FACTORadalah konstanta yang memengaruhi seberapa cepat rata-rata "mengejar" tren terbaru. Semakin kecil angkanya semakin cepat. ( 1Ini bukan lagi rata-rata dan hanya menjadi nilai terbaru.)

Jawaban ini membutuhkan penghitung berjalan counter. Jika bermasalah, min(counter, FACTOR)bisa diganti dengan just FACTOR, mengubahnya menjadi jawaban Muis . Masalah dengan melakukan ini adalah rata-rata bergerak dipengaruhi oleh apa pun averageyang dimulai. Jika itu diinisialisasi ke0 , nol itu bisa memakan waktu lama untuk bekerja di luar rata-rata.

Bagaimana hasilnya nanti

Rata-rata bergerak eksponensial

antak
sumber
3
Dijelaskan dengan baik. Saya hanya melewatkan rata-rata biasa di grafik Anda, karena itulah yang diminta OP.
xmedeko
Mungkin saya melewatkan sesuatu, tetapi apakah Anda, secara kebetulan, bermaksud demikian max(counter, FACTOR). min(counter, FACTOR)akan selalu mengembalikan FACTOR, bukan?
WebWanderer
1
Saya percaya intinya min(counter, FACTOR)adalah memperhitungkan periode pemanasan. Tanpanya, jika FAKTOR Anda (atau N, atau jumlah sampel yang diinginkan) adalah 1000, maka Anda memerlukan setidaknya 1000 sampel sebelum Anda mendapatkan hasil yang akurat, karena semua pembaruan sebelumnya akan menganggap Anda memiliki 1000 sampel, padahal Anda mungkin hanya memiliki 20.
rharter
Alangkah baiknya berhenti menghitung setelah mencapai faktor, mungkin akan lebih cepat seperti itu.
inf3rno
8

Jawaban Flip secara komputasi lebih konsisten daripada jawaban Muis.

Menggunakan format angka ganda, Anda bisa melihat masalah pembulatan dalam pendekatan Muis:

Pendekatan Muis

Saat Anda membagi dan mengurangi, pembulatan muncul di nilai yang disimpan sebelumnya, mengubahnya.

Namun, pendekatan Flip mempertahankan nilai yang disimpan dan mengurangi jumlah divisi, karenanya, mengurangi pembulatan, dan meminimalkan kesalahan yang disebarkan ke nilai yang disimpan. Menambahkan hanya akan memunculkan pembulatan jika ada sesuatu untuk ditambahkan (ketika N besar, tidak ada yang ditambahkan)

Pendekatan Balik

Perubahan tersebut luar biasa ketika Anda membuat rata-rata nilai yang besar cenderung ke nol.

Saya tunjukkan hasilnya menggunakan program spreadsheet:

Pertama, hasil yang diperoleh: Hasil

Kolom A dan B masing-masing adalah nilai n dan X_n.

Kolom C adalah pendekatan Flip, dan D adalah pendekatan Muis, hasilnya disimpan dalam mean. Kolom E sesuai dengan nilai media yang digunakan dalam perhitungan.

Grafik yang menunjukkan rata-rata nilai genap adalah yang berikutnya:

Grafik

Seperti yang Anda lihat, ada perbedaan besar antara kedua pendekatan tersebut.

José Manuel Ramos
sumber
2
Bukan jawaban, tapi info berguna. Akan lebih baik lagi jika Anda menambahkan garis ke-3 ke grafik Anda, untuk rata-rata sebenarnya di atas n nilai lampau, sehingga kita dapat melihat mana dari dua pendekatan yang paling mendekati.
jpaugh
2
@jpaugh: Kolom B bergantian antara -1.00E + 15 dan 1.00E + 15, jadi jika N genap, mean sebenarnya harus 0. Judul grafik adalah "Mean parsial genap". Ini berarti baris ke-3 yang Anda tanyakan hanyalah f (x) = 0. Grafik tersebut menunjukkan bahwa kedua pendekatan tersebut menyebabkan kesalahan yang terus meningkat dan meningkat.
desowin
Benar, grafik menunjukkan dengan tepat kesalahan yang disebarkan menggunakan angka besar yang terlibat dalam penghitungan menggunakan kedua pendekatan.
José Manuel Ramos
Legenda grafik Anda memiliki warna yang salah: Muis berwarna jingga, Flip berwarna biru.
xmedeko
6

Contoh penggunaan javascript, sebagai perbandingan:

https://jsfiddle.net/drzaus/Lxsa4rpz/

function calcNormalAvg(list) {
    // sum(list) / len(list)
    return list.reduce(function(a, b) { return a + b; }) / list.length;
}
function calcRunningAvg(previousAverage, currentNumber, index) {
    // [ avg' * (n-1) + x ] / n
    return ( previousAverage * (index - 1) + currentNumber ) / index;
}

drzaus
sumber
1

Di Java8:

LongSummaryStatistics movingAverage = new LongSummaryStatistics();
movingAverage.accept(new data);
...
average = movingAverage.getAverage();

kamu juga punya IntSummaryStatistics, DoubleSummaryStatistics...

jmhostalet.dll
sumber
2
OP meminta algoritma, bukan penunjuk bagaimana menghitung ini di Java.
olq_plo
0

Solusi Python yang rapi berdasarkan jawaban di atas:

class RunningAverage():
    def __init__(self):
        self.average = 0
        self.n = 0
        
    def __call__(self, new_value):
        self.n += 1
        self.average = (self.average * (self.n-1) + new_value) / self.n 
        
    def __float__(self):
        return self.average
    
    def __repr__(self):
        return "average: " + str(self.average)

pemakaian:

x = RunningAverage()
x(0)
x(2)
x(4)
print(x)
Dima Lituiev
sumber