Прошу совета.
Какие существуют методы определения подобия кривых, заданных в виде временного ряда.
Делал попытки решить задачу с помощью нейропрограммы, однако получается сложно.
Как эта задача решается обычными математическими методами. Была сделана программа сравнения соответствующих значений кривых с контролем на допуск и подсчётом количества совпадений в качестве критерия подобия.
Какие способы определения подобия известны ещё? Особенно, если временные ряды имеют сильные отскоки, или подобие не сильно выражено. Помогите с литературой по этому вопросу.Хотелось бы получить общее представление.
[email protected]

Попробуйте аппроксимацию полиномом N-ой степени (от 3 до 5), с подгонкой к-тов полинома нейронной сетью обратного распространения. У меня была курсовая работа на эту тему.

P.S. не прокатит при большом кол-ве изгибов в графике.

Цитата

Какие существуют методы определения подобия кривых, заданных в виде временного ряда.

Вопрос лежит еще глубже: какие (физические) объекты моделируют эти кривые. Отсюда - какие выбрать критерии подобия. Затем уже методы.
Добавлено @ 09:41

Цитата(mr @ 6.10.2005, 08:26)

Попробуйте аппроксимацию полиномом N-ой степени

В таких делах бывают "неувязочки". Например, для бесконечной синусоиды понадобится полином бесконечной степени Один-два периода синусоиды смоделировать полиномом - не очень большая проблема, а больше?

Цитата

Как эта задача решается обычными математическими методами. Была сделана программа сравнения соответствующих значений кривых с контролем на допуск и подсчётом количества совпадений в качестве критерия подобия.

Не совсем ясно, сравниваются две кривые? Тоды есть один метод, существующий в радиотехнике (сначала аналоговой, а потом цифровой) уже многие десятилетия. Я ж его "рядом" описАл:

http://forum.vingrad.ru/index.php?showtopic=62047

Если же идет, речь о самоподобии по-типу фракталов, то нужно подумать.

Вообще-то корреляционный метод довольно фундаментален, находит применение в алгоритмах видеосжатия, системах распознавания образов, некоторых методах спектрального анализа, радиотехнических методах фильтрации/детектирования (особенно сложных комплексных сигналов при низком соотношении сигнал/шум) и т.д. и т.п. Если бы существовал более надежный метод, думаю, он бы давно вытеснил корреляционный. Причем он (корреляционный) абсолютно не сложен, если в него вдуматься. Правда может я его недоходчиво изложил , что вполне может быть. Доходчивее чем в книжке Юкио Сато "Обработка сигналов. Первое знакомство" Москва, "Додека", 2002 год, 176 страниц я пояснения этого метода не встречал. Книжка есть и в электронном (DjVu) виде, но че-то не закачивается :

http://dsp-book.narod.ru/biblio.htm

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

Цитата

Если бы существовал более надежный метод, думаю, он бы давно вытеснил корреляционный

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

Цитата(mr @ 6.10.2005, 07:26)

Попробуйте аппроксимацию полиномом N-ой степени (от 3 до 5), с подгонкой к-тов полинома нейронной сетью обратного распространения. У меня была курсовая работа на эту тему. P.S. не прокатит при большом кол-ве изгибов в графике.

Спасибо за помощь. Действительно аппроксимация полиномом даёт некоторый образ временного ряда. Я это пробовал вручную в Exel и есть программа в Интернете.
Как оценить степень подобия для двух временнх рядов по их аппроксимациям, что можно взять за критерий?

Параметры для оценки подобия исходных временных рядов, которые интересны в первую очередь: тренд, точки перегиба и их сдвиг по времени относительно друг друга...

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

Цитата(maxim1000 @ 7.10.2005, 11:49)

...для других задач хороши другие методы...

Какие другие методы можете предложить для моей задачи (с учётом 2-го сообщения)? Спасибо.

Цитата

Какие другие методы можете предложить для моей задачи (с учётом 2-го сообщения)? Спасибо

никаких, т.к. это

Цитата

Второй ряд - реализация исследуемого процесса, шума нет

не описание процесса

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

To:maxim1000

Так давайте по-порядку:

Цитата(maxim1000 @ 7.10.2005, 11:49)

есть куча задач по сравнению чего-либо

На скале познания я не стоЮ так высоко что бы кого-то чему-то учить. Пока с радостью учусь сам. Поэтому если вы приведете мне примеры других методов эффективного сравнения/распознавания функций, я с радостью перейму опыт, тем более что обработка сигналов - мое хобби (интересуюсь буквально всем в этой области, от аналоговой схемотехники, до алгоритмов и методов ЦОС) и люблю я всему находить практическую реализацию. Но все-таки мне кажется, не напрасно этот метод получил огромнейшее распространение, и рассматривается в радиотехнических учебниках в теории оптимального приема. По-сути коррелятор - оптимальный радиоприемник. И стоИт он сейчас во всех цифровых военных линиях связи, в той или иной форме. И линии эти рассчитаны на работу в условиях "навязанных" помех довольно таки отличающихся от Гауссо-Марковского "белого шума". Правда там секрет в самом сигнале, но я уже не туда забрел. Причем корреляционный метод запросто подходит для одно-, двух-, трех- ... N-мерных случаев. Основное-то достоинство метода, что он дает однозначный числовой критерий "подобия" функций. А не какой-нибудь вектор или полином которые, в свою очередь, необходимо анализировать.

