4S: Skalierbares Subraum-Suchschema zur Überwindung der traditionellen Apriori-Verarbeitung
- Autor:
-
Quelle:
Tagungsband der IEEE International Conference on Big Data (BigData 2013), Santa Clara, CA, USA
-
In vielen realen Anwendungen werden Daten in mehrdimensionalen Räumen gesammelt. Allerdings sind nicht alle Dimensionen für die Datenanalyse relevant. Stattdessen ist interessantes Wissen in korrelierten Teilmengen von Dimensionen (d. h. Teilräumen des ursprünglichen Raums) verborgen. Die Erkennung dieser korrelierten Unterräume unabhängig von der zugrunde liegenden Bergbauaufgabe ist ein offenes Forschungsproblem. Aufgrund des exponentiellen Suchraums ist dies eine Herausforderung. Bestehende Methoden haben versucht, dieses Problem durch den Einsatz von Apriori-Suchschemata anzugehen. Allerdings weisen sie eine schlechte Skalierbarkeit auf und es fehlen qualitativ hochwertige Unterräume. In diesem Artikel wird ein skalierbares Unterraumsuchschema (4S) vorgestellt, das das Effizienzproblem überwindet, indem es von der traditionellen stufenweisen Suche abweicht. Wir schlagen einen neuen verallgemeinerten Begriff korrelierter Unterräume vor, der den Weg für die Transformation des Suchraums in einen Korrelationsgraphen von Dimensionen freigibt. Dann führen wir ein direktes Mining korrelierter Unterräume im Diagramm durch. Schließlich führen wir Unterräume nach dem MDL-Prinzip zusammen und erhalten hochdimensionale Unterräume mit minimaler Redundanz. Wir zeigen theoretisch, dass unser Suchschema allgemeiner ist als bestehende Suchschemata und eine deutlich geringere Laufzeitkomplexität aufweist. Unsere Experimente zeigen, dass 4S nahezu linear mit der Datenbankgröße und -dimensionalität skaliert und Unterräume mit höherer Qualität erzeugt als modernste Methoden.