Сглаживание функции

[SYROTENKO]

Добрый день Ув. Форумчане!
Хотел бы услышать, как бы Вы решили такую проблемму.

Есть набор точек записанных в таблицу, кот. состоит из 16*10^6 строчек. Стоит задача найти минимум ф-ции.
В силу того, что каждая точка в силу измерений имеет погрешность, то нужно для начала сгладить какой-нибуть ф-цией эти точки и затем найти минимум.

Как можно построить аппроксимирущую ф-цию для такого кол-ва точек? Существуют ли какие-нибуть методы?


Большое спасибо за ответы!

[Yuri Gendelman]

Ваша функция имеет один локальный минимум или много (2, 3, а фиг его знает)? Можете ли Вы на основании анализа Вашего массива 16000000 точек выделить области, где стоит искать минимум?

Когда области поиска выделены (м.б. только одна область из всех точек), я бы посоветовал применить для каждой области интерполяционные сплайны.

Проблема еще в том, что если у функции много _локальных_ минимумов, то найденное значение _глобального_ минимума может негладко зависеть от заданной погрешности интерполяции: при изменении погрешности вычисленный глобальный минимум будет "перескакивать" из окрестности одного локального минимума в окрестность другого.

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

[незваный гость]

Сплайн. Только не интерполяционный, а сглаживающий.

Алььтернатива — какой-нибудь сглаживающий фильтр (например — сглаживание по 5-7 точкам) и прямой поиск. Этот метод дает ответ худшего качества, но очень быстро.

[SYROTENKO]

Yuri Gendelman писал(а):

Ваша функция имеет один локальный минимум или много (2, 3, а фиг его знает)? Можете ли Вы на основании анализа Вашего массива 16000000 точек выделить области, где стоит искать минимум?

Когда области поиска выделены (м.б. только одна область из всех точек), я бы посоветовал применить для каждой области интерполяционные сплайны.

Проблема еще в том, что если у функции много _локальных_ минимумов, то найденное значение _глобального_ минимума может негладко зависеть от заданной погрешности интерполяции: при изменении погрешности вычисленный глобальный минимум будет "перескакивать" из окрестности одного локального минимума в окрестность другого.

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

Спасибо за ответ!
Мне нужно найти глобальный минимум. Кол-во локальных не известно.
Могу ли я выделить область, где буду искать локальный минимум, сложно сказть. Я не знаю как это сдалать. Да и вобще задача найти глобальный минимум, а не локальные.
Почему вы везде употребляете слово интерполяция, а не аппроксимация?
Ведь нужно сгаживать данные, в силу того, что точки расположены не точно (есть погрешность измерений), Т.е. нам не нужно, чтобы наша ф-циия проходила через эти точки, а только их сглаживала. Т.е. нужно аппроксимировать их.

[незваный гость]

SYROTENKO писал(а):

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

За один проход массива можно найти точку глобального минимума и максимума зашумленных данных. Возьмите области, в которые Вы находитесь в 10% от минимума. Это позволит резко сократить объем обрабаттываемых данных.

Заметьте, что это — эвристика. И, как таковая, требует настройки. Например, Вы можете получить много одно-двух точечных фрагментов. Это должно нсторожить — скорее всего, шум составляет порядка 10% диапазона сигнала. Один из выходов — всегда расширять выбранную область на, например, 10 точек в каждую сторону.

И еще. Имейте в виду, что как только Вы сказали сглаживание, так сразу у Вас результат потерял «абсолютную» правильность. Поскольку он существенно зависит от алгоритма сглаживания.

[SYROTENKO]

незваный гость писал(а):

:evil:
Сплайн. Только не интерполяционный, а сглаживающий.

Алььтернатива — какой-нибудь сглаживающий фильтр (например — сглаживание по 5-7 точкам) и прямой поиск. Этот метод дает ответ худшего качества, но очень быстро.

Огромнейшее спасибо за ответ!
Очень хотелось бы услышать от Вас, что такое сглаживающий фильтр и можно ли его применять в моём случае. Был бы очень благодарен, если бы дали какую-нибуть ссылку, которая помогла бы мне разобратся с этим.

Еще раз спасибо.

[незваный гость]

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

Вообще, теория фильтров обширна и богата. Развилась она в последние годы в связи с обработкой сигналов на компах (DSP, digital signal processing). По коим ключевым словам и надо гуглать.

Добавлено спустя 1 минуту 26 секунд:

Мне кажется, что тема уместнее в Computer Science. Куда и переношу. // нг

[SYROTENKO]

незваный гость писал(а):

И еще. Имейте в виду, что как только Вы сказали сглаживание, так сразу у Вас результат потерял «абсолютную» правильность. Поскольку он существенно зависит от алгоритма сглаживания.

А что, есть способ найти минимум "Абсолютно" правильно, без сглаживания ? Моя задача найти максимально точно минимум ф-ции заданной таблично набором точек. Но учитывая, что все точки имеют погрешность измеерний их необходимо сгладить (аппроксимировать). Или может быть я ошибась?

[незваный гость]

Без сглаживания, Вы можете пройти по массиву данных и найти минимальную точку. И этот результат не зависит от метода. Как только Вы начинаете сглаживать, Ваш результат может очень сильно меняться в зависимости от алгоритма сглаживания, который Вы используете (теряется независимость результата от метода).

[SYROTENKO]

незваный гость писал(а):

:evil:
Без сглаживания, Вы можете пройти по массиву данных и найти минимальную точку. И этот результат не зависит от метода. Как только Вы начинаете сглаживать, Ваш результат может очень сильно меняться в зависимости от алгоритма сглаживания, который Вы используете (теряется независимость результата от метода).

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

Спасибо!

[незваный гость]

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

Я уже обрисовал свой подход:

1) если надо очень быстро, подобрал бы сглаживающий фильтр. И использовал бы результаты фильтрации для поиска минимума, например, по трем точкам (проводя через них параболу).

2) Если есть время, выделил бы области потенциального минимума. В каждой из таких областей построил бы сглаживающий сплайн, и искал бы его минимумы. Этот метод медленнее, зато дает несколько более точный результат.

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

[G^a]

Добречко!

SYROTENKO писал(а):

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

А Вам нужен минимум в исходном сигнале, или в наблюдаемом? Если в наблюдаемом, то ничего фильтровать не надо, а если в исходном, то...

Раз Вы хотите метрологически корректно и достоверно, то для начала вопросы:
1) У Вас одна реализация временного ряда, или несколько?
2) Присутствуют только случайные ошибки измерения, или систематические тоже есть?
3) Какое распределение имеет шум измерения, и каковы его параметры?
4) Шум измерения аддитивен, или мультипликативен?
5) Возможны ли отдельные выбросы (артефакты) при измерении или нет? Другими словами, присутствует ли импульсная помеха?
6) Каковы параметры оцифровки сигнала (разрядность АЦП, темп опроса)?
7) Есть ли априорная модель сигнала, или нет?
8) Какова граничная частота в полезном сигнале?
9) Можно ли пренебречь дрейфом характеристик измерителя при получении наблюдаемой реализации?

Это для начала!
После этого можно сформировать модель наблюдателя. И изучив апостериорные параметры измерительного шума и априорные исходного сигнала, можно приступать к процедуре выбора фильтра.

Успехов!

[PAV]

Маленький вопрос - от скольких аргументов функция?

[SYROTENKO]

PAV писал(а):

Маленький вопрос - от скольких аргументов функция?

У меня функция 5-ти аргументов