Data Mining - uni-leipzig.de · 2018-11-01 · Data Mining 1-8 WS 2018/19 Hintergrund • „Welt der Datenbanken“: Data Mining bezieht sich auf die Anwendung effizienter Algorithmen

1-1Data Mining WS 2018/19

Data Mining

Kapitel 1: Einführung

Johannes Zschache

Wintersemester 2018/19

Abteilung Datenbanken, Universität Leipzig

http://dbs.uni-leipzig.de


Inhaltsverzeichnis

• Organisation

• Data Mining

• Übersicht zur Vorlesung

• Wiederholung: Hashfunktionen

• Large-Scale Data Processing

– Verteilte Dateisysteme

– MapReduce

– Algorithmen mit MapReduce

– Workflow-System: Spark

– Kommunikationskosten

– Komplexitätstheorie für MapReduce


Organisation

• Vorlesungstermine

– Donnerstags, 9:15-10:45 Uhr, HS 20

– 18.10.2018 – 7.2.2019 (6.12, 27.12. & 3.1. entfallen)

• Anmeldung: AlmaWeb

• Webseite mit Folien: https://dbs.uni-leipzig.de/de/study/2018ws/dm

• Prüfung: Klausur am Ende des Semesters

• Inhalt: „Mining of Massive Datasets“ von J. Leskovec, A. Rajaraman

und J. Ullman, Stanford University

• Buchkapitel, Originalfolien und Videos online:

http://www.mmds.org/

https://dbs.uni-leipzig.de/de/study/2018ws/dm



Lehrveranstaltungen WS 2018/19

• Lehrveranstaltungen: https://dbs.uni-leipzig.de/de/stud

– Datenbanksysteme 1 (DBS1)

– Implementierung von Datenbanksystemen (1 + 2)

– Data Mining

– Praktikum: Data Warehousing

– Seminar: Secure Data Processing

– Bachelor-/Masterseminar (Vortrag über laufende Bachelor-/Masterarbeit)

• Verwendung der Data-Mining-Vorlesung:

– Bachelor-Modul „Realisierung von Informationssystemen“ (5LP, zwei Vorlesungen)

– Master-Modul „Moderne Datenbanktechnologien”

• (kleines) Kernmodul (5LP, zwei Vorlesungen)

• (großes) Vertiefungsmodul (10LP, zwei Vorlesungen + Praktikum/Seminar)

• “Moderne Datenbanktechnologien” (großes Modul) ist Pflichtmodul für den

Masterschwerpunkt “Big Data”

https://dbs.uni-leipzig.de/de/stud


Inhaltsverzeichnis

• Organisation

• Data Mining





– MapReduce






Data Mining

• Zur Gewinnung des Wissens müssen die Daten gespeichert,

verarbeitet und analysiert werden

• Data Mining = Extraktion von umsetzbaren Informationen aus

(meist) sehr großen Datensätzen

• Ergebnis einer Anfrage = Modell (auch: Muster)

– Deskriptiv: für Menschen verständliche Zusammenfassung

– Prädiktiv: Vorhersage unbekannter Werte aus bekannten Werten

– Statistisch: Schätzwerte der Parameter

Data Mining =? Big Data =? Data Science =? Maschinelles Lernen

– Unterschiedliche Verwendung

– Abgrenzung schwierig


Hintergrund

• „Welt der Datenbanken“: Data Mining bezieht sich auf die Anwendung effizienter Algorithmen zur Erkennung von Mustern in großen Datenmengen

• „Welt der Statistik/des Maschinellen Lernens“: Data Mining bedeutet Inferenz eines Modells

• Generell: Unterscheidung zwischen Algorithmus und Inferenz, z.B.

– Berechnung eines Mittelwerts ist Algorithmus: ҧ𝑥 =1

𝑛σ𝑖=1𝑛 𝑥𝑖

– Inferenz ermöglich eine Bewertung des Ergebnisses

• Schwerpunkt dieser Vorlesung: skalierbare Algorithmen– Parallelisierung oft notwendig bei

