algorithm - 实时时间序列数据中的峰值信号检测

Question

更新:迄今为止性能最好的算法is this one。

这个问题探索了用于检测实时时间序列数据中突然峰值的鲁棒算法。
考虑以下数据集:

Matlab格式的数据示例(但此问题与语言无关，而与算法有关):

p = [1 1 1.1 1 0.9 1 1 1.1 1 0.9 1 1.1 1 1 0.9 1 1 1.1 1 1 1 1 1.1 0.9 1 1.1 1 1 0.9, ...
     1 1.1 1 1 1.1 1 0.8 0.9 1 1.2 0.9 1 1 1.1 1.2 1 1.5 1 3 2 5 3 2 1 1 1 0.9 1 1, ... 
     3 2.6 4 3 3.2 2 1 1 0.8 4 4 2 2.5 1 1 1];

您可以清楚地看到有三个大峰和一些小峰。该数据集是问题所涉及的时间序列数据集类别的特定示例。此类数据集具有两个常规功能:

有基本的噪音，一般意思是

有很大的“峰值”或“较高的数据点”，它们与噪声有很大的偏差。

我们还假设以下内容:

无法事先确定峰的宽度

峰高明显不同于其他值

所使用的算法必须计算实时性(因此对每个新数据点进行更改)

对于这种情况，需要构造一个触发信号的边界值。但是，边界值不能是静态的，必须根据算法实时确定。

我的问题:一种实时计算此类阈值的好的算法是什么？ 有针对这种情况的特定算法吗？什么是最著名的算法？

鲁棒的算法或有用的见解都受到高度赞赏。 (可以用任何语言回答:这与算法有关)

Answer 1

稳健的峰值检测算法(使用z分数)
我想出了一种对这些类型的数据集非常有效的算法。它基于dispersion原理:如果新数据点是给定的x偏离某个移动平均值的标准偏差数，则算法会发出信号(也称为z-score)。该算法非常健壮，因为它构造了单独的移动平均值和偏差，从而信号不会破坏阈值。因此，无论先前信号的数量如何，都以大致相同的精度识别 future 信号。该算法需要3个输入:lag = the lag of the moving window，threshold = the z-score at which the algorithm signals和influence = the influence (between 0 and 1) of new signals on the mean and standard deviation。例如，lag为5将使用最后5个观测值来平滑数据。如果数据点与移动平均值相差3.5个标准偏差，则threshold为3.5会发出信号。 0.5的influence给信号带来的影响是普通数据点的一半。同样，influence为0时会完全忽略用于重新计算新阈值的信号。因此，影响力0是最可靠的选项(但假定为stationarity)；将影响力选项设置为1的方法最不可靠。因此，对于非平稳数据，影响选项应置于0到1之间。
其工作方式如下:
伪码

# Let y be a vector of timeseries data of at least length lag+2
# Let mean() be a function that calculates the mean
# Let std() be a function that calculates the standard deviaton
# Let absolute() be the absolute value function

# Settings (the ones below are examples: choose what is best for your data)
set lag to 5;          # lag 5 for the smoothing functions
set threshold to 3.5;  # 3.5 standard deviations for signal
set influence to 0.5;  # between 0 and 1, where 1 is normal influence, 0.5 is half

# Initialize variables
set signals to vector 0,...,0 of length of y;   # Initialize signal results
set filteredY to y(1),...,y(lag)                # Initialize filtered series
set avgFilter to null;                          # Initialize average filter
set stdFilter to null;                          # Initialize std. filter
set avgFilter(lag) to mean(y(1),...,y(lag));    # Initialize first value
set stdFilter(lag) to std(y(1),...,y(lag));     # Initialize first value

for i=lag+1,...,t do
  if absolute(y(i) - avgFilter(i-1)) > threshold*stdFilter(i-1) then
    if y(i) > avgFilter(i-1) then
      set signals(i) to +1;                     # Positive signal
    else
      set signals(i) to -1;                     # Negative signal
    end
    # Reduce influence of signal
    set filteredY(i) to influence*y(i) + (1-influence)*filteredY(i-1);
  else
    set signals(i) to 0;                        # No signal
    set filteredY(i) to y(i);
  end
  # Adjust the filters
  set avgFilter(i) to mean(filteredY(i-lag),...,filteredY(i));
  set stdFilter(i) to std(filteredY(i-lag),...,filteredY(i));
