KDD (Kap 1&2: Einführung und Grundlagen)

Knowledge Discovery in Databases (KDD) ist der Prozess der (semi-) automatischen Extraktion von Wissen aus Datenbanken, das gültig, bisher unbekannt und potentiell nützlich ist

Erfassung und Speicherung großer Datenmengen

•Artikeldaten, Lagerbestände, Warenbewegungen, Lieferantendaten

•Kaufvorgänge, Kreditkartentransaktionen

•Kundenbefragungen

Datenauswertung mit dem Ziel

•Optimierung der Prozesse

•Verbesserung des Service

•Senkung der Kosten

automatisierte Beobachtung und Erfassung

•Himmelsteleskope

•Simulationsmodelle (Wetter, Erdbeben, . . . )

•Microarrays in der Genforschung

Produktion riesiger Datenbestände (GB/Stunde)

•manuelle Aufbereitung und Auswertung kaum möglich

Ziele einer Analyse

•Klassifikation / Segmentierung der Daten

•Erstellung von Hypothesen

KDD:

• Grundidee der Wissensentdeckung: Wissen aus Daten

• Einordnung: KDD ist iterativer Prozess, in welchem die Hypothesen des Data-Mining-Schritts verifiziert und/oder interpretiert werden

Data Mining

Data-Mining ist also ein bestimmter Teil von KDD. Es ist der Prozess der Entdeckung von bedeutungsvollen neuen Korrelationen, Pattern (Muster) und trends durch die Durchsuchung von großen Datenmengen aus Repositories mithilfe von Mustererkennungstechnologien als auch statistischen und mathematischen Techniken.

- keine Verifikation statistischer Annahmen

- „selbständige" Generierung von Hypothesen

KDD-Aufgaben

•Produkte, die häufig gemeinsam gekauft wurden

•Kriterien für Kreditwürdigkeit von Kunden

•Sterne oder Galaxien mit ähnlichen Merkmalen

•. . .

keine KDD-Aufgaben

•Suche bei google

•Verkaufszahlen einer CD im letzten Monat

•. . .

Ø Neue Herausforderungen:

○ Datenvolumen

○ Hohe Dimensionalität der Daten

○ Heterogenität

○ Verteilung

=>iterativer Prozess

○ Selektion: Auswahl von Daten einer Datenbasis

○ Vorverarbeitung: Störungen wie Datenfehler oder Unvollständigkeit suchen und entfernen (entfällt beim Data Warehousing)

○ Transformation: Quantität verringern

-> Attribute ohne oder mit geringem Vorkommen in der Datenbasis entfernen

-> in geeignete Analyseform umformen

○ Data Mining: Aufgabenspezifikation bestimmt das Data Mining Verfahren

○ Interpretation und Verifikation

„File Mining"

•Daten meist in Datenbanksystem (DBS)

•Data Mining bisher auf speziell vorbereiteten Files

Integration des Data Mining mit DBS

•Vermeidung von Redundanzen und Inkonsistenzen

•Nutzung der DBS-Funktionalität (z.B. Indexstrukturen)

Basisoperationen zum Data Mining

•Standard-Operationen für eine Klasse von KDD-Algorithmen

•effiziente DBS - Unterstützung

•schnellere Entwicklung neuer KDD-Algorithmen

•bessere Portabilität der Algorithmen

Integration von Daten aus unterschiedlichen Quellen

•einfache Übersetzungen von Attributnamen, z.B. KNr => KundenSchl

•Nutzen von Anwendungswissen um ähnliche Daten zusammenzufassen (z.B. regionale Zuordnung von Postleitzahlen)

Konsistenzprüfung

•Test anwendungsspezifischer Konsistenzbedingungen

•Bereinigung von Inkonsistenzen

Vervollständigung

•Ersetzen von unbekannten Attributwerten durch Defaults

•Verteilung der Attributwerte soll i.A. erhalten bleiben!

Diskretisierung numerischer Attribute

•unabhängig von der Data-Mining-Aufgabe z.B. Aufteilung des Wertebereichs in Intervalle gleicher Länge