Datenmengen/Berechnungen, die nicht in den Hauptspeicher eines Rechners passen

– Verteilte Verarbeitung über z.B. MapReduceoder Datenströme

Datenbank

Theorie,

Algorithmen

Maschinelles

Lernen

Data

Mining


Inhaltsverzeichnis

• Organisation

• Data Mining





– MapReduce






Abgrenzung zu anderen Vorlesungen

• Schwerpunkt dieser Vorlesung: skalierbare Algorithmen

• Data Mining ist letztes Kapitel der Vorlesung „Data Warehousing“

• Cloud Data Management: Ausführliche Behandlung von Technologien für

Large-Scale Computing

• Keine Datenbanken (Mehrrechner-Datenbanken, NoSQL, Data Warehousing)

• Kein Maschinelles Lernen/Inferenz (Statistisches Lernen)

• Betonung auf Algorithmen: Fortsetzung der Vorlesungen zu „Algorithmen

und Datenstrukturen“

• Fokus auf das Gebiet der Datenanalyse


Lernziele

• Kenntnis verschiedener Algorithmenklassen zur Analyse von Daten

– Nachvollziehen der Funktionsweise der Algorithmen

– Anwendung der Algorithmen an kleinen Beispieldaten

• Komplexität der Algorithmen bewerten und Engpässe erkennen

– Beurteilung der Anwendbarkeit von Algorithmen

– Vergleich verschiedener Algorithmen hinsichtlich ihrer Komplexität

• Zukünftig (nicht Ziel der Vorlesung):

– Implementierung der Algorithmen (z.B. Big Data Praktikum, Abschlussarbeit)

– Eigene Verbesserungen existierender Algorithmen

– Entwurf effizienter Verfahren zur Datenanalyse


Übersicht

Hoch-dimension.

Daten

Locality sensitive hashing

Clustering

Dimension.reduction

Graph-daten

PageRank, SimRank

Network Analysis

Spam Detection

UnbegrenzteDaten

Filtering data

streams

Web advertising

Queries on streams

MaschinellesLernen

Support Vector

Machines

Decision Trees

Nearest Neighbors

Anwendung

Recommen.Systems

Association Rules

Duplicate document detection


Kapitel

1. Einführung

2. Finding Similar Items

3. Mining Data Streams

4. Link Analysis

5. Frequent Itemsets

6. Clustering

7. Advertising on the Web

8. Recommendation Systems

9. Mining Social-Network Graphs

10. Dimensionality Reduction

11. Large-Scale Machine Learning


Inhaltsverzeichnis

• Organisation

• Data Mining





– MapReduce






Hashfunktion

• „Bucket“-Anzahl 𝐵 ∈ ℕ

• Hashfunktion ℎ: Objekt → 0,… , 𝐵 − 1

• Randomisierend:

– Gleichmäßige Aufteilung der Objekte über die Buckets

– 𝐵 ist kleiner als die Menge aller Objekte

• Beispiele

– N modulo p, wobei p eine Primzahl und N eine natürliche Zahl

– Zeichenketten: Summe über deren ASCII/Unicode-Repräsentation

– Tupel: Summe über Hash-Werte der Elemente

Objekt 1 1ℎ

Objekt 2 5ℎ

Objekt 3 2ℎ


Index

• Effiziente Suche eines Eintrags über Attribut

• Beispiel: Hashtabelle

• Je größer B, desto effizienter die Suche


Inhaltsverzeichnis

• Organisation

• Data Mining





– MapReduce






Rechencluster

• Single-Node-Architektur ist begrenzt bzgl. Speicher und Rechenzeit

• Cluster-Architektur:

Mem

Disk

CPU

Mem

Disk

CPU

…

Switch

Jedes Rack besteht aus 16-64 Rechenknoten

Mem

Disk

CPU

Mem

Disk

CPU

…

Switch

Switch

Mehrere Gbps Backbone zwischen den Racks


