OPTICS

통계 수치해석 소프트웨어 마지막 수정: 2026-09-05 04:52:19

1. 개요[편집]

OPTICS Ordering Points To Identify the Clustering Structure
제안	Ankerst · Breunig · Kriegel · Sander (1999, SIGMOD)
출력	군집 라벨이 아니라 점의 순서 + 도달거리 배열
모수	MinPts (실질) · ε (성능 상한일 뿐)
핵심 자료구조	우선순위 큐
비용	범위질의 n번 — 색인이 먹히면 O(n log n), 아니면 O(n²)
메모리	O(n)
읽는 법	도달거리 플롯의 골짜기 = 군집

$\varepsilon$ 하나로는 안 되는 데이터가 있다. 그러면 $\varepsilon$ 을 전부 다 써 보고, 그 결과를 그림 한 장으로 늘어놓으면 되지 않나?

OPTICS(Ordering Points To Identify the Clustering Structure)는 평평한 군집 라벨을 내놓는 대신, 점들을 밀도가 높은 곳부터 이어지도록 하나의 선형 순서로 배열하고 각 점이 그 순서에 편입될 때의 「도달거리」를 기록하는 밀도 기반 군집화 알고리즘이다. 출력은 라벨이 아니라 길이 $n$ 짜리 순서와 길이 $n$ 짜리 실수 배열 하나이고, 그것을 막대그래프로 그린 도달거리 플롯(reachability plot)이 이 알고리즘의 얼굴이다.

동기는 DBSCAN이 남긴 구조적 한계 하나다 — $\varepsilon$ 이 전역 상수라서 조밀한 군집과 성긴 군집이 공존하면 어떤 값을 골라도 한쪽이 깨진다. 같은 연구 그룹이 3년 뒤 내놓은 답이 ” $\varepsilon$ 을 고르지 말고, 모든 $\varepsilon$ 에 대한 결과를 한 번에 계산해 두자”였다. 그래서 OPTICS는 정확히 말하면 군집화 알고리즘이라기보다 군집 구조의 시각화·요약 절차에 가깝고, 원논문 제목에 clustering이 아니라 clustering structure가 들어간 것도 그 때문이다.¹

이 문서는 순서화의 정의와 플롯을 읽는 법을 다룬다. 밀도·핵심점·잡음의 기본 정의는 DBSCAN에, 같은 문제를 계층과 자동 선택으로 푼 쪽은 HDBSCAN에 있으니 반복하지 않는다.

2. 두 개의 거리[편집]

OPTICS가 새로 정의하는 양은 두 개뿐이다.

핵심거리(core distance). 점 $p$ 가 핵심점일 때, 즉 $\lvert N_\varepsilon(p)\rvert\ge\mathrm{MinPts}$ 일 때

\mathrm{cd}(p) = \big\lVert p - \mathrm{NN}_{\mathrm{MinPts}}(p)\big\rVert

로, $\mathrm{MinPts}$ 번째 최근접 이웃까지의 거리다. 핵심점이 아니면 정의되지 않는다. 이것은 $p$ 를 핵심점으로 만드는 최소 반경이며, 뒤집어 읽으면 국소 밀도의 역수 눈금이다. 커널 밀도 추정의 $k$ -최근접 이웃 판본과 같은 양이라는 점도 짚어 둘 만하다.

도달거리(reachability distance). 핵심점 $p$ 와 그 $\varepsilon$ -이웃 안의 점 $o$ 에 대해

\mathrm{rd}(o \mid p) = \max\big(\mathrm{cd}(p),\ d(p,o)\big)

이고, $p$ 가 핵심점이 아니거나 $o$ 가 $\varepsilon$ 밖이면 정의되지 않는다( $\infty$ 로 둔다). ” $p$ 에서 출발해 $o$ 에 닿으려면 반경을 얼마까지 키워야 하는가”를 재는 값이고, $\max$ 안의 핵심거리 항이 바닥을 깔아 아무리 가까운 이웃이라도 그 이하로는 못 내려가게 한다. 이 바닥이 성긴 지역과 조밀한 지역을 구분하는 장치 전부다.

