Clustering

Unsupervised Learning

• 지도 학습 (Supervised Learning)
  : 입력 데이터에 대해 정답(label)이 붙어 있는 상태에서 모델을 학습

• 비지도 학습 (Unsupervised Learning)
  : 데이터에 레이블(정답)이 전혀 없는 상태에서,
  데이터 안에 숨어 있는 구조나 규칙(패턴)을 찾아내는 학습 방법

What is Clustering?

클러스터링
: 서로 유사(similar) 한 데이터 포인트끼리 하나의 그룹(클러스터)으로 묶는 기법

• 유사도는 사용자가 선택한 기준에 따라 정의됨

비지도 학습의 한 종류

• 데이터에 미리 라벨(label)이 붙어 있지 않은 상태에서
  어떻게 그룹화할지 사전에 알려주지 않고 스스로 군집을 찾아냄
• 데이터 내부에 숨어 있는 패턴이나 구조(Structure)를 발견

How to Define Similarity?

클러스터링은 데이터 포인트를 서로 유사한 것들끼리 묶는 기법
유사도의 정의는 데이터에서 찾고자 하는 특징(패턴)에 따라 달라짐

올바른 유사도 측정값(Measure)을 선택하는 것이 중요

ex. 유사도 표현 방식

→ C와 D가 A와 B보다 더 유사

Similarity Measures

p차원 실수 벡터
$X = (x_1, x_2, \ldots, x_p)\;\text{와}\;Y = (y_1, y_2, \ldots, y_p)\in \mathbb{R}^p$

유클리드 거리 (Euclidean Distance)

p차원 공간에서 X와 Y를 잇는 직선(최단 경로) 길이.

맨해튼 거리 (Manhattan Distance, L₁ 거리)

좌표별 차이를 절댓값으로 합산한 형태.
: 격자 모양(grid) 위에서만 이동한다면
(→, ↓ 같은 축 방향만 움직일 때), X에서 Y까지 가는 총 이동량.

민코프스키 거리 (Minkowski Distance)

q=1인 경우 → 맨해튼 거리
q=2인 경우 → 유클리드 거리

q가 클수록 큰 좌표 차이에 더 민감하게 반응
: q<1으로 두면 이상치가 더 강조, q>2이면 큰 차이에 더욱 반응.

코사인 유사도 (Cosine Similarity)

X와 Y가 이루는 각 $θ$의 코사인 값.

값의 범위: −1에서 +1.

• +1: 방향이 완전히 동일(정규화된 벡터가 겹침) → 매우 유사
• 0: 완전히 직교 → 유사도 없음
• -1: 정반대 방향 → 전혀 유사하지 않음

Types of Clustering

Hard Clustering vs. Soft (Fuzzy) Clustering

• Hard Clustering
  : 각 데이터 포인트는 오직 하나의 클러스터에만 속함

• Soft (Fuzzy) Clustering
  : 각 데이터 포인트가 여러 개의 클러스터에 동시에
  부분적으로 속할 수 있도록 허용하는 방식

Flat vs. Hierarchical Clustering

• Flat Clustering (Partitional Clustering)
  : 모든 클러스터가 동일한 수준(level)에 존재,
  어떠한 클러스터도 다른 클러스터의 상위(부모) 또는 하위(자식) 관계가 아님

• Hierarchical Clustering
  : 클러스터들이 트리(tree) 형태로 계층 구조를 이루는 방식

Methods

주요 클러스터링 기법들

• 계층적 클러스터링 (Hierarchical Clustering)
• K-Means Clustering
• DBSCAN
• GMM (Gaussian Mixture Model)

Hierarchical Clustering

병합형 군집화(Agglomerative Clustering)

• 처음에 각각의 데이터 포인트를 독립된 하나의 클러스터로 간주

• 유사도가 가장 높은 (또는 거리가 가장 가까운) 두 클러스터를
  반복적으로 병합

• 최종적으로 하나의 거대한 클러스터가 될 때까지 진행

덴드로그램(Dendrogram)

• 병합 높이(거리 값)
  : 서로 병합된 두 개체(클러스터)가 세로축 높이가 낮을수록
  더 유사한(가까운) 두 점 또는 클러스터

• 원하는 개수의 클러스터 선택(Cutting the Tree)
  : 덴드로그램을 특정 높이(거리 값 기준)에서 수평선으로 자르면,
  수평선 아래에 분리되어 있는 가지(branch) 개수만큼의 클러스터가 형성.