Large-Scale Computing

• Large-Scale Data Mining auf Standardhardware

• Herausforderungen:

– Wie können die Berechnungen möglichst einfach verteilt werden?

– Wie kann der Ausfall einzelner Rechner abgefangen werden?

• Ein Rechner kann 3 Jahre (1000 Tage) ohne Unterbrechung laufen

• Bei 1.000 Rechnern fällt 1 pro Tag aus

• Bei 1M Rechnern versagen täglich 1000 Maschinen!

• Problem: Das Kopieren von Daten über ein Netzwerk braucht Zeit

• Idee:

– Bringe die Berechnungen zu den Daten

– Repliziertes Speichern der Daten für erhöhte Zuverlässigkeit

• Hadoop adressiert diese Probleme/Herausforderungen

– Verteiltes Dateisystem: HDFS

– Programmiermodelle: MapReduce, Spark


Inhaltsverzeichnis

• Organisation

• Data Mining





– MapReduce






Verteiltes Dateisystem

• Stellt globalen Namespace bereit

• Typisches Nutzung:

– Riesige Dateien (100 GB bis einige TB)

– Daten werden selten direkt aktualisiert

– Lesen und Anhängen sind üblich

• Chunk-Server

– Eine Datei wird in zusammenhängende Teile (Chunks, 16-64 MB) aufgeteilt

– Jeder Chunk wird repliziert (2-3x) auf verschiedenen Rechnern/Racks gespeichert

• Master/Name-Server

– Speichert Metadaten darüber, wo Dateien gespeichert sind

– Sollte auch repliziert werden

• Client-Bibliothek für den Dateizugriff

– Kommunikation mit Master um Chunk-Server zu finden

– Stellt eine direkte Verbindung zu Chunk-Servern her, um auf Daten zuzugreifen

C0 C1

C2C5

Chunk server 1

D1

C5

Chunk server 3

C1

C3C5

Chunk server 2

C2

D0

D0

C0 C5

Chunk server 4

C2D0


Inhaltsverzeichnis

• Organisation

• Data Mining





– MapReduce






MapReduce

• MapReduce ist ein Programmiermodell für:

– Einfache parallele Verarbeitung

– Unsichtbare Verwaltung von Hard- und Softwarefehlern

• Implementierungen: Google, Hadoop, Spark, Flink

• 3 Schritte

1. Map:

• Anwendung einer benutzerdefinierten Funktion auf jedes Eingabeelement (aus Chunk)

• Die Ausgabe der Map-Funktion ist eine Menge von Schlüssel-Wert-Paaren

2. Gruppieren nach Schlüssel: Das System sortiert alle Schlüssel-Wert-Paare nach

Schlüssel und gibt Schlüssel-Wertelisten-Paare aus

3. Reduce:

• Ein Reducer pro Schlüssel

• Benutzerdefinierte Funktion wird auf Werteliste eines Schlüssels angewandt

Vorgehen bleibt immer gleich; Map- und Reduce-Funktion wird spezifiziert, um

das Problem zu lösen


MapReduce: Diagramm

MAP:Liest die Eingabe und

erzeugt eine Menge von

Schlüssel-Wert-Paaren

Gruppierung:Sammle alle Paare mit dem

selben Schlüssel(Hash merge, Shuffle, Sort,

Partition)

Reduce:Nimm alle Werte eines

Schlüssels und

berechne Ausgabe

Chunk 1 Chunk 4 Chunk 5…… … …


MapReduce: Parallele Ausführung


Beispiel: Erhebung der Häufigkeit von Wörtern

Anwendungen:

• Analyse eines Webserver-Protokolls (Log), um beliebte URLs zu finden

• Statistische maschinelle Übersetzung

The crew of the space

shuttle Endeavor recently

returned to Earth as

ambassadors, harbingers of

a new era of space

exploration. Scientists at

NASA are saying that the

recent assembly of the

Dextre bot is the first step in

a long-term space-based

man/mache partnership.

'"The work we're doing now

