KDD (Kap 6: Spatio-temporal Mining)

Beispiele für Daten

• Satellitenbilder
• Datenbanken mit Kundentransaktionen (georeferenzierte Kundenadressen)
• Behördendatenbanken, z.B. zu Orten mit Straftaten
• Web browsing sessions (IP-Addressen, GPS)
• Web-Seiten (extrahierte geographische Objekte)
• Geo-Datenbanken (Open Street Map, Flickr, Twitter)
• Sensornetze (z.B. Tonnen im Meer)
• Nutzer-Trajektorien (Mobiltelefone)
• Hurrikan-Trajektorien (abgeleitet aus Satellitenbildern)

• Spatio-temporale Dimensionen
  • viele Daten im Data Mining sind hochdimensional, allerdings sind
  • diese Dimensionen meist relativ unabhängig voneinander
  • Spatio-temporale Daten sind höherdimensional, jedoch bis zu 4 Dimensionen sind untereinander abhängig
  • Raumbezogene und temporale Dimensionen bilden oft den Rahmen für Messungen in den anderen Dimensionen
• Komplexe raumbezogene Objekte
  • Nicht-raumbezogene Informationen können oft als Punkte im Informationsraum repräsentiert werden
  • Größe, Gestalt, Begrenzung von Raum-/Geo-Objekten können komplexe Eigenschaften im Informationsraum sein

• temporale Autokorrelation
  • Prozesse/Phänomene/Ereignisse in zeitlicher Nähe tendieren dazu, ähnlich zu sein
• raumbezogene Autokorrelation
  • mit zunehmender Nähe zweier Objekte steigt die Wahrscheinlichkeit, dass sie ähnliche Eigenschaften besitzen

Räumliche Abhängigkeit

• bezeichnet die Tendenz von Attributen, an bestimmten Lokationen in Beziehung zu stehen

Räumliche Heterogenität

• bezeichnet Nicht-Stationärität der meisten geographischen Prozesse
• geographische Prozesse/Phänomene variieren oft mit der Lokation (Bsp. Baumhöhe in Abhängigkeit von der geographischen Höhe)
• Behandlung nicht-stationärer Phänomene ist eine Herausforderung

(statistische Methoden können helfen)

• Supervised (Raumbezogene Interpolation)
  • Wahrscheinlichkeit für das Finden von Öl an einem gegebenen Koordinationpunkt
  • typische Dauer einer Web-Browser-Sitzung eines mobilen Nutzer an einem gegebenen Ort
• Unsupervised (Clustering, Regionalisierung)
  • Hot Spots von Straftaten zur Planung von Polizeieinsätzen
  • Charakteristische Trajektorien von Mobilfunknutzern
• Assoziationsregeln
  • (Gesteinstyp = Kalkstein) ∧ (Bodentiefe < 20 cm) ⇒ (Risiko für Erdfall = Hoch)

• zunehmende Erfassung beweglicher Objekte: eingebettete Sensorik (GPS, WLAN, RFID)
• ermöglicht Ermittlung von Trajektorien (Bewegungspfade) von bewegten Objekten (Personen, Fahrzeuge, Produkte, . . . )
• Anwendungsgebiete:
  • Homeland security (Grenzüberwachung, Terroristenerkennung, Videoüberwachung),
  • ökologische Analysen (Tierbeobachtungen),
  • Wettervorhersage,
  • Verkehrsbeeinflussung,
  • Location-based Services, . . .

• Unsicherheit
  • variierende Samplingrate: von Sekunden bis Tagen
  • spärliche, dünn besetzte Daten
• Rauschen
  • fehlerhafte Messungen
• Hintergrundinfos
  • Autos fahren auf Straßennetz
  • Tiere folgen Pfaden entlang von Bergen, zu Seen und Flüssen, . . .
• Interaktion von Bewegungen
  • Bewegung eines Objektes kann durch sich bewegende Objekte in der Nähe beeinflusst werden („Ausweichen“)