두 클러스터 사이 거리를 재는 방법

Single Linkage (단일 연결법)

두 클러스터 A와 B 사이의 거리
= 클러스터 A내 어떤 점 x와 클러스터 B내 어떤 점 y간의 거리 중 최솟값

Complete Linkage (완전 연결법)

두 클러스터 A와 B 사이의 거리
= 클러스터 A 내 모든 점과 클러스터 B 내 모든 점 간 거리 중에서 최댓값

Average Linkage (평균 연결법)

두 클러스터 A와 B 사이의 거리
= 클러스터 A 내 모든 점과 B 내 모든 점 쌍 간 거리의 평균

Centroid Linkage (중심 연결법)

두 클러스터 A와 B 사이의 거리
= 각 클러스터 A, B에 대해 두 중심(centroid) 간 거리

Ward Linkage (워드 연결법)

두 클러스터 A와 B를 병합할 때 클러스터 내 분산이 최소로 증가하도록.

• 병합 후 클러스터 내부 응집도가 최대한 유지되도록(분산이 최소로 증가) 함
• 균일한 크기와 형태를 갖는 클러스터를 형성하는 경향이 있음

Hierarchical Clustering 의 장단점

Pros (장점)

사전 클러스터 수 지정 불필요

• K-means처럼 군집 개수 k를 미리 정하지 않아도 됨
• 덴드로그램(dendrogram)을 통해
  분할할 높이만 선택하면 원하는 개수의 군집을 얻을 수 있음

상세한 군집 관계 파악

• 덴드로그램을 통해 각 데이터 포인트가 어떻게 점진적으로 묶이는지를 시각적으로 확인 가능

클러스터 형태에 대한 유연성

• 구형(spherical) 모양뿐 아니라, 사슬 형태(chain-like), 타원형(elliptical), 불규칙(irregular) 모양 등 다양한 분포를 포착 가능

소규모 데이터셋에 적합

• 작은 규모에서 데이터 구조를 파악하기에 효과적

Cons (단점)

확장성(Scalability) 이슈

• 시간 복잡도 $O(n^3)$, 공간(메모리) 복잡도 $O(n^2)$.
  대규모 데이터셋에는 적용이 어려움

노이즈(Noise) 및 이상치(Outliers)에 민감

• 초기 단계에서 이상치 하나가 다른 데이터와 먼저 병합되면,
  → 덴드로그램 전체 구조가 뒤틀릴 수 있음

링케이지(linkage) 기준에 따른 임의성

• 어떤 linkage가 최선인지를 판별할 객관적 지표가 없음

K-Means Clustering

K-Means Clustering 알고리즘의 절차

주어진 데이터셋을 k개의 클러스터로 나누되,
클러스터 내 응집도(점들 간 거리의 제곱합 최소화)가 최대화되도록 함.

1. 클러스터 개수 k 선택

2. 클러스터 중심(centroids) 초기화

• 방법 1: 무작위 데이터 포인트 선택
  전체 데이터에서 k개의 점을 랜덤하게 뽑아, 이를 초기 중심으로 설정

• 방법 2: 랜덤 할당 후 평균 계산
  각 점에 무작위로 군집 번호를 부여하고,
  각 군집에 속한 점들의 평균을 내서 초기 중심을 구함.

• 방법 3: K-means++
  첫 번째 중심을 무작위로 고른 뒤,
  다음 중심은 기존 중심과의 거리에 비례해 확률적으로 선택

3. 데이터 할당(Assignment) 단계

각 데이터 포인트 $x_i$에 대해,
현재 할당된 k개의 중심 중에서 가장 가까운 중심을 찾아, 그 군집에 할당

4. 중심 업데이트(Update) 단계

3단계에서 새로 할당된 군집 구성원(점)들의 평균을 계산하여,
각 군집의 중심을 갱신

5. 반복(Iteration)

할당(3번) → 중심 업데이트(4번) 과정을 반복

K-Means Clustering 알고리즘의 종료(Stopping) 조건

• 고정된 반복 횟수
  전에 정해둔 최대 반복 횟수에 도달하면 무조건 알고리즘을 멈춤

• Clusters Remain Unchanged
  한 iteration에서 각 데이터 포인트가 속한 클러스터 번호(레이블)가 전의 이터레이션과 동일해지는 시점에 알고리즘을 멈춤