-- the robotics we're doing -

- is what we're going to

need ……………………..

Dokument

(The, 1)

(crew, 1)

(of, 1)

(the, 1)

(space, 1)

(shuttle, 1)

(Endeavor, 1)

(recently, 1)

….

(crew, 1)

(crew, 1)

(space, 1)

(the, 1)

(the, 1)

(the, 1)

(shuttle, 1)

(recently, 1)

…

(crew, 2)

(space, 1)

(the, 3)

(shuttle, 1)

(recently, 1)

…

Map Gruppierung Reduce

(Key, Value)

Vom Programmierer

bereitgestellt

(Key, Value)(Key, Value)

Seq

uen

tiel

les

Les

en

Vom Programmierer

bereitgestellt


Beispiel: Erhebung der Häufigkeit von Wörtern

map(key, value):

// key: document name; value: text of the document

for each word w in value:

emit(w, 1)

reduce(key, values):

// key: a word; value: an iterator over counts

result = 0

for each count v in values:

result += v

emit(key, result)


MapReduce: System

• MapReduce-Implementierung kümmert sich um

– Partitionierung der Eingabedaten

– Planung der Programmausführung über mehrere Rechner hinweg

– Durchführung des Gruppierungsschritts (Engpass in der Praxis)

– Behandlung von Serverausfällen

– Verwaltung der Kommunikation zwischen den Rechnern

• Datenfluss:

– Speichern der Eingabe und Ausgabe im verteilten Dateisystem (Master versucht

Map-Tasks „in der Nähe“ des physischen Speicherorts der Daten auszuführen)

– Zwischenergebnisse werden im lokalen Dateisystem der ausführenden Rechner

gespeichert

– Die Ausgabe ist oft die Eingabe einer weiteren MapReduce-Prozedur


MapReduce: Master

• Master-Knoten kümmert sich um:

– Den Status der Tasks: unbearbeitet, in Arbeit oder abgeschlossen

– Unbearbeitete Aufgaben werden übergeben, sobald eine Rechner verfügbar

– Wenn eine Map-Task abgeschlossen ist, sendet sie dem Master die Lokalisierung

und Größe der Zwischenergebnisse

– Der Master übergibt diese Information den verfügbaren Reduce-Rechnern

• Der Master pingt alle Rechner regelmäßig, um Ausfälle zu erkennen

• Umgang mit Ausfällen

– Ausfall eines Map-Rechners: alle Tasks (in Arbeit oder abgeschlossen) werden auf

unbearbeitet gesetzt und neu vergeben; zuständige Reduce-Rechner werden über

neuen Map-Rechner benachrichtigt

– Ausfall eines Reduce-Rechners: Reduce-Tasks, die in Arbeit sind, werden

zurückgesetzt und neu vergeben

– Ausfall des Masters: MapReduce-Prozedur wird abgebrochen


MapReduce: Optimierung

• Anzahl der Reducer > Anzahl der Reduce-Tasks

– Minimiert Overhead (Anzahl der Dateien mit Zwischenergebnissen)

– Ähnliche durchschnittliche Ausführungsdauer aller Reduce-Tasks (unterschiedliche

Anzahl an Werten pro Key)

• Für Map-Tasks sind unterschiedliche Ausführungszeiten vorteilhaft:

Gruppierungsphase während der Map-Phase möglich

– Anzahl der Map-Tasks > Anzahl der Server: Bessere dynamische Lastverteilung

– Beschleunigung des Abschlusses einer Phase durch Backup Tasks: mehrere

Kopien der gleichen Task; „der Erste gewinnt“


MapReduce: Combiners

• Ein Map-Task erzeugt oft viele Paare des gleichen Schlüssels

• Weniger Kommunikation zwischen Rechnern, wenn Werte im Mapper

durch eine Combiner-Funktion vorab aggregiert werden

– Combiner-Funktion ist normalerweise identisch zur Reduce-Funktion

– Funktioniert nur, wenn die Reduce-Funktion kommutativ und assoziativ ist