여기서 놓치면 안 되는 것이 비대칭성이다. $\mathrm{rd}(o\mid p)$ 는 $p$ 의 핵심거리만 보고 $o$ 의 것은 안 본다. 표기에 세로선을 쓴 이유가 그것이고, 이 한 가지가 뒤에서 HDBSCAN과의 차이를 만든다.

3. 순서화 — 사실은 프림 알고리즘[편집]

알고리즘 자체는 짧다.

미처리 점 $p$ 를 하나 꺼내 출력 순서에 추가하고, 그 도달거리는 정의되지 않음( $\infty$ )으로 기록한다.
$p$ 가 핵심점이면 $N_\varepsilon(p)$ 의 미처리 이웃 $o$ 들을 우선순위 큐에 $\mathrm{rd}(o\mid p)$ 를 키로 넣는다. 이미 큐에 있으면 더 작은 값으로만 갱신한다.
큐에서 키가 가장 작은 점을 꺼내 출력 순서에 추가하고, 그 키를 그 점의 도달거리로 기록한다. 그 점이 핵심점이면 2번을 반복한다.
큐가 비면 남은 미처리 점 중 아무거나 집어 1번으로 돌아간다.

이 구조를 보면 정체가 드러난다. “이미 확장한 집합에서 밖으로 나가는 가장 싼 간선을 매번 고른다” — 최소 신장 트리를 만드는 프림 알고리즘 그 자체다. 간선 가중치가 도달거리이고, 큐가 비어 새로 시작하는 것은 그래프가 반경 $\varepsilon$ 에서 끊겨 있어 신장 숲이 되는 경우다. 다만 가중치 $\mathrm{rd}(o\mid p)$ 가 어느 쪽에서 출발했느냐에 따라 달라지므로, 엄밀히는 대칭 그래프 위의 MST가 아니라 방향이 붙은 판본이다.² 이 미묘한 차이가 다음 절들의 배경이다.

$\varepsilon$ 의 지위가 DBSCAN과 완전히 다르다는 것이 이 알고리즘의 핵심 설계다. 여기서 $\varepsilon$ 은 군집을 정의하지 않고, “이보다 먼 것은 어차피 안 볼 테니 질의 범위를 잘라라”는 성능 상한일 뿐이다. $\varepsilon=\infty$ 로 두면 정보 손실이 전혀 없고 대신 비용이 $O(n^2)$ 이 된다. 실제로 대표 라이브러리 구현이 $\varepsilon$ 의 기본값을 무한대로 두고 있으며, 이 값을 줄이는 것은 정확도와 속도를 맞바꾸는 손잡이로만 쓴다.³ 결과적으로 사용자가 실제로 정해야 하는 모수는 $\mathrm{MinPts}$ 하나뿐이다.

4. 비용[편집]

각 점에 대해 범위질의를 정확히 한 번씩 하므로 비용 구조가 DBSCAN과 동일하다. 공간 색인(KD-트리, R-트리)이 질의를 $O(\log n)$ 에 처리하면 전체가 $O(n\log n)$ , 색인이 안 먹히거나 $\varepsilon$ 이 커서 이웃이 $O(n)$ 개면 $O(n^2)$ 이다. 여기에 우선순위 큐 갱신 비용 $O(n\log n)$ 이 더 붙지만 지배항은 아니다.

DBSCAN 문서가 지적한 함정이 그대로 온다. $O(n\log n)$ 은 조건부로만 참이고, 차원이 10을 넘어가면 색인 가지치기가 무너져 사실상 전수 탐색이 된다. 거기에 OPTICS 특유의 비용이 하나 더 붙는데, $\varepsilon$ 을 관대하게(또는 무한대로) 두는 것이 정상 사용법이라 DBSCAN보다 실측 비용이 대체로 크다. 경험적으로 같은 데이터에서 1.5~3배를 잡는데, 그 대가로 얻는 것이 ” $\varepsilon$ 을 다시 안 골라도 된다”는 것이다.

메모리는 $O(n)$ 이다. 거리 행렬을 만들지 않고 순서 배열과 도달거리 배열만 들고 있으면 되므로, 이 점에서는 DBSCAN과 같은 급이다.

5. 도달거리 플롯 읽는 법[편집]

가로축이 출력 순서, 세로축이 도달거리인 막대그래프가 결과물이다. 읽는 규칙은 몇 개 안 된다.

