#3-(5) 군집 알고리즘 : k-평균 군집(k-means)

※ 이 글의 내용은 O'REILLY의 <파이썬 라이브러리를 활용한 머신러닝> 책을 기반으로 한다.

군집 알고리즘 : k-평균 군집(k-means)

• 군집

 - 군집(Clustering) : 군집은 데이터를 비슷한 것끼리 묶어 클러스터(Cluster)라는 그룹으로 나누는 작업이다. 군집 알고리즘의 목표는 한 클러스터 안의 데이터 포인트끼리는 매우 비슷하고, 다른 클러스터의 데이터 포인트와는 구분되도록 데이터를 나누는 것이다. 데이터 포인트들 간의 유사성(Similarity)을 비교하여 데이터를 나눈다. 분류 알고리즘과 비슷하게 군집 알고리즘은 각 데이터 포인트가 어느 클러스터에 속하는지 예측한다. 

 - 유사성(Similarity) : 유사성의 실제 의미는 철학적인 문제이고, 직관적으로 아는 것이라 정의하기 힘들다. 데이터 포인트 사이의 유사성을 측정하기 위해서는 두 포인트 사이의 거리(distance)를 측정한다. 데이터 포인트 간의 거리를 측정하기 위해서는 거리를 잴 수 있는 공간의 데이터들로 맵핑(mapping)시켜야 하는데, 특정한 수치를 지닌 벡터로 표현 되도록 맵핑해야한다. 간단하게는, 데이터 간의 거리를 직선 거리로 나타낼 수 있는 유클라디안 공간의 점으로 변환하는 것이다.

 - 데이터를 분할하는 것 자체가 목적이 되거나 방대한 데이터에서 어떠한 지식을 발견하는 것(주제)이 목적이 되어 데이터를 클러스터로 묶을 수 있다. 또한 데이터를 클러스터로 묶게 되면, 데이터의 내부 구조에 대한 정보를 얻을 수 있다. 

• k-평균 군집

 - k-평균 군집(k-means clustering) : k-평균 군집은 가장 간단하고 또 널리 사용하는 군집 알고리즘이다. 이 알고리즘은 주어진 데이터를 k개의 클러스터로 묶는 알고리즘으로, 각 클러스터와 거리 차이의 분산을 최소화하는 방식으로 동작한다. 즉, 같은 클러스터에 속하는 데이터들의 내부 유사성을 증가시키는 방향으로 클러스터를 형성하는 것이다. 다만 데이터의 평균을 구할 수 있도록 데이터가 유클라디안 공간 위에서 실수의 좌표를 가져야만 한다. 

 - 먼저, 이 알고리즘은 데이터가 위치한 공간에서 클러스터의 중심이 될 k개의 클러스터 중심(Cluster Center, centroid)을 무작위로 선택한다. 그리고 각각의 데이터 포인트들을 자신과 가장 가까운 클러스터 중심에 할당한다. 같은 클러스터 중심에 할당된 데이터 포인트들의 평균을 구하고, 구한 평균 값을 2번째 클러스터 중심으로 설정한다. 다시 각각의 데이터 포인트들을 가장 가까운 2번째 클러스터 중심에 할당하고, 그 평균 값으로 3번째 클러스터 중심을 설정한다. 이것을 각 클러스터 중심에 속한 데이터 포인트들이 변하지 않을 때까지 반복한다. 즉, 데이터 자신이 속한 클러스터가 변하지 않을 때까지 반복하는 것이다. 

 - 군집은 각 데이터 포인트가 레이블을 가진다는 면에서 분류와 비슷해 보일 수 있다. 그러나 특정한 의미가 있는 분류에서의 레이블과는 다르게, 클러스터는 단지 데이터의 묶음일 뿐 자체적인 의미를 가지고 있지는 않다.

 - k-평균 군집 알고리즘에서 각 클러스터를 정의하는 것이 중심 하나이고, 그 중심에서 각 데이터 포인트간의 거리가 가까운 것을 클러스터로 묶기 때문에 클러스터는 둥근 형태로 나타난다. 이러한 이유로 k-평균 알고리즘은 비교적 간단한 형태의 데이터를 구분할 수 있다. 또한 k-평균은 모든 클러스터의 반경이 똑같고, 모든 방향이 중요하다고 가정하기 때문에, 클러스터 중심 사이의 딱 중간에 경계를 그린다. 따라사 위와 같은 복잡한 모양의 데이터에는 성능이 매우 나쁘다.

• k-평균 군집 알고리즘 평가

 - 장점 : 비교적 이해하기 쉽고 구현하기도 쉽다. 또한 비교적 빠르고 대용량 데이터 세트에도 잘 작동하여 가장 인기있는 군집 알고리즘이다. 

 - 단점 : 평균이 정의되어야만 적용가능하고, 무작위 초기화를 사용하여 알고리즘의 출력이 난수 초깃값에 따라 달라진다. 가장 큰 단점은 클러스터의 모양을 원으로 가정하고 있기 때문에 활용 범위가 비교적 제한적이며, 찾으려 하는 클러스터의 개수(k)를 지정해야만 한다는 것이다. (실제로는 알 수 없다.)