Хочется научиться находить участки, которые на глаз кажутся "впадинами" и "пиками".
Пик, наверное, можно считать "пройденным" как только "миновали вершину".
Когда считать считать "состоявшейся" впадину, я не знаю.
Наверное, пики не обязательно точно перемежаются со впадинами.
Сформулировать формальнее я не смогу.
Попробовал два наивных подхода: (1) сглаживать и оценивать знак кривизны и наклон касательной; (2) двигать два окна и сранивать минимумы, максимумы и "децили".
Результат работы перешагивает уровень минимальных хотелок (даже половина пропущенных событий вполне пойдет), но реализация самобытная, колхозная и мало "устойчивая". Особенно в части учета того, что масштаб и длины участвков могут быть разные.
Буду благодарен за ключевые слова по которым гуглить готовые известные и надежные подходы.
Спасибо.
N>Я для подобного использую алгоритм Дугласа-Пекера (Рамера-Дугласа-Пекера)
Мне он в голову не пришел, потому что не вся линия сразу доступна, вместо этого она "поступает" по точкам.
И остается вопрос с тем, когда останавливать спрямление.
Вероятно, в момент, когда спрямтся "лишее" (пик соединится с дальнй точкой впадины), резко возрастет "площадь" ошибки.
Осталось определить, что значит резко , но может что и выйдет.
Спасибо!
Здравствуйте, ylem, Вы писали:
Y>И остается вопрос с тем, когда останавливать спрямление. Y>Вероятно, в момент, когда спрямтся "лишее" (пик соединится с дальнй точкой впадины), резко возрастет "площадь" ошибки. Y>Осталось определить, что значит резко , но может что и выйдет.
Обычно есть какая-то априорная информация о погрешности или о том, сколько экстремумов надо получить в итоге. От этого и пляшут.
Есть и более современные методы — Largest Triangle Three Buckets (теория и реализация на куче языков).
Здравствуйте, ylem, Вы писали:
Y>На ходу постуют числовые вещественные значения... Хочется научиться находить участки, которые на глаз кажутся "впадинами" и "пиками".
Не поверишь, уже довольно давно грызу похожую тему, только задача как бы обратная. Тебе нужно обнаружить среди тенденции резко выпадающее из нее значение, а мне наоборот, среди последовательности сплошных "пиков" выделить тенденцию. И мне также трудно сформулировать, что мне в точности надо.
В твоем случае я бы использовал пошаговое усреднение. Берем сумму n последовательных значений, предположим, их будет сотня. При поступлении нового из суммы отнимаем самое "старое", новое добавляем. Делим на 100, сравниваем с предыдущим усреднением. Если отклонение +10%, поймали "пик". Или, если -10%, то впадину. Значение пика не учитывается в будущих усреднениях.
Использованные значения "100", "10%" — настраиваемые параметры конфигурации. "Я вижу пик — но почему я считаю это пиком?" Потому что значение пика изменило текущее пошаговое среднее из 100 значений на 10%. Субъективная это штука — "вижу пик". А кто-то, глядя с будущей вершины, предположит, что это норка суслика.
Здравствуйте, ravik, Вы писали:
R>Не поверишь, уже довольно давно грызу похожую тему, только задача как бы обратная. Тебе нужно обнаружить среди тенденции резко выпадающее из нее значение, а мне наоборот, среди последовательности сплошных "пиков" выделить тенденцию. И мне также трудно сформулировать, что мне в точности надо.
Построить линейную (полиномиальную) регрессию методом наименьших квадратов?
R>В твоем случае я бы использовал пошаговое усреднение. Берем сумму n последовательных значений, предположим, их будет сотня. При поступлении нового из суммы отнимаем самое "старое", новое добавляем. Делим на 100, сравниваем с предыдущим усреднением. Если отклонение > 10%, поймали "пик". Или, если < 10%, то впадину. Значение пика не учитывается в будущих усреднениях.
Лучше перейти в более подходящую терминологию случайных процессов. Твой метод подразумевает, что на некотором небольшом участке мы имеем стационарный случайный процесс. Отклонение — это что? Среднеквадратичное отклонение? Если перейти в правильную терминологию, то ты считаешь, что на участке 100 измерений у нас стационарный случайный процесс, мы находим его статистические характеристики: среднее и среднеквадратичное отклонение. Далее формализуем 10%: по факту нас интересует расстояние Махаланобиса, которое показывает с какой вероятностью новое измерение принадлежит текущему (полученному за 100 прошлых тактов). Расстояние Махаланобиса в данном случае считается по формуле: abs(M — x) / sigma < eps, где M — мат. ожидание, x — новое измерение, sigma — среднеквадратичное отклонение, eps — некоторая константа эпсилон, полученная из даблицы интегральной функции Лапласа (таблица гуглится, значения надо удваивать). Вот eps как раз и подбирается по таблице исходя из вероятностного порога.
Что делать, если у нас ряд не стационарный, то есть на искомом интервале у нас характеристики процесса (матожидание и дисперсия) могут резко меняться? Очевидно, что резкое падение вниз или вверх всё испортят.
В этом случае есть несколько путей:
1. Сделать ряд стационарным! Например, найти линейный тренд (построить линейную регрессию), вычесть её значения из ряда и работать с ним по предыдущему алгоритму.
2. Если тренда постоянного нет или он может резко меняться, то надо использовать нелинейную регрессию или детектировать изменение тренда.
3. Можно вместо твоего метода (moving average по сути), использовать экспоненциальное сглаживание для среднего и отклонения (низкочастотный фильтр). В таком случае нам не надо хранить 100 значений, а только последнее и с некоторой константой alpha = [0; 1] обновлять статистики при приходе каждого измерения. В данном случае в зависимости от alpha система будет быстрее реагировать на нестационарность процесса.
Выглядит рабочим вариантом, хорошие мысли. Надеюсь, топикстартеру помогут. "Мой" метод из давнишней практики разработок АСУТП, и все-таки предназначался в основном для сглаживания флуктуаций сигналов.
Но применительно к моей задаче решения уравнений вида 2(x^2 + x) — 1/2(y^2 + y) = N не очевидно, какие статистические методы срабатывают. Я пытаюсь определить множество частных решений. Например, одно сразу бросается в глаза при 2x = y, что позволяет покрыть 99,9...% траектории частными решений вида kx = y. Но, к сожалению, оставшийся пусть и относительно небольшой участок (при достижении k некоего критического значения) сводит на нет предыдущие усилия. Вот над ним (над участком) я и корплю. Пока даже не понятно, какого вида соотношения здесь следует ожидать.
Здравствуйте, ylem, Вы писали:
Y>На ходу постуют числовые вещественные значения. Y>График выглядит примерно так: http://files.rsdn.org/66566/Img.png
Y>Масштаб значений меняется, но меняется медленно.
Y>Хочется научиться находить участки, которые на глаз кажутся "впадинами" и "пиками". Y>Пик, наверное, можно считать "пройденным" как только "миновали вершину". Y>Когда считать считать "состоявшейся" впадину, я не знаю.
Y>Наверное, пики не обязательно точно перемежаются со впадинами.
Y>Сформулировать формальнее я не смогу.
Y>Попробовал два наивных подхода: (1) сглаживать и оценивать знак кривизны и наклон касательной; (2) двигать два окна и сранивать минимумы, максимумы и "децили". Y>Результат работы перешагивает уровень минимальных хотелок (даже половина пропущенных событий вполне пойдет), но реализация самобытная, колхозная и мало "устойчивая". Особенно в части учета того, что масштаб и длины участвков могут быть разные.
Y>Буду благодарен за ключевые слова по которым гуглить готовые известные и надежные подходы. Y>Спасибо.
интегрирование/дифференцирование
анализ функций
анализ роста (перепадов)
как минимум нужно это сгладить. Я бы предложил фильтр Калмана попробовать, после анализировать.
Соберите несколько примерных данных, сгладьте до приемлемого результата, а дальше dy/dt
Здравствуйте, ylem, Вы писали:
Y>На ходу постуют числовые вещественные значения. Y>График выглядит примерно так: http://files.rsdn.org/66566/Img.png
Y>Масштаб значений меняется, но меняется медленно.
Y>Хочется научиться находить участки, которые на глаз кажутся "впадинами" и "пиками".
Вот тут прежде всего проблема. "На глаз" — это для глаза хорошо. И то, что одному глазу хорошо, другому — не очень. Для алгоритма придется формулировать.
Y>Пик, наверное, можно считать "пройденным" как только "миновали вершину".
Это неверно уже исходя из доступной формулировки. Требуется находить участки, а вершина — это лишь точка на участке. И за этой точкой может быть еще одна вершина, еще выше, чем прежняя. А для того, что бы проверить, хорош ли участок с N вершинами на нем, уже нужна точная формулировка. Y>Когда считать считать "состоявшейся" впадину, я не знаю.
С этим проще. Отзеркалить формулировку с участком пика, когда с ним будет понятно.
Y>Наверное, пики не обязательно точно перемежаются со впадинами.
Это зависит от формулировки. Ведь вполне может оказаться, что участок с пиком будет пересекаться со впадиной. типа такого. И это еще не коснулись масштаба.
-----\/\/\/----
Y>Сформулировать формальнее я не смогу.
Надо. Как искать то, не знаю, что? Так даже невозможно формально проверить, является ли конкретный участок пиком или впадиной. И какого масштаба/окрестности?
может быть более ясно будет, если сформулировать исходную задачу, или для чего эти пики нужны?
Тут явно постановка задача из области "сделай мне то, о чём я думаю", я бы посоветовал формализировать задачу, тогда и алгоритм быстро найдётся. Если промежуток значений фиксированный, то можно обучить самую обычную модель на основе нормального распределения и определять пики/впадины, сравнивая каждое следующее значение с N-ым перцентилем.
1) попробуй так —
а) напиши программу генерирующую последовательность сигнала максимально похожую в твоем интуитивном смысле на образец!
(!) в программе координаты точки пиков долны фигурировать как параметры (!)
б) подбирай параметры генератора сигнала по наименьшей суммарной ошибке по отношению к образцу
2) предлагаю если ты сам не можешь определиться что такое пик — такую формулировку —
пик в отрезке сигнала по оси Х от Х[0] до Х[N] это это отрезок значительно меньшей длинны К, где К << N
где сосредоточено скажем > 50% энергии сигнала всего отрезка от Х[0] до Х[N]
(причем короткий отрезок не упирается в границы длинного отрезка, т.к. пик может быть точно на границах или в данном отрезке его вообще нет
и он находится в соседнем отрезке)- в РЛС это метод Пик-фактор.
3) прочитай про вероятности правильного обнаружения, вероятность ложного обнаружения, вероятность пропуска правильного сигнала,
вероятность правильного НЕ обнаружения. Обычно эти вероятности отношении пиков сигнала подробно рассматриваются в учебниках по радиолокации.
4) или еще такой интуитивный не оптимальный, но реально работающий метод, може быть не очень хорошо.
1) находим максимум на отрезке анализа, это пик N1
2) обнуляем все отсчеты некоторой окрестности этого пика и запоминаем координаты найденного пика и его тоже обнуляем.
3) снова ищем максимум на всем отрезке и находим пик N2
4) go to 2)
НО на границах отрезка надо что-то "нахимичить"
Здравствуйте, ylem, Вы писали:
Y>Буду благодарен за ключевые слова по которым гуглить готовые известные и надежные подходы.
Стандартная задача — решается путем применения не запаздывающего фильтра низких частот с последующем вычитанием выходы фильтра из сигнала.
В описании решения опущены детали, например результат разницы возможно надо будет "привести" или "нормализовать", то есть получить безразмерную величину, тогда уровни начала "максимумов" можно выставлять в диапазоне от 0 до 1, а не в величине сигнала.
Чтобы получить такой подобный сигнал генерируйте случайное число и прибавляйте его к предидущему значению. )
То есть чтобы вы не делали с непрерывной слуайной величиной, вы все равно в итоге вы получите случайное распределение событий. Только распределение будет другое — например бернулли или с другое распределение для временных событий. )
Здравствуйте, ylem, Вы писали:
Y>На ходу постуют числовые вещественные значения. Y>График выглядит примерно так: http://files.rsdn.org/66566/Img.png
Y>Масштаб значений меняется, но меняется медленно.
Y>Хочется научиться находить участки, которые на глаз кажутся "впадинами" и "пиками".
I>Стандартная задача — решается путем применения не запаздывающего фильтра низких частот с последующем вычитанием выходы фильтра из сигнала.
спектр пиков и не пиков вполне может быть одинаков и фильтрация как по НЧ так и по ВЧ а также и оптимальная или
согласованная фильтрация только ухудшит обнаружение.
I>Чтобы получить такой подобный сигнал генерируйте случайное число и прибавляйте его к предидущему значению. )
нет, это простой ФНЧ, больших острых пиков редких так не получить если их не было в исходной случайной последовательности.
Я бы предложил "проигрывать" много раз по интервалу генерации сигнала
массив с записанной формой пика в рандомное время с рандомной амплитудой и несколько проигрываний типа истинные пики с сильно увеличенной
тоже рандомной амплитудой и временем начала проигрывания.
P>4) или еще такой интуитивный не оптимальный, но реально работающий метод, може быть не очень хорошо.
Это же вроде жадного алгоритма?
В планах попробовать (это хобби, времени есть не всегда) просто последовательно обнулять самые в каком-нибудь смысле маленькие неровности,
пока не останется пиков или сколько мне нужно, или только пики из каких-нибудь самых верхних перцентилей изначального распределения.
Про учебники по радиолокации и ложно положительные и ложно отрицательные определения отдельное спасибо.
Жаль, что у меня приоритеты, явно, не те: меня устроит пропустить половину сигналов, но очень нежелательны ложные срабатываения
R>Не поверишь, уже довольно давно грызу похожую тему, только задача как бы обратная. Тебе нужно обнаружить среди тенденции резко выпадающее из нее значение, а мне наоборот, среди последовательности сплошных "пиков" выделить тенденцию. И мне также трудно сформулировать, что мне в точности надо.
, но может что и выйдет.
