转载一篇方差的增量算法

lg676041036

最近在做一个数据采集实时标准差的计算，用简化公式计算总是出现错误，终于找到这个算法来分享一下。
转载于：https://www.cnblogs.com/yoyaprogrammer/p/delta_variance.html

一个小小的方差增量算法，使得消除持续增长的上百GB的明细数据成为可能，空间效率和时间效率都可得到无以伦比的提升。

下面一码给你重现整个过程，小伙伴们一起激动激动。

背景

搞推荐就要玩好私人定制，要玩好私人定制，就得分析用户的购买和浏览行为。我们系统里某个地方就需要针对每个用户，计算他（她）曾经购买过的所有产品的价格的方差。

来，和你一起回顾下方差的定义。

方差的统计学定义

方差是反应数值型数据离散程度的最重要的指标。

假设X样本的有N个样本值：

x1,x2,...,xNx1,x2,...,xN

X样本的平均值计算很简单：

Xˉˉˉˉ=1N∑i=1NxiXˉ=1N∑i=1Nxi

那么计算X样本的方差的公式如下：

σ2X=1N∑i=1N(xi−Xˉˉˉˉ)2σX2=1N∑i=1N(xi−Xˉ)2

从表面上看，为了计算一组样本值的方差，需要知道所有样本值明细。

持续增长中的上百GB的明细数据

为了保证及时算出产品价格方差这一重要指标，专门存储了每个用户购买的所有产品的价格，还没到一年，数据量就奔着百GB俱乐部的规模去了。问题来了，如果需要分析更长时间内用户的数据，5年，10年，这数据就上TB。总是有增无减，就不是可持续发展的套路，这个算法套路得改改。

如果方差算法能够像订单数一样不断增量处理，不就万事大吉了吗？

增量方差的推导

假设我们现在有两组样本值，一组为历史样本值：

h1,h2,...,hMh1,h2,...,hM

一组为增量样本值：

a1,a2,...,aNa1,a2,...,aN

根据之前介绍的方差和均值的定义，我们可以得到两组样本值的如下四个指标：

历史平均值

Hˉˉˉˉˉ=1M∑i=1MhiHˉ=1M∑i=1Mhi

历史方差

σ2H=1M∑i=1M(hi−Hˉˉˉˉˉ)2σH2=1M∑i=1M(hi−Hˉ)2

增量样本均值

Aˉˉˉˉ=1N∑j=1NajAˉ=1N∑j=1Naj

增量样本方差

σ2A=1N∑j=1N(aj−Aˉˉˉˉ)2σA2=1N∑j=1N(aj−Aˉ)2

目前关键问题在于：

h1,h2,...,hM,a1,a2,...,aNh1,h2,...,hM,a1,a2,...,aN

这组全量样本值的方差是否能够由历史样本和增量样本的指标直接计算得到。下面一码就给你推导推导，看能够做到这点。

首先，全量样本均值的计算如下：

Xˉˉˉˉ=1M+N[∑i=1Mhi+∑j=1Naj]=MHˉˉˉˉˉ+NAˉˉˉˉM+N(1)Xˉ=1M+N[∑i=1Mhi+∑j=1Naj](1)=MHˉ+NAˉM+N

其次，全量样本方差的计算和推导如下：

σ2=1M+N[∑i=1M(hi−Xˉˉˉˉ)2+∑j=1N(aj−Xˉˉˉˉ)2]=1M+N[∑i=1M((hi−Hˉˉˉˉˉ)−(Xˉˉˉˉ−Hˉˉˉˉˉ))2+∑j=1N((aj−Aˉˉˉˉ)−(Xˉˉˉˉ−Aˉˉˉˉ))2]=1M+N[∑i=1M((hi−Hˉˉˉˉˉ)2−2(hi−Hˉˉˉˉˉ)(Xˉˉˉˉ−Hˉˉˉˉˉ)+(Xˉˉˉˉ−Hˉˉˉˉˉ)2)+∑j=1N((aj−Aˉˉˉˉ)2−2(aj−Aˉˉˉˉ)(Xˉˉˉˉ−Aˉˉˉˉ)+(Xˉˉˉˉ−Aˉˉˉˉ)2)]=1M+N[Mσ2H+M(Xˉˉˉˉ−Hˉˉˉˉˉ)2−2(Xˉˉˉˉ−Hˉˉˉˉˉ)(∑i=1Mhi−MHˉˉˉˉˉ)+Nσ2A+N(Xˉˉˉˉ−Aˉˉˉˉ)2−2(Xˉˉˉˉ−Aˉˉˉˉ)(∑j=1Naj−NAˉˉˉˉ)]=1M+N[Mσ2H+M(Xˉˉˉˉ−Hˉˉˉˉˉ)2+Nσ2A+N(Xˉˉˉˉ−Aˉˉˉˉ)2]=M[σ2H+(Xˉˉˉˉ−Hˉˉˉˉˉ)2]+N[σ2A+(Xˉˉˉˉ−Aˉˉˉˉ)2]M+N(2)(3)(4)(5)(6)(7)(8)σ2=1M+N[∑i=1M(hi−Xˉ)2+∑j=1N(aj−Xˉ)2](2)=1M+N[∑i=1M((hi−Hˉ)−(Xˉ−Hˉ))2+∑j=1N((aj−Aˉ)−(Xˉ−Aˉ))2](3)=1M+N[∑i=1M((hi−Hˉ)2−2(hi−Hˉ)(Xˉ−Hˉ)+(Xˉ−Hˉ)2)(4)+∑j=1N((aj−Aˉ)2−2(aj−Aˉ)(Xˉ−Aˉ)+(Xˉ−Aˉ)2)](5)=1M+N[MσH2+M(Xˉ−Hˉ)2−2(Xˉ−Hˉ)(∑i=1Mhi−MHˉ)(6)+NσA2+N(Xˉ−Aˉ)2−2(Xˉ−Aˉ)(∑j=1Naj−NAˉ)](7)=1M+N[MσH2+M(Xˉ−Hˉ)2+NσA2+N(Xˉ−Aˉ)2](8)=M[σH2+(Xˉ−Hˉ)2]+N[σA2+(Xˉ−Aˉ)2]M+N

从推导出来的公式看，通过两组样本的样本数，均值，方差，完全可以计算出全量样本的方差。

eric2013

谢谢楼主分享。