Institut für Informatik, LFE Datenbanksysteme
Prof. Dr. Hans-Peter Kriegel
Institute for Computer Science
Database and Information Systems
|
Ludwig-Maximilians-Universität
München
Institut für Informatik, LFE Datenbanksysteme Prof. Dr. Hans-Peter Kriegel |
University of
Munich
Institute for Computer Science Database and Information Systems |
Projektarbeit
Partielle Ähnlichkeitssuche
in hochdimensionalen Daten
Beschreibung
Untersuchung haben ergeben, dass sich der Nächste-Nachbar im hochdimensionalen
"seltsam" verhält. Siehe unter anderem:
Beyer, Goldstein, Ramakkrishnan & Shaft: When is "Nearest Neighbor"
Meaningful und
Hinneburg, Aggarwal, Keim: What is th nearest neighbor in high dimensional
spaces?
In vielen Fällen nähert sich mit steigender Dimension die
Entfernung eines Datenpunkts zu seinem nächsten Nachbarn bzw. seinem
entferntersten Nachbarn an.
Um diesem Problem zu begegenen kann man versuchen die Dimensionalität
der Daten zu reduzieren. Welche Auswirkungen das haben kann, beschreibt
unter anderen:
Aggarwal: On the Effects of Dimensionality Reduction on High Dimensional
Similarity Search.
Ein weitere Ansatz für hochdimensionale Daten, der zum Beispiel im Data Mining unter dem Stichwort Subspace Clustering bekannt ist, ist die Suche in niedrigdimensionaleren Projektionen der Daten (sogenannten Subspaces). Bei der Nächste-Nachbarn-Suche könnte das bedeuten, das für die Berechnung der Ähnlichkeit zwischen zwei Objekten nur eine Teilmenge der Attribute herangezogen wird.
Im Rahmen dieser Projektarbeit soll das Phänomen des nächsten Nachbarn im hochdimensionalen empirisch evaluiert werden. Neben der Nächsten-Nachbarn-Suche im Volldimensionalen, soll auch ein Ansatz zur Nächsten-Nachbarn-Suche in Attributteilmengen implementiert werden.
Programmierkenntnisse in Java
Bearbeiter:
Sandra Bauer, Christoph Kretner
Ansprechpartner:
Karin Kailing, Zi. E 1.06, Tel. 2180-9325, email: kailing@dbs.informatik.uni-muenchen.de
DBSInstitutLMU