K-means algorithm / Clustering 위키피디아 정리, 구현

K-means algorithm

출처 : 위키피디아 (https://ko.wikipedia.org/wiki/K-%ED%8F%89%EA%B7%A0_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98)

K-평균 알고리즘(K-means algorithm)은 주어진 데이터를 k개의 클러스터로 묶는 알고리즘으로, 각 클러스터와 거리 차이의 분산을 최소화하는 방식으로 동작한다.

이 알고리즘은 자율 학습의 일종으로, 레이블이 달려 있지 않은 입력 데이터에 레이블을 달아주는 역할을 수행한다.

이 알고리즘은 EM 알고리즘을 이용한 클러스터링과 비슷한 구조를 가지고 있다.

개요 >>

k-평균 클러스터링 알고리즘은 클러스터링 방법 중 분할법에 속한다. 분할법은 주어진 데이터를 여러 파티션 (그룹) 으로 나누는 방법이다.

예를 들어 n개의 데이터 오브젝트를 입력받았다고 가정하자. 이 때 분할법은 입력 데이터를 n보다 작거나 같은 k개의 그룹으로 나누는데,

이 때 각 군집은 클러스터를 형성하게 된다. 다시 말해, 데이터를 한 개 이상의 데이터 오브젝트로 구성된 k개의 그룹으로 나누는 것이다.

이 때 그룹을 나누는 과정은 거리 기반의 그룹간 비유사도 (dissimilarity) 와 같은 비용 함수 (cost function) 을 최소화하는 방식으로 이루어지며,

이 과정에서 같은 그룹 내 데이터 오브젝트 끼리의 유사도는 증가하고, 다른 그룹에 있는 데이터 오브젝트와의 유사도는 감소하게 된다.

k-평균 알고리즘은 각 그룹의 중심 (centroid)과 그룹 내의 데이터 오브젝트와의 거리의 제곱합을 비용 함수로 정하고,

이 함수값을 최소화하는 방향으로 각 데이터 오브젝트의 소속 그룹을 업데이트 해 줌으로써 클러스터링을 수행하게 된다.

목표 >>

n개의 d-차원 데이터 오브젝트 (x1, x2, …, xn) 집합이 주어졌을 때, K-평균 알고리즘은 n개의 데이터 오브젝트들을 각 집합 내 오브젝트 간 응집도를 최대로 하는

k ( ≤ n ) 개의 집합 S = {S1, S2, …, Sk} 으로 분할한다. 다시 말해, μi가 집합 Si의 중심점이라 할 때

     

각 집합별 중심점~집합 내 오브젝트간 거리의 제곱합을 최소로 하는 집합 S를 찾는 것이 이 알고리즘의 목표다.

이 목적 함수의 전역 최솟값 (global minimum) 을 찾는 것은 NP-난해 문제이므로, 언덕 오르기 (hill climbing) 방식으로 목적 함수의 오차를 줄여나가며

지역 최솟값 (local minimum) 을 발견했을 때 알고리즘을 종료함으로써 근사 최적해를 구한다.

표준 알고리즘 >>

i 번째 클러스터의 중심을 μ i  클러스터에 속하는 점의 집합을 S i  라고 할 때, 전체 분산은 다음과 같이 계산된다.

     

이 값을 최소화하는 S i  을 찾는 것이 알고리즘의 목표가 된다.

알고리즘은 우선 초기의 μ i 를 설정하는 것으로 시작한다. 이후 다음의 두 단계를 반복한다.

클러스터 설정: 각 데이터로부터 각 클러스터들의 μ i 까지의 유클리드 거리를 계산하여, 해당 데이터에서 가장 가까운 클러스터를 찾아 데이터를 배당한다.

     

클러스터 중심 재조정: μ i 를 각 클러스터에 있는 데이터들의 무게중심 값으로 재설정해준다.

     

만약 클러스터가 변하지 않는다면 반복을 중지한다.

정리하면..

1. 맨 처음, 각 점들을 k개 집합으로 나눈다. 이때 임의로 나누거나, 어떤 휴리스틱 기법을 사용할 수도 있다.
2. 그 다음 각 집합의 무게 중심을 구한다.
3. 각각의 점들을 방금 구한 무게중심 가운데 제일 가까운 것에 연결지음으로써 새로이 집합을 나눌 수 있다.
4. 이 작업(2,3)을 반복하면 점들이 소속된 집합을 바꾸지 않거나, 무게중심이 변하지 않는 상태로 수렴될 수 있다.

실행과정 >>

1) 초기 k "평균값" (위의 경우 k=3) 은 데이터 오브젝트 중에서 무작위로 뽑힌다. (색칠된 동그라미로 표시됨).

 

2) k 각 데이터 오브젝트들은 가장 가까이 있는 평균값을 기준으로 묶인다. 평균값을 기준으로 분할된 영역은 보로노이 다이어그램 으로 표시된다.

3) k개의 클러스터의 중심점을 기준으로 평균값이 재조정된다

4) 수렴할 때 까지 2), 3) 과정을 반복한다.

초기화 기법 >>

 - 무작위 분할 (Random Partition)

무작위 분할 알고리즘은 가장 많이 쓰이는 초기화 기법으로, 각 데이터들을 임의의 클러스터에 배당한 후, 각 클러스터에 배당된 점들의 평균 값을 초기 μ i  로 설정한다. 무작위 분할 기법의 경우 다른 기법들과는 달리 데이터 순서에 대해 독립적이다. 무작위 분할의 경우 초기 클러스터가 각 데이터들에 대해 고르게 분포되기 때문에 각 초기 클러스터의 무게중심들이 데이터 집합의 중심에 가깝게 위치하는 경향을 띈다. 이러한 특성 때문에 K-조화 평균이나 퍼지 K-평균에서는 무작위 분할이 선호된다.

 - Forgy