• Beispiel: Häufigkeit von Wörtern


Inhaltsverzeichnis

• Organisation

• Data Mining





– MapReduce






Algorithmen mit MapReduce

• MapReduce ist ineffizient für Probleme, die wahlfreien Zugriff (randomaccess) auf Daten erfordern, z.B. OLTP

• MapReduce ist ideal für– Probleme, die einen sequentiellen Datenzugriff erfordern

– Große Datenmengen mit wenig Aktualisierungen

– Große Batch-Jobs (nicht interaktiv)

– Analytische Anfragen auf großen Datenmengen

• Typische Beispiele:– Matrix-Vektor-Produkt

– Matrixmultiplikation

– Operationen der Relationalen Algebra:

• Selektion

• Projektion

• Vereinigung

• Natural Join

• Gruppierung & Aggregation


Beispiel: Join mit MapReduce

• Natural Join R(A,B) ⋈ S(B,C)

• R und S sind als Dateien gespeichert

• Ein Tupel ist ein Paar (a,b) oder (b,c)

A B

a1 b1

a2 b1

a3 b2

a4 b3

B C

b2 c1

b2 c2

b3 c3

⋈A C

a3 c1

a3 c2

a4 c3

=

RS


Beispiel: Join mit MapReduce

• Sei 𝑘 die Anzahl der Reducer-Tasks

• Verwendung eine Hash-Funktion ℎ, die von den Werten aus B auf die

Menge der Reducer bzw. auf {1,… , 𝑘} abbildet

• Map:

– Eingabe R(a,b) zu (b,(a,R))

– Eingabe S(b,c) zu (b,(c,S))

• Schlüssel-Wert-Paar mit Schlüssel 𝑏 wird dem Reducer-Taks ℎ(𝑏)übergeben (automatisch in Hadoop)

• Reduce:

– Ein Schlüssel b verweist auf eine Liste von Paaren des Typs (a,R) oder (c,S)

– Erzeuge alle Kombination der Paare (a,R) mit alle Paaren (c,S)

– Ergebnis: Liste von Tupeln (a,b,c)


Inhaltsverzeichnis

• Organisation

• Data Mining





– MapReduce






Erweiterungen

• Einschränkungen von MapReduce:

– Schwierige Programmierung: Viele Probleme sind nicht einfach als MapReduce-Prozedur

beschreibbar

– Leistungsengpässe: Speicherung auf Festplatte ist wesentlich langsamer als die Arbeit

im Hauptspeicher

• Kurz: MapReduce ist ungeeignet für umfangreiche Anwendungen

• Oft müssen mehrere MapReduce-Schritte kombiniert werden

• Erweiterungen: Workflow Systeme

– Erlauben andere Funktionen als Map und Reduce

– Erlauben eine beliebige Anzahl von Phasen: azyklisches Datenfluss-Netzwerk

– Blocking Property:

• Ausgabe erst nach Verarbeitung

der kompletten Eingabe

• Ermöglicht die Wiederherstellung von

einzelnen Tasks anstatt des ganzen Jobs

– Verteilte Ausführung

• Beispiele: Spark, Flink, TensorFlow, Giraph (zyklisch, Bulk-Synchronous System)


Spark

• Ergänzungen zu MapReduce:

– Allgemeine Ausführungsgraphen (gerichtet und azyklisch)

– Mehr Funktionen als nur Map und Reduce

– Vermeidung des Speicherns von Zwischenergebnissen auf Festplatte

• Kompatibel mit Hadoop

• Datenformat: Resilient Distributed Dataset (RDD)

– Datei mit Objekten eines Types (z.B. Schlüssel-Wert-Paare)

– Repliziert verteilt über Cluster

– Cache im Hauptspeicher (Rückgriff auf Festplatte möglich)

• RDDs werden über Hadoop geladen oder aus einer anderen RDD erstellt

• RDDs eignen sich am besten für Anwendungen, die dieselbe Operation

