K-means Algorithm

분류 : 기계학습 - 비지도 학습(Unsupervised learning) - clustering - K means

기계학습 관련하여 일을 하거나 혹은 공부를 하는 사람이라면 k-means clustering에 대해 많이 들어봤을 것이다. 엄청 단순하고 간단한 알고리즘이나 k-means에 대해 자세히 설명하라 하면 할 수 있는 사람이 생각보다 많지 않다. 

아마도 '대충 비슷한 놈들끼리 묶어 주는 건가보네' 하고 넘어가는 경우가 많지 않을까 싶다. 

그래서 엄청 단순하지만 성능은 꽤 좋은 k-means 알고리즘에 대해 설명한다. 

* 사전 지식 *

혹여나 기계학습에 대한 기본적인 지식이 없는 상태에서 블로그를 방문한 사람이라면 이 부분을 먼저 읽길 바란다. 그렇지 않은 사람이라면 넘어가시길...

 - 기계 학습의 분류 (방법론적인 관점)

• 정답이 주어진 데이터에 대한 학습 : Supervised Learning
• 정답이 주어지지 않은 데이터에 대한 학습 : Unsupervised Learning
• 뭐 Semi 어쩌구 강화 어쩌구... 일단 대충 그렇다

 - Clustering

정답이 주어지지 않은 데이터에 대한 학습(Unsupervised Learning) 의 대표적인 예다.

여기서 문제!!!

문제) 아래의 그림에 있는 도형들을 비슷한 놈들끼리 묶어봐라.

이 그림을 보고 대부분의 사람들이 아래와 같이 묶었을 것이다.

여러분이 방금 한 것이 Unsupervised Learning 이면서 동시에 Clustering의 작업을 한 것이다. 

즉 clustering 은 속성이 비슷한 놈들끼리 묶어주는 일련의 작업을 말한다.

- k-means 알고리즘

  k means 알고리즘은 주어진 sample 들을 k 개의 묶음으로 묶어주는 작업을 수행한다. 아래의 그림은 k가 3일 때, 좌표평면 상의 점들을 세개의 분류로 나눠주는 예이다. (아래의 실험에 대해 아래에서 자세히 설명한다.)

K-means Clustering 수행 예

알고리즘 설명

   1. k 개의 점(sample)을 임의로 선택하여 그 점(sample)의 위치를 각 Class의 기준 위치으로 지정한다. 

   2. 모든 점(sample)들 각각에 대해 k개의 기준 위치 중에서 가장 가까운 기준위치(A)를 찾아내고 해당 점             (sample) 을 기준위치(A) 의 class 로 배정한다.

      예를 들어 기준위치가 다음과 같고 각각의 class 명을 A,B, C라 하자

          기준위치 / Class 명   -   (10,10) / A        (10, 90) / B       (90, 10) / C

      이때, 점 (5,5)는 class A에 속하게 된다. ((5,5) 와 (10,10) 의 거리가 class B,C의 기준위치와의 거리보다         가깝기 때문이다.)

      모든 점(sample)들에 대해 위와 같이 하나의 class로 배정한다.

  3. 기준위치 갱신

    A class, B class , C class 에 속한 점(sample)들의 평균값으로 A, B, C class의 기준위치를 변경한다. 

  4. 새로운 class 배정 결과 얻기

   3번에서 얻은 새로운 기준위치를 기준으로 하여 2번 과정과 동일한 과정을 반복하여 class 에 점(sample)들이    배정된 새로운 결과를 얻는다.

  5. 클러스터링 종료판단

   새로운 class 배정 결과가 이전의 class 배정 결과와 차이가 없다면 클러스터링 작업을 종료한다.

   차이가 있다면 3번 부터 다시 시작한다.

* 위의 그림에서 노란 네모는 각 클래스의 중심점이 어떻게 이동하는 지를 보여주며 동그란 점들의 색깔은 점       (sample) 들이 class 에 배정된 결과를 보여준다.

설명은 장황하나 무척 심플한 발상이다. 

k-means 알고리즘 적용 시 고려해야 할 몇가지 상황이 있다. 

