데이터마이닝-연속규칙

개념
- 연관 규칙에 시간의 개념을 첨가하여 시간의 흐름에 따른 항목들의 상호 연관성을 탐색 - 사용자가 정의한 최소지지도를 갖는 시퀀스인 빈도가 높은 시퀀스(large sequence)를 추출하고 이들 가운데 최대 시퀀스(maximal sequence)를 찾는 것 - 동시에 구매될 가능성이 큰 상품군을 찾아내는 연관성 측정에서 시간이라는 시계열 자료의 개념이 포함되어 순차적인 구매 가능성이 큰 상품군을 찾아내는 것

I. 대용량 데이의 유용한 정보의 추출, 데이터 마이닝의 개요

가. 데이터 마이닝 연관규칙(순차패턴)의 정의

- 연관 규칙에 시간의 개념을 첨가하여 시간의 흐름에 따른 항목들의 상호 연관성을 탐색

- 사용자가 정의한 최소지지도를 갖는 시퀀스인 빈도가 높은 시퀀스(large sequence)를 추출하고 이들 가운데 최대  시퀀스(maximal sequence)를 찾는 것

- 동시에 구매될 가능성이 큰 상품군을 찾아내는 연관성 측정에서 시간이라는 시계열 자료의 개념이 포함되어 순차적인 구매 가능성이 큰 상품군을 찾아내는 것

 

나. 순차패턴의 알고리즘 단계

- 1단계 : 거래의 정렬 단계(Sort Phase)

- 2단계 : 빈도가 높은 항목집합 발견 단계(Litemset Phase)

- 3단계 : 거래 데이터베이스 변환 단계(Transformation Phase)

- 4단계 : 빈도가 높은 시퀀스 발견단계(Sequence Phase)

- 5단계 : 최대 시퀀스 발견 단계(Maximal Phase)

 

 

II. 순차패턴 알고리즘의 종류

가. 순차패턴 알고리즘의 종류

구분

항목

내용

Apriori

AprioriAll

  • 순차패턴 4단계와 5단계를 알고리즘으로 구현
  • 각각의 단계에서 후보 시퀀스를 생성, 각각의 후보 시퀀스에 대한 지지도를 구한 후 미리 정해놓은 최소 지지도 보다 작은 지지도를 갖는 후보 시퀀스들을 후보에서 제외시켜 빈도가 높은 시퀀스를 생성

AprioriSome

  • 전진 단계(forward phase)
    에서, 특정 길이의 시퀀스만을 구함

DynamicSome

  • 전진 단계에서 특정 길이의 후보 시퀀스를 구하는 것을 건너뛴다. 후보 시퀀스는 가변 단계(variable step)에 의해서 결정된다. 초기화 단계(initialization phase)에서, 후보 시퀀스들은 길이가 증가하면서 구해진다. 그 다음, 전진 단계에서, 모든 후보 시퀀스의 길이는 단계(step)의 곱으로서 구해진다

GSP

(Generalized Sequential Patterns)

  • GPS 알고리즘 단계
  1. 후보키 생성(candidate generation)
  2. 지지도 계산(support counting)
  • 순차패턴 문제에 시간제한(time constraints), 이동시간 윈도우(sliding time windows), 분류(taxonomies)를 도입하여 순차패턴 문제를 일반화.
  • 후보 생성이 지지도(support) 계산에 대한 데이터베이스의 완전한 패스의 결과로 일어남
  • GSP의 한계점
  1. 커다란 후보 시퀀스군이 연속 데이터베이스에서 생성.
  2. 마이닝시 데이터베이스 검사가 많음.
  3.  Apriori식 방법은 긴 순차형 마이닝할 때 어려움에 봉착

Pattern-Growth

FreeSpan
(Frequent Pattern-Projected Sequential PAtterN mining)

  • 빈도가 높은 패턴(frequent pattern)에 따라 자료를 투영(projection)하고, 이 자료를 통해 각각의 빈도의 수를 계산(count)하는 방법
  • 완전한 패턴을 마이닝 하지만 후보 부분시퀀스 생성 크게 줄임
  • 실질적으로 더 적은 수의 부분시퀀스 조합을 검토하고 Apriori식 GSP 알고리즘보다 훨씬 빠르게 작동
  • Apriori식 순차 마이닝의 병목현상 해소
  • FreeSpan 알고리즘을 요약
  1. S를 검사, S에서 빈도가 높은 항목을 찾고 F 리스트로 분류.
  2. 구성되는 종속적인 수준 설계

(alternative-level projection) 수행.

  • 데이터베이스를 검사 빈도 높은 항목 행렬구성
  • length-2 연속형과 항목 반복형 및 투영된 데이터베이스(projected database)에 관한 주석을 생성
  • 반복형과 투입된 데이터베이스를 생성하는 데이터베이스를 검사
  • 마이닝 해야 할 긴 후보 패턴이 있으면 투입된 데이터베이스에 대한 매트릭스 설계마이닝을 반복

PrefixSpan
(Prefix-projected Sequential PAterrN mining)

  • FreeSpan 알고리즘과 유사하게 빈도가 높은 패턴의 전위표기에 따라 자료를 투영(projection)하는 방법
  • 완전한 패턴을 마이닝 하지만 후보 부분 시퀀스 생성 노력을 크게 줄임
  • Apriori식 GSP 알고리즘과 FreeSpan보다 성능이 우수
 

 

III. 최근 연구동향

가. 시퀀스 데이터베이스에서 빈도가 높은 시퀀스를 찾는 것으로 데이터 마이닝 작업에서 매우 중요하고 폭넓은 응용 가능.

나. 고객의 범주나 다른 다차원 정보와 관련이 되어 있다면 분류되는 패턴들은 좀 더 유용할 것이므로 효과적인 마이닝 예상.

다. 최근 연구들은 데이터 마이닝 연구의 또 다른 분야로서 다차원 분석이 관심의 대상.

라. 순차 패턴 마이닝과 다차원 분석을 통합하여 다차원 순차 패턴 마이닝 알고리즘이 제안.                                         

댓글