GALACTIC: Global and Local Agnostic Counterfactuals for Time-series Clustering

이 논문은 기존 설명 방법의 한계를 극복하고 시계열 클러스터링의 국소적 및 전역적 해석을 통합하기 위해, 최소 설명 길이 (MDL) 기반의 효율적인 알고리즘을 제안한 'GALACTIC' 프레임워크를 소개합니다.

핵심

이 논문은 **'GALACTIC'**이라는 새로운 도구를 소개합니다. 이 도구의 역할은 시간이 지남에 따라 변하는 데이터(예: 주식 차트, 심박수, 날씨 기록 등)를 그룹으로 묶을 때, **"왜 이 데이터가 A 그룹에 속하고, 어떻게 하면 B 그룹으로 바뀔 수 있을까?"**를 설명해주는 것입니다.

기존의 방법들은 "이 데이터는 A 그룹이야"라고만 말해주거나, 너무 복잡해서 이해하기 어려웠습니다. GALACTIC 은 이를 훨씬 직관적이고 간단하게 설명해줍니다.

이 내용을 일상적인 비유로 쉽게 풀어보겠습니다.

---

1. 상황: 혼란스러운 파티와 그룹 나누기

가상의 파티를 상상해 보세요. 수많은 손님들이 들어와서 서로 대화하며 무리를 짓고 있습니다.

• 클러스터링 (Clustering): 파티에서 사람들은 자연스럽게 비슷한 취향이나 옷차림을 기준으로 무리를 만듭니다. 하지만 파티 주최자 (컴퓨터 알고리즘) 는 "저 무리는 왜 저렇게 모였지?"라고 물어보면 "모르겠다, 그냥 그렇게 된 거야"라고 답할 뿐입니다.
• 문제점: 우리는 단순히 "저 무리는 A 그룹이야"라는 라벨만 원하는 게 아닙니다. "내가 만약 이런 행동을 했다면, A 그룹이 아니라 B 그룹으로 갈 수 있을까?"라는 구체적인 변화의 시나리오를 알고 싶어 합니다.

2. GALACTIC 의 등장: "만약에..."를 알려주는 마법사

GALACTIC 은 이 파티에서 두 가지 중요한 역할을 하는 마법사입니다.

역할 1: 개인에게 맞는 설명 (Local - 로컬)

• 비유: 한 손님이 "저는 왜 이 그룹에 속해 있나요?"라고 물었을 때, GALACTIC 은 **"만약 당신이 이 30 분 동안만 조금 더 웃고, 이 5 분 동안만 조용히 있다면, 당신은 바로 옆의 다른 그룹으로 이동할 수 있어요"**라고 말합니다.
• 핵심:
  • 최소한의 변화: 손님의 성격을 완전히 바꾸는 게 아니라, 가장 중요한 부분만 살짝 건드려서 그룹을 바꾸는 방법을 찾습니다. (예: 옷 전체를 갈아입는 게 아니라, 넥타이 색깔만 바꾸는 것)
  • 자연스러움: 데이터의 흐름을 무시하고 엉뚱한 부분만 건드리지 않습니다. 마치 사람의 말투를 바꾸되, 원래의 말투 특징은 살려주는 것처럼요.

역할 2: 전체 그룹을 위한 요약 (Global - 글로벌)

• 비유: 파티 주최자가 "A 그룹 전체가 B 그룹으로 가려면 어떤 공통된 변화가 필요할까?"라고 물었을 때, GALACTIC 은 수천 명의 개인별 설명을 일일이 나열하는 대신, **"A 그룹의 사람들이 B 그룹으로 가려면, 대부분 '음악을 크게 틀고 춤을 추는 것'을 멈추고 '조용히 대화하는 것'을 시작해야 해요"**라고 한두 가지 핵심 요약을 알려줍니다.
• 핵심:
  • 불필요한 정보 제거: 수천 가지의 다른 설명이 있을 때, 가장 중요하고 반복되는 패턴만 추려냅니다. (마치 긴 뉴스 기사를 한 줄의 헤드라인으로 요약하는 것)
  • 효율성: 너무 많은 설명은 오히려 혼란을 줍니다. GALACTIC 은 "가장 적은 정보로 가장 많은 사람을 설명할 수 있는 방법"을 찾아냅니다.

3. GALACTIC 의 비밀 무기: "MDL" (최소 설명 길이)

이 도구가 어떻게 이렇게 똑똑한 요약을 할 수 있을까요? 바로 **MDL(Minimum Description Length)**이라는 원리를 사용합니다.

• 비유: 친구에게 여행 계획을 설명할 때, "첫날 A, 둘째날 B, 셋째날 C..."라고 100 줄로 설명하는 대신, **"우리는 '산'을 좋아하니까 산으로 가는 길만 따라가자"**라고 한 줄로 설명하는 것과 같습니다.
• 원리: GALACTIC 은 "이 설명을 전달하는 데 필요한 정보의 양 (비트 수)"을 계산합니다. 설명이 너무 길면 (복잡하면) 점수를 낮추고, 설명이 짧으면서도 많은 사람을 설명할 수 있으면 점수를 높게 줍니다. 이를 통해 가장 간결하고 확실한 설명만 골라냅니다.

