Как уменьшить вычисление среднего числа к подмножествам общим способом?

Пусть X будет вашим набором образцов. Разделите его на два набора A и B любым способом. Определите delta = m_B - m_A , где m_S обозначает среднее значение набора S . Тогда

m_X = m_A + delta * |B| / |X|

, где | S | обозначает мощность набора S . Теперь вы можете повторно применить это к разделу и вычислить среднее значение.

Почему это правда? Пусть s = 1 / | A | и t = 1 / | B | и u = 1 / | X | (для удобства обозначений) и пусть aSigma и bSigma обозначают сумму элементов в A и B соответственно, так что:

  m_A + delta * |B| / |X|
= s * aSigma + u * |B| * (t * bSigma - s * aSigma)
= s * aSigma + u * (bSigma - |B| * s * aSigma)
= s * aSigma + u * bSigma - u * |B| * s * aSigma
= s * aSigma * (1 - u * |B|) + u * bSigma
= s * aSigma * (u * |X| - u * |B|) + u * bSigma
= s * u * aSigma * (|X| - |B|) + u * bSigma
= s * u * aSigma * |A| + u * bSigma
= u * aSigma + u * bSigma
= u * (aSigma + bSigma)
= u * (xSigma)
= xSigma / |X|
= m_X

Доказательство завершено.

Отсюда очевидно, как использовать это либо для рекурсивного вычисления среднего (скажем, путем многократного разделения набора пополам), либо как использовать это для распараллеливания вычисления среднего значения набора.

Известный онлайн-алгоритм вычисления среднего - лишь частный случай этого. Это алгоритм, который, если m является средним значением {x_1, x_2, ..., x_n} , то среднее значение {x_1, x_2, ..., x_n, x_ (n + 1)} равно m + ((x_ (n + 1) - m)) / (n + 1) . Таким образом, с X = {x_1, x_2, ..., x_ (n + 1)} , A = {x_ (n + 1)} и B = {x_1, x_2, ..., x_n} мы восстанавливаем онлайн-алгоритм.

Хорошо известный онлайн-алгоритм вычисления среднего - лишь частный случай этого. Это алгоритм, который, если m является средним значением {x_1, x_2, ..., x_n} , то среднее значение {x_1, x_2, ..., x_n, x_ (n + 1)} равно m + ((x_ (n + 1) - m)) / (n + 1) . Таким образом, с X = {x_1, x_2, ..., x_ (n + 1)} , A = {x_ (n + 1)} и B = {x_1, x_2, ..., x_n} мы восстанавливаем онлайн-алгоритм.

Хорошо известный онлайн-алгоритм вычисления среднего - лишь частный случай этого. Это алгоритм, который, если m является средним значением {x_1, x_2, ..., x_n} , то среднее значение {x_1, x_2, ..., x_n, x_ (n + 1)} равно m + ((x_ (n + 1) - m)) / (n + 1) . Таким образом, с X = {x_1, x_2, ..., x_ (n + 1)} , A = {x_ (n + 1)} и B = {x_1, x_2, ..., x_n} мы восстанавливаем онлайн-алгоритм.

Если вы заранее знаете количество значений (скажем, N ), вы просто добавляете 1 / N + 2 / N + 3 / N и т.д., предположим, что у вас есть значения 1, 2, 3 . Вы можете разбить это на столько вычислений, сколько захотите, и просто сложить свои результаты. Это может привести к небольшой потере точности, но это не должно быть проблемой, если вам также не нужен сверхточный результат.

Если вы заранее не знаете количество элементов, вам, возможно, придется более творческий. Но вы, опять же, можете делать это постепенно. Скажем, список 1, 2, 3, 4 . Начните с среднего = 1 . Тогда среднее = среднее * (1/2) + 2 * (1/2) . Тогда среднее = среднее * (2/3) + 3 * (1/3) . Тогда среднее значение = среднее значение * (3/4) + 4 * (1/4) и т. Д. Это легко обобщить,

Нестандартное мышление: Используйте вместо этого медиану. Это намного проще вычислить - существует множество алгоритмов (например, с использованием очередей), вы часто можете найти хорошие аргументы в пользу того, почему это более значимо для наборов данных (меньше подвержено влиянию экстремальных значений и т. Д.), И у вас не будет проблем с числовая точность. Это будет быстро и эффективно. Кроме того, для больших наборов данных (которые, похоже, у вас есть), если распределения действительно не странные, значения для среднего и медианы будут одинаковыми.

Когда вы разбиваете числа на наборы, вы просто делите их на общее число, или мне что-то не хватает?

Вы написали это как

/ 1   2   3 \   / 4   5   6 \
| - + - + - | + | - + - + - |
\ 3   3   3 /   \ 3   3   3 /
 ----------      -----------
      2               2

, но это всего лишь

