Обнаружение шагов

Примеры сигналов, которые могут содержать шаги, искаженные шумом. (a) Соотношения числа копий ДНК из данных микрочипов , (b) интенсивность космических лучей из нейтронного монитора , (c) скорость вращения жгутикового двигателя R. Sphaeroides в зависимости от времени , и (d) интенсивность красных пикселей из одной строки сканирования цифрового изображения.

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

Проблема обнаружения шагов возникает в различных научных и инженерных контекстах, например, в статистическом управлении процессами ^[1] ( контрольная карта является наиболее непосредственно связанным методом), в разведочной геофизике (где проблема заключается в сегментации записи каротажа скважины на стратиграфические зоны ^[2] ), в генетике (проблема разделения данных микроматрицы на схожие режимы числа копий ^[3] ), и в биофизике (обнаружение переходов состояний в молекулярной машине , как записано в трассах времени-позиции ^[4] ). Для 2D-сигналов связанная проблема обнаружения границ интенсивно изучалась для обработки изображений . ^[5]

Алгоритмы

Когда обнаружение шага должно выполняться по мере поступления данных, обычно используются онлайн-алгоритмы , ^[6] и это становится частным случаем последовательного анализа . Такие алгоритмы включают классический метод CUSUM, применяемый к изменениям среднего. ^[7]

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

Сверху вниз

Эти алгоритмы начинаются с предположения, что шагов нет, и вводят возможные шаги-кандидаты по одному за раз, проверяя каждого кандидата, чтобы найти тот, который минимизирует некоторые критерии (например, наименьшее квадратичное соответствие оценочного, базового кусочно-постоянного сигнала). Примером является алгоритм пошагового размещения прыжков , впервые изученный в геофизических задачах, ^[2] , который недавно нашел применение в современной биофизике. ^[8]

Вверх дном

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

Раздвижное окно

Рассматривая небольшое «окно» сигнала, эти алгоритмы ищут доказательства наличия шага в пределах окна. Окно «скользит» по временному ряду, по одному шагу за раз. Доказательства наличия шага проверяются статистическими процедурами, например, с помощью двухвыборочного t-критерия Стьюдента . В качестве альтернативы к сигналу применяется нелинейный фильтр , такой как медианный фильтр . Такие фильтры пытаются удалить шум, сохраняя при этом резкие шаги.

Глобальный

Глобальные алгоритмы рассматривают весь сигнал за один раз и пытаются найти шаги в сигнале с помощью некоторой процедуры оптимизации. Алгоритмы включают в себя методы вейвлетов ^[9] и полное вариационное шумоподавление , которое использует методы из выпуклой оптимизации . Если шаги можно смоделировать как цепь Маркова , то также часто используются скрытые марковские модели (популярный подход в сообществе биофизиков ^[10] ). Когда есть только несколько уникальных значений среднего, то также можно использовать кластеризацию k-средних .

Линейные и нелинейные методы обработки сигналов для обнаружения шагов

Поскольку шаги и (независимый) шум имеют теоретически бесконечную полосу пропускания и, таким образом, перекрываются в базисе Фурье , подходы обработки сигналов для обнаружения шагов обычно не используют классические методы сглаживания, такие как фильтр нижних частот . Вместо этого большинство алгоритмов явно нелинейны или изменяются во времени. ^[11]

Обнаружение шагов и кусочно-постоянные сигналы

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

Обнаружение шага как восстановление набора уровней

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

Обнаружение шага с помощью 0-градусной сплайновой подгонки

Многие алгоритмы явно подгоняют сплайны 0-й степени под зашумленный сигнал, чтобы обнаружить шаги (включая методы пошагового размещения прыжков ^{[2] [8]} ), но существуют и другие популярные алгоритмы, которые также можно рассматривать как методы подгонки сплайнов после некоторого преобразования, например, полного вариационного шумоподавления . ^[12]

Обобщенное обнаружение шага с помощью кусочно-постоянного шумоподавления

Все упомянутые выше алгоритмы имеют определенные преимущества и недостатки в конкретных обстоятельствах, однако, на удивление большое количество этих алгоритмов обнаружения шагов являются частными случаями более общего алгоритма. ^[11] Этот алгоритм включает минимизацию глобального функционала: ^[13]

