Сопоставление сигналов

[allchemist]

Всем привет.

Имеются два произвольных дискретных сигнала равной длины, предварительно очищенных от шумов. Пытаюсь придумать метод определения их похожести друг на друга.
Например, два этих куска сигнала:

должны быть ощутимо более похожи, чем эти два:


В таком виде это эффективно решается банальными способами типа отцентрировать и отнормировать каждый сигнал и посчитать скалярное произведение.
Но при этом сигналы:

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

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

Можно ли считать численными выражениями этих самых характерных признаков, скажем, значения каких-либо коэффициэнтов фурье- или вейвлет-преобразования? или пики частотных спектров?

Или может быть эта, в общем-то фундаментальная, задача уже давно решена и не нужно изобретать велосипеды?

[Pphantom]

allchemist в сообщении #901520 писал(а):

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

allchemist в сообщении #901520 писал(а):

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

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

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

[allchemist]

Pphantom в сообщении #901524 писал(а):

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

Некий вменяемый нормировочный порог я могу подобрать руками и смириться с этим.

Но что если есть две пары сигналов:


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

Это чисто в качестве примера.

[Pphantom]

allchemist в сообщении #901560 писал(а):

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

Надо попробовать, но, скорее всего, нет. Как раз из-за нормировки "более длинный хвост" превратится в обычный.

[_hum_]

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

[allchemist]

Pphantom в сообщении #901640 писал(а):

Надо попробовать, но, скорее всего, нет. Как раз из-за нормировки "более длинный хвост" превратится в обычный.

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

[Pphantom]

Можно сделать "нелинейную нормировку" - например, логарифмическую.

[allchemist]

_hum_ в сообщении #901666 писал(а):

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

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

-- Пт авг 29, 2014 20:16:02 --

Pphantom в сообщении #901816 писал(а):

Можно сделать "нелинейную нормировку" - например, логарифмическую.

Спасибо, хорошая идея.

[_hum_]

allchemist в сообщении #901819 писал(а):

без включения априорных сведений о задаче

без этого задача является некорректно поставленной.

allchemist в сообщении #901819 писал(а):

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

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

[allchemist]

_hum_ в сообщении #901850 писал(а):

без этого задача является некорректно поставленной.

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

allchemist в сообщении #901819 писал(а):

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

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

[arseniiv]

Ага, а есть ли они. И на движение курсора, кроме человека, влияют ещё, как минимум, мышка и поверхность, по которой ей водят.

[_hum_]

allchemist в сообщении #901909 писал(а):

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

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

[allchemist]

arseniiv в сообщении #901941 писал(а):

Ага, а есть ли они. И на движение курсора, кроме человека, влияют ещё, как минимум, мышка и поверхность, по которой ей водят.

Таки есть, и по мнению большинства исследователей, вполне уникальны для каждого человека, как почерк. (в англоязычной литературе это называется mouse dynamics)

-- Сб авг 30, 2014 09:44:38 --

_hum_ в сообщении #901945 писал(а):

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

Собстно, исследователи темы mouse dynamics так и делают - анализируют иинтергальные параметры типа кривизны траектории мыши. Очевидно, что львиная доля информации при этом теряется, ибо параметр интегральный.

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

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

[Pavia]

Один сигнал можно сравнить с другим бесконечным числом способов. И при этом получить разные результаты.
Для того чтобы можно было отобрать те или иные методы сравнения нужен критерий сравнения методов. Как правило таким критерием выступают данные о классах. Или другими словами классификация на примерах.
Но даже в этом случае методов сравнения очень много. И нужна метрика или методика. Эту методику можно найти в книгах или у экспертов. Либо же придется наугад пробовать разные методы и смотреть что получится. Отсеивая худшие.
Общего и единого подхода тут нет.
Хотя некоторые рекомендации вы можете найти.

По поводу кривизны. Кривизну можно считать как по всей кривой так и по её части. Если взять некоторый сегмент и его двигать с перекрытием, то у тебя получиться непрерывная функция.

[arseniiv]

allchemist в сообщении #901981 писал(а):

Очевидно, что львиная доля информации при этом теряется, ибо параметр интегральный.

Неочевидно. Возьмите какой-нибудь чистый шум и попытайтесь выделить оттуда эту львиную долю.

allchemist в сообщении #901981 писал(а):

Такого вроде еще никто не делал (по крайней мере, публично), поэтому как и любой "первопроходческий" эксперимент это выглядит крайне сомнительно. :)

Обычно эксперименты типа «а что будет, если смешать 81 разных веществ» не проводят, потому что результаты потом трудно разобрать. Может, лучше видвигать и проверять гипотезы о mouse dynamics по одной, и пытаться как-то их выводить из того, как рука способна двигаться, и других перечисленных непсихических причин? Тогда ведь можно оценить, где именно стоит искать неслучайность (а где явно будет шум; или что необходимо перед сбором движений (ну, например, если окажется, что трение о стол существенно — придётся к движениям как-то прикладывать данные о нём) фиксировать для получения какого-то результата)!

Кстати, ещё один отвлекающий фактор — настройки мыши в ОС (скорость движения указателя и двойного щелчка, если щелчки анализировать тоже).