«Потоковая» статистика?

Или как это назвать?
 
+
-
edit
 

Balancer

администратор
★★★★★
Есть неупорядоченный поток данных и крайне скудные вычислительные ресурсы. Есть простой способ приближённого подсчёта средней величины. Требуется только одна ячейка памяти (Avg) и затем, при получении очередного значения (X):

Avg = (Avg*N + X)/(N + 1),

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

А вот как аналогично считать минимальные и максимальные значения за период? Как считать минимум и максимум за всю историю — понятно, обычное условие. Но если данные имеют склонность «сдвигаться», то найденное максимальное и минимальное значение через какое-то время будут уже не актуальны. Имея массив данных можно тупо выбирать минимум/максимум за последний отрезок времени. Но желательно, аналогично, укладываться в одну переменную.

Навскидку полагаю, можно пробовать метод, аналогичный среднему, только с большим N и если X окажется меньше (для минимума) — принудительно записывать его в переменную. Типа:

if x < min then min = x else min = (min*99+x)/100

Есть что-то более корректное и изящное? :)
 55

ssb

новичок

Balancer> ...
Balancer> Есть что-то более корректное и изящное? :)

Есть интересный алгоритм для получения порядковой статистики (минимум, максимум, медиана или любой квантиль) от последних N принятых величин. Рецепт:

Берём бинарное сортирующее дерево. Для эффективности организуем его in-place в массиве размера N (как в heapsort), причём в массиве элементы располагаются в порядке следования по времени. Отдельно храним указатель на самый старый (N-й) элемент. Таким образом наша структура преставляет собой одновременно и дерево и циклический список и работа ведётся в фиксированном массиве без обращения к системе за новой памятью.

Алгоритм добавления нового элемента очевиден: по указателю выбираем самый старый элемент, удаляем его из дерева. На его место записываем новый. Вставляем его в дерево. Передвигаем указатель на следующий по времени прихода элемент.

Для получения элемента по его порядковому номеру требуется хитрая модификация дерева, описанная Кнутом в TAOCP в пункте 6.2.3 (третий том). Модификация заключается в добавлении одного поля RANK в узлы дерева и, соответственно, обновлении этого поля по заданному рецепту в алгоритмах поиска/вставки и удаления элементов. Плюс дополнительный алгоритм поиска элемента по его порядковому номеру (который очень похож на стандартный алгоритм поиска по ключу).

В итоге имеем решение, которое работает в фиксированном массиве размером N ячеек. На добавление новой величины и запроса порядковой статистики требуется O (log N) времени.

У меня есть реализация описанной схемы на C.
 61.061.0

Balancer

администратор
★★★★★
ssb> Есть интересный алгоритм для получения порядковой статистики (минимум, максимум, медиана или любой квантиль) от последних N принятых величин.

Не годится. N реально большое должно быть. Скажем, выборка за сутки, а отсчёты каждые 10 секунд. Памяти реально — единичные ячейки :)

При полном хранении какого-то числа отсчётов посчитать по любому классическому алгоритму не проблема. Со временем расчёта проблем нет :)
 55

GOGI

координатор
★★★★
Я видел только алгоритм экспоненциального скользящего среднего, без использования буфера. Ну его ты и сам легко найдешь.
А так мне кажется на 518 тысячах выборок все это приблизительное будет сильно врать.
А что за железо такое?
1  52.052.0

Balancer

администратор
★★★★★
GOGI> А так мне кажется на 518 тысячах выборок все это приблизительное будет сильно врать.

Я ж и пишу приблизительно :) Мне не нужна полная точность.

GOGI> А что за железо такое?

Да всякое встраиваемое. И распределённое key-value.

GOGI> Я видел только алгоритм экспоненциального скользящего среднего

О! Это как раз, по сути, и есть то, что я в начале привёл. Только формула в другом виде. А суть та же — накопленное среднее и новое значение складываются долями.
 55

Balancer

администратор
★★★★★
GOGI> А что за железо такое?

Вот пример (один из). Есть тупые сенсоры газов MQ-XXX. Они реально очень тупые и просто показывают сопротивление подогретой подложки, которое меняется в зависимости от изменения концентрации целевых газов. Проблема в том, что правильные попугаи там не абсолютные, и относительные к сопротивлению в инертной атмосфере, X = R/R0. А это R0 имеет склонность со временем уплывать и сильно. Перекалибровывать периодически — не выход. Но концентрация измеряемых газов часто падает до нуля (типа, регулярное проветривание и т.п.), поэтому в качестве R0 можно брать минимум за период. Хоть за сутки, хотя можно/лучше и за больше, скажем, за месяц.

