Cálculo do novo desvio padrão usando o desvio padrão antigo após alteração no conjunto de dados

16

Eu tenho uma matriz de n valores reais, que tem média μold e desvio padrão σold . Se um elemento da matriz xi for substituído por outro elemento xj , a nova média será

μnew=μold+xj−xin

A vantagem dessa abordagem é que ela requer computação constante, independentemente do valor de n . Existe alguma abordagem para calcular σnew usando σold como o cálculo de μnew usando μold ?

standard-deviation online do utilizador
fonte
Isso é lição de casa? Uma tarefa muito semelhante foi perguntado em nosso curso de estatística matemática ...
krlmlr
2
@ user946850: Não, não é tarefa de casa. Estou conduzindo minha tese sobre Algoritmo Evolucionário . Eu quero usar o desvio padrão como uma medida da diversidade populacional. Apenas procurando uma solução mais eficiente.
usuário
1
O SD é a raiz quadrada da variação, que é apenas o valor médio quadrático (ajustado por um múltiplo da média quadrática, que você já sabe como atualizar). Portanto, os mesmos métodos usados ​​para calcular uma média de corrida podem ser aplicados sem nenhuma alteração fundamental para calcular uma variação de corrida. De fato, estatísticas muito mais sofisticadas podem ser calculadas on-line usando as mesmas idéias: consulte os threads em stats.stackexchange.com/questions/6920 e stats.stackexchange.com/questions/23481 , por exemplo.
whuber
1
@ whuber: isso é mencionado no artigo da Wikipedia para Variance , mas também com uma nota sobre o cancelamento catastrófico (ou perda de significância) que pode ocorrer. Isso é superestimado ou é um problema real para a variação em execução?
krlmlr
Essa é uma ótima pergunta. Se você acumular as variações ingenuamente, sem centralizá-las antecipadamente, poderá realmente ter problemas. O problema ocorre quando os números são enormes, mas sua variação é pequena. Por exemplo, considere uma série de medições precisas da velocidade da luz em m / s, como em 299792458.145, 299792457.883, 299792457.998, ...: sua variação, que é em torno de 0,01, é tão pequena em comparação com seus quadrados, em torno de , que o cálculo descuidado (mesmo em dupla precisão) resultaria em variação zero: todos os dígitos significativos desapareceriam. 1017
whuber

Respostas:

7

Uma seção no artigo da Wikipedia sobre "Algoritmos para calcular a variação" mostra como calcular a variação se elementos forem adicionados às suas observações. (Lembre-se de que o desvio padrão é a raiz quadrada da variação.) Suponha que você acrescente à sua matriz e, em seguida,xn+1

σnew2=σold2+(xn+1−μnew)(xn+1−μold).

EDIT : A fórmula acima parece estar errada, veja o comentário.

Agora, substituir um elemento significa adicionar uma observação e remover outra; ambos podem ser calculados com a fórmula acima. No entanto, lembre-se de que podem ocorrer problemas de estabilidade numérica; o artigo citado também propõe variantes numericamente estáveis.

Para obter a fórmula por si mesmo, compute usando a definição de variância da amostra e substituto μ n e w pela fórmula que você deu quando apropriado. Isso fornece σ 2 n e w - σ 2 o l d no final e, portanto, uma fórmula para σ n e w μ o l d(n−1)(σnew2−σold2)μnewσnew2−σold2σnew dado eσoldμold . Na minha notação, suponho que você substitua o elemento por x ′ n :xnxn′

σ2=(n−1)−1∑k(xk−μ)2(n−1)(σnew2−σold2)=∑k=1n−1((xk−μnew)2−(xk−μold)2)+ ((xn′−μnew)2−(xn−μold)2)=∑k=1n−1((xk−μold−n−1(xn′−xn))2−(xk−μold)2)+ ((xn′−μold−n−1(xn′−xn))2−(xn−μold)2)

The xk in the sum transform into something dependent of μold, but you'll have to work the equation a little bit more to derive a neat result. This should give you the general idea.

krlmlr
fonte
the first formula you gave does not seem correct, well it means that if the xn+1 is smaller/larger then from both new and old mean, the variance always increases, which does not make any sense. It may increase or decrease depending on the distribution.
Emmet B
@EmmetB: Yes, you're right -- this should probably be σnew2=n−1nσold2+1n(xn+1−μnew)(xn+1−μold). Unfortunately, this renders void my whole discussion from there, but I'm leaving it for historic purposes. Feel free to edit, though.
krlmlr
4

Based on what i think i'm reading on the linked Wikipedia article you can maintain a "running" standard deviation:

real sum = 0;
int count = 0;
real S = 0;
real variance = 0;

real GetRunningStandardDeviation(ref sum, ref count, ref S, x)
{
   real oldMean;

   if (count >= 1)
   {
       real oldMean = sum / count;
       sum = sum + x;
       count = count + 1;
       real newMean = sum / count;

       S = S + (x-oldMean)*(x-newMean)
   }
   else
   {
       sum = x;
       count = 1;
       S = 0;         
   }

   //estimated Variance = (S / (k-1) )
   //estimated Standard Deviation = sqrt(variance)
   if (count > 1)
      return sqrt(S / (count-1) );
   else
      return 0;
}

Although in the article they don't maintain a separate running sum and count, but instead have the single mean. Since in thing i'm doing today i keep a count (for statistical purposes), it is more useful to calculate the means each time.

Ian Boyd
fonte
0

Given original x¯, s, and n, as well as the change of a given element xn to xn′, I believe your new standard deviation s′ will be the square root of

s2+1n−1(2nΔx¯(xn−x¯)+n(n−1)(Δx¯)2),
where Δx¯=x¯′−x¯, with x¯′ denoting the new mean.

Maybe there is a snazzier way of writing it?

I checked this against a small test case and it seemed to work.

Whistling in the Dark
fonte
1
@john / whistling in the Dark: I liked your answer, it seems work properly in my small dataset. Is there any mathematical foundation/reference on it? Could you kindly help?
Alok Chowdhury
The question was all @Whistling in the Dark, I just cleaned it up for the site. You should pose a new question referencing the question and answer here. And also you should upvote this answer if you feel that way.
John