1. 거리측정 문제

  1-1. 점과 점 사이의 거리

     점과 점 사이의 거리를 구하는 방법은 여러가지가 있다. 

     맨하탄 거리 - 바둑판 거리라고 생각하면 될듯 하다 수직 혹은 수평 방향으로만 갈 수 있다고 가정했을 때의 거리이다. 예를 들면 (1,1) 에서 (2,2) 까지의 맨하탄 거리는 2이다. (1,1) 에서 (2,2)로 가기 위해선 위로 한칸, 오른쪽으로 한칸 이니 두칸을 이동해야 한다. 

     유클리디안 거리 - 수학시간에 배운 점과 점사이의 거리이다. 각 축의 거리차를 제곱하여 합한 후 축의 갯수가 N 이라 할때 1/N 승을 해주면 된다. (1,1), (2,2) 의 거리는 잘 알다시피 root(2) = 1.414... 로 구해진다.

     마할라노비스 거리 - 모든 샘플에 대해 각 축에 사상시킨 값에 대한 분산을 구하여 분산의 정도에 따라 가중치를 부여하여 거리를 구한는 방법이다. 유클리디안 거리를 구하는 공식에 분산을 이용한 가중치 부분이 추가된 것이다.

     (1 - 코사인유사도) - 점사이의 거리는 유사도를 이용하여 표현할 수 있으며 그 반대도 가능하다. 코사인 유사도를 이용하여 점 사이의 거리를 구할 수 있다. 코사인 유사도는 text 문서와 같은 sample을 다룰 때 주로 사용하는 거리 측정법으로 sample의 볼륨 차이를 무시할 수  있는 거리측정법이다. 코사인유사도 참고

     이 외에도 sample 이 binary 속성을 갖을 때의 거리 측정법 등 다양한 방법이 존재한다. 이러한 것들 중 어떠한 것을 선택하여 사용할 것인지는 sample 의 속성과 clustering의 목적에 맞게 사용하여야 한다.

  1-2. 점과 class 사이의 거리

      위의 알고리즘 설명 부분에서는 class 에 속한 sample들의 평균 값을 구하여 그 위치를 class 에 대한 기준위치로 삼아 다은 점들과의 거리를 계산할 때 사용하였다. 이러한 방법 이외에도 class 내의 대표 sample을지정하여 그 sample 과의 거리를 사용하는 방법도 있다. 대표 sample을 지정하는 방법은 거리를 측정할 점과 가장 가까운 점 혹은 가장 먼 점을 선택할 수도 있고 클래스 내에서 다른 점들과의 거리의 합이 가장 작은점을 대표 sample 로 지정하는 방법 등 다양한 방법이 있다. 어떠한 방법을 선택하느냐에 따라 외톨이(outlier)에 민감하게 혹은 둔감하게 만들 수 있으니 적절한 방법의 선택이 필요하다.

2. 초기화의 문제

  k-means 알고리즘은 초기화에 따라 결과가 상이하다. 

 따라서 어떠한 샘플을 초기화에 사용할 것인지 결정하는 것이 쉽지 않은 문제이다. 

 이를 해결하는 하나의 해결책이 다중 k-means 로 다양한 초기화 값으로 k-means 알고리즘을 수행 후 

 클러스터링 결과를 기준으로 제곱오류를 계산하여 제곱오류가 가장 작은 결과를 최적 결과로 취하는 것이다.

 아래의 그림에서 동일한 데이터에 대해 초기화 위치에 따른 k-means의 결과가 상이한 것을 확인할 수 있다.

 

 

위의 이미지들은 k-means 알고리즘 테스트를 위해 임의로 생성한 데이터를 가지고 k-means clustering을 수행한 이미지이다. 테스트의 목적은 k-means 알고리즘의 수행 단계를 눈으로 보기 위함과 초기화에 따라 결과가 상이한 것을 확인하기 위함이었다. 

테스트한 코드를 첨부하니 궁금하신 분들은 돌려보기시 바란다. 

 python 3.x 를 사용하였으며 matplotlib 를 설치하여야 한다. 

P.S - 첫 번째 포스팅이라 쓰다보니 내용이 그지같네요. 뭔가 설명을 잘하려 했는데 자꾸 산으로 가는... 읽는 사람의 지식 수준을 정하지 않고 설명하다보니 힘이드는 경향이 없지 않아 있네요 ㅋ 추가로, k-means 알고리즘의 개떡같은 부분은 k 를 알고 있어야 한다는 거 겠지요. k 값을 몰라도 clustering 작업이 가능한 network 구조를 이용하는 SOM, ART 등의 알고리즘이 있습니다. 저도 공부를 하다 말아서... ㅎㅎ 간략히 본 바로는 ART 알고리즘이 SOM 알고리즘의 확장판의 개념이고 ART 의 구조는 auto-encoder 랑 비슷한 느낌이 있더군요. 근데 저는 둘다 정확히 몰라서 ㅎㅎ 공부 후에 추가 포스팅 하도록 하겠습니다. (무슨 PS 가 이래.....ㅋㅋㅋ그럼..이만)