Есть две числовые последовательности (времянных ряда, одномерных сигнала и т.д.), с немного разной длиной.
Нужно придумать меру их сходства, например от 0 до 1.

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

Придумали эвристику на основе Левенштейна - цена замены - модуль разницы между сигналами. Как-то работает - но хочется сделать по науке

Натолкнился на статью в википедии по взаимной корреляции
https://ru.wikipedia.org/wiki/%D0%92%D0%B7%...%86%D0%B8%D1%8F

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

Заранее спасибо.

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

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

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

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

Вот не надо про гены и бинарные прошивки. Мне кажется я нормально описал задачу. Последовательности числовые, могут "немного" различаться масштабом (по x и/или по y), может быть сдвиг.


Спасибо, это уже ближе к телу. А формул не подкинете? Как в этом случае вычисляется сходство сдвинутых последовательностей, скалярное произведение? Или скреднеквадратичное отклонение?

Насколько я понял, элемент взаимнокорреляционного полинома (как и свёртки) складывается из многих элементов исходных последовательностей. И может быстро вычисляться через БПФ.
Вы кажется предлагаете какое-то попарное сравнение с перебором. Это не подходит. Сигнал может быть визуально сходен, но при попарном сравнении будет каша из-за разнице в масштабах по x. Или может я чего недопонял...
Я спрашиваю, как получить из взаимнокорреляционного полинома некоторую числовую меру сходства.

Другие идеи сравнения я не отметаю, но хотелось бы чего-нибудь математически обоснованного

"Мера сходства" зависит от статистики искажений ваших последовательностей.

Если (и только тогда!) искажение — это AWGN, то корреляция и будет лучшей "мерой".

Если статистика другая, то и "мера" должна быть другая, И ОНА ОБЯЗАТЕЛЬНО ЗАВИСИТ ОТ СТАТИСТИКИ!

Если отличие в масштабе по Y, то это совершенно нормально. А вот различие масштабов по Х - очень плохо. Плохо потому, что не позволяет сводить меру сходства к числу совпадений.

Вы напрасно отмахиваетесь от моих объяснений , полагая, что я говорю о чем-то, не имеющего отношения к вашей задаче. На самом деле это не так. Пусть с пример на генетических текстах вас расстроил , но я могу привести и более приземленный пример. Скажем текст книги в электронном формате, где каждая буква = байт = один элемент последовательности. И вот редактор добавляет в середину текста мягкий знак, который автор по ошибке пропустил. Спрашивается, какой мерой оценить изменение текста в процессе редактирования? Насколько сильно текст был модифицирован при редактировании? Если вы подумаете, то поймете, что эта задача сродни вашей, поскольку текст удлинился (на одну букву), и теперь приходится сравнивать между собой две последовательности разной длины (до и после редактирования).

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


Формула в Википедии в статье "Корреляция" (это там, дается выражение для r_XY=).
Но я полагаю, что счет будет быстрее, если сперва из каждой последовательности вычесть среднее, а потом нормировать на единицу. А уже с модифицированными таким образом последовательностями просто вычислять скалярное произведение. Алгебраически то на то и получится, зато не надо будет при каждом сдвиге перевычислять знаменатель.
А то, что я вам предложила - это поиск максимума "автокорреляционной функции". Про автокорреляционнаую функцию в Википедии тоже есть статья.
Только не забывайте мой пример с редактированием теста, т.к. иначе вы рискуете стать жертвой красоты формул.


Если у вас длина более короткой последовательности является целой степенью двойки, то тогда с БПФ может быть стоит возиться. Здесь главным является то, насколько одна из ваших последовательности короче другой. Ведь именно эта разность определяет число возможных сдвигов. И если они отличаются не более, чем на 50%, то связываться с БПФ смысла не имеет.


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


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

Иногда для сравнения последовательностей (например, двух звуковых сигналов), нахождения метрики (расстояния) и того, как правильно "растянуть" сигналы используется DTW http://en.wikipedia.org/wiki/Dynamic_time_warping

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

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

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

Да, неужели нельзя настроить АЦП при приёме второй последовательности, чтобы её частота совпала с первой ?
Тогда простейший кореллятор со сдвигами на +-N справится после приведения к 0 и нормализации -- только искать нужно минимум сумм каких-то разностей.
Или идёт непредсказуемое растяжение/сжатие аналогичных форм сигнала, которое не поддаётся регулировке, типа Киркорова несёт между октавами и громкостями, но общая противность должна остаться и определиться ?

Если применять ряды Фурье к эталонному и масштабированному текущему сигналам, у похожих (в принципе) сигналов могут быть похожие матрицы коэффициентов ?

