시간 창 온라인 분산 알고리즘

Question

나는 사전 정의 된 시간 창 (예 : 지난 5 분)에서 롤링 분산을 계산하기위한 효율적인 온라인 알고리즘을 찾으려고합니다. 초당 10M 데이터 포인트의 빈도에 도달하기 때문에 시간 창 내 모든 데이터 포인트를 유지할 수 없다는 점에서 효율적이어야합니다. 이상적으로 알고리즘은 수치 적으로 안정해야합니다. 윈도우가 아닌 롤링 차이에 대해 Welford's algorithm을 알고 있습니다.

나는 고정 크기 windows에 대한 다른 응답을 알고 있습니다. 나는 이것이 다른 질문이라고 생각한다.

Answer 1

정확하게 말씀하신대로 문제를 해결할 수있을 것이라고 생각합니다.

부동 소수 샘플 1 = {0.0, 0.0} 0 = {-1.0, 1.0}의 쌍으로 인코딩 된 비트 스트림을 생각해 보자. 임의의 비트 스트림을 알고리즘에 인코딩 한 결과를 피드에 넣고 0의 스트림을 보내면 알고리즘 리포트는 윈도우의 가장 자리에서 방금 떨어진 샘플 쌍이 변동하는지 여부에 따라 변동합니다 {0.0, 0.0} 또는 {-1.0, 1.0}이었다.

그래서 알고리즘을 사용하여 슬라이딩 윈도우 크기의 약 절반 크기의 비트 스트림을 외울 수 있습니다. 따라서이 정도의 저장 용량을 사용하지 않으면 알고리즘을 구현할 수 없습니다.

아마 몇 가지 지수 스무딩 방식을 사용할 수 있습니다. 간단한 지수 스무딩은 가중치가 기하 급수적으로 감소하는 가중치 평균과 동일하며, 제곱 값을 부드럽게하면 기하 급수적으로 제곱 된 합계를 얻게됩니다. 지수 가중치가 아닌 미확인 값의 합계가있는 경우 두 값을 결합하여 원하는 중앙 값에 대해 일부 중심 값의 지수 편차 제곱의 지수 가중치 합계를 얻을 수 있습니다. 물론 수치 적으로 안정된 것을 얻기 위해서는이 아이디어를 크게 개선해야합니다. 위 인용문이 인용 한 Wikipedia 기사의 끝에있는 가중 분산 알고리즘 중 하나의 세부 사항에서 다루어집니다.

Answer 2

이것은 평균 및 분산을 결합하는 방법에 대한 tibbe의 의견에 대한 답변입니다.

단어에서 결합 된 평균은 평균의 평균이며, 결합 된 분산은 평균의 분산과 평균의 합입니다.

더 많은 형식적으로 : 데이터의 k 부분 집합에 대해 개수 n, 평균 m 및 분산 평균이 있다고 가정합니다. 서브 세트는 해체된다고 가정 카운트 N은 M과 K 개의 서브 세트의 조합의 변동 V에 의해 계산 될 수 있음을 의미 :

N = Sum{ n[i] } 
M = Sum{ w[i]*m[i] } 
V = Sum{ w[i]*v[i] } + Sum{ w[i]*(m[i]-M)*(m[i]-M)} 
where 
w[i] = n[i]/N