[algorithm] 실시간 시계열 데이터에서 피크 신호 ​​감지

Program / 글쓴이

업데이트 : 지금까지 가장 성능이 좋은 알고리즘 은 이것 입니다.

이 질문은 실시간 시계열 데이터에서 갑작스러운 피크를 감지하기위한 강력한 알고리즘을 탐구합니다.

다음 데이터 세트를 고려하십시오.

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];

(매트랩 형식이지만 언어가 아니라 알고리즘에 관한 것입니다)

데이터 도표

세 개의 큰 피크와 약간의 작은 피크가 있음을 분명히 알 수 있습니다. 이 데이터 세트는 질문과 관련된 시계열 데이터 세트 클래스의 특정 예입니다. 이 클래스의 데이터 세트에는 두 가지 일반적인 기능이 있습니다.

  1. 일반적인 평균과 기본 소음이 있습니다
  2. 노이즈에서 크게 벗어난 큰 ‘ 피크 ‘또는 ‘ 높은 데이터 포인트 ‘가 있습니다.

다음을 가정 해 봅시다.

  • 피크의 폭은 미리 결정될 수 없다
  • 피크의 높이가 다른 값과 명확하고 크게 벗어납니다.
  • 사용 된 알고리즘은 실시간을 계산해야합니다 (따라서 새로운 데이터 포인트마다 변경)

이러한 상황에서는 신호를 트리거하는 경계 값을 구성해야합니다. 그러나 경계 값은 정적 일 수 없으며 알고리즘을 기반으로 실시간으로 결정해야합니다.

내 질문 : 실시간으로 그러한 임계 값을 계산하는 좋은 알고리즘은 무엇입니까? 그러한 상황에 대한 특정 알고리즘이 있습니까? 가장 잘 알려진 알고리즘은 무엇입니까?

강력한 알고리즘 또는 유용한 통찰력은 모두 높이 평가됩니다. (어떤 언어로든 대답 할 수 있습니다 : 알고리즘에 관한 것입니다)

답변

강력한 피크 감지 알고리즘 (z- 스코어 사용)

이러한 유형의 데이터 세트에 매우 잘 작동하는 알고리즘을 생각해 냈습니다. 이는 분산 원리를 기반으로합니다 . 만약 새로운 데이터 포인트가 어떤 이동 평균과 거리를두고 주어진 x 수의 표준 편차라면, 알고리즘 신호 (또는 z- 점수 라고도 함 ). 이 알고리즘은 신호가 임계 값을 손상시키지 않도록 별도의 이동 평균 및 편차를 구성하기 때문에 매우 강력 합니다. 따라서 미래의 신호는 이전 신호의 양에 관계없이 거의 동일한 정확도로 식별됩니다. 알고리즘은 lag = the lag of the moving window, threshold = the z-score at which the algorithm signals및의 3 가지 입력을받습니다 influence = the influence (between 0 and 1) of new signals on the mean and standard deviation. 예를 들어, a lagof 5는 마지막 5 개의 관측 값을 사용하여 데이터를 평활화합니다. ㅏthreshold데이터 포인트가 이동 평균에서 3.5 표준 편차 떨어져있는 경우 3.5의 신호는 신호를 보냅니다. 그리고 influence0.5의 값은 신호 가 정상 데이터 포인트에 미치는 영향의 절반 을 나타냅니다. 마찬가지로, influence0은 새 임계 값을 다시 계산하기 위해 신호를 완전히 무시합니다. 따라서 0의 영향이 가장 강력한 옵션입니다 (그러나 정상 성을 가정 함 ). 영향 옵션을 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 코드는 여기 에서 찾을 수 있습니다 . 데모를 사용하려면 데모를 실행하고 상단 차트를 클릭하여 시계열을 직접 만드십시오. lag여러 관측 값 을 그린 후 알고리즘이 작동하기 시작합니다 .

결과

원래 질문에 대해이 알고리즘은 다음 설정을 사용할 때 다음과 같은 출력을 제공합니다. lag = 30, threshold = 5, influence = 0:

임계 값 알고리즘 예

다른 프로그래밍 언어로 구현 :

알고리즘 구성을위한 경험 법칙

