Direkt zu


Informationen für Studierende

zur Startseite

Projekt-INF

Evaluation von Sampling-Verfahren auf verteilten Analyseumgebungen
Projekt Interactive Rapid Analytic Concepts
Betreuer M.Sc. Manuel Fritz
Prüfer PD Dr. rer. nat. habil. Holger Schwarz
Ende29.09.2018
Beschreibung

Ausgangssituation/Motivation

In Zeiten von Industrie 4.0, Internet of Things (IoT) und Big Data ist ein stetiger Zuwachs verfügbarer Daten zu beobachten. Um aus diesen Daten Wissen zu generieren, werden Data-Mining-Methoden angewandt, wie z.B. Klassifikation, Regression, Clustering oder Assoziationsregelanalyse. Teilweise sind diese Algorithmen durch ein hohes Laufzeitverhalten geprägt, wie z.B. O(n2) für eine naive Implementierung des DBSCAN-Algorithmus für das Clustering [1]. Es ist folglich mit langen Laufzeiten zu rechnen, wenn große Datenmengen von komplexen Algorithmen verarbeitet werden. Ferner ist darauf zu achten, dass Data Mining als ein iterativer und explorativer Prozess verstanden wird, bei dem ggf. Algorithmen und Parameter schrittweise angepasst werden, um belastbare Ergebnisse zu erzielen. Gerade unerfahrene Analysten durchlaufen folglich mehrere solcher Iterationen, wobei jeweils mit einer langen Laufzeit zu rechnen ist, bis das Ergebnis den gewünschten Anforderungen entspricht.

Ziele

Das Ziel dieser Arbeit besteht darin, den Einfluss diverser Sampling-Verfahren auf die Qualität der Data-Mining-Algorithmen genauer zu untersuchen. Sampling adressiert das Ziehen einer Teilmenge der Gesamtdaten, welche jedoch die Gesamtmenge möglichst genau repräsentiert [2, 3]. Da jedoch nur eine Teilmenge zur weiteren Analyse verwendet wird, ist mit einer verkürzten Ausführungszeit für die jeweiligen Data-Mining-Algorithmen zu rechnen.

In dieser Arbeit sollen mehrere Sampling-Verfahren umgesetzt werden, indem diese von bereits existierenden Bibliotheken herangezogen oder von Grund auf neu implementiert werden. Anschließend werden die erhaltenen Samples mit Apache Spark [4] analysiert. Dabei ist sowohl die Ausführungszeit als auch die Qualität des Endergebnisses im Vergleich zur Ausführung auf dem gesamten Datensatz zu evaluieren. Da das Ziehen eines Samples ggf. längere Laufzeiten mit sich bringt, sollen diese entsprechend festgehalten werden. Ausgewählte Sampling-Strategien sollen auf Apache Spark umgesetzt werden, um einen realen Einblick in das Laufzeitverhalten von diesen Strategien auf verteilten Systemen zu erhalten. Für die Evaluation soll ein erweiterbares Rahmenwerk entwickelt werden, welches es erlaubt, Sampling-Strategien oder weitere Ausführungsumgebungen, wie z. B. Apache Mahout [5] möglichst leicht hinzuzufügen und anschließend zu evaluieren.

Die Arbeit umfasst dazu folgende Aufgaben:

  • Literaturrecherche zu geeigneten Sampling-Verfahren
  • Aufbau eines anpassbaren Rahmenwerkes für Qualitäts- und Zeitmessungen
  • Umsetzung diverser Sampling-Strategien
  • Evaluation der Qualitäts- und Zeitunterschiede auf Spark
  • Zusammenfassung und Präsentation der Ergebnisse anhand eines Posters
  • Präsentation der Ergebnisse in einem Vortrag

Literatur

[1] M. Ester, H.P. Kriegel, J. Sander, X. Xu, A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise, 2nd International Conference on Knowledge Discovery and Data Mining pp. 226–231 (1996)
[2] S.K. Thompson, Sampling. Wiley series in probability and mathematical statistics : applied probability and statistics section (Wiley, New York [u.a.], 1992)
[3] Y. Tillé, Sampling Algorithms. Springer Series in Statistics (Springer New York, 2006). DOI 10.1214/009053606000000524. URL http://link.springer.com/10.1007/0-387-34240-0
[4] The Apache Software Foundation. Apache SparkTM - Lightning-Fast Cluster Computing. URL https://spark.apache.org/
[5] The Apache Software Foundation. Apache Mahout. URL https://mahout.apache.org/