|
|
|
|
BIRCH ist ein hierarchisches, lokales Clusteringverfahren, welches durch geschickte Reduzierung des Datenvolumens für niedrigdimensionale Daten sehr effizient arbeitet, bei hochdimensionalen Daten jedoch die bekannten Probleme aufweist. Es baut intern einen sog. CF-Tree auf, der die Cluster sehr platzsparend speichert; die Blätter dieses Baumes werden mit einem beliebigen globalen Algorithmus geclustert.
OPTICS ordnet Datenpunkte so an, daß im Raum nahe beieinander liegende Punkte auch in ihrer Reihenfolge möglichst nahe sind. Es liefert zwar keine explizite Clusterbeschreibung, umgeht aber dafür die Probleme, die bei verschieden dichten Clustern auftreten und funktioniert auch für hochdimensionale Daten.
Es soll nun untersucht werden, inwieweit sich OPTICS als Clusterverfahren in Birch einsetzen läßt, und wie die speziellen Eigenschaften des CF-Trees optimal ausgenützt werden können. In Experimenten soll die Eignung des Verfahrens sowohl in Bezug auf Geschwindigkeit als auch Qualität der erkannten Cluster getestet werden.
Weiterhin wird ein zellenbasierter Ansatz verfolgt: der Raum wird in ein Gitter eingeteilt, und diese Gitterzellen werden, geeignet gewichtet mit der Anzahl der darin liegenden Datenpunkte, in OPTICS eingespeist, um den Aspekt der Datenkompression mit der Kompression durch BIRCH zu vergleichen.
BIRCH (sowie der Zellengenerator) wird über Zwischendateien an OPTICS gekoppelt, wobei zunächst die CF-Daten nur durch einzelne Punkte approximiert werden. Im zweiten Schritt wird untersucht, ob OPTICS entsprechend erweitert werden kann, um die CF optimaler verwenden zu können.
Durch die Datenreduzierung von BIRCH kann die Performanz des OPTICS-Algorithmus evl. wesentlich verbessert werden. Andererseits kann BIRCH evtl. auch im Hochdimensionalen besser verwendet werden, wenn es mit OPTICS kombiniert wird.
| Bearbeiter | Ekkehard Krämer |
| Betreuer | Markus Breunig |
| Arbeitsabschnitt | Zeitbedarf |
BIRCH zum Laufen bringen
|
9,5 |
OPTICS in BIRCH integrieren
|
18 |
| Zellenbasierten Ansatz für BIRCH-Eingabedaten entwickeln und testen, wieder in Zusammenhang mit OPTICS | 8 |
| Zellenbasierter Ansatz im Hochdimensionalen | 4 |
Es wurde ein System erstellt, mit man sehr schnell Eingabedaten erzeugen und durch verschiedene Variationen von BIRCH/OPTICS laufen lassen sowie die Ergebnisse auf diverse Weisen visualisieren kann.
Durch die Komprimierung der Eingabedaten mittels BIRCH läßt sich die Laufzeit von OPTICS beeindruckend reduzieren. Dies erkauft man sich mit einer etwas weniger intuitiv erkennbaren, aber aufgrund einiger Erweiterungen des OPTICS-Algorithmus in vielen Fällen durchaus brauchbaren Cluster-Struktur im OPTICS-Reachability-Plot. Im momentanen Status verschliessen sich die Plots aber der automatisierten Weiterverarbeitung in Cluster-Erkennungs-Algorithmen, wenn man nicht auf zu viele Informationen verzichten kann bzw. will.
Der zellenbasierte Ansatz hat sich im Vergleich mit BIRCH als
nicht lohnenswert herausgestellt: wo BIRCH seine Clustering
Features sehr flexibel positionieren kann (z.B. entspricht der
CF eines Rausch-Punktes exakt dem ursprünglichen Punkt), ist
dies beim Rastern nicht möglich; die Rasterung verbraucht
besonders bei mehr als 2 Dimensionen bei weitem mehr
Speicherplatz für annähernd vergleichbare Ergebnisse und hat
keine erkennbaren Vorteile gegenüber BIRCH (abgesehen von der
wesentlich leichteren Implementierung).
DBS
Institut
LMU