lag: lag 매개 변수는 데이터를 얼마나 부드럽게 할 것인지와 알고리즘이 데이터의 장기 평균 변화에 얼마나 적응할 수 있는지를 결정합니다. 더 많은 고정 데이터, 당신은 포함해야 더 시차 (이 알고리즘의 견고성을 개선해야한다)입니다. 데이터에 시변 추세가 포함 된 경우 알고리즘이 이러한 추세에 얼마나 빨리 적용되기를 원하는지 고려해야합니다. 즉, lag10 을 입력 하면 알고리즘의 임계 값이 장기 평균의 체계적인 변경에 맞게 조정되기 전에 10 개의 ‘기간’이 걸립니다. 따라서 lag데이터의 트 렌딩 동작과 알고리즘의 적응성을 기반으로 매개 변수를 선택하십시오 .

influence:이 파라미터는 알고리즘의 감지 임계 값에 대한 신호의 영향을 결정합니다. 0으로 설정하면 신호는 임계 값에 영향을 미치지 않으므로 미래 신호는 과거 신호의 영향을받지 않는 평균 및 표준 편차로 계산 된 임계 값을 기반으로 감지됩니다. 이것에 대해 생각하는 또 다른 방법은 영향을 0으로 설정하면, 고정도를 암시 적으로 가정한다는 것입니다 (즉, 신호의 수에 관계없이 시계열은 항상 장기적으로 동일한 평균으로 돌아갑니다). 그렇지 않은 경우 신호가 데이터의 시변 추세에 체계적으로 영향을 줄 수있는 정도에 따라 영향 매개 변수를 0과 1 사이에 놓아야합니다. 예를 들어 신호가 구조적 중단으로 이어질 경우 시계열의 장기 평균에서 영향 매개 변수를 높게 (1에 가깝게) 설정하여 임계 값이 이러한 변화에 빠르게 적응할 수 있도록해야합니다.

threshold: 임계 값 매개 변수는 알고리즘이 새로운 데이터 포인트를 신호로 분류하는 이동 평균과의 표준 편차 수입니다. 예를 들어, 새 데이터 포인트가 이동 평균보다 4.0 표준 편차이고 임계 값 매개 변수가 3.5로 설정된 경우 알고리즘은 데이터 포인트를 신호로 식별합니다. 이 매개 변수는 예상되는 신호 수에 따라 설정해야합니다. 예를 들어, 데이터가 정규 분포 인 경우 임계 값 (또는 z- 점수) 3.5는 이 표의 신호 확률 0.00047에 해당 합니다.)는 2128 개의 데이터 포인트 (1 / 0.00047)마다 한 번씩 신호를 예상한다는 의미입니다. 따라서 임계 값은 알고리즘의 민감도와 알고리즘 신호 빈도에 직접적인 영향을줍니다. 자신의 데이터를 검사하고 필요할 때 알고리즘 신호를 만드는 합리적인 임계 값을 결정하십시오 (여러 목적에 적합한 임계 값에 도달하려면 일부 시행 착오가 필요할 수 있습니다).

경고 : 위 코드는 항상 모든 데이터 포인트가 실행될 때마다 반복됩니다. 이 코드를 구현할 때는 신호 계산을 별도의 함수 (루프없이)로 분할해야합니다. 그런 다음 새로운 데이터 포인트가 도착하면, 갱신 filteredY, avgFilter그리고 stdFilter한 번. 새 데이터 포인트가있을 때마다 (위의 예와 같이) 모든 데이터에 대한 신호를 다시 계산하지 마십시오. 이는 매우 비효율적이고 느립니다!

잠재적 인 개선을 위해 알고리즘을 수정하는 다른 방법은 다음과 같습니다.

  1. 평균 대신 중앙값 사용
  2. 용도 규모의 강력한 조치를 대신 표준 편차, 같은 MAD로,
  3. 신호 마진을 사용하면 신호가 너무 자주 전환되지 않습니다
  4. 영향 매개 변수 작동 방식 변경
  5. 치료 업 및 다운 다른 신호 (비대칭 처리)
  6. influence평균과 표준에 대한 별도의 매개 변수를 만듭니다 ( 이 Swift 변환에서 수행 된 것처럼 )

이 StackOverflow 답변에 대한 (알려진) 학술 인용 :

알고리즘을 사용하는 다른 작업

이 알고리즘의 다른 응용

다른 피크 검출 알고리즘에 대한 링크

이 기능을 어딘가에 사용하면 저 또는이 답변을 알려주십시오. 이 알고리즘에 대해 궁금한 점이 있으면 아래 의견에 게시하거나 LinkedIn 에서 문의하십시오 .

답변

