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

Die Arbeit stellt GALACTIC vor, ein einheitliches Framework, das erstmals lokale und globale kontrafaktische Erklärungen für das unüberwachte Clustering von Zeitreihen vereint, indem es instanzspezifische Störungen generiert und durch ein supermodulares MDL-Optimierungsverfahren eine kompakte, nicht-redundante globale Zusammenfassung der Clusterübergänge liefert.

Das Wesentliche

🌌 GALACTIC: Der Navigator für Zeitreihen-Cluster

Stellen Sie sich vor, Sie haben einen riesigen Haufen von Musikstücken (das sind die Zeitreihen). Ein Computer sortiert diese Musik automatisch in verschiedene Regale: Regal A für „Traurige Balladen", Regal B für „Tanzmusik" und Regal C für „Jazz". Das nennt man Clustering.

Das Problem: Der Computer sagt Ihnen nur: „Dieses Lied gehört zu Regal B." Aber er erklärt nicht, warum. Und noch wichtiger: Er sagt Ihnen nicht, was Sie ändern müssten, damit dieses Lied plötzlich in Regal A (die Balladen) landen würde.

Bisherige Methoden waren wie ein blinder Koch, der nur Zutaten auflistet, aber nicht sagt, wie man das Rezept ändert. GALACTIC ist der neue, cleere Koch, der Ihnen genau sagt: „Ändere nur die Geschwindigkeit im zweiten Takt, und dein Lied wird zur Ballade."

Hier ist, wie GALACTIC das macht, aufgeteilt in zwei Ebenen:

---

