[C++] K-means clustering

K-means clustering이란?

주어진 데이터를 K 개의 군집으로 묶는 알고리즘으로 아래와 같은 특징을 가집니다.

• k-means 클러스터링을 통해 데이터 집합 내에서 유사한 점의 그룹을 찾을 수 있다.
• k-means 클러스터링은 그룹 내의 총 분산을 최소화하기 위해 데이터 세트에서 포인트 그룹을 찾는 작업이다.
• k-means 클러스터링은 각 데이터 지점과 중심 사이의 4차 유클리드 거리의 합인 클러스터 내 제곱합 편차를 최소화하기 위해 공간을 k개의 하위 집합으로 분할하는 작업이다.
• 공식적으로, k-means 군집화는 S={S1,S2, …Sk} 분할을 찾는 작업이다.

K-means algorithm

k-means clustering 문제는 실제로 해결하기 어려운 문제입니다. 예를 들어 우리에게 200개의 데이터포인트가 존재하고 이걸 5개의 그룹, 즉 클러스터로 나누려고 한다고 가정합니다. 그랬을 때 200개의 데이터포인트가 5개의 그룹 중 하나에 속할 경우의 수는 200^5가 됩니다. 이런 경우의 수에 대해서는 Brute Force로는 해결할 수 없습니다. 그러므로 우리는 최적의 솔루션을 찾기 위한 알고리즘이 필요합니다.

이 글에서는 K-means 알고리즘에 대해 설명하고 코드로 간단히 동작을 설명하려 합니다. K-means 알고리즘을 설명하면 다음과 같습니다.

1. 데이터 오브젝트 집합 D에서 k 개의 데이터 오브젝트를 임의로 추출하고, 이 데이터 오브젝트들을 각 클러스터의 중심 (centroid)으로 설정한다. (초기값 설정)
2. 집합 D의 각 데이터 오브젝트들에 대해 k 개의 클러스터 중심 오브젝트와의 거리를 각각 구하고, 각 데이터 오브젝트가 어느 중심점 (centroid) 와 가장 유사도가 높은지 알아낸다. 그리고 그렇게 찾아낸 중심점으로 각 데이터 오브젝트들을 할당한다.
3. 클러스터의 중심점을 다시 계산한다. 즉, 2에서 재할당된 클러스터들을 기준으로 중심점을 다시 계산한다.
4. 각 데이터 오브젝트의 소속 클러스터가 바뀌지 않을 때까지 2, 3 과정을 반복한다.
   (위키피디아 - k-평균 알고리즘 참고)

구현해보자!

이 글의 목표는 위에서 언급했듯이 실제로 K-means 알고리즘을 코드로 분석하는 것입니다. 예제는 2차원에서 랜덤 좌표값들을 이용하여 테스트를 진행할 것입니다. 결과는 가능하다면 Python으로 한번 확인해보겠습니다.

데이터포인트 자료형 정의

C++의 구조체를 사용하여 Point 데이터를 정의하였습니다. 구조체 내부에는 좌표점 x,y의 값과 어떤 cluster에 속하는지 저장할 값과 cluster 중심점과의 최소값을 저장해두기 위한 변수까지 선언하였습니다.

typedef struct Point {
    double x, y;
    int cluster;
    double minDistance;

    Point() :
        x(0.0),
        y(0.0),
        cluster(-1),
        minDistance(std::numeric_limits<double>::max()) {}

    double distance(Point p) {
        return (p.x - x) * (p.x - x) + (p.y - y) * (p.y - y);
    }
};

여기서 주의할 점은 minDistance 변수는 초기화 시 double 자료형의 max 값으로 할당하는 것입니다. std::numeric_limits::max()를 사용하여도 되고, DBL_MAX 를 사용해도 무관합니다. 그리고 Point 간의 거리를 계산해주는 distance() 메소드를 정의합니다. 거리를 측정하는 방법은 유클리드 거리를 사용합니다.

Data 생성하기

좌표상 생성할 Point는 0~100 사이의 x,y 값으로 설정할 것입니다. 랜덤값을 생성하여 할당해줍니다. 이 부분은 중요한 부분은 아니니 코드만 보여드리겠습니다. (이해하실 필요 없습니다.)

 unsigned short pseudo_rand() {
    static unsigned long long seed = 5;
    return (seed = seed * 25214903917ULL + 11ULL) >> 16;
}

  void build() {
    int loop = 0;
    while (loop < 100000) {
        int tmp = 0;
        for (int i = 0; i < 3; i++) tmp += pseudo_rand() % 100;

        data[loop].x = (double)((tmp / 3 + alpha) % 100) + (pseudo_rand() % 1000000) / 1000000.;
        data[loop].y = (double)((tmp / 3 + beta) % 100) + (pseudo_rand() % 1000000) / 1000000.;
        loop++;
    }
}

K-means Algorithm

위에서 설명한 알고리즘을 다시 한번 짚고 넘어가겠습니다.

