비지도학습(Unsupervised Learning) — K-Means, DBSCAN
라벨도 없고, 선생님도 없습니다. 알고리즘이 스스로 구조를 찾습니다.
유형: Build
언어: Python
선수 지식: Phase 1 (Norm과 거리, 확률과 분포), Phase 2 Lessons 1-6
예상 시간: 약 90분
학습 목표
- K-Means, DBSCAN, 가우시안 혼합 모델(Gaussian Mixture Model, GMM)을 처음부터 구현하고 군집화(clustering) 동작을 비교합니다.
- 실루엣 점수(Silhouette score)와 엘보 방법(Elbow method)을 사용해 군집(cluster) 품질을 평가하고 적절한 K를 선택합니다.
- DBSCAN이 K-Means보다 나은 상황을 설명하고, 비구형 군집(cluster)과 이상치를 처리하는 알고리즘을 식별합니다.
- 군집화(clustering) 방법으로 정상 패턴에서 벗어난 포인트를 표시하는 이상 탐지(Anomaly detection) 파이프라인을 만듭니다.
문제
지금까지의 머신러닝(Machine Learning; ML) 강의는 대부분 라벨이 있는 데이터를 가정했습니다. "여기 입력이 있고, 여기에 정답 출력이 있다"는 식입니다. 하지만 현실에서 라벨은 비쌉니다. 병원에는 수백만 건의 환자 기록이 있지만, 질병 범주를 사람이 전부 붙여두지는 않았을 수 있습니다. 이커머스 사이트에는 수백만 개의 사용자 세션(session)이 있지만, 고객 세그먼트(segment)를 사람이 직접 라벨링하지 않았을 수 있습니다. 보안팀에는 네트워크 로그(network log)가 있지만, 모든 이상치(anomaly)가 표시되어 있지는 않을 수 있습니다.
비지도 학습(Unsupervised learning)은 무엇을 찾아야 하는지 알려주지 않아도 패턴(pattern)을 찾습니다. 비슷한 데이터 포인트를 묶고, 숨은 구조를 발견하고, 이상치를 드러냅니다. 지도 학습(Supervised learning)이 정답지가 있는 교과서로 배우는 것이라면, 비지도 학습은 원시 데이터(raw data)를 바라보다가 패턴이 드러나게 만드는 일에 가깝습니다.
문제는 라벨이 없으면 "맞다" 또는 "틀리다"를 직접 측정할 수 없다는 점입니다. 알고리즘이 찾은 구조가 의미 있는지 평가하려면 다른 도구가 필요합니다.
개념
군집화(Clustering): 비슷한 것끼리 묶기
군집화(Clustering)는 각 데이터 포인트를 군집(cluster)에 할당합니다. 같은 군집 안의 포인트는 다른 군집의 포인트보다 서로 더 비슷해야 합니다. 핵심 질문은 언제나 같습니다. "비슷하다"는 무엇을 뜻하나요?
flowchart LR
A[Raw Data] --> B{방법 선택}
B --> C[K-Means]
B --> D[DBSCAN]
B --> E[Hierarchical]
B --> F[GMM]
C --> G[평평한 구형 군집]
D --> H[임의 모양, 노이즈 탐지]
E --> I[중첩 군집 트리]
F --> J[소프트 할당, 타원형 군집]
K-Means: 기본 도구
K-Means는 데이터를 정확히 K개의 군집(cluster)으로 나눕니다. 각 군집에는 중심점(centroid)이 있고, 모든 포인트는 가장 가까운 중심점에 속합니다.
Lloyd 알고리즘은 다음과 같습니다.
- K개의 무작위 포인트를 초기 중심점(centroid)으로 선택합니다.
- 각 데이터 포인트를 가장 가까운 중심점에 할당합니다.
- 각 군집의 중심점(centroid)을 할당된 포인트들의 평균으로 다시 계산합니다.
- 할당이 더 이상 바뀌지 않을 때까지 2-3단계를 반복합니다.
목적 함수인 관성(Inertia)은 각 포인트와 할당된 중심점(centroid) 사이의 제곱 거리 합입니다. K-Means는 이를 최소화하지만 지역 최솟값(Local minimum)만 찾습니다. 초기화가 다르면 결과도 달라질 수 있습니다.
K 선택하기
표준적인 방법은 두 가지입니다.
엘보 방법(Elbow method): K = 1, 2, 3, ...에 대해 K-Means를 실행합니다. K에 따른 관성(inertia)을 그립니다. 군집을 더 추가해도 관성이 크게 줄지 않는 "팔꿈치" 지점을 찾습니다.
실루엣 점수(Silhouette score): 각 포인트가 자기 군집과 얼마나 비슷한지(a), 가장 가까운 다른 군집과 얼마나 다른지(b)를 측정합니다. 실루엣 계수는 (b - a) / max(a, b)이고, -1에서 +1 사이입니다. -1은 잘못된 군집에 있다는 뜻이고, +1은 잘 군집화되었다는 뜻입니다. 전체 점수는 모든 포인트의 평균입니다.
DBSCAN: 밀도 기반 군집화(Density-Based Clustering)
K-Means는 군집(cluster)이 구형이라고 가정하고 K를 미리 지정해야 합니다. DBSCAN은 두 가정을 모두 하지 않습니다. DBSCAN은 밀도가 높은 영역을 군집으로 찾고, 희소한 영역으로 군집을 구분합니다.
두 파라미터가 있습니다.
- eps: 이웃 영역(neighborhood)의 반경
- min_samples: 밀도 있는 영역을 만들기 위해 필요한 최소 포인트 수
포인트는 세 유형으로 나뉩니다.
- 핵심 포인트(Core point): eps 거리 안에 최소
min_samples개 포인트가 있는 점
- 경계 포인트(Border point): 핵심 포인트의 eps 안에 있지만 자신은 핵심 포인트가 아닌 점
- 노이즈 포인트(Noise point): 핵심도 경계도 아닌 점. 이상치입니다.
DBSCAN은 eps 안에서 서로 연결된 핵심 포인트(core point)를 같은 군집으로 묶습니다. 경계 포인트(border point)는 가까운 핵심 포인트의 군집에 합류합니다. 노이즈 포인트(noise point)는 어떤 군집에도 속하지 않습니다.
강점은 임의 모양의 군집을 찾고, 군집 개수를 자동으로 결정하며, 이상치를 식별한다는 점입니다. 약점은 군집마다 밀도가 크게 다르면 어려워진다는 점입니다.
계층적 군집화(Hierarchical Clustering)
계층적 군집화(Hierarchical clustering)는 중첩 군집의 트리(tree), 즉 덴드로그램(Dendrogram)을 만듭니다.
병합식(Agglomerative, bottom-up) 방식은 다음과 같습니다.
- 각 포인트를 자기만의 군집으로 시작합니다.
- 가장 가까운 두 군집을 합칩니다.
- 군집이 하나만 남을 때까지 반복합니다.
- 원하는 수준(level)에서 덴드로그램(dendrogram)을 잘라 K개의 군집을 얻습니다.
군집 사이의 가까움은 여러 방식으로 측정할 수 있습니다.
- 단일 연결(Single linkage): 두 군집에 있는 임의 두 점 사이의 최소 거리
- 완전 연결(Complete linkage): 두 군집에 있는 임의 두 점 사이의 최대 거리
- 평균 연결(Average linkage): 모든 쌍(pair) 거리의 평균
- Ward 방법(Ward's method): 군집 내부 분산의 총 증가가 가장 작은 병합
가우시안 혼합 모델(Gaussian Mixture Model, GMM)
K-Means는 하드 할당(hard assignment)을 사용합니다. 각 포인트는 정확히 하나의 군집에 속합니다. GMM은 소프트 할당(soft assignment)을 사용합니다. 각 포인트는 각 군집에 속할 확률을 갖습니다.
GMM은 데이터가 K개의 가우시안 분포(Gaussian distribution) 혼합에서 생성되었다고 가정합니다. 각 가우시안(Gaussian)은 자기 평균과 공분산(Covariance)을 갖습니다. 기대-최대화(Expectation-Maximization, EM) 알고리즘은 두 단계를 반복합니다.
- E-step: 각 포인트가 각 가우시안에 속할 확률을 계산합니다.
- M-step: 데이터 가능도(likelihood)가 커지도록 각 가우시안의 평균, 공분산, 혼합 가중치(mixing weight)를 업데이트합니다.
GMM은 K-Means처럼 구형 군집만이 아니라 타원형 군집도 모델링할 수 있고, 겹치는 군집을 자연스럽게 다룰 수 있습니다.
언제 무엇을 쓸까
| 방법 | 적합한 경우 | 피해야 할 경우 |
|---|
| K-Means | 큰 데이터셋, 구형 군집, K를 아는 경우 | 불규칙한 모양, 이상치가 있는 경우 |
| DBSCAN | K를 모르는 경우, 임의 모양, 이상치 탐지 | 밀도가 크게 다른 군집, 매우 높은 차원 |
| 계층적 군집화(Hierarchical) | 작은 데이터셋, 덴드로그램(dendrogram)이 필요한 경우, K를 모르는 경우 | 큰 데이터셋. 메모리 O(n^2) |
| GMM | 겹치는 군집, 소프트 할당(soft assignment)이 필요한 경우 | 매우 큰 데이터셋, 차원이 너무 많은 경우 |
군집화를 이용한 이상 탐지
군집화(Clustering)는 자연스럽게 이상 탐지를 지원합니다.
- K-Means: 어떤 중심점(centroid)에서도 먼 포인트는 이상치(anomaly)입니다.
- DBSCAN: 노이즈 포인트(noise point)는 정의상 이상치입니다.
- GMM: 모든 가우시안(Gaussian)에서 확률이 낮은 포인트는 이상치입니다.
만들어 보기
Step 1: K-Means 처음부터 구현하기
import math
import random
def euclidean_distance(a, b):
return math.sqrt(sum((ai - bi) ** 2 for ai, bi in zip(a, b)))
def kmeans(data, k, max_iterations=100, seed=42):
random.seed(seed)
n_features = len(data[0])
centroids = random.sample(data, k)
for iteration in range(max_iterations):
clusters = [[] for _ in range(k)]
assignments = []
for point in data:
distances = [euclidean_distance(point, c) for c in centroids]
nearest = distances.index(min(distances))
clusters[nearest].append(point)
assignments.append(nearest)
new_centroids = []
for cluster in clusters:
if len(cluster) == 0:
new_centroids.append(random.choice(data))
continue
centroid = [
sum(point[j] for point in cluster) / len(cluster)
for j in range(n_features)
]
new_centroids.append(centroid)
if all(
euclidean_distance(old, new) < 1e-6
for old, new in zip(centroids, new_centroids)
):
print(f" {iteration + 1}번째 반복(iteration)에서 수렴했습니다")
break
centroids = new_centroids
return assignments, centroids
Step 2: 엘보 방법과 실루엣 점수
def compute_inertia(data, assignments, centroids):
total = 0.0
for point, cluster_id in zip(data, assignments):
total += euclidean_distance(point, centroids[cluster_id]) ** 2
return total
def silhouette_score(data, assignments):
n = len(data)
if n < 2:
return 0.0
clusters = {}
for i, c in enumerate(assignments):
clusters.setdefault(c, []).append(i)
if len(clusters) < 2:
return 0.0
scores = []
for i in range(n):
own_cluster = assignments[i]
own_members = [j for j in clusters[own_cluster] if j != i]
if len(own_members) == 0:
scores.append(0.0)
continue
a = sum(euclidean_distance(data[i], data[j]) for j in own_members) / len(own_members)
b = float("inf")
for cluster_id, members in clusters.items():
if cluster_id == own_cluster:
continue
avg_dist = sum(euclidean_distance(data[i], data[j]) for j in members) / len(members)
b = min(b, avg_dist)
if max(a, b) == 0:
scores.append(0.0)
else:
scores.append((b - a) / max(a, b))
return sum(scores) / len(scores)
def find_best_k(data, max_k=10):
print("엘보 방법:")
inertias = []
for k in range(1, max_k + 1):
assignments, centroids = kmeans(data, k)
inertia = compute_inertia(data, assignments, centroids)
inertias.append(inertia)
print(f" K={k}: 관성(inertia)={inertia:.2f}")
print("\n실루엣 점수:")
for k in range(2, max_k + 1):
assignments, centroids = kmeans(data, k)
score = silhouette_score(data, assignments)
print(f" K={k}: 실루엣(silhouette)={score:.4f}")
return inertias
Step 3: DBSCAN 처음부터 구현하기
def dbscan(data, eps, min_samples):
n = len(data)
labels = [-1] * n
cluster_id = 0
def region_query(point_idx):
neighbors = []
for i in range(n):
if euclidean_distance(data[point_idx], data[i]) <= eps:
neighbors.append(i)
return neighbors
visited = [False] * n
for i in range(n):
if visited[i]:
continue
visited[i] = True
neighbors = region_query(i)
if len(neighbors) < min_samples:
labels[i] = -1
continue
labels[i] = cluster_id
seed_set = list(neighbors)
seed_set.remove(i)
j = 0
while j < len(seed_set):
q = seed_set[j]
if not visited[q]:
visited[q] = True
q_neighbors = region_query(q)
if len(q_neighbors) >= min_samples:
for nb in q_neighbors:
if nb not in seed_set:
seed_set.append(nb)
if labels[q] == -1:
labels[q] = cluster_id
j += 1
cluster_id += 1
return labels
Step 4: 가우시안 혼합 모델(Gaussian Mixture Model, EM 알고리즘)
def gmm(data, k, max_iterations=100, seed=42):
random.seed(seed)
n = len(data)
d = len(data[0])
indices = random.sample(range(n), k)
means = [list(data[i]) for i in indices]
variances = [1.0] * k
weights = [1.0 / k] * k
def gaussian_pdf(x, mean, variance):
d = len(x)
coeff = 1.0 / ((2 * math.pi * variance) ** (d / 2))
exponent = -sum((xi - mi) ** 2 for xi, mi in zip(x, mean)) / (2 * variance)
return coeff * math.exp(max(exponent, -500))
for iteration in range(max_iterations):
responsibilities = []
for i in range(n):
probs = []
for j in range(k):
probs.append(weights[j] * gaussian_pdf(data[i], means[j], variances[j]))
total = sum(probs)
if total == 0:
total = 1e-300
responsibilities.append([p / total for p in probs])
old_means = [list(m) for m in means]
for j in range(k):
r_sum = sum(responsibilities[i][j] for i in range(n))
if r_sum < 1e-10:
continue
weights[j] = r_sum / n
for dim in range(d):
means[j][dim] = sum(
responsibilities[i][j] * data[i][dim] for i in range(n)
) / r_sum
variances[j] = sum(
responsibilities[i][j]
* sum((data[i][dim] - means[j][dim]) ** 2 for dim in range(d))
for i in range(n)
) / (r_sum * d)
variances[j] = max(variances[j], 1e-6)
shift = sum(
euclidean_distance(old_means[j], means[j]) for j in range(k)
)
if shift < 1e-6:
print(f" GMM이 {iteration + 1}번째 반복(iteration)에서 수렴했습니다")
break
assignments = []
for i in range(n):
assignments.append(responsibilities[i].index(max(responsibilities[i])))
return assignments, means, weights, responsibilities
Step 5: 테스트 데이터 만들고 실행하기
def make_blobs(centers, n_per_cluster=50, spread=0.5, seed=42):
random.seed(seed)
data = []
true_labels = []
for label, (cx, cy) in enumerate(centers):
for _ in range(n_per_cluster):
x = cx + random.gauss(0, spread)
y = cy + random.gauss(0, spread)
data.append([x, y])
true_labels.append(label)
return data, true_labels
def make_moons(n_samples=200, noise=0.1, seed=42):
random.seed(seed)
data = []
labels = []
n_half = n_samples // 2
for i in range(n_half):
angle = math.pi * i / n_half
x = math.cos(angle) + random.gauss(0, noise)
y = math.sin(angle) + random.gauss(0, noise)
data.append([x, y])
labels.append(0)
for i in range(n_half):
angle = math.pi * i / n_half
x = 1 - math.cos(angle) + random.gauss(0, noise)
y = 1 - math.sin(angle) - 0.5 + random.gauss(0, noise)
data.append([x, y])
labels.append(1)
return data, labels
if __name__ == "__main__":
centers = [[2, 2], [8, 3], [5, 8]]
data, true_labels = make_blobs(centers, n_per_cluster=50, spread=0.8)
print("=== 3개 덩어리(blob)에 K-Means 적용 ===")
assignments, centroids = kmeans(data, k=3)
print(f" 중심점(centroids): {[[round(c, 2) for c in cent] for cent in centroids]}")
sil = silhouette_score(data, assignments)
print(f" 실루엣 점수: {sil:.4f}")
print("\n=== 엘보 방법 ===")
find_best_k(data, max_k=6)
print("\n=== 3개 덩어리(blob)에 DBSCAN 적용 ===")
db_labels = dbscan(data, eps=1.5, min_samples=5)
n_clusters = len(set(db_labels) - {-1})
n_noise = db_labels.count(-1)
print(f" 군집(cluster) {n_clusters}개와 노이즈 포인트(noise point) {n_noise}개를 찾았습니다")
print("\n=== 3개 덩어리(blob)에 GMM 적용 ===")
gmm_assignments, gmm_means, gmm_weights, _ = gmm(data, k=3)
print(f" 평균(means): {[[round(m, 2) for m in mean] for mean in gmm_means]}")
print(f" 가중치(weights): {[round(w, 3) for w in gmm_weights]}")
gmm_sil = silhouette_score(data, gmm_assignments)
print(f" 실루엣 점수: {gmm_sil:.4f}")
print("\n=== 반달(moon) 데이터, 비구형 군집(cluster)에 DBSCAN 적용 ===")
moon_data, moon_labels = make_moons(n_samples=200, noise=0.1)
moon_db = dbscan(moon_data, eps=0.3, min_samples=5)
n_moon_clusters = len(set(moon_db) - {-1})
n_moon_noise = moon_db.count(-1)
print(f" 군집(cluster) {n_moon_clusters}개와 노이즈 포인트(noise point) {n_moon_noise}개를 찾았습니다")
print("\n=== 반달(moon) 데이터에 K-Means 적용, 제대로 분리하지 못함 ===")
moon_km, moon_centroids = kmeans(moon_data, k=2)
moon_sil = silhouette_score(moon_data, moon_km)
print(f" 실루엣 점수: {moon_sil:.4f}")
print(" K-Means는 반달 모양이 구형이 아니기 때문에 잘못 나눕니다")
print("\n=== DBSCAN으로 이상 탐지 ===")
anomaly_data = list(data)
anomaly_data.append([20.0, 20.0])
anomaly_data.append([-5.0, -5.0])
anomaly_data.append([15.0, 0.0])
anomaly_labels = dbscan(anomaly_data, eps=1.5, min_samples=5)
anomalies = [
anomaly_data[i]
for i in range(len(anomaly_labels))
if anomaly_labels[i] == -1
]
print(f" 이상치(anomaly) {len(anomalies)}개를 탐지했습니다")
for a in anomalies[-3:]:
print(f" 포인트(point) {[round(v, 2) for v in a]}")
사용하기
scikit-learn에서는 같은 알고리즘을 간단히 사용할 수 있습니다.
from sklearn.cluster import KMeans, DBSCAN, AgglomerativeClustering
from sklearn.mixture import GaussianMixture
from sklearn.metrics import silhouette_score as sklearn_silhouette
km = KMeans(n_clusters=3, random_state=42).fit(data)
db = DBSCAN(eps=1.5, min_samples=5).fit(data)
agg = AgglomerativeClustering(n_clusters=3).fit(data)
gmm_model = GaussianMixture(n_components=3, random_state=42).fit(data)
직접 구현한 버전은 라이브러리가 실제로 무엇을 계산하는지 보여줍니다. K-Means는 할당과 중심점(centroid) 재계산을 반복합니다. DBSCAN은 밀도 높은 시작점(seed)에서 군집(cluster)을 확장합니다. GMM은 기댓값 계산(expectation)과 최대화(maximization)를 번갈아 수행합니다. 라이브러리 버전은 수치 안정성, 더 나은 초기화(K-Means++), GPU 가속 등을 추가하지만 핵심 로직(core logic)은 같습니다.
출하하기
이 lesson은 K-Means, DBSCAN, GMM의 작동 구현을 산출합니다. 이 군집화(clustering) 코드는 더 고급 비지도 방법의 기반으로 재사용할 수 있습니다.
연습문제
-
K-Means++ 초기화를 구현합니다. 중심점(centroid)을 완전히 무작위로 고르는 대신, 첫 중심점은 무작위로 고르고 이후 중심점은 기존 중심점 중 가장 가까운 것까지의 제곱 거리에 비례해 선택합니다. 무작위 초기화와 수렴 속도를 비교합니다.
-
계층적 병합 군집화(clustering)를 코드에 추가합니다. Ward 연결(Ward linkage)을 구현하고, 병합(merge)의 중첩 리스트(list)로 덴드로그램(dendrogram)을 만듭니다. 여러 수준(level)에서 잘라 K-Means 결과와 비교합니다.
-
간단한 이상 탐지 파이프라인(pipeline)을 만듭니다. 같은 데이터에 DBSCAN과 GMM을 실행하고, 두 방법이 모두 이상치라고 동의한 포인트를 표시합니다. DBSCAN에서는 노이즈(noise), GMM에서는 낮은 확률 포인트입니다. 겹치는 정도를 측정하고 두 방법이 언제 다르게 판단하는지 논의합니다.
핵심 용어
| 용어 | 흔한 설명 | 실제 의미 |
|---|
| 군집화(Clustering) | 비슷한 것끼리 묶기 | 특정 거리 척도에서 그룹 내부 유사도가 그룹 사이 유사도보다 크도록 데이터를 부분집합(subset)으로 나누는 것 |
| 중심점(Centroid) | 군집 중심 | K-Means에서 군집 대표로 쓰는, 해당 군집 포인트들의 평균 |
| 관성(Inertia) | 군집이 얼마나 조밀한지 | 각 포인트와 할당된 중심점(centroid) 사이의 제곱 거리 합 |
| 실루엣 점수(Silhouette score) | 군집이 얼마나 잘 분리됐는지 | 각 포인트에 대해 (b - a) / max(a, b)를 계산한 값 |
| 핵심 포인트(Core point) | 밀도 높은 영역의 점 | DBSCAN에서 eps 거리 안에 최소 min_samples개 이웃이 있는 점 |
| EM 알고리즘(EM algorithm) | 소프트 K-Means | 소속 확률(membership probability)을 계산하는 E-step과 분포 파라미터를 갱신하는 M-step을 반복하는 방법 |
| 덴드로그램(Dendrogram) | 군집 트리 | 계층적 군집화에서 군집이 병합된 순서와 거리를 보여주는 트리 다이어그램(tree diagram) |
| 이상치(Anomaly) | 이상치 | DBSCAN의 노이즈(noise) 또는 GMM의 낮은 확률처럼 기대 패턴에 맞지 않는 데이터 포인트 |
더 읽을거리