如何使用 Welford 的在线算法计算更新和删除的值

Question

用例：流式传输大量事件源数据，这些数据可能具有插入、更新和删除操作，并且有保证的顺序。

假设 Welford 算法在事件流中以这种形式插入：

private double _count = 0;
private double _mean = 0;
private double _s = 0;

public void Insert(double value)
{
    var prev_mean = _mean;
    _count = _count + 1;
    if (_count == 1)
    {
        _mean = value;
        _s = 0;
    }
    else
    {
        _mean = _mean + (value - _mean) / _count;
        _s = _s + (value - _mean) * (value - prev_mean);
    }
}

public double Var  => ((_count > 1) ? _s / (_count - 1) : 0.0);

public double StDev => Math.Sqrt(Var);

是否可以根据已知的预先存在的值更改在线统计信息。或者是否有比 Welford 算法更合适的方法来满足需求？

public void Update(double previousValue, double value)
{
   //I got this value correct
   var prev_mean = (_count * _mean - value) / (_count - 1);

   //I did the inversion, but this doesn't give the right values
   var prev_s = -previousValue^2 + previousValue* prev_mean + _mean * previousValue - _mean * prev_mean + _s
}

public void Delete(double previousValue)
{
    _count = _count - 1;
}

编辑

具体问题是：

在更新的情况下如何计算 _mean 和 _s 的正确值？

在删除的情况下如何计算 _mean 和 _s 的正确值？

Answer 1

部分答案（如果我解决完会更新）：

我原来在Update上倒错了。

编辑

一旦我解决了更新，删除就变得微不足道了

private void Update(double previousValue, double value)
{
    if (_count == 1)
    {
        _mean = value;
        _s = 0;
    }
    else
    {
        var prev_mean = (_count * _mean - previousValue) / (_count - 1);
        var prev_s = -(_mean * prev_mean) + (_mean * previousValue) + (prev_mean * previousValue) - Math.Pow(previousValue, 2) + _s;

        //Revert Mean and S
        _mean = prev_mean;
        _s = prev_s;

        //Do same operation as Insert
        _mean = _mean + (value - _mean) / _count;
        _s = prev_s + (value - _mean) * (value - prev_mean);
    }
}

public void Delete(double previousValue)
{
    _count = _count - 1;

    if (_count == 0)
    {
        _mean = 0;
        _s = 0;
        return;
    }
    if (_count == 1)
    {
        _mean = (_count * _mean - previousValue) / (_count - 1);
        _s = 0;
        return;
    }
    else
    {
        var prev_mean = (_count * _mean - previousValue) / (_count - 1);
        var prev_s = -(_mean * prev_mean) + (_mean * previousValue) + (prev_mean * previousValue) - Math.Pow(previousValue, 2) + _s;

        //Revert Mean and S
        _mean = prev_mean;
        _s = prev_s;
    }
}

编辑好的，找到了原始算法的更好实现，以此为基础，然后在 Wolfram Mathematica 的帮助下，我能够解决我需要的反演问题。我在本地做了一个测试运行一百万个随机活动（按随机顺序插入、更新、删除）

我用这个作为逻辑 Assert.IsTrue(Math.Abs(x - y) < .0000001);

其中 x 是 c# 中的本机 2 遍算法，y 是此实现的值。看起来本机实现舍入了一些这没有的东西。

在此插入基于工作的方法 https://www.johndcook.com/blog/skewness_kurtosis/

删除方法是我自己的工作。

public class StatisticsTracker
    {
        private long n = 0;
        private double _sum, _s, M1, M2, M3, M4 = 0.0;

        public long Count => n;

        public double Avg => (n > 2) ? M1 : 0.0;

        public double Sum => _sum;

        public double Var => M2 / (n - 1.0);

        public double StDev => Math.Sqrt(Var);

        //public double Skewness => Math.Sqrt(n) * M3 / Math.Pow(M2, 1.5);

        //public double Kurtosis => (double)n * M4 / (M2 * M2) - 3.0;



        public void Insert(double x)
        {
            double delta, delta_n, delta_n2, term1;
            _sum += x;

            long n1 = n;
            n++;
            delta = x - M1;
            delta_n = delta / n;            
            term1 = delta * delta_n * n1;
            M1 = M1 + delta_n;
            M2 += term1;

            //Required for skewness and Kurtosis
            //Will solve later
            //delta_n2 = delta_n * delta_n;
            //M3 += term1 * delta_n * (n - 2) - 3 * delta_n * M2;
            //M4 += term1 * delta_n2 * (n * n - 3 * n + 3) + 6 * delta_n2 * M2 - 4 * delta_n * M3;            
        }

        public void Update(double previousvalue, double value)
        {
            Delete(previousvalue);
            Insert(value);
        }

        public void Delete(double x)
        {
            var o = ((M1 * n) - x) / (n - 1.0);
            var v = M2;
            var y2 = (-(n - 1.0) * Math.Pow(o, 2.0) + (2.0 * (n - 1) * o * x) + (n * (v - Math.Pow(x, 2.0))) + Math.Pow(x, 2.0)) / n;

            M1 = o;
            M2 = y2;

            n = n - 1;
            _sum -= x;
        }
    }

如何使用 Welford 的在线算法计算更新和删除的值

How to calculate updated and deleted values with Welford's online algorithm

math

statistics

event-sourcing