조각별 회귀는 단일 라인이 데이터 세트를 모델링하기에 충분하지 않을 때 발생하는 특수한 유형의 선형 회귀입니다. 조각 별 회귀는 도메인을 잠재적으로 많은”세그먼트”로 나누고 각 세그먼트를 통해 별도의 라인에 맞습니다. 예를 들어 아래 그래프에서는 한 줄로 데이터를 모델링할 수 없으며 세 줄로 구분된 회귀 분석을 수행할 수 없습니다:
이 게시물은 시계열 데이터에 대한 조각 별 회귀를 자동화하는 데이터 독의 접근 방식을 제시합니다.
목표
조각별 회귀는 다른 상황에서 약간 다른 것을 의미할 수 있으므로,조각별 회귀 알고리즘으로 정확히 무엇을 달성하려고 하는지 명확히 하기 위해 잠시 시간을 내자.
자동 중단점 감지. 고전 통계 문헌에서 조각 별 회귀는 종종 수동 회귀 분석 작업 중에 제안되며,한 선형 추세가 다른 선형 추세로 향하는 육안으로는 분명합니다. 이 경우 인간은 조각 별 세그먼트 사이의 중단 점을 지정하고 데이터 집합을 분할하며 각 세그먼트에 대해 선형 회귀를 독립적으로 수행 할 수 있습니다. 우리의 사용 사례에서 우리는 초당 수백 개의 회귀를 수행하기를 원하며 인간이 모든 중단 점을 지정하는 것은 가능하지 않습니다. 대신,우리는 조각 별 회귀 알고리즘이 자체 중단 점을 식별해야한다는 요구 사항을 가지고 있습니다.
자동 세그먼트 카운트 감지. 데이터 세트에 정확히 두 개의 세그먼트가 있다는 것을 알고 있다면 가능한 각 세그먼트 쌍을 쉽게 볼 수 있습니다. 그러나 실제로는 임의의 시계열이 주어지면 하나 이상의 세그먼트가 있거나 3 또는 4 또는 5 보다 작아 야한다고 믿을 이유가 없습니다. 우리의 알고리즘은 사용자가 지정하지 않고 적절한 수의 세그먼트를 선택해야합니다.
연속성 요구 사항 없음. 조각 별 회귀에 대한 일부 방법은 각 세그먼트의 끝점이 다음 세그먼트의 시작점 인 연결된 세그먼트를 생성합니다. 우리는 알고리즘에 그러한 요구 사항을 부과하지 않습니다.
과제
자동화된 중단점 탐지를 사용하여 조각별 회귀를 구현하는 가장 분명한 과제는 솔루션 검색 공간의 크기가 크다는 점입니다. 시계열을 세그먼트로 나눌 수 있는 방법은 시계열의 길이가 지수적입니다. 동적 프로그래밍을 사용하여 순진한 무차별 대입 구현보다 훨씬 효율적으로 검색 공간을 통과 할 수 있지만 실제로는 여전히 너무 느립니다. 탐욕스러운 휴리스틱은 검색 공간의 넓은 영역을 신속하게 폐기하는 데 필요할 것입니다.
더 미묘한 도전은 한 솔루션의 품질을 다른 솔루션과 비교할 수있는 방법이 필요하다는 것입니다. 문제의 우리의 버전,알 수없는 번호와 세그먼트의 위치,우리는 세그먼트와 다른 중단 점의 다른 번호와 잠재적 인 솔루션을 비교해야합니다. 우리는 두 가지 경쟁 목표의 균형을 맞추려고 노력합니다:
- 오류를 최소화하십시오. 즉,각 세그먼트의 회귀선을 관찰된 데이터 포인트에 가깝게 만듭니다.
- 데이터를 잘 모델링하는 가장 적은 수의 세그먼트를 사용합니다. 각 점에 대해 단일 세그먼트(또는 두 점마다 하나의 세그먼트)를 생성하여 항상 제로 오류가 발생할 수 있습니다. 타임스탬프와 관련 메트릭 값 사이의 일반적인 관계에 대해서는 아무것도 배울 수 없으며 보간이나 외삽에 결과를 쉽게 사용할 수 없습니다.
솔루션
조각 회귀 문제에 대해 다음과 같은 욕심 많은 알고리즘을 사용합니다:
- 와 함께 조각 별 회귀 수행 엔/2 세그먼트,여기서 엔 시계열의 관측치 수입니다. 각 세그먼트의 회귀선은 일반 최소 제곱 회귀를 사용하여 적합합니다. 이 초기 조각 별 회귀 분석에는 오류가 거의 없지만 데이터 세트를 심각하게 초과합니다.
- 단 하나의 세그먼트가 있을 때까지 반복적으로:
- 인접 세그먼트의 모든 쌍에 대해 두 세그먼트가 결합된 경우 두 회귀선이 단일 회귀선으로 대체되는 총 오차 증가를 평가합니다.
- 오류가 가장 적게 증가하는 세그먼트 쌍을 함께 병합합니다.
- 이 병합을 수행하는 것이 중지 기준(아래에 정의 됨)을 충족하면 너무 멀리 떨어져 분리되어야하는 두 세그먼트를 병합했을 수 있습니다. 이 경우,이 반복의 병합 이전의 세그먼트 상태를 기억하십시오.
- 병합으로 인해 위의 세그먼트 상태가 기억되지 않은 경우 가장 좋은 방법은 하나의 큰 세그먼트입니다. 그렇지 않으면(2)에서 기억 될 마지막 세그먼트 상태가 최상의 솔루션입니다.
중지 기준
이전 병합보다 제곱된 오류의 총 합계를 늘리면 병합이 잠재적인 중지 지점으로 간주됩니다. 하나의 세그먼트만 있어야 하는 경우에 너무 빨리 중지되는 것을 방지하기 위해 하나의 세그먼트를 사용한 회귀의 총 오류의 3%미만인 총 오류의 증가를 초래하지 않는 한 병합을 잠재적 중지 지점으로 간주하지 않습니다. (3%는 임의의 임계 값이지만 실제로 잘 작동하는 것으로 나타났습니다.)이 중지 기준이 작동하는 이유를 설명하는 몇 가지 예가 아래에 나와 있습니다.
먼저 한 줄을 따라 점에 정규 분산 노이즈를 추가하여 생성 된 데이터 세트를 살펴 보겠습니다. 알고리즘은 이 데이터 세트를 통해 단일 세그먼트에만 올바르게 맞습니다.
이 경우 병합하지 않으면 총 제곱 오류 합계가 3%이상 증가합니다. 따라서 병합은 적절한 중지 지점으로 간주되지 않으며 모든 병합이 실행된 후 최종 상태를 사용합니다. 아래 그림에서 나중에 병합하면 이전 병합보다 더 많은 오류가 발생하는 경향이 있지만(각각 더 많은 포인트에 영향을 미치기 때문에 의미가 있음)더 많은 세그먼트가 병합되면 오류의 증가가 점차 증가한다는 것을 알 수 있습니다.
둘째,데이터 세트에 7 개의 별개의 세그먼트가있는 예를 살펴 보겠습니다.
이 경우 각 병합에 의해 도입 된 오류 플롯을 볼 때 마지막 6 개의 병합이 이전 병합보다 훨씬 더 많은 오류를 도입 한 것을 알 수 있습니다. 따라서 우리의 알고리즘은 6 번째에서 마지막 병합 이전의 세그먼트 상태를 기억하고 최종 솔루션으로 사용했습니다.
코드
데이터 도그/조각 별 기 허브에서는 알고리즘의 파이썬 구현을 찾을 수 있습니다. 데이터 집합이 주어지면 각 적합 세그먼트에 대한 위치 및 회귀 계수가 반환됩니다.
또한 요지에 포함 된plot_data_with_regression()—빠르고 쉬운 플로팅을위한 래퍼 함수. 이것이 어떻게 사용될 수 있는지에 대한 간단한 예:
# Generate a short time series.t = np.arange(25)v = np.abs(t-7) + np.random.normal(0, 2, len(t))# Fit a piecewise regression, and plot the result.plot_data_with_regression(t, v)
이 구현은 선형 회귀를 사용하지만 동일한 프레임 워크를 적용하여 관련 문제를 해결할 수 있습니다. 제곱 오차를 절대 오차 또는 후버 손실로 대체함으로써 회귀를 강력하게 만들 수 있습니다. 또는 각 세그먼트에 해당 도메인의 관측치 평균과 동일한 상수 값을 할당하여 단계 함수를 맞출 수 있습니다.
