기계 학습과 데이터 마이닝
패러다임 지도 학습 비지도 학습 준지도 학습 자기 지도 학습 강화 학습 메타 학습 온라인 기계 학습 배치 학습 커리큘럼 학습 규칙 기반 기계 학습 신경-기호 AI 뉴로모픽 엔지니어링 양자 기계 학습
문제 분류 생성 모델링 회귀 군집화 차원 축소 밀도 추정 이상 탐지 데이터 정제 AutoML 연관 규칙 의미 분석 구조적 예측 특징 공학 특징 학습 순위 학습 문법 유도 온톨로지 학습 멀티모달 학습
지도 학습 (분류 • 회귀) 도제 학습 결정 트리 앙상블 배깅 부스팅 랜덤 포레스트 k-NN 선형 회귀 나이브 베이즈 인공 신경망 로지스틱 회귀 퍼셉트론 상관 벡터 머신 (RVM) 서포트 벡터 머신 (SVM)
군집화 BIRCH CURE 계층적 k-평균 퍼지 기댓값 최대화 (EM) DBSCAN OPTICS 평균 이동
차원 축소 인자 분석 CCA ICA LDA NMF PCA PGD t-SNE SDL
구조적 예측 그래프 모형 베이즈 네트워크 조건부 무작위장 은닉 마르코프 모형
이상 탐지 RANSAC k-NN 국소 특이점 요인 고립 포레스트
인공 신경망 오토인코더 딥 러닝 순방향 신경망 순환 신경망 LSTM GRU ESN 리저버 컴퓨팅 볼츠만 머신 제한된 GAN 확산 모델 SOM 합성곱 신경망 U-Net LeNet 알렉스넷 딥드림 신경장 신경 방사장 물리정보 신경망 트랜스포머 비전 맘바 스파이킹 신경망 멤트렌지스터 ECRAM
강화 학습 Q 러닝 정책 경사법 SARSA 시간차 학습 (TD) 다중 에이전트 셀프 플레이
인간 참여 학습 액티브 러닝 크라우드소싱 휴먼인더루프 기계적 해석 가능성 RLHF
모델 진단 결정계수 혼동 행렬 러닝 커브 ROC 곡선
수학적 이론 커널 머신 편향-분산 트레이드오프 계산학습이론 경험적 위험 최소화 오캄 학습 PAC 러닝 통계적 학습이론 VC 이론 위상 수학적 딥 러닝
회의/저널 AAAI ECML PKDD NeurIPS ICML ICLR IJCAI ML JMLR
관련 문서 인공지능 용어집 기계 학습 연구를 위한 데이터 세트 목록 컴퓨터 비전 및 이미지 처리 데이터 세트 목록 기계 학습 개요
v t e

OPTICS는 공간 데이터에서 밀도 기반^[1] 군집을 찾기 위한 알고리즘이다. 1999년 미하엘 앙커스트(Mihael Ankerst), 마르쿠스 M. 브로이닉(Markus M. Breunig), 한스-페터 크리겔, 요르크 잔더가 발표하였다.^[2] 기본 개념은 DBSCAN과 유사하지만,^[3] DBSCAN의 주요 약점 중 하나인 데이터의 밀도가 다를 때 의미 있는 군집을 탐지하는 문제를 해결한다. 이를 위해 데이터베이스의 점들을 공간적으로 가장 가까운 점들이 정렬 순서상 인접하도록 (선형적으로) 정렬한다. 추가로, 각 점에는 두 점이 같은 군집에 속하기 위해 받아들여야 하는 밀도를 나타내는 특별한 거리가 저장된다. 이는 덴드로그램으로 표현된다.

DBSCAN과 마찬가지로 OPTICS는 두 개의 매개변수를 필요로 한다. 고려할 최대 거리(반경)를 나타내는 ε과 군집을 형성하는 데 필요한 점의 수를 나타내는 MinPts이다. 점 p의 ε-이웃 ${\displaystyle N_{\varepsilon }(p)}$ 내에 (점 p 자신을 포함하여) 최소 MinPts 개의 점이 발견되면 p를 핵심점(core point)이라고 한다. DBSCAN과 달리 OPTICS는 더 밀도가 높은 군집의 일부인 점들도 고려하므로, 각 점에는 MinPts 번째로 가까운 점까지의 거리를 설명하는 핵심 거리(core distance)가 할당된다.

${\displaystyle {\text{core-dist}}_{\mathit {\varepsilon ,MinPts}}(p)={\begin{cases}{\text{UNDEFINED}}&{\text{if }}|N_{\varepsilon }(p)|<{\mathit {MinPts}}\\{\mathit {MinPts}}{\text{-th smallest distance in }}N_{\varepsilon }(p)&{\text{otherwise}}\end{cases}}}$

점 p로부터 다른 점 o까지의 도달 가능 거리(reachability-distance)는 o와 p 사이의 거리와 p의 핵심 거리 중 더 큰 값이다.

