Имеется набор точек (X_n, t_n).
(Зависимость величины X от времени t)
Надо постоить график X(t)
Проблема в том, что точек слишком много. Надо придумать эффективный алгоритм выброса точек, так чтобы вид графика не сильно изменился.

Слишком много - это сколько?

Алгоритм выбраковки зависит от того, как рассматривать сильно отличающиеся значения - как выбросы или как характерные особенности?

Кроме того, насколько сложна зависимость?
Быть может, по МНК можно подобрать простую двух-параметрическую зависимость и построить уже ее график.

Использовать полиномы.

Использовать вейвлеты.


А может так - провести медианное сглаживание, затем исключить соседние точки с повторяющиеся значениями.

.....

График - это зависимость количества компов в сетке от времени
За день накапливается много точек - они идут через каждые 3 секунды.
Примерный график тут:

МНК и другие приближения - это все неправильно. Вид зависимости неопределен. Интересно, какой степени должен быть полином, чтобы определить центральный минимум (приглядись внимательно к графику).

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

Как понимать:

Цитата

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

Цитата

Большие отклонения от плавающего среднего выбрасывать нельзя.

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

Но тогда:

Цитата

МНК и другие приближения - это все неправильно.

Почему? МНК как раз весьма чувствителен к большим отклонениям.

Далее:

Цитата

За день накапливается много точек - они идут через каждые 3 секунды

Если я правильно врубился в вопрос, нужен не алгоритм отбраковки точек, а способ отображения зависимости на длительном интервале времени.
В АСУ ТП с этим борются просто - простым усреднением на некотором временном интервале. Длительность этого интервала задается исходя из того, насколько подробный график надо нарисовать.
Экономисты борются еще хитрее (пожалуй, хитрее всех) - применяют графики дневные, часовые, минутные, "тиковые" и т.д., изображая такой временной период какой-нибудь фигурой (например, японская свечка), которая изображает значения в начале и конце временного интервала (часа, минуты и т.п.), а также максимальное и минимальное значения на том же интервале.

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

Цитата(Seti @ 18.12.2003, 21:57)

График - это зависимость количества компов в сетке от времени За день накапливается много точек - они идут через каждые 3 секунды. Примерный график тут: МНК и другие приближения - это все неправильно. Вид зависимости неопределен. Интересно, какой степени должен быть полином, чтобы определить центральный минимум (приглядись внимательно к графику). Надо не подгонять под теоретическую зависимость, а изображать фактические данные. Большие отклонения от плавающего среднего выбрасывать нельзя.

1) 20 в минуту, 1200 в час. Ну, скажем не так чтобы уж слишкм много. Вполне нормальное количество точек.

2) Картинку не вижу

3) Вам надо определиться, что конкретно Вы хотите делать, так как смысл графика - визуализация данных и
а) если речь идет только о картинке, то единственно правильный подход - усреднение точек за некоторый интервал времени, например за минуту.
б) если речь идет о компактной форме хранения, то это либо вейвлеты либо другие методы сжатия.
в) если речь идет об исследовании локальных особенностей поведения функции, то необходимо анализировать все точки, но узких интервалах. Кстати, для прогнозирования поведения функции по имеющимся данным возможно удачным решением станет применение нейронных сетей.
г) если необходимо искать глобальные минимумы/максимумы - либо по всем точкам, либо сперва по усредненномк интервалу найти нужный, в затем уточненный поиск в нем.
д) если использовать полином, то не обязательно, чтобы его степень совпадала с числом точек. Скорее это просто бессмысленно. Но такое использование полинома обязательно приведет к сглаживанию экспериментальной зависимости. А добиться этого можно разными способами. Каким именно? - Однозначного ответа нет и быть не может. Самый простой способ - эмпирически подобрать наиболее пригодный вариант.

Да, вот еще одна мысль - вдогонку:
А что, если отображать сразу две зависимости:
1я - усредненная
2я - резкие выбросы

В результате,
1) вместо одного большого массива имеем два маленьких, но без потери информации;
2) сама информация представленна доступно и наглядно;
3) легко проводить обработку;
4) легко решается задача анализа полученных зависимостей;
....

P.S. Принципы усреднения и определения информативных выбросов - на Ваше усмотрение.

Это сообщение отредактировал(а) remax - 20.12.2003, 14:24

Цитата

1) 20 в минуту, 1200 в час. Ну, скажем не так чтобы уж слишкм много. Вполне нормальное количество точек.

в день, за неделю, за месяц? выборка - несколько недель, возможно будет несколько месяцев.

Цитата

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

