Crowd Sensing und Social Data Mining mit Mobilen Agenten

Einführung in das Data Mining

Begriffe

Sourcing

Schöpfung von Mehrwert: Quelle von Informationen mit Bereitstellung von Daten; Aber auch Bereitstellung von Arbeitsleistung; Sammlung von Gütern

Sensing

Wahrnehmung von sensorischen Informationen

Perzeption

Wahrnehmung und Interpretation von sensorischen Informationen

Sensoren

Wandler die eine physikalische in eine andere physikalische Größe umwandeln (i.A. elektrisch oder digital)

Virtuelle Sensoren

Funktionen mit einer Eingangs- und Ausgangsschnittstelle zur Weiterverarbeitung und Fusion von Sensorsignalen

Begriffe

Umfrage

Neben der Bereitstellung von sensorischen Daten X=x₁,..,x_i (ggfs. passiv) kann es aktive Teilnahme an Datenerhebung geben i.A. mit einem zu testenden Modell, d.h.,

Data Mining

Ableitung von Informationen aus Daten (Variablen X=x₁,..,x_i) häufig ohne genaue Modelle (statistisch) und Korrelation der Variablen, d.h.:

Begriffe

Crowd Sourcing (CWO)

Bereitstellung von Arbeitsleistung durch eine größere Gruppe von Menschen die nicht unmittelbar organisiert (sozial verbunden) sind. Aktive Teilnahme an Umfragen kann dazu gehören (d.h. CWS ⊂ CWO)

Crowd Sensing (CWS)

Erhebung und Erfassung von sensorischen Informationen die durch eine größere Gruppe von Menschen, die nicht unmittelbar organisiert (sozial verbunden) sind, bereit gestellt werden.

Mobiles Crowd Sensing (MCWS)

CWS mit mobilen Geräten und beweglichen Nutzern → räumliche Veränderung und Ortskontext können eine wichtige Rolle spielen!

Das Konzept

• Die automatisierte Wahrnehmung sensorischer Informationen soll durch mobile Agenten implementiert werden

• Diese Agenten können durch eine universelle Ausführungsplattform auf einer Vielzahl von Computern und mobile Geräten ausgeführt werden

• Die Plattformen spannen ein virtuelles Netzwerk auf, dass es den Agenten ermöglicht verschiedene Geräte zu “besuchen”

• Dabei sollen die Agenten mit Menschen und Maschinen interagieren

  • Mensch-Agent-Maschine Schnittstelle
  • Maschine-Agent-Maschine Schnittstelle
  • Agent-Agent Schnittstelle

• Die Agenten werden in lose gekoppelten Multiagentensystemen durch Divide-and-Conquer und Selbstorganisation ihre Aufgaben erfüllen

Das Konzept

Das Konzept

Das Konzept

Das Konzept

Das JavaScript Agenten Labor (webui)

Das Konzept

Data Mining

Data Mining - Grundlagen

Data Mining ⇔ Knowledge discovery from data (KDD)

Data Mining - Grundlagen

Welche Daten und Quellen?

Data Mining - Grundlagen

Architektur

Data Mining - Datenwarenhäuser

Begriff

• Ein Datenwarenhaus (Data Warehouse, DW) ist ein Sammlung (Pool) mit Informationen, die aus mehreren Quellen gesammelt, unter einem einheitlichen Schema gespeichert werden und sich normalerweise an einem einzigen Standort befinden.
• Datenwarenhäuser werden durch einen Prozess der Datenbereinigung, Datenintegration, Datentransformation, Datenspeicherung und periodische Datenaktualisierung erstellt.

Data Mining - Datenwarenhäuser

Eigenschaften

Zentrale Datenverwaltung

Die Daten sind zentral gespeichert und nicht über viele verschiedene Systeme verteilt → erhöht Performance und den Überblick.

Archivierung der Daten

Auch historische Daten, die für die Operativen Systeme meist bedeutungslos sind, werden in einem DW gespeichert, um den Analysen mehr Aussagekraft zu verleihen.

Schneller Zugriff

Mehrdimensionale Abfragen auf dem DW sind effizienter als einzelne Abfragen auf den Quellsystemen.