Можно сэиплировать обоих на гораздо большей частоте, чем исходный сигнал, чтобы на каждую "волну" приходилось по несколько отсчётов, да легче было пересэмплировать без потери информации по Котельниковым причинам. Или коэффициент растяжения точно неизвестен и должен быть также выработан наружу, если найдётся подходящий перебором ?
На DSP и ПЛИС всё возможно, конечно, только нужны разумные ограничения. Хотелось бы "в студию" пару "жизненных" примеров, какие последовательности ТС считает схожими, а какие -- нет, если само существо задачи закрыто. Взгляд человека на график сразу ловит "оно -- не оно" ?

У нас алгоритмический народ любит использовать пирамиду масштабов -- с уменьшением ряда отсчётов в 2 раза последовательно много раз. Глобально тоже видно большие всплески, но искать на мелком масштабе эффективней, большое видится на расстоянии.

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

Я хз, ниразу не встречал его в русском варианте. Все обычно не парятся и просто пишут DTW

Всегда интересовался вопросом но не смог найти ответ в умных книжках, какая мера нужна если шум не AWGN, то есть обычно в радиочастотных книжках пишут -- типа шум белый и всё тут -- поэтому оптимальный фильтр или приём сигнала -- это корреляция с самим сигналом, а если шум не белый??
а например:
1. синусойда (но заранее не знаешь фазу, а частоту знаешь плюс минут 20 процентов)
2. или если шум это ШИМ-сигнал который эту синусойду должен генерировать?
3. обобщая или может упрощая -- что если шум в узком спектре, и накладывается на широкополосный сигнал, то есть сигнал -- все цвета радуги а шум -- какой то сигнал в жёлтой части?

Понятно, что можно увиличить соотношение С/Ш задавить фильтром полосу шума но вместе с полосой мы и сам полезный сигнал давим -- но если шум он не цветной, а имеет более-менее известную форму -- можно же как то априори зная не только что шум не белый, а имеет определённую форму, обойтись не фильтрами заграждаюшими, а каким то более полезным критерием?



подскажите ссылки или книжки пожалуйста....

Не могу, общий случай сложен и при этом далековат от практики.. :-))

Точно можно сказать одно:: если шум не AWGN, то оптимальный приёмник будет нелинейным (корреляционный приёмник, напротив, линеен).

А во всех трёх ваших случаях решение известно, называется обеляющий фильтр. Он работает примерно как вы и говорите - давит те места в спектре, где стоят помехи с высокой спектральной плотностью, давит вместе с сигналом, естественно. Но тем не менее приёмник на основе обеляющего фильтра является оптимальным для узкополосных помех + AWGN. Это доказано ещё Котельниковым в работе "Теория потенциальной помехоустойчивости"..

поиск в гугле по словам обеляющий фильтр / whitening filter

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

Спасибо за совет, однако хочется ещё подискутировать и предложить такой менее "сферическйи в ваккуме" пример: Умеется звуковая схема на которую воздействует помеха от сети, и мне доступен только её выход в котором присутвует полезный сигнал и сетевая помеха, могу ли я каким либо путём повысить соотношение С/Ш, ведь практически я могу подключится через резисторы к 220 вольтам и снимать сигнал с сети(в которой помимо 50 герцовой составляюшей есть ещё кратные гармоники а если двигатель асинхронный включён то и частота проскальзывания присутвует (45...49) герц.

1. То есть в случае с обеляюшим фильтром я вынужден вырезать 45...51 герц 100 герц 150 герц и так далее. Однако на практике есть конкретная информация о помехе. Некоторое пространство состояний которое вырезает обеляющий фильтр гораздо шире чем текущий сигнал помехи.

2. Лично мне, не очень опытному теоретику и практику, приходит на ум способ вычитания сигнала от розетки с каким-то коэффициентом и фазовым сдвигом -- сложный фильтр помехи который некоторой автоподстройкой узнаёт сдвиг фазы и амплитуду помехи и потом делает вычитание... то есть схема такая:
сигнал от разетки --> автоподстроечный фильтр --> вычитание входного сигнала и выхода фильтра --> схема обучения фильтра минимизурующая шум

Вообще это адаптивным фильтром делается, описано во многих книгах.

А можно побольше описания физики процесса? Что за задача? Почему у вас по времени есть искажения? Тогда может может ещё они не однородные?
Можете привести графики или лучше файл .mat с последовательностями

А можно побольше описания физики процесса? Что за задача? Почему у вас по времени есть искажения? Тогда может ещё они не однородные?
Можете привести графики или лучше файл .mat с последовательностями