Цитата(maxim1000 @ 7.10.2005, 11:49)

корреляционный метод хорош, когда помеха является аддитивной (возможно, еще какие-то ограничения)

Тяжело возразить, тем более я уже немножко возразил выше, но в "нашем" случае сигнал то вообще не зашумлен !

Цитата(maxim1000 @ 7.10.2005, 11:49)

уже от случайных повторений или пропусков он не спасет...

тяжело прокомментировать, так как я не понял, что Вы имели ввиду.

Цитата(maxim1000 @ 7.10.2005, 14:07)

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

Математического ( и вероятностного) описания процесса нет.
По сути процесса можно привести аналогию с измерением температуры на улице градусником. Например в течение суток смотрим каждые 5 мин. на градусник и фиксируем значение. При этом градусник исправен, глаз (или датчик) не ошибается, т.е. считаем, что всё идеально, помех и шума нет. Таким образом получаем 2 -й временной ряд. Теперь требуется выбрать метод для определения степени подобия с модельной кривой. Хотелось бы знать, какие методы есть, чтобы не изобретать велосипед.

To:учч

Цитата

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

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

Цитата

Параметры для оценки подобия исходных временных рядов, которые интересны в первую очередь: тренд, точки перегиба и их сдвиг по времени относительно друг друга...

С этим - туже. Надо подумать.

Цитата

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

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

Цитата

Поэтому если вы приведете мне примеры других методов эффективного сравнения/распознавания функций

Цитата

тяжело прокомментировать, так как я не понял, что Вы имели ввиду

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

НО: есть еще один вид искажений - мы слишком слабо нажали на клавишу или случайно попали сразу по двум

получаем:
alskdjfi
aslskdjfi
во-первых, у них разная длина, что уже создает проблемы для применения побуквенного сравнивания
во-вторых, даже если мы обрежем кусок сигнала, проблемы это не решит
разница между этими последовательностями будет просто ужасно большой
хотя они, несомненно, похожи

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

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

Цитата

Теперь требуется выбрать метод для определения степени подобия с модельной кривой

вотв том-то и вопрос: что считать подобным?
можно сравнивать средние значения - например, чтобы приблизительно определить время года
можно сравнивать форму кривой - горб или впадина - например, чтобы отличать ночь от дня

как это делалось для речи:
человек произносил одно и то же слово
а исследователи смотрели, какие отличия получаются

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

Цитата(DRUID3 @ 7.10.2005, 20:24)

To:учч Цитата Один из рядов является моделью и генерируется математически из программы. Второй ряд - реализация исследуемого процесса, шума нет. Т.о. решается задача оценки подобия модели и реализации за один и тот же отрезок времени. Вообще-то все реализации по форме удаётся свести ~ к 8 типам и такого знания было бы достаточно для работы со всем множеством имеющихся рядов. М.б. эта задача из области распознавания образов? Настаивать не буду, но обратите пристальное внимание на мой скромный совет. Корреляционный метод не даром нашел такое распространение, можно сказать - он фундаментален. Вы о нем прочитайте и подумайте немного, так просто понимание не приходит, но поверьте, время напрасно не потеряете. Основные доводы - у Вас точно определен период, т.е. снято основное ограничение метода и есть эталонная ("ведущая") функция, действительно задача близка к распознаванию образов, вычислительные трудности правда остаются... Цитата Параметры для оценки подобия исходных временных рядов, которые интересны в первую очередь: тренд, точки перегиба и их сдвиг по времени относительно друг друга... С этим - туже. Надо подумать.

Какие расчёты могут проводится при распознавании образов, для двух временных рядов с использованием корреляционного метода, где об этом почитать?

To:учч

Цитата

Какие расчёты могут проводится при распознавании образов, для двух временных рядов с использованием корреляционного метода, где об этом почитать?

http://forum.vingrad.ru/index.php?showtopic=62047

Скалярное произведение N-мерных вектороФФ. ( {a,b}=a1*b1+a2*b2+a3*b3+...+aN*bN ) И их "модули" - абсолютные длинны. ( ||a|| = sqrt( a1*a1 + a2*a2+a3*a3+...+aN*aN) ), де aN - (в Вашем случае) отсчет функции в такой то момент времени, т.е. один член временного ряда. Там все написано. С этими "модулями" должны быть хитрые финты ушами, быстрые sqrt() можно и на форуме поискать, но кто-то когда-то что-то мне рассказывал о "модулях" векторов и матрицах (или просто массивах???), очень при этом размахивая руками. Руки запомнил - суть нет. Я Вам еще на мыло кое-что брошу.