/ 1   2   3 \   / 4   5   6 \
| - + - + - | + | - + - + - |
\ 6   6   6 /   \ 6   6   6 /

, поэтому для чисел от 1 до 7 одна возможная группировка - это просто

/ 1   2   3 \   / 4   5   6 \   / 7 \
| - + - + - | + | - + - + - | + | - |
\ 7   7   7 /   \ 7   7   7 /   \ 7 /

Average of x_1 .. x_N
    = (Sum(i=1,N,x_i)) / N
    = (Sum(i=1,M,x_i) + Sum(i=M+1,N,x_i)) / N
    = (Sum(i=1,M,x_i)) / N + (Sum(i=M+1,N,x_i)) / N

Это можно применять неоднократно, и это верно независимо от того, имеют ли суммы одинакового размера. Итак:

• Продолжайте добавлять члены до тех пор, пока оба:
• • добавление еще одного приведет к переполнению (или иначе потеряет точность)
• • деление на N не приведет к потере значимости
• Разделите сумму на N
• Добавьте результат к среднее-до сих пор

Есть один очевидный неудобный случай, заключающийся в том, что в конце последовательности есть несколько очень маленьких членов, так что у вас заканчиваются значения, прежде чем вы удовлетворяете условию «деление на N не приведет к потере значимости» . В этом случае просто отбросьте эти значения - если их вклад в среднее значение не может быть представлен в вашем плавающем типе, то он, в частности, меньше, чем точность вашего среднего. Поэтому для результата не имеет значения, включаете вы эти термины или нет.

Есть также несколько менее очевидных неудобных случаев, связанных с потерей точности отдельных суммирований. Например, какое среднее из значений:

10^100, 1, -10^100

Математика говорит, что это 1, но арифметика с плавающей запятой говорит, что это зависит от того, в каком порядке вы складываете члены, и в 4 из 6 возможных вариантов это 0, потому что (10 ^ 100) + 1 = 10 ^ 100. Но я думаю, что некоммутативность арифметики с плавающей запятой - это другая и более общая проблема, чем этот вопрос. Если о сортировке ввода не может быть и речи, я думаю, что есть вещи, которые вы можете сделать, если вы будете поддерживать множество аккумуляторов разной величины и добавлять каждое новое значение к тому, какое из них даст наилучшую точность. Но я точно не знаю.

s среднее значение:

10^100, 1, -10^100

Математика говорит, что это 1, но арифметика с плавающей запятой говорит, что это зависит от того, в каком порядке вы складываете члены, и в 4 из 6 возможных вариантов это 0, потому что (10 ^ 100) + 1 = 10 ^ 100. Но я думаю, что некоммутативность арифметики с плавающей запятой - это другая и более общая проблема, чем этот вопрос. Если о сортировке ввода не может быть и речи, я думаю, что есть вещи, которые вы можете сделать, если вы будете поддерживать множество аккумуляторов разной величины и добавлять каждое новое значение к тому, какое из них даст наилучшую точность. Но я точно не знаю.

s среднее значение:

10^100, 1, -10^100

Математика говорит, что это 1, но арифметика с плавающей запятой говорит, что это зависит от того, в каком порядке вы складываете члены, и в 4 из 6 возможных вариантов это 0, потому что (10 ^ 100) + 1 = 10 ^ 100. Но я думаю, что некоммутативность арифметики с плавающей запятой - это другая и более общая проблема, чем этот вопрос. Если о сортировке ввода не может быть и речи, я думаю, что есть вещи, которые вы можете сделать, если вы будете поддерживать множество аккумуляторов разной величины и добавлять каждое новое значение к тому, какое из них даст наилучшую точность. Но я точно не знаю.

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

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

Некоторые математические решения здесь очень хороши. Вот простое техническое решение.

Используйте больший тип данных. Это делится на две возможности:

1. Использовать высокоточную библиотеку с плавающей запятой. Тот, кто сталкивается с необходимостью усреднить миллиард чисел, вероятно, имеет ресурсы для покупки или способность писать 128-битную (или более длинную) библиотеку с плавающей запятой.

   Я понимаю здесь недостатки. Это определенно будет медленнее, чем использование внутренних типов. Вы все равно можете переполниться / опуститься, если количество значений станет слишком большим. Yada yada.