усреднение точек плохо вот чем: допустим в каком-то сегменте сети произошел перебой с электропитанием. При этом 20% компов оказались в offлайне. Это должно быть обязательно отражено на графике. Усреднение может привести к тому, что на графике эти 20% превратятся в 5%.
Хотя, конечно, 1 минута - это достаточно маленький промежуток времени (за это время компы не успеют перезагрузиться).

Цитата

2) Картинку не вижу

http://fastik3.narod.ru/online-day.JPG
обрати внимание на узкий минимум примерно в центре картинки.

Вы так и не ответили на вопрос: "Что именно требуется - просматривать, прогнозировать или реагировать на резкие изменения в реальном времени?"

Картинку посмотрел - судя по масштабу графика (1 деление - 1 час) то в районе 10 часов был примерно 10-15 минутный провал. Это очень продолжительно (в измерениях это не меньше 30). Исходя из этого и необходимо выбирать ширину базы фильтра.

p.s. Чтобы долго и много не говорить зря - намыль фрагмент массива, скажем как на картинке с 8 до 12 часов (или аналогичный). Я его покручу сам. Можно несколько разных.

s.p.s. А если сохронять все измерения в базе данных и вынимать из базы по запросу часть информации?

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

если основная задача все-таки вывести все это на экран, мне кажется, стоит за интервал усреднения взять промежуток времени, соответствующий одному пикселу, больше информации вывести все равно не получится

Цитата(remax @ 20.12.2003, 14:22)

Да, вот еще одна мысль - вдогонку: А что, если отображать сразу две зависимости: 1я - усредненная 2я - резкие выбросы В результате, 1) вместо одного большого массива имеем два маленьких, но без потери информации; 2) сама информация представленна доступно и наглядно; 3) легко проводить обработку; 4) легко решается задача анализа полученных зависимостей; .... P.S. Принципы усреднения и определения информативных выбросов - на Ваше усмотрение.

Так это почти сжатие с помощью дискретного вейвлет-преобразования:
1-я зависимость - это "аппроксимация" (низкочастотная составляющая)
2-я зависимость - "детали" (высокочастотный "дребезг").
Поскольку дискретное вейвлет-преобразование подразумевает предварительное прореживание исходной последовательности, то как 1-я, так и 2-я зависимости будут в два раза короче исходной. 2--ю по идее можно даже выкинуть.

Цитата

усреднение точек плохо вот чем: допустим в каком-то сегменте сети произошел перебой с электропитанием. При этом 20% компов оказались в offлайне. Это должно быть обязательно отражено на графике. Усреднение может привести к тому, что на графике эти 20% превратятся в 5%. Хотя, конечно, 1 минута - это достаточно маленький промежуток времени (за это время компы не успеют перезагрузиться).

Если это действительно так, то не нужны никакие усреднения.
Надо взять типы графиков, которые используются в анализе финансовых временных рядов. Лично я рекомендую "японские свечи". Они очень наглядны.



Одна свеча отражает характер процесса на выбранном временном интервале (минута, час, 4 часа, день и т.д.). Значения процесса, соответствующие началу и концу выбранного интервала времени, формируют тело свечи (прямоугольник). От тела свечи до максимального значения проводится тонкая линия (верхняя тень). Тонкая линия между телом свечи и минимумом образует нижнюю тень. Если значение начала больше значения окончания временного промежутка, то свечу закрашивают черным цветом. Таким образом, если на графике много идущих подряд белых свечей, то это означает, что с течением времени значение измеряемого параметра возрастает и наоборот.
Естественно, подробная информация о протекании процесса внутри одной свечи не отображается, но она и не теряется: чтобы заглянуть "внутрь" одной свечки просто выбирается другой масштаб и всё! А для построения одной свечи нужно из БД считать только 4 значения: начало, конец, максимум и минимум.

В результате получим что-то такое:



Это внутридневной график акций РАО ЕЭС, 5 ноября 2003 г.
Одна свеча = 10 минут.

Цитата

Вы так и не ответили на вопрос: "Что именно требуется - просматривать, прогнозировать или реагировать на резкие изменения в реальном времени?"

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

Цитата

в районе 10 часов был примерно 10-15 минутный провал. Это очень продолжительно (в измерениях это не меньше 30). Исходя из этого и необходимо выбирать ширину базы фильтра.

Это вполне мог быть двухминутный провал, если электричество отрубилось, а затем сразу включилось.
За 2 минуты компы успеют загрузиться. А еще мог вырубиться свитч - тогда даже 15 - секундной детализации надостаточно. Поэтому я и делаю точки так часто - через 3 секунды.

Цитата

s.p.s. А если сохронять все измерения в базе данных и вынимать из базы по запросу часть информации?

Пришли к самому началу. Какую именно часть?

Логи на другом компе, когда смогу, отправлю.