•abhängig von der Data-Mining-Aufgabe z.B. Aufteilung in Intervalle so, dass der Informationsgewinn in Bezug auf die Klassenzugehörigkeit maximiert wird

Erzeugen abgeleiteter Attribute

•durch Aggregation über Mengen von Datensätzen z.B. von einzelnen Verkäufen zu „Tagesumsatz, Wochenumsatz, Monatsumsatz"

•durch Verknüpfung mehrerer Attribute z.B. Umsatzänderung = Umsatz 2005 - Umsatz 2004

Attribut-Selektion

•manuell:

•wenn Anwendungswissen über die Bedeutung der Attribute und über die gegebene Data-Mining-Aufgabe bekannt ist

•automatisch:

•Bottom-Up (ausgehend von der leeren Menge jeweils ein Attribut hinzufügen)

•Top-Down (ausgehend von der Gesamtmenge der Attribute jeweils ein Attribut entfernen) z.B. so, dass die Diskriminierung der Klassen optimiert wird

Problem

•zu viele Attribute führen zu Ineffizienz und evtl. Ineffektivität des Data Mining

•manche Transformationen können durch OLAP-Systeme realisiert werden

Data Mining ist die Anwendung effizienter Algorithmen, die die in der Datenbank enthaltenen Muster liefern

Prediktive Verfahren (Vorhersage):

-Nutzung von Merkmalen (Variablen) zur Vorhersage unbekannter oder zukünftiger Werte anderer Merkmale

-Beispiel: Klassifikation

Deskriptive Verfahren (Beschreibung):

-Extraktion von durch Menschen interpretierbare Muster, die die Daten beschreiben

-Beispiele: Assoziationsregeln, Clustering

Präsentation der gefundenen Muster: häufig durch entsprechende Visualisierungen

falls schlechte Bewertung (durch Benutzer):

•erneutes Data Mining mitanderen Parametern, anderem Verfahren, anderen Daten

falls gute Bewertung (durch Benutzer):

•Integration des gefundenen Wissens in die Wissensbasis

•Nutzung des neuen Wissens für zukünftige KDD-Prozesse

Bewertung der gefundenen Muster

•Vorhersagekraft der Muster

•Verwendete Daten sind Stichprobe aus der Grundgesamtheit aller Daten.

•Wie gut lassen sich die in diesen „Trainingsdaten" gefundenen Muster auf zukünftige Daten verallgemeinern?

•Vorhersagekraft wächst mit Größe und Repräsentativität der Stichprobe.

Interessantheit der Muster

•Muster schon bekannt?

•Muster überraschend?

•Muster für viele Fälle anwendbar?

Deskriptive Statistik

• beschreibende und graphische Aufbereitung von Daten (Mittelwert, Streuung)

• auch zur Validierung der Daten (Entdecken inkonsistenter Daten)

• Beispiel: „Nettomiete / Wohnfläche für Mietspiegel"

Explorative Statistik (hypothesen-generierende Statistik)

• Suche nach (unbekannten) Strukturen und Besonderheiten, wenn die Wahl eines geeigneten statistischen Modells unklar ist

• Was ist an einer Verteilung eines Merkmals bemerkenswert oder ungewöhnlich?

• keine Wahrscheinlichkeitsrechnung

Induktive Statistik (schließende Statistik)

• zieht aus den beobachteten Daten Schlüsse auf umfassendere Grundgesamtheiten

• Wahrscheinlichkeitstheorie liefert Grundlagen für Schätz- und Testverfahren

• Beispiel: „Wie gut kann man mit der durchschnittlichen Nettomiete aus einer Stichprobe die Durchschnittsmiete aller mietspiegelrelevanten Wohnungen vorhersagen?"

nominal: Unterscheidung von Werten

• Bsp.: ID, PLZ, Geschlecht

• Operationen: =, ≠

ordinal: Festlegung einer Ordnung für Werte

• Bsp.: Zensur, Rang, Rating

• Operationen: =, ≠, <, >

Intervall: Differenz von Werten

• Bsp.: Datum, Zeit