• 센트로이드 수렴(Centroid Convergence)
  각 이터레이션에서 모든 클러스터 중심(centroid) 이동 거리를 계산하여,
  그 이동량이 미리 정해둔 임계값(ε) 이하로 줄어들었을 때 알고리즘을 멈춤

K-Means++

초기 중심들을 데이터 분포를 고려해 최대한 멀리 떨어뜨려 선택하여

• K-Means 수렴 속도를 높이고
• 더 안정적인 군집화 결과를 얻도록 돕는 초기화 알고리즘

K-Means++ 초기화 절차

1. 첫 번째 중심 무작위 선택

2. 아직 선택되지 않은 각 데이터 x에 대해,
   현재까지 선택된 중심 중 가장 가까운 중심과의 거리 $D(x)$를 계산

3. 다음 중심으로 선택될 후보 x를, 거리 D(x)에 비례하여 확률적으로 뽑음
   : 가장 먼 데이터일수록 중심으로 뽑힐 확률이 높음

4. 과정을 반복해 k개의 중심 확보

K-Means Clustering의 주요 장단점

Pros (장점)

효율성 (Efficiency)

• 계층적 군집화(Hierarchical)에 비해 계산 속도가 빠르고
  메모리 소모가 적어, 대규모 데이터셋에 더 적합

Easy to Implement and Interpret

• 알고리즘이 직관적이며 구현이 쉬움

Cons (단점)

군집 수 사전 결정 필요 (Requirement of Cluster Number)

• 알고리즘을 실행하기 전에 반드시 몇 개의 클러스터 k를 만들 것인지를 지정해야 함

초기값 민감성 (Sensitivity to Initial Conditions)

• 초기 중심(centroids) 위치에 따라 최종 결과가 크게 달라질 수 있음

Poor Performance with Non-Spherical Clusters

• K-Means는 구형 군집을 가정하고 설계되었기 때문에,
  타원형(elliptical) 분포, 밀도가 서로 다른 군집, 복잡한 형상(반달, 링 형태) 분포를 제대로 나누지 못함

이상치(Outliers) 민감성 (Sensitivity to Outliers)

• 이상치 한두 개가 클러스터 중심을 크게 왜곡할 수 있음

DBSCAN (Density-Based Spatial Clustering of Applications with Noise)

K-Means vs. DBSCAN 비교

K-Means의 한계

• 군집 개수 k를 미리 지정해야 함
• 구형(원형) 클러스터에 최적화됨

DBSCAN의 특징

• 사전 군집 개수 불필요
• 다양한 형태와 크기의 클러스터 탐지 가능

주변에 일정 개수 이상의 이웃(minPts)을 가진 점을
핵심점(Core Point)으로 간주하고,
핵심점을 중심으로 반경 ε 이내에 있는 점들은 같은 클러스터로 묶는 방법

• 핵심점 (Core Point)
  ε 반경 안에 최소 MinPts 개 이상의 점이 존재하는 점

• 경계점 (Border Point)
  스스로 핵심점이 되지는 못하지만,
  주변 핵심점의 클러스터에 속할 수 있는 점

• 노이즈점/이상치 (Noise Point/Outlier)
  ε 반경 안에 MinPts 개 이상의 이웃이 존재하지 않고,
  또한 어떤 핵심점의 ε 반경에도 속하지 않는 점

이웃(Neighbors) 찾기

두 점 x와 z 사이의 거리를 dist(x,z)라고 하면,

핵심점(Core Point) 판정

어떤 점 x를 기준으로 이웃 개수를 세어 보았을 때,

이면 x는 핵심점(Core Point)

DBSCAN 전체 알고리즘

[1] 미방문 점 p 선택
    │
    ├─ (핵심점 판단: ε 반경 내 이웃 개수 ≥ MinPts?)
    │       ├─ 예 → [2] 새 클러스터 Ci 생성 → 이웃 집합 N = N(p, ε) 계산
    │       │                 │
    │       │                 └─ [3] N을 하나씩 순회:
    │       │                       • 이미 라벨 있으면 패스
    │       │                       • 없으면 → Ci에 라벨
    │       │                       • n이 핵심점이면 → N ← N ∪ N(n,ε)
    │       │                       → N이 빈 집합이 될 때까지 반복
    │       │                 └─ 클러스터 Ci 완성
    │       └─ 아니오 → p를 노이즈로 라벨 → 다음 미방문 점으로 이동
    │
[5] 모든 점에 대해 라벨 할당 완료 시 종료

DBSCAN 예시

