Алгоритм обработки информации от датчиков (фильтрация помех)
Есть следующая задача.
У меня поступает информация от некоторых датчиков. Количество датчиков не фиксировано — они могут добавляться и исчезать, но у каждого в любом случае свой уникальный идентификатор. Информация поступает неравномерно во времени — то есть датчик может молчать неделю, а потом выдать два значения с интервалом в секунду а потом исчезнуть вообще; или же может внезапно появиться датчик, который будет регулярно присылать данные. Для простоты будем считать, что каждый датчик выдаёт значение из некоторого фиксированного набора значений — то есть датчики дискретны. Плюс к тому датчики приведены друг к другу = откалиброваны — то есть если любой датчик выдаёт А, то это А. Данные с датчиков пишутся в лог в формате (время, идентификатор, значение).
Задача заключается в фильтрации информации. Мне нужно из этого лога выбрать ОДНУ запись, которую я считаю текущей истиной. То есть, например, если я получаю свежую запись от одного датчика, что значение у меня А, но перед этим 10 датчиков говорили, что значение на самом деле Б, то истина на данный момент (!) это Б. Значения А-с-половиной быть не может — всё дискретно. Если дальше другие датчики начнут подтверждать, что да, всё-таки А, то со временем А станет истиной. В то же время задача не сводится к обычной фильтрации помех, потому что если был один датчик который твердил всю неделю каждую секунду, что значение = А, а тут появляются пять датчиков, которые совсем недавно говорят, что на самом деле значение Б, то истиной сразу становится Б, несмотря на всю историю — количество независимых источников тоже имеет вес, в общем.
То есть у меня получается некая функция двух переменных — время (устаревание информации) и количество уникальных датчиков в момент времени. И опять же всё усложняется тем, что я не могу перейти в дискретность — я не могу взять информацию за час и по ней делать выводы, потому что у меня инфа поступает неравномерно, и вся суть может находиться сразу за этим интервалом. Я дошёл в своих размышлениях до того, что здесь явно суть в том, что вес записи (а мне нужно будет в итоге просто выбрать запись у которой этот вес наибольший) зависит не только от значений в этой самой записи (времени и собственно значения), а и от значений в соседних записях. То есть таблицу нужно будет пройти по N раз для каждой из N записей. Ну, это я так думаю — я не утверждаю.
Я старался объяснить как можно более понятно, если что — задавайте любые уточнения — я буду отвечать. Данные пишутся в SQL базу, так что можно оперировать терминами SQL, если так удобней. Но в целом меня интересует сам алгоритм, реализацию я осилю.
P.S. Очень не исключаю, что на этот счёт есть готовый давно известный алгоритм…
Пляшите от медианы: придумайте какую-нибудь весовую функцию, которая бы «оценивала» удаленность от медианного значения совместно с устареванием. Из полученных результатов выбирайте максимум весовой функции. Как все эти алгоритмы вписываются в sql — понятия не имею. Я бы загрузил массивы (значение + таймстамп) в память и работал там ;)
Такое чувство, что простейший кворум с кучей эвристик тут самое оно. Или простое обучение на каком-то окне с выбором одного максимально правдоподобного датчика.
Можно посмотреть доклад про временные ряды с последнего YAC, там ищут различные всплески, провалы и перепады на графиках сильно упрощенным кросскорреляционным анализом, может натолкнет на что.
Реалтайм. Последние N отсчётов тоже могут быть не показательны, потому что там может быть N записей от одного датчика подряд, а потом за этим пределом будет 3 записи, но все от разных датчиков — в итоге они должны быть важней.
Обучение? Вряд ли. Подбор коэффициентов в формулу конечно будет. Ок, доклады гляну, спасибо!