Если тупо считать абсолютный минимум, то не будет учитываться уплывание. Надо периодически сбрасывать.

Хранить N последний значений, в общем, можно (вот и на графике в аттаче — там в RRD много истории), но это привлечение внешнего ресурса, система перестаёт быть автономной.

Вот первая идея, по аналогии с скользящим средним, медленно-медленно «подтягивать» минимум к средним величинам, но отбрасывать его к фиксированным значениям, если полученный минимум станет меньше. Надо попробовать, насколько на практике такой метод будет работать и сравнить его с «честным» на большой машине.
Прикреплённые файлы:
 
 55

GOGI

координатор
★★★★
Так контроллер-то какой с датчика сигнал снимает.
Учитывая погрешность сенсора, вряд ли его сигнал имеет больше одного полезного байта.
Соответственно, чтобы иметь возможность, смотреть среднее, минимальное, максимальное за 100 секунд, тебе надо 10 байт на окно, чтобы за последние 1000 секунд еще плюс 10 байт и так далее. Ну что у тебя, 40 байт памяти не найдется в контроллере? Самое мелкое, с чем я работал - Attiny45, там и то 128 байт ОЗУ.
1  61.061.0

Balancer

администратор
★★★★★
GOGI> Учитывая погрешность сенсора, вряд ли его сигнал имеет больше одного полезного байта.

Значения 0…1023 :) А если нормализовать, то как раз минимум нужно знать. Тупо загрублять же, отбрасывая младшие 2 бита — грубо выходит.

GOGI> Соответственно, чтобы иметь возможность, смотреть среднее, минимальное, максимальное за 100 секунд

Мне нужно за сутки, лучше — за неделю :)

GOGI> тебе надо 10 байт на окно, чтобы за последние 1000 секунд еще плюс 10 байт и так далее. Ну что у тебя, 40 байт памяти не найдется в контроллере?

И сенсора — 4. Так что в лоб надо, скажем, 4*7*86400/10 = ~236кБайт. Можно как-то прореживать, хранить N последних, а уже из них минимум и максимум записывать в следующие, более грубые секции — это тот же RRD вручную получается. Сложно, криво…

Плюс это не единственный способ применения. Например, данные пишутся в MQTT. Это простой key-value. В случае потоковой записи я могу подписаться на изменения ключа, читать среднее/минимальное, высчитывать новое и писать изменённый ключ. Автоматически идёт накопление статистики без потери данных на перезагрузках и т.п. Можно, конечно, в MQTT хранить по ключу сразу сериализованный массив, но жирно будет гонять туда/сюда каждый десяток секунд десятки (как минимум) килобайт сериализованных данных.
 55
RU Alehandro #07.09.2018 22:09  @Balancer#07.09.2018 20:22
+
-
edit
 

Alehandro

новичок

Balancer> Вот первая идея, по аналогии с скользящим средним, медленно-медленно «подтягивать» минимум к средним величина...

Здесь надо рассматривать не просто точки максимума и минимума, а точки локального максимума и минимума. Такие вещи ющутся через производные. Поэтому я бы контролировал момент смены знака градиента величины. Если меняется с + на - максимум, с - на + минимум. Чтобы не хватать всякие нанолокальные изменения величины градиент тоже надо усреднить. Как-то так
 68.0.3440.9168.0.3440.91
RU Balancer #07.09.2018 22:24  @Alehandro#07.09.2018 22:09
+
-
edit
 

Balancer

администратор
★★★★★
Alehandro> Здесь надо рассматривать не просто точки максимума и минимума, а точки локального максимума и минимума. Такие вещи ющутся через производные.

Давай потоковый метод вычисления производных без массивов :)
 55
RU Alehandro #07.09.2018 23:34  @Balancer#07.09.2018 22:24
+
-
edit
 

Alehandro

новичок

Alehandro>> Здесь надо рассматривать не просто точки максимума и минимума, а точки локального максимума и минимума. Такие вещи ющутся через производные.
Balancer> Давай потоковый метод вычисления производных без массивов :)


X'(i)=X(i) - X(i-1)
где X'(i) - значение i-го отчета производной 
X(i) - значение i-го отчета измеряемой величины
X(i-1) - значение i-1-го отчета измеряемой величины

Не совсем производная с точки зрения математики, но в твоей ситуации должно хватить. Для вычисления локального минимума и максимума надо знать 3 величины X'(i),X'(i-1), X(i-1). Чтобы во всякие локальные впадины не соваться, вместо X(i) - можно взять не саму измеряемую величину, а ее скользящее среднее (надо экспериментировать). Как я понял с вычислением скользящего среднего у тебя проблем нет.
 64.0.3282.11964.0.3282.119