골짜기 하나가 군집 하나다. 순서화가 조밀한 영역을 연달아 훑는 동안 도달거리가 낮게 유지되고, 다른 영역으로 건너뛰는 순간 한 번 치솟는다. 그 치솟는 봉우리가 군집의 경계다.
골짜기의 깊이 = 밀도, 폭 = 크기. 깊고 좁은 골짜기는 작고 조밀한 덩어리, 얕고 넓은 골짜기는 크고 성긴 덩어리다. 밀도가 다른 군집이 한 그림에 동시에 보인다는 것이 DBSCAN 대비 결정적 이득이다.
골짜기 안의 골짜기가 하위 군집이다. 계층 구조가 중첩된 골짜기로 나타난다. 이 때문에 도달거리 플롯은 덴드로그램과 정보량이 사실상 같으며, 실제로 두 표현이 서로 변환 가능한 동치 표현이라는 것이 잔더 외(2003)의 결과다.
높은 곳에 흩어진 막대가 잡음이다. 어느 골짜기에도 안 들어가고 봉우리 높이에 머무는 점들.
첫 점의 도달거리는 항상 정의되지 않는다. 그리고 큐가 비어 새로 시작할 때마다 $\infty$ 막대가 하나씩 생긴다. 이 막대는 “여기서 $\varepsilon$ -연결이 완전히 끊겼다”는 신호다.
가로축의 위치 자체에는 의미가 없다. 순서는 유일하지 않고(같은 키의 타이가 흔하다) 구현·입력 정렬에 따라 달라진다. 읽어야 하는 것은 골짜기의 모양이지 좌표가 아니다.

플롯 전체가 평평하면 밀도가 균일하다는 뜻이라 밀도 기반 군집화 자체가 답이 아니고, 전체가 뾰족뾰족하면 $\mathrm{MinPts}$ 가 너무 작아 잡음에 반응하고 있다는 뜻이다. 그림 자체가 진단 도구라는 것이 이 알고리즘이 30년 가까이 살아남은 이유다.⁴

6. 수평으로 자르면 DBSCAN[편집]

플롯을 높이 $\varepsilon'\le\varepsilon$ 에서 수평으로 자르고, 그 선 아래에 잠긴 연속 구간을 하나의 군집으로 읽는다. 그러면 $\varepsilon'$ 로 DBSCAN을 돌린 결과가 (거의) 그대로 나온다. OPTICS 한 번을 계산해 두면 $\varepsilon$ 스윕이 배열 훑기 한 번으로 끝난다는 뜻이고, 원논문의 판매 문구가 정확히 이것이었다.

“거의”에 붙는 단서를 정확히 알아 둘 필요가 있다. 도달거리는 핵심점으로부터의 값만 기록하므로, 이 절단이 정확히 재현하는 것은 핵심점들의 밀도-연결 구조다. 두 군집의 핵심점 이웃에 동시에 걸친 경계점의 배정은 원래 DBSCAN과 다를 수 있다. DBSCAN에서도 이 배정은 처리 순서에 의존하는 유일한 비결정성이었으므로, 차이는 “재현되지 않는 부분이 다르게 재현되지 않는다”는 정도다. 라이브러리 문서가 “DBSCAN과 결과가 미세하게 다를 수 있다”고 적어 두는 이유가 이것이고, 라벨을 직접 비교할 때는 순열 불변 척도를 쓰는 편이 안전하다.

7. xi 방법 — 골짜기를 자동으로 찾기[편집]

수평 절단은 여전히 값 하나를 요구하고, 그러면 밀도가 다른 군집을 동시에 잡는다는 목적이 무너진다. 원논문이 함께 제시한 자동 추출이 $\xi$ 방법이다.

발상은 절단선이 아니라 기울기를 본다는 것이다. $\xi\in(0,1)$ 을 하나 고르고, 이웃한 두 도달거리의 비가 $1-\xi$ 를 넘게 떨어지는 점을 “가파른 하강점”, 반대로 그만큼 치솟는 점을 “가파른 상승점”이라 부른다. 이 점들이 연달아 나오는 구간이 가파른 하강 영역·상승 영역이고, 하강 영역으로 시작해 상승 영역으로 끝나는 구간을 군집 후보로 잡는다. 후보 중 최소 크기를 넘고 양 끝의 높이가 서로 맞는 것만 채택하면, 중첩을 허용하는 계층적 군집 집합이 나온다.

