K-Means
  • Clustering 알고리즘
  • 비지도 학습(Unsupervised Learning)
  • 레이블 되어있지 않은 데이터를 k개의 군집으로 클러스터링
K-Means 장점
  • 구현하기가 비교적 간단하다
  • 사전 레이블된 학습 데이터가 필요하지 않다 (클러스터링의 일반적인 장점)
  • 새로운 데이터의 클러스터를 찾을 때 계산량이 적다
K-Means 단점
  • 초기에 군집 수를 설정하기 때문에 k의 값에 따라 정확도가 달라진다
  • 학습 후 초기 학습한 군집 수를 변경이 불가능하기 때문에 데이터 증가에 따라 새로운 클러스터를 형성하는 것은 불가능하다
Visualize
K-Means 구현하기
k-Means 구현 순서
  1. 클러스터 중심점 초기화
  2. Expectation
  3. Maximazation
  4. 왜곡 측정 (J)
  5. J 값이 최소화 될 때 까지 2~4 반복
클러스터 중심점 초기화
  •  무작위 분할 (Random Partition): 데이터를 무작위로 클러스터에 할당
  •  Forgy:  무작위로 k개를 선정하여 중심점으로 설정
  •  MacQueen:  무작위로 k개의 중심점 선정 후 거리순으로 클러스터에 할당정
  •  Kaufman: 전체 데이터의 중심점을 찾고, 가장 가까운 무게중심보다 할당되지 않은 데이터에 대해 가까이 있는 지점을 중심점으로 설정
Distance & Similarity
  • Euclidean Distance
  • Inner Product
  •  more...
Expectation
  • 초기 선정된 중심점 정보를 바탕으로 전체 데이터를 클러스터로 할당
let r = [];
for(let n = 0 ; n < dataset.length ; n++) {
    let x = dataset[n];
    let minDist = -1, rn = 0;
    for(let k = 0 ; k < center.length ; k++) {
        let dist = distance(dataset[n], center[k]);
        if(minDist === -1 || minDist > dist) {
            minDist = dist;
            rn = k;
        }
    }
    r[n] = rn;
}
Maximazation
  • Expectation을 통해 형성된 클러스터를 통해 중심점 재계산
center = Array.apply(null, Array(center.length));
let centerSum = Array.apply(null, Array(center.length)).map(Number.prototype.valueOf, 0);
for(let n = 0 ; n < dataset.length ; n++) {
    let k = r[n] * 1;
    let x = dataset[n];

    if(!center[k]) center[k] = {};
    for(let key in x) {
        if(!center[k][key]) center[k][key] = 0;
            center[k][key] += x[key] * 1;
    }
    centerSum[k]++;
}

for(let k = 0 ; k < center.length ; k++) {
    for(let _key in center[k]) {
        center[k][_key] = center[k][_key] / centerSum[k * 1];
    }
}

왜곡 측정 및 Iteration
  • 왜곡 측정값은 전체 데이터에서 가장 가까운 중심점들의 거리를 각각 더한 값
  • 왜곡 측정값이 임계치에 도달할 때 까지 E-M 과정을 반복함
The End