(전공복습) 인공지능 6. 군집화

차례

• 차례
• 들어가기 전에
• 군집화(Clustering)
  • 기본 아이디어
  • 종류
  • K-Means Clustering
    • 복잡도
    • 수렴
    • 한계
  • 거리함수(Distance Metric)
  • Agglomerative Clustering
• 정리

들어가기 전에

이 글은 컴퓨터학과 이중전공생으로서 배운 것들을 다시 한번 정리하고자 남기는 글입니다. 불완전한 기억 등의 이유로 오류가 있을 수 있으며, 참조 내지 이정표로만 사용해주세요.
본 게시글은 고려대학교의 인공지능 강의를 기반으로 작성자의 추가적인 설명이 덧붙여진 글입니다. 또한 해당 강의는 UC 버클리 CS188을 기반으로 함을 밝힙니다.

군집화(Clustering)

이전에 살펴본 결정트리와 나이브 베이지언은 분류(Classification)를 위한 모델에 해당한다. 분류는 주어진 데이터의 피처(\(X\))를 통해 어떤 클래스(\(Y\))에 속하는지 예측하는 것을 의미했다. 분류를 위해서는 훈련 대상 데이터가 이미 분류되어 있어야 한다. 그 분류된 데이터를 통해 학습해서 분류되지 않은 실제 데이터를 예측할 수 있기 때문이다. 이처럼 분류는 지도학습(Supervisded Learning)에 해당한다.
반면, 군집화는 비지도학습(Unsupervised Learning)으로, 학습에 사용될 데이터가 분류되어있지 않아도 학습이 가능하다. 어떤 클래스에 속하는지를 예측하는 분류와 달리, 군집화는 비슷한 데이터끼리 모아주기만 하기 때문이다. 이러한 군집화는 고객들의 소비 패턴을 분석하거나, 이미지의 영역을 구분하는 등의 작업에 사용된다.

기본 아이디어

군집화는 그럼 어떻게 작동하는가? 군집화를 위해 우리는 다음과 같은 사실을 전제할 것이다: 비슷한 피처를 지닌 데이터는 다른 측면에서도 비슷할 것이다. 예를 들어 사람들의 소비 패턴을 파악하기 위해 나이와 소득을 수집할 수 있다. 그렇다면 우리는 나이와 소득이 유사한 사람들을 하나의 그룹으로 만들 수 있다. 이것이 군집화의 기본 아이디어이다.
그렇다면 유사하다의 기준은 무엇일까? 어떻게 그 사람의 나이나 소득이 다른 사람들과 유사하다고 할 수 있을까? 방법 중 하나는 거리를 확인하는 것이다. 거리를 측정하는 방법도 여러가지가 있지만, 우리는 가장 일반적인 유클리드 거리(Euclidean Distance)를 사용하겠다. 유클리드 거리란 흔히 생각하는 기하학에서의 두 점 사이의 거리를 의미한다. 즉 두 피처 \(a\), \(b\)에 대해, \(\mathrm{dist}(a, b) = \sqrt{ {(a_1 - a_2)}^2 + {(b_1 - b_2)}^2 }\)로 나타낼 수 있다. 이렇게 계산된 거리가 가까우면 유사한 데이터라고 생각할 수 있을 것이다(가까움의 정의는 조금 있다 다시 다뤄보도록 하자).

종류

군집화는 크게 두 가지로 구분할 수 있다. 첫번째는 위에서 언급한 것처럼 단순히 데이터를 나누는 것이다. 즉 단순히 Flat Partitioning을 수행하는 알고리즘이다. 예시로는 K-Means, Mixture of Gaussian(GMM), Spectral Clustering 등이 있다(이게 다 뭔지는 아직 몰라도 된다).
반면, 군집에 계층(Hierarchy)이 있을 수도 있다. 이를테면 군집 1과 군집 2는 A라는 더 큰 군집에 속하고, 군집 3과 군집 4는 B라는 더 큰 군집에 속하고, A와 B는 X라는 또다른 군집에 속하는, 이처럼 계층 관계가 있는 군집화 역시 가능하다. 이때, 작은 군집들을 합쳐가면서 큰 군집을 만들어가는 상향식(Bottom Up) 군집화를 Agglomerative Clustering이라 하고, 반대로 큰 군집을 쪼개서 작은 군집들로 다시 나누는 하향식(Top Down) 군집화를 Divisive Clustering이라 한다. Agglomeration는 응집을 의미하고, Division은 분할을 의미하니, 나름 직관적인 명칭이다.
아래는 심슨 가족을 Flat Partitioning하거나 Hierarchical Clustering한 예시이다. 참고로 Hierarchical Clustering의 결과 나오는 트리 형태의 그림은 덴드로그램(Dendrogram)이라 부른다.

