K-means clustering

•       주어진 데이터를 k개의 cluster로 묶는 알고리즘

•       각 cluster 내 데이터들의 분산이 최소화하도록 학습

•       목표: cluster의 assignment {Zi}와 cluster center {𝜇j} 계산

 

 

• unsupervised learning의 대표적 ex.
  • 데이터를 k개의 clustering 묶음
  • 100개의 점을 3개의 cluster로

 

• 좋은 clustering의 기준
  • 각 cluster 내 data의 분산의 최소화
  • (평균 - 데이터)^2
    • 중심과 해당 cluster 내 모든 data의 center와의 거리의 제곱

 

• cluster의 assignment {zi}, cluster center {𝜇j}
  • zi: xi의 cluster label
  • ex. k=3
  • zi = {1, 2, 3}

 

• k-means loss function
  • -means가 얼마나 clustering이 잘 되었는지를 정의하는 loss f

  • 

  • zi와 𝜇i가 learning parameters
  • 해당 loss function은 분산을 구하는 function
    • Euclidean distance의 square
    • 𝜇: 중심 point(centroid)

 

 

• optimizer
  • 여기서는 z와 𝜇를 둘 다 update
  • 둘 다 update를 동시에 하기 어려우니 각각 별도  step에서 처리

 

• 1. Z assignment step (어디에 assign 되는지 찾는 step)
  • 각 data에 대해 어느 centroid에 가까운지 결정
  • 𝜇를 고정
  • z를 찾음     
  • 각 data에 대해 cluster center가 가장 가까운 cluster에 할당
    • zi <- arg min || pi(xi) -  𝜇k||^2
      • k=1, ...k
    • 가장 가까운 center를 찾아서 해당 center로 assign 해야 분산이 가장 작아짐
    • arg min
    • 우측 수식을 최소로 만드는 k 값을 리턴
• 2. 𝜇 update step
  • z는 고정
  • 𝜇를 찾음
    • Cluster에 속하는 데이터들의 평균 값으로 centroid를 update
    • cluster를 이루는 sample들의 평균으로 center를 이동