기술 요약: ExDBSCAN – 반사실 추론을 통한 DBSCAN 설명

문제 제기

클러스터링은 근본적인 비지도 학습 기법이지만, 지도 학습에 비해 해석 가능성의 격차가 큽니다. 반사실 설명 (CEs) 은 예측을 변경하는 최소한의 입력 변화를 식별함으로써 지도 학습 모델 설명의 표준이 되었지만, 클러스터링에는 직접 적용되지 않습니다. 이 격차는 임의의 모양을 가진 클러스터를 찾고 노이즈를 식별할 수 있는 인기 있는 알고리즘인 DBSCAN(Density-Based Spatial Clustering of Applications with Noise) 에 특히 심각합니다.

DBSCAN 은 $\varepsilon$과 $minPts$ 파라미터로 정의된 밀도 도달 가능성에 기반하여 점들을 코어, 경계, 또는 노이즈로 할당합니다. 그러나 특정 점이 왜 그 할당을 받았는지, 또는 그 할당이 작은 데이터 변화에 대해 견고한지에 대한 통찰력을 제공하지는 않습니다. 기존 CE 방법들은 DBSCAN 에 적용될 때 다음과 같은 세 가지 주요 장애물에 직면합니다:

1. 미분 가능성 부족: DBSCAN 은 미분 가능한 손실 함수를 사용하지 않으므로, 지도 학습 CE 생성에서 흔히 사용되는 경계 기반 검색 방법을 사용할 수 없습니다.
2. 확률의 부재: 분류 모델과 달리 DBSCAN 은 연속적인 클래스 확률 대신 이산적이고 연결성 기반의 소속 관계를 제공하며, 많은 모델-중립적 (model-agnostic) CE 방법들은 이에 의존합니다.
3. 복잡한 유사성 구조: DBSCAN 의 밀도 연결성은 두 점이 유클리드 공간에서는 가깝더라도 클러스터 소속 측면에서는 효과적으로 멀리 떨어져 있을 수 있음을 의미합니다 (긴 밀도 연결 경로를 필요로 함). 다른 CE 방법들이 사용하는 표준 유클리드 거리 척도는 이를 포착하지 못해, 중복되거나 무효한 반사실 예시를 생성할 수 있습니다.

방법론: ExDBSCAN

저자들은 DBSCAN 에 특화된 최초의 사후 (post-hoc) 설명 방법인 ExDBSCAN을 제안합니다. 이 방법은 노이즈에서 클러스터로의 전환과 클러스터 간 전환 모두에 대해 실행 가능한 반사실 예시를 생성하며, 유효성에 대한 이론적 보장을 제공합니다.

핵심 구성 요소

1. 그래프 기반 유사성 표현:
   유클리드 거리에 의존하는 대신, ExDBSCAN 은 클러스터 구조를 무방향 가중 그래프 $G(V, E)$로 모델링합니다.

   • 정점 ($V$): 클러스터의 코어 점들을 나타냅니다.
   • 간선: 두 정점이 직접 밀도 도달 가능 (거리 $< \varepsilon$) 한 경우 연결됩니다.
   • 가중치: 연결된 코어 점들 간의 유클리드 거리입니다.
   • 거리 척도: 임의의 두 점 사이의 거리는 $G$ 내의 가중 최단 경로로 정의됩니다. 이는 "근접성"이 클러스터의 밀도 연결 구조를 존중하도록 보장합니다.

2. 물리학에서 영감을 받은 최적화:
   $k$개의 다양하고 근접한 반사실 예시 세트를 생성하기 위해, ExDBSCAN 은 참조 코어 점들의 선택을 물리적 에너지 최소화 문제로 모델링합니다. 이 시스템은 후보 코어 점들을 두 가지 힘에 노출된 하전 입자로 간주합니다:

   • 반발 (다양성): 쿨롱의 법칙을 모방하여, 후보 코어 점들은 서로를 반발합니다. 반발력은 그들 사이의 가중 최단 경로 거리에 반비례합니다. 이는 선택된 반사실 예시들이 클러스터의 밀도 구조 전반에 걸쳐 퍼지도록 하여 중복을 방지합니다.
   • 인력 (근접성): 훅의 법칙 (스프링 힘) 을 모방하여, 후보 코어 점들은 설명 대상인 원래 인스턴스 $p$로 끌립니다. 힘은 거리에 비례하여 증가하며, 선택을 가장 가까운 유효 코어 점 쪽으로 편향시킵니다.

   선택된 코어 점 집합 $C'$의 총 에너지 $E_{C'}$는 다음과 같이 정의됩니다:
   $$E_{C'} = \sum_{V_i \in C'} \sum_{V_j \in C': j > i} \frac{1}{D(V_i, V_j)} + \sum_{V_i \in C'} d^2(p, V_i)$$
   여기서 $D$는 가중 그래프 거리이고, $d$는 원래 점까지의 유클리드 거리입니다.