$ε$= 1.75, $minPts = 4$ 기준

DBSCAN의 주요 장단점

Pros (장점)

클러스터 개수 미리 지정 불필요

• K-Means처럼 몇 개의 군집을 만들 것인지 미리 정할 필요가 없음

비정형(Arbitrary) 형태의 군집 처리 가능

• 구형(spherical)일 필요 없이, 다양한 형태의 클러스터 생성

노이즈·이상치(Outlier)에 강건함(Robustness)

• 이상치가 클러스터 포함되어 중심을 왜곡하는 일이 줄어듦

Cons (단점)

파라미터 민감성 (ε, MinPts 선택 어려움)

• 데이터 특성에 맞게 적절한 ε, MinPts 값을 찾기 어려움, 검증 필요

밀도 편차가 큰 데이터셋에서 성능 저하

확장성(Scalability) 이슈

• dense region(밀집 영역)의 모든 점 쌍(pair) 간 거리 계산이 필요, 메모리·시간 소모가 매우 커질 수 있음

GMM (Gaussian Mixture Model)

K-Means의 한계

• Hard Clustering(단일 할당)
  K-Means는 각 데이터 포인트를 오직 하나의 군집(cluster) 에만 할당

• 불확실성(Uncertainty) 표현 불가
  K-Means는 점이 이 군집에 속한다를 결정적으로(binary) 나타냄.
  점이 특정 군집에 속할 확률 등의 확률적 정보는 제공하지 않음

GMM을 통한 Soft Clustering

Soft Clustering(연속 할당)

• GMM은 데이터마다 여러 군집에 걸친 확률적 소속도를 알 수 있음
  : 각 데이터 포인트가 각 가우시안 분포(클러스터)에 속할
  확률적 정도를 계산해 줌

GMM 정의

여러 개의 가우시안 분포(정규분포)를 서로 가중합(mixture)한 확률 밀도 함수.
K개의 서로 다른 정규분포를 섞어서 모델링

• 평균(Mean, $μ_k$)
  각 성분 k가 대표하는 클러스터의 중심 위치

• 공분산(Covariance, $Σ_k$)
  클러스터가 얼마나 퍼져 있는지를 나타냄

• 혼합 계수(Mixing Coefficient, $π_k$)
  가우시안 성분 $k$가 전체에서 차지하는 가중치

  $\sum_{k=1}^{K} \pi_{k} = 1,\quad 0 \le \pi_{k} \le 1$

  : 다 합치면 1

전체 데이터의 확률 밀도 함수 $p(\mathbf{x})$

${N}\bigl(\mathbf{x}\mid \mu_{k}, \Sigma_{k}\bigr)$ : 평균 $μ_k$, 공분산 $Σ_k$ 를 가지는 가우시안 정규분포

$D$ : 특성 공간의 차원(변수 개수)

ex. 1차원(D=1)일 경우,

responsibility $γ(zₙₖ)$

관측된 데이터 포인트 $x_n$ 가 가우시안 성분 $k$ 에서 생성되었을 확률

$γ(zₙₖ)$ 계산 by. 베이즈 정리(Bayes’ Theorem)

• 사전확률(prior)
  $p(z_k=1)$은 클러스터 비중

  $p(z_k = 1) = \pi_k$

• 우도(likelihood)
  성분 k의 가우시안 분포”에서 $x_n$이 관측될 확률

  $p(x_n \mid z_k = 1) = \mathcal{N}(x_n \mid \mu_k, \Sigma_k)$

• 정규화 상수(normalizer)
  모든 성분(1부터 K)에 걸친 기여도를 합산하여 계산

  $p(x_n) = \sum_{j=1}^{K} p(z_j = 1)\,p(x_n \mid z_j = 1) = \sum_{j=1}^{K} \pi_{j}\,\mathcal{N}\bigl(x_n \mid \mu_{j}, \Sigma_{j}\bigr)$

• $γ(zₙₖ)$ 계산식

  $\gamma(z_{nk}) = p(z_k = 1 \mid x_n) = \frac{p(z_k = 1)\,p(x_n \mid z_k = 1)} {\sum_{j=1}^{K} p(z_j = 1)\,p(x_n \mid z_j = 1)} = \frac{\pi_k\,\mathcal{N}\bigl(x_n \mid \mu_k, \Sigma_k\bigr)} {\sum_{j=1}^{K} \pi_j\,\mathcal{N}\bigl(x_n \mid \mu_j, \Sigma_j\bigr)}$

