PatchCore의 k-center problem 이해하기 (260816)

PatchCore의 k-center problem 이해하기

1. 문제를 직관적으로 이해하기

대학교 캠퍼스에 편의점을 몇 개 배치한다고 상상해봅시다. 학생 수는 매우 많은데(=전체 패치 특징들), 편의점은 예산 문제로 딱 $k$개만 지을 수 있습니다(=coreset 크기).

목표: 캠퍼스 어디에 있는 학생이든, "가장 가까운 편의점까지의 거리"가 너무 멀지 않도록 편의점 위치를 정하고 싶습니다. 더 정확히는, "가장 불운한 학생"(편의점에서 제일 멀리 떨어진 학생) 이 걸어야 하는 거리를 최소화하고 싶은 겁니다.

이게 바로 k-center problem입니다. PatchCore에서는:

• "학생" = 정상 학습 데이터에서 뽑은 패치 특징 벡터 (전체 집합 $\mathcal{M}$)
• "편의점" = memory bank에 저장할 대표 벡터들 (부분집합 $\mathcal{M}_C \subset \mathcal{M}$)
• "거리가 멀다" = 해당 정상 패턴이 memory bank로 잘 대표되지 못한다 → 테스트 시 정상인데도 이상하다고 오판할 위험이 커진다

2. 수식으로 표현하면 (Minimax Facility Location)

$\mathcal{M}_C = \arg\min_{\mathcal{M}_C \subset \mathcal{M}} \; \max_{m \in \mathcal{M}} \; \min_{c \in \mathcal{M}_C} \; \| m - c \|_2$

바깥에서부터 읽어봅시다:
1. 가장 안쪽 $\min_{c \in \mathcal{M}_C} \|m - c\|_2$ : 어떤 점 $m$에서, 뽑아놓은 대표점들($\mathcal{M}_C$) 중 가장 가까운 것까지의 거리
2. 가운데 $\max_{m \in \mathcal{M}}$ : 전체 데이터 중에서 그 거리가 가장 큰 점(=가장 소외된 점)을 찾음
3. 가장 바깥 $\min_{\mathcal{M}_C}$ : 이 "가장 소외된 점까지의 거리"가 최소가 되도록 대표점 집합 $\mathcal{M}_C$를 고름

즉 "최악의 경우(가장 못 커버된 점)를 가장 낫게 만드는" 대표점들을 고르는 문제입니다. 이 문제는 조합적으로 가능한 부분집합이 너무 많아서 NP-hard이고, 정확히 풀 수 없습니다.

3. Greedy 근사 알고리즘

정확히 못 푸니, PatchCore는 다음과 같은 탐욕적(greedy) 근사를 사용합니다 (Sener & Savarese, 2018의 k-Center-Greedy를 그대로 채용):

Algorithm: Greedy k-Center

1. 대표점 집합 C = {} (비어있음)
2. 임의의 점 하나를 뽑아 C에 추가
3. target 개수에 도달할 때까지 반복:
     a. 아직 안 뽑힌 각 점 m에 대해, C 안의 가장 가까운 점까지의 거리 d(m, C)를 계산
     b. d(m, C)가 가장 큰 점 u를 찾음  (=현재 대표점들로부터 가장 멀리 떨어진 점)
     c. u를 C에 추가
4. C를 반환

핵심 아이디어: "지금 대표점들이 가장 못 커버하고 있는 빈틈"을 매번 채워나간다는 것입니다. 그래서 결과적으로 데이터가 밀집된 곳뿐 아니라 희소한 곳까지 골고루 커버하게 됩니다.

4. 코드로 직접 확인해보기

프로젝트 코드의 _greedy_sample과 같은 로직을, 이해하기 쉽게 최소한의 numpy만으로 다시 짜서 직접 동작을 확인해보겠습니다.한글 폰트가 없어 그래프의 한글이 깨질 수 있으니, 라벨을 영어로 바꿔서 다시 생성하겠습니다.결과 그림을 보면 차이가 바로 눈에 들어옵니다:

• 왼쪽(Random): 밀집된 영역(왼쪽 아래) 안에서도 점들이 서로 가까이 뭉쳐서 뽑힌 게 보입니다. 좁은 곳에 여러 개를 낭비하고 있는 것 — 이미 뽑은 점과 비슷한 정보를 담은 점을 또 뽑는 셈입니다.
• 오른쪽(Greedy): 밀집 영역의 가장자리(edge)까지 골고루 퍼져서 뽑혔고, 두 덩어리(클러스터) 사이의 빈 공간도 감안해서 배치됩니다. 같은 개수(20개)로 훨씬 넓은 영역을 "커버"하고 있습니다.

이게 바로 PatchCore가 원하는 것입니다: 20개(=k)로 뽑되, 어떤 정상 패치가 나오더라도 memory bank 안에 "충분히 가까운" 대표점이 있도록 만드는 것.

5. 우리 프로젝트 코드와의 대응관계