Das Temporal Data Mining (auch sequentiell Pattern mining) beschäftigt sich mit der Analyse von zeitbezogenen Daten.

Solche Daten haben typischerweise neben inhaltlichen Attributen noch ein weiteres Attribut, dessen Werte auf Punkte oder Abschnitte in einem zeitlichen Bezugssystem (beispielsweise eines Kalenders) verweisen.

Der Bezug auf die Zeit impliziert eine Ordnung auf den Werten des Attributs, das die Zeit modelliert. Dadurch repräsentieren die Datensätze einer zeitbezogenen Datenmenge entweder einen einzigen Ablauf (eine Entwicklung) oder eine Menge unterschiedlicher Abläufe (mehrere Entwicklungen) von Ereignissen.

1. Bestimmung, Beschreibung und Analyse von zeitlich determinierten Zusammenhängen innerhalb einzelner Abläufe oder Entwicklungen.

2. Bestimmung, Beschreibung und Analyse von Zusammenhängen zwischen verschiedenen Abläufen oder Entwicklungen unter Berücksichtigung ihres zeitlichen Verlaufs.

Die Einbeziehung der Zeit beim Data Mining führt zu gewissen Besonderheiten, die zusätzlich berücksichtigt werden müssen. Es ergeben sich durch die Modellierung der Zeit komplexe und vielfaltige zeitliche Relationen zwischen Zeitpunkten und Zeitintervallen (z.B. "während", "überschneidend", "direkt aufeinanderfolgend"), die bei entsprechender Berücksichtigung in einem Algorithmus zu neuen und interessanten Regeln führen können, aber auch eine
zusätzliche Komplexität der Algorithmen zur Folge haben.

Das Finden von häufig auftretenden Sequenzen (kurz: häufigen Sequenzen) ist verwandt mit dem Finden von Assoziationsregeln, die in vorangegangenen Kapitel dargestellt wurden. Hierbei werden jedoch nicht mehr Mengen einzelner Warenkörbe oder Transaktionen untersucht, sondern Mengen von zusammengehörigen und zeitlich geordneten Sequenzen solcher Transaktionen.

Eine häufige Sequenz drückt die Tatsache aus, daß viele Kunden, die zu einem bestimmten Zeitpunkt gewisse Waren oder Dienstleistungen (A, B, C) eingekauft haben, zu einem späteren Zeitpunkt auch die Waren oder Dienstleistungen D, E und F gekauft haben.
Das Wissen um häufige Sequenzen dient typischerweise der Analyse von Kundenverhalten und wird dort etwa dazu verwendet, einem Kunden aufgrund seines bisherigen Kaufverhaltens gezielte Empfehlungen oder Vorschläge für Angebote zu machen.

Ein Anwender könnte beispielsweise ein Buchklub sein, bei dem häufige Sequenzen etwa wie die folgende aussehen:

"5% aller Kunden haben zuerst das Buch Solaris, danach das Buch Transfer und dann Der Futuralogische Kongreß gekauft."

Einem Kunden, der bisher schon Solaris gekauft hat, könnte dann, wenn er das Buch Transfer bestellt, auch noch Der Futuralogische Kongreß empfohlen werden.

126.

s.Abb

Der Algorithmus GSP ("Generalized Sequential Patterns") hat die gleiche Struktur wie der Apriori-Algorithmus zum Finden von Frequent Itemsets für Assoziationsregeln. Die Datenmenge wird dabei in ähnlicher Weise mehrmals durchlaufen:

• erster Durchlauf:
  • Bestimmung des Supports für jedes einzelne Item
  • Bildung der häufigen 1-Sequenzen aus einem Element mit einem einzigen Item
• folgende Durchläufe:
  • Bildung von Kandidatensequenzen mit k + 1 Items aus den im vorhergehenden Durchlauf bestimmten häufigen Sequenzen mit k Items
