K-means Clustering Algorithm

소개글

K-means Clustering Algorithm 개념 및 이해 (장, 단점)
알고리즘의 이해
소스코드 설명
응용 프로그램 소개

목차

1. K-means clustering algorithm
1.1 Introduction
1.2 Algorithm
1.3 Example
1.4 Program
1.5 Toy Problems
1.6 Real Application

본문내용

1.1 Introduction

다수의 데이터가 주어졌을 때, 계산을 단순화 하고 수렴을 가속시키기 위한 기법으로 군집화 기법을 사용한다. 그 중 k-means clustering algorithm(k-평균 알고리즘)은 간단하면서도 효과적인 군집화(Clustering) 문제를 해결하는 비교사 학습(Unsupervised Learning) 알고리즘이다. 데이터가 벡터 공간을 이룬다는 가정아래, 각 묶음의 분산도를 최소화하는 k개의 묶음으로 나누는 방법이다.

주어진 데이터 수는 n, 원하는 클러스터 수는 k로 표기한다. 데이터 집합으로부터 무작위로 선택된 k개의 초기 클러스터 중심벡터(μ1, μ2, ..., μk)로부터 클러스터를 구성한다. 각 데이터는 가장 가까운 거리에 있는 초기 중심 벡터를 기준으로 분류된다. 나누어진 각 클러스터에서 평균값으로 중심 값을 새로 갱신하고 이를 반복적으로 수행하여 오차 감소율이 매우 작아지거나, 중심 값이 변하지 않으면, 끝낸다.



1.1.1 장점
 군집분석 이외에도 분류∙예측을 위한 선행작업, 특이 오류 값이나 결손 값 처리작업 등 다양한 분석에 사용할 수 있다.

1.1.2 단점
 속성들의 형태가 다르거나 같은 형태의 속성이라도 값의 범위가 다양할 경우 거리 측정기준을 설정하는데 어려움이 따른다.
 k-means clustering 기법은 사용자가 지정한 K값에 따라 데이터를 K개의 군집으로 나눈다. 그러나 실제 데이터의 구조가 이 값보다 작거나 큰 수의 군집 특성을 갖고 있다면 좋은 결과를 기대하기 어렵다. 실제로 초기 클러스터 센터를 어떻게 정하느냐에 따라서 다른 최종 클러스터가 나올 수 있다. 즉, 안정된 상태의 클러스터는 보장하지만, 최적이라는 것은 보장하지 못한다.
 클러스터의 개수에 해당하는 K 값을 먼저 선택하여야 한다.

참고 자료

[1] 패턴인식 개론 / 한학용 / 한빛미디어
[2] 데이터마이닝 가볍게 따라하기 / 김현철 / 홍릉과학출판사
[3] Pattern Classification (2nd Edition) / Richard O. Duda, Peter E. Hart, David G. Stork / Info-Tech Corea
[4] Datamining / Tan, Steinbch and Kumar / Addison Wesley