여기서이다 Python/의 numpy평활화 Z 점수 알고리즘의 구현 (참조 : 상기 답 ). 여기서 요점을 찾을 수 있습니다 .

#!/usr/bin/env python
# Implementation of algorithm from https://stackoverflow.com/a/22640362/6029703
import numpy as np
import pylab

def thresholding_algo(y, lag, threshold, influence):
    signals = np.zeros(len(y))
    filteredY = np.array(y)
    avgFilter = [0]*len(y)
    stdFilter = [0]*len(y)
    avgFilter[lag - 1] = np.mean(y[0:lag])
    stdFilter[lag - 1] = np.std(y[0:lag])
    for i in range(lag, len(y)):
        if abs(y[i] - avgFilter[i-1]) > threshold * stdFilter [i-1]:
            if y[i] > avgFilter[i-1]:
                signals[i] = 1
            else:
                signals[i] = -1

            filteredY[i] = influence * y[i] + (1 - influence) * filteredY[i-1]
            avgFilter[i] = np.mean(filteredY[(i-lag+1):i+1])
            stdFilter[i] = np.std(filteredY[(i-lag+1):i+1])
        else:
            signals[i] = 0
            filteredY[i] = y[i]
            avgFilter[i] = np.mean(filteredY[(i-lag+1):i+1])
            stdFilter[i] = np.std(filteredY[(i-lag+1):i+1])

    return dict(signals = np.asarray(signals),
                avgFilter = np.asarray(avgFilter),
                stdFilter = np.asarray(stdFilter))

아래는 R/ 에 대한 원래 답변과 동일한 플롯을 생성하는 동일한 데이터 세트에 대한 테스트입니다.Matlab

# Data
y = np.array([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])

# Settings: lag = 30, threshold = 5, influence = 0
lag = 30
threshold = 5
influence = 0

# Run algo with settings from above
result = thresholding_algo(y, lag=lag, threshold=threshold, influence=influence)

# Plot result
pylab.subplot(211)
pylab.plot(np.arange(1, len(y)+1), y)

pylab.plot(np.arange(1, len(y)+1),
           result["avgFilter"], color="cyan", lw=2)

pylab.plot(np.arange(1, len(y)+1),
           result["avgFilter"] + threshold * result["stdFilter"], color="green", lw=2)

pylab.plot(np.arange(1, len(y)+1),
           result["avgFilter"] - threshold * result["stdFilter"], color="green", lw=2)

pylab.subplot(212)
pylab.step(np.arange(1, len(y)+1), result["signals"], color="red", lw=2)
pylab.ylim(-1.5, 1.5)
pylab.show()

답변

한 가지 방법은 다음 관찰을 기반으로 피크를 감지하는 것입니다.

  • 시간 t는 (y (t)> y (t-1)) && (y (t)> y (t + 1) 인 경우 피크 임)

상승 추세가 끝날 때까지 기다림으로써 오 탐지를 피합니다. 피크가 1 dt만큼 빠질 것이라는 점에서 정확히 “실시간”은 아닙니다. 비교를 위해 마진을 요구함으로써 감도를 제어 할 수 있습니다. 시끄러운 감지와 감지 지연 사이에는 상충 관계가 있습니다. 더 많은 매개 변수를 추가하여 모델을 보강 할 수 있습니다.

  • (y (t)-y (t-dt)> m) && (y (t)-y (t + dt)> m) 피크

여기서 dt 와 m 은 감도 대 시간 지연을 제어하기위한 매개 변수입니다.

이것은 언급 된 알고리즘으로 얻는 것입니다.
여기에 이미지 설명을 입력하십시오

파이썬으로 줄거리를 재현하는 코드는 다음과 같습니다.

import numpy as np
import matplotlib.pyplot as plt
input = np.array([ 1. ,  1. ,  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. ,  1. ,  1. ,  1. ])
signal = (input > np.roll(input,1)) & (input > np.roll(input,-1))
plt.plot(input)
plt.plot(signal.nonzero()[0], input[signal], 'ro')
plt.show()

을 설정 m = 0.5하면 오 탐지가 하나만있는 더 깨끗한 신호를 얻을 수 있습니다.
여기에 이미지 설명을 입력하십시오

답변

