3. 주요 분석기법 – 시계열 분석과 순차데이터

(9) 시계열 및 순차데이터에 대한 분석

가. 시계열 (time-series) 데이터의 분석 마이닝

앞서 우리는 시계열 분석을 통한 예측기법에 대해 알아본 바 있다. 여기서는 축적된 시계열 데이터를 통해 미래에 대한 예측을 하는 대신 그 안에 내재된 규칙과 숨겨진 모습을 찾아내는 분석기법에 대해 알아본다.

우 선 시계열 데이터베이스는 시시각각 변하는 값 또는 시간에 따라 발생하는 사건의 순차(순서)로 이루어져 있는데 이들 값은 보통 일정한 시간 간격으로 측정된다. 대표적 예로 증권시세, 각 지역별 교통량데이터, 다양한 종류의 센서로부터 발생되는 센서 데이터 등을 들 수 있다.

시계열 분석에서의 유사성 탐색

일반적 유사성 탐색에서 정확히 일치하는 (exact match) 데이터를 탐색하는 것이라면 시계열 데이터에 대한 유사성 탐색 (similarity search)에서는 query sequence 상의 약간의 차이가 용인된다. 유사성 탐색의 예로는 주식 시세에 관한 순차데이터에서 일정한 유사성을 탐색할 수도 있고 전력 소비패턴을 분석함으로써 시간대별 또는 다른 요인에 의해 유발되는 특이한 소비패턴을 구별해 내는데 이용되기도 한다.

구 체적으로 시계열 데이터 S가 주어졌을 때 유사성 탐색의 방법에는 크게 2가지가 있다. 우선 부분순차일치 (sub-sequence matching)에서는 찾고자 하는 순차데이터와 근접하는 데이터를 질의어를 통해 S 안에서 찾는다. 반명 전체순차일치 (whole sequence matching)에서는 S 안에 있는 순차데이터 중 서로 비슷한 것들을 찾아낸다.

데이터 축소와 변환기법

시계열 데이터베이스는 데이터의 크기와 차원이 매우 높기 때문에 처리속도의 개선이 필요한데 이를 위해 1차적으로 데이터 축소를 시도한다.

앞에서도 본 바와 같이 데이터 축소에는 다음의 몇 가지 접근법이 있다.

  •  속성부분집합 선택 (attribute subset selection) – 관련이 없거나 중복되는 속성 및 차원을 제거하는 것
  •  차원축소 (dimensionality reduction) – 신호처리기술을 원용해서 원래의 데이터를 압축된 형식으로 축소시키는 것.
  •  수 치 축소 (numerosity reduction) – 데이터의 수치값을 대체값으로 변경시킴으로써 데이터의 크기를 줄이는 것이며 예를 들어 histogram, 군집화, 표본추출 등의 기법을 이용한다. 이 중에서도 시계열 데이터는 각각의 시간요소가 차원의 의미를 가진다는 의미에서 차원이 매우 높기 때문에 특히 시간 또는 빈도 등과 관련한 차원축소 (dimensionality reduction)를 중요시한다.  그리고 시계열데이터에 주로 이용하는 차원축소의 기법으로는 다음과 같은 것들이 있다.
  •  이산 푸리에 변환 (DFT: Discrete Fourier Transformation)
  •  이산 wavelet 변환 (DWT: Discrete Wavelet Transformation)
  •  Singular Value Decomposition (SVD) – 주성분 분석(PCA) 기법에 기반함.
  •  임의투사 (random projection) 기반의 sketch기법
유사성 탐색의 절차와 기법

이제 유사성 탐색의 절차를 간단히 살펴 보자면 다음과 같다.

(1) 사전에 다차원 인덱스 (multidimensional index)를 생성한다. 이때는 앞서의 기법을 이용한 Fourier 계수를 적용한다.

(2) 분석자가 질의어를 입력한다.

(3) 질의어상의 검색어와 인덱스 사이의 유사도를 거리(distance) 개념에 입각하여 계산한 후 가장 근접한 것을 산출한다.

(4) (3)번에서의 산출에 대한 후처리 (postprocessing)을 통해 시간축 (time domain) 내에서의 sequence간의 실제 거리를 계산하고 이를 통해 실제 인접된 것만을 골라낸다.

(5) 분석자에게 최종 결과물을 출력한다.

이처럼 유사성 분석을 위해서는 인덱스의 생성이 중요한데 시간과 계산비용이 매우 많이 소요되기 때문에 이를 단축시키고자 많은 노력이 기울여지고 있다. (예: R-tree 등)

또 한 시계열 데이터의 유사성 탐색에 사용되는 거리 척도로는 유클리드 거리 (Euclidean distance)가 이용되는데 복수의 시계열 데이터 간의 거리가 짧을 수록 유사도가 크다는 것을 뜻하게 된다. 그리고 이때의 거리계산을 정확하 하기 위해서 데이터 값을 정규화변환을 실시하기도 한다.

변위와 진폭의 차이를 다루는 방법

실제 응용에서 부분순차가 완벽히 일치하는 것을 요구할 수는 없으며 대부분 부분순차의 쌍이 같은 모양이기만 하면 된다. 이는 주로 순차 내의 간격이나 변위 또는 진폭의 차이에 의한 것으로서 이를 극복하기 위해 분석가가 분석의 창(window), 유사성에 대한 포함선의 넓이와 간격 또는 일치 비율 등을 명시하도록 하는 방법으로 처리한다.