für alle Elemente eines Datasets anwenden


Spark: RDD Operationen

• Transformation: Umwandlung eines RDD über Operator:

– z.B. map, flatmap, filter, join, groupBy

– Lazy evaluation: Keine Berechnung bis erforderlich

• Action: Berechnung eines Wertes oder Exportierung des RDD

– z.B. count, collect, reduce, save

– Anwendung auf RDD

– Aktionen erzwingen Berechnungen und geben Werte aus

join

filter

groupBy

Stage 3

Stage 1

Stage 2

A: B:

C: D: E:

F:

= RDD

map


Berkeley Data Analytics Stack (BDAS).

Quelle: https://amplab.cs.berkeley.edu/software/


Inhaltsverzeichnis

• Organisation

• Data Mining





– MapReduce






Kommunikationskosten

• Engpass in Workflow Systemen ist Kommunikation zwischen Tasks

• Berechnungszeit der Tasks weniger wichtig, da

– Oft linear in der Größe der Eingabe

– Berechnungen im Hauptspeicher sind WESENTLICH SCHNELLER als

Kommunikation mit Festplatte bzw. über Netzwerk

• Kommunikationskosten = Summe der Größen aller Eingaben

über alle Tasks

• Beispiel: 3-way Join mit MapReduce

– R(A,B) ⋈ S(B,C) ⋈ T(C,D)

– Kommunikationskosten von R ⋈ S: 2 𝑅 + 2 𝑆

– Ausgabe hat Größe |R ⋈ S| (Vielfaches von |R| + |S|)

– 2-fache Ausführung eines Natural Join: 2 𝑅 + 2 𝑆 + 2 𝑇 + 2|R ⋈ S|


Alternative Berechnung 3-way Join

• Hash: ℎ: 𝑣𝑎𝑙𝑢𝑒𝑠(𝐵) → {1,… , 𝑏} und g: 𝑣𝑎𝑙𝑢𝑒𝑠(𝐶) → {1,… , 𝑐}

• Ein Reducer für jedes Paar (i, j) mit i ∈ {1,… , 𝑏} und j ∈ {1,… , 𝑐}

• Map:

– Eingabe R(A,B) zu ( ℎ 𝐵 , 𝑗 , 𝑅(𝐴, 𝐵)) für alle j ∈ {1, … , c}

– Eingabe T(C,D) zu ((𝑖, 𝑔(𝐶)) , 𝑇(𝐶, 𝐷)) für alle i ∈ 1, … , b

– Eingabe S(B,C) zu ℎ 𝐵 , 𝑔 𝐶 , 𝑆 𝐵, 𝐶

• Reduce:

– Ein Schlüssel (i, j) verweist auf

eine Liste von Tupeln aus R, S und T mit

ℎ 𝐵 = 𝑖 und g 𝐶 = 𝑗

– Erzeuge Join aus allen Tupeln

mit R.B = S.B und S.C = T.C

• Minimale Kommunikationskosten für eine gegebene Anzahl an Reducer

𝑘 = 𝑏𝑐: 𝑅 + 2 𝑆 + 𝑇 + 2 𝑘 𝑅 𝑇


Inhaltsverzeichnis

• Organisation

• Data Mining





– MapReduce






Komplexitätstheorie für MapReduce

• Verhältnis zwischen Kommunikationskosten und Rechenzeit (Reducer)

• Rechenzeit wird minimiert durch

– Parallelisierung

– Berechnung im Hauptspeicher

• Dazu sollte Eingabe der Reducer nicht zu groß sein (z.B. 2 - 32GB

passen in Hauptspeicher eines Rechners)

• Reducer Size 𝑞: Obere Schranke der Anzahl der Werte für einen

Schlüssel aus dem Map-Schritt

• Replication Rate 𝑟: durchschnittliche Anzahl der Schlüssel-Wert-Paare,

die pro Eingabe durch Mapper erzeugt werden

• Oft: Inverse Beziehung zwischen 𝑞 und 𝑟