• Der Support der Kandidaten wird gezählt, und es werden diejenigen Sequenzen für den nächsten Durchlauf bestimmt, die minimalen Support haben. Dies wird solange durchgeführt, bis bei einer bestimmten Anzahl von ltems keine häufigen Sequenzen mehr gefunden werden können.
  Zum Abschluß werden aus der Menge der gefundenen häufigen Sequenzen diejenigen wieder gelöscht, deren Support, unter Berücksichtigung anderer häufiger Sequenzen zusammen mit der Item-Taxonomie, "uninteressant" ist.
   
• Modifikationen des Apriori-Algorithmus:
  • Kandidatengenerierung, Zählen des Supports von Kandidaten
  • Berücksichtigung von Item-Taxonomien

• Constraints für den zeitlichen Abstand zwischen den Gruppen von Transaktionen, die ein Element einer Sequenz unterstützen
• z.B. für Support der Sequenz ⟨(Solaris),(Transfer)⟩: Datensequenzen nicht berücksichtigen, bei denen zwischen Kauf von „Solaris“ und „Transfer“ drei Jahre liegen

Ein Zeitfensters wird durch eine ganze Zahl window-size vorgegeben, welche die "Breite" des Zeitfenster spezifiziert.

Zeitliche Constraints werden durch ganze Zahlen min-gap und max-gap vorgegeben, welche den minimalen und den maximalen Abstand zwischen unterstützenden Transaktionen spezifizieren.

Fenster w wird beschrieben durch [l, u] mit

• l = frühestes Auftreten eines Ereignisses im Fenster w
• u = letztes Auftreten eines Ereignisses im Fenster w
   

Die Besonderheit des Spatial Data Mining gegenüber dem relationalen Data Mining ist, daß die Nachbarn eines Objekts o Einfluß auf das Objekt o haben können, d.h. es bestehen typischerweise Abhängigkeiten zwischen den Attributswerten von benachbarten Objekten. Dieser Einfluß wird bestimmt vom Typ der räumlichen Nachbarschaftsbeziehung.

Die Verschmutzung der Umgebung, die von einer Industrieanlage ausgeht, hängt z.B. von der Distanz und von der Richtung ab.

Zwei Beispiele für raumbezogene Mustern:

• raumbezogene Assoziationsregeln
• Ko-Lokationsmuster/-regeln

Räumliche Assoziationsregeln basieren auf dem Konzept der Assoziationsregeln. Eine räumliche Assoziationsregel ist eine Assoziationsregel, die mindestens eine räumliche Nachbarschaftsbeziehung enthält. Ein Benutzer möchte z.B. die Assoziationen der Städte in British Columbia (Kanada) mit Straßen, Gewässern und Grenzen entdecken. Es könnte dann etwa folgende räumliche Assoziationsregel gefunden werden:
is-a(X,town) -> close-to(X,Y) AND is-a(Y,water) (80%)

Diese Regel besagt, daß 80% der relevanten Städte einem Gewässer benachbart sind, d.h dass Städte in British Columbia im allgemeinen nahe bei einem See, einem Fluß oder am Meer liegen.

Ko-Lokationsmuster sind Muster raumbezogener Objete, die häufig zusammen in räumlicher Näher auftreten.

Ansätze:

• Statistische Ansätze: Bestimmung der räumlichen Korrelation zwischen zwei Klassen von Objekten
• Clustering-basierte Ansätze: Bestimmung der Überlappungsverhältnisse geclusterter Klassen
• Ansätze basierend auf Assoziationsregel-Mining
  • Daten-partitionierend: Erzeugen von Transaktionen basierend auf Datenpartitionierungen
  • Referenzfeature-basiert: Erzeugen einer Transaktionsdatenbank unter Nutzung ausgewählter Features als Transaktionsbasis
  • Ereigniszentriert: Nutzung eines Maßes für Häufungen auf Nachbarschaftsrelationen