Zugriff

Das DW ist für viele Nutzer zugänglich.

Unabhängigkeit

Unabhängigkeit zwischen Datenquellen und Analysesystemen

Data Mining Funktionen

• Es gibt eine Reihe von Data Mining-Funktionen. Dazu gehören

  • Charakterisierung und Diskriminierung;
  • Die Gewinnung häufiger Muster, Assoziationen und Korrelationen;
  • Klassifizierung und Regression;
  • Clusteranalyse; und
  • Ausreißeranalyse.

• Data Mining-Funktionen werden verwendet, um die Arten von Mustern anzugeben, die in Data Mining-Aufgaben zu finden sind.

• Im Allgemeinen können solche Aufgaben in zwei Kategorien unterteilt werden:

  • Beschreibende Kategorie; und
  • Vorhersagende Kategorie.

• Beschreibende Mining-Aufgaben charakterisieren die Eigenschaften der Daten in einem Zieldatensatz.

• Vorhersagende Mining-Aufgaben führen eine Reduzierung der aktuellen Daten durch, um Vorhersagen zu treffen.

Data Mining - Datenverarbeitung

Datenverarbeitungsparadigmen

• Die Datenverarbeitung kann klassifiziert werden nach Daten- und Instruktionsströmen (DS/IS)

  • Ursprünglich nach Flynn für Parallelrechner angewendet
  • Art und Anzahl der Daten- und Instruktionsströme bestimmt die Performanz des Gesamtsystems
  • Je stärker Daten- und Instruktionsströme lokalisiert sind (d.h. keine oder nur geringe Netzwerkkommunikation benötigen), um so hier wird die Performanz
  • Große Datenmengen müssen gespeichert werden → Verteiltes Speichermodell vs. Geteiltes Speichermodell

• Kann für netzwerkgekoppelte und verteilte Rechnersysteme adaptiert werden:

  • Wo sind die Daten?
  • Wohin müssen Daten übertragen werden (DS)?
  • Wo werden die Daten verarbeitet (IS)?

Data Mining - Datenverarbeitung

Data Mining - Datenverarbeitung

Verteilte Datenverarbeitung

• Klassischer Ansatz (1) : Zentrale Recheninstanz mit paralleler Datenverarbeitung

  • Erfordert Datenkollektion mit großen Datenströmen, Daten müssen zur Berechnung gebracht werden → nicht (gut) skalierbar
  • Beim Data Mining (und Big Data) sind die Daten bereits verteilt!

• Klassischer Ansatz (2) : Verteilte Recheninstanzen (Cloud) mit paralleler Datenverarbeitung

  • Auch hier sind Daten und Berechnung u.U. noch getrennt und müssen zusammengeführt werden

• Neuer Ansatz (z.B. Hadoop) : Verteilte Recheninstanzen (Cloud) mit paralleler Datenverarbeitung mit Datenkopplung

  • Die Berechnung wird zu den Daten gebracht!

Data Mining - Datenverarbeitung

Data Mining - Datenverarbeitung

Map-Reduce Algorithmen

Data Mining - Datenverarbeitung

Motivation

• Großskalige Datenverarbeitung

  • Viele Daten verarbeiten (> 1 TB)
  • Parallelisierung auf Hunderttausende von CPUs
  • Einfache Handhabung und Umsetzung

• Map-Reduce bietet:

  • Automatische Parallelisierung und Verteilung
  • Fehlertoleranz
  • Stellt Status- und Überwachungstools bereit.
  • Abstraktion für Programmierer

Data Mining - Datenverarbeitung

Funktionale Programmierung

• Map-Reduce Algorithmen, wie sie z.B. im Hadoop System verwendet werden, haben Ähnlichkeit mit funktionalen Programmiersprachen (wenn auch Map&Reduce kein spezifisches funktionales Problem ist):
  • Funktionale Operationen verändern keine Datenstrukturen: Sie erstellen immer neue;
  • Originaldaten sind unverändert vorhanden;
  • Datenfluss ist im Programmdesign implizit;
  • Reihenfolge der Operationen spielt keine Rolle.
  • Funktionale Programmierung wendet Operationen auf Listen an

