[algorithm] 통계적 중앙값, 모드, 왜도, 첨도를 추정하기위한 “온라인”(반복자) 알고리즘?

값 집합의 중앙값, 모드, 왜도 및 / 또는 첨도를 추정하는 알고리즘이 있지만 한 번에 모든 값을 메모리에 저장할 필요는 없습니까?

기본 통계를 계산하고 싶습니다.

• 평균 : 산술 평균
• 분산 : 평균에서 제곱 된 편차의 평균
• 표준 편차 : 분산의 제곱근
• 중앙값 : 숫자의 큰 절반과 작은 절반을 구분하는 값
• 모드 : 세트에서 가장 자주 발견되는 값
• 왜도 : tl; 박사
• 첨도 : tl; 박사

이것들 중 하나를 계산하는 기본 공식은 초등학교 산술이며, 나는 그것들을 알고 있습니다. 이를 구현하는 많은 통계 라이브러리도 있습니다.

내 문제는 내가 처리하고있는 집합에있는 많은 수 (십억)의 값입니다. Python으로 작업하면 수십억 개의 요소로 목록이나 해시를 만들 수 없습니다. 내가 이것을 C로 썼더라도 10 억 요소 배열은 너무 실용적이지 않습니다.

데이터가 정렬되지 않습니다. 다른 프로세스에 의해 즉석에서 무작위로 생성됩니다. 각 세트의 크기는 매우 가변적이며 크기는 미리 알 수 없습니다.

나는 이미 평균과 분산을 꽤 잘 처리하는 방법을 알아 냈고, 어떤 순서로든 세트의 각 값을 반복합니다. (사실, 제 경우에는 생성 된 순서대로 가져옵니다.) 다음은 제가 사용하는 알고리즘입니다. http://en.wikipedia.org/wiki/Algorithms_for_calculating_variance#On-line_algorithm :

• 세 가지 변수 초기화 : 개수, 합계 및 sum_of_squares
• 각 값에 대해 :
  • 증가 카운트.
  • 합계에 값을 더합니다.
  • sum_of_squares에 값의 제곱을 더합니다.
• 합계를 개수로 나누고 변수 평균으로 저장합니다.
• sum_of_squares를 개수로 나누고 변수 mean_of_squares로 저장합니다.
• 제곱 평균, square_of_mean으로 저장합니다.
• mean_of_squares에서 square_of_mean을 빼서 분산으로 저장합니다.
• 출력 평균 및 분산.

이 “온라인”알고리즘에는 약점이 있지만 (예 : sum_of_squares가 정수 범위 또는 부동 소수점 정밀도보다 빠르게 커짐에 따른 정확도 문제) 기본적으로 각 세트에 모든 값을 저장할 필요없이 필요한 것을 제공합니다.

하지만 추가 통계 (중앙값, 모드, 왜도, 첨도)를 추정하는 데 유사한 기법이 있는지 여부는 알 수 없습니다. N 값을 처리하는 데 필요한 메모리가 실질적으로 O (N)보다 작은 한 편향된 추정기 또는 정확도를 어느 정도 저하시키는 방법으로 살 수 있습니다.

라이브러리에 “온라인”작업 중 하나 이상을 계산하는 함수가있는 경우 기존 통계 라이브러리를 가리키는 것도 도움이됩니다.