[ML] K-means clustering

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 보다 많은 시간이 소요됨