4. 왜 이것이 중요한가요?

• 기존의 문제: 예전 방법들은 "이게 A 그룹이야"라고만 알려주거나, 너무 복잡한 설명을 줘서 사람들이 이해하지 못했습니다.
• GALACTIC 의 장점:
  1. 간결함: "이 부분만 고치면 그룹이 바뀐다"라고 명확하게 알려줍니다.
  2. 신뢰성: 데이터의 흐름을 무시하지 않고, 자연스러운 변화만 제안합니다.
  3. 빠름: 복잡한 계산을 효율적으로 해서 결과를 빨리 줍니다.

요약

GALACTIC은 복잡한 데이터 그룹을 분석할 때, **"왜 이 데이터가 여기에 속하는지"**와 **"어떻게 하면 다른 그룹으로 갈 수 있는지"**를 가장 간단하고 명확하게 설명해주는 도구입니다.

마치 복잡한 지도를 읽지 않고도, "이 길만 따라가면 목적지에 간다"라고 알려주는 친절한 길잡이와 같습니다. 이제 우리는 데이터가 왜 그렇게 행동하는지, 그리고 어떻게 변화시킬 수 있는지 훨씬 쉽게 이해할 수 있게 되었습니다.

기술 요약

1. 문제 정의 (Problem Definition)

• 배경: 시계열 데이터 클러스터링은 금융, 신경과학, 로봇공학 등 다양한 분야에서 패턴 발견을 위한 핵심 도구입니다. 그러나 기존 클러스터링 모델은 '블랙박스' 성향이 강하며, 특정 인스턴스가 왜 특정 클러스터에 할당되었는지, 그리고 어떻게 변형되어야 다른 클러스터로 이동할 수 있는지에 대한 설명 (Explainability) 이 부족합니다.
• 한계:
  • 기존 설명 방법론 (특성 중요도, 메타데이터 등) 은 클러스터 경계를 넘나드는 전환 (Transition) 을 식별하지 못합니다.
  • 기존 반사실적 설명 (Counterfactual Explanations, CEs) 은 주로 지도 학습 (Supervised) 환경에 국한되어 있으며, 비지도 클러스터링의 잠재적 구조를 반영하지 못합니다.
  • 시계열 데이터의 경우, 기존 CE 방법들은 시간적 일관성을 해치거나 특징적인 구조를 무시한 채 노이즈가 많은 편집을 생성하는 경향이 있습니다.
• 목표: 클러스터링 알고리즘의 종류에 구애받지 않는 (Agnostic) 로컬 (개별 인스턴스) 과 글로벌 (전체 클러스터) 수준의 반사실적 설명을 통합하여 제공하는 프레임워크 개발.

2. 방법론 (Methodology: GALACTIC Framework)

GALACTIC 은 로컬 및 글로벌 설명을 위한 두 단계의 접근 방식을 제시합니다.

2.1. 로컬 반사실적 설명 (Local Counterfactuals)

• 목표: 특정 시계열 인스턴스를 현재 클러스터에서 다른 타겟 클러스터로 이동시키는 최소한의 시간적 변형 (Perturbation) 을 생성.
• 핵심 기법:
  • 확률적 대리 모델 (Probabilistic Surrogate): 클러스터링 알고리즘의 결정 경계를 근사하는 분류기 $g$를 학습하여 미분 가능한 목적 함수를 확보합니다.
  • 구조 인식 최적화 (Structure-Aware Optimization):
    • 세그먼트화 및 중요도 매핑: 변화점 탐지 (Change-point detection) 를 통해 시계열을 세그먼트로 나누고, 서브그룹 (Subgroup) 단위로 순열 분석 (Permutation analysis) 을 수행하여 '차별적 시간 구간'을 식별합니다.
    • 가중치 마스크 (Importance Mask): 식별된 고중요도 구간에만 편집을 허용하는 하드 제약 (Hard constraint) 을 적용합니다. 이는 불필요한 시간 구간을 변경하지 않고 시계열의 전체적인 형태 (Shape) 를 보존하며 희소성 (Sparsity) 을 확보합니다.
  • 최적화: 근접성 (Proximity) 과 유효성 (Validity, 클러스터 전환) 을 균형 있게 고려하는 목적 함수 하에 경사 하강법 (Gradient-based optimization) 을 수행합니다.

2.2. 글로벌 반사실적 설명 (Global Counterfactuals)

