1. K-Means
K-means는 이번 글에서 설명할 알고리즘 중 가장 간단하다. 주어진 데이터를 미리 지정한 K개의 클러스터로 묶는 알고리즘으로 각 샘플들은 각 클러스터 내에 존재하는 centroid(무게중심점)과의 거리가 다른 클러스터 내의 centroid와의 거리보다 가깝게 둔다.
1.1. 원리
입력값:
- k: 생성할 클러스터의 수
- X: n개의 샘플을 포함하고 있는 집합
출력값:
- k개의 클러스터
알고리즘:
- 초기값 설정: 다양한 방법 중 Random Partition이 가장 흔하고 쉬운 방법이지만 라이브러리를 호출하면 kmeans++가 기본값으로 설정되어 있다. a. Random Partition: 집합 X에서 k개의 랜덤한 샘플을 추출하고 이를 각 클러스터의 centroid(중심)으로 설정한다. b. kmeans++: 집합 X에서 1개의 랜덤 샘플을 추출한다. 이후 k개의 centroid가 선택될 때까지 X의 각 샘플마다 그 샘플과 가장 가까운 centroid까지의 거리 D(x)를 계산하고 아래 공식에 따른 확률에 기반한 임의의 샘플을 n번째 centroid로 설정한다. n이 k와 같아질 때까지 반복한 다음 그 값을 초기 centroid로 설정한다.
- 샘플을 각 클러스터에 할당: 각 샘플마다 샘플과 k개의 centroid 사이의 거리를 구하고 가장 거리가 centroid가 속한 클러스터에 해당 샘플을 배치한다.
: t번째 반복에서 i번째 클러스터에 속한 점의 집합
: t번째 반복에서 i번째 클러스터의 centroid
: 각 샘플 점
- centroid 재설정: 모든 샘플을 각 클러스터에 할당했다면 각 클러스터에서 새로운 무게중심을 계산하여 centroid를 재설정한다.
: t번째 반복에서 i번째 클러스터에 속한 샘플의 개수
- 더 이상 클러스터가 변하지 않을 때까지 과정 2.와 3.을 반복한다.
1.2. sklearn Kmeans 간단 예시
여러 라이브러리 중 sklearn을 통해 쉽게 K-means를 구현할 수 있다.
from sklearn.cluster import KMeans SEED = 42 k_val = 3 # 데이터 입력 # df는 기존에 있다고 가정. X = df[['latitude', 'longitude']] # 모델 생성 및 학습 kmeans = KMeans(n_clusters=k_val, random_state=SEED) # 모델 정의 kmeans.fit(X) # 클러스터링 계산 # 클러스터 예측 labels = kmeans.labels_ # 각 데이터의 클러스터 레이블 centers = kmeans.cluster_centers_ # 클러스터 중심점
1.3. 장점
계산이 비교적 빠르고 클러스터의 개수를 명확하게 정의할 수 있다.
1.4. 단점
클러스터가 나뉘어질 때 각 centroid에 대한 수직이등분선으로 나뉘어지기에 클러스터가 정다각형에 가까운 모양으로 한정되어진다. 그래서 복잡한 구조의 클러스터를 효과적으로 분리할 수 없다.
2. DBSCAN
DBSCAN(Density-Based Spatial Clustering of Applications with Noise)은 K-means와 Hierarchical와는 다르게 거리가 아닌 밀도를 기반으로 클러스터링을 한다. 간단히 설명하자면 특정 반경 ε 내에 n개 이상의 샘플이 있다면 클러스터가 되고 어느 클러스터에도 속하지 못한 점은 노이즈가 된다.
2.1. 원리
입력값:
- ε(epsilon): 클러스터를 만들 수 있는 최소 거리
- minPts: 클러스터를 만들 수 있는 최소한의 샘플 수
- X: n개의 샘플을 포함하고 있는 집합
출력값:
- n개의 샘플 중 k개를 포함하는 클러스터
- n개의 샘플 중 n-k개가 존재하는 노이즈
사진 출처: https://en.wikipedia.org/wiki/DBSCAN
자세한 알고리즘을 설명하기 전에 각 개념의 정의부터 살펴보자. 위의 사진에서 각 원의 반지름이 ε이고 minPts는 4이다.
- Core point: 자기 자신을 포함한 채로 minPts 이상의 점이 ε보다 가까운 거리에 존재한다면 그 점은 Core point가 된다. 사진에서는 점 A가 Core point이다. Core point로부터 ε보다 가까운 거리에 있는 그 점의 종류에 관계없이 모든 점은 서로 같은 클러스터에 속한다.
- directly reachable: 어느 한 점이 특정 Core point로부터 ε 내의 거리에 있다면 그 점은 directly reachable하며 Core point와 같은 클러스터에 속한다.
- Border point: 자신이 Core point는 아니지만 directly reachable한 점을 Boder point라고 한다. 사진에서는 점 B, 점 C가 그러하다.
- Noise: Core point도 아니고 directly reachable하지도 않으면 그 점은 Noise이다. Noise는 어떠한 클러스터에도 속하지 않는다. 사진에서는 점 N이 그러하다.
그에 따라 각 클러스터 내의 점들은 서로 density-reachable하다.
알고리즘:
- 아직 방문하지 않은 임의의 점을 판단한다: 그 점에서 ε 내에 점이 minPts보다 적다면 그 점을 Noise로 설정하고 1.로 돌아가 다음 점을 판단한다. 그 점에서 ε 내에 점이 minPts 이상이라면 그 점을 Core point P로 설정하고 P를 제외한 ε내의 점들의 집합 S를 설정한 뒤 반복문 2.를 실행한다.
- S에 속한 각 점 Q마다 아래 내용을 실행한다. Q가 노이즈였다면 Q를 P가 속한 클러스터에 포함시킨다. (Border point) Q가 defined 되어 있다면 (Border point 등이라면) 2.로 돌아가 S에 속한 다음 점을 실행한다. Q를 P가 속한 클러스터에 포함시킨다. Q로부터 ε 내에 있는 점들을 찾고 그 수가 minPts 이상이라면 그 점들을 P가 속한 클러스터에 포함시킨다. 반복문 2.가 완료되면 1.로 돌아가 다음 점을 판단한다.
2.2. sklearn DBSCAN 간단 예시
K-means와 마찬가지로 sklearn를 통해 쉽게 구현할 수 있다.
from sklearn.cluster import DBSCAN eps = 0.1 min_samples = 10 # 데이터 입력 # df는 기존에 있다고 가정. X = df[['latitude', 'longitude']] # 모델 생성 및 학습 dbscan = DBSCAN(eps=eps, min_samples=min_samples) # 모델 정의 dbscan.fit(X) # 클러스터링 계산 # 클러스터 예측 labels = dbscan.labels_ # 각 데이터의 클러스터 레이블
2.3. 장점
DBSCAN은 밀도를 기반으로 클러스터링을 하기 때문에 클러스터가 원형이 아닌 도넛 모양, 회오리 모양이어도 밀도만 충분히 크다면 얼마든지 같은 클러스터에 속하게 할 수 있다.
2.4. 단점
그러나 실제 상황에서는 모든 부분에서 데이터의 밀도가 높게 형성되지 않기 때문에 노이즈가 매우 빈번하게 발생한다. 노이즈는 어떤 클러스터에도 속해 있지 않기 때문에 사람 손을 쓰든 다른 방법을 쓰든 처리를 해야만한다. 아래 그림에서 파란 점이 노이즈이다. 왼쪽 그림에서 eps=0.02, min_samples = 2인 것을 보면 노이즈가 매우 심한 것을 알 수 있다. 또한 갈색 클러스터를 보면 다른 클러스터에 비해 개수가 과도하게 많아 좋은 클러스터링의 조건 5번에 부합하지 않음을 알 수 있다. 한편 가운데 사진에서는 eps=0.05로 조금 늘렸다. 그랬더니 주황색 점이 전체 영역을 다 차지하게 되었다. 오른쪽 사진에서는 eps=0.10으로 더 키웠는데 빨간색 점이 영역을 꽉 채우고 있지만 여전히 노이즈가 발생함을 알 수 있다.
이렇듯 좋은 클러스터링의 조건 5가지를 모두 부합시키기에는 매우 부적절한 클러스터링이 이루어지고 있다. 그 이유는 주문들의 밀도가 균일하지 않아서이다.
뿐만 아니라 eps과 min_samples의 값을 얼마로 정의해야하는 지도 문제이다. K-means는 k값 하나만 정해주면 되었지만 DBSCAN은 하이퍼파라미터 2개를 정의해줘야 해서 최적의 파라미터를 튜닝하기 더 복잡해진다. Optuna와 같이 hyperparameter optimization framework를 사용한다고 하더라도 만족할만한 클러스터를 형성하기 어려웠다.
3. Agglomerative Clustering
계층적 군집(Hierarchical Clustering)은 K-means와는 다르게 클러스터의 개수를 미리 정하지 않아도 된다. 계층적 군집은 이름 그대로 계층을 나누어 클러스터링을 진행하는 알고리즘이다. 계층적 군집은 크게 2가지로 나뉜다.
- Divisive(분할): 모든 샘플을 하나의 클러스터로 묶은 뒤 특정 조건이 만족될 때까지 클러스터를 작은 단위로 분할한다.
- Agglomerative(병합): 모든 샘플을 n개의 클러스터로 정의한 뒤 특정 조건이 만족될 때까지 클러스터를 큰 단위로 병합한다.
Divisive는 모든 샘플을 하나의 클러스터로 묶고 시작하기 때문에 샘플이 많아질수록 계산량이 기하급수적으로 늘어난다. 따라서 일반적으로 Agglomerative를 더 많이 사용한다.
2.3.3.1. 원리
입력값:
- X: n개의 샘플을 포함하고 있는 집합
출력값:
- 덴드로그램(Dendrogram)
알고리즘:
- 모든 샘플을 각각의 클러스터로 정의한다.
- 가장 가까운 두 클러스터를 하나의 클러스터로 병합한다.
- 하나의 클러스터가 남을 때까지 2번 과정을 반복한다.
3.2. Linkage
Agglomerative Clustering에서 '가장 가까운 두 클러스터'를 어떻게 정의하느냐에 따라 클러스터의 모양이 달라진다. 이를 Linkage라고 하며, 주로 4가지 방법이 사용된다.
- Single Linkage: 두 클러스터에서 가장 가까운 점 사이의 거리를 기준으로 병합한다.
- Complete Linkage: 두 클러스터에서 가장 먼 점 사이의 거리를 기준으로 병합한다.
- Average Linkage: 두 클러스터의 모든 점들 사이의 평균 거리를 기준으로 병합한다.
- Ward's Linkage: 두 클러스터를 병합했을 때, 클러스터 내의 분산이 가장 작아지는 방향으로 병합한다. (기본값)
3.3. sklearn Agglomerative Clustering 간단 예시
마찬가지로 sklearn을 통해 쉽게 구현할 수 있다.
from sklearn.cluster import AgglomerativeClustering # 데이터 입력 # df는 기존에 있다고 가정. X = df[['latitude', 'longitude']] # 모델 생성 및 학습 agg = AgglomerativeClustering(n_clusters=3, linkage='ward') # 모델 정의 agg.fit(X) # 클러스터링 계산 # 클러스터 예측 labels = agg.labels_ # 각 데이터의 클러스터 레이블
3.4. 장점
클러스터의 개수를 미리 정하지 않아도 되며, 덴드로그램을 통해 클러스터링 과정을 시각적으로 확인할 수 있다.
3.5. 단점
계산량이 많아 데이터가 클 경우 속도가 느려질 수 있으며, 한번 병합된 클러스터는 다시 나눌 수 없다는 단점이 있다.