end

在下面可以找到为数据选择良好参数的经验法则。

演示版

该演示的Matlab代码可以在 here中找到。要使用该演示，只需运行它并单击上方的图表即可自己创建一个时间序列。该算法在绘制观察值的 lag后开始工作。

结果
对于原始问题，使用以下设置时，此算法将提供以下输出: lag = 30, threshold = 5, influence = 0:


不同编程语言的实现:

Matlab(我)

R(我)

Golang(Xeoncross)

Python(R Kiselev)

Python [有效版本](delica)

Swift(我)

Groovy(JoshuaCWebDeveloper)

C++(布莱德)

C++(Animesh Pandey)

Rust(向导)

Scala(Mike Roberts)

Kotlin(leoderprofi)

Ruby(Kimmo Lehto)

Fortran [用于共振检测](THo)

Julia(马特训练营)

C#(海洋空投)

C(DavidC)

Java(takanuva15)

JavaScript(DirkLüsebrink)

TypeScript(Jerry Gamble)

Perl(Alen)

PHP(radhoo)

配置算法的经验法则
lag :lag参数确定将对您的数据进行平滑处理的数量，以及该算法对数据的长期平均值变化的适应性。数据 stationary越多，应包含的滞后就越多(这将提高算法的鲁棒性)。如果数据包含随时间变化的趋势，则应考虑希望算法多快适应这些趋势。也就是说，如果将 lag设置为10，则需要10个“期间”，才能将算法的阈值调整为长期平均值的任何系统变化。因此，请根据数据的趋势行为以及该算法的适应性来选择 lag参数。
influence :此参数确定信号对算法检测阈值的影响。如果将其设置为0，则信号对阈值没有影响，因此，将根据阈值来检测将来的信号，该阈值的平均值和标准偏差不受过去信号的影响。如果设为0.5，则信号的影响是正常数据点的一半。考虑这一点的另一种方法是，如果将影响设为0，则隐含假设平稳(即，无论有多少信号，您始终希望时间序列从长远来看会返回相同的平均值)。如果不是这种情况，则应将影响参数设置在0到1之间，这取决于信号可以系统地影响数据的时变趋势的程度。例如，如果信号导致时间序列的长期平均值 structural break，则应将影响参数设置为较高(接近1)，以便阈值可以快速响应结构性断裂。
threshold :阈值参数是与移动平均值的标准偏差数，在该平均值以上，算法会将新数据点分类为信号。例如，如果新数据点比移动平均值高4.0个标准差，并且阈值参数设置为3.5，则算法会将数据点识别为信号。该参数应根据您期望的信号数量来设置。例如，如果您的数据是正态分布的，则阈值(或z分数)为3.5时，对应的信号概率为0.00047(来自 this table)，这意味着您希望每2128个数据点(1/0.00047)发送一次信号。因此，阈值直接影响算法的敏感度，从而也确定算法发出信号的频率。检查您自己的数据，然后选择一个合理的阈值，该阈值可以在您希望算法发出信号时发出信号(此处可能需要反复试验才能达到您的目的所需的良好阈值)。

警告:上面的代码每次运行时总是在所有数据点上循环。 在实现此代码时，请确保将信号的计算拆分为一个单独的函数(无循环)。然后，当一个新的数据点到达时，更新 filteredY， avgFilter和 stdFilter一次。请勿在每次有新数据点时都重新计算所有数据的信号(如上例中所示)，这在实时应用中会非常低效且缓慢。
修改算法(以进行潜在改进)的其他方法是:

使用中位数代替平均值

使用诸如MAD之类的robust measure of scale代替标准偏差

使用信令余量，因此信号切换的频率不会太高

更改影响参数的工作方式

以不同方式处理上下信号(不对称处理)

为均值和std(as in this Swift translation)

创建一个单独的 influence参数

(已知)对此StackOverflow答案的学术引用:

Gao，S.，＆Calderon，D.P.(2020年)。 Robust alternative to the righting reflex to assess arousal in rodents。科学报告，10(1)，1-11。

Chen，G.＆Dong，W.(2020年)。 Reactive Jamming and Attack Mitigation over Cross-Technology Communication Links。传感器网络上的ACM交易，第17(1)条。

R.高桥，福本，M.，Han，C.Sasatani，T.，Narusue，Y.，＆Kawahara，Y.(2020年)。 TelemetRing: A Batteryless and Wireless Ring-shaped Keyboard using Passive Inductive Telemetry。在第33届ACM年度用户界面软件和技术研讨会论文集(第1161-1168页)中。

Negus，M.J.，Moore，M.R.，Oliver，J.M.，Cimpeanu，R.(2020年)。 Droplet impact onto a spring-supported plate: analysis and simulations。 ArXiv电子打印，可从以下位置访问:https://arxiv.org/abs/2009.09872

Yin，C.(2020年)。 Dinucleotide repeats in coronavirus SARS-CoV-2 genome: evolutionary implications。 ArXiv电子打印，可从以下位置访问:https://arxiv.org/pdf/2006.00280.pdf

Esnaola-Gonzalez，I.，Gómez-Omella，M.，Ferreiro，S.，Fernandez，I.，Lázaro，I.，＆García，E.(2020年)。 An IoT Platform Towards the Enhancement of Poultry Production Chains。传感器，20(6)，1549。

Gao，S.，＆Calderon，D.P.(2020年)。 Continuous regimens of cortico-motor integration calibrate levels of arousal during emergence from anesthesia。 bioRxiv。

Cloud，B.，Tarien，B.，Liu，A.，Shedd，T.，Lin，X.，Hubbard，M.，...＆Moore，J.K.(2019)。 Adaptive smartphone-based sensor fusion for estimating competitive rowing kinematic metrics。一，14(12)。

Ceyssens，F.，Carmona，M. B.，Kil，D.，Deprez，M.，Tooten，E.，Nuttin，B.，...＆Puers，R.(2019)。 Chronic neural recording with probes of subcellular cross-section using 0.06 mm² dissolving microneedles as insertion device。传感器和执行器B:化学，284，第369-376页。

Dons，E.，Laeremans，M.，Orjuela，J.P.，Avila-Palencia，I.，de Nazelle，A.，Nieuwenhuijsen，M.，...＆Nawrot，T.(2019年)。 Transport most likely to cause air pollution peak exposures in everyday life: Evidence from over 2000 days of personal monitoring。大气环境，213，424-432。

Schaible B.J.，Snook K.R.，Yin J.等。 (2019)。 Twitter conversations and English news media reports on poliomyelitis in five different countries, January 2014 to April 2015。永久杂志，23，18-181。

Lima，B.(2019年)。 Object Surface Exploration Using a Tactile-Enabled Robotic Fingertip(渥太华大学/渥太华大学博士学位论文)。

Lima，B.M. R.，Ramos，L.C.S.，de Oliveira，T.E.A.，da Fonseca，V.P.＆Petriu，E.M.(2019)。 Heart Rate Detection Using a Multimodal Tactile Sensor and a Z-score Based Peak Detection Algorithm。 CMBES session 记录，42。

Lima，B.M. R.，de Oliveira，T.E.A.，da Fonseca，V.P.，Zhu，Q.，Goubran，M.，Groza，V.Z.，＆Petriu，E.M.(2019年6月)。 Heart Rate Detection Using a Miniaturized Multimodal Tactile Sensor。在2019 IEEE医疗测量和应用国际研讨会(MeMeA)(第1-6页)。 IEEE。

Ting，C.，Field，R.，Quach，T.，Bauer，T.(2019)。 Generalized Boundary Detection Using Compression-based Analytics。 ICASSP 2019-2019 IEEE声学，语音和信号处理国际 session (ICASSP)，英国布莱顿，第3522-3526页。

Carrier，E.E.(2019)。 Exploiting compression in solving discretized linear systems。伊利诺伊大学香槟分校博士论文。