RU Balancer #08.09.2018 00:42  @Alehandro#07.09.2018 23:34
+
-
edit
 

Balancer

администратор
★★★★★
Alehandro> Для вычисления локального минимума …

Кстати. Стоп. Мне минимум как раз не локальный нужен, а глобальный (на условном большом отрезке — неделя, например, 50 тыс. отсчётов) :)

Локальных минимумов у меня итак будет каждый день десяток…
 55

PSS

литератор
★★
Balancer>

Храним минимум и время. Получая очередной локальный минимум проверяем сколько прошло времени и если больше недели, теперь его ставим в качестве основного.

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

Можно придумать варианты когда он пропустит минимум но в реальных условиях алгоритм будет работать и нужно будет хранить только две переменных.
История "Планеты Бурь" http://shubinpavel.ru/  55
RU Alehandro #08.09.2018 07:27  @Balancer#08.09.2018 00:42
+
-
edit
 

Alehandro

новичок

Alehandro>> Для вычисления локального минимума …
Balancer> Кстати. Стоп. Мне минимум как раз не локальный нужен, а глобальный (на условном большом отрезке — неделя, например, 50 тыс. отсчётов) :)
Balancer> Локальных минимумов у меня итак будет каждый день десяток…

Если рассматривать отрезок, точки экстремумов легко на концы отрезка лечь могут, что неправильно. Возьми локальность в пределах недели - кто мешает, шаг крупнее делай, при расчете производной бери например каждый сотый отчет, остальные херь. Или выкидывай младшие биты как GOGI предложил. Нулевые значения производной тоже выкидывай. Тебе же грубо говоря переворот производной ловить надо, а не абсолютное значение. Если есть дамп с отчетами, неплохо бы озвученные идеи в матлабе проверить прежде чем в железо код заливать.
 64.0.3282.11964.0.3282.119

Balancer

администратор
★★★★★
PSS> Храним минимум и время.

Нет единого времени.
 55
RU Balancer #08.09.2018 12:20  @Alehandro#08.09.2018 07:27
+
-
edit
 

Balancer

администратор
★★★★★
Alehandro> Если рассматривать отрезок, точки экстремумов легко на концы отрезка лечь могут, что неправильно.

Что ж тут неправильного? Если минимум был точно неделю назад, на границе отрезка, то он минимумом быть не перестаёт :)

Alehandro> Возьми локальность в пределах недели - кто мешает, шаг крупнее делай

Какой шаг? У меня нет массива данных. Есть только текущие значения. Ну и максимум 1-2 переменных.

Alehandro> Тебе же грубо говоря переворот производной ловить надо, а не абсолютное значение

Переворот производной — это локальный минимум :) Таких по десятку и больше в день будет. Сотня в неделю.

Alehandro> Если есть дамп с отчетами, неплохо бы озвученные идеи в матлабе проверить прежде чем в железо код заливать.

Да я, один фиг, на MQTT сперва тестировать буду :)
 55
EE Татарин #08.09.2018 12:52  @Balancer#07.09.2018 09:25
+
-
edit
 

Татарин

координатор
★★★★☆

Balancer> А вот как аналогично считать минимальные и максимальные значения за период? Как считать минимум и максимум за всю историю — понятно, обычное условие. Но если данные имеют склонность «сдвигаться», то найденное максимальное и минимальное значение через какое-то время будут уже не актуальны.
Храни порядковый номер отсчёта для максимума и минимума. Когда максимум(минимум) покинут окно известной истории, пересчитай максимум(минимум).
100% корректный и универсальный способ, а дополнительные расходы вычмощи невелики, потому что такой пересчёт - редкое событие. И чем больше окно, тем больше расходы вычмощи, но и реже событие.

Вариация на эту тему - хранить и поддерживать стек максимумов и минимумов с участками неубывания/невозрастания отсчётов на случай пересчёта.
...А неубитые медведи делили чьи-то шкуры с шумом. Боюсь, мы поздно осознали, к чему всё это приведёт.  68.0.3440.10668.0.3440.106
Это сообщение редактировалось 08.09.2018 в 12:58
RU Balancer #08.09.2018 12:58  @Татарин#08.09.2018 12:52
+
-
edit
 

Balancer

администратор
★★★★★
Татарин> Когда максимум(минимум) покинут окно известной истории, пересчитай максимум(минимум).

Пересчитать из чего? Ловить первый попавшийся минимум? :)



Но идея может сработать, если хранить, например, пару минимумов за два последних периода (хоть пусть и неделя последняя и неделя перед ней). Тогда по переполнению числа отсчётов просто переписываем последний минимум в предыдущий («глобальный») и начинаем считать последний минимум заново.
 55