1. 데이터 오브젝트 집합 D에서 k 개의 데이터 오브젝트를 임의로 추출하고, 이 데이터 오브젝트들을 각 클러스터의 중심 (centroid)으로 설정한다. (초기값 설정)
2. 집합 D의 각 데이터 오브젝트들에 대해 k 개의 클러스터 중심 오브젝트와의 거리를 각각 구하고, 각 데이터 오브젝트가 어느 중심점 (centroid) 와 가장 유사도가 높은지 알아낸다. 그리고 그렇게 찾아낸 중심점으로 각 데이터 오브젝트들을 할당한다.
3. 클러스터의 중심점을 다시 계산한다. 즉, 2에서 재할당된 클러스터들을 기준으로 중심점을 다시 계산한다.
4. 각 데이터 오브젝트의 소속 클러스터가 바뀌지 않을 때까지 2, 3 과정을 반복한다.
   (위키피디아 - k-평균 알고리즘 참고)

아래 코드는 위 알고리즘을 구현한 메소드입니다.

void kMeansClustering(int epoch) {
    for (int i = 0; i < 5; i++)
        centroids[i] = data[pseudo_rand() % 100000];

    while (epoch-- > 0) {
        for (int i = 0; i < 5; i++) {
            for (register int idx = 0; idx < 100000; idx++) {
                double dist = centroids[i].distance(data[idx]);
                if (dist < data[idx].minDistance) {
                    data[idx].minDistance = dist;
                    data[idx].cluster = i;
                }
            }
        }

        int point_cnt[5] = { 0, };
        double sum_x[5] = { 0, };
        double sum_y[5] = { 0, };

        for (register int i = 0; i < 100000; i++) {
            int cluster_id = data[i].cluster;
            point_cnt[cluster_id] += 1;
            sum_x[cluster_id] += data[i].x;
            sum_y[cluster_id] += data[i].y;

            data[i].minDistance = DBL_MAX;
        }

        for (int i = 0; i < 5; i++) {
            centroids[i].x = sum_x[i] / point_cnt[i];
            centroids[i].y = sum_y[i] / point_cnt[i];
        }
    }
}

전체 코드 확인하기

#define _CRT_SECURE_NO_WARNINGS
#include <ctime> 
#include <fstream>
#include <iostream>
#include <vector>

typedef struct Point {
    double x, y;
    int cluster;
    double minDistance;

    Point() :
        x(0.0),
        y(0.0),
        cluster(-1),
        minDistance(std::numeric_limits<double>::max()) {}

    double distance(Point p) {
        return (p.x - x) * (p.x - x) + (p.y - y) * (p.y - y);
    }
};

Point data[100000];
Point centroids[5];

unsigned short pseudo_rand() {
    static unsigned long long seed = 5;
    return (seed = seed * 25214903917ULL + 11ULL) >> 16;
}

void build() {
    int alpha = pseudo_rand();
    int beta = pseudo_rand();

    int loop = 0;
    while (loop < 100000) {
        int tmp = 0;
        for (int i = 0; i < 3; i++) tmp += pseudo_rand() % 100;

        data[loop].x = (double)((tmp / 3 + alpha) % 100) + (pseudo_rand() % 1000000) / 1000000.;
        data[loop].y = (double)((tmp / 3 + beta) % 100) + (pseudo_rand() % 1000000) / 1000000.;
        loop++;
    }
}

void kMeansClustering(int epoch) {
    /* Init cluster */
    for (int i = 0; i < 5; i++)
        centroids[i] = data[pseudo_rand() % 100000];

    while (epoch-- > 0) {
        /* Assign Points to a cluster */
        for (int i = 0; i < 5; i++) {
            for (register int idx = 0; idx < 100000; idx++) {
                double dist = centroids[i].distance(data[idx]);
                if (dist < data[idx].minDistance) {
                    data[idx].minDistance = dist;
                    data[idx].cluster = i;
                }
            }
        }

        /* Computing new centroids */
        int point_cnt[5] = { 0, };
        double sum_x[5] = { 0, };
        double sum_y[5] = { 0, };

        for (register int i = 0; i < 100000; i++) {
            int cluster_id = data[i].cluster;
            point_cnt[cluster_id] += 1;
            sum_x[cluster_id] += data[i].x;
            sum_y[cluster_id] += data[i].y;

            data[i].minDistance = DBL_MAX;
        }

        for (int i = 0; i < 5; i++) {
            centroids[i].x = sum_x[i] / point_cnt[i];
            centroids[i].y = sum_y[i] / point_cnt[i];
        }
    }
}

int main()
{
    build();
    kMeansClustering(100);

    std::ofstream myfile;
    myfile.open("output.csv");
    myfile << "x,y,c" << std::endl;

    for (register int i = 0; i < 100000; i++) {
        myfile << data[i].x << "," << data[i].y << "," << data[i].cluster << std::    endl;
    }
    myfile.close();

    return 0;
}

감사합니다.