Khandakar，A.，Chowdhury，M.E.，Ahmed，R.，Dhib，A.，Mohammed，M.，Al-Emadi，N.A.，＆Michelson，D.(2019年)。 Portable system for monitoring and controlling driver behavior and the use of a mobile phone while driving。传感器，19(7)，1563。

Baskozos，G.，Dawes，J.M.，Austin，J.S.，Antunes-Martins，A.，McDermott，L.，Clark，A.J.，...＆Orengo，C.(2019)。 Comprehensive analysis of long noncoding RNA expression in dorsal root ganglion reveals cell-type specificity and dysregulation after nerve injury。疼痛，160(2)，463。

Cloud，B.，Tarien，B.，Crawford，R.，＆Moore，J.(2018年)。 Adaptive smartphone-based sensor fusion for estimating competitive rowing kinematic metrics。 engrXiv预印本。

Zajdel，T.J.(2018年)。 Electronic Interfaces for Bacteria-Based Biosensing。加州大学伯克利分校博士论文。

Perkins，P.，Heber，S.(2018年)。 Identification of Ribosome Pause Sites Using a Z-Score Based Peak Detection Algorithm。 IEEE第八届生物与医学科学计算国际 session (ICCABS)，ISBN:978-1-5386-8520-4。

Moore，J.，Goffin，P.，Meyer，M.，Lundrigan，P.，Patwari，N.，Sward，K.，＆Wiese，J.(2018年)。 Managing In-home Environments through Sensing, Annotating, and Visualizing Air Quality Data。 ACM关于交互式，移动，可穿戴和无处不在技术的 session 论文集，2(3)，128。

Lo，O.，Buchanan，W. J.，Griffiths，P.，and Macfarlane，R.(2018)，Distance Measurement Methods for Improved Insider Threat Detection，安全和通信网络，第1卷。 2018，物品ID 5906368。

Apurupa，N.V.，Singh，P.，Chakravarthy，S.，＆Buduru，A.B.(2018年)。 A critical study of power consumption patterns in Indian Apartments。博士学位论文，IIIT-德里。

Scirea，M.(2017年)。 Affective Music Generation and its effect on player experience。哥本哈根IT大学数字设计博士论文。

Scirea，M.，Eklund，P.，Togelius，J.，＆Risi，S.(2017年)。 Primal-improv: Towards co-evolutionary musical improvisation。计算机科学与电子工程(CEEC)，2017(pp.172-177)。 IEEE。

Catalbas，M.C.，Cegovnik，T.，Sodnik，J.和Gulten，A.(2017年)。 Driver fatigue detection based on saccadic eye movements，第十届国际电气和电子工程 session (ELECO)，第913-917页。

使用此答案中的算法的其他作品

Bernardi，D.(2019年)。 A feasibility study on pairing a smartwatch and a mobile device through multi-modal gestures。阿尔托大学硕士论文。

Lemmens，E.(2018年)。 Outlier detection in event logs by using statistical methods，埃因霍温大学硕士论文。

Willems，P.(2017年)。 Mood controlled affective ambiences for the elderly，特温特大学硕士论文。

Ciocirdel，G.D.和Varga，M.(2016)。 Election Prediction Based on Wikipedia Pageviews。阿姆斯特丹Vrije大学项目文件。

此答案中算法的其他应用

Python package: Machine Learning Financial Laboratory，基于De Prado，M.L.(2018)的工作。 Advances in financial machine learning。约翰·威利父子。

Adafruit CircuitPlayground Library，Adafruit板(Adafruit Industries)

Step tracker algorithm，Android应用(jeeshnair)

R package: animaltracker(Thea Sukianto乔·乔恩)

链接到其他峰检测算法

Real-time peak detection in noisy sinusoidal time-series

如何引用此算法:

Brakel, J.P.G. van (2014). "Robust peak detection algorithm using z-scores". Stack Overflow. Available at: https://stackoverflow.com/questions/22583391/peak-signal-detection-in-realtime-timeseries-data/22640362#22640362 (version: 2020-11-08).

如果您在某处使用此功能，请使用上述引用资料归功于我。如果您对算法有任何疑问，请将其发布在下面的评论中，或者通过 LinkedIn与我联系。