Das Fachprojekt

In allen Bereichen werden heutzutage Unmengen an Daten produziert und - sofern möglich - gespeichert. So wird zum Beispiel im FACT-Projekt ein Teleskop in den Himmel gerichtet, das pro Nacht bis zu 1 TB Daten produziert. In Server-Systemen werden sämtliche Vorgänge in Log-Dateien protokolliert - was je nach Granularität ebenfalls enorme Datenmengen bedeutet.

Diese großen Datenmengen lassen sich mit herkömmlichen Methoden nur noch sehr schwer analysieren. Gängige Methoden des Maschinellen Lernens oder Data-Mining verarbeiten Datenmengen indem in mehreren Iterationen Modelle gelernt werden oder die es erfordern, die Daten komplett im Hauptspeicher zu halten.

Ein Paradigma, dass in den letzten Jahren Popularität erlangt hat, sind sogenannte one-pass oder online-Verfahren, bei denen ein Algorithmus jedes Element einer Datenmenge nur noch genau einmal betrachtet.

Innerhalb dieses Fachprojektes wollen wir einige Beispiele für Online-Algorithmen untersuchen.

Die Themenblöcke

Bei der Analyse von Datenströmen gibt es bereits einige Algorithmen, für unterschiedliche Bereiche, z.B.

Zu jedem dieser Themenblöcke, die im Folgenden genauer beschrieben werden, wird eine kleine "Expertengruppe" gebildet, die zu ausgewählten Ansätzen Vorträge ausarbeitet und ausgewählte Algorithmen implementiert und in der zweiten Hälfte des Fachprojektes testet.

Online Statistiken

Für viele Lernverfahren sind einige grundlegende Funktionen unerläßlich:

Natürlich kann man z.B. die Objekte in einem Datensatz zählen - z.B. wenn wir feststellen wollen, wie oft eine bestimmte URL aufgerufen wird. In diesem Fall müssten wir für jede URL einen Zähler verwalten und bei Auftauchen dieser URL den Zähler erhöhen.

Was passiert allerdings, wenn wir das in einem unendlich langen Datenstrom machen wollen? Wie haben nur begrenzten Speicher zur Verfügung und können daher nicht beliebig viele Zähler verwalten.

Hier benötigen wir Algorithmen, die uns zumindest approximativ eine gute Näherung für die Häufigkeit von URLs in dem Strom liefert.

Paper zum Thema Online-Statistiken

Diese Papiere sind eine Auswahl von verschiedenen Zählverfahren, Algortihmen um Quantil-Modelle zu berechnen und die k häufigsten Elemente zu finden (top-k Problem):

Die folgenden Papiere haben einen Fokus auf dem frequent itemset mining, d.h. es geht darum Mengen von Elementen zu finden, die häufig sind:

Klassifikation

Die Aufgabe der Klassifikation ist zu entscheiden, welcher Klasse ein Datenobjekt aus dem Strom zugeordnet werden soll. Ein bekanntes Beispiel ist die Klassifikation von E-Mails in die Klassen spam und no-spam.

Verfahren, wie z.B. der Naive Bayes Algorithmus basieren auf Wahrscheinlichkeitsverteilungen, die wiederum auf Grundlage von Zählverfahren Wahrscheinlichkeitsverteilungen annähern. So wird dann anhand einer Menge von Merkmalen (Attributen) eine Wahrscheinlichkeit für die Klassen spam und no-spam bestimmt.

Für neu zu klassifizierende E-Mails werden dann diese Merkmale bestimmt und Anhand der Merkmale jede E-Mail der Klasse mit der höchsten Wahrscheinichkeit zugeordnet.

Paper zum Thema Online-Klassifikation

Clustering

In vielen Fällen hat man - insbesondere bei großen Datenmengen - keine Menge von festen Klassen gegeben. So müssen z.B. bei der SPAM-Klassifikation zuvor eine Menge von E-Mails per Hand mit den richtigen Klassen versehen werden, damit ein Klassifikations-Algorithmus darauf trainiert werden kann.

Das Clustering gehört zu den sogenannten unüberwachten Lernaufgaben, d.h. wir haben Daten vorliegen, für die es keinen Datensatz mit richtigen/falschen Klassenzuordnungen gibt, auf denen gelernt werden kann.

Die Aufgabe des Clustering ist es, genau auf solchen Daten sinnvolle Gruppen zu finden, die jeweils ähnliche Objekte des Datenstroms zusammenfassen. Als Beispiel sei der Dienst "Twitter" genannt. Hier könnte man jetzt anhand von Twitter-Nachrichten Gruppen von Benutzern finden, die z.B. über ähnliche Themen schreiben.

Bezogen auf Log-Daten Analyse wären Fragestellungen interessant, die z.B. IP-Adressen anhand der häufig angefragten URLs gruppieren, oder Benutzer anhand ähnlicher HTTP-Sessions.

Paper zum Thema Clustering

Ausreißer-Erkennung

Die Ausreißer-Erkennung ist ein wenig das Gegenstück zum Clustering. Waren wir beim Clustering daran interessiert, möglichst ähnliche Objekte zu finden und zu Gruppen (Clustern) zusammenzufassen, geht es jetzt darum, Anomalien in den Daten zu erkennen, d.h. Datenpunkte, die nicht in das Gesamtbild passen:

Für den Fall der Log-Analyse könnten das Zugriffe sein, die ungewöhnliche Parameter-Werte übertragen um eine Web-Anwendung anzugreifen. Im Falle des FACT-Teleskops werden immer wieder ungewöhnliche Meßwerte aufgezeichnet, die aufgrund von Meßfehlern passieren und die Gesamtanalyse beeinträchtigen.

Die Erkennung von Ausreißern wird immer wichtiger, da Ausreißer zum einen höchst interessante Einzelfälle darstellen können (z.B. Angriffe) und zum anderen zur Qualitätssicherung der Daten erkannt werden müssen (Meßfehler).

Paper zum Thema Ausreißer-Erkennung

Die folgenden Paper zum Thema Ausreißer-Erkennung könnten im Fachprojekt betrachtet werden:

Ein weiteres wichtiges Thema bei der Stream-Analyse ist die Erkennung von concept drifts, d.h. die Verlagerung der Datenverteilung. Beispielsweise kann es sein, dass bei einem Experiment etwas geändert wurde (Teleskop-Einstellungen) und nun alle nachfolgenden Werte "anders" sind.

Paper, die sich mit der Erkennung von concept drifts befassen sind z.B.