10장. 군집화 오일석, 패턴인식, 교보문고, 2008. © 오일석, 전북대학교 컴퓨터공학.

Presentation on theme: "10장. 군집화 오일석, 패턴인식, 교보문고, 2008. © 오일석, 전북대학교 컴퓨터공학."— Presentation transcript:

1 10장. 군집화 오일석, 패턴인식, 교보문고, 2008. © 오일석, 전북대학교 컴퓨터공학

2 군집화clustering 구현에는 두 가지 필요
들어가는 말 패턴인식 문제로 공식화 가능 고객이 샘플, 샘플은 특징 벡터 x=(x1,x2,…,xd)T로 표현 직업, 월평균 구매액 등이 특징이 됨 유사한 (거리가 가까운) 샘플 집합을 군집이라 함 군집화clustering 구현에는 두 가지 필요 1) 거리 척도, 2)유사한 샘플을 군집으로 만드는 알고리즘

3 들어가는 말 지도 학습 과 비지도 학습 지도 학습supervised learning
2~7장에서 공부한 분류기 학습 (MLP, SVM, HMM 등) 각 샘플이 그가 속한 부류를 알고 있다. (훈련 집합 X={(x1,t1), (x2,t2), …, (xN,tN)}으로 표기) 비지도 학습 unsupervised learning 샘플은 부류 정보가 없다. (X={x1, x2, …, xN}으로 표기) 군집화는 비지도 학습에 해당 군집이 몇 개인지 모르는 경우도 많다. 군집화를 부류 발견 작업이라고도 부른다.

4 들어가는 말 군집화의 특성 주관성: 군집화 결과의 품질은 응용이 처한 상황과 요구 사항에 따라 다름

5 10.1 정의

6 10.2 거리와 유사도

7 10.2.1 특징 값의 종류 특징 값의 종류는 다양하다. (군집화를 공부하는데 이에 대한 이해가 필요하다.)

8 고객 레코드 (샘플)을 12개의 특징으로 표현한다고 하자.

9 10.2.2 거리와 유사도 측정 Hamming 거리 Minkowski 거리 (10.4)
두 점 xi=(xi1,…,xid)T와 xj=(xj1,…,xjd)T간의 거리 척도 p=2면 유클리디언 거리 (10.5), p=1이면 도시블록 거리 (10.6) Hamming 거리 이진 특징 벡터에 적용 가능 (서로 다른 비트의 개수) 예) (1,0,1,0,0,0,1,1)T과 (1,0,0,1,0,0,1,0)T의 해밍 거리는 3

10 10.2.2 거리와 유사도 측정 이진 특징 벡터의 유사도 유사도와 거리는 쉽게 상호 변환할 수 있다. 코사인 유사도
문서 검색 응용에서 주로 사용 (단어가 특징, 출현 빈도가 특징 값) 이진 특징 벡터의 유사도 유사도와 거리는 쉽게 상호 변환할 수 있다.

11 10.2.3 점 집합을 위한 거리 점과 군집 사이의 거리 (모든 샘플이 참여)
여기에서는 점과 점 집합 또는 두 점 집합 간의 거리 ( 절은 두 점간의 거리 정의) 점 xi와 군집 (점 집합) cj 간의 거리를 D(xi,cj)로 표기 두 군집 ci 와 cj 간의 거리는 D(ci,cj)로 표기 점과 군집 사이의 거리 (모든 샘플이 참여) dik는 xi와 yk는 간의 거리 (yk는 cj에 속한 샘플) Dmax와 Dmin은 외톨이에outlier 민감

12 10.2.3 점 집합을 위한 거리 점과 군집 사이의 거리 (대표 샘플만 참여) 평균을 대표로 삼음
다른 것들과 가장 가까운 샘플을 대표로 삼음

13 (rep=3이 됨)

14 점 집합을 위한 거리 두 군집 사이의 거리 dkl는 xk와 yl 간의 거리 (xk는 ci, yl은 cj에 속한 샘플)

15 10.2.4 동적 거리 샘플마다 특징 벡터의 크기가 다른 경우 예) 온라인 필기 인식, DNA 열
(6.3 절의) 교정 거리 활용

16 10.3 군집화 알고리즘의 분류 매우 다양한 알고리즘 군집화 문제의 본질적인 성질에 기인 (주관이 많이 개입되는 성질)

17 10.3 군집화 알고리즘의 분류 분류 체계 계층 군집화: 군집 결과를 계층을 나타내는 덴드로그램으로 표현
분할 군집화: 각 샘플을 군집에 배정하는 연산 사용 신경망: SOM, ART 통계적 탐색: 시뮬레이티드 어닐링, 유전 알고리즘 등

