[ML Algorithm] 군집화(clustering)

1. 군집화(clustering)이란? 

•  주어진 데이터들의 특성을 고려해 데이터 집단(클러스터)을 정의하고 데이터 집단의 대표할 수 있는 대표점을 찾는 것으로 데이터 마이닝의 한 방법이다.
• 클러스터란 비슷한 특성을 가진 데이터들의 집단이다.
• 반대로 데이터의 특성이 다르면 다른 클러스터에 속해야 한다. (by 위키백과) 
• 비지도학습종류 2가지 1. 데이터 클러스터링 2. 특성 변수 관계 탐색
• -> 데이터 클러스터링? 여러번의 반복을 통해 데이터의 최적 분할을 진행하는 방법
• -> 특성 변수 관계 탐색? 각종 연관성 분석 방법을 통해 변수 사이의 관계를 찾는것 

 

 

 

2. 군집화 알고리즘 

(1)  K 평균   

• 군집 중심점(centroid)라는 특정한 임의의 지점을 선택해 해당 중심에 가장 가까운 포인트들을 선택하는 군집화기법
• 선택된 포인트의 평균지점으로 이동하고 이동된 중심점에서 다시 가까운 포인트를 선택, 다시 중심점을 평균 지점으로 이동하는 프로세스를 반복적으로 수행 
• 장단점이 명확하기 때문에 K평균 알고리즘 튜닝 필요

장점	단점
일반적으로 군집화에서 가장 많이 사용되는 알고리즘 알고리즘이 쉽고 간결	거리기반 알고리즘으로 속성의 개수가 매우 많을수록 군집화 정확도가 떨어짐(PCA 차원감소 적용) 반복을 수행하는데 반복횟수가 많을 경우 수행시간이 매우 느려짐   몇개의 군집을 선택해야할 지 가이드하기가 어려움  -> 사람이 사전에 초기 k값을 지정해 주어야 하며, 해당 값이 실제 데이터 분포와 다를 가능성 존재

 

 

* K평균 알고리즘의 단점을 개선한 모델

(1) K-means++ 알고리즘

- K평균 알고리즘은 시작할 때 데이터 세트 중에서 임의로 K개의 샘플을 군집 중심으로 설정 

- K-means++ 알고리즘은 K개 군집 중심을 설정하여 이미 n개의 초기 군집 중심을 선택했다고 가정한다면,  n+1번째 군집 중심 선택할 때 현재 n개 군집 중심에서 거리가 먼 샘플이 선택될 확률을 높게 만든다. 

 

 

(2) ISODATA 알고리즘

- K값의 크기가 불명확할 때 사용하는 알고리즘

- Iterative Self-Organiziing Data Analysis Technique Algorithm 

- 모 클래스에 속하는 샘플 수가 작아지면 해당클래스를 삭제하고 모 클래스에 속하는 샘플 수가 많아지거나 분산 정도가 비교적 크다면 해당 클래스를 두개의 하위 클래스로 나눔

- ISODATA 알고리즘은 K평균 알고리즘을 기반으로 두가지 단계를 더함 1. 분열 -> 군집 중심 수 늘리기  2. 합병 -> 군집 중심 수를 줄이기 

- 하지만 지정해야 할 파라미터의 수가 비교적 많음, 참고용 군집 개수 $K_0$ 뿐만 아니라 임곗값 3개 추가 설정 필요 

- ISODATA 알고리즘 파라미터 

(1) 예상되는 군집 중심 개수 K  (2) 각 클래스에 포함되어야 하는 최소한의 샘플개수 $N_min$ (3) 최대분산 시그마 (4) 두 군집 중심사이에 가질 수 있는 최소한의 거리  $D_min$  

 

 

 

(2)  평균이동(Mean Shift) 

• K 평균과 유사하지만 거리 중심이 아니라 데이터가 모여있는 밀도가 가장 높은쪽으로 군집 중심점을 이동하면서 군집화를 수행함
• 일반 업무 기반의 정형 데이터 세트보다 컴퓨터 비전 영역에서 이미지나 영상 데이터에서 특정 개체를 구분하거나 움직임을 추적하는데 뛰어난 역할을 수행하는 알고리즘
• 이러한 특성 때문에 업무 기반의 데이터 세트보다는 컴퓨터 비전 영역에서 잘 사용됨 

장점	단점
데이터 세트의 형태를 특정 형태로 가정한다던가, 특정 분포도 기반의 모델로 가정하지 않기 때문에 좀 더 유연한 군집화 가능  이상치의 영향력 크지 않음 미리 군집의 개수 정할 필요 없음	알고리즘의 수행시간이 오래 걸림 bandwidth의 크기에 따른 군집화 영향도가 매우 크다

 

 

 

 

(3) 가우스 혼합 모델 GMM(Gaussian Mixture Model)

GMM 군집화는 군집화를 적용하는 데이터가 여러개의 가우시안분포를 모델을 섞어서 생성된 모델로 가정해 수행하는 방식

 

Q. 가우시안분포란?

A. 좌우 대칭형의 bell 형태를 가진 통계학에서 가장 잘 알려진 연속확률함수

 