• 목표: 수천 개의 로컬 반사실적 설명을 요약하여, 전체 클러스터 집단의 전환을 설명하는 대표적인 변형 패턴 (Representative Perturbations) 의 집합을 선택.
• 핵심 기법:
  • 최소 설명 길이 (Minimum Description Length, MDL): 설명의 복잡도 (모델 길이) 와 설명되지 않은 데이터 (잔여 오차) 를 동시에 고려하는 정보 이론적 접근법을 도입합니다.
    • $L(M)$: 선택된 변형 집합의 복잡도 (개수, 희소성, 크기).
    • $L(D|M)$: 선택된 변형으로 설명되지 않은 인스턴스들의 비용.
  • 서브모듈러 최적화 (Submodular Optimization):
    • MDL 목적 함수가 초모듈러 (Supermodular) 성질을 가지며, 이에 따른 MDL 감소량이 단조 서브모듈러 (Monotone Submodular) 집합 함수임을 수학적으로 증명했습니다.
    • 이 성질을 이용하여 그리디 (Greedy) 알고리즘을 적용함으로써, $(1 - 1/e)$ 의 근사 보장 (Approximation guarantee) 을 가지면서 효율적으로 최적의 변형 집합을 선택합니다.
  • 계층적 정제 (Hierarchical Refinement): 클러스터 내 서브그룹의 밀도와 복잡도에 따라 계층적으로 설명을 정제하여 확장성을 높입니다.

3. 주요 기여 (Key Contributions)

1. 문제 공식화: 비지도 시계열 클러스터링에 대한 로컬 및 글로벌 반사실적 설명을 모델-중립적 (Model-agnostic) 인 환경에서 공식화했습니다.
2. 구조적 제약이 있는 로컬 CE: 서브그룹 및 클러스터별 시간적 중요도를 활용한 제약 경사 최적화를 통해, 희소하고 형태를 보존하는 반사실적 설명을 생성하는 방법을 제안했습니다.
3. MDL 기반 글로벌 요약: 다목적 최적화의 트레이드오프를 해결하기 위해 파라미터가 필요 없는 MDL 기반 모델 선택 목적 함수를 제안하고, 서브모듈러성을 증명하여 효율적인 그리디 선택 전략을 도출했습니다.
4. 적응형 계층적 정제: 클러스터 서브그룹의 내부 밀도를 활용하여 조정 가능한 글로벌 설명을 제공하는 확장성 있는 메커니즘을 개발했습니다.
5. 종합적 실험 평가: UCR 아카이브의 30 개 데이터셋을 통해 GALACTIC 이 기존 기법들보다 더 희소한 로컬 CE 와 더 간결한 글로벌 요약을 생성함을 입증했습니다.

4. 실험 결과 (Experimental Results)

• 데이터셋: UCR Time-Series Archive 의 30 개 데이터셋 (이미지, 모션, 센서 등 다양한 도메인).
• 비교 대상:
  • 로컬: $k$-NN, TSEvo (진화 알고리즘), Glacier (경사 기반).
  • 글로벌: GLOBE-CE*, Glacier-G* (클러스터링 환경에 맞게 수정된 기법).
• 성능 지표: 유효성 (Effectiveness), 평균 전환 비용 (Average Flipping Cost), 변경된 세그먼트/타임스텟 수 (Sparsity), 실행 시간.
• 주요 결과:
  • 로컬 성능: GALACTIC-L 은 기존 기법들보다 더 높은 유효성과 훨씬 더 낮은 비용 (희소성) 을 달성했습니다. 특히 TSEvo 는 비용이 높고 실행 시간이 길었으며, Glacier 는 불필요한 시간 구간을 변경하는 경향이 있었습니다.
  • 글로벌 성능: GALACTIC-G 는 MDL 기반 선택을 통해 더 높은 커버리지와 더 낮은 전환 비용을 제공하며, 기존 글로벌 기법들보다 압도적으로 빠른 실행 시간을 보였습니다.
  • 타겟 선택: 무작위 타겟 선택보다 '두 번째로 확률이 높은 클러스터 (Second Possible)'를 타겟으로 설정할 때 유효성이 크게 향상되었습니다.

5. 의의 및 결론 (Significance)

• 이론적 기여: 비지도 학습 환경에서의 반사실적 설명 문제를 MDL 과 서브모듈러 최적화 이론을 통해 엄밀하게 수학화했습니다.
• 실용적 가치: 클러스터링 결과의 투명성을 높여, 의사결정 지원 도구로서의 활용도를 극대화합니다. 예를 들어, "어떤 시계열이 어떤 패턴을 바꾸면 다른 행동 양상 (클러스터) 으로 변할 수 있는지"를 구체적이고 실행 가능한 인사이트로 제공합니다.
• 확장성: 시계열 데이터의 시간적 의존성과 구조적 특성을 고려하여, 다양한 도메인 (의료, 금융, IoT 등) 에 적용 가능한 범용적인 프레임워크를 제시했습니다.

요약하자면, GALACTIC 은 비지도 시계열 클러스터링의 불투명성을 해결하기 위해 로컬 수준의 구조 보존 반사실적 설명과 글로벌 수준의 MDL 기반 요약을 통합한 최초의 프레임워크로, 이론적 엄밀성과 실용적 효율성을 모두 갖춘 획기적인 접근법입니다.