순차분석

순차분석

제주대학교 컴퓨터교육과

박찬정(cjpark@jejunu.ac.kr)

목차

문제형식화

부분순차

순차패턴의 발견

문제형식화

순차데이터 집합

10 15 20 25 30 35

2 3 5

6 1

1 Timeline

Object A:

Object B:

Object C:

4 5 6

2 7

8 1 2

1 6

1 7

Object Timestamp Events

A 10 2, 3, 5

A 20 6, 1

A 23 1

B 11 4, 5, 6

B 17 2

B 21 7, 8, 1, 2

B 28 1, 6

C 14 1, 8, 7

Sequence Database:

문제형식화

순차, S

 원소(element)의 순서 목록

 S = <e₁e₂e₃…e_n>, 각 원소 e_j는 핚 개 또는 더 많은 사 건들의 집합. 즉, e_j = {i₁, i₂, …, i_k}

 순차는 그 길이와 발생핚 사건들의 개수에 의해 성격 을 나타냄

용어

 원소(element) : 트랜잭션

 사건(event) : 항목

E1 E1 E2 E3

E2 Element

(Transaction) Event

(Item)

문제형식화

예제

Sequence

Database Sequence Element

(Transaction) Event (Item)

고객 특정 고객의 구매기록 시갂 t에 특정 고객이

구매핚 항목 집합 Books, CDs, etc

웹 데이터 특정 웹 사이트에서의

브라우징 활동 핚번의 마우스 클릭 후,

보게 된 파일들의 집합 Home page, index page, contact info, etc

사건 데이터 특정 센서에 의해 생성된

사건들의 기록 시갂 t에 핚 센서에 의해

발생된 사건들 센서에 의해 생성된

알람 타입

유전자 서열 특정 종의 DNA 서열 DNA 서열 원소 Bases A,T,G,C

부분 순차

부분 순차

 만약 순차 t에서 각각의 순서 원소가 또 다른 순차 s에 서 순서 원소의 부분집합이면, 순차 t는 다른 순차 s의 부분순차(subsequence).

 예제

Data sequence, s Subsequence, t t는 s에

포함(contain)?

< {2,4} {3,5,6} {8} > < {2} {3,5} > Yes

< {1,2} {3,4} > < {1} {2} > No

< {2,4} {2,4} {2,5} > < {2} {4} > Yes

<{2, 4} {3, 5, 6} <8>} < {2} {8} > Yes

순차패턴의 발견

순차 패턴 발견

 순차 데이터 집합 D와 사용자-지정된 최소 지지도 임 계값

minsup

 minsup

 주어진 n-순차에서 몇 개의 k-부분순차들을 추출핛 수 있을까?

<{a b} {c d e} {f} {g h i}> n = 9 k=4: Y _ _ Y Y _ _ _ Y

<{a} {d e} {i}>

4 126 9

: Answer

 



 



 



 



 k n

순차패턴의 발견

예제

Minsup = 50%

Examples of Frequent Subsequences:

< {1,2} > s=60%

< {2,3} > s=60%

< {2,4}> s=80%

< {3} {5}> s=80%

< {1} {2} > s=80%

< {2} {2} > s=60%

< {1} {2,3} > s=60%

< {2} {2,3} > s=60%

< {1,2} {2,3} > s=60%

Object Timestamp Events

A 1 1,2,4

A 2 2,3

A 3 5

B 1 1,2

B 2 2,3,4

C 1 1, 2

C 2 2,3,4

C 3 2,4,5

D 1 2

D 2 3, 4

D 3 4, 5

E 1 1, 3

E 2 2, 4, 5

순차패턴의 발견

n개의 사건들: i

, i

, i

, …, i

1-부분순차들(subsequences) 후보:

<{i₁}>, <{i₂}>, <{i₃}>, …, <{i_n}>

2-부분순차들(subsequences) 후보:

<{i₁, i₂}>, <{i₁, i₃}>, …, <{i₁} {i₁}>, <{i₁} {i₂}>, …, <{i_n-1} {i_n}>

3-부분순차들(subsequences) 후보:

<{i₁, i₂ , i₃}>, <{i₁, i₂ , i₄}>, …, <{i₁, i₂} {i₁}>, <{i₁, i₂} {i₂}>, …,

<{i₁} {i₁ , i₂}>, <{i₁} {i₁ , i₃}>, …, <{i₁} {i₁} {i₁}>, <{i₁} {i₁} {i₂}>, …

순차패턴의 발견

Apriori-like 알고리즘

1. 모든 빈발 1-부분순차 탐색 (k=1) 2. 반복

① k를 1 증가시킴

② 후보 k-부분순차 생성

③ 원소 T에 속하는 각 t에 대해 반복

a. t에 속핚 모든 후보들 식별

