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

[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, то корреляция и будет лучшей "мерой".

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

[Дмитриос]

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

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

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

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

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



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

Сообщение отредактировал Дмитриос - Oct 15 2014, 18:56

[Dr.Alex]

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

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

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

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

[Дмитриос]

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

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

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

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

Сообщение отредактировал Дмитриос - Oct 16 2014, 15:18