2. Если ваши значения являются целыми числами или могут быть легко преобразованы в целые числа, сохраните сумму в списке целых чисел. При переполнении просто добавьте еще одно целое число. По сути, это упрощенная реализация первого варианта. один набор из них) и большую часть своей работы выполняет с целыми числами. Однако я не оптимизировал его, и я почти уверен, что при необходимости его можно сделать немного быстрее. Отказ от рекурсивного вызова функций и индексации списка был бы хорошим началом. Опять же упражнение для читателя. Код призван быть легким для понимания.

   Если кто-то более мотивированный, чем я в данный момент, захочет проверить правильность кода и исправить любые проблемы, которые могут возникнуть, пожалуйста, будьте моим гостем.

   ---

   Я ' Мы проверили этот код и внесли несколько небольших исправлений (отсутствующая пара круглых скобок в вызове конструктора List и неправильный делитель в последнем делении DivideBy ] функция).

   Я проверил его, сначала прогнав через 1000 наборов случайной длины (от 1 до 1000), заполненных случайными целыми числами (от 0 до 2 ³² - 1). Это были наборы, точность которых я мог легко и быстро проверить, также используя для них каноническое среднее.

   Затем я протестировал 100 ^* больших серий со случайной длиной от 10 ⁵ ] и 10 ⁹ . Нижняя и верхняя границы этих серий также были выбраны случайным образом, с ограничениями, чтобы серия соответствовала диапазону 32-битного целого числа. Для любой серии результаты легко проверить как (нижняя граница + верхняя граница) / 2 .

   _{^{* Хорошо, это небольшая невинная ложь. Я прервал тест большой серии примерно после 20 или 30 успешных запусков. Серия длиной 10 9 занимает чуть менее полутора минут на моей машине, так что полчаса или около того тестирования этой процедуры было достаточно на мой вкус.}}

   Для тех, кто заинтересован, мой тестовый код приведен ниже:

   static IEnumerable<uint> GetSeries(uint lowerbound, uint upperbound){
       for(uint i = lowerbound; i <= upperbound; i++)
           yield return i;
   }
   
   static void Test(){
       Console.BufferHeight = 1200;
       Random rnd = new Random();
   
       for(int i = 0; i < 1000; i++){
           uint[] numbers = new uint[rnd.Next(1, 1000)];
           for(int j = 0; j < numbers.Length; j++)
               numbers[j] = (uint)rnd.Next();
   
           double sum = 0;
           foreach(uint n in numbers)
               sum += n;
   
           double avg = sum / numbers.Length;
           double ans = new BigMeanSet().GetAverage(numbers);
   
           Console.WriteLine("{0}: {1} - {2} = {3}", numbers.Length, avg, ans, avg - ans);
   
           if(avg != ans)
               Debugger.Break();
       }
   
       for(int i = 0; i < 100; i++){
           uint length     = (uint)rnd.Next(100000, 1000000001);
           uint lowerbound = (uint)rnd.Next(int.MaxValue - (int)length);
           uint upperbound = lowerbound + length;
   
           double avg = ((double)lowerbound + upperbound) / 2;
           double ans = new BigMeanSet().GetAverage(GetSeries(lowerbound, upperbound));
   
           Console.WriteLine("{0}: {1} - {2} = {3}", length, avg, ans, avg - ans);
   
           if(avg != ans)
               Debugger.Break();
       }
   }
   

Вот еще один подход. Вы "получаете" числа один за другим из какого-то источника, но можете отслеживать среднее на каждом шаге.

Сначала я выпишу формулу среднего на шаге n+1:

mean[n+1] = mean[n] - (mean[n] - x[n+1]) / (n+1)

с исходным условием:

mean[0] = x[0]

(индекс начинается с нуля).

Первое уравнение можно упростить до:

mean[n+1] = n * mean[n] / (n+1) + x[n+1]/(n+1)

Идея состоит в том, что Вы отслеживаете среднее, и когда Вы "получаете" следующее значение в Вашей последовательности, Вы вычисляете его смещение от текущего среднего, и делите его поровну между n+1 примерами, рассмотренными до сих пор, и соответствующим образом корректируете свое среднее значение. Если Ваши числа не имеют большой дисперсии, Ваше бегущее среднее должно быть очень слегка скорректировано с новыми числами, так как n становится большим.

Очевидно, что этот метод работает, даже если Вы не знаете общего количества значений при старте. Дополнительным преимуществом является то, что Вы всегда знаете значение текущего среднего. Один из недостатков, о котором я могу подумать, заключается в том, что он, вероятно, придает больше "веса" числам, видимым в начале (не в строгом математическом смысле, а из-за представления с плавающей точкой)

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

В качестве теста я сгенерировал N=100000 нормально распределенных случайных чисел со средним нулем и дисперсией 1. Затем я вычислил их среднее значение тремя методами.

1. sum(numbers) / N, назовем его m₁,
2. мой метод выше, назовем его m₂,
3. сортируем числа, а затем используем мой метод выше, назовем его m₃.

Вот что я нашел: m₁ - m₂ ∼ -4. 6×10^-17, m₁ - m₃ ∼ -3×10^-15, m₂ - m₃ ∼ -3×10^-15. Таким образом, если ваши номера отсортированы, то ошибка может быть недостаточно мала для вас. (Обратите внимание, однако, что даже самая худшая ошибка - это 10^-15 частей в 1 для 100000 чисел, так что в любом случае она может быть достаточно хорошей)

.