Онлайн оценка квартилей без сохранения наблюдений

Мне нужно вычислить квартили (Q1, медиана и Q3) в режиме реального времени на большом наборе данных без сохранения наблюдений. Сначала я попробовал алгоритм P-квадрата (Jain / Chlamtac), но меня это не удовлетворило (слишком частое использование процессора, и я не был уверен в точности, по крайней мере, в моем наборе данных).

Теперь я использую алгоритм FAME ( Feldman / Shavitt ) для оценки медианы на лету и пытаюсь вывести алгоритм для вычисления также Q1 и Q3:

M = Q1 = Q3 = first data value 
step =step_Q1 = step_Q3 = a small value
for each new data :
        # update median M 
        if M > data:
            M = M - step
        elif M < data:
            M = M + step
        if abs(data-M) < step:
            step = step /2

        # estimate Q1 using M
        if data < M:
            if Q1 > data:
                Q1 = Q1 - step_Q1
            elif Q1 < data:
                Q1 = Q1 + step_Q1
            if abs(data - Q1) < step_Q1:
                step_Q1 = step_Q1/2
        # estimate Q3 using M
        elif data > M:
            if Q3 > data:
                Q3 = Q3 - step_Q3
            elif Q3 < data:
                Q3 = Q3 + step_Q3
            if abs(data-Q3) < step_Q3:
                step_Q3 = step_Q3 /2

Чтобы возобновить, он просто использует медиану M, полученную на лету, чтобы разделить набор данных на две части, а затем повторно использовать один и тот же алгоритм для Q1 и Q3.

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

Большое спасибо за Вашу помощь !

==== РЕДАКТИРОВАТЬ =====

Для тех, кто интересуется такими вопросами, через несколько недель я, наконец, закончил, просто используя выборку из резервуара с ревервуаром 100 значений, и это дало очень удовлетворительные результаты (для меня).

quantiles median online Луи Хьюг
источник

Вы ищете доказательство того, что Q1 и Q2 сходятся к истинным квантилям, поскольку число примеров увеличивается аналогично анализу цепей Маркова на слайдах, которые вы связали? С точки зрения реализации, приведенный выше алгоритм не выглядит ошибочным (я тестировал аппроксимирующие квантили для стандартного нормального в R, и алгоритм работает нормально).

Theja

@ Theja спасибо, я не ищу доказательств (слишком много работы), а просто советы и комментарии. Основная проблема, которую я вижу, состоит в том, чтобы основывать вычисления на бегущей оценке медианы, как указал Уабер.

Луи Хьюг

Ответы:

Медиана - это точка, в которой 1/2 наблюдения опускаются ниже, а 1/2 выше. Точно так же 25-й перцентиль - это медиана для данных между минимумом и медианой, а 75-й перцентиль - это медиана между медианой и максимумом, так что да, я думаю, что вы на твердой почве, применяя алгоритм медианы, который вы используете сначала весь набор данных, чтобы разделить его, а затем на две результирующие части.

Обновление :

Этот вопрос о переполнении стека приводит к работе: Радж Джейн, Имрих Хламтак: Алгоритм P2 для динамического вычисления квантилей и гистограмм без сохранения наблюдений. Commun. ACM 28 (10): 1076-1085 (1985) , резюме которого указывает, что он, вероятно, представляет для вас большой интерес:

Предложен эвристический алгоритм для динамического расчета медианы и других квантилей. Оценки производятся динамически по мере генерации наблюдений. Наблюдения не сохраняются; следовательно, алгоритм имеет очень маленькое и фиксированное требование к памяти независимо от количества наблюдений. Это делает его идеальным для реализации в квантовом чипе, который может использоваться в промышленных контроллерах и рекордерах. Алгоритм далее распространяется на построение гистограммы. Точность алгоритма анализируется.

Авраам
источник

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

whuber

n

$n$

1 : 3

$1:3$

2 : 2

$2:2$

1 : 1

$1:1$

n

$n$

@Avraham, спасибо за указание на статью, как я уже говорил, я уже попробовал алгоритм P-квадрата от Chain и Chlamtac. в моем наборе данных алгоритм, который я описал, дает лучший результат (MSE) и работает быстрее. Так что я спрашивал, может ли это все же иметь какую-то проблему. Как отметил Уабер, тот факт, что он использует текущую оценку, является потенциальной проблемой; но я не знаю, действительно ли это важно или нет.

Луи Хьюг

Ой, видел это и забыл это. Мои извенения.

Авраам

Очень небольшое изменение в методе, который вы опубликовали, и вы можете вычислить любой произвольный процентиль, не вычисляя все квантили. Вот код Python:

class RunningPercentile:
    def __init__(self, percentile=0.5, step=0.1):
        self.step = step
        self.step_up = 1.0 - percentile
        self.step_down = percentile
        self.x = None

    def push(self, observation):
        if self.x is None:
            self.x = observation
            return

        if self.x > observation:
            self.x -= self.step * self.step_up
        elif self.x < observation:
            self.x += self.step * self.step_down
        if abs(observation - self.x) < self.step:
            self.step /= 2.0

и пример:

import numpy as np
import matplotlib.pyplot as plt

distribution = np.random.normal
running_percentile = RunningPercentile(0.841)
observations = []
for _ in range(1000000):
    observation = distribution()
    running_percentile.push(observation)
    observations.append(observation)

plt.figure(figsize=(10, 3))
plt.hist(observations, bins=100)
plt.axvline(running_percentile.x, c='k')
plt.show()

parrowdice
источник