Быстрый способ расчета однородности или расхождения набора номеров

Question

Hello Предположим, у меня есть набор чисел, я хочу быстро рассчитать некоторую меру однородности. Я знаю, что дисперсия является наиболее очевидным ответом, но я боюсь, что сложность наивного алгоритма слишком высока У кого-нибудь есть предложения?

Answer 1

«Интуитивно понятные» алгоритмы вычисления дисперсии обычно страдают одним или обоими из следующих:

1. Используйте два цикла (один для вычисления среднего, другой для дисперсии)
2. Не численно устойчивы

Хороший алгоритм, имеющий только один цикл и численно устойчивый, обусловлен D. Кнут (как всегда).

Из Википедии :

n = 0
mean = 0
M2 = 0
 def calculate_online_variance(x):
    n = n + 1
    delta = x - mean
    mean = mean + delta/n
    M2 = M2 + delta*(x - mean)  # This expression uses the new value of mean

    variance_n = M2/n
    variance = M2/(n - 1) #note on the first pass with n=1 this will fail (should return Inf)
    return variance

Вы должны вызывать calc_online_variance (x) для каждой точки, и она возвращает вычисленную дисперсию.

Answer 2

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

1. . Вычислить mu, среднее значение множества
2. Пусть s = 0
3. Для каждого элемента x в списке, пусть s = s + (x - mu) * (x-mu)
4. Рассчитать s / n

Обратите внимание, что иногда лучше разделить s на n-1 (особенно, когда вы беспокоитесь о смещенных оценках).См. статью в Википедии об исправлении Бесселя , почему

Конечно, более низкая дисперсия указывает на высокую однородность.

Обратите внимание, что, возможно, было бы неплохо дополнительно разделить вашу дисперсию на mu ^ 2, чтобы получить абсолютную меру однородности (то есть так, чтобы считалось ".5 1 .5 1 .5 1"менее плотный, чем "100 101 100 101 100 101", так как относительные различия в первом случае намного больше, чем во втором).