$\xi$ 는 “골짜기라고 부를 만큼 가파른 게 얼마나 가파른 것인가”를 정하는 값이다. 작게 두면 완만한 굴곡까지 군집으로 잡아 결과가 잘게 부서지고, 크게 두면 뚜렷한 골짜기만 남는다. 실무 기본값은 0.05 근처이며, 여기에 최소 군집 크기가 함께 들어간다.

정직하게 말하면 $\xi$ 방법은 $\varepsilon$ 문제를 완전히 없애지 못한다. 손잡이가 물리적 스케일에서 무차원 기울기로 바뀌었을 뿐이고, 여전히 사람이 값을 정해야 하며 결과가 그 값에 꽤 민감하다. 이 지점이 HDBSCAN의 안정성 기반 자동 선택이 시장을 가져간 이유다 — 그쪽은 선택 기준을 명시적 목적함수로 세워 두고 트리 위 동적계획법으로 푼다.

8. HDBSCAN 과 무엇이 다른가[편집]

둘 다 “모든 밀도 문턱에 대한 DBSCAN”을 계산한다. 차이는 세 군데에 몰려 있다.

	OPTICS	HDBSCAN
거리 정의	한쪽 핵심거리만: $\max(\mathrm{cd}(p),\,d)$	양쪽 대칭: $\max(\mathrm{cd}(a),\,\mathrm{cd}(b),\,d)$
산출 구조	선형 순서 + 도달거리 배열	MST → 응축 트리
평평한 군집	사람이 자르거나 $\xi$	안정성 목적함수로 자동
추가 모수	MinPts (+ 추출 시 $\xi$ )	min_cluster_size (+ min_samples)
부산물	OPTICS-OF 이상 점수	소속 확률 · GLOSH
사람이 보는 그림	도달거리 플롯	응축 트리

첫 줄이 계보상 가장 중요하다. OPTICS의 도달거리는 출발점의 핵심거리만 쓰므로 방향에 따라 값이 달라지고, HDBSCAN의 상호 도달거리는 양쪽의 최대를 취해 대칭이다. 대칭화한 덕분에 HDBSCAN 쪽은 정직한 거리(자기 거리 0만 빼고 삼각부등식까지 만족)가 되어 MST와 계층 이론을 그대로 얹을 수 있었다. OPTICS의 순서화는 그 계층을 1차원으로 눌러 놓은 그림자에 가깝고, 그래서 정보를 잃지는 않지만 알고리즘이 자동으로 다루기는 불편하다.

그래도 OPTICS가 안 죽는 자리가 있다. 도달거리 플롯은 데이터 전체의 밀도 구조를 한 장에 보여 주는 거의 유일한 그림이고, “이 데이터에 군집이 있기는 한가”라는 질문에 응축 트리보다 직관적으로 답한다. 탐색적 분석의 첫 그림으로 OPTICS를 그리고 생산 파이프라인은 HDBSCAN으로 짜는 조합이 실무에서 꽤 합리적이다.

9. 변형과 부산물[편집]

OPTICS-OF. 같은 저자 그룹이 같은 해에 낸 국소 이상치 점수로, 점의 도달거리를 이웃들의 도달거리와 비교해 상대적 이상도를 잰다. 이듬해 나온 국소 이상치 인자(LOF)의 직계 선행 연구이며, “이상치는 절대적 밀도가 아니라 주변 대비 밀도로 판정해야 한다”는 이 계열 전체의 발상이 여기서 정리됐다. 이상치 탐지 문서가 다루는 그 계보다.
DeLi-Clu(2006). $\varepsilon$ 을 완전히 없애고 R-트리의 최근접 쌍 순위화로 순서를 만든다. 단일연결 계층 군집화와 OPTICS를 합친 형태이며, 성능 상한으로서의 $\varepsilon$ 조차 사라진다.
HiSC · HiCO · DiSH. 같은 그룹이 부분공간·상관 군집화로 확장한 계열. 거리 정의만 바꾸면 순서화 골격이 그대로 재사용된다는 것을 보여 준다.
구현. 저자 그룹의 ELKI가 사실상 참조 구현이고, 대표 파이썬 라이브러리도 2019년부터 표준 제공한다. 후자는 추출 방식으로 $\xi$ 와 DBSCAN식 절단을 모두 노출하며, 앞서 말한 대로 $\varepsilon$ 기본값이 무한대다.

