K-Means 클러스터링

머신 러닝 | 비지도학습( Unsupervised Learning ) | 군집화( Clustering )

머신 러닝 기법 중의 하나인 군집화( Clustering 이하 클러스터링 )는 특성이 비슷한 데이터들을 군집화 하는 것이다. 분류( Classification )와 구별이 필요하다. 클러스터링은 정답이 없는 즉, 라벨링 되어 있지 않은 데이터를 묶는 비지도 학습( Unsupervised Learning ) 방법이 일반적으로 사용된다.

여러 가지 클러스터링 알고리즘( KMeans, Hierarchical Clustering, Spectral Clustering, DBSCAN )이 있으나, 데이터의 형태에 적합한 알고리즘을 선택하는 것이 중요하다. 

클러스터링 기법 중 하나인 K-Means에 대해서 알아보자.

K-Means 란?

K-Means Clustering은 대표적인 분리형 군집화( Clustering ) 알고리즘이다. 각 cluster는 하나의 중심을 가지며 각 데이터는 가장 가까운 중심에 할당된다. 같은 중심에 할당된 데이터들이 모여 하나의 cluster를 형성한다. 사전에 군집 수( K )를 정해줘야 cluster를 만들 수 있다. 즉,  K가 하이퍼파라메터( Hyperparameter )다.

• Clustering 알고리즘.

• 비지도 학습(Unsupervised Learning).

• 레이블 되어있지 않은 데이터를 k개의 군집으로 클러스터링.

• K Means는 EM 알고리즘을 기반으로 작동함.

• EM알고리즘은 크게 Expectation과 Maximization 스텝으로 나뉘고 이를 수렴할 때까지 반복하는 방식.

• K Means 경우 (1) 각 군집 중심의 위치 (2)각 데이터가 어떤 군집에 속해야 하는지, 이 두 가지를 동시에 찾아야 하기 때문에 EM 알고리즘을 적용함.

학습과정을 보면 좀 더 이해가 쉬울 것이다.

학습과정

 

A. 클러스터 수 결정( 즉, K 결정. 여기서 K = 2 )

B. 초기 Centroid 선택
  - 랜덤 설정 / 수동 설정 / K-Means++

• 랜덤 설정 : 무작위로 Centroid를 설정하는 방법( centroid는 데이터일수도 아닐 수도 있음. )
• 수동 설정 : 임의의 값으로 Centroid를 설정하는 방법.(centroid는 데이터일수도 아닐 수도 있음. )
• K-Means++ : 전체 데이터 중에서 임의의 데이터를 Centroid로 설정하는 방법

  - 여기서 Centroid 선택 방식을 주어진 데이터에서 선택하는 방법이 K-Means++ 방식이다.

C. K개 만큼 설정된 Centroid에 가까운 데이터를 해당  Centroid로 assign

D. Centroid를 클러스터의 중심으로 이동

E. 클러스터에 assign 되는 데이터가 없을 때까지 스텝 C, D 반복

K는 어떻게 결정 할 것인가?

즉, 몇개의 Cluster를 만들 것인가? 

클러스터링을 하기 위해서는 몇개의 클러스터가 적절할지 결정해야 하는데, 그러려면 일단 “좋은 군집”이란 무엇인지 정의할 수 있어야 한다.

만약, 클러스터가 잘 되었다면 각 클러스터의 샘플이 가까운 거리에서 오밀조밀하게 묶일 거다. 클러스터 내의 데이터들이 얼마나 퍼져 있는지 (혹은 얼마나 뭉쳐있는지) 응집도는 inertia 값으로 확인한다. inertia는 각 데이터로부터 자신이 속한 군집의 중심까지의 거리를 의미하기 때문에 inertia 값이 낮을수록 군집화가 더 잘 됐다고 볼 수 있는 거다.

그럼 적절한 K에 의해 클러스터링이 얼마나 잘 되었는지 평가하는 방법에 대해서 알아 보자.

클러스터링 평가 방법

클러스터를 평가하는 방법은 크게 내부 평가와 외부 평가가 있으나 우선 내부 평가 체계인 군집타당성지표( Clustering Validity Index )에 대해서 알아보자.

 

군집타당성지표( Clustering Validity Index )

• 내부 평가 체계이며

• 군집 간 거리 / 군집의 지름 / 군집의 분산 등을 고려한다.

• Elbow, Silhouette, Dunn index 등이 있다.

Dunn Index

Dunn index는 밀도가 높고 잘 나뉜 클러스터링 결과에 대한 평가가 목표이다.

• 군집 간 거리의 최소값(하단 좌측)을 분자, 군집 내 요소 간 거리의 최대값(하단 우측)을 분모로 하는 지표.

• Dunn index 값이 클수록 즉, 군집 간 거리는 멀수록, 군집 내 분산은 작을 수록 좋은 군집화 결과.

Elbow

•  K-Means 클러스터링은 데이터와 중심과의 오차제곱합( SSE )의 값이 최소가 되도록 중심을 잡아 가는 방법.

•  클러스터의 개수를 증가 시켜가면서 SSE 값을 비교.

•  SSE 값은 클러스터 내의 데이터들이 얼마나 뭉쳐 있는지를 판단하는 값으로 값이 낮을 수록 잘 뭉쳐 있다고 볼 수 있음.

아래는 python 코드이다.

def elbow(feature):     sse = []     for i in range(1, 11):         km = KMeans(n_clusters = i)         km.fit(feature)         sse.append(km.inertia_)     plt.plot(range(1, 11), sse, marker='o')     plt.xlabel('Number of Cluster')     plt.ylabel('SSE')     plt.show()

K가 3일때 최적임을 알 수 있다.

Silhouette

아래는 Silhouette 방법을 통한 샘플 데이터다.

K-Means 클러스터링 장/단점

장점	단점
구현하기가 비교적 간단. 사전 레이블된 학습 데이터가 필요하지 않음.( 클러스터링의 일반적인 장점 ) 새로운 데이터의 클러스터를 찾을 때 계산량이 적음.	K의 값에 따라 정확도가 달라짐. 각 군집 중심의 초기값을 랜덤하게 정하는 방식으로 초기값 위치에 따라 원하는 결과가 나오지 않을 있음. 학습 후 초기 학습한 군집 수 변경이 불가능 데이터 증가에 따라 새로운 클러스터 형성 불가능 이상치(Outliers)가 많을 경우 적절한 군집화 불가능

활용 분야

• Data Mining 에서 데이터 분류 및 군집 알고리즘으로 활용

• 시장과 고객 분석, 패턴인식, 공간데이터 분석, Text Mining 등

• 최근 패턴인식, 음성인식의 기본 알고리즘으로 활용

• 개체가 불규칙적이고, 개체 간 관련성을 정확히 알 수 업슨 분류 초기 단계