Efficient clustering of massive data with MapReduce

• Effizientes Clustering großer Datensätze mit MapReduce

Fries, Sergej; Seidl, Thomas (Thesis advisor); Rahm, Erhard (Thesis advisor)

Aachen : Publikationsserver der RWTH Aachen University (2015)
Doktorarbeit

Aachen, Techn. Hochsch., Diss., 2014

Kurzfassung

Nach der Epoche der Agrargesellschaft und dem Industriezeitalter befindet sich die Menschheit seit einigen Jahrzehnten im Informationszeitalter. Die Information oder was viel wichtiger ist das Wissen wurde zur kostbarsten Ressource. Die bisherigen Ansätze zur Generierung des Wissens ist die Analyse von Beobachtungen oder anderen Rohdaten. Und mit wachsender Vernetzung der Daten wächst auch der Anteil des Wissens, das daraus extrahiert wird. Aus diesem Grund war der Trend des letzten Jahrzehnts die Sammlung aller mölglichen Informationen in allen Bereichen unseres Lebens, sei es in der Industrie, der Wissenschaft oder allgemein der Gesellschaft. Die technologische Entwicklung der Speichermedien und der Sensortechnologien führten zum immer größer werdenden Zuwachs an Daten. So wurde von Peter Hirshberg (global pulse summit) vorhergesagt, dass allein im Jahr 2011 mehr Daten generiert würden als während der gesamten Geschichte der Menschheit vorher. Die Wichtigkeit der Wissensextraktion führte zur Entwicklung des Wissensextraktionsprozesses in Datenbanken (Knowledge Discovery process in Databases) im Jahre 1996. Der KDD-Prozess beschreibt einen Workflow von rohen Daten, über ihre Vorverarbeitung, Analyse bis zur endgültigen Visualisierung für weitere Interpretationen. In den letzten Jahrzehnten dominierte bei der Wissensextraktion das modellgeleitete Vorgehen. D. h., die gesammelten Daten wurden zur Annahme oder zur Ablehnung eines von einem menschlichen Experten erstellten Modells verwendet. Somit hing die Vorhersagegenauigkeit des Modells sehr stark von der Expertise der Spezialisten ab. Sogar gute Modelle berücksichtigen unter Umständen nicht alle Aspekte des gegebenen Problems. In den letzten Jahren rückten datengeleitete Ansätze zur Wissensextraktion mehr in den Vordergrund. Die Idee dabei ist, die Daten "für sich sprechen zu lassen", d.h. die Modelle direkt aus den Daten zu generieren und diese erst danach zu validieren. Da die Modelle im Vorhinein nicht bekannt sind, ist das Hauptziel, unbekannte Muster in den Daten zu finden. Im KDD Prozess wird diese Aufgabe von sogenannten Clusteranalyse-Techniken des Data Minings gelöst. Die Verfahren der Clusteranalyse haben jedoch oft eine hohe Rechenkomplexität, so dass effiziente Methoden zur Analyse von großen Datenmengen unabdingbar sind. Ein weit verbreiteter Weg dazu ist die Parallelisierung von Algorithmen, die dann auf Multi-Core Computern oder auf Clustern ausgeführt werden können. Der Autor dieser Arbeit verfolgt den gleichen Lösungsweg und stellt neue Techniken zur Analyse von großen Datenmengen im MapReduce-Framework vor. MapReduce ist ein Parallelisierungsframework für datenintensive Anwendungen, das im Jahre 2004 von Google vorgestellt wurde. Seitdem entwickelte sich MapReduce zu einer der wichtigsten Technologien zur Verarbeitung von datenintensiven Aufgaben. Den Schwerpunkt dieser Arbeit stellen zwei Klassen der Clusteranalyse dar, die dichtebasierten und Projected Clustering Verfahren. Dabei werden für jeweils einen Kandidaten aus jeder Klasse - und zwar den DBSCAN- und den P3C-Algorithmus - effiziente Verfahren vorgestellt und evaluiert. Als Teil der dichtebasierten Verfahren wurden in dieser Arbeit des Weiteren effiziente Techniken zum Selbstähnlichkeits-Join in Vektorräumen und ein Verfahren zur Bestimmung der Zusammenhangskomponenten in Graphen vorgestellt.

Einrichtungen

• Lehrstuhl für Informatik 9 (Process and Data Science) [122510]
• Fachgruppe Informatik [120000]