k-Means Clustering

k-Means 클러스터링은 비지도 학습(Unsupervised Learning) 알고리즘 중 하나로 데이터를 유사도를 바탕으로 k개의 그룹으로 구분하는 알고리즘이다. 레이블이 없는 데이터 집합에서 분류 작업을 할 때 유용하게 사용된다. 이 글에서는 k-Means의 기초적인 개념을 바탕으로, 간단하게 구현하는 과정을 소개한다.

관련 키워드: k-Means, 클러스터링, 기계학습, node.js

k-Means 알고리즘이란?

k-Means 알고리즘은 비지도 학습(Unsupervised Learning)의 한 종류로 레이블 되어있지 않은 데이터를 k개의 군집으로 클러스터링해주는 알고리즘이다.

k-Means의 장점

구현하기가 비교적 간단하다
사전 레이블된 학습 데이터가 필요하지 않다 (클러스터링의 일반적인 장점)
새로운 데이터의 클러스터를 찾을 때 계산량이 적다

k-Means의 단점

초기에 군집 수를 설정하기 때문에 k의 값에 따라 정확도가 달라진다
학습 후 초기 학습한 군집 수를 변경이 불가능하기 때문에 데이터 증가에 따라 새로운 클러스터를 형성하는 것은 불가능하다

nodeml을 사용한 k-Means 알고리즘 실험

아래의 코드는 nodeml 라이브러리를 사용하여 kMeans 알고리즘을 사용하는 예제이다.

'use strict';

const {sample, kMeans, evaluate} = require('nodeml');
const bulk = sample.iris();

let kmeans = new kMeans();
kmeans.train(bulk.dataset, {k: 3});
result = knn.test(bulk.dataset);

console.log(result);

k-Means 구현하기

k-Means 알고리즘은 아래와 같은 순서로 진행된다.

클러스터 중심점 초기화
Expectation
Maximazation
왜곡 측정 (J)
J 값이 최소화 될 때 까지 2~4 반복

이 과정 중 Expectation과 Maximazation 과정을 EM 알고리즘이라고 한다. 클러스터의 중심점을 초기화 하는 방법은 여러가지가 있지만, 현재 nodeml에는 데이터 집합에서 무작위 선택으로 초기화하는 방법만 구현해놓았다.

데이터 집합

과정을 살펴보기 위해 iris 데이터 집합을 사용한다. nodeml을 설치한후 내장되어있는 iris 데이터 집합을 불러온다.

'use strict';

const {sample} = require('nodeml');
const dataset = sample.iris().dataset;

클러스터 중심점 초기화

위키를 참조하면 Random Partition, Forgy, MacQueen, Kaufman 등 클러스터 중심점을 초기화 하는 기법들이 다양하게 존재하는 것을 확인 할 수 있다. 이 글에서는 단순히 무작위로 초기 중심점을 설정하여 학습하는 방법으로 kMeans를 구현할 예정이다.

const k = 3;
let center = [];
let preRand = {}; // 중복된 center가 존재하지 않도록 점검
while(true) { // k개의 데이터가 선택될 때까지 실행
    let rand = Math.floor(Math.random() * dataset.length);
    if(preRand[rand]) continue;
    if(dataset[rand]) {
        center.push(dataset[rand]);
        preRand[rand] = true;
    }
    if(center.length == k) break;
}

console.log(center);

위의 코드를 실행해보면 3개의 중심점이 랜덤으로 선택되어 출력되는 것을 확인 할 수 있다.

거리 측정 함수

expectation 과정을 수행하기 위해서는 중심점과 데이터의 거리 측정 함수가 필요하다. 거리를 측정하는 방법에는 여러가지가 있지만 간단히 Euclidean Distance를 측정하는 함수를 만들어 사용하도록한다.

let distance = (x, y)=> {
    let sum = 0;
    let keys = {};
    for(let key in x) keys[key] = true;
    for(let key in y) keys[key] = true;

    for(let key in keys) {
        let xd = x[key] ? x[key] * 1 : 0;
        let yd = y[key] ? y[key] * 1 : 0;
        sum += (xd - yd) * (xd - yd);
    }

    return Math.sqrt(sum);
};

Expectation

Expectation 과정은 선정된 k개의 중심점으로부터 데이터와의 거리를 측정하여 각 데이터들이 어느 클러스터에 소속되는지를 찾는 과정이다. 아래는 r[n]을 n번째 데이터의 기대값으로 설정하여 전체 데이터의 기대값을 갱신하는 코드이다.

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

Maximazation 과정은 계산된 기대값을 바탕으로 중심점을 최적화하여 업데이트하는 과정이다. 기대값 계산을 통해 클러스터에 속한 데이터들을 찾고, feature의 평균값을 계산하여 중심점을 업데이트한다.

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

왜곡 측정값(J)는 전체 데이터에서 가장 가까운 중심점과의 거리들을 계산하여 더한 값이다. J 값이 최소화되는 시점까지 데이터를 순회하면서 최적의 중심값을 찾는다. 아래의 코드에서는 J값이 이전값과 비교하여 변하지 않을 때까지 루프를 순회하도록 하였다.

let preJ = 0;
while(true) {
    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;
    }

    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];
        }
    }

    // 왜곡 측정
    let J = 0;
    for(let n = 0 ; n < dataset.length ; n++) {
        let x = dataset[n];
        let minDist = -1;
        for(let k = 0 ; k < center.length ; k++) {
            let dist = distance(dataset[n], center[k]);
            if(minDist === -1 || minDist > dist) {
                minDist = dist;
            }
        }
        J += minDist;
    }

    // 이전값과 비교하여 차이가 없으면 종료
    let diff = Math.abs(preJ - J);
    if(diff <= 0) break;
    preJ = J;
};

아래의 그림은 중심값을 최소화한 후 이터레이션을 돌면서 중심점이 변화되는 것을 보여주는 그림이다. 큰 원이 중심점이고 작은 원들은 클러스터에 소속된 데이터들인데 EM 과정을 거치면서 중심점이 이동하는 것을 확인 할 수 있다.

kmeans

참고자료

https://ko.wikipedia.org/wiki/K-%ED%8F%89%EA%B7%A0_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98
http://norman3.github.io/prml/docs/chapter09/1.html
http://sanghyukchun.github.io/69/

k-Means Clustering

k-Means 알고리즘이란?

k-Means 구현하기

이것이 좋아요:

관련

댓글 남기기 응답 취소

k-Means 알고리즘이란?

k-Means 구현하기

SNS 공유

이것이 좋아요:

관련

댓글 남기기 응답 취소