논문읽기_시계열 클러스터링 K자형

2015년 SIGMODE 국제 데이터 관리 컨퍼런스에서 발표된 논문으로 시계열 데이터를 클러스터링하기 위한 K-Shape 방법을 주로 제안하고 있습니다. 기존 방식에 비해 거리 계산 방식인 중심 계산 방식을 최적화하고, 주파수 영역 특징 추출 방식도 도입해 효율성을 높였다.

저자는 이것이 도메인 독립적이고 정밀도가 높으며 효율적인 시계열 클러스터링 방법이라고 믿습니다.

DTW 방법에 비해 클러스터링 효과가 더 좋다고 생각합니다. 효과는 약간 떨어지지만 속도는 훨씬 빠릅니다. 결국 원칙적인 관점에서 K-Shape는 세로 방향의 신축과 가로 방향의 평행 이동만을 고려하는 반면, DTW는 가로 방향의 신축도 고려합니다.

K-Shape의 원리는 거리 계산 방법을 개선하고 중심 계산 방법을 최적화한다는 점을 제외하면 K-평균과 유사합니다. 한편으로는 진폭 스케일링 및 변환 불변성을 지원하는 반면, 계산 효율성은 상대적으로 높으며 매개변수를 수동으로 설정할 필요가 없어 더 많은 필드로 쉽게 확장할 수 있습니다.

두 시계열 데이터 세트 간의 차이를 계산하는 데 거리 알고리즘이 사용됩니다. 핵심 문제는 논문의 그림 1에 표시된 심전도 데이터의 변형을 처리하는 방법입니다. A/B :

그 중 A형의 특징은 상승 -> 하락 -> 상승, B형의 특징은 하락 -> 상승입니다. 그림 1의 오른쪽 아래 패널은 동일한 패턴을 인식하고 진폭과 위상의 차이를 무시하는 이상적인 모델링 효과를 보여줍니다. 사람들은 거리를 계산할 때도 이 방법을 사용하는 경향이 있으며, 클러스터링 방법보다 거리 계산 방법이 더 중요하다고 생각하는 경우도 많습니다. 일반적으로 진폭 스케일링 및 변환 불변성을 지원하는 방법은 계산 비용이 많이 들고 대용량 데이터 볼륨을 모델링하기 어렵습니다.

K-Shape 이전의 주류 거리 알고리즘은 다음과 같습니다.

K-Shape은 교차 상관 방법을 사용하여 두 시계열 간의 거리를 계산합니다. 두 개의 시계열 X와 Y가 있고 시퀀스 길이가 모두 m이라고 가정합니다. 변환 불변성을 달성하려면 Y를 변경하지 않고 X를 단계별로 슬라이드한 다음 각 단계에서 X와 Y의 차이를 계산합니다.

위 그림과 같이 녹색 영역이 Y, 흰색 영역이 스와이프 X, 각 행 s(단계)가 한 단계 앞으로 스와이프되고 시퀀스 길이가 m=4라고 가정하고, s∈(-3 ,3) ***7 값, w는 2m-1=7번의 모든 이동 가능성, w-m=s=k, 아래 수식의 정렬 위치입니다(정렬 논리는 전체를 통해 실행됩니다). 연산).

상호 상관 계수 CC 정의:

R을 사용하여 각 단계에서 x와 y 사이의 유사성을 계산하고 쌍의 위치(X와 Y 모두에 존재함)를 계산합니다. ) 내적, 궁극적으로 R은 유효한 영역의 내적의 합입니다(각 쌍의 패치에 대해 합산됨). R이 클수록 두 시퀀스가 ​​더 유사하다고 말할 수 있습니다.

비교되는 각 하위 시퀀스는 진폭이 다르고 블록 번호도 다르기 때문에 비교 중에 정규화를 수행해야 합니다. 세 번째 방법은 상호 상관 방법을 사용하는데 가장 좋은 효과를 나타냅니다.

정규화 효과는 아래 그림과 같습니다.

그림 (a)는 z-정규화를 사용하여 변환 없이 진폭만 정규화하는 것을 볼 수 있습니다. 정렬 효과는 변환이 없을 때(직접 위를 향함) 가장 좋습니다. (b)(c)(d)를 보면 알 수 있다. (d) 그림에서는 세 번째 방법을 사용하는데, 중간점(s=0), 즉 서로 마주보는 지점에서 유사도 값이 가장 크다. , 유사도가 가장 크며 이는 (a)에 표시된 효과와 일치합니다. 그리고 (b)와 (c) 모두 가장 유사한 상황이 오른쪽에서 발생한다고 생각하는데, 이는 분명히 옳지 않습니다.

기사에서는 모양 기반 거리 SBD(Shape-based distance)를 정의합니다. 블록이 많이 겹칠수록 모양이 CC와 더 유사해집니다. 가능한 모든 위치의 유사도 값을 비교합니다. 가장 유사한 max(CC) 를 사용하고 SBD를 얻기 위해 1-max(CC)를 사용합니다. 즉, 모양이 유사할수록 SBD의 거리가 더 작아집니다. 따라서 정규화된 NCC 값은 두 값 사이에 있습니다. SBD 값은 사이입니다.

