OPTICS¶

논문 정보¶

항목	내용
제목	OPTICS: Ordering Points To Identify the Clustering Structure
저자	Mihael Ankerst, Markus M. Breunig, Hans-Peter Kriegel, Jörg Sander
연도	1999
학회	SIGMOD (ACM SIGMOD International Conference on Management of Data)
링크	ACM DL

핵심 아이디어¶

DBSCAN의 문제점: - 단일 ε 값으로 모든 밀도를 처리 - ε를 바꿔가며 여러 번 실행해야 다양한 밀도 탐색 가능

OPTICS의 해결책: - 데이터를 밀도 순서(reachability order)로 정렬 - Reachability Plot으로 시각화 - 다양한 ε 값에 대한 클러스터를 한 번의 실행으로 탐색 - 사용자가 플롯을 보고 적절한 임계값 선택

OPTICS는 클러스터링 결과보다 클러스터 구조의 시각화에 초점을 맞춘다.

알고리즘¶

핵심 개념¶

Core Distance (DBSCAN과 동일) $$\text{core-dist}_{\epsilon, MinPts}(p) = \begin{cases} \text{UNDEFINED} & \text{if } |N_\epsilon(p)| < MinPts \\ d(p, N_{MinPts}(p)) & \text{otherwise} \end{cases}$$

Reachability Distance $$\text{reach-dist}_{\epsilon, MinPts}(p, o) = \begin{cases} \text{UNDEFINED} & \text{if } |N_\epsilon(o)| < MinPts \\ \max(\text{core-dist}(o), d(o, p)) & \text{otherwise} \end{cases}$$

o에서 p로의 "도달 거리"
o가 core point가 아니면 정의되지 않음
core point 내부에서는 core distance로 하한이 설정됨

알고리즘 절차¶

입력: 데이터 D, ε (최대 반경), MinPts
출력: 순서화된 점 목록, 각 점의 reachability distance

1. 모든 점의 reachability distance를 UNDEFINED로 초기화
2. 모든 점을 UNPROCESSED로 표시

3. 각 점 p ∈ D에 대해:
   if p가 PROCESSED면 건너뜀

   a. N_ε(p) 계산
   b. p를 PROCESSED로 표시
   c. 출력 순서에 p 추가
   d. if |N_ε(p)| ≥ MinPts (p는 core point):
      - Seeds = 빈 우선순위 큐
      - update(N_ε(p), p, Seeds)
      - while Seeds가 비어있지 않음:
        * q = Seeds에서 최소 reachability distance 점 추출
        * N_ε(q) 계산
        * q를 PROCESSED로 표시
        * 출력 순서에 q 추가 (reachability distance와 함께)
        * if |N_ε(q)| ≥ MinPts:
          - update(N_ε(q), q, Seeds)

update(N, p, Seeds):
  for each o ∈ N:
    if o가 UNPROCESSED:
      new_reach_dist = max(core_dist(p), d(p, o))
      if o의 reachability가 UNDEFINED:
        o.reachability_distance = new_reach_dist
        Seeds에 o 삽입
      else if new_reach_dist < o.reachability_distance:
        o.reachability_distance = new_reach_dist
        Seeds에서 o 업데이트

Reachability Plot¶

X축: 처리 순서
Y축: Reachability distance
Valley(골짜기) = 클러스터
Peak(봉우리) = 클러스터 경계

reach_dist
    |     ___
    |    /   \      ___
    |   /     \    /   \
    |__/       \__/     \__
    |_________________________ order
       Cluster1  Cluster2

시간 복잡도¶

구현	복잡도
기본	O(n²)
공간 인덱스	O(n log n)

장단점¶

장점¶

장점	설명
다중 밀도 탐색	한 번의 실행으로 다양한 밀도
시각화	Reachability plot으로 구조 파악
ε 불필요	최대 ε만 지정 (넉넉하게)
계층 구조	HDBSCAN과 유사한 계층