18 10.4 계층 군집화

19 샘플 각각이 군집이 되어 출발, 유사한 군집을 모으는 작업을 반복
응집 계층 알고리즘 샘플 각각이 군집이 되어 출발, 유사한 군집을 모으는 작업을 반복 출력은 군집화 결과를 트리로 표현한 덴드로그램

20 일곱 개의 샘플이 주어진 상황 (라인 1의) 초기화에 의해,

21 루프를 반복하면, (거리 척도는 유클리언 거리와 Dmin을 가정)
연필을 들고 직접 계산해 보자. 직접 해보는 것의 힘은 생각보다 크다. Dmin대신 Dmax를 사용하면 어떻게 될까?

22 사용하는 거리 척도에 따라 다른 이름의 알고리즘
응집 계층 알고리즘 사용하는 거리 척도에 따라 다른 이름의 알고리즘 Dmin 사용하면 단일 연결single-linkage, Dmax 사용하면 완전 연결complete-linkage, Dave 사용하면 평균 연결average-linkage 알고리즘 세 알고리즘의 동작 특성 단일 연결은 긴 군집, 완전 연결은 둥근 군집을 선호 (평균 연결은 중간) 예) 그림 10.10

23 10.4.1 응집 계층 알고리즘 세가지 부연 설명 군집의 개수를 어떻게 알아낼까? 모든 군집화 알고리즘이 안고 있는 문제임
사용자가 지정 또는 자동 결정 (자동 결정은 어렵다.) 단일 연결과 완전 연결은 외톨이에outlier 민감 평균 연결은 외톨이에 덜 민감 계산 복잡도 세제곱에 비례하므로 효율적인 구현 필요 CURE, ROCK, CHAMELEON, BIRCH 등 [Xu05]

24 10.4.2 분열 계층 알고리즘 분열 계층은 하향 방식top-down
모든 샘플이 하나의 군집으로 출발, 군집을 나누는 작업을 반복 (앞 절의 응집 계층은 상향 방식bottom-up: 샘플 각각이 군집이 되어 출발, 유사한 군집을 모으는 작업을 반복) 지수적 복잡도

25 10.5 분할 군집화partitional clustering
다양한 알고리즘 순차 알고리즘 k-means 알고리즘 MST알고리즘 GMM 알고리즘 …

26 10.5.1 순차 알고리즘 특성 군집 개수를 찾아준다. (대신 임계값을 설정해주어야 한다.)
순서에 민감하다. 빠르다 (선형 시간).

27 10.5.2 k-means 알고리즘 특성 가장 널리 쓰인다. (직관적 이해. 구현 간편) 군집 개수를 설정해주어야 한다.

28 7개 샘플을 k=3개의 군집으로 만드는 상황 초기화에 의해 (그림 10.12(a)), 라인 5에 의해
(그림 10.12(b)),

29 세 번째 루프는 그 이전과 결과가 같다. 따라서 멈춘다. 결국 출력은
두 번째 루프를 실행하면 (그림 10.12(c)), 세 번째 루프는 그 이전과 결과가 같다. 따라서 멈춘다. 결국 출력은

30 10.5.2 k-means 알고리즘 이론적 배경 (10.23)을 비용 함수로 하는 내리막 경사법의 일종
항상 지역 최적점으로 수렴한다. (전역 최적점 보장 못함) 초기 군집 중심에 민감 빠르다. 외톨이에 민감하다. (k-medoids는 덜 민감) (진파랑은 k-medoids, 연파랑은 k-means)

31 샘플로부터 가우시언을 추정하고 그 결과에 따라 군집 배정
모델 기반 알고리즘 샘플로부터 가우시언을 추정하고 그 결과에 따라 군집 배정 가우시언 추정은 EM 알고리즘을 사용할 수 있다.

32 10.6 신경망 신경망 지도 학습: 퍼셉트론, 다층 퍼셉트론 (4 장) 비지도 학습 (군집화): SOM, ART (10 장)

33 자기 조직화 맵self-organizing map (SOM)
자기 조직화 맵 자기 조직화 맵self-organizing map (SOM) 샘플들을 상호 비교하며 스스로 군집을 조직해 냄 경쟁 학습을 사용 하나의 샘플이 입력되면 여러 대표 벡터가 경쟁 가장 가까운 벡터가 승자가 되어 그것을 취함 (승자 독식 전략) 승자는 그 샘플에 적응하는 방향으로 벡터 값을 조금 변화시킴

34

35 10.6.1 자기 조직화 맵 SOM 학습 규칙 (10.25)에 의해 wnew는 wold보다 x에 가깝게 된다.

36

37

38

39