Neue Methode liefert nahezu optimale lineare Clusterung ohne Trennbarkeit

Lineare Predictive Clustering (LPC) teilt Datenpunkte anhand gemeinsamer linearer Beziehungen zwischen Merkmalen und Zielvariablen. Diese Technik findet breite Anwendung in Bereichen wie Marketing, Medizin und Bildung, wo die Identifikation von Mustern in komplexen Datensätzen entscheidend ist.

Traditionell werden LPC‑Modelle mit gierigen Optimierungsverfahren erstellt, die abwechselnd Cluster bilden und lineare Regressionen durchführen. Diese Verfahren erreichen zwar gute Ergebnisse bei klar separablen Clustern, verlieren jedoch an Genauigkeit, wenn Cluster im Merkmalsraum überlappen. Eine alternative, globale Optimierungsmethode – ein Mixed-Integer-Programm (MIP) – garantiert optimale Lösungen, leidet jedoch unter schlechter Skalierbarkeit.

Die vorliegende Arbeit baut auf diesem MIP‑Paradigma auf und präsentiert zwei neue Ansätze, die die Effizienz der globalen Optimierung deutlich steigern. Durch die Nutzung theoretischer Eigenschaften der Trennbarkeit werden nahezu optimale Approximationen mit nachweisbaren Fehlergrenzen erzeugt, wodurch die Komplexität des MIP reduziert und die Skalierbarkeit verbessert wird. Zusätzlich wird LPC als Quadratic Pseudo-Boolean Optimization (QPBO) formuliert, was in bestimmten Szenarien erhebliche Rechenzeitersparnisse ermöglicht.

Vergleichende Tests an synthetischen und realen Datensätzen zeigen, dass die neuen Methoden konsequent nahezu optimale Lösungen liefern, die Regressionsfehler deutlich senken und gleichzeitig die Skalierbarkeit gegenüber bestehenden MIP‑Formulierungen übertreffen. Diese Fortschritte eröffnen neue Möglichkeiten für die Anwendung von LPC in großen, nicht separablen Datensätzen.