Dünne Unterraum-Clustering: Algorithmus, Theorie und Anwendungen

In vielen praktischen Problemen arbeiten wir mit Sammlungen hochdimensionaler Daten, wie zum Beispiel Bildern, Videos, Texten und Webdokumenten, DNA-Mikroarrays und anderen. Häufig liegen diese hochdimensionalen Daten nahe an niedrigdimensionalen Strukturen, die den verschiedenen Klassen oder Kategorien entsprechen, zu denen die Daten gehören. In dieser Arbeit schlagen und untersuchen wir einen Algorithmus vor, der als Sparse Subspace Clustering (SSC) bezeichnet wird, um Datenpunkte zu clustern, die in einer Vereinigung niedrigdimensionaler Unterräume liegen. Das zentrale Konzept ist, dass unter den unendlich vielen möglichen Darstellungen eines Datenpunktes in Bezug auf andere Punkte eine dünnbesetzte Darstellung dem Auswählen weniger Punkte aus demselben Unterraum entspricht. Dies motiviert das Lösen eines dünnbesetzten Optimierungsprogramms, dessen Lösung in einem spektralen Clusterverfahren verwendet wird, um die Zuordnung der Daten zu den Unterräumen zu bestimmen. Da das Lösen des dünnbesetzten Optimierungsprogramms im Allgemeinen NP-schwer ist, betrachten wir eine konvexe Relaxierung und zeigen, dass unter geeigneten Bedingungen zur Anordnung der Unterräume und zur Verteilung der Daten das vorgeschlagene Minimierungsprogramm erfolgreich die gewünschten dünnbesetzten Darstellungen wiederherstellt. Der vorgeschlagene Algorithmus kann effizient gelöst werden und kann auch mit Datenpunkten umgehen, die in der Nähe von Schnittstellen von Unterräumen liegen. Ein weiterer wesentlicher Vorteil des vorgeschlagenen Algorithmus gegenüber dem Stand der Technik besteht darin, dass er direkt mit Störungen in den Daten umgehen kann, wie zum Beispiel Rauschen, dünnbesetzte Ausreißer und fehlende Einträge, indem das Modell der Daten in das dünnbesetzte Optimierungsprogramm einbezogen wird. Wir demonstrieren die Effektivität des vorgeschlagenen Algorithmus durch Experimente sowohl mit synthetischen Daten als auch mit zwei realen Problemen: Bewegungssegmentierung und Gesichtserkennung.