Здесь x _i для i  = 1, ....,  N — это дискретный по времени входной сигнал длины N , а m _i — это выходной сигнал алгоритма. Цель состоит в том, чтобы минимизировать H [ m ] относительно выходного сигнала  m . Форма функции определяет конкретный алгоритм. Например, выбрав: ${\displaystyle \scriptstyle \Lambda }$

${\displaystyle \Lambda ={\frac {1}{2}}\left|x_{i}-m_{j}\right|^{2}I(i-j=0)+\gamma \left|m_{i}-m_{j}\right|I(i-j=1)}$

где I ( S ) = 0, если условие S ложно, и единица в противном случае, получаем алгоритм шумоподавления полной вариации с параметром регуляризации . Аналогично: ${\displaystyle \gamma }$

${\displaystyle \Lambda =\min \left\{{\frac {1}{2}}\left|m_{i}-m_{j}\right|^{2},W\right\}}$

приводит к алгоритму среднего сдвига при использовании адаптивного шагового интегратора Эйлера, инициализированного входным сигналом  x . ^[13] Здесь W  > 0 — параметр, определяющий поддержку ядра среднего сдвига. Другой пример:

${\displaystyle \Lambda ={\frac {1-\exp(-\beta |m_{i}-m_{j}|^{2}/2)}{\beta }}\cdot I(|i-j|\leq W)}$

что приводит к двустороннему фильтру , где — параметр тонального ядра, а W — поддержка пространственного ядра. Еще один особый случай: ${\displaystyle \scriptstyle \beta >0}$

${\displaystyle \Lambda ={\frac {1}{2}}\left|x_{i}-m_{j}\right|^{2}I(i-j=0)+\gamma \left|m_{i}-m_{j}\right|^{0}I(i-j=1)}$

задание группы алгоритмов, которые пытаются жадно подогнать сплайны 0-й степени к сигналу. ^{[2] [8]} Здесь определяется как ноль, если x  = 0, и единица в противном случае. ${\displaystyle \scriptstyle \left|x\right|^{0}}$

Многие из функционалов в уравнении ( 1 ), определяемые конкретным выбором, являются выпуклыми : их можно минимизировать с помощью методов выпуклой оптимизации . Другие же являются невыпуклыми, но был разработан ряд алгоритмов для минимизации этих функционалов. ^[13] ${\displaystyle \scriptstyle \Lambda }$

Обнаружение шагов с использованием модели Поттса

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

${\displaystyle u^{*}=\arg \min _{u\in \mathbb {R} ^{N}}\gamma \|\nabla u\|_{0}+\|u-x\|_{p}^{p}}$

Член штрафует число скачков, а член измеряет точность данных x . Параметр γ > 0 управляет компромиссом между регулярностью и точностью данных . Поскольку минимизатор кусочно-постоянен, шаги задаются ненулевыми положениями градиента . Для и существуют быстрые алгоритмы, которые дают точное решение задачи Поттса в . ^{[14] [15] [16] [17]} ${\displaystyle \|\nabla u\|_{0}=\#\{i:u_{i}\neq u_{i+1}\}}$ ${\displaystyle \|u-x\|_{p}^{p}=\sum _{i=1}^{N}|u_{i}-x_{i}|^{p}}$ ${\displaystyle u^{*}}$ ${\displaystyle \nabla u^{*}}$ ${\displaystyle p=2}$ ${\displaystyle p=1}$ ${\displaystyle O(N^{2})}$

Смотрите также

• Сегментация временных рядов

Ссылки

1. ES Page (1955). «Тест на изменение параметра, происходящее в неизвестной точке». Biometrika . 42 (3–4): 523–527. doi :10.1093/biomet/42.3-4.523. hdl : 10338.dmlcz/103435 .
2. Gill, D. (1970). «Применение метода статистической зональности для оценки резервуара и анализа оцифрованных каротажных диаграмм». Бюллетень Американской ассоциации геологов-нефтяников . 54 : 719–729. doi :10.1306/5d25ca35-16c1-11d7-8645000102c1865d.
3. Снайдерс, AM; и др. (2001). «Сборка микрочипов для измерения числа копий ДНК по всему геному». Nature Genetics . 29 (3): 263–264. doi :10.1038/ng754. PMID  11687795. S2CID  19460203.
4. Sowa, Y.; Rowe, AD; Leake, MC; Yakushi, T.; Homma, M.; Ishijima, A.; Berry, RM (2005). «Прямое наблюдение шагов вращения бактериального жгутикового двигателя». Nature . 437 (7060): 916–919. Bibcode :2005Natur.437..916S. doi :10.1038/nature04003. PMID  16208378. S2CID  262329024.
5. Серра, Дж. П. (1982). Анализ изображений и математическая морфология . Лондон; Нью-Йорк: Academic Press.
6. Бассвиль, М.; И. В. Никифоров (1993). Обнаружение резких изменений: теория и применение . Prentice Hall.
7. Родионов, С.Н., 2005a: Краткий обзор методов обнаружения смены режима. ссылка на PDF в: Крупномасштабные нарушения (смена режима) и восстановление водных экосистем: проблемы управления в направлении устойчивости, В. Великова и Н. Чипев (ред.), Семинар ЮНЕСКО-РОСТЕ/БАС по смене режима, 14–16 июня 2005 г., Варна, Болгария, 17–24.
8. Kerssemakers, JWJ; Munteanu, EL; Laan, L.; Noetzel, TL; Janson, ME; Dogterom, M. (2006). "Динамика сборки микротрубочек при молекулярном разрешении". Nature . 442 (7103): 709–712. Bibcode :2006Natur.442..709K. doi :10.1038/nature04928. PMID  16799566. S2CID  4359681.
9. Маллат, С.; Хванг, В. Л. (1992). «Обнаружение сингулярности и обработка с помощью вейвлетов». Труды IEEE по теории информации . 38 (2): 617–643. CiteSeerX 10.1.1.36.5153 . doi :10.1109/18.119727. 
10. МакКинни, СА; Джу, К.; Ха, Т. (2006). «Анализ траекторий FRET одиночной молекулы с использованием скрытого марковского моделирования». Biophysical Journal . 91 (5): 1941–1951. Bibcode :2006BpJ....91.1941M. doi :10.1529/biophysj.106.082487. PMC 1544307 . PMID  16766620. 
11. Little, MA; Jones, NS (2011). «Обобщенные методы и решатели для удаления шума из кусочно-постоянных сигналов: Часть I. Фоновая теория». Труды Королевского общества A . 467 (2135): 3088–3114. Bibcode :2011RSPSA.467.3088L. doi :10.1098/rspa.2010.0671. PMC 3191861 . PMID  22003312. 
12. Чан, Д.; Т. Чан (2003). «Сохраняющие края и зависящие от масштаба свойства регуляризации полной вариации». Обратные задачи . 19 (6): S165–S187. Bibcode :2003InvPr..19S.165S. doi :10.1088/0266-5611/19/6/059. S2CID  30704800.
13. Mrazek, P.; Weickert, J.; Bruhn, A. (2006). "О надежной оценке и сглаживании с пространственными и тональными ядрами". Геометрические свойства для неполных данных . Берлин, Германия: Springer.
14. Мамфорд, Д. и Шах, Дж. (1989). Оптимальные приближения кусочно-гладкими функциями и связанные с ними вариационные задачи. Сообщения по чистой и прикладной математике, 42(5), 577-685.
15. Винклер, Г.; Либшер, В. (2002). «Сглаживатели для прерывистых сигналов». Журнал непараметрической статистики . 14 (1–2): 203–222. doi :10.1080/10485250211388. S2CID  119562495.
16. Фридрих и др. (2008). «M-оценка со штрафом за сложность: быстрое вычисление». Журнал вычислительной и графической статистики . 17 (1): 201–224. doi : 10.1198/106186008x285591. S2CID  117951377.
17. А. Вайнманн, М. Сторат, Л. Демарет. « Функционал -Поттса для надежной реконструкции скачкообразных разреженных множеств». Журнал SIAM по численному анализу, 53(1):644-673 (2015). ${\displaystyle L^{1}}$

Внешние ссылки

• PWCTools: гибкое программное обеспечение Matlab и Python для обнаружения шагов с помощью кусочно-постоянного шумоподавления
• Pottslab: набор инструментов Matlab для кусочно-постоянной оценки на основе модели Поттса