패턴인식 개론 Ch.8 클러스터링

학습목표 데이터 마이닝(data mining) : 각종 데이터 속에 숨어있는 패턴, 규칙, 관계 등의 정보를 자동으로 탐색하고 데이터 간의 연관을 발굴(mining)해 내는 인공지능, 공학 및 통계 기법을 연구하는 학문 분야이다. 이 장에서는 데이터 마이닝의 시작이라고 할 수 있는 같은 패턴끼리 모아주는 클러스터링(Clustering) 방법에 관하여 설명한다. 실습에서는 임의의 데이터에 대하여 k-means 알고리즘을 이용하여 직접 클러스터링 시뮬레이션을 해본다.

교사 학습 vs. 비교사 학습 교사/감독 학습 (supervised learning) - {x, ω} 관측된 자료가 특징 벡터 x 와 관측 값이 속해있는 클래스 ω 로 이루어진 변수 쌍 {x, ω}으로 구성될 경우의 학습은 특징벡터와 정확한 답이 주어졌기 때문에 교사/감독 (supervised : 교사와 함께 훈련한) 학습이라고 한다. 모수적 또는 비모수적 방법을 통해서 각 클래스의 확률밀도를 추정하여 분류기에 사용한다. 비교사/무감독 학습 (unsupervised learning) - {x} 클래스 라벨 ω 가 주어지지 않고 특징 벡터 x={x1, x2,...,xN } 만으로 이루어진 데이터 집합이 주어질 경우의 학습은 정확한 답은 제공 받지 못하므로 비교사/무감독 (unsupervised : 교사 없이 훈련한) 학습이라고 한다. 모수적 방법 비모수적 방법 비교사 학습이 유용한 경우 1) 데이터 마이닝과 같이 원천적으로 데이터에 대한 클래스 라벨들이 주어지지 않을 경우 2) 많은 데이터 집합들이 작은 프로토타입(원형) 집합으로 압축되어 질 수 있는 경우 3) 표본의 수가 너무 많아서 각 표본마다 일일이 라벨링하는 것이 비용이 많이 드는 지루한 과정일 경우

비교사학습의 두가지 접근법 모수적 (parametric) 방법 (혼합 모델 구축을 통한 방법) 이 방법은 여러 개의 모수적 확률밀도함수(주로 가우시안)를 혼합하여 주어진 확률밀도함수를 모델링하는 방법으로 아래 식과 같이 모델링 되며, 모델 파라미터를 찾는 것이 목적이다. 이 방법을 “모수적 혼합 모델(parametric mixture models)”이라고 한다. 비모수적 (non-parametric) 방법 이 방법은 주어진 데이터에 대한 어떠한 가정도 하지 않고 정해진 수의 클러스터들로 데이터를 나누는 방법으로 군집화 (클러스터링)라고 한다. 이 방법은 파라미터 최우추정(MLE)과 밀접하게 관련되어 있다.

클러스터링 아래의 좌측 그림처럼 분산된 데이터 집합은 수많은 특징 벡터들로 이루어져 있다. 이들 데이터 집합을 그룹들 혹은 클러스터들로 나누어 각 클러스터의 중심의 대표 벡터로 할당하려고 한다. 이러한 대표벡터들의 개 수 K는 미리 정해져 있어야 한다. 즉, K는 결정적이지 않다. 아래의 우측의 그림은 2차원 유클리디안 공간상에서 K=8 의 영역으로 공간을 분할한 그림이다. 이 중심벡터들의 위치는 검은 점으로 보여주고 있는데, 클러스터에 사상되는 특징벡터들은 클러스터링 되었다고 말한다.

클러스터링 비모수 군집화의 세가지 단계 1) 표본간의 유사(또는 차이)정도를 측정방법 정의 2) 군집화를 위한 결정함수 정의 3) 결정함수를 최대화(또는 최소화) 시키는 알고리즘 정의 특징벡터 집합 x가 새로운 벡터집합 y로 군집화되는 과정은 특징벡터들 간에 정의된 거리척도(distance measure) 또는 측량(metric)과 깊은 관련이 있다. 유클리디안 자승거리 중심평균 N개의 벡터에서 전체 왜곡 알고리즘 종류 k-means 알고리즘 비균일 이진 분할(non-uniform binary split) 알고리즘 k-means 알고리즘에 따른 이진 분할 알고리즘: LBG 알고리즘

