uncategorized

k-means clustering

basic 개념

  1. 몇개의 centroid를 정할지 즉 K를 몇으로 할지 정해야 한다

  2. 개별 데이터들은 가장 가까운 centroid에 assign 하면 된다

  • J를 minimize 시킨다(centroid와 개별 데이터간의 거리)

  • $r_{nk}$ : 개별 데이터가 centroid에 할당되면 1, 할당되지 않으면 0 [The assignment of data points to clusters]

  • $\mu_{k}$ : centroid의 위치 (the location of centroid)

  • 두개의 파라미터가 있으므로 interactive 하게 optimization 하게 된다

Expectation, Maximization

  • Expectation

    • centroid와 가까운 데이터를 할당($r_{nk}$ 를 최적화)

$r_{nk}$ : {0, 1}

  • Maximization

    • log-likelihood를 이용해 parameter 최적화
      centroid position($\mu_k$)을 최적화시킨다

$\frac{d J}{d \mu_k} = \frac{d}{d \mu_k}\sum_{n=1}^N \sum_{k=1}^K r_{nk} \lVert x_n - \mu_k \rVert^2$

$= \frac{d}{d \mu_k}\sum_{n=1}^Nr_{nk} \lVert x_n - \mu_k \rVert^2$

$= \sum_{n=1}^N -2 r_{nk} (x_n - \mu_k)$

$= -2 (- \sum_{n=1}^N r_{nk} \mu_k + \sum_{n=1}^N r_{nk} x_n) = 0$

Problem of K-means

  1. centroid의 갯수를 잘 정해야 한다

  2. centroid의 위치를 처음에 잘 정해야 한다

  3. 유클리디안 거리를 사용해서 제약적이다

  4. Hard clustering이다

$r_{nk}$가 {0,1}뿐이면 어중간한 위치에 있는 데이터에 대해서 soft하게 하지 못하고 딱딱하게 결정을 내린다
즉 빨간점일 확률과 파란점일 확률이 반반임에도 불구하고 빨간색으로 정해버리거나 파란색으로 정해버린다

3번과 4번은 Gaussian Mixture 모델로 보완이 가능하다

Share