Machine Learning/Model

[ML] K-means clustering

파송송 2022. 9. 6. 16:30
728x90

Clustering (비지도 학습)

  • 주어진 데이터의 집합을 유사한 데이터들의 그룹으로 나누는 것
  • 이렇게 나누어진 유사한 데이터의 그룹을 군집 cluster라고 함

cluster 거리

K-means

장점

  • 비교적 구현하기 간단함
  • 레이블 된 학습 데이터가 필요하지 않음(비지도 학습의 특성)
  • 새로운 데이터의 클러스터를 찾을 때 계산량이 적음

단점

  • 차원이 커질수록 거리를 이용하여 clustering 하는 것은 정확도가 떨어짐
  • 초기 중심 값에 민감한 반응을 보임
  • 노이즈와 아웃라이어에 민감함
  • k를 구하기 어려움

비지도 학습

  • clustering은 비지도 학습의 일종
  • 종속 변수 y 가 존재하지 않고, 독립 변수 x간의 관계에 대해 모델링 하는 것
  • 군집 분석 : 유사한 데이터 끼리 그룹화 시키는 것
  • PCA : 독립 벽수들의 차원을 축소 시키는 것

종류

  • K - means clustering : 데이터를 사용자가 지정한 k개의 군집으로 나눔
  • Hierarchical clustering 계층적 군집 분석 : 나무 모양의 계층 구조를 형성해 나가는 방법
  • DBSCAN : k개를 설정할 필요없이 군집화 할 수 있는 방법

K-means clustering

  • 각 군집에 할당된 포인트들의 평균 좌표를 이용해 중심점을 반복적으로 업데이트하는 방법

step

  1. k개의 임의의 중심점(centroid)을 배치함
  2. 각 데이터들을 가장 가까운 중심점으로 할당하여 군집을 형성함
  3. 할당된 군집을 기반으로 새로운 중심 계산, 중심점은 군집 내부 점들 좌표의 평균(mean)으로 함
  4. 각 cluster의 할당이 바뀌지 않을 때까지 반복함
  5.  

거리 측정하기

Manhattan distance

  • 각 축에 수직으로만 이동하여 거리를 계산하는 방식

Euclidean distance

  • 점과 점 사이의 가장 짧은 거리를 계산하는 거리 측정 방식

 

K 찾기

  • 군집의 개수, hyperparameter이기 때문에 최적의 k를 구해야함
  • Elbow method, Silhouette method

Elbow method

  • \( ratio =  \frac{BSS}{TSS} = \frac{TSS - WSS}{TSS}  \)
  • 군집간 분산(BSS Between cluster Sum of Squares)과 전체 분산(TSS = BSS + WSS)의 비율
  • ratio가 클수록 좋음( 군집이 잘 잡혀있다면 각 군집간의 거리가 멀어지기 때문) 
    • WSS Within cluster Sum of Squares
      • 객체 \( x_{i} \)와 군집 \( j \)의 중심 \( c_{j} \)와의 거리 제곱합
      • \( \sum_{j=1}^K  \sum_{i \epsilon c_{j}} d(x_{i},c_{j})^{2}  \)
    • TSS Total Sum of Squares
      • 객체 \( x_{i} \)와 전체 데이터의 중심 \( c \)와의 거리 제곱합 (전체 데이터의 분산)
      • \( \sum_{i=1}^Nd(x_{j}, c)^{2}  \)

  • 군집이 잘못 잡혀있다면 WSS가 커진다

ratio

 

  • 분산의 비율 증가가 줄어드는 지점인 k = 4 가 적절한 클러스터 개수

 

WSS

  • WSS가 줄어드는 지점인 k = 3가 적절한 클러스터 개수

Silhouette method

  • \( s(i) =  \frac{b(i) - a(i)}{max\{{a(i), b(i)\}}} , where -1 <= s(i) <= 1 \)
  • 객체와 그 객체가 속한 국집의 데이터들과의 비유사성 (dissimilarity)을 계산하는 방법으로, elbow method에 비해 상대적으로 간단함
  • 값이 1에 가까울 수록 올바르게 cluster가 된 것임
    • \( a(i) \) : 객체 \( i \) 와 그 객체가 속한 군집의 데이터들과의 비유사성
      • \( a(i) =  \frac{1}{|g(x_{i})|-1} \sum_{j \epsilon g(x_{i})} d(x_{i}, x_{j}) \)
      • \( b(i) \) : 그 객체가 속하지 않은 다른 군집의 모든 데이터들과의 비유사성의 최솟값
        • \( b(i) = min_{k}( \frac{1}{|g_{k}|} \sum_{j \epsilon g_{k}} d(x_{i}, x_{j})) \)

 

k = 3일 때, 최적의 k이다.

K-medoids clustering

  • k-means clustering의 변형으로, 군집의 무게 중심을 구하기 위해 데이터의 평균 대신 중심점 (medoids)을 사용함
  • k-means보다 이상치에 강건한 성능을 보임
  • 데이터 간의 모든 거리 비용을 반복하여 계산하기 때문에 상대적으로 k-means 보다 많은 시간이 소요됨

728x90