MLE (Maximum Likelihood Estimation)

GMM(혼합 가우시안 모델)의 파라미터 추정을 위해 사용
: 데이터를 가장 잘 설명하는 파라미터 $\hat{\theta}$
$L(X;θ)$를 최대화(maximize)

log‐likelihood로 변환

$μ_k$에 대한 MLE(최대우도추정)

$L(X;θ)$를 $μ_k$에 대한 편미분 → 최적화 조건

을 만족하는 mean

$Σ_k$ 대한 MLE(최대우도추정)

$L(X;θ)$를 $Σ_k$에 대한 편미분 → 최적화 조건

을 만족하는 가중 공분산(weighted covariance)

$πₖ$(혼합 비율)에 대한 MLE(최대우도추정)

$πₖ$는 합이 1인 제약조건이 있으므로,
이를 사용하기 위해 라그랑주 승수 $λ$를 도입

라그랑주 함수 $J(X; \theta, \lambda)$를 $πₖ$에 대해 편미분 → 최적화 조건

이므로

GMM에서 EM 알고리즘을 통해 파라미터($\{\mu_k,\,\Sigma_k,\,\pi_k\}$)를 학습하는 과정

• E‐스텝: 각 데이터가 각 성분에 속할 responsibility $γ(zₙₖ)$를 계산

• M‐스텝: 책임도를 가중치로 사용해 $\{\mu_k,\,\Sigma_k,\,\pi_k\}$를 각각 업데이트

• 반복: 로그우도를 최대화할 때까지 E↔M 스텝을 반복 수행

K‐means가 GMM의 특별한 경우가 되는 조건

1. 클러스터가 구형(spherical)이고,
   모든 성분이 같은 분산(등방공분산)을 갖는다고 가정

2. $ϵ→0$ (또는 매우 작은 값)으로 한정
   : soft assignment가 hard assignment(0 또는 1)처럼 변함
   → K‐means의 클러스터 배정 룰(가장 가까운 중심에만 속함)과 동일

GMM(가우시안 혼합 모델)의 주요 장단점

장점 (Pros)

소프트 클러스터링 (Soft Clustering) 제공

• 0 또는 1이 아니라 “어느 정도 비율로 여러 클러스터에 속할 수 있음”을 표현

클러스터 공분산의 유연성 (Flexible Covariance)

• 각 성분마다 공분산 행렬 $Σ_k$를 별도로 추정하므로,
  구형(spherical)·타원형(elliptical)·회전된 형태(rotated) 등
  다양한 형태의 클러스터를 모델링 가능

단점 (Cons)

초기값(Initialization)에 민감

• EM 알고리즘 수행 시, 초기 $\{\mu_k,\,\Sigma_k,\,\pi_k\}$가 큰 영향을 줌

가우시안 분포 가정의 한계

• "데이터가 실제로 가우시안 분포들의 혼합 형태로 생성되었다”는
  전제가 잘 맞지 않을 수 있음

계산 복잡도 (Computational Complexity)

• 데이터 차원(D)이나 군집 수(K)가 커질수록 EM의 각 반복마다 연산량 증가

Cluster Quality Measures

클러스터 품질 평가 지표

외부 기준(External Criterion)

클러스터링 결과가 이미 알고 있는 정답 레이블(ground truth)과
얼마나 일치하는지를 평가

→ 표준 데이터셋에 미리 주어진 클래스 정보가 있을 때,
이를 기준으로 클러스터링 품질을 측정

내부 기준(Internal Criterion)

오로지 클러스터링 결과(할당된 군집들)와
데이터 내부 분포/유사도 척도만을 이용해 클러스터링 품질을 판단

→ 레이블 없이, 클러스터 내부 응집도(cohesion)와
클러스터 간 분리도(separation) 중심으로 평가

Other Issues

클러스터링 시 기타 고려사항

속성의 단위(Unit of Attributes)

서로 다른 단위를 가지는 속성들을 그대로 사용하면,
단위가 큰 속성이 전체 거리에 과도하게 영향.

• 표준화(Standardization) 또는 정규화(Normalization) 적용
• 단위 통일(단위 변환)

속성의 중요도(Importance of Attributes)

실제 문제에서는 어떤 속성은 다른 속성보다 더 중요한 정보인 경우가 많음.

• 특성 가중치(Feature Weighting) 적용
• 특성 선택(Feature Selection)
• 차원 축소 기법