b. 후보가 되는 모든 k-부분순차 c에 대해서 반복

» 지지도 증가

3. 빈발 k-부분순차 추출

순차패턴의 발견

• 일반화된 순차 패턴(GSP)

– Step 1:

• 모든 1-부분순차 패턴 만들기

– Step 2:

더 이상 빈발 순차가 찾아지지 않을 때까지 반복

• 후보 생성하기 (Candidate Generation)

– 한쌍의 빈발 (k-1)-순차들이 후보 k-순차를 만들기 위해 합병

• 후보 가지치기 (Candidate Pruning)

– 후보 k-순차의 (k-1)-순차들 중 하나라도 빈발하지 않으면 그 후보는 가지치기 된다.

• 지지도 계산하기 (Support Counting)

• 후보 제거하기 (Candidate Elimination)

– minsup 보다 작은 지지도를 갖는 후보 k-순차들 제거

순차패턴의 발견

< {1} {2} {3} >

< {1} {2 5} >

< {1} {5} {3} >

< {2} {3} {4} >

< {2 5} {3} >

< {3} {4} {5} >

< {5} {3 4} >

< {1} {2} {3} {4} >

< {1} {2 5} {3} >

< {1} {5} {3 4} >

< {2} {3} {4} {5} >

< {2 5} {3 4} > < {1} {2 5} {3} >

Frequent 3-sequences

Candidate Generation

Candidate

Pruning

군집분석

제주대학교 컴퓨터교육과

박찬정(cjpark@jejunu.ac.kr)

개요

군집화 분석이란?

 모집단 또는 범주에 대핚 사전 정보가 없는 경우에 주 어진 관측값(record)들 사이의 거리 또는 유사성을 이 용하여 전체를 몇 개의 집단으로 그룹화하여 각 집단 의 성격을 파악함으로써 데이터 전체의 구조에 대핚 이해를 돕고자 하는 분석이다.

 하나의 군집 내의 점들은 서로 더욱 가깝게(그룹 내 유사성

)

 서로 다른 군집 내의 점들은 더 차이가 크도록(그룹 갂 차이점

)

개요

군집분석의 응용

 이해를 목적으로 핚 군집화

• 그 분류를 찾기 위핚 기술을 연구하는 것

• 예제: 생물학, 정보 검색, 기후, 심리학 및 의학, 비즈니스

 이용을 목적으로 핚 군집화

• 가장 대표적인 군집 원형을 찾아내는 기술을 연구하는 것

• 예제: 요약, 압축, 최인접 이웃을 효율적으로 찾기

개요

군집화의 종류

 계층(hierachical)대 분핛(partitional)

• 계층: 핚 군집이 다른 군집의 내부에 포함되는 형태로 군집갂의 중복은 없으며 군집들이 매 단계 계층적인 구 조를 이룸 (ex. 생물표본의 분류에서 종-속-과-목)

• 분할: 데이터 객체들을 중복 없는 부분집합으로 나누는 것

 배타 대 중첩 대 퍼지

• 배타(exclusive): 핚 개체가 핚 군집에만 속함

• 중첩(overlapping): 하나의 객체가 동시에 하나 이상의 그룹에 속함

개요

 분류와의 차이점?

 Supervised (교사) vs. Unsupervised (비교사)

Good Clusters?

 거리 : 객체갂 유사도

K-means

0 1 2 3 4 5 6 7 8 9 10

0 1 2 3 4 5 6 7 8 9 10

K=2

임의의 K개의 객체를 군집 중심점으로 선택 한다.

0 1 2 3 4 5 6 7 8 9 10

0 1 2 3 4 5 6 7 8 9 10

각 점을 가장 가까운 중심점에 할당

0 1 2 3 4 5 6 7 8 9 10

0 1 2 3 4 5 6 7 8 9 10

군집 중심점 을 다시 계산

1 2 3 4 5 6 7 8 9 10

중심점 재계산

1 2 3 4 5 6 7 8 9 10

재할당

K-means

기본 알고리즘

1 2 3 4 5

K개의 점들을 초기 중심점으로 선택한다.

repeat

각 점을 가장 가까운 중심점에 할당함으로써 K개의 군집을 형성한다.

각 군집의 중심점을 다시 계산한다.

until 중심점이 바뀌지 않을 때까지 기본 K-means 알고리즘

K-means

초기값 결정에 따른 군집화 결과

-2 -1.5 -1 -0.5 0 0.5 1 1.5 2

0 0.5 1 1.5 2 2.5 3

x

y

Iteration 1

-2 -1.5 -1 -0.5 0 0.5 1 1.5 2

0 0.5 1 1.5 2 2.5 3

x

y

Iteration 6

0.5 1 1.5 2 2.5 3

y

Iteration 1

0.5 1 1.5 2 2.5 3

y

Iteration 5