k-means 알고리즘과 EM알고리즘 ■ k-means 알고리즘 다음과 같이 주어지는 평균자승오차(Mean Squared Error) 규준함수 JMSE 를 반복적인 스타일로 최소화시키는 가장 단순한 군집화(clustring)과정이다. 클러스터의 개수 K 를 결정 임의의 클러스터 중심을 할당하여 클러스터 초기화 각각의 클러스터에 대하여 표본 평균을 새로 구함 각각의 표본을 가장 근접한 평균을 갖는 클러스터로 다시 할당함 모든 표본에 변화가 없으면 알고리즘 중지 또는 3번 단계로 이동하여 계속 수행

k-means 알고리즘과 EM알고리즘 ■ k-means 알고리즘의 계산 절차 중심 초기화 : 데이터 집합 {x1,…,xN} 으로부터 임의의 K개의 벡터를 선택하여 K개의 초기 중심집합 {y1, …,yK} 을 만든다. 클러스러링 단계 : 만약 데이터 xn 이 yi 에 가장 가깝다면 클러스터 X i 에 속하도록 라벨링한다. 결국 데이터 집합을 K개의 클러스터들 {X1, …, XK}로 나누어진다. 중심갱신 단계 : 클러스터링 단계에서 구한 새로운 클러스터들에서 각각의 중심을 갱신한다. 왜곡검증 단계 : 데이터와 가장 가까운 클러스터 중심들과 거리의 합으로 총 왜곡 (distortion)을 구한다. 총 왜곡이 적절하게 변하지 않거나 설정된 반복횟수에 도달할 때까지 단계2~단계4를 반복한다. 왜곡 검증 예 :

비균일 이진 분할 ■ 비균일 이진 분할 계산 절차 한 개의 클러스터 X1과 관련된 중심이 y1=c(X1)인 모든 데이터 점들 xn으로 시작한다. 클러스터 카운트는 k=1으로 둔다. K 개의 중심들을 얻기 위해서 3 ~ 6단계를 (K-1)번 반복한다. 클러스터 내의 점들과 중심의 평균 거리로 측정된 가장 큰 왜곡을 가진 클러스터 Xi 를 선택한다(비균일 알고리즘). (균일 알고리즘의 경우는 모든 클러스터를 차례대로 선택한다). 선택된 클러스터 Xi 를 K=2로 k-means를 행하여 두 개의 부-클러스터 Xa 와 Xb로 나눈다. 중심 yi 를 대치하고 새로운 중심을 다음과 같이 둔다. yi = c(Xa) yk+1 = c(Xb) 클러스터 카운트를 증가 시킨다. k  k+ 1

군집화 알고리즘 종류 군집화 알고리즘 세가지 k-means 알고리즘 비균일 이진 분할 (non-uniform binary split) 알고리즘 LBG 알고리즘 ( k-means 알고리즘에 따르는 이진 분할 알고리즘 ) : k-means의 초기값을 랜덤 데이터 점으로 하는 대신에 이진 분리로 구한 중심을 사용하면 표준 k-means 방법을 사용하는 경우보다 더 나아질 것이다. 이와 같이 이진 분할과 k-means를 결합된 알고리즘을 LBG 알고리즘이라고 한다. LBG는 Linde, Y., A. Buzo, and R. M. Gray 세 명의 연구자 이름의 첫 문자를 의미한다. .

ISODATA ■ ISODATA ( Iterative Self-Organizing Data Analysis Technique Algorithm ) 자기 발견적 학습법을 통해서 자동적으로 군집의 개수를 선택하는 k-mean 알고리즘의 확장된 방법이다. ISODATA 알고리즘은 사용자로부터 일련의 파라미터를 선택하도록 요구한다. NMIN_EX : 군집당 최소 표본 수 ND : 대략적으로 요구되는 군집 개수 σs2 : 분리가 요구되는 최대 분산 파라미터 DMERGE : 결합이 요구되는 최대 분리 거리 NMERGE : 걸합될 수 있는 최대 군집 수 알고리즘은 다음과 같이 반복적으로 작동된다. K-means 군집화를 수행한다. 충분이 다른 표본들로 구성된 군집을 분리한다. 충분이 근접한 두 개의 군집을 결합한다. ①-과정으로 돌아 간다.

MATLAB 실습 ■ k-means 알고리즘을 이용한 시뮬레이션 ■ 왜곡 검증이 포함된 k-means 알고리즘 시뮬레이션 K-means 알고리즘에 왜곡검증을 포함한 내용이다. 실행 스크립트 파일은 vp_test.m 파일이다.

MATLAB 실습

MATLAB 실습 ■ LBG 알고리즘 을 이용한 시뮬레이션 LBG 알고리즘을 이용한 시뮬레이션으로 k-means 알고리즘보다 빠르게 클러스터링하는 과정을 확인할 수 있을 것이다.