ScaDS Logo

COMPETENCE CENTER
FOR SCALABLE DATA SERVICES
AND SOLUTIONS

Graph Mining für fortgeschrittene Datenanalysen

Beitragsseiten

Um komplexe analytische Fragestellungen zu beantworten, werden Data Mining-Verfahren oft mit anderen Schritten der Datenverarbeitung kombiniert, zum Beispiel zur Vorbereitung des Suchraums oder zur Nachbearbeitung der Ergebnisse. Um die Kombination von Data Mining-Algorithmen mit anderen Operatoren zu ermöglichen, bieten produktive Lösungen zur Analyse relationaler oder multidimensionaler Daten meist umfangreiche Toolkits an. Anders ist das in Bezug auf die weniger etablierten Verfahren des Graph Mining. Hier existieren zwar Forschungsprototypen, aber keine Lösung, die komplexe analytische Programme aus mehren Graphoperationen unterstützt. Das an der Universität Leipzig und dem ScaDS Dresden/Leipzig entwickelte Open Source System Gradoop hat sich zum Ziel gesetzt, dies zu ändern. Gradoop ist das erste System, welches es ermöglicht, in einfachen Skripten ein oder mehrere Graph-Algorithmen mit weiteren vor- und nachgelagerten Graph-Operatoren zu kombinieren. Hierdurch werden neuartige Anwendungsfälle möglich, zum Beispiel die nachfolgend gezeigte Analyse von Geschäftsdaten. Durch den Einsatz aktueller Big Data-Technologie bietet Gradoop nicht nur einen einzigartigen Funktionsumfang, sondern ist auch out-of-the-box horizontal skalierbar. Zudem bietet es eine Schnittstelle für Plug in-Algorithmen und ist damit offen für anwendungsspezifische Erweiterungen.

Graphen für die Analyse von Geschäftsdaten

Das erste Graph Mining-Verfahren, welches in Gradoop verfügbar ist, dient dem Auffinden häufiger Muster (Frequent Subgraph Mining). Wie auch beim relationalen Pendant (Frequent Itemset Mining) werden häufig zusammen auftretende Entitäten ausgewertet. Im Beispiel der klassischen Warenkorbanalyse stellt ein Muster eine bestimmte Kombination von Produkten, wie etwa Brot, Butter und Milch, dar. In konkreten Anwendungsfällen sind analytische Fragestellungen jedoch selten so einfach wie im Lehrbuch. So können etwa bei der Optimierung von Webshops nicht generell häufig zusammen gekaufte Produkte von Interesse sein, sondern beispielsweise häufig zusammen auftretende Produktgruppen in abgebrochenen Bestellvorgängen. Um solche komplexeren Fragen zu beantworten sind mehrere Schritte der Datenverarbeitung notwendig. Bevor der eigentliche Algorithmus ausgeführt wird, müssen hier abgebrochene Bestellungen gefiltert und Produkte durch Repräsentanten Ihrer Gruppen ersetzt werden. Für relationale und multidimensionale Daten existieren bereits produktive Lösungen, die solche mehrstufigen Analysen in flexibler Art und Weise unterstützen. Anders ist das in Bezug auf Graphdaten. Doch welchen Vorteil bietet das Graphmodell?

Neben dem gemeinsamen Auftreten bestimmter Entitäten (Knoten) beinhalten Graphmuster zusätzlich auch deren Beziehungen (Kanten). Zur Analyse von Geschäftsdaten lassen sich beispielsweise alle Daten, die während der Ausführung von Geschäftsprozessen aufgezeichnet werden, als Menge von Graphen abbilden. Dabei stellt jeder Graph eine einzelne Prozessausführung dar. Ein Graph enthält dabei alle Daten rund um einen Online-Kaufvorgang beginnend von der kundenseitigen Bestellung, über Einkaufs- und Lagervorgänge bis hin zur Auslieferung. Knoten können hier sowohl Stammdaten, wie etwa Mitarbeiter und Produkte, als auch transaktionale Daten, wie Rechnungen oder Lieferscheine, sein. Die Kanten stellen dann zusätzlich Informationen über Beziehungen bereit, etwa welcher Mitarbeiter ein bestimmtes Paket gepackt hat. Durch diese Abbildung als Graphmenge lassen sich Muster erkennen, die sowohl das gemeinsame Auftreten bestimmter Stammdaten als auch deren Rollen im Prozess repräsentieren, d.h. wer oder was in welcher Form im Prozess involviert war.

Abbildung 1 : Graphmuster in Prozessdaten.

Derartige Musteranalysen werden vor allem im ökonomischen Kontext interessant, zum Beispiel der Zusammenhang von Mustern und Reklamationen. Doch welche Schritte müssen erfolgen um solche Muster zu finden? Zunächst müssen Graphen, die Reklamationen enthalten, identifiziert und gefiltert werden. Nehmen wir zudem an, dass Knoten Geschäftsobjekte mit Typen (z.B. Mitarbeiter, Rechnung oder Produkt) und Eigenschaften (z.B. Identifikatoren oder Preise) beschreiben. Dann sind vor allem jene Muster interessant, die eine Aussage darüber liefern, welche konkreten Stamm- und transaktionalen Daten in welchen Prozessschritten in welcher Art und Weise involviert waren. Dazu müssen die verbleibenden Graphen so transformiert werden, dass Identifikatoren von Stammdaten gemeinsam mit Typen von transaktionalen Knoten und Kanten ausgewertet werden können. Abbildung 1 zeigt zwei Beispiele für Graphmuster in Prozessdaten. Man sieht dabei, dass sowohl einfache Muster (i) aber auch komplexere Beziehungsgeflechte (ii) gefunden werden können. Mit Gradoop lassen sich Graphdaten in einem einzigen Programm entsprechend unseres Beispiels kategorisieren und filtern um anschließend häufige Muster zu identifizieren.