2013-05-27 5 views
2

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

Текущий расчет онлайн-дисперсии - это однопроходный алгоритм с двумя делениями и умножениями в основном цикле (что и влияет на скорость). Из википедии:

def online_variance(data): 
    n = 0 
    mean = 0 
    M2 = 0 

    for x in data: 
     n = n + 1 
     delta = x - mean 
     mean = mean + delta/n 
     M2 = M2 + delta*(x - mean) 

    variance = M2/(n - 1) 
    return variance 
+0

Мы не можем сказать, что алгоритм быстрее другого, не зная другого ... – Floris

ответ

3

То, что вызывает расчет наивной дисперсии для нестабильно является тем фактом, что вы отдельно просуммировать X (чтобы получить среднее (х)) 2 значения и Х ^, а затем взять разницу

var = mean(x^2) - (mean(x))^2 

Но поскольку определение дисперсии является

var = mean((x - mean(x))^2) 

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

EDIT Теперь, когда вы дали «оригинальный» код, легко быть лучше (быстрее). Как вы правильно указываете, деление во внутреннем цикле замедляет вас. Попробуйте это для сравнения:

def newVariance(data, mean): 
    n = 0 
    M2 = 0 

    for x in data: 
    n = n + 1 
    delta = x - mean 
    M2 = M2 + delta * delta 

    variance = M2/(n - 1) 
    return variance 

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