시퀀스가 ​​길면 위 방법을 사용하는 경우 시간 복잡도가 상대적으로 높다는 것을 알 수 있는데, 이 문제를 해결하려면 계산량이 매우 많아야 합니다. 저자는 푸리에를 사용할 것을 제안합니다. 변환은 시퀀스를 시간 영역에서 주파수 영역으로 변환한 후 비교하여 계산량을 절약합니다.

거리를 정의한 후에는 거리 논리에 따라 중심 알고리즘을 조정해야 합니다.

그림 4에서 볼 수 있듯이 시계열 데이터의 중심은 시계열 변화선이기도 합니다. 그림의 파란색 선은 평균 방법(각 지점의 평균 계산)을 사용하여 계산합니다. 중심이 어긋나서 파동의 최고점과 최저점이 직선으로 그려지므로 모양 추세를 올바르게 표현할 수 없습니다.

K-Shape는 SBD 기반 방법을 사용하여 질량 중심을 계산합니다.

이 공식의 목표는 질량 중심 μk와 클러스터 Pk의 각 시퀀스 xi 간의 유사성 NCC를 최대화하기 위해 μk*를 찾는 것입니다.

알고리즘 1: 먼저 SBD() 함수를 사용하여 dist를 계산하고 y'는 시계열 x와 y 사이의 거리이고 y'는 x와 가장 잘 일치하는 y의 하위 세그먼트입니다. 이 방법을 사용하면 최고점과 최저점이 잘못 정렬되어 서로 상쇄되는 문제가 해결됩니다.

그런 다음 선형 대수학 기반 방법을 사용하여 공식 13을 공식 15로 확장합니다.

마지막으로 레일리 몫 공식을 사용하여 단순화할 수 있습니다.

레일리 몫 R (M,x)의 중요한 속성은 R의 최대값이 행렬 M의 최대 고유값과 같고, 최소값이 행렬 M의 최소 고유값과 같다는 것입니다. 이때 R(M,x)의 x(즉, 이 질문에서는 uk)에 대해 너무 많이 생각할 필요가 없습니다. 공식 13은 다음 알고리즘으로 단순화됩니다.

알고리즘 2: ShapeExtraction()은 클러스터의 현재 중심 C와 클러스터의 모든 점 X를 기반으로 보다 합리적인 중심 C'를 계산합니다.

line2: 클러스터의 모든 점 X(i)를 탐색합니다.

line3: 각 점과 질량 중심 및 가장 유사한 세그먼트 x' 사이의 거리 dist를 계산합니다. 질량 중심

line4: X'에 가장 유사한 조각을 추가합니다.

line5: X'를 전치하고 X를 곱하여 정사각 행렬(정규화된 행렬 Q를 기반으로 한 제곱)을 생성합니다.

line7: 정규화 후 행렬 M 생성

line8: X'의 특징 추출을 달성하기 위해 가장 큰 고유값에 해당하는 행렬 M의 고유벡터를 가져옵니다.

( 위의 설명은 개인적인 이해이므로 꼭 맞는 것은 아니며 참고용입니다.)

최종 군집화 방법은 반복을 통해 구현되며 각 반복은 두 단계로 나누어집니다. 첫 번째 단계는 중심을 계산하는 것입니다. , 두 번째 단계에서는 각 시퀀스가 ​​새 중심으로부터의 거리에 따라 다른 클러스터에 다시 할당됩니다. 레이블이 더 이상 변경되지 않을 때까지 루프가 반복됩니다.

알고리즘 3: 클러스터링의 전체 프로세스는 k-Shape()에 의해 구현됩니다.

여기서 X는 모든 시퀀스, k는 클러스터 수, IDX는 레이블입니다.

line3: 레이블이 안정되고 반복 횟수가 100회를 초과하지 않을 때까지 반복을 계속합니다.

line4-10: 클러스터의 요소를 기반으로 각 클러스터의 중심 C를 다시 계산합니다. 클러스터

line11-line17: 각 시퀀스와 각 중심 사이의 거리를 계산하고 이를 새 클러스터에 할당합니다(레이블 재지정).

K-Shape 알고리즘의 각 반복에 필요한 시간은 다음과 같습니다.

O(max{n·k·m·log(m), n·m^2, k ·m ^3})

여기서 n은 인스턴스 수, k는 클러스터 수, m은 시퀀스 길이입니다. 이 알고리즘의 계산 비용의 대부분은 시계열 m의 길이에 따라 달라짐을 알 수 있습니다. 그러나 이 길이는 일반적으로 시계열 수보다 훨씬 작으므로 m에 대한 의존도는 병목 현상이 아닙니다. m이 매우 큰 드문 경우에는 분할 또는 차원 축소 방법을 사용하여 시퀀스 길이를 효과적으로 줄일 수 있습니다.

그림-5에서는 K-Shape, ED 및 DTW 모델의 효과를 비교합니다. 대부분의 경우 SBD가 ED보다 우수하고 경우에 따라 SBD가 DTW보다 우수함을 알 수 있습니다. 하지만 SBD의 장점은 DTW보다 빠르다는 것입니다.