10. 실무에서 확인할 것[편집]

표준화했는가. 밀도 기반 방법 전체의 1번 항목이다. 안 했으면 핵심거리가 단위 큰 축의 함수일 뿐이다.
$\mathrm{MinPts}$ 를 먼저 정한다. DBSCAN과 같은 관례( $d+1$ 이상, 잡음이 많으면 $2d$ 근처)를 쓰면 된다. 키우면 플롯이 매끄러워지고 잡음에 둔감해진다. $\varepsilon$ 은 건드리지 말고 무한대로 두는 것이 기본값이다.
플롯부터 그린다. 라벨 벡터만 받아 쓸 거면 애초에 OPTICS를 쓸 이유가 없다. 골짜기가 안 보이면 그 데이터에 밀도 기반 구조가 없다는 정보이고, 그건 실패가 아니라 결과다.
$\xi$ 를 흔들어 본다. 0.01·0.05·0.1 세 값에서 군집 개수가 3에서 40으로 튄다면 그 결과를 보고서에 넣기 전에 다시 생각하는 게 좋다.
차원이 몇인가. 15차원을 넘으면 거리 집중 때문에 핵심거리 자체의 의미가 흐려지고, 색인도 무너져 $O(n^2)$ 이 된다. 차원의 저주를 먼저 처리하는 것이 순서다.
$n$ 이 얼마인가. 도달거리 플롯은 화면 폭이 유한하므로 $n$ 이 수십만이면 막대 하나가 화소 하나보다 얇아져 눈으로 읽는 이득이 사라진다. 이 규모에서는 표본을 뽑아 플롯을 보고, 전체에는 HDBSCAN을 거는 편이 낫다.

11. 관련 문서[편집]

이 연구 그룹의 작명 전통은 일관되게 억지스럽다. DBSCAN, OPTICS, DeLi-Clu, HiSC, DiSH — 전부 두문자를 먼저 정해 놓고 뜻을 끼워 맞춘 티가 난다. 그중에서도 OPTICS는 광학과 아무 관계가 없는데 검색하면 렌즈 회사가 먼저 나온다는 점에서 특히 비용이 컸다. ↩
“새 알고리즘인 줄 알았는데 프림이었다”는 이 바닥의 흔한 결말이다. OPTICS 논문 자체는 MST를 언급하지 않고 밀도 도달가능성의 언어로만 서술했고, 두 절차가 같다는 것은 나중에 정리됐다. HDBSCAN이 명시적으로 MST를 쓰는 것은 이 관찰을 이론의 출발점으로 삼았기 때문이다. 같은 알고리즘을 두 번 발명하는 것보다 나쁜 것은, 두 번 발명하고도 같은 것인 줄 모르는 것이다. ↩
$\varepsilon$ 을 무한대로 두라는 조언에는 함정이 하나 있다. 범위질의가 매번 전체 점을 반환하므로 색인이 무의미해지고 비용이 확정적으로 $O(n^2)$ 이 된다. $n$ 이 수만을 넘으면 “정확도 손실 없음”의 대가가 몇 시간이 될 수 있어서, 실전에서는 $k$ -거리 그래프로 넉넉한 상한을 잡아 넣는 타협을 한다. 결국 $\varepsilon$ 을 완전히 잊지는 못한다는 뜻이고, 그 잔재를 없앤 것이 DeLi-Clu다. ↩
도달거리 플롯을 사람이 눈으로 자른다는 것이 1999년에는 기능이었다. 데이터 마이닝이 “전문가가 도구를 들고 데이터를 탐색하는 일”이던 시절의 설계 철학이고, 논문에도 대화형 탐색이 장점으로 적혀 있다. 자동화 파이프라인에 사람이 그림을 보는 단계를 끼워 넣을 수 없게 된 지금은 같은 특징이 그대로 단점으로 읽힌다. 알고리즘은 변하지 않았는데 평가가 뒤집힌 사례. ↩