지도학습 - 군집화

군집화

비지도학습의 일종으로, 학습 데이터는 군집으로 주어지고, 학습하면서 서로소인 부분집합을 결과로 도출해냄
(로그인 인증할 때 조건에 맞는 그림 고르는것... 그것 또한 군집화의 예라고 볼 수 있다)

적용 방법론

• K-평균 굱딥화, 계층적 군집화
• 가우시안 혼합 모델, SOM(Self Organizing Feature Map)

군집화가 적용 가능한 데이터

• 클래스 레이블이 주어지지 않는 경우
• 클래스 레이블링에 비용이 많이 드는 경우

K-평균 군집화 (K-means)

주어진 데이터 집합을 K개의 그룹으로 묶는 알고리즘

WARNING

K-NN : 분류기
K-MEANS : 군집화

알고리즘

주어진 데이터 집합을 K개의 그룹으로 묶는 알고리즘

• 수행 단계: 시작(초기화) -> 데이터 그룹핑 -> 대표 벡터 수정 -> 반복 여부 결정

1. 시작(초기화)

데이터 집합{X1, X2, ... , Xn}으로부터 임의로 K개의 벡터를 선택하여 K개의 초기 대표 벡터 집합 {M1, M2, ... , Mk}를 생성함

2. 데이터 그룹핑

각 데이터 Xj (j=1, ... , N)에 대해 K개의 대표 벡터들과의 거리 d(Xj, Mk) (k=1,...,K)를 계산함
만약 데이터 Xj가 대표 벡터 Mk에 가장 가깝다면 이 데이터를 클러스터 Ck에 속하도록 레이블링함 이 과정을 통해 데이터 집합을 K개의 클러스터{C1, C2,...,Ck}로 나눔

3. 대표 벡터 수정

이전 단계에서 구한 새로운 클러스터들에서 각각의 대표 벡터를 갱신함

4. 반복 여부 결정

벡터가 더 이상 수정해도 결과가 바뀌지 않거나 설정한 반복 횟수에 도달하면 종료

TIP

K-평균 군집화 알고리즘은 목적함수 J를 극소화하는 지역 극소점을 찾는 것을 보장함

군집 간의 거리를 계산하는 방식

• 최단 연결법 : 고립된 군집을 찾는 데 유용
• 최장 연결법 : 응집된 군집을 찾는 데 중점을 둠
• 중심 연결법 : 특이값에 강건함
• 평균 연결법 : 작은 분산을 가지는 군집을 형성함
• Ward's 방법 : 비슷한 크기의 군집을 병합함