PASS: Skalierbares Clustering mit Unsicherheitsgesteuerten Teilmengen

Ein neues Verfahren namens PASS (Pairwise‑Constraints and Ambiguity‑Driven Subset Selection) verspricht, die klassische und sogar die noch aufkommende Quanten‑Clustering‑Forschung zu revolutionieren. Durch die Kombination von Must‑Link‑ und Cannot‑Link‑Informationen mit einer cleveren Teilmengen‑Auswahl kann PASS große Datensätze effizient in sinnvolle Cluster zerlegen.

Must‑Link‑ und Cannot‑Link‑Constraints geben an, welche Datenpunkte zusammengehören und welche getrennt bleiben sollen. Diese zusätzlichen Regeln erhöhen jedoch die Komplexität des Problems erheblich, sodass herkömmliche Algorithmen bei großen oder hochdimensionalen Daten oft an ihre Grenzen stoßen.

PASS löst dieses Problem, indem es Must‑Link‑Paare in sogenannte Pseudo‑Punkte zusammenfasst und zwei Auswahlmechanismen einsetzt. Der erste, ein margin‑basierter Regelmechanismus, sammelt Punkte nahe der Entscheidungsgrenze sowie alle erkannten Cannot‑Link‑Verletzungen. Der zweite Ansatz nutzt die Fisher‑Rao‑Distanz aus weichen Zuordnungs­posterioren, um die informativeren Punkte zu identifizieren und unter einem einfachen Budget auszuwählen.

In umfangreichen Benchmarks hat PASS gezeigt, dass es vergleichbare Summe‑of‑Squared‑Errors (SSE) erzielt, dabei aber deutlich weniger Rechenaufwand benötigt als exakte oder penalitätsbasierte Methoden. Besonders beeindruckend ist die Robustheit in Szenarien, in denen frühere Ansätze versagen – ein entscheidender Vorteil für spezialisierte Anwendungen wie Quanten‑Hybrid‑Clustering.