Bitte benutzen Sie diese Kennung, um auf die Ressource zu verweisen: http://dx.doi.org/10.18419/opus-10152
Autor(en): Breyer, Marcel
Titel: Ein hoch-performanter (approximierter) k-Nächste-Nachbarn Algorithmus für GPUs
Erscheinungsdatum: 2018
Dokumentart: Abschlussarbeit (Bachelor)
Seiten: 78
URI: http://nbn-resolving.de/urn:nbn:de:bsz:93-opus-ds-101694
http://elib.uni-stuttgart.de/handle/11682/10169
http://dx.doi.org/10.18419/opus-10152
Zusammenfassung: In der heutigen Zeit, in der immer mehr Daten zur Verfügung stehen, gewinnt das Data-Mining zunehmendan Bedeutung. Insbesondere ist die Klassifizierung eine zentrale Methode des Data-Minings. Eine Möglichkeit Daten zu klassifizieren, stellt die Nächste-Nachbarn-Klassifikation dar. Dabei wird einem Objekt eine Klasse nur aufgrund dessen lokaler Nachbarschaft zugewiesen. Der naive Ansatz zur Lösung der Nächste-Nachbarn-Klassifikation setzt jedoch voraus, dass alle anderen Objekte in der Datenmenge betrachtet werden müssen, wodurch er eine quadratische Komplexität besitzt, was bei deren stetig wachsender Größe immer ineffizienter wird. Aufgrund dieser hohen Kosten, sind bei großen Datenmengen approximierende Verfahren attraktiv. Ein solches approximierendes Verfahren ist das in dieser Arbeit verwendete Locality Sensitive Hashing. Dieses Verfahren teilt alle Datenpunkte basierend auf deren Lokalisation durch spezielle Hash-Funktionen in Hash-Buckets auf. Mithilfe dieser Aufteilung müssen bei der Suche nach den Nächsten-Nachbarn nicht mehr alle Datenpunkte betrachtet werden. Zusätzlich zur Wahl des Algorithmus, muss jedoch auch auf eine hochperformante Implementierung für Grafikkarten geachtet werden. Dabei konnte auf NVIDIAs QUADRO GP100 Grafikkarte eine Laufzeitverbesserung um das bis zu 10-fache bei einer gleichzeitigen Genauigkeit von über 90%, gegenüber einer ebenfalls für Grafikkarten optimierten Implementierung des Naiven Algorithmus, für einen Datensatz mit 500 000 Datenpunkten in 10 Dimensionen beobachtet werden.
Enthalten in den Sammlungen:05 Fakultät Informatik, Elektrotechnik und Informationstechnik

Dateien zu dieser Ressource:
Datei Beschreibung GrößeFormat 
Bachelor_Arbeit_Marcel_Breyer.pdf1,25 MBAdobe PDFÖffnen/Anzeigen


Alle Ressourcen in diesem Repositorium sind urheberrechtlich geschützt.