EE Татарин #08.09.2018 13:04  @Balancer#08.09.2018 12:58
+
-
edit
 

Татарин

координатор
★★★★☆

Татарин>> Когда максимум(минимум) покинут окно известной истории, пересчитай максимум(минимум).
Balancer> Пересчитать из чего? Ловить первый попавшийся минимум? :)
Ты совсем не хранишь отсчёты?

Balancer> Но идея может сработать, если хранить, например, пару минимумов за два последних периода (хоть пусть и неделя последняя и неделя перед ней). Тогда по переполнению числа отсчётов просто переписываем последний минимум в предыдущий («глобальный») и начинаем считать последний минимум заново.
Да, стек минимумов, стек максимумов.
...А неубитые медведи делили чьи-то шкуры с шумом. Боюсь, мы поздно осознали, к чему всё это приведёт.  68.0.3440.10668.0.3440.106
RU Alehandro #08.09.2018 14:11  @Balancer#08.09.2018 12:20
+
-
edit
 

Alehandro

новичок

Alehandro>> Если рассматривать отрезок, точки экстремумов легко на концы отрезка лечь могут, что неправильно.
Balancer> Что ж тут неправильного? Если минимум был точно неделю назад, на границе отрезка, то он минимумом быть не перестаёт :)

И зависит от разбиения на отрезки, что не правильно. Начало отрезка при старте только нужно, чтобы было отчего отталкиваться.

Alehandro>> Возьми локальность в пределах недели - кто мешает, шаг крупнее делай

Balancer> Какой шаг? У меня нет массива данных. Есть только текущие значения. Ну и максимум 1-2 переменных.

Шаг - разность индексов величин, которые для расчета используются. Бери каждый сотый отчет. Что ты берешь каждый сотый, что каждый первый - для расчета производной требуется помнить предыдущее значение: в одном случае это будет X(i-99), в другом X(i-1) - одна переменная, а не массив значений.

Alehandro>> Тебе же грубо говоря переворот производной ловить надо, а не абсолютное значение
Balancer> Переворот производной — это локальный минимум :) Таких по десятку и больше в день будет. Сотня в неделю.

Переворот производной — это локальный экстремум: локальный минимум или максимум. Ну и ворота для значений и индексов используй - насколько значение (или индекс) нового экстремума от текущего будет отличатся чтобы новое значение текущим стало - азы теории управления.
Единственный косяк может возникнуть - если измеряемая величина - монотонная функция, но в это слабо верится.

Если не хочешь с производными заморачиваться - используй значение и номер отчета, как Татарин предлагает.

Если концентрация газа часто падает до 0, можно взять два скользящих средних, один с большим, другой с меньшим шагом. Среднее с большим шагом будет соответствовать R0, с меньшим R.
 64.0.3282.11964.0.3282.119

PSS

литератор
★★
PSS>> Храним минимум и время.
Balancer> Нет единого времени.

Добавить его. В еще одну переменную. Есть же у считывания данных определенный период.
История "Планеты Бурь" http://shubinpavel.ru/  55
RU Balancer #08.09.2018 16:07  @Татарин#08.09.2018 13:04
+
-
edit
 

Balancer

администратор
★★★★★
Татарин> Ты совсем не хранишь отсчёты?

Конечно. Потому и тема, как считать статистику без хранения данных :)

Татарин> Да, стек минимумов, стек максимумов.

Только не стек, а очередь :)
 55

GOGI

координатор
★★★★
Balancer> Конечно. Потому и тема, как считать статистику без хранения данных :)
Я так понял ты на ESP платах делаешь? Имея сколько там, 50 кБ ОЗУ и несколько мегабит SPI flash, жаловаться что памяти нет?!!
1  62.062.0

Balancer

администратор
★★★★★
GOGI> Я так понял ты на ESP платах делаешь?

Не только. Например, данные у меня собирает Arduino Nano (банально т.к. в ESP только один канал АЦП), а ESP только ретранслирует. А возможен вариант с ретрансляцией по nRF24L01. И «вычисления» статистики на MQTT-хуках.

GOGI> и несколько мегабит SPI flash

Ресурс по циклам записи у ESP не так велик, там тысяч 10 циклов. Если каждые 10 секунд обновляться, то чуть больше, чем через сутки ресурс кончится :) Но, да, оперативки свободной килобайт до 10 можно, наверное, выкроить :) Но это — частный случай.
 55

в начало страницы | новое
 
Поиск
Настройки
Твиттер сайта
Статистика
Рейтинг@Mail.ru