• Operationen: =, ≠, <, >, +, −

Ratio/Verhältnis

• Bsp.: Menge, Anzahl, Länge

• Operationen: =, ≠, <, >, +, −, *, /

diskrete Attribute

• endliche bzw. abzählbar unendliche Wertemenge

• Datentyp: meist integer

• Bsp.: Anzahl, Menge, PLZ, . . .

stetige bzw. kontinuierliche Attribute

• reellwertiger Wertebereich

• werden jedoch meist mit endlicher Anzahl von Stellen repräsentiert

• Datentyp: float, double, decimal

• Bsp.: Preis, Masse, Temperatur

Rauschen (noise)

• zufällige Störungen der Daten in einem (meist) uniformen Spektrum

Fehlende Werte

• Fehlen von Daten auf unterschiedlichen Ebenen

• Instanzebene: Werte, Datensätze, Teilrelationen, . . .

• Schemaebene: Attribute, . . .

• Probleme speziell auf Instanzebene:

• Behandlung von Nullwerten: fehlender Wert, Defaultwert oder nicht anwendbarer Wert?

• Verwerfen oder Ersetzen (bei Erhaltung der Verteilung)

Ausreißer

• Ausreißer: Wert, der nicht in eine erwartete Messreihe passt

• Aspekte:

• Erkennung: Verteilung, „Geometrie", Zeitreihe

• Interpretation: Mess- bzw. Datenfehler oder echtes Ereignis?

Duplikate

• Duplikate: Datenobjekte, die das gleiche Real-Welt-Objekt repräsentieren

• exakte Duplikate: in SQL trivial

select distinct ... from ...

Data Warehouse := dauerhafte

integrierte Sammlung von Daten

aus unterschiedlichen Quellen

zum Zweck der Analyse bzw. Entscheidungsunterstützung

• Klassifikation
  • Zuordnung v. Objekten zu verschiedenen vorgegebenen Klassen, d.h. Vorhersage von Merkmalen (Klassenzuordnung) anhand anderer Merkmale
• Assoziationsregeln
  • Aufdeckung statistischer Zusammenhänge zw. Variablen (Modell: Ass.regeln oder "Frequent ItemSets"; Bsp: Warenkorbanalyse)
• Clustering
  • Einordnung ähnlicher Objekte in neu gebildete Gruppen, sodass a) Ähnlichkeit innerhalb einer Gruppe möglichst groß und b) Ähnlichkeit zwischen Gruppen möglichst gering
• Sequenzanalyse
  • Suche nach häufig auftretenden Episoden oder Ereignisfolgen in Datenbeständen mit (zeitlicher) Ordnung (Bsp: zeitliches Kaufverhalten, wie Harry Potter DVD -> Harry Potter Buch)
• Graph Mining
  • Analyse sozialer Netzwerke: Freundschaftsbeziehungen in sozialen Netzen wie Facebook, Twitter-Follower...; auffinden von Communities: Gruppen mit starken innerem Zusammenhang + Identifizieren von Autoritäten (wichtige Knoten/Peers im Netzw.)
• Stream Mining
  • Analyse von kontinuierlichen, mit der Zeit variierenen und potenziell unbeschränkten Folgen von Datensätzen
• Spatio-Temporal Mining
  • Analyse von Daten mit räumlichem und/o. zeitlichem Bezug (zB Stauzonen in Verkehrsnetzen)

Erkennen & Beseitigen von Inkonsistenzen, Widersprüchen und Fehlern in Daten mit dem Ziel der Qualitätsverbesserung

• satzorientierte Daten (Menge von Sätzen (Records) mit fester Attributmenge)
• Dokumentdaten (Dokumentrepräsentation als Vektor)
• Transaktionsdaten (spezielle Form satzorientierter Daten - Datensatz entspricht Transaktion aus Transaktions-ID und Menge von Elementen (Items))
• Graphdaten (Graphstruktur, zB Web-Dokumente mit HTML-Links)
• Ordnungsbasierte Daten (geordnete Folge von Elementen, zB Alarmmeldungen, Weblogs, Gensequenzen..)