군집화는 최적화 문제
군집화는 최적화 문제이다. 어떤 집단의 점수 분포가 흩어진 정도를 나타내는 variability(분산과는 다르다)를 모두 더해서 구하는 dissimilarity를 최소화하는 것이 군집화이고, 그렇기 때문에 군집화는 최적화 문제라고 볼 수 있다.
\(\displaystyle variability(c) = \sum_{e \in c}^{}{distance(mean(c), e)^2}\)
\(\displaystyle dissimilarity(C) = \sum_{c \in C}^{}{variability(c)}\)
여기에는 물론 제한조건이 필요하다. 집단 간의 최소 거리, 집단의 수 등이 그 제한조건이 된다.
군집화에는 두 가지 방법이 있다. 위계적 군집화와 k-평균 알고리즘이다.
위계적 군집화
위계적 군집화는 다음과 같이 진행한다.
- 각각의 요소를 집단으로 지정. (N개의 요소가 있다면 N개의 집단이 생기는 셈.)
- 가장 가까운 한 쌍의 집단을 찾아 병합.
- 모든 요소를 가진 단 하나의 집단이 나올 때까지 반복.
당연히 3번까지 수행하는 사람은 없을 것이다. 그럼 군집화를 하는 의미가 없을테니 말이다. 위계적 군집화의 장점은 군집화가 진행되는 과정을 자세히 관찰할 수 있고, 적당한 시점에서 이를 종료할 수 있다는 것에 있다.
다만 모든 과정을 지켜보다 보니 당연히 느리다(최악의 경우 $n^3$의 복잡도를 가진다).
위에서 2번 과정을 진행하려면 거리를 측정해야 하는데, 여기에는 3가지 방법이 있다.
- 단일 연결: 한 집단과 다른 집단의 사이의 임의의 요소 간 가장 짧은 거리 사용
- 완전 연결: 한 집단과 다른 집단의 사이의 임의의 요소 간 가장 긴 거리 사용
- 평균 연결: 한 집단과 다른 집단의 사이의 모든 요소 간 가장 평균 거리 사용
k-평균 알고리즘
k-평균 알고리즘에서 k는 만들고자 하는 군집의 개수를 의미한다. 즉, k-평균 알고리즘은 군집의 개수가 미리 정해져 있을 때 유용하다. 방법은 다음과 같다.
- k개의 데이터를 중심으로 활용하기 위해 임의로 선택.
- 데이터를 1에서 만든 중심 중에 가장 가까운 것에 할당하여 k개의 군집을 만든다.
- 각 군집에서 평균을 계산하여 중심을 다시 만든다.
- 중심이 더 이상 이동하지 않을 때까지 2 ~ 3을 반복한다.
복잡도는 어떻게 될까? k $\times$ n $\times$ d 가 된다. k는 군집의 개수, n은 반복하는 횟수, d는 점들 사이 거리 계산에 필요한 시간을 의미한다.
물론 k-평균 알고리즘이 항상 좋기만은 한 것은 아니다. 크게 두 가지 문제가 있다.
먼저, 잘못된 k를 선택했을 때이다. 누가 봐도 (혹은 공식적으로) 4개의 군집이 가능한 상황에서 k를 3으로 지정한다면 잘못된 결과가 도출될 것이다.
또한, 결과가 초기에 설정된 중심에 의존적이라는 것도 문제다. 중심을 잘못 설정하면 군집화에 시간이 오래 걸릴 뿐만 아니라 그 결과가 일정하지 않다는 것이 걸리는 점이다.
어떻게 이 두 가지 문제를 해결할까?
첫 번째 문제를 해결하기 위해서는 k를 잘 선택하면 된다. 대부분의 사람들은 자신이 이미 알고 있거나 공인된 지식을 기반으로 k를 정한다. 예를 들어, 대한민국 국적을 지닌 사람과 그렇지 않은 사람(k=2), 학계에서 인정된 세균의 분류(k=5) 등이 있다.
다르게 해결할 수도 있다. k를 바꾸어 가며 알고리즘을 실행해 결과를 종합적으로 평가하는 것이다. 아니면 위계적 군집화를 먼저 사용해서 데이터의 구조를 파악한 뒤 k를 선택할 수도 있다.
두 번째 문제를 해결하는 것은 생각보다 간단하다. 중심을 설정할 때 의도적으로 중심들을 떨어뜨려 배치하거나, 중심을 무작위로 배치하는 대신 알고리즘 자체를 여러 번 수행하여 가장 최고의 결과를 선택하는 것이다.
마지막으로 교수님은 환자들의 분당 심박수, 심장마비 경력, 나이, ST상승 여부 데이터(각각이 특성이라고 생각하면 된다)를 가지고 클러스터링을 하였다. 각각의 환자의 사망여부는 사전에 알려져 있지만 클러스터링에 사용되지는 않았다. 클러스터링 결과를 이용하면 어떤 특성이 사망률을 높이는 데 영향을 주는지 분석할 수 있을 것이다. 클러스터링을 하면서 한 가지 주의해야하는 것은 scaling인데, 심박수, 심장마비 경력(0 or 1), 나이, ST상승 여부(0 or 1)는 모두 다른 scale을 가지므로 이를 적절히 scaling하여 클러스터링해야 한다.
댓글남기기