클러스터링(군집 분석) —비 계층적 군집 분석
이전 글인 계층적 군집에 이어서 군집 분석 중 비계층적 군집 분석(Partitioning Clustering)에 대해서 알아보려고 합니다.
계층적 군집분석은 nested 성질을 가지고 있어 한 군집이 다른 군집에 속할 수 있지만, 비계층적 군집분석은 partitoned 성질이라 한 군집이 다른 군집에 속할 수 없다.
위와 같은 정의를 보았습니다. 계층적 군집분석은 더 유사한 것 끼리 묶으면서 댄드로그램으로 나타낼 수 있는데, 그리다 보면 hierarchy가 자연스럽게 생기게 됩니다. 그러니 명칭도 Hierarchical Clustering이 아닐까 하는 생각이 들었습니다. 비계층적 군집 분석은 명칭에 partition이 들어가는 것처럼 분할하는 것에 더 목표를 둔 군집 분석이라 생각이 듭니다.
비 계층적 군집 분석의 대표적인 방법 K-Means clustering 에 관하여 작성했습니다.
K-Means clustering 알고리즘의 특징
- 사전에 군집의 개수(K)를 정해주어야 합니다.
- 클러스터 내 데이터 개체들을 최대한 비슷하게 만들면서도 클러스터 간의 차이를 최대화합니다.
- 개체와 클러스터의 중심 사이의 거리 제곱합이 최소가 되도록 개체를 클러스터에 할당합니다.
- 군집 내 거리 제곱합이 작을수록 동일한 군집 내의 유사성이 증가합니다.
K-Means clustering 알고리즘 방법
- K개의 군집 수를 사전에 결정합니다.
- 군집의 초기값에 의해 결정된 초기 군집에 개체를 할당합니다.
- 각 군집의 중심(centroid)을 계산하여 각 개체를 가장 가까운 군집에 재할당하고 개체가 재할당되면 새로운 군집의 중심을 다시 계산한 후 다시 재할당 여부를 판정합니다. (일반적으로 유클리드 거리를 사용)
- 더 이상의 재할당이 없을 때까지 3번을 반복합니다. 이 말은 중앙값에 변화가 없을 때까지 계속 반복한다는 의미입니다.
2번 단계에서 군집의 초기값을 랜덤으로 선택하게 되는데, 어느 지점을 선택했는지에 따라서 다른 결과를 가져올 수 있습니다.
예시로 보는 K-Means clustering
StatQuest: K-means clustering 에서 설명한 예시를 가져왔습니다.
Case 1.
step1.
아래에 총 12개의 점이 한 줄에 있습니다. 이 점들을 3개로 분할하려고 합니다. 왼쪽부터 차례로 1,2, … , 12라고 했을 때 딱 보아도 3등분을 어떻게 나누면 될지 보입니다. (4-4-4)
step2.
하지만 초기 값 설정이 아래 파랑(2), 초록(4), 주황색(7) 점처럼 설정을 한다고 했을 때, 클러스터링은 다음과 같이 작동합니다.
step3.
1. 1번 점은 2번 파란색과 가장 가까운 거리를 가지게 되므로 2번과 같이 파란 군집으로 묶이게 됩니다.
2. 3번 점은 4번 초록점과 가장 가까운 거리를 가지게 되니 4번과 같이 초록 군집으로 묶입니다.
3. 5,6,8 번은 7번 주황 군집과 가장 가까운 거리를 가지므로 7번과 같이 주황 군집으로 묶입니다.
4. 멀리 떨어져 있는 9,10,11,12번 점들에게 가장 가까운 점은 7번 주황색 점입니다. 그러므로 주황 군집으로 묶이게 됩니다.
step4.
결론적으로 2–2–8개의 군집으로 나누어지게 되었습니다.
위처럼 나눈 군집이 잘 분류된 군집이라고 할 수 있는 사람은 몇 없을 겁니다.
랜덤으로 초기값을 선정된 경우에도 3번 방법을 통해 어떻게 클러스터링이 진행되는지를 살펴보겠습니다.
각 군집의 중심(centroid)을 계산하여 각 개체를 가장 가까운 군집에 재할당하고 개체가 재할당되면 새로운 군집의 중심을 다시 계산한 후 다시 재할당 여부를 판정을 반복
Case 2.
step1.
5, 6, 12번 점이 초기값으로 지정되었습니다. 1, 2, 3, 4, 5번 점이 파란 군집에, 6, 7, 8 점이 초록 군집 그리고 9, 10, 11, 12 점이 주황 군집에 속하게 됩니다.
step2.
이때 각 군집의 중심으로 중심점을 옮깁니다. 파란 군집의 중심값은 3과 4 사이에, 초록 군집은 6과 7 사이로, 주황 군집은 10과 11 사이로 옮겨진 것을 확인할 수 있습니다.
step3.
이 과정을 반복하면 아래처럼 군집이 나눠지는 것을 볼 수 있습니다. 눈으로 보기에도 합리적으로 보입니다.
위와 같이 처음 초기값이 잘못 설정되어도 중앙값을 재할당하는 방식을 반복하면서 올바르게(?) 분할할 수 있게 합니다. 단, case 1번처럼 중앙값을 재할당해도 회복이 안 되는 케이스들도 존재하기 때문에, 클러스터링을 할 때 시뮬레이션을 한 번만 하는 것이 아니라 여러 번 하는 것을 권장합니다.
K-Means clustering의 문제점
- K 결정이 주관적입니다.
(아래 군집의 개수(K) 결정 방법에서 설명합) - 여러 개의 초기값이 동일 군집 내에 존재할 경우 결과가 이상해집니다.
(위에서 설명) - 아웃라이어가 있을 경우 적어도 한 군집은 거리가 멀어도 해당 값을 억지로 한 군집으로 묶는 성향이 있습니다.
- 사전에 k개의 군집으로 되어 있다는 것을 알아도, 크기가 작은 그룹에서는 제대로 작동하지 않을 수 있습니다.
즉 군집의 사이즈나 모양이 다를 경우 애매한 결과가 나올 수도 있습니다. - 차원이 많아지는 경우 유사도 측정에 어려움을 겪습니다.
(이전 글에서 설명) - 반복 특성과 중심 무작위 초기화 때문에, k 평균 알고리즘은 local optimum에 고착될 수 있고 global optimum에 수렴되지 않을 수 있습니다.
3번, 모든 레코드의 거리를 계산하고 분리하려는 성질 때문에 아웃라이어도 centroid를 재설정할 때마다 고려하게 됩니다. 이를 보완하기 위해서는 이전에 데이터를 정제하는 과정에서 아웃라이어를 제외하면 어떨까 싶습니다.
4번, 그림으로 확인해 볼 수 있습니다. 좌측 그림은 군집이 각각 사이즈가 다른 세 개로 원형 군집으로 나눠져 있습니다. 하지만 K-mean 클러스터링을 하게 되면 우측 그림처럼 같은 사이즈로 군집을 분류하려는 성질을 가집니다. 눈으로 확인 하기에도 좌측보다 더 애매하게 나누어졌다는 것을 알 수 있습니다.
6번, 초기 설정값에 따라 local optimum인데 더 진행되지 않을 수 있으니, 초기 설정값을 여러 번 바꾸어서 진행해보는 것으로 보완할 수 있습니다.
이런 문제점이 있음에도 K-mean 클러스터링을 대표적으로 쓰이는 것은 구현하기가 비교적 쉬우며, 대규모 데이터셋을 정해진 값(K)으로 분석할 수 있기 때문입니다.
군집의 개수(K) 결정 방법
크게 3가지 방법이 있습니다.
- 계층적 군집분석의 덴드로그램을 이용한 군집의 개수 결정
- The elbow method
- 군집 내 개체간 거리 제곱합의 총합으로 구하는 방법과 그룹 간 분산의 비율을 계산하는 방법 2가지가 있습니다. 각각 방법으로 K 숫자를 늘려갈 때 팔꿈치 모양으로 꺾이는 지점의 수를 K로 지정하는 방법을 말합니다.
3. The Silhouette method
- 엘보 방법보다 덜 주관적인 방법입니다.
- 전체 군집분석의 실루엣들을 하나의 그래프에 모아서 보여줌으로써, 데이터 구성과 형상의 개요와 군집들의 상대적인 질을 평가합니다.
- 평균 실루엣 폭은 군집화 결과에 대한 타당성을 평가하고, 적절한 군집 개수를 선택하는데 활용하게 됩니다.
- 실루엣 값이 1에 가까우면 다른 군집과의 거리보다 동일 군집 내 객체 간 거리가 가깝다는 뜻으로 객체가 잘 군집화가 되었다는 의미며, 반대로 실루엣값이 -1에 가까우면 객체의 군집화가 잘못되었다는 뜻입니다.
마무리 하며..
막연하게 데이터들을 세 집단으로 나누고 싶다는 생각을 했었습니다. 클러스터링을 배우면서 처음으로 든 생각이 내가 분류하고 싶다고 K를 특정 상수로 두고 라이브러리를 돌리면 안 되겠다였습니다.
데이터 종류와 단위부터 맞춘 후, K가 몇 개가 적절할 지부터 살펴봐야겠다 생각이 들었습니다. K를 결정하는 것이 그 무엇보다 중요한 것이 아닌가 하는 생각이 들 정도였습니다.
그 후에는 아웃라이어들을 제거하고, 초기값 설정이 잘못되진 않았는지 반복으로 돌려보고, 군집의 크기가 다른데 같게 분류하기 위해 혹은 원형으로 작동하기 위해 결론이 잘못되지 않았는지를 계속 확인을 해야 하는 작업을 진행해야겠습니다.
비록 클러스터링이 맞다 틀리다를 결정할 수 없는 작업이지만, 적어도 눈으로 봤을 때 ‘어랏 이건 아닌 것 같은데..’ 싶으면 안 되니까요.
같은 데이터지만 ‘잘’ 나눠진 케이스와 ‘이건 아닌데’ 싶은 케이스 두 가지를 예시로 마무리하겠습니다.