단점¶

단점	설명
해석 필요	플롯에서 수동으로 임계값 선택
자동화 어려움	DBSCAN처럼 직접 라벨 안 줌
계산 비용	DBSCAN보다 약간 느림

OPTICS vs DBSCAN vs HDBSCAN¶

항목	DBSCAN	OPTICS	HDBSCAN
출력	Hard labels	Ordering + Plot	Hard labels + Soft
밀도 처리	단일	다중 (시각화)	다중 (자동)
파라미터	ε, MinPts	max_ε, MinPts	min_cluster_size
자동화	완전	수동 해석	완전
용도	클러스터링	탐색/시각화	클러스터링

언제 쓰는가¶

적합한 경우¶

데이터의 클러스터 구조를 탐색하고 싶을 때
다양한 밀도 수준의 클러스터 시각화
DBSCAN의 ε 선택이 어려울 때 가이드로 사용
클러스터 계층 구조를 시각적으로 파악

부적합한 경우¶

자동 클러스터링이 필요할 때 → HDBSCAN 사용
대규모 데이터
고차원 데이터

Python 코드¶

import numpy as np
from sklearn.cluster import OPTICS, cluster_optics_dbscan
from sklearn.datasets import make_blobs
import matplotlib.pyplot as plt

# 다양한 밀도의 데이터 생성
np.random.seed(42)
blob1, _ = make_blobs(n_samples=500, centers=[[0, 0]], cluster_std=0.5)
blob2, _ = make_blobs(n_samples=100, centers=[[5, 5]], cluster_std=0.2)
blob3, _ = make_blobs(n_samples=300, centers=[[-5, 5]], cluster_std=1.5)
X = np.vstack([blob1, blob2, blob3])

# OPTICS 적용
optics = OPTICS(
    min_samples=10,
    xi=0.05,            # 클러스터 추출 파라미터
    min_cluster_size=0.05,  # 최소 클러스터 비율
    max_eps=np.inf,     # 최대 eps (기본값: 무한대)
    metric='euclidean',
    cluster_method='xi'  # 'xi' 또는 'dbscan'
)
optics.fit(X)

# 결과
labels = optics.labels_
reachability = optics.reachability_
ordering = optics.ordering_

n_clusters = len(set(labels)) - (1 if -1 in labels else 0)
print(f"클러스터 수: {n_clusters}")

Reachability Plot¶

fig, axes = plt.subplots(2, 1, figsize=(12, 8))

# Reachability Plot
colors = ['g.', 'r.', 'b.', 'y.', 'c.']
for klass, color in zip(range(0, 5), colors):
    Xk = X[optics.labels_ == klass]
    # reachability는 ordering 순서대로 정렬되어 있음

space = np.arange(len(X))
reachability_ordered = reachability[ordering]
labels_ordered = labels[ordering]

# Reachability plot
for klass in range(n_clusters):
    mask = labels_ordered == klass
    axes[0].fill_between(space[mask], reachability_ordered[mask], alpha=0.3)

axes[0].plot(space, reachability_ordered, 'k.', markersize=2)
axes[0].set_ylabel('Reachability Distance')
axes[0].set_xlabel('Ordering')
axes[0].set_title('OPTICS Reachability Plot')

# 클러스터링 결과
scatter = axes[1].scatter(X[:, 0], X[:, 1], c=labels, cmap='viridis', s=10)
axes[1].scatter(X[labels == -1, 0], X[labels == -1, 1], c='red', marker='x', s=30, label='Noise')
axes[1].set_title(f'OPTICS Clustering ({n_clusters} clusters)')
axes[1].legend()
plt.colorbar(scatter, ax=axes[1])

plt.tight_layout()
plt.show()

DBSCAN 스타일로 클러스터 추출¶

# 다양한 eps 값으로 클러스터 추출
eps_values = [0.3, 0.5, 0.7, 1.0]
fig, axes = plt.subplots(2, 2, figsize=(12, 10))

