Мера близости последовательностей на основе взаимной корреляции Опции

[roman73_2]

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

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

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

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

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

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

[Xenia]

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

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

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

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

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

[roman73_2]

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

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

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

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

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

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

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

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

[Dr.Alex]

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

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

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