[Matlab] K-Means Clustering (K-평균 군집화) 알고리즘 구현하기

1967년 처음 제안된 K-Means 클러스터링 (K-평균 군집화)은 군집화 알고리즘의 시작을 알린 데이터 마이닝 기법입니다. 파티션을 분리하는 기법 (Partitioning) 으로 분류되는 K-means 는 사전에 부여된 클러스터의 개수와 개체 간의 거리를 기반으로 전체 클러스터의 중심과의 거리를 최소화 하며 군집을 수행합니다. 이번 포스팅에서는 간단하게 K-Means 알고리즘을 살펴본 뒤, 매트랩에서 직접 알고리즘을 구현해보도록 하겠습니다.

 

1. K-Means 알고리즘의 목표

$n$ 개의 데이터를 가지는 $d$ 차원 데이터 집합 $X=(x_1,x_2,...,x_n)$가 있습니다. 쉽게 예를 들기 위해, $d=2$를 가지는 2차원 공간 데이터로 가정하게되면 그림 1과 같이 표현이 가능합니다.

 

 

그림 1. K-Means 알고리즘 예시

 

 

데이터 집합 $X$가 주어졌을때, K-Means는 사전에 지정된 클러스터 개수 $k$ 만큼 집합을 만들고 각 집합에 포함된 데이터들끼리의 응집도를 최대로 하는 방식으로 군집을 수행합니다. 여기서 클러스터 개수는 전체 데이터의 개수 $n$ 보다 작게 설정되어야 하며, 전체 클러스터의 집합 $C=(c_1,c_2,...,c_k)$로 표현됩니다.

 

 

1. $n$개로 구성된 $d$ 차원의 데이터 집합 $X=(x_1,x_2,...,x_n)$

 

2. $k(<=n)$개의 지정된 클러스터 개수

 

3. $C=(c_1,c_2,...,c_k)$로 표현되는 전체 클러스터 집합

 

 

이때, 집합 $C$ 군집을 대표하는 중심(Centroid)축을 $u_k$로 정의합니다. 중심축 $u_k$가 K-Measn의 군집 방식 '응집도를 최대로' 하는 방향으로 학습하며 최적화됩니다. 이는 식 1과 같습니다.

 

$$\underset{s}{\operatorname{argmin}} \sum_{i=1}^{k}\sum_{x\in{C_i}}||x-u_i||^2$$

 

응집도의 최대화하는 것은 공간적으로 같은 군집끼리의 거리를 최소화하는것이 됩니다. 즉, K-Means 알고리즘의 핵심은 전체 군집 개수 $k$까지 집합 $C_i$에 포함된 데이터 $x$와 $C_i$를 대표하는 중심축 $u_i$의 거리를 최소화하는 문제입니다.

 

2. K-Means 알고리즘

 

1. $u_k$ 초기화 :  초기 Centroid  값을 선정하기 위해 집합 $X$ 에서 임의로 값을 선정합니다.

 

2. 응집도 연산 : 모든 데이터에 대하여 초기화된 $u_k$와 거리를 구합니다. 이후, 가장 인접한 Centroid 값을 가지는 클러스터 집합 $C$의 원소로 입력합니다.

 

3. 군집 업데이트 : 모든 데이터가 $C$의 원소로 선택되었다면, 이를 바탕으로 $C$의 중심축 $u_k$를 수정합니다. 일반적인 K-Means는 이 과정에서 집합 내 원소의 평균값으로 갱신됩니다.

 

4. 원하는 학습 횟수 또는 목적 함수가 최적화될때까지 2~3의 과정을 반복합니다.

 

 

3. Matlab 코드

 

0. 샘플 코드 다운로드

 

git clone https://github.com/DEEPI-LAB/k-means-implementation-in-matlab.git

 

매트랩 코드와 2차원 데이터 샘플을 포함하고 있는 예제입니다. 아래 경로를 통해서도 직접 다운로드가 가능합니다.

 

github.com/DEEPI-LAB/k-means-implementation-in-matlab

DEEPI-LAB/k-means-implementation-in-matlab

 

1. 학습 파라미터 초기화

 

load corner.mat