for ax, eps in zip(axes.flatten(), eps_values):
    # OPTICS의 reachability 정보로 DBSCAN 클러스터 추출
    labels_dbscan = cluster_optics_dbscan(
        reachability=optics.reachability_,
        core_distances=optics.core_distances_,
        ordering=optics.ordering_,
        eps=eps
    )

    n_clusters = len(set(labels_dbscan)) - (1 if -1 in labels_dbscan else 0)
    n_noise = list(labels_dbscan).count(-1)

    ax.scatter(X[:, 0], X[:, 1], c=labels_dbscan, cmap='viridis', s=10)
    ax.scatter(X[labels_dbscan == -1, 0], X[labels_dbscan == -1, 1], 
               c='red', marker='x', s=30)
    ax.set_title(f'eps={eps}: {n_clusters} clusters, {n_noise} noise')

plt.tight_layout()
plt.show()

Xi 클러스터 추출¶

# Xi 방법으로 자동 클러스터 추출
xi_values = [0.01, 0.05, 0.1, 0.2]
fig, axes = plt.subplots(2, 2, figsize=(12, 10))

for ax, xi in zip(axes.flatten(), xi_values):
    optics_xi = OPTICS(min_samples=10, xi=xi, min_cluster_size=0.05)
    labels_xi = optics_xi.fit_predict(X)

    n_clusters = len(set(labels_xi)) - (1 if -1 in labels_xi else 0)

    ax.scatter(X[:, 0], X[:, 1], c=labels_xi, cmap='viridis', s=10)
    ax.scatter(X[labels_xi == -1, 0], X[labels_xi == -1, 1], 
               c='red', marker='x', s=30)
    ax.set_title(f'xi={xi}: {n_clusters} clusters')

plt.tight_layout()
plt.show()

Reachability Plot 상세 분석¶

fig, ax = plt.subplots(figsize=(14, 6))

space = np.arange(len(X))
reachability_ordered = reachability[ordering]

# 플롯
ax.bar(space, reachability_ordered, width=1.0, color='steelblue', alpha=0.7)

# 클러스터 경계 표시
for i, (label, reach) in enumerate(zip(labels_ordered[:-1], reachability_ordered[:-1])):
    if labels_ordered[i] != labels_ordered[i+1]:
        ax.axvline(x=i+0.5, color='red', linestyle='--', alpha=0.5)

ax.set_xlabel('Ordering')
ax.set_ylabel('Reachability Distance')
ax.set_title('Detailed Reachability Plot')

# 평균 reachability로 임계값 표시
threshold = np.percentile(reachability_ordered[reachability_ordered < np.inf], 75)
ax.axhline(y=threshold, color='green', linestyle='--', label=f'Threshold (75th percentile): {threshold:.2f}')
ax.legend()

plt.show()

참고 문헌¶

Ankerst, M., Breunig, M. M., Kriegel, H. P., & Sander, J. (1999). OPTICS: Ordering Points To Identify the Clustering Structure. ACM SIGMOD Record, 28(2), 49-60.
Sander, J., Qin, X., Lu, Z., Niu, N., & Kovarsky, A. (2003). Automatic Extraction of Clusters from Hierarchical Clustering Representations. PAKDD 2003.

OPTICS¶

논문 정보¶

핵심 아이디어¶

알고리즘¶

핵심 개념¶

알고리즘 절차¶

Reachability Plot¶

시간 복잡도¶

장단점¶

장점¶

단점¶

OPTICS vs DBSCAN vs HDBSCAN¶

언제 쓰는가¶

적합한 경우¶

부적합한 경우¶

Python 코드¶

Reachability Plot¶

DBSCAN 스타일로 클러스터 추출¶

Xi 클러스터 추출¶

Reachability Plot 상세 분석¶

관련 기법¶

참고 문헌¶