Data Mining - Datenverarbeitung

Map0

function (f: ’a->’b, ’a list) -> ’b list

Ursprüngliche funktionale map Funktion. Erzeugt eine neue Liste durch Anwendung einer Funktion f auf jedes Element der Eingangsliste (oder Arrays) → Abbildung

[a]

Data Mining - Datenverarbeitung

Map

function (in_key,in_value) -> (out_key,intermediate_value) list

Adaption der ursprünglichen map Funktion. Datensätze von einer Datenquelle (Zeilen aus Dateien, Zeilen einer Datenbank usw.) werden als Schlüssel / Wert-Paare in die Abbildungsfunktion eingegeben: z.B. (Dateiname, Zeile). map erzeugt aus der Eingabe einen oder mehrere Zwischenwerte zusammen mit einem Ausgabeschlüssel.

[a]

Data Mining - Datenverarbeitung

Fold

function (f:'a*'b->'b, x0:'b, lst;'a list) ->'b

Ursprüngliche funktionale fold Funktion. Iteriert über eine Liste und wendet f auf jedes Element plus einen Akkumulator an (Anfangswert x₀). f gibt den nächsten Akkumulatorwert zurück, der mit dem nächsten Element der Liste kombiniert wird → Reduktion.

[a]

Data Mining - Datenverarbeitung

Reduce

function (out_key, intermediate_value list) -> out_value list

Adaption der ursprünglichen fold Funktion. Nach der Beendigung der Abbildungsphase werden alle Zwischenwerte für einen bestimmten Ausgabeschlüssel zu einer Liste zusammengefasst. reduce kombiniert diese Zwischenwerte zu einem oder mehreren Endwerten für denselben Ausgabeschlüssel (in der Praxis normalerweise nur ein Endwert pro Schlüssel)

[a]

Data Mining - Datenverarbeitung

Map-Reduce Beispiel in JavaScript

Data Mining - Datenverarbeitung

Map-Reduce Methode in Hadoop

• Daten werden verteilt im HDFS (Hadoop Distributed File System) abgelegt

• Datenblöcke werden mehreren Mappern zugewiesen, die Schlüssel-Wert-Paare ausgeben, die parallel gemischt und sortiert werden.

• Der Reduzierungsschritt gibt ein oder mehrere Paare (mit Daten die den gleichen Schlüssel haben) aus, wobei die Ergebnisse im HDFS gespeichert werden

Data Mining - Datenverarbeitung

Data Mining - Datenverarbeitung

Limitierungen von Hadoop

Leistung

• Hadoop hat sich als skalierbare Implementierung erwiesen, die auf Tausenden von Cores laufen kann.
• Es ist jedoch auch bekannt, dass der Aufwand für die Einrichtung von Jobs relativ hoch ist und die Laufzeit nicht optimal ist.
• Eine leere Aufgabe in Hadoop (d.h. Ohne Mapper oder Reduktion) kann selbst in einem modernen Cluster etwa 30 Sekunden dauern.
• Dieser Aufwand macht ihn für Echtzeitdaten oder interaktive Jobs ungeeignet.
  • Das Problem rührt hauptsächlich von der Tatsache her, dass Hadoop-Überwachungsprozesse nur innerhalb eines Jobs leben.
  • Daher muss dieser Prozess bei jeder Übergabe eines Jobs gestartet und gestoppt werden, was wiederum zu einem erheblichen Overhead führt.

Data Mining - Datenverarbeitung

Echtzeitanwendungen

• In der aktuellen Konfiguration unterstützt Hadoop nur Batch-Datenverarbeitungsjobs. Dies ist beabsichtigt, daher ist es keine Einschränkung für Hadoop selber.

• Da jedoch immer mehr Anwendungen großvolumige Datensätze in Echtzeit verarbeiten, wächst die Community, die Map-Reduce für die Echtzeitverarbeitung verwendet, ständig weiter.

• Die Unterstützung von Streaming oder Echtzeitdaten ist für Hadoop eindeutig ein Nachteil gegenüber anderen Implementierungen.

Data Mining - Datenverarbeitung

Cloud Computing

• Cloud Computing bedeutet die lose Kopplung von Rechnern in einem Netzwerk (Internet) bei dem sich die Konfiguration (Art und Anzahl der Rechner) sowie die Vernetzung dynamisch ändern können

• Eine Cloud kann Datenverarbeitungsdienste bereit stellen die über eine (evtl. käufliche) Schnittstelle nutzbar sind → Cloud Services.

• Virtualisierung von Speicher und Berechnung spielt eine große Rolle beim Cloud Computing → Ziel: Mobile Agenten!

• Beim Cloud Computing, welches auch beim Crowdsensing eingesetzt wird, unterscheidet man verschiedene Klassen:

  1. Öffentliche Cloud
  2. Private Cloud
  3. Hybride Cloud

Data Mining - Datenverarbeitung

• Crowdsensing an der Schnittstelle von öffentlicher und privater Cloud

Data Mining - Datenverarbeitung

Cloud Computing-Funktionen

• Cloud Computing bringt im Vergleich zu anderen Computing-Paradigmen eine Reihe neuer Funktionen mit sich (Wang et al., 2008; Grossman, 2009).

Skalierbarkeit und On-Demand-Services

Cloud Computing stellt Ressourcen und Services für Benutzer zur Verfügung. Die Ressourcen sind über mehrere Rechenzentren skalierbar.

Benutzerzentrierte Benutzeroberfläche

Cloud-Schnittstellen sind ortsunabhängig und können von jedem durch etablierte Schnittstellen wie Webdienste und Internetbrowser genutzt werden.

Data Mining - Datenverarbeitung

Garantierte Quality of Service (QoS)

Durch Cloud-Berechnungen kann QoS für Benutzer in Bezug auf Hardware / CPU, Leistung, Bandbreite und Speicherkapazität garantiert werden.

Autonomes System

Die Cloud-Computing-Systeme sind autonom und transparent. Software und Daten in Clouds können jedoch je nach den Anforderungen des Benutzers automatisch rekonfiguriert und zu einer einfachen Plattform konsolidiert werden.

Preisgestaltung

Cloud Computing erfordert keine Investitionen. Benutzer zahlen für Dienste und Kapazität, wenn sie benötigt werden.

Data Mining - Datenverarbeitung

Data Mining - Datenvisualisierung

• Die Daten eines komplexen Datenbanksystems (wie eines digitalen Warenhauses) werden in der Regel durch eine mehrdimensionale Datenstruktur modelliert, die als Datenwürfel bezeichnet wird:

  • Jede Dimension wird einem Attribut oder einer Gruppe von Attributen im Schema entstprechen
  • Jede Zelle gibt den Wert irgendeiner aggregierten Kennzahl wie z.B. count oder sum (z.B. von Verkaufszahlen) an.

• Ein Datenwürfel bietet eine mehrdimensionale Ansicht der Daten und ermöglicht die Vorberechnung und den schnellen Zugriff auf zusammengefasste Daten.

• Es können verschiedene Ansichten des Würfels aus aggregierten Daten abgeleitet werden

Data Mining - Datenvisualisierung

Smart Environments

• Z.B. Smart Cities bestehen aus heterogenen Informations- und Kommunikationsarchitekturen und Technologien

• Baumstruktur:

  1. Cloud Computing mit großen Datenbanken und Servern
  2. Internet und Mobile Geräte
  3. Edge/Fog Computing
  4. Geräte und Sensoren
  5. Aktuatorische Systeme (Cyber-Physical Systems)

• Existierende Smart Environments stellen eine Plattform für das Crowdsensing dar

  • Mit Menschinteraktion
  • Reine Gerätedaten → Internet der Dinge!

• Traditionelle Sensornetzwerke (die anwendungsspezifisch sind) und Crowdsensingsysteme (die eher geenrisch sind) sind ähnlich und können sich ergänzen (Sensordatenfusion)

Smart Environments

Smart Environments

Mobile Netzwerke

Smart Environments

Crowdsensing Architektur - Der Klassiker

Smart Environments

Smartphone - Softwarearchitektur