K-Means Clustering

K-Means 군집화는 이름처럼 \(K\)개의 군집을 만들고, 그 군집의 중심(평균 위치)을 정하는 알고리즘이다. K-Means는 아래의 과정을 따른다.

1. \(K\)개의 랜덤한 지점을 중심으로 정한다.
2. 모든 데이터를 \(K\)개의 중심 중 가장 가까운 지점에 할당한다.
3. \(K\)개의 중심점을 각각 할당된 데이터의 중심(평균)으로 옮긴다.
4. 모든 데이터가 할당된 \(K\)가 변하지 않을 때까지 2와 3을 반복한다.

구체적으로 알아보자. 위는 처음 2개의 중심점을 무작위로 정하고 각 데이터를 할당한 상태이다. 무작위로 지점을 정했기 때문에, 군집화가 잘 되어 있는 상태는 아니다.

이제 2개의 중심점을 해당하는 데이터의 중앙(평균 위치)으로 옮긴다. 아직 데이터의 할당은 바뀌지 않은 상태로, 중심점의 위치만 바뀌었다.

이제 바뀐 중심점에 데이터들을 다시 할당한다. 처음에 비해 더 합리적인 군집들이 나온 것을 볼 수 있다. 이런 과정을 반복해서 데이터를 각 군집에 할당하게 된다.

복잡도

K-Means의 단계별 시간 복잡도는 어떻게 될까? 우선 \(N\)개의 데이터를 \(K\)개의 중심점 중 하나에 할당해야 하는데, 그러기 위해서는 각 \(N\)과 \(K\) 사이의 거리를 재야 하므로 \(O(NK)\)의 시간이 걸린다. 이후 데이터의 평균을 구해서 중심점을 옮겨야 하는데, 이는 \(N\)개의 데이터에 대해서만 계산되므로 \(O(N)\)이다. 따라서 각 단계별 최종 시간복잡도는 \(O(NK)\)가 된다.

수렴

그런데 우리는 어떻게 K-Means가 수렴할 것이라 생각하는가? 알고리즘의 수행 과정에서 중심점들의 위치가 영원히 바뀌게 될 수도 있을 것이다. 하지만 실제로 그런 일은 일어나지 않는다. 직접 증명해보도록 하자.

1. 각 데이터를 \(x\), 군집의 중심들을 \(\mu\), 각 군집에 할당된 데이터들의 집합을 \(C\)라 하자.
   • 그렇다면 K-Means의 목적함수는 \(\min_\mu \min_C \sum\limits_{i=1}^k \sum\limits_{x \in C_i} \vert x - \mu_i \vert^2\)이다.
   • 이는 다시 말해 군집 중심의 위치 \(\mu\)와 데이터들의 군집에 대한 할당 \(C\)를 바꿔서 최솟값을 찾는 문제이다.
2. 각 데이터를 군집에 할당하는 단계는 수학적으로 아래와 같다.
   • \[\min_C \sum\limits_{i=1}^k \sum\limits_{x \in C_i} \vert x - \mu_i \vert^2\]
   • 위 수식은 쉽게 말하자면, 모든 군집 중심과 그 군집에 해당하는 데이터의 거리 총합이 최솟값이 되는 할당 \(C\)를 찾는 것이다.
3. 반대로 군집의 위치를 데이터의 중심으로 옮기는 단계는 수학적으로 아래와 같다.
   • \[\min_\mu \sum\limits_{i=1}^k \sum\limits_{x \in C_i} \vert x - \mu_i \vert^2\]
   • 위 수식 역시 모든 군집 중심과 그 군집에 해당하는 데이터의 거리 총합이 최솟값이 되도록 하는데, 이때는 \(C\)가 아니라 군집 중심의 위치 \(\mu\)를 바꾸는 것이다.
   • 최솟값을 구하기 위해서 \(\mu_i\)에 대하여 편미분하고 \(0\)이 되도록 하면 \(\mu_i = {1 \over \vert C_i \vert} \sum\limits_{x \in C_i}x\)가 된다.
   • 사실 이건 그냥 최소제곱법(Least Squares, 최소자승법)이고, 즉 거리 합을 최소화하는 각 군집 중심 \(\mu_i\)는 그 군집에 속한 데이터들의 평균이라는 것을 알 수 있다.