• basieren auf Maß der räumlichen Überlappung von Clustern, die unabhängig voneinander pro Menge von Punkten mit Marken ermittelt wurden:
  • Aufteilen der Punkte X in disjunkte Mengen Xi , . . . , Xk basierend auf ihren Marken f1,...,fk.
  • Bestimmen der C1 , . . . , Ck für jede Punktmenge (beliebiger Clustering-Algorithmus)
  • Bestimmen der Ko-Lokationsmuster auf Basis der räumlichen Überlappung der Cluster

• basiert auf „Transaktionalisierung“ des räumlichen Objektraumes
  • Wähle ein Feature/Klasse als Transaktionsbasis
  • Generiere eine Transaktionsbasis basierend auf dem ausgewählten Featuretyp und der Nachbarschaftsrelation R
  • Ermittle häufige Itemsets (häufige Ko-Lokationsmuster) mittels Apriori
• nutzt globales Häufigkeitsmaß (minimaler Support): Ko-Lokationen mit signifikanten Korrelation aber geringen Häufigkeiten werden nicht gefunden

• erfordert keine Vorab-„Transaktionalisierung” des Objektraumes und benötigt keine globales Häufigkeitsmaß
• Musterinstanzen (Nachbarschaften) werden während des Mining-Prozesses durch Verbund mit bereits ermittelten Ko-Lokationen (Tabelleninstanzen)
• erfordert eine Nachbarschaftsrelation R auf der Menge der markierten Eingabepunkte X: definiert eine Menge {I1, . . . , Im} von R-Nachbarschafts-Cliquen
• zwei Nachbarschaftsrelationen Ii und Ij sind R-erreichbar, gdw. Ii ∪ Ij ist eine R-Nachbarschaft

• Flock (m > 1, r > 0): mind. m Entities befinden sich innerhalb einer kreisförmigen Region mit Radius r und bewegen sich in die gleiche Richtung
• Leadership (m > 1, r > 0, s > 0): mind. m Entities befinden sich innerhalb einer kreisförmigen Region mit Radius r, bewegen sich in die gleiche Richtung und mind. eine Entity hat sich schon seit s Zeitschritten in diese Richtung bewegt
• Convergence (m > 1, r > 0): mind. m Entities werden die gleiche kreisförmige Region mit Radius r passieren (Annahme: ihre Richtung bleibt erhalten)
• Encounter (m > 1, r > 0): mind. m Entities werden gleichzeitig in der gleichen kreisförmigen Region mit Radius r (Annahme: Beibehaltung von Geschwindigkeit und Richtung)

Menge von Objekten, die sich für ein längeres Zeitintervall nah zu einander bewegen (äquivalent zu Flocks). -> Folge von (Snapshot-)Clustern.

Basisalgorithmus:

1. Führe DBSCAN für jede Zeitscheibe aus

2. Für jedes Paar eines Clusters c und einen bewegten Cluster g prüfe, ob g durch c erweitert werden kann

• falls ja: nutze g in der nächsten Iteration
• sonst: Gib g als Ergebnis aus

Verbesserungen:

• Vermeiden von redundanten Überprüfungen (Schritt 2)
•  Reduzierung der Anzahl der DBSCANs (Schritt 1)

• Induktionsschleifen
  • Integriert in Fahrbahn
  • nur aggregierte Daten
• Kameras
  • Erkennung von Fahrzeugkennzeichen
• RFID
  • Transponder für Mautgebühren

• Welche Straßen sind zu welchen Zeiten besonders ausgelastet?
• An welchen Kreuzungen ist die Wahrscheinlichkeit von Staus am größten?
• Wann ist die beste Zeit, den Berliner Ring ohne Verkehrsbeeinträchtigungen zu befahren?
• Welche Route ist unter den gegebenen Bedingungen (Wetter, Verkehrslage, Zeit) in den nächsten Stunden am schnellsten?
• ....