1. Die lokale Ebene: Der Einzelfall (Der „Was-wäre-wenn"-Fall)

Stellen Sie sich vor, Sie haben ein einzelnes Musikstück, das im Computer fälschlicherweise als „Tanzmusik" (Regal B) gelabelt wurde, obwohl es eigentlich wie eine Ballade klingt. Sie wollen wissen: Was ist das Mindestmaß an Änderung, damit der Computer es als Ballade erkennt?

• Das alte Problem: Bisherige Methoden waren oft wie ein wilder Maler. Sie haben das ganze Bild übermalt, um die Farbe zu ändern. Das Ergebnis war oft unbrauchbar oder klang nicht mehr wie Musik.
• Die GALACTIC-Lösung: GALACTIC nutzt eine Art „Wichtigkeits-Maske".
  • Es analysiert das Lied und sagt: „Die ersten 10 Sekunden sind egal für die Klassifizierung. Aber die Melodie zwischen Sekunde 15 und 20 ist entscheidend."
  • GALACTIC ändert nur diese kritischen 5 Sekunden. Alles andere bleibt unberührt.
  • Die Analogie: Stellen Sie sich vor, Sie wollen einen Schalter umlegen, damit das Licht angeht. Ein alter Roboter würde versuchen, das ganze Haus umzubauen. GALACTIC drückt nur genau den richtigen Schalter. Das Ergebnis ist sparsam, präzise und klingt immer noch wie das Original.

2. Die globale Ebene: Der Überblick (Die „Zusammenfassung")

Jetzt stellen Sie sich vor, Sie haben nicht nur ein Lied, sondern 1.000 Lieder im Regal „Tanzmusik". Sie wollen wissen: „Was haben diese Lieder gemeinsam, und wie kann man alle von ihnen in die Balladen-Regale verschieben?"

• Das alte Problem: Wenn man 1.000 einzelne Erklärungen gibt („Lied 1: Ändere Takt 3", „Lied 2: Ändere Takt 5"), bekommt man ein unübersichtliches Chaos. Das ist zu viel Information für das menschliche Gehirn.
• Die GALACTIC-Lösung: GALACTIC nutzt ein Prinzip namens MDL (Minimum Description Length).
  • Die Analogie: Stellen Sie sich vor, Sie wollen einem Freund erklären, wie man alle diese 1.000 Lieder in Balladen verwandelt.
    • Schlechter Weg: Sie schreiben 1.000 separate Anweisungen auf.
    • GALACTIC-Weg: GALACTIC sucht nach den wichtigsten 3 bis 5 Regeln, die für die meisten Lieder gelten. Es sagt: „Wenn du bei 80 % der Lieder die Geschwindigkeit leicht drosselst und die Basslinie weich machst, sind sie alle Balladen."
  • GALACTIC filtert die unnötigen Details heraus und liefert eine kompakte Zusammenfassung. Es wählt die Erklärungen so aus, dass sie den größten Nutzen bei der kleinsten Beschreibung bieten (wie ein gut zusammengefasstes Kochbuch statt einer Liste von 1.000 einzelnen Rezepten).

Warum ist das so besonders?

1. Es ist „agnostisch": GALACTIC ist wie ein Universal-Schlüssel. Es funktioniert mit jedem beliebigen Computer-Algorithmus, der die Musik sortiert, egal wie komplex oder geheimnisvoll dieser Algorithmus ist.
2. Es ist effizient: Durch die mathematische Magie (Submodularität) kann GALACTIC die besten Erklärungen sehr schnell finden, ohne stundenlang zu rechnen. Es ist wie ein kluger Suchalgorithmus, der sofort weiß, welche 3 Bücher in einer Bibliothek die wichtigsten sind, ohne jedes Buch lesen zu müssen.
3. Es ist verständlich: Anstatt zu sagen „Ändere 500 Datenpunkte", sagt es: „Ändere nur diesen einen kleinen Abschnitt." Das macht die Ergebnisse für Menschen (z. B. Ärzte, Finanzanalysten oder Ingenieure) wirklich nutzbar.

Fazit

GALACTIC ist wie ein Dolmetscher zwischen dem Computer und dem Menschen.

• Auf lokaler Ebene sagt es Ihnen: „Hier ist der winzige Knopf, den du drücken musst, um dein Ergebnis zu ändern."
• Auf globaler Ebene sagt es Ihnen: „Hier sind die drei Hauptregeln, die erklären, warum diese ganze Gruppe von Daten so ist, wie sie ist, und wie man sie verändert."

Es verwandelt undurchsichtige Datenberge in klare, handlungsanweisende Anleitungen – und das alles, ohne das ursprüngliche Muster der Daten zu zerstören.

Technische Zusammenfassung

1. Problemstellung

Das Paper adressiert die mangelnde Erklärbarkeit (Explainability) von Time-Series-Clustering. Während Clustering ein fundamentales Werkzeug zur Mustererkennung in zeitlichen Daten ist (z. B. in Finanzen, Medizin oder Robotik), bleiben die zugrunde liegenden Zuweisungslogiken oft intransparent („Black Box").

Bestehende Erklärungsansätze scheitern an zwei Hauptproblemen:

• Fokus auf überwachtes Lernen: Die meisten Methoden für kontrafaktische Erklärungen (Counterfactual Explanations, CEs) sind für Klassifikationsaufgaben (überwacht) entwickelt und nicht für das unsupervised Clustering geeignet.
• Fehlende globale Übersicht: Aktuelle Methoden liefern oft nur lokale Erklärungen für einzelne Instanzen, aber keine konsolidierte, globale Zusammenfassung darüber, wie sich ganze Cluster-Gruppen verhalten oder wie Übergänge zwischen Clustern strukturell aussehen.
• Strukturelle Inkonsistenz: Bei Zeitreihen führen viele bestehende Methoden zu „rauschhaften" oder nicht zusammenhängenden Änderungen, die die charakteristische Form der Zeitreihe zerstören.

Das Ziel von GALACTIC ist es, einen einheitlichen, modellagnostischen Rahmen zu schaffen, der sowohl lokale (instanzspezifische) als auch globale (cluster-spezifische) kontrafaktische Erklärungen für Zeitreihen-Clustering generiert.

2. Methodik: Der GALACTIC-Rahmen

GALACTIC besteht aus zwei Hauptkomponenten: einer lokalen Suchstrategie und einer globalen Selektionsstrategie.

A. Lokale Ebene (Local Counterfactuals)

Für eine einzelne Zeitreihe $x$, die einem Cluster $C_k$ zugeordnet ist, sucht GALACTIC eine minimale Perturbation $\delta$, sodass die Reihe in einen Zielcluster $C_{k'}$ wechselt.

• Probabilistischer Surrogat: Da viele Clustering-Algorithmen keine explizite Entscheidungsfunktion für neue Datenpunkte bieten (transduktiv), wird ein probabilistischer Surrogat-Klassifikator $g$ trainiert, der die Cluster-Zuordnungen approximiert.
• Strukturelle Einschränkungen & Wichtigkeitsmasken: Um die zeitliche Kohärenz zu bewahren, wird die Suche nicht im gesamten Raum durchgeführt. Stattdessen wird eine Wichtigkeitsmaske ($w$) verwendet, die nur diskriminierende zeitliche Segmente für Änderungen zulässt.
  • Diese Masken werden durch Permutationsanalysen abgeleitet: Segmente werden zufällig gemischt, und der Einfluss auf die Surrogat-Genauigkeit wird gemessen.
  • Es werden drei Strategien kombiniert: Source-Importance (Schutz der aktuellen Cluster-Identität), Target-Importance (Fokus auf Merkmale des Zielclusters) und eine Kombinierte Strategie, die beides berücksichtigt.
• Optimierung: Die Suche erfolgt über einen gradientenbasierten Optimierer (Adam), der die Maske als harte Einschränkung auf die Gradienten anwendet ($\nabla \leftarrow \nabla \odot w$). Dies stellt sicher, dass nur kritische Zeitpunkte verändert werden, während die globale Struktur erhalten bleibt.

B. Globale Ebene (Global Counterfactuals)

Das Ziel ist es, eine kleine Menge von Perturbationen zu finden, die für einen großen Teil der Cluster-Instanzen einen Cluster-Wechsel bewirken (hohe Abdeckung) und dabei minimalen Aufwand (Kosten) verursachen.

• Kandidatengenerierung: Zuerst werden lokale kontrafaktische Beispiele für repräsentative Instanzen (Prototypen und „Kritiker" mittels MMD-Critic) generiert, um einen Pool potenzieller globaler Perturbationen zu erstellen.
• MDL-Optimierung (Minimum Description Length): Anstatt ein mehrkriterielles Optimierungsproblem (Abdeckung vs. Kosten) manuell zu gewichten, formuliert GALACTIC die Auswahl als MDL-Problem.
  • Das Ziel ist es, die Gesamtlänge der Beschreibung $L(D, M) = L(M) + L(D|M)$ zu minimieren.
  • $L(M)$: Komplexität der gewählten Perturbationen (Anzahl, Sparsity, Magnitude).
  • $L(D|M)$: Kosten für das Kodieren der Instanzen, die nicht durch die gewählten Perturbationen erklärt werden (Outlier).
• Submodularität und Greedy-Algorithmus:
  • Die Autoren beweisen, dass die MDL-Zielfunktion supermodular ist, was bedeutet, dass die Reduktion der Beschreibungslänge eine monotone submodulare Funktion ist.
  • Dies ermöglicht die Anwendung eines effizienten Greedy-Algorithmus mit einer garantierten Approximationsgüte von $(1 - 1/e)$.
  • Zusätzlich wird eine hierarchische Verfeinerung vorgeschlagen, die zuerst auf Subgruppen-Ebene und dann auf Cluster-Ebene selektiert, um die Skalierbarkeit bei großen Datensätzen zu gewährleisten.

3. Schlüsselbeiträge

1. Problemformulierung: Erste formale Definition von kontrafaktischer Erklärbarkeit für Zeitreihen-Clustering auf lokaler und globaler Ebene in einem modellagnostischen Setting.
2. Strukturell eingeschränkte lokale CEs: Einführung einer gradientenbasierten Optimierung, die durch Subgruppen-spezifische Wichtigkeitsmasken gesteuert wird, um spärliche und form-erhaltende Erklärungen zu erzeugen.
3. Globale Zusammenfassung via MDL: Entwicklung eines parameterfreien Auswahlmechanismus basierend auf dem MDL-Prinzip, der den Trade-off zwischen Abdeckung und Komplexität automatisch löst.
4. Theoretische Garantien: Beweis der Submodularität der MDL-Reduktion, was effiziente Greedy-Strategien mit theoretischen Approximationsgrenzen ermöglicht.
5. Adaptive Hierarchische Verfeinerung: Ein Mechanismus, der die Dichte von Cluster-Subgruppen nutzt, um die Anzahl der globalen Erklärungen dynamisch anzupassen.

4. Ergebnisse und Evaluation

Die Evaluation erfolgte auf 30 Datensätzen aus dem UCR Time-Series Archive. GALACTIC wurde mit State-of-the-Art-Baselines verglichen (u.a. $k$-NN, TSEvo, Glacier).

• Lokale Ergebnisse:
  • GALACTIC erreicht eine höhere Effektivität (Success Rate) als Gradienten-basierte Baselines (wie Glacier), während es gleichzeitig signifikant spärlichere Erklärungen liefert (weniger geänderte Segmente und Zeitpunkte).
  • Im Vergleich zu evolutionären Methoden (TSEvo) ist GALACTIC um Größenordnungen schneller.
  • Die „Combined Importance"-Strategie erwies sich als optimaler Kompromiss zwischen Validität und Interpretierbarkeit.
• Globale Ergebnisse:
  • GALACTIC-G (Global) liefert präzisere und kompaktere globale Zusammenfassungen als adaptierte Baselines (GLOBE-CE*, Glacier-G*).
  • Die MDL-basierte Selektion identifiziert Perturbationen, die die Cluster-Struktur besser abbilden und weniger „Rauschen" enthalten.
  • Die hierarchischen Varianten bieten eine hervorragende Skalierbarkeit bei sehr großen Datensätzen, ohne dabei die Qualität der Erklärungen drastisch zu mindern.

5. Bedeutung und Fazit

GALACTIC schließt eine wichtige Lücke in der Explainable AI (XAI) für Zeitreihen. Es ist das erste Framework, das lokale und globale kontrafaktische Erklärungen für unsupervised Clustering vereint.

• Praktische Relevanz: Durch die Bereitstellung von „handlungsorientierten" Einblicken (welche minimalen Änderungen führen zu einem anderen Verhalten?) wird Clustering von einer rein deskriptiven Technik zu einem Entscheidungsunterstützungswerkzeug.
• Theoretischer Fortschritt: Die Anwendung des MDL-Prinzips auf die Auswahl globaler kontrafaktischer Erklärungen bietet einen eleganten Weg, um das Problem der mehrkriteriellen Optimierung ohne manuelle Gewichtung zu lösen.
• Robustheit: Die Methode ist modellagnostisch und funktioniert mit beliebigen Clustering-Algorithmen, solange ein Surrogat-Modell trainiert werden kann.

Zusammenfassend bietet GALACTIC einen theoretisch fundierten, effizienten und interpretierbaren Ansatz, um die „Black Box" des Zeitreihen-Clustering zu öffnen und die Übergänge zwischen Verhaltensmustern verständlich zu machen.