4. 2번 과정(\(C\)를 바꿈)은 오직 목적함수가 더 작아지는 경우에만 \(C\)가 변화하고, 그렇지 않은 경우 \(C\)가 그대로이다(수렴한다).
5. 3번 과정(\(\mu\)를 바꿈)에서 우리는 군집 중심을 평균 위치로 옮기면 거리의 총합이 최솟값이 됨을 증명했다. 즉 목적함수의 값은 점점 작아지거나, 최소한 같을 것이다.
6. 4와 5에 의하면, K-Means 알고리즘을 수행할수록 목적함수는 점점 작아지(거나 그대로)고, 더이상 작아질 수 없는 경우 \(C\)가 그대로이다(수렴한다). 또한 가능한 \(C\)의 개수는 \(KN\)개로 유한하므로 우리는 언젠가 수렴하리라는 것을 보장할 수 있다.

한계

K-Means 군집화도 단점이 있는데, 바로 처음 군집 중심의 위치에 따라서 결과가 바뀐다는 점이다. 즉, K-Means 알고리즘의 수렴이 보장된다는 것은 그 값이 최적이라는 뜻이 아니라, 더이상 K-Means를 수행해도 목적함수가 줄어들지 않게 될 뿐이라는 것을 의미한다.
또한, K-Means의 \(K\)를 결정하기 위한 문제 역시 해결해야 한다. 대상 데이터에 몇 개의 군집을 설정하는 게 적합할 것인가? 이를 위해 분석가의 사전 지식에 의존할 수도 있고 Elbow Method와 같은 방법을 사용할 수도 있다.
(이에 관해서는 기계학습 게시글에서 더 자세히 다루도록 하겠다.)
또한, K-Means는 거리(일반적으로 유클리드 거리)에 기반하여 군집화를 진행하는데, 따라서 데이터가 군집 중심에 가까우면 그 군집에 속한다는 전제를 준수하는 경우에만 의미가 있다. 이를테면 군집이 볼록이 아니거나(Non-Convex), 원형이 아니거나(Non-Round), 군집들의 밀도가 다르거나, … sklearn.make_circles()를 통해 만들어진 것처럼 사람이 보기엔 직관적인 군집화가 가능하지만 K-Means는 제대로 군집화하지 못하는 예시가 많다. 예를 들어 아래와 같은 형태의 데이터는 시각적으로는 직관적인 군집이 존재하지만, 수학적으로 생각하기엔 까다로운 케이스이다.

거리함수(Distance Metric)

지금까지, 우리는 거리를 재기 위해 일반적인 개념의 거리, 즉 유클리드 거리를 사용했다. 하지만, 아래 거리함수의 조건만 만족한다면, 다른 형태의 거리 역시 계산에 사용할 수 있다.

• Symmetry: \(\mathrm{dist}(x,y) = \mathrm{dist}(y,x)\)
  • \(x\)에서 \(y\)까지 거리는 \(y\)에서 \(x\)까지의 거리와 같다.
• Positivity: \(\mathrm{dist}(x,y) \ge 0\)
  • 두 지점 사이의 거리는 음수가 될 수 없다.
• Self-Similarity: \(\mathrm{dist}(x, y) = 0 \iff x = y\)
  • 두 지점이 같은 지점이라면 거리는 0이다.
  • 두 지점이 다른 지점이라면 거리는 0이 아니다.
• Triangle Inequality: \(\mathrm{dist}(x, y) + \mathrm{dist}(y, z) \ge \mathrm{dist}(x, z)\)
  • 두 지점을 바로 가는 거리는 다른 지점을 거쳐서 가는 거리보다 길 수 없다.

(구체적인 다른 형태의 거리는 기계학습 등 다른 강의복습에서 확인해보도록 하자.)

Agglomerative Clustering

앞서서 언급한 것처럼, Agglomerative Clustering이란 작은 군집을 뭉쳐서 더 큰 군집을 만드는 방법이다. 데이터 사이의 거리는 상기한 거리함수의 조건을 지키는 선에서 사용하거나, 혹은 간단하게 유클리드 거리를 사용할 수 있을 것이다. 그런데 군집 사이의 거리는 어떻게 측정하는가? 대략 세 가지 방법을 생각해볼 수 있다(물론 이 외에도 얼마든지 생각할 수 있을 것이다).

• Single Link: 두 군집의 데이터 중 가장 가까운 것 두 개를 취한다(최소 거리).
• Complete Link: 두 군집의 데이터 중 가장 먼 것 두 개를 취한다(최대 거리).
• Average Link: 가능한 모든 경우의 수를 평균내어 사용한다.

정리

오늘은 군집화, 그 중에서도 K-Means 알고리즘을 위주로 알아보았다. 거리 함수에 대해서도 잘 알아두면 좋을 듯하다.

다음 신경망에 관한 내용을 끝으로 인공지능 강의 정리가 끝나게 된다. 이후로는 어떤 강의를 다루어야 할까 생각 중이다.

• 2024 18
• 2023 143