Среднее и стандартное отклонениебольшого набора данных с использованием рекурсии

Question

Допустим, у меня большой набор данных.

Затем я могу разделить его на два, найти среднее из этих двух и вычислить среднее из последних двух значений, которые я получу.

а) Является ли это средним значением исходного большого количества?

б) Могу ли я использовать такой метод расчета стандартного отклонения ??

Answer 1

а) только если наборы, на которые вы делите, всегда имеют одинаковый размер, это означает, что размер исходного набора должен быть степенью 2.

Например, среднее значение {6} равно 6, а среднее значение {3,6} равно 4,5, но среднее значение {3,6,6} - это не 5,25, а 5 *.

Конечно, вы можете рекурсивно разделить на части, чтобы вычислить сумму, и поделить на общий размер в конце. Не уверен, что это вам хорошо.

б) нет

Например, s.d для {2} равно 0, а s.d. {1} равен 0, но s.d для {1,2} не равно 0.

После того, как вы вычислили среднее значение для всего набора, вы можете рекурсивно разделить, чтобы вычислить среднеквадратичное отклонение от среднего, и, как и в случае среднего значения, разделить на общий размер и взять квадратный корень в конце. [Правка: на самом деле все, что вам нужно для вычисления s.d, это сумма квадратов, сумма и количество. Забыли об этом. Таким образом, вам не нужно сначала вычислять среднее значение]

Answer 2

Конечно, вы можете. Нет необходимости в равных наборах, сила двух. Псевдокод:

N1,mean1,s1;
N2,mean2,s2;
N12,mean12,s12;

N12 = N1+N2;
mean12 = ((mean1*N1) + (mean2*N2)) / N12;
s12 = sqrt( (s1*s1*N1 + s2*s2*N2) / N12 + N1*N2/(N12*N12)*(s1-s2)*(s1-s2) );

http://en.wikipedia.org/wiki/Weighted_mean

http://en.wikipedia.org/wiki/Standard_deviation#Combining_standard_deviations

Answer 3

On (a) - это только правильно, если вы точно поделили набор на две части. Например, если было нечетное количество предметов, есть небольшая утяжеленность в сторону меньшей «половины». Чем больше набор, тем менее значимой является проблема. Тем не менее, проблема повторяется для небольших наборов, когда вы делите. Вы получаете очень большую ошибку при разделении набора из трех предметов на один предмет и пару - каждый предмет в паре имеет лишь половину значимости для конечного результата, как отдельный предмет.

Я не вижу усиления, хотя. Вы все еще делаете столько дополнений. Вы даже в конечном итоге делаете больше делений. Что еще более важно, вы обращаетесь к памяти в непоследовательном порядке, что приводит к снижению производительности кэша.

Обычный подход для среднего и стандартного отклонения состоит в том, чтобы сначала вычислить сумму всех элементов и сумму квадратов - оба в одном цикле. Старые калькуляторы использовали это для вычисления промежуточных итогов, а также для подсчета количества предметов по мере их поступления. В конце концов, эти три значения (n, сумма-x и сумма-x-квадрат) - это все, что вам нужно - остальное - просто замена стандартных формул для среднего и стандартного отклонения.

EDIT

Если вы не можете использовать рекурсию для этого, посмотрите "хвостовая рекурсия". Математически хвостовая рекурсия и итерация эквивалентны - разные представления одного и того же. В терминах реализации хвостовая рекурсия может вызвать переполнение стека, когда итерация будет работать, но (1) некоторые языки гарантируют, что этого не произойдет (например, Scheme, Haskell), и (2) многие компиляторы все равно будут обрабатывать это как оптимизацию (например, GCC для C или C ++).

Answer 4

Это неверно, но если вы можете выразить среднее и стандартное отклонение набора от среднего значения, стандартных отклонений и размера наборов, на которые этот набор делится.

В частности, если m_x, s_x и n_x являются средними значениями, стандартными отклонениями и размерами x, а X разбивается на множество x, то

n_X = sum_x(n_x)
m_X = sum_x(n_x m_x)/n_X
s_X^2 = (sum_x(n_x(s_x^2 + m_x^2)) - m_X)/n_X

при условии, что стандартное отклонение имеет вид суммы (x - среднее (x)) / n; если это образец несмещенной оценки, просто отрегулируйте веса соответственно.