мигрировал из math.stackexchange .
Я обрабатываю длинный поток целых чисел и рассматриваю возможность отслеживания нескольких моментов, чтобы иметь возможность приблизительно рассчитать различные процентили для потока без сохранения большого количества данных. Какой самый простой способ вычислить процентили из нескольких моментов. Есть ли лучший подход, который предполагает хранение небольшого количества данных?
algorithms
mathematical-statistics
moments
jonderry
источник
источник
Ответы:
Вы не заявляете об этом явно, но из вашего описания проблемы кажется вероятным, что вы хотите получить набор квантилей с высоким смещением (например, 50-й, 90-й, 95-й и 99-й процентили).
Если это так, у меня был большой успех с методом, описанным в «Эффективном вычислении смещенных квантилей над потоками данных» Cormode et al. Это быстрый алгоритм, который требует мало памяти, и его легко реализовать.
Метод основан на более раннем алгоритме Гринвальда и Ханны, который поддерживает небольшую выборку входного потока вместе с верхними и нижними границами ранга значений в выборке. Это требует больше места, чем набор нескольких моментов, но будет гораздо лучше точно описать интересную хвостовую область распределения.
источник
Существует более свежий и гораздо более простой алгоритм для этого, который обеспечивает очень хорошие оценки экстремальных квантилей.
Смотрите https://github.com/tdunning/t-digest
источник