• GMM은 데이터를 여러개의 가우시안 분포가 섞인것으로 간주 ---> 섞인 데이터 분포에서 개별 유형의 가우시안 분포를 추출한다. 
• 전체 데이터 세트는 서로 다른 정규분포를 가진 여러가지 확률 분포 곡선으로 구성되어 있으며, 정규분포에 기반에 군집화를 수행하는 것이 GMM 군집화 방식
• 일정한 데이터 세트가 있으면 이를 구성하는 여러개의 정규 분포 곡선 추출 뒤, 개별 데이터가 이 중 어떤 정규분포에 속하는지 결정 
• 이러한 방식을 모수추정이라고 하며 "개별 정규 분포의 평균과 분산", "각 데이터가 어떤 정규 분포에 해당되는지의 확률"을 구하기 위해서 추정한다 
• GMM은 모수추정을 하기 위해 EM(Expectation and Maximization)방법을 적용하고 있음 

 

 

(4)  DBSCAN 

• DBSCAN(Density Based Spatial Clustering of Applications with Noise)
• 밀도 기반 군집화의 대표적 예
• 간단하고 직관적인 알고리즘으로 되어 있음에도 데이터의 분포가 기하학적으로 복잡한 데이터 세트에도 효과적인 군집화가 가능 
• 특정 공간 내에 데이터 밀도 차이를 기반 알고리즘으로 하고 있어서 복잡한 기하학적 분포도를 가진 데이터 세트에 대해서도 군집화를 잘 수행한다. 
• 아래의 복잡한 군집화도 가능!

https://kr.mathworks.com/matlabcentral/mlc-downloads/downloads/submissions/53842/versions/4/screenshot.png

 

 

 

(5)  자기 조직화 지도(Self-Organizing Map, SOM)

- (= Kohenen map) 

- 비지도학습 방법

- 자율학습의 방법으로 훈련이 되며, 저차원(보통 2차원)의 지도를 생성 

- 클러스터링, 고차원 시각화, 데이터 압축, 특성 추출 

- 생물 신경 시스템 기능을 모방하여 만들어진 일종의 인공 신경망

- SOM은 입력층과 출력층, 두개의 층으로 구성된 신경망, 입력층은 외부 입력 신호를 감지하는 망막으로 모방, 출력층은 이에 응답하는 대뇌 피질 모방 --> 출력층의 뉴런 개수는 일반적으로 군집의 개수와 같음, 클러스터링해야하는 클래스 대표 

- 훈련 시 경쟁학습 방식을 선택하여 각 입력 샘플에서의 모든 가중치와 유클리드 거리를 계산하여 최소가 되는 가장 적합한 노드 찾기 -> 활성화 노드

- 다음 확률적 경사하강법(Stochastic Gradient Descent) 사용하여 활성화 노드의 파라미터를 갱신, 동시에 활성화 노드와 인접한 점도 이들의 거리에 기반해 적절하게 파라미터 갱신 

- SOM의 두가지 네트워크 구조 (1) 1차원 모델 -> 은닉도느 1차원 직선 (2) 2차원 위상 관계 -> 2차원 평면  

 

 

 

 

 

cf) SOM과 K평균 알고리즘 차이

(1)   K평균 알고리즘은 사전에 군집개수를 설정해야 하지만 SOM은 사전에 군집개수 설정 필요 없음

 

 

3. 클러스터링 평가 척도

• 내부평가, 외부평가
• 대부분의 군집화는 비교할 만한 타깃 레이블을 가지고 있지 않음 
• 데이터내에 숨어 있는 별도의 그룹을 찾아서 의미를 부여하거나 동일한 분류 값에 속하더라도 그 안에서 더 세분화된 군집화를 추구하거나 서로 다른 분류 값의 데이터도 더 넓은 군집화 레벨화 등의 영역을 가진다. 
• 클러스터 내 높은 유사도 (high intra-cluster similarity) 를 가지고, 클러스터 간 낮은 유사도 (low inter-cluster similarity) 를 가진 결과물에 높은 점수를 줌
• 하지만!!! 데이터를 클러스터링 결과물만을 보고 판단하기 때문에 평가 점수가 높다고 해서 실제 참값에 가깝다는 것을 반드시 보장하지 않음! 

 

(1) 내부평가

# 실루엣 분석(silhouette analysis)

• 1986년 Peter J. Rousseeuw에 의해 처음으로 서술됨 
• 각 군집간의 거리가 얼마나 효율적으로 분리되어 있는지 나타앰
• 잘 분리됐다는 것의 의미? 다른 군집과의 거리는 떨어져 있고 동일 군집 끼리의 데이터는 서로 가깝게 잘 뭉쳐있다는 의미 
• 군집화가 잘 될 수록 개별 군집은 비슷한 정도의 여유 공간을 가지고 떨어져 있을 것임 

 

# Davies-Bouldin index 

• 높은 클러스터 내 유사도를 가지고 낮은 클러스터간 유사도를 가지는 클러스터들을 생성하는 클러스터링 알고리즘은 낮은 Davies-Bouldin index 값을 가지게 됨 
•  이 지표가 낮은 클러스터링 알고리즘이 좋은 클러스터링 알고리즘으로 평가

 

 

# Dunn index

• 밀도가 높고 잘 나뉜 클러스터링 결과를 목표로 함 
• 클러스터간 최소 거리와 클러스터간 최대 거리의 비율로 정의

 

 

(2) 외부평가

 

# 랜드 측정

 

 

#  F 측정

 

 

# 자카드 지수 

 

 

 

 

 

* 헷갈린다면? 

1. 유사도 관련 정리 

 

 

<출처>

1. 파이썬 머신러닝 완벽가이드, 권철민 지음 

2. 클러스터_분석 위키백과 

클러스터 분석 - 위키백과, 우리 모두의 백과사전

3.K-평균_알고리즘#클러스터링_평가_척도

4.