Алгоритм онлайн / потоковой передачи для выбора верхнего X процента временного ряда

Question

Я работаю над временным рядом числовых значений, например, полученных датчиком температуры. Я хотел бы отфильтровать эти значения, примерно выбрав те образцы, которые образуют, например, верхние 10% полученных значений.

Очевидное решение для записи всех выборок и использования любого известного алгоритма для извлечения k-максимальных значений невозможно в моем случае по двум причинам:

• Ряд может быть бесконечным, память определенно нет.

• Я бы хотел, чтобы этот алгоритм можно было использовать в режиме реального времени или, по крайней мере, в потоковом режиме с заданной задержкой.

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

В отличие от этого вопроса , мне не нужна идеальная точность, хотя я хотел бы иметь возможность настроить параметры алгоритма выбора.

Я полагаю, что нечто подобное используется в медиа-кодеках с переменной скоростью передачи данных (VBR) за один проход для выделения доступной полосы пропускания каждому кадру путем определения количества доступных битов. К сожалению, все алгоритмы VBR, которые я изучал, слишком сфокусированы на DSP и медиапотоках, чтобы я мог их понять и / или реализовать.

Существуют ли какие-либо известные алгоритмы, которые могли бы помочь мне решить эту проблему? Будем очень благодарны за любые подсказки, которые будут ориентировать меня в правильном направлении.

Answer 1

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

В любое времяу вас есть небольшая куча, полная высоких предметов и большая куча, полная низких предметов, и вы знаете, был ли последний элемент в верхних 10% этих 10N.

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

Были опубликованы научные работы по поиску приблизительных квантилей потоковых данных.Одним из них является «Эффективное вычисление смещенных квантилей по потокам данных» , Кормод, Корн, Мутукришнан и Шривастава

Answer 2

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

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

Если вам нужно хранить весь поток, вам больше не нужен онлайн-алгоритм.

Теперь, если вы знаете что-то о распределении, возможно, вы сможете сделать что-то лучше ... Наивный алгоритм будетразделить поток на фрагменты и рассчитать 10% от каждого фрагмента.