<그림>

시계열 데이터에서 모양은 같지만 이를 적시하기 어려을 때 gap, 편차 (offset), 진폭등을 조절해서 subsequence를 찾아내는 모습

즉, 변위와 진폭 내에서 간격과 차이를 다루는 유사성 탐색은 다음의 단계로 수행된다.

  •  원자 일치 (atomic matching) : 유사한 형태를 가지는 작은 또는 간격 없는 윈도우의 모든 쌍을 찾는다.
  •  Window 꿰매기 (window stitching): 원자 일치된 간격을 허용하면서 많은 유사한 부분순차들의 쌍을 형성하는 유사한 window를 서로 연결한다.
  •  부분순차의 순서화 (subsequence ordering):  충분히 유사한 조각들이 존재하는지 결정하기 위해 부분순서 일치들을 일렬로 정렬한다.

나. 순차데이터 분석

개요

순차 (Sequence)데이터란 순서를 가지는 데이터 요소의 집합 (Ordered set of elements)을 말한다.

        s = a1,a2,..an

이 때 각각의 항목는 수치 데이터일 수도 있고 범주형 (Categorical일 수도 있으며 복수의 속성을 가지는 경우도 많다. 단, 이때 각 순차 (즉, 시점별 데이터)는 특별히 고정된 길이를 가지지 않으며 다양한 형태가 가능하다. 아울러 순서는 시간에 의할 수도 있지만, 그 이외에도 위치 등에 다른 요인에 의해 순서가 매겨질 수도 있음을 유의해야 한다.

순차 데이터베이스 (sequence database)는 시계열 데이터와 같은 개념이지만 구체적 시간측정이 없이 사건데이터의 순차(순서)로만 구성될 수도 있다. 예컨대 사용자의 웹 페이지 방문순서에 때해 하나의 페이지에서 다음 페이지로 link를 따라 움직이는 경우 순차 데이터에 해당되지만 시계열 데이터는 아닐 수도 있다.

이러한 순차데이터의 예는 매우 광범위하여 그 쓰임새가 매우 넓다. 예컨대 사람의 대화를 각종 언어 요소 (발성요소)의 순서로 보고 분석하기도 하고 최근 관심을 모으는 각종의 생명데이터 분석 (Bioinformatics)과 관련한 것들도 들 수 있다.

즉, 유전자 정보에서의 4가지의 nucleotides (핵산의 구성요소)를 들 수 있다. |S|=4

예: AACTGACCTGGGCCCAATCC

또는 단백질을 20가지의 아미노산의 순차데이터로 볼 수도 있다 |S|=20

 

기타의 예는 다음과 같다.

  •   통신망: 통신에서의 각각의 패킷 데이터, 침입탐지를 위한 패킷분석
  •   소매거래: 소비자 동향,  e-store에서의 session정보 (예: Amazon)
순차데이터에 대한 분석
순차데이터 마이닝 개요

순차 패턴분석은 상징적 패턴(symbolic pattern)과 함께 다음의 몇몇 요인도 중시한다.

(1) 시간순차의 지속기간 (duration) T – 지속기간은 데이터베이스에서 특정 사건 전후의 매 1주일 또는 1개월과 같이 분할된 순차의 집합으로 정할 수 있는데 이를 통해 주기패턴 (periodic pattern)을 발견하고자 한다.

(2) 사건 접음 윈도우 (event folding window) – 특정 기간 내에 발생하는 사건의 집합을 분석하면 이들이 본질적으로 연관된 패턴을 구성함을 발견할 수 있다. 만약 윈도우의 크기를 w라 할 때 (예컨대 24시간 내에…) 이 거래들은 그 기간 내에 발생된 것으로서 이들 순차를 묶어서 처리하게 된다.

(3) 시간 간격 (interval) int – 발견된 패턴에 있는 시간들 사이의 시간 간격으로서 만약 int = 0로 설정하면 간격을 설정하지 않는 즉, 엄격하게 순차적으로 발생하는 것만을 의미하게 된다.

한편 순차데이터에 대한 분석활용은 목적에 따라 달라지겠으나 일반 거래데이터와 공통되는 활용과 특유하게 활용 시 감안되는 항목이 있다.

  •   전통적 방식
  •   분류
  •   군집
  •   반복패턴의 분석
  •   sequence 데이터 처리를 위한 요소
  •   Sequence 각각에 대한 분석
  •   Partial sequence 분류 (Tagging)
  •   sequence에 대한 구분 (segmentation)
  •   sequence에서 다음 출현할 부호에 대한 예측
순차데이터 분석기법

순차데이터에 대한 분석기법은 초기에 Agrawal & Srikant가 개발한 Apriori 부류의 알고리즘이 주류를 이루었는데 그 기본형태는 다음과 같다.

<수식>

If a sequence S is not frequent

Then none of the super-sequences of S is frequent

 

이후 이를 응용한 Apriori기반의 GSP 알고리즘이 개발되어 많이 사용되었고 이후 이를 응용한 다음의 알고리즘이 큰 인기를 끌고 있다.

  •   GSP 알고리즘
  •   Equivalence class를 이용한 순차패턴의 발견  (SPADE)
  •   Apriori 알고리즘
  •   FreeSpan
  •   PrefixSpan
  •   MAPres

 

이 글은 카테고리: Hadoop과 Analytics에 포함되어 있습니다. 고유주소를 북마크하세요.