Projektarbeit:Hochrechnung eines gesampelten OPTICS-Clustering

Projektarbeit

Hochrechnung eines gesampelten OPTICTS-Clustering auf die Gesamtmenge

Inhalt

OPTICS benötigt auf hochdimensional Eingabedaten quadratische Rechenzeit, was bei großen, hochdimensional Datenmengen zu erheblichen Laufzeiten führt. Daher soll mittels eines vorgeschaltetem Sampling die Größe der Eingabedaten verringert werden. Um dabei den Informationsverlust zu minimieren, wird das Ergebnis von OPTICS, angewandt auf den Sample, auf die Gesamtdatenmenge hochgerechnet.

Problemstellung

OPTICS ist ein dichte-basiertes hierarchisches Clustering-Verfahren. Sein Ergebnis - eine Clustering-Ordnung - lässt sich auch noch bei sehr grossen Datenmengen übersichtlich und verständlich darstellen. Wegen des erheblichen Rechenaufwandes ist eine interaktive Anwendung von OPTICS auf relativ kleine Datenmengen beschränkt. Ziel ist es, auch auf großen Datenmengen die Laufzeit zu verbessern, und dafür ein ungenaueres Ergebnis in Kauf zu nehmen.
Dieser Ansatz nutzt die guten Eigenschaften von OPTICS bei relativ kleinen Datenmengen. Durch ein vorgeschaltetes Sampling soll die Eingabedatenmenge deutlich reduziert werden. Das Ergebnis, das OPTICS von diesem Sample liefert, soll mit Hilfe verschiedener Klassifikationsverfahren auf die gesamte Datenmenge hochgerechnet werden. Die Klassifikation soll graphisch in das Errreichbarkeitsdiagramm des Samples integriert werden.

Lösungsansatz

Die Datenmenge wird auf verschiedene Arten gesampelt und OPTICS darauf angewendet. Der Rest der Daten wird mit einem Klassifikationsverfahren dem Ergebnis zugeordnet. Mehrere Verfahren sollen hier getestet werden: nn-Klassifikation, nächster core-Punkt, kleinste Reachability im Range, maximum likelyhood, evtl. LTUs.
Im Erreichbarkeitsdiagramm soll dann für jedes gesampeltes Objekt nicht nur die Erreichbarkeitsdistanz sondern auch die Anzahl der ihm durch die Klassifikation zugeordneten Objekte angezeigt werden.

Ziel

Verbesserung des Laufzeitverhaltens von OPTICS: Entwicklung eines Verfahrens, die die sinnvoll und interaktive Anwendung von OPTICS auch auf große Datenmengen erlaubt.

Tools

OPTICS-Algorithmus, Java, Gnuplot

Personen

Bearbeiter	Peer Kröger
Betreuer	Markus Breunig

Arbeitsplan

Arbeitsabschnitt	Zeitbedarf
Einarbeitung	10 Tage
Implementierung	20 Tage
Test/Bewertung	20 Tage

Ergebnis

Das Verfahren wurde in Java implementiert und getestet. Es wurde nur die nn-Klassifikation verwendet. Dabei wurde ein enormer Speed-Up gegenüber dem herkömmlichen OPTICS erzielt. Auch relativ komplizierte Strukturen konnten bei kleinen Sample-Größen (z.B. 100 Punkten) bereits im Reachability-Plot des Samples erkannt werden. Die Klassifikation ist dennoch als Nachbereitung sinnvoll, da es sein kann, dass es im Sample-Plot zu Stauchungen und/oder Streckungen der Cluster kommen kann (was am Sampling selber liegt, da es vorkommen kann, dass aus einem Cluster mehrere Punkte dem Anteil entsprechend ausgewählt werden, als bei einem anderen). Ausserdem sind die Punkte, die nicht ins Sample gewählt wurden, keinem Cluster zuordbar. Diesen Informationsverlust kann die Klassifikation ausmerzen. Durch das Ausgleichen der Stauchungen und/oder Streckungen des Sample-Plots kann man anhand des Klassifikations-Plots auf die tatsächliche Größe der Cluster schließen. Auch kann jeder Punkt aus der ursprünglichen Menge einem Cluster zugeordnet werden.

Die Graphik rechts zeigt eines der Ergebnisse mit einem zwei dimensionalen Datensatz bestehend aus 100 000 Punkten. Der Sample-Plot (mitte) zeigt im Vergleich zum original OPTICS-Plot (oben) deutlich Stauchungen und Streckungen (z.B. zweiter und letzter Cluster), die im Plot nach der Klassifikation (unten) wieder ausgeglichen sind.

Das Verfahren ist besonders bei großen Datensätzen, die eine deutliche Cluster-Struktur aufweisen, geeignet, um die Laufzeit der Analyse auf ein erträgliches Maß zu verringern. Dagegen wurden schlechte Ergebnisse bei Real-Datensätzen mit sehr wenig Struktur verbucht. Extrem kleine Cluster gehen in kleinen Sample-Mengen evtl. verloren.

Reachability-Plots eines 2 dim Datensatzes: Oben: Original OPTICS. Mitte: OPTICS auf einem Sample mit 200 Punkten. Unten: nach der Klassifikation

Homepages: DBS Institut LMU
10.11.1999, Peer Kröger