# 2차원 공간 데이터
X = X;
# 클러스터 개수
k = 4;                       
# 클러스터 위치 초기화 인덱스 선정
rand = randperm(length(X),k);
# 초기 Centroid 값
u = X(rand ,:);
# 학습 횟수
z = 10;

 

가장 기본적인 클러스터 데이터 중 하나인 2차원 공간 데이터를 함께 첨부하였습니다. K-Means 알고리즘 초기화 단계입니다. $u_k$를 초기화하기 위해 임의로 입력 데이터 $X$의 원소를 선정합니다.

 

 

 2. 응집도 연산

 

# 학습 시작
for z=1:10
    # 최대값 저장메모리 할당
    C = cell(k,1);
    for j=1:length(X)
        
        # 거리 구하기
        for i =1:k
            dist(i,1) = norm(X(j,:)-u(i,:));
        end
        # 중심점과 가장 유사도가 높은 데이터를 중심점 클러스터로 할당
        arg = find(dist==min(dist));
        C{arg}(end+1,:) = X(j,:);
    end

 

학습이 반복될때마다 클러스터 집합 $C$가 갱신될 수 있도록 초기화해줍니다. 이후, 모든 데이터 $X$를 스캔하면서 $c_k$와의 거리를 구한 뒤, 가장 인접함 Centorid 값을 가지는 집합 $C$의 원소로 설정합니다.

 

 

3. 업데이트

 

 for i = 1:k
 
 	# 군집된 클러스터 원소
        cluster = C{i};
 	# 전체 평균값 
 	cluster = sum(cluster) ./ sum(cluster~=0,1);
        try
            u(i,:) = cluster;
        end
    end
end

 

한번 반복이 완료되면, 를 바탕으로 $C$의 중심축 $u_k$를 원소의 평균을 통해 수정하게 됩니다.

 

 

4. 최종코드

 

# *********************************************
# Unsupervised Learning - K-Means algorithm
# Deep.I Inc.
# *********************************************

load corner.mat

# 2차원 공간 데이터
X = X;
# 클러스터 개수
k = 4;                       
# 클러스터 위치 초기화 인덱스 선정
rand = randperm(length(X),k);
# 초기 Centroid 값
u = X(rand ,:);
# 학습 횟수
z = 10;

# 학습 시작
for z=1:10
    # 최대값 저장메모리 할당
    C = cell(k,1);
    for j=1:length(X)
        # 거리 구하기
        for i =1:k
            dist(i,1) = norm(X(j,:)-u(i,:));
        end
        # 중심점과 가장 유사도가 높은 데이터를 중심점 클러스터로 할당
        arg = find(dist==min(dist));
        C{arg}(end+1,:) = X(j,:);
    end
   
    for i = 1:k
        cluster = C{i};
        cluster = sum(cluster) ./ sum(cluster~=0,1);
        try
            u(i,:) = cluster;
        end
    end
    
    # 실시간으로 군집 결과 확인하기
    cla; hold on;
    for i = 1: k
        cluster = C{i};
        try
            scatter(cluster(:,1),cluster(:,2),'.')
            scatter(u(:,1),u(:,2),'*r','LineWidth',5)
        end
    end
    pause(2)
    
end

 

4. 결론

 

그림 2. 알고리즘 구현 화면

 

 

사실 K-Means는 비선형 데이터 군집이나, 군집의 개수를 알지 못하는 경우에는 적용할 수가 없다는 치명적인 단점이 존재합니다. 이밖에도 군집 밀도나 겹침 등의 문제에도 낮은 강인성을 보이고 있죠. 첨부된 군집 데이터 모두 K-Means로는 쉽게 군집되지 않습니다. 이를 해결하기 위해 현대의 클러스터링 기법은 밀도를 이용하거나 그래프 모델, 신경망 등의 다양한 알고리즘으로 군집 문제를 접근하고 있습니다. 

 

 

 

# 머신러닝 프로젝트 제작, 상담 및 컨설팅  / 머신러닝 접목 졸업작품 컨설팅

# 데이터 가공, 수집, 라벨링 작업 / C, 파이썬 프로그램 제작

# email : deepi.contact.us@gmail.com

# site : www.deep-i.net