알고리즘의 핵심 로직(min_dist 갱신하며 매번 argmax 뽑기)은 완전히 동일하고, 실제 구현은 고차원·대용량 데이터를 다루기 위해 (1) random projection, (2) torch 텐서 연산이라는 두 가지 공학적 장치를 추가한 것뿐입니다.### 6. 정리

"""
Greedy k-Center Coreset Selection - 교육용 최소 예제

PatchCore(Roth et al., CVPR 2022) 논문에서 memory bank를 줄일 때 쓰는
minimax facility location 문제의 greedy 근사 알고리즘을,
외부 의존성(torch, faiss) 없이 순수 numpy로 재구현한 버전입니다.

실제 프로젝트의 patchcore.py::CoresetSampler._greedy_sample() 과
로직은 동일하고, 이해를 돕기 위해 2D 데이터 + 시각화만 추가했습니다.
"""

import numpy as np
import matplotlib.pyplot as plt


def greedy_k_center(points, k, seed=0):
    """
    points: [N, D] 전체 데이터
    k: 뽑고 싶은 대표점(coreset) 개수

    반환: 선택된 점들의 인덱스 리스트 (선택된 "순서" 그대로)
    """

    rng = np.random.default_rng(seed)
    n = len(points)

    # 1) 첫 대표점은 무작위로 하나 선택
    selected = [int(rng.integers(0, n))]

    # min_dist[i] = 점 i 에서, 현재까지 선택된 대표점들 중 "가장 가까운" 점까지의 거리
    min_dist = np.linalg.norm(points - points[selected[0]], axis=1)
    min_dist[selected[0]] = -1  # 이미 뽑힌 점은 다시 안 뽑히도록 표시

    # 2) target 개수에 도달할 때까지 반복
    for _ in range(1, k):
        # "현재 대표점들로부터 가장 멀리 떨어진 점"을 다음 대표점으로
        next_idx = int(np.argmax(min_dist))
        selected.append(next_idx)

        # 새로 뽑힌 점을 기준으로 거리 갱신 (더 가까워졌으면 갱신, 아니면 유지)
        new_dist = np.linalg.norm(points - points[next_idx], axis=1)
        min_dist = np.minimum(min_dist, new_dist)
        min_dist[next_idx] = -1

    return selected


if __name__ == "__main__":

    rng = np.random.default_rng(42)

    # ------------------------------------------------------------
    # 일부러 "밀도가 불균형한" 2D 데이터를 만든다
    #   - 큰 덩어리 (dense): 점 400개, 좁은 영역에 밀집
    #   - 작은 덩어리 (sparse): 점 20개, dense와 멀리 떨어진 위치
    # 실제 정상 데이터에서 "자주 나오는 패턴 vs 드문 패턴"을 흉내낸 것
    # ------------------------------------------------------------

    dense = rng.normal(loc=[0, 0], scale=0.6, size=(400, 2))
    sparse = rng.normal(loc=[6, 6], scale=0.3, size=(20, 2))
    points = np.concatenate([dense, sparse], axis=0).astype(np.float32)

    k = 20  # 전체 420개 중 20개만 대표점으로 선택 (~4.8%)

    # ------------------------------------------------------------
    # 비교 대상: 그냥 랜덤으로 20개 뽑기
    # ------------------------------------------------------------

    random_idx = rng.choice(len(points), size=k, replace=False)

    # ------------------------------------------------------------
    # Greedy k-center로 20개 뽑기
    # ------------------------------------------------------------

    greedy_idx = greedy_k_center(points, k, seed=1)

    # sparse 영역(점 400번 인덱스 이후)이 각각 몇 개 뽑혔는지 확인
    sparse_start = 400
    n_sparse_random = sum(1 for i in random_idx if i >= sparse_start)
    n_sparse_greedy = sum(1 for i in greedy_idx if i >= sparse_start)

    print(f"전체 sparse 영역 비율: {20/420*100:.1f}%")
    print(f"Random이 뽑은 sparse 점 개수 : {n_sparse_random} / {k}")
    print(f"Greedy가 뽑은 sparse 점 개수 : {n_sparse_greedy} / {k}")

    # ------------------------------------------------------------
    # 시각화
    # ------------------------------------------------------------

    fig, axes = plt.subplots(1, 2, figsize=(11, 5))

    for ax, idx, title in [
        (axes[0], random_idx, f"Random Sampling\n(sparse region: {n_sparse_random} selected)"),
        (axes[1], greedy_idx, f"Greedy k-Center\n(sparse region: {n_sparse_greedy} selected)"),
    ]:
        ax.scatter(points[:, 0], points[:, 1], s=10, color="#cccccc", label="all points")
        ax.scatter(
            points[idx, 0], points[idx, 1],
            s=90, color="#e63946", edgecolor="black", linewidth=0.8,
            label="selected coreset",
        )
        ax.set_title(title)
        ax.set_xlim(-2.5, 7.5)
        ax.set_ylim(-2.5, 7.5)
        ax.set_aspect("equal")
        ax.legend(loc="lower right", fontsize=8)

    plt.tight_layout()
    plt.savefig("/mnt/user-data/outputs/greedy_vs_random.png", dpi=150)
    print("\n그림 저장 완료: greedy_vs_random.png")