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

[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. Или может я чего недопонял...
Я спрашиваю, как получить из взаимнокорреляционного полинома некоторую числовую меру сходства.

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

[Xenia]

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

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

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

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

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

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

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

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

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

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

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

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