신호 처리에서 피크 검출은 종종 웨이블릿 변환을 통해 수행됩니다. 기본적으로 시계열 데이터에서 이산 웨이블릿 변환을 수행합니다. 반환되는 세부 계수의 제로 크로싱은 시계열 신호의 피크에 해당합니다. 다른 세부 계수 레벨에서 다른 피크 진폭을 감지하여 다중 레벨 분해능을 제공합니다.

답변

우리는 데이터 세트에서 평활화 된 z- 점수 알고리즘을 사용하려고 시도했습니다. 이는 중간 정도가 거의없이 과민성 또는 과민성 (매개 변수 조정 방법에 따라 다름)을 초래합니다. 사이트의 트래픽 신호에서 일일주기를 나타내는 저주파 기준선을 관찰했으며, 가능한 최상의 매개 변수 (아래 그림 참조)를 사용하더라도 대부분의 데이터 포인트가 비정상으로 인식되기 때문에 특히 4 일째에 계속 이어집니다. .

원래의 z- 점수 알고리즘을 기반으로 리버스 필터링을 통해이 문제를 해결하는 방법을 찾았습니다. 수정 된 알고리즘 및 TV 광고 트래픽 속성에 대한 애플리케이션의 세부 사항은 팀 블로그 에 게시되어 있습니다.

여기에 이미지 설명을 입력하십시오

답변

전산 토폴로지에서 지속적인 상 동성이라는 아이디어는 효율적으로 (정렬 숫자만큼 빠름) 솔루션으로 이어집니다. 피크를 감지 할뿐만 아니라 피크의 “유의”를 자연스럽게 정량화하여 중요한 피크를 선택할 수 있습니다.

알고리즘 요약.
1 차원 설정 (시계열, 실수 신호)에서 알고리즘은 다음 그림으로 쉽게 설명 할 수 있습니다.

가장 지속적인 피크

함수 그래프 (또는 하위 수준 세트)를 가로로 생각하고 수위가 무한대 (또는이 그림에서 1.8)에서 시작하는 것을 고려하십시오. 레벨이 감소하는 동안 로컬 최대 섬에서 팝업이 나타납니다. 지역 최소에서이 섬들은 합쳐집니다. 이 아이디어의 세부 사항 중 하나는 나중에 나타난 섬이 더 오래된 섬으로 병합된다는 것입니다. 섬의 “지속성”은 출생 시간에서 사망 시간을 뺀 것입니다. 파란색 막대의 길이는 지속성을 나타내며 위에서 언급 한 피크의 “의의”입니다.

능률.
함수 값이 정렬 된 후 선형 시간으로 실행되는 구현 (실제로 단일 루프 임)을 찾는 것은 그리 어렵지 않습니다. 따라서이 구현은 실제로 빠르며 쉽게 구현됩니다.

참고 문헌.
전체 스토리를 작성하고 지속적인 상 동성 (전산 적 대수 토폴로지의 필드)의 동기에 대한 언급은 https://www.sthu.org/blog/13-perstopology-peakdetection/index.html 에서 확인할 수 있습니다.

답변

시계열의 피크 검출을위한 단순 알고리즘 에서 GH Palshikar의 또 다른 알고리즘을 찾았습니다 .

알고리즘은 다음과 같습니다.

algorithm peak1 // one peak detection algorithms that uses peak function S1

input T = x1, x2, …, xN, N // input time-series of N points
input k // window size around the peak
input h // typically 1 <= h <= 3
output O // set of peaks detected in T

begin
O = empty set // initially empty

    for (i = 1; i < n; i++) do
        // compute peak function value for each of the N points in T
        a[i] = S1(k,i,xi,T);
    end for

    Compute the mean m' and standard deviation s' of all positive values in array a;

    for (i = 1; i < n; i++) do // remove local peaks which are “small” in global context
        if (a[i] > 0 && (a[i] – m') >( h * s')) then O = O + {xi};
        end if
    end for

    Order peaks in O in terms of increasing index in T

    // retain only one peak out of any set of peaks within distance k of each other

    for every adjacent pair of peaks xi and xj in O do
        if |j – i| <= k then remove the smaller value of {xi, xj} from O
        end if
    end for
end

장점

  • 이 논문은 피크 검출을위한 5 가지 알고리즘을 제공합니다
  • 알고리즘은 원시 시계열 데이터에서 작동합니다 (스무딩 필요 없음)

단점

  • 결정하기 k가 h어렵고 미리
  • 피크 는 평평 할 수 없습니다 (테스트 데이터의 세 번째 피크처럼)

예:

여기에 이미지 설명을 입력하십시오