3. 최적화 및 구성:

   • NP-난해성: 이 에너지를 최소화하는 코어 점들의 최적 집합을 찾는 것은 NP-난해한 것으로 증명되었습니다. ExDBSCAN 은 근사 해를 구하기 위해 **탐욕 알고리즘 (greedy algorithm)**을 사용합니다. 이는 현재 선택된 집합을 고려할 때 총 시스템 에너지를 최소화하는 코어 점을 반복적으로 선택합니다.
   • 반사실 생성: 참조 코어 점 집합이 선택되면, 최종 반사실 예시들은 이러한 코어 점들의 $\varepsilon$-이웃 내에서 구성됩니다. 구체적으로, 반사실 예시 $p'$는 원래 점 $p$의 방향으로 참조 코어 $q$로부터 거리 $\varepsilon$만큼 떨어진 위치에 배치됩니다.
   • 유효성 보장: 구성에 의해, 생성된 모든 반사실 예시는 목표 클러스터의 코어 점으로부터 $\varepsilon$ 이내에 위치하므로, DBSCAN 의 밀도 연결 기준을 충족하고 목표 클러스터의 유효한 구성원이 됩니다.

4. 제약 조건 처리:
   이 방법은 실행 불가능한 특성 (예: 나이, 성별) 을 고려하여 검색 공간을 제한합니다. 비실행 가능 속성을 수정하지 않고도 $\varepsilon$-이웃에 도달할 수 있도록 코어 점들을 필터링하여 설명이 현실적으로 유지되도록 합니다.

주요 기여

• 최초의 DBSCAN 특화 CE 방법: ExDBSCAN 은 밀도 기반 클러스터링, 특히 노이즈에서 클러스터로의 전환과 클러스터 간 전환을 모두 다루기 위해 설계된 최초의 반사실 설명 방법입니다.
• 새로운 물리학 영감 모델: 저자들은 정전기적 반발과 스프링 같은 인력을 사용하여 근접성과 다양성을 균형 있게 조절하는 모델을 도입했으며, 가중 그래프를 통해 DBSCAN 의 밀도 연결 구조를 명시적으로 고려합니다.
• 이론적 유효성: 이 방법은 생성된 모든 반사실 예시가 DBSCAN 의 할당 규칙 하에서 유효하다는 이론적 보장 (정리 3.1) 을 제공합니다.
• 실증적 우수성: 30 개의 표형 데이터셋에 대한 광범위한 평가에서 ExDBSCAN 은 유효성, 근접성, 다양성 측면에서 기존 베이스라인 (BayCon, DiCE, Growing Spheres 와 같은 모델-중립적 방법 포함) 보다 우수함을 입증했습니다.

실험 결과

저자들은 30 개의 OpenML 표형 데이터셋에서 ExDBSCAN 을 DiCE, BayCon, Growing Spheres 및 무작위 변형 등을 포함한 7 개의 베이스라인과 비교 평가했습니다.

• 유효성: ExDBSCAN 은 모든 쿼리에서 100% 유효성을 달성했습니다. 반면, 대리 모델 기반 방법 (DiCE-Surrogate, GS-Surrogate) 과 모델-중립적 방법 (BayCon) 은 심각한 어려움을 겪었으며, 종종 50% 미만의 유효성률을 보였습니다. 이는 그들의 연속 최적화 목적 함수와 DBSCAN 의 이산적이고 밀도 기반 할당 사이의 불일치 때문입니다.
• 근접성: 높은 유효성을 달성한 방법들 중에서 ExDBSCAN 은 경쟁사보다 원래 인스턴스에 훨씬 더 가까운 반사실 예시를 생성했습니다. 이는 그래프 기반 거리를 사용한 스프링 같은 인력 항의 명시적 최적화 때문입니다.
• 다양성: ExDBSCAN 은 가장 높은 다양성 점수를 달성했습니다. 클러스터 그래프 내의 가중 최단 경로 거리에 기반한 반발 메커니즘은 선택된 반사실 예시들이 유클리드 공간에서 단순히 가깝기만 한 것이 아니라, 클러스터의 위상 내에서 구별되는 대안을 대표하도록 보장했습니다.
• 실행 시간: ExDBSCAN 은 단순한 무작위 휴리스틱보다 계산적으로 더 집약적이지만, 특히 유효한 반사실 예시를 찾지 못하는 경우 DiCE 와 BayCon 이 요구하는 무거운 최적화보다 일반적으로 더 빠릅니다.

중요성과 주장

이 논문은 ExDBSCAN 을 비지도 학습의 해석 가능성 격차를 해소하는 중요한 단계로 위치시킵니다. 저자들은 DBSCAN 의 특정 메커니즘에 맞춘 반사실 추론을 활용함으로써 실무자들이 다음을 얻을 수 있다고 주장합니다:

• 실행 가능한 통찰력: 어떤 특성이 점의 클러스터 할당이나 노이즈 상태를 주도하는지 이해합니다.
• 견고성 점검: 클러스터 할당이 작은 교란에 대해 안정적인지 아니면 민감한지 평가합니다.
• 신뢰와 투명성: 대리 모델이 만든 인위적인 경계가 아니라 데이터의 실제 밀도 기반 구조를 반영하는 "만약에 (what-if)" 시나리오를 제공합니다.

저자들은 공식적인 사용자 연구가 이 작업의 범위를 벗어난다고 겸손하게 언급하지만, 이 방법은 클러스터 할당이 어떻게 변경될 수 있는지에 대한 구체적이고 이론적으로 근거 있는 예시를 제공한다고 강조합니다. 그들은 향후 작업이 ExDBSCAN 을 점진적 또는 스트리밍 시나리오로 확장하고 현재 탐욕 근사법을 넘어선 더 정교한 최적화 전략을 탐구할 수 있음을 제안합니다.