Forgy 알고리즘은 1965년 Forgy에 의해 고안되었으며 현재 주로 쓰이는 초기화 기법 중 하나로, 데이터 집합으로부터 임의의 k개의 데이터를 선택하여 각 클러스터의 초기 μ i 로 설정한다. 무작위 분할 기법과 마찬가지로 Forgy 알고리즘은 데이터 순서에 대해 독립적이다. Forgy 알고리즘의 경우 초기 클러스터가 임의의 k개의 점들에 의해 설정되기 때문에 각 클러스터의 무게중심이 중심으로부터 퍼져있는 경향을 띈다. 이러한 특성 때문에 EM 알고리즘이나 표준 K-평균 알고리즘에서는 Forgy 알고리즘이 선호된다.

 - MacQueen

1967년 MacQueen에 의해 고안된 MacQueen 알고리즘은 Forgy 알고리즘과 마찬가지로 데이터 집합으로 부터 임의의 k 개의 데이터를 선택하여 각 클러스터의 초기 μ i     로 설정한다. 이후 선택되지 않은 각 데이터들에 대해, 해당 점으로부터 가장 가까운 클러스터를 찾아 데이터를 배당한다. 모든 데이터들이 클러스터에 배당되고 나면 각 클러스터의 무게중심을 다시 계산하여 초기 μ i 로 다시 설정한다. MacQueen 알고리즘의 경우 최종 수렴에 가까운 클러스터를 찾는 것은 비교적 빠르나, 최종 수렴에 해당하는 클러스터를 찾는 것은 매우 느리다.

 - Kaufman

1990년에 Kaufman과 Rousseeuw에 의해 고안된 Kaufman 알고리즘은 전체 데이터 집합 중 가장 중심에 위치한 데이터를 첫번째 μ i 로 설정한다. 이후 선택되지 않은 각 데이터들에 대해, 가장 가까운 무게중심 보다 선택되지 않은 데이터 집합에 더 근접하게 위치한 데이터를 또 다른 μ i 로 설정하는 것을 총 k 개의 μ i 가 설정될 때 까지 반복한다. 무작위 분할과 마찬가지로, Kaufman 알고리즘은 초기 클러스터링과 데이터 순서에 대해 비교적 독립적이기 때문에 해당 요소들에 의존적인 다른 알고리즘들 보다 월등한 성능을 보인다.

한계점 ★★★

1. 클러스터 개수 K값을 파라미터로 지정해주어야 한다. 이 알고리즘은 k값에 따라 결과값이 완전히 달라진다.
2. 알고리즘의 에러 수렴이 전역 최솟값이 아닌 지역 최솟값으로 수렴할 가능성이 있다. (초기값을 주는 방법이 중요)
3. 이상값에 민감하다. 큰 에러 수치에 의하여 클러스터 내의 전체 평균값이 크게 왜곡될 수 있다. (많이 몰려 있는 곳의 중심이 클러스터의 중심이어야 가장 좋은데 큰 에러 값이 그것을 중심을 크게 변화 시킨다)
4. 구형으로 분포하는 형상이 아닌 클러스터를 찾는데는 적절하지 않다. (많이 몰려 있는것을 중심으로 구분을 하는것이 알고리즘의 목적이므로..)

출처 : 위키피디아 (https://ko.wikipedia.org/wiki/K-%ED%8F%89%EA%B7%A0_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98)

테스트 >>

    // random partition

    const int k = 5;

    Point k_center[k];

    Point k_center_backup[k];

    int cntK[5] = { 0, };

    // 준비

    for (int i = 0; i < numCandiates; i++)

    {

        circles[i].k = -1; // 초기화; circles[i].k는 감지된 i번째 circle의 할당된 클러스터 k;

        val = 거리 또는 원하는 값을 구한다

        k_center[i % k] += val; // 이런식으로 랜덤(?)하게 넣어보았다

        cntK[i % k]++; //

    }

    for (int i = 0; i < k; i++)

        k_center[i] /= cntK[i]; // 클러스터의 평균값;

    while (1)

    {

        for (int i = 0; i < numCandiates; i++)

        {

            val = 거리 또는 원하는 값을 구한다

            int min = INT_MAX;

            for (int _k = 0; _k < k; _k++)

            {

                d = 새로구한 중심점과의 거리를 구한다

                if (min > d) // 더 가까운 클러스터 할당;

                {

                    min = d;

                    circles[i].k = _k;

                }

            }

        }

        // 초기화;

        for (int i = 0; i < k; i++)

        {

            k_center[i] = Point(0, 0);

            cntK[i] = 0;

        }

        // 다시 계산;

        for (int i = 0; i < numCandiates; i++)

        {

           val = 거리 또는 원하는 값을 구한다 (ciecles[i])

            k_center[circles[i].k] += val;

            cntK[circles[i].k] += 1;

        }

        bool re = true;

        for (int i = 0; i < k; i++)

        {

            if (cntK[i] == 0) continue;

            k_center[i] /= cntK[i];

            if (k_center_backup[i] != k_center[i]) re = false;

        }

        // 모든 클러스터의 값이 수렴하면 빠져나간다;

        if (re) break;

        for (int i = 0; i < k; i++)

        {

            k_center_backup[i] = k_center[i];

        }

    }

2016.07.05

int 를 float로 변경

결과 (타원의 크기로 클러스터링) >>