Beispiel: Similarity Join

• Berechnung der Ähnlichkeit zwischen 1 Million Bilder (jeweils 1 MB)

• Naiver Ansatz:

– Map: jedes Bild 𝑃𝑖 auf die Schlüssel {𝑖, 𝑗} mit 𝑗 ∈ 1, … , 106 , 𝑗 ≠ 𝑖

– Reduce: zwei Bilder 𝑃𝑖 und 𝑃𝑗 pro Reducer, d.h. 𝑞 = 2

– Da 𝑟 = 999.999, ca. 1 Exabyte Kommunikation, 2,5 Jahre bei 100 Gbps Ethernet

• Besser: Gruppierung der Bilder in 𝑔 Gruppen

– Map: jedes Bild 𝑃𝑖 auf die Schlüssel {𝑢, 𝑣} mit 𝑣 ∈ 1,… , 𝑔 , 𝑢 ≠ 𝑣 und 𝑢 ist die

Gruppe von 𝑃𝑖, d.h. 𝑟 = 𝑔 − 1

– Reducer des Schlüssels {𝑢, 𝑣} erhällt alle Bilder der Gruppen 𝑢 und 𝑣

– da 𝑞 = 2106

𝑔reicht für Reducer ein 2GB-Hauptspeicher bei g = 1000

– Kommunikation benötigt „nur noch“ 22 Stunden

• Effizientere Verfahren im nächsten Kapitel, aber 𝑟 ≥106

𝑞(untere

Schranke, siehe Abschnitt 2.6.6 im MMDS)


Referenzen, Beispiele, Übungen

Kapitel 1 + 2 aus „Mining of Massive Datasets“:


Übungen:

• Optimierung der Reduce-Tasks: 2.2.1

• Algorithmen für MapReduce: 2.3.1

• Kommunikationskosten: 2.5.1



Übung 2.2.1

MapReduce für Häufigkeit von Wörtern; 100 Map-Tasks

a) Gibt es große Unterschiede in den Verarbeitungszeiten der Reducer,

wenn keine Combiner verwendet werden?

– Reducer, die für Stoppwörter (z.B. und, der, …) zuständig sind, benötigen wesentlich

länger als Reduce, die für seltene Wörter zuständig sind

b) Je kleiner die Anzahl der Reducer-Tasks, desto …

– ähnlicher die Ausführungszeiten der Tasks.

– Begründung: häufige und seltene Wörter werden gleichmäßig über die Reducer-

Tasks verteilt

c) Gibt es große Unterschiede in den Verarbeitungszeiten der Reducer,

wenn Combiner verwendet werden?

– Die Ergebnisse eines Combiner umfassen beinahe alle vorkommenden Wörtern

– Jeder Reducer bekommt dann ca 100 Werte pro Schlüssel (genauso viele Combiner

wie Map-Tasks)


Übung 2.3.1

MapReduce Algorithmus auf Datei mit ganzen Zahlen

a) Maximum

– Map: Berechnung des Maximum

– 1 Reducer bildet Maximum über alle Maxima der Mapper

b) Durchschnitt

– Map: Berechnung der Summe und Anzahl der Elemente

– 1 Reducer berechnet Durchschnitt

c) Eindeutige Elemente (distinct)

– Ein Reducer pro Wort

d) Anzahl eindeutiger Elemente

– Über Zwei MapReduce-Prozeduren


Übung 2.5.1

Kommunikationskosten

a) Matrix-Vektor-Multiplikation: 2 ⋅ |M| + |v|

b) Vereinigung: 2 ⋅ (|R| + |S|)

c) Aggregation: 2 ⋅ |R|

d) Matrix-Multiplikation: |M| + |N| + m|N| + n|M|

Documents

Data Mining - uni-leipzig.de · 2018-11-01 · Data Mining 1-8 WS 2018/19 Hintergrund • „Welt der Datenbanken“: Data Mining bezieht sich auf die Anwendung effizienter Algorithmen