Value of Life

k-means 알고리즘 본문

IT/이미지 프로세싱

k-means 알고리즘

앵글메이커 2008. 8. 16. 14:04
반응형

군집분석, 군집탐색(clustering)이라는 말이 있죠..

여러 데이터가 있을때, 이 데이터들을 '군집'이라는 단위로 나누는 것을 말하는데,,,,

이것은 아래와 같은 특징이 있습니다.

 

- 군집분석의 장점

    1. 탐색적인 기법 : 대용량에 대한 탐색적인 기법이므로 사전적인 정보없이 의미있느 자료구조를 얻는다.

    2. 다양한 형태의 데이터에 적용가능 : 거의 모든 형태의 데이터에 적용가능

    3. 분석방법의 적용 용이성 : 변수들에 대한 역할정의가 필요없으므로 적용이 쉽다.

- 군집분석의 단점

    1. 가중치와 거리정의 : 비유사성 거리정의와 가중치결정 어렵다.

    2. 초기 군집수 설정 : K평균 군집분석의 경우 군집수 K가 적합지 않으면 결과가 나쁘다.

    3. 결과해석의 어려움 : 사전에 주어진 목적이 없으므로 결과해석이 애매하다.


이 기법은 데이타 마이닝이나, 영상처리 등에서 응용이 됩니다.


이 중에서도 K-means(K평균)라는 기법을 소개해 드리겠습니다.

이것은 거리에 기반을 둔 clustering방법으로 가까운 곳에 있는 데이터들끼리 같은 군집으로 두겠다는 것이죠.


1. 여러 데이터가 있을때, 임의로 K개의 군집수를 정하고, 이것의 군집중앙위치를 임의로 정합니다.

2. 각각의 데이터에 대해서, K개의 군집중앙까지의 거리를 구하고, 가장 가까운 군집에 속하게 합니다.

3. 각 군집에 속해진 데이터들을 통해서, 그 데이터로부터 군집중앙까지의 평균을 구해서, 군집중앙을 새롭게 정해줍니다.

4. 만약 새롭게 정해준 군집중앙이 이전의 군집중앙과 동일하다면, 알고리즘은 종료합니다.

5. 동일하지 않다면, 2번의 과정부터 되풀이 하게 됩니다.



이 과정을 거치면, 임의로 정해준 K개의 군집으로 데이터들이 나뉘게 됩니다.

하지만, 이 방법은 앞의 단점에서 말씀드렸듯이 군집수 K를 임의로 정해줘야 한다는 것에 있죠. 그리고, 군집의 갯수(K), 초기 군집 중심의 선택, 어떤 데이터부터 처리를 해줄 것인가 등의 영향을 받게 됩니다.

그래서 이 알고리즘을 적용할때는 서로 다른 초기 군집중심 뿐 아니라 다양한 K값에 대해서 실험을 해봐야 합니다.


실행 예:

반응형

'IT > 이미지 프로세싱' 카테고리의 다른 글

PSNR(peak signal to noise rate)이란?  (0) 2009.04.15
영상처리 용어 해설  (0) 2008.08.16