${\displaystyle {\text{reachability-dist}}_{\mathit {\varepsilon ,MinPts}}(o,p)={\begin{cases}{\text{UNDEFINED}}&{\text{if }}|N_{\varepsilon }(p)|<{\mathit {MinPts}}\\\max({\text{core-dist}}_{\mathit {\varepsilon ,MinPts}}(p),{\text{dist}}(p,o))&{\text{otherwise}}\end{cases}}}$

p와 o가 가장 가까운 이웃이라면, 이는 p와 o가 같은 군집에 속하도록 가정해야 하는 ${\displaystyle \varepsilon '<\varepsilon }$를 의미한다.

핵심 거리와 도달 가능 거리는 (ε에 대해) 충분히 밀도가 높은 군집을 사용할 수 없는 경우 정의되지 않는다. 충분히 큰 ε을 주면 이러한 일은 일어나지 않지만, 모든 ε-이웃 질의가 전체 데이터베이스를 반환하게 되어 ${\displaystyle O(n^{2})}$의 시간 복잡도를 초래한다. 따라서 더 이상 흥미롭지 않은 군집의 밀도를 차단하고 알고리즘의 속도를 높이기 위해 ε 매개변수가 필요하다.

엄밀히 말해 ε 매개변수는 반드시 필요한 것은 아니다. 단순히 가능한 최대값으로 설정할 수 있다. 그러나 공간 인덱스를 사용할 수 있는 경우 복잡도 측면에서 실제적인 역할을 한다. OPTICS는 이 매개변수를 제거함으로써, 최소한 최대값만 제공하면 되도록 DBSCAN을 추상화한다.

OPTICS의 기본 접근 방식은 DBSCAN과 유사하지만, 처리되지 않은 군집 멤버들을 집합에 유지하는 대신 우선순위 큐 (예: 인덱싱된 힙 사용)에 유지한다.

function OPTICS(DB, ε, MinPts) is
    for each point p of DB do
        p.reachability-distance = UNDEFINED
    for each unprocessed point p of DB do
        N = getNeighbors(p, ε)
        mark p as processed
        output p to the ordered list
        if core-distance(p, ε, MinPts) != UNDEFINED then
            Seeds = empty priority queue
            update(N, p, Seeds, ε, MinPts)
            for each next q in Seeds do
                N' = getNeighbors(q, ε)
                mark q as processed
                output q to the ordered list
                if core-distance(q, ε, MinPts) != UNDEFINED do
                    update(N', q, Seeds, ε, MinPts)

update() 함수에서는 우선순위 큐 Seeds가 각각 ${\displaystyle p}$와 ${\displaystyle q}$의 ${\displaystyle \varepsilon }$-이웃으로 업데이트된다.

function update(N, p, Seeds, ε, MinPts) is
    coredist = core-distance(p, ε, MinPts)
    for each o in N
        if o is not processed then
            new-reach-dist = max(coredist, dist(p,o))
            if o.reachability-distance == UNDEFINED then // o is not in Seeds
                o.reachability-distance = new-reach-dist
                Seeds.insert(o, new-reach-dist)
            else               // o in Seeds, check for improvement
                if new-reach-dist < o.reachability-distance then
                    o.reachability-distance = new-reach-dist
                    Seeds.move-up(o, new-reach-dist)

따라서 OPTICS는 최소 도달 가능 거리(원래 알고리즘에서는 핵심 거리도 내보내지만, 추후 처리에는 필수가 아님)가 주석으로 달린 특정 순서로 점들을 출력한다.

도달 가능성 플롯(일종의 덴드로그램)을 사용하면 군집의 계층적 구조를 쉽게 얻을 수 있다. 이는 x축에 OPTICS가 처리한 점의 순서를, y축에 도달 가능 거리를 나타내는 2D 플롯이다. 군집에 속한 점들은 가장 가까운 이웃까지의 도달 가능 거리가 낮기 때문에, 군집은 도달 가능성 플롯에서 계곡 형태로 나타난다. 계곡이 깊을수록 군집의 밀도가 높다.

위의 이미지는 이 개념을 설명한다. 왼쪽 상단 영역에는 합성 예제 데이터 세트가 표시되어 있다. 오른쪽 상단은 OPTICS에 의해 생성된 신장 부분 그래프를 시각화하며, 하단은 OPTICS로 계산된 도달 가능성 플롯을 보여준다. 이 플롯의 색상은 레이블이며 알고리즘에 의해 계산된 것은 아니지만, 플롯의 계곡이 위 데이터 세트의 군집과 어떻게 대응되는지 잘 보여준다. 이 이미지에서 노란색 점들은 노이즈로 간주되며, 도달 가능성 플롯에서 계곡을 찾을 수 없다. 이 점들은 일반적으로 계층적 결과 내의 항상 존재하는 "모든 데이터" 군집을 제외하고는 군집에 할당되지 않는다.

이 플롯에서 군집을 추출하는 작업은 시각적 확인 후 x축의 범위를 선택하거나, y축의 임계값을 선택하여 수동으로 수행할 수 있다(결과는 동일한 ${\displaystyle \varepsilon }$ 및 minPts 매개변수를 가진 DBSCAN 군집화 결과와 유사함; 여기서 0.1 정도의 값이 좋은 결과를 낼 수 있음). 또는 급경사, 무릎 감지, 국소 최대값을 통해 계곡을 감지하려는 다양한 알고리즘을 사용할 수도 있다. 급격한 하강으로 시작하여 급격한 상승으로 끝나는 플롯의 범위는 계곡으로 간주되며, 고밀도의 인접 영역에 대응된다. 계곡의 마지막 점들을 내부 또는 외부 군집에 할당할 때는 이전 점을 고려하여 추가적인 주의를 기울여야 한다.^[4] 이런 방식으로 얻은 군집화는 일반적으로 계층적 군집화이며, 단일 DBSCAN 실행으로는 달성할 수 없다.

DBSCAN과 마찬가지로 OPTICS는 각 점을 한 번씩 처리하며, 이 과정에서 한 번의 ${\displaystyle \varepsilon }$-이웃 질의를 수행한다. ${\displaystyle O(\log n)}$ 시간 복잡도로 이웃 질의를 보장하는 공간 인덱스가 주어진다면, 전체 시간 복잡도는 ${\displaystyle O(n\cdot \log n)}$이 된다. 그러나 최악의 경우 DBSCAN과 같이 ${\displaystyle O(n^{2})}$이다. 원본 OPTICS 논문의 저자들은 DBSCAN과 비교하여 1.6배의 실제 상수 속도 저하를 보고했다. ${\displaystyle \varepsilon }$ 값이 너무 크면 이웃 질의 비용이 선형 복잡도로 상승할 수 있으므로, ${\displaystyle \varepsilon }$ 값이 알고리즘 비용에 큰 영향을 미칠 수 있음에 유의해야 한다.

특히 ${\displaystyle \varepsilon >\max _{x,y}d(x,y)}$ (데이터 세트의 최대 거리보다 크게)로 선택하는 것은 가능하지만, 모든 이웃 질의가 전체 데이터 세트를 반환하기 때문에 이차 복잡도를 초래한다. 공간 인덱스를 사용할 수 없는 경우에도 힙을 관리하는 데 추가 비용이 든다. 따라서 ${\displaystyle \varepsilon }$은 데이터 세트에 적합하게 선택해야 한다.

OPTICS-OF^[5]는 OPTICS 기반의 이상 탐지 알고리즘이다. 주요 용도는 다른 이상 탐지 방법 대비 낮은 비용으로 기존 OPTICS 실행에서 이상치를 추출하는 것이다. 더 잘 알려진 버전인 LOF도 동일한 개념에 기반한다.

DeLi-Clu^[6]는 Density-Link-Clustering의 약자로, 계층적 군집화와 OPTICS의 아이디어를 결합하여 ε 매개변수를 제거하고 OPTICS보다 성능을 개선한다.

HiSC^[7]는 OPTICS 기반의 계층적 부분 공간 군집화 방법이다.

HiCO^[8]는 OPTICS 기반의 계층적 상관 군집화 알고리즘이다.

DiSH^[9]는 더 복잡한 계층을 찾을 수 있는 HiSC의 개선판이다.

FOPTICS^[10]는 랜덤 투영을 사용하여 더 빠른 구현을 제공한다.

HDBSCAN*^[11]은 DBSCAN의 개선판을 기반으로 하며, 경계점들을 군집에서 제외함으로써 하티건(Hartigan)이 정의한 밀도 수준의 기본 정의를 더 엄격하게 따른다.^[12]

OPTICS Cordillera^[13]는 데이터 세트의 군집화 정도를 나타내는 설명적 Scagnostics 측정치이다. OPTICS를 사용하여 덴드로그램을 생성한 다음, 덴드로그램 정보를 0(군집화 없음)과 1(최대 군집화) 사이의 군집화 정도로 집계한다.

OPTICS, OPTICS-OF, DeLi-Clu, HiSC, HiCO 및 DiSH의 자바 구현은 ELKI 데이터 마이닝 프레임워크에서 사용할 수 있다(여러 거리 함수에 대한 인덱스 가속 및 ξ 추출법을 사용한 자동 군집 추출 기능 포함). 다른 자바 구현체로는 Weka 확장(군집 추출용 ξ 미지원)이 있다.

R 패키지 "dbscan"은 유클리드 거리에 대해서만 K-d 트리를 사용한 인덱스 가속을 지원하는 C++ 기반의 OPTICS 구현(전통적인 dbscan 방식 및 ξ 군집 추출 방식 모두 포함)을 포함하고 있다.

OPTICS의 파이썬 구현은 PyClustering 라이브러리와 Scikit-learn에서 사용할 수 있다. HDBSCAN*은 hdbscan 라이브러리에서 사용할 수 있다.