Как найти пики в наборе данных?

47

Если у меня есть набор данных, который создает график, подобный следующему, как бы я алгоритмически определил значения x показанных пиков (в данном случае три из них):

введите описание изображения здесь

nonaxiomatic
источник
13
Я вижу шесть локальных максимумов. На какие три вы ссылаетесь? :-). (Конечно, это очевидно - суть моего замечания - побудить вас более точно определить «пик», потому что это ключ к созданию хорошего алгоритма.)
whuber
3
Если данные представляют собой чисто периодические временные ряды с добавлением некоторого случайного компонента шума, вы можете использовать функцию гармонической регрессии, где период и амплитуда - это параметры, которые оцениваются по данным. Получившаяся модель будет гладкой периодической функцией (то есть функцией нескольких синусов и косинусов) и, следовательно, будет иметь уникально идентифицируемые моменты времени, когда первая производная равна нулю, а вторая производная отрицательна. Это были бы пики. Места, где первая производная равна нулю, а вторая производная положительна, будут тем, что мы называем впадинами.
Майкл Черник
2
Я добавил метку режима, ознакомьтесь с некоторыми из этих вопросов, у них будут интересные ответы.
Энди W
Спасибо всем за ваши ответы и комментарии, это очень ценится! Мне потребуется некоторое время, чтобы понять и реализовать предложенные алгоритмы в том, что касается моих данных, но я обязательно сделаю обновление позже с обратной связью.
неаксиоматичный
Может быть, это потому, что мои данные действительно шумные, но у меня не получилось с ответом ниже. Тем не менее, у меня был успех с этим ответом: stackoverflow.com/a/16350373/84873
Даниэль

Ответы:

36

Общий подход состоит в том, чтобы сгладить данные и затем найти пики, сравнивая локальный максимальный фильтр с сглаживанием . В R:

argmax <- function(x, y, w=1, ...) {
  require(zoo)
  n <- length(y)
  y.smooth <- loess(y ~ x, ...)$fitted
  y.max <- rollapply(zoo(y.smooth), 2*w+1, max, align="center")
  delta <- y.max - y.smooth[-c(1:w, n+1-1:w)]
  i.max <- which(delta <= 0) + w
  list(x=x[i.max], i=i.max, y.hat=y.smooth)
}

Его возвращаемое значение включает в себя аргументы локальных максимумов ( x), которые отвечают на вопрос, и индексы в массивы x и y, где встречаются эти локальные максимумы ( i).

Есть два параметра, которые нужно настроить в зависимости от обстоятельств: w это полуширина окна, используемая для вычисления локального максимума. (Его значение должно быть существенно меньше, чем половина длины массива данных.) Маленькие значения улавливают крошечные локальные выпуклости, тогда как большие значения будут проходить прямо над ними. Другой - не явный в этом коде - spanаргумент loessсглаживателя. (Как правило, он находится между нулем и единицей; он отражает ширину окна как пропорцию диапазона значений x.) Большие значения сгладят данные более агрессивно, в результате чего локальные неровности исчезнут вообще.

Чтобы увидеть эту настройку в действии, давайте создадим небольшую тестовую функцию для отображения результатов:

test <- function(w, span) {
  peaks <- argmax(x, y, w=w, span=span)

  plot(x, y, cex=0.75, col="Gray", main=paste("w = ", w, ", span = ", span, sep=""))
  lines(x, peaks$y.hat,  lwd=2) #$
  y.min <- min(y)
  sapply(peaks$i, function(i) lines(c(x[i],x[i]), c(y.min, peaks$y.hat[i]),
         col="Red", lty=2))
  points(x[peaks$i], peaks$y.hat[peaks$i], col="Red", pch=19, cex=1.25)
}

Вот несколько экспериментов, примененных к некоторым синтетическим, слегка зашумленным данным.

x <- 1:1000 / 100 - 5
y <- exp(abs(x)/20) * sin(2 * x + (x/5)^2) + cos(10*x) / 5 + rnorm(length(x), sd=0.05)
par(mfrow=c(3,1))
test(2, 0.05)
test(30, 0.05)
test(2, 0.2)

Сюжеты

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

Обратите внимание, что локальные максимумы в конечных точках не обнаружены. Они могут быть проверены отдельно. (Для поддержки argmaxвозвращает сглаженные значения y.)


Этот подход имеет несколько преимуществ перед более формальным моделированием для работы общего назначения:

  • Он не принимает какую-либо предвзятую модель данных.

  • Это может быть адаптировано к характеристикам данных.

  • Он может быть адаптирован для обнаружения интересующих нас видов пиков.

Whuber
источник
3
Напротив, @Michael: я ничего не предполагаю о периодичности. Действительно, пример выглядит периодическим, но это не так: обратите внимание на квадратичный член. Гармоническая регрессия потерпит неудачу в этом примере (и во многих других подобных сериях). Более того, я не выбираю ничего «визуально»: все это делается с помощью алгоритма. (Почему у меня создается сильное впечатление, что вы на самом деле не читали этот ответ?)
whuber
1
Я могу найти пики алгоритмически через первый и второй производные тесты, тогда как вам нужно использовать некоторые другие средства (возможно, что-то вроде числового поиска). Я не хотел пытаться утверждать, что один подход лучше другого, и я не критиковал ваш ответ вообще. Я просто вижу много сходств и различий, и я пытался получить более четкое представление о том, как вы идентифицируете свои пики.
Майкл Черник
3
O(n)
4
@ Майкл, если у вас нет «времени», чтобы прочитать ответ / комментарий, то вы можете воздержаться от ответа на / делать утверждения о посте. Это то, что вы делали неоднократно, и это часто приводит к неконструктивным обменам и / или неправильным заявлениям, которые вы позже отрекаетесь. Это кажется пустой тратой вашего времени и других, с кем вы вступаете в такие разговоры. Например, вся эта цепочка комментариев наверняка заняла больше времени, чем просто чтение ответа. Почему вы решили использовать сайт таким образом, продолжает меня озадачивать. Я не понимаю, как это может кому-нибудь помочь.
Макрос
2
Спасибо за интересный подход. Я думаю, что я также понял, чего достиг Майкл: вам нужно было просмотреть графики, чтобы определить наилучшие значения для wи span, а также обнаружить, что более высокие значения spanсмещают пики. Такое чувство, что даже эти шаги могут быть автоматизированы. Например, для первого выпуска, если бы мы могли оценить качество обнаруженных пиков, мы могли бы работать optimizeпо параметрам! Для второй проблемы, например, выберите окно по обе стороны от обнаруженного пика и ищите более высокие значения.
Даррен Кук
1

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

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

Майкл Черник
источник
2
Не могли бы вы продемонстрировать «эффективную манеру» вашего подхода? Часть задачи состоит в том, чтобы разработать алгоритм для поиска нескольких пиков - что в вашем случае означает поиск всех нулей (дорогостоящих вычислений) производной, а не только одного нуля, - и точно указать, какую из этих критических точек вы классифицируете как "пики", а какие нет. Кроме того, некоторая поддержка или усиление вашего утверждения о том, что «параметрический подход лучше, когда параметрические предположения являются подходящими», было бы хорошо, поскольку, как мы все знаем, параметрические предположения никогда не бывают абсолютно правильными.
whuber
@whuber Я сказал, что вы бы подходили модели тогда, так как модель представляет собой сумму синусов и косинусов, функция периодическая, пики возникают, когда первая производная равна нулю, а вторая производная в нулевой точке уменьшается. Вот что я имел в виду, когда сказал, что вы берете первый и второй производные тесты. Теперь вы можете решить, чтобы найти все решения, но если у вас есть один пик, то другие - один период и несколько периодов от решения, которое у вас есть. Моя точка зрения не в том, чтобы претендовать на какое-либо превосходство метода. Я просто хочу отметить, что бесплатного обеда не существует.
Майкл Черник
Непараметрические методы имеют то преимущество, что не требуют предположения моделирования, в этом случае нет предположения периодичности. Мое утверждение о том, что параметрические подходы лучше непараметрических, когда верны предположения моделирования, должно быть вам хорошо знакомо. Мне не нужно спорить о параметрических предположениях, которые никогда не выполняются точно. Это мнение, с которым я в принципе согласен. Но я говорю о чем-то вроде эффективности Питмана. Непараметрические оценки не так эффективны, как параметрические оценки, когда модель «правильная».
Майкл Черник
Это теория. На практике параметрические модели могут быть хорошим приближением к реальности. В этом случае параметрическая оценка (скажем, mle) является более эффективной, чем непараметрическая оценка. Также параметрические доверительные интервалы будут лучше, потому что они будут более узкими. Но часто вы не знаете, насколько хороша параметрическая модель для вашего примера. В таких случаях вам приходится выбирать между консервативностью (безопасностью) с непараметрическим подходом или смелостью (и, возможно, ошибкой) с использованием параметрического подхода.
Майкл Черник
1
Майкл, я пытаюсь предположить, что в этом случае непараметрический подход, вероятно, будет намного лучше, чем любой параметрический подход, за исключением тех случаев, когда данные особенно тесно связаны с моделью - и даже тогда он будет работать хорошо. Предположим, что периодичность является отличным примером: ваш алгоритм будет делать ошибки того же порядка, что и отклонения от периодичности в данных. Возможность совершать такие ошибки сводит на нет любые преимущества, связанные с большей асимптотической эффективностью. Использование такой процедуры без проведения обширного тестирования GoF было бы плохой идеей.
whuber
1

Классический подход обнаружения пиков в обработке сигналов заключается в следующем:

  1. Отфильтруйте сигнал до некоторого разумного разумного диапазона, в зависимости от частоты дискретизации и свойств сигнала, например, для ЭКГ, полосового фильтра IIR при 0,5-20 Гц, фильтр нулевой фазы обеспечит отсутствие сдвига фазы (и связанной временной задержки)
  2. Гильбертово преобразование или вейвлет-подход можно использовать для выделения пиков.
  3. Затем может быть применен статический или динамический порог, где все выборки выше порога считаются пиками. В случае динамического порога он обычно определяется как пороговое значение N стандартных отклонений выше или ниже оценки среднего скользящего среднего.

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

Надеюсь это поможет.

BGreene
источник