Vergleich der Ansätze des Inkrementellen Lernen mit den Ideen des Online Data Mining Einführungspräsentation Steffen Ciupke Jörg Hipp

Vergleich der Ansätze des „Inkrementellen Lernen“ mit den Ideen des „Online Data Mining“

Einführungspräsentation

Steffen CiupkeJörg Hipp

Agenda

Inkrementelles LernenInkrementelles Lernen

Online Data MiningOnline Data Mining

AusblickAusblick

EinleitungEinleitung

Einleitung

Einsatzmöglichkeit inkrementeller Clustering Verfahren und Online Data Mining zur Klassifizierung von Telekommunikationsdaten

• Vergleich der Ansätze des inkrementellen Lernens und des Online Data Mining

• Vorstellung einiger Verfahren und der Anforderungen an die dabei verwendeten Algorithmen

• Evaluierung der Verfahren hinsichtlich möglicher Erweiterungen oder Kombinationsmöglichkeiten

Synthese beider Ansätze in Hinblick auf große DatenmengenZiel

Motivation und Charakteristika inkrementeller Lernverfahren

Inkrementelles Lernen

Charakteristika

• Verwendung einer Wissensbasis

• Effizienter Zugriff

• Einfache Updates bzw. Assimilation neuer Beobachtungen

Tradeoff: Cost vs. Quality

Motivation

• Zugriff auf Wissen - sporadisch- häufig

• Daten sollen bereits unmittelbar nach Beobachtung verwendbar sein


Mit inkrementellen Lernverfahren verbundene Probleme

Inhärente Unsicherheit hinsichtlich verschiedener Fragestellungen

Pro

ble

me

• Wie weit hängt das Ergebnis von der Reihenfolge der Beobachtungen ab?

• Sind lokale Restrukturierungen in der Wissensbasis ausreichend, um schlechte Anfangsentscheidungen auszugleichen?

• Stellt das Ergebnis ein (lokales) Minimum der Zielfunktion dar?


Überblick über Entwicklungen in diesem Bereich des Machine Learning um

• Unterschiedliche Ansätze in der Darstellung der Wissensbasis

• Verschiedene Umsetzungen des inkrementellen Aspekts

• Trends in der Performance der Verfahren

Auffinden der für die Klassifikationgroßer Datenmengen geeignete Verfahren oder Ansätze

Ziel

Kennen zu lernen.


Inkrementelles Lernen aus BeispielenConcept Learning System (CLS) [Hunt, Martin, Stone; 1966]

Vorgehen

• Nicht inkrementeller Aufbau eines Entscheidungsbaumes

• Erste Teilung entlang der Werte eines „best discriptive attribute“ Verwendung einer einfachen Häufigkeitsmessung

• Neue Beobachtungen werden bestehenden Klassen zugeordnet

• Bei einer Missklassifikation wird der gesamte Baum neu berechnet

„revolutionäres“ Verfahren

Kritik

• Keine eigenständige Klassifikation der Daten

• Vollständige Konsistenz

• Schlechte Performance wegen ständiger Neuberechnungen


Inkrementelles Lernen aus BeispielenAQ [Michalski; 1973]

Vorgehen

• Darstellung der Wissensbasis als „flache“ logische „Concept Descriptions“

• Nur ein Teil der Beobachtungen zur Neuberechnung „fehlerhafter“ Teile der Wissensbasis benutzt wird

• Verwendung einer Euklidischen Distanzmessung um „gute“ Repräsentanten der Konzepte zu erkennen

• Limitierung der Neuberechnung auf die Teile der Wissensbasis, die zu einer Missklassifikation geführt habenKritik


• Benötigt vollständige Konsistenz


Inkrementelles Lernen aus BeispielenSTAGGER [Schlimmer; 1987]

Vorgehen

• Darstellung der Wissensbasis als „flache“ logische „Concept Descriptions“ mit lokalen Reparaturen der Wissensbasis

• Benötigt keine vollständige Konsistenz der Daten keine abrupten Reparaturen nach jeder Missklassifikation

• Repräsentation der Konzepte als probabalistische Zusammenfassung wichtiger Subkomponenten

Effektiver Umgang mit statistischem Rauschen

Fähigkeit Umweltveränderungen zu erkennen


Inkrementelles Lernen aus BeispielenID4 [Fisher; 1986]

Vorgehen

• Weiterentwicklung von CLS

• Feinere Methode zur Auswahl des „best divisive attribute“

• Statt der kompletten Datenbasis, wird nur eine stochastische Zusammenfassung gespeichert

• Lokale Reparaturen an den Teilbäumen

Kritik



Incremental Conceptual Clustering

COBWEB [Fisher; 1987]

Vorgehen

• Eigenständige Entwicklung eines „Classification Tree“

• Integration neuer Beobachtungen entlang „best matching nodes“

• Speicherung einer statistischen Zusammenfassung in jedem Knoten (vgl. ID4)

• Evaluation Function basiert auf den Attributwerten aller BeobachtungenKritik

• Reihenfolgeabhängig

Methode, um verständliche Muster in Daten zu entdecken


Prinzipieller Unterschied zu nicht inkrementellen Clusteralgorithmen

• K-Means iteriert über gesamtem Datenbestand Verwendet Distanzmessung

• COBWEB arbeitet Datenbestand Instanz für Instanz ab Verwendet Wahrscheinlichkeiten/Häufigkeiten


Beim Incremental Conceptual Clustering wird bei jedem Schritt ein Baum gebildet, dessen Blätter die Instanzen und die Wurzel den gesamten Datenbestand repräsentierten.

Verfahren

• Updates Einfügen eines neuen Blattes Komplette Restrukturierung des Baumes

• Evaluation Function Category Utility misst die Gesamtqualität der Unterteilung Schlüssel für Entscheidung über Updates

• Restrukturierung Merge: Vereinigt zwei Subcluster Split: Ersetzt Knoten durch Söhne

inkrementelle Möglichkeit den Baum nach fehlerhaften Wahlentscheidungen zu restrukturieren


Beispiel für den Aufbau eines „Classification Tree“ mit „incremental conceptual clusering“


Erweiterungen des Incremental Conceptual Clustering Prinzips um nicht erwünschte Eigenschaften zu vermeiden

• Numerische Attribute Category Untility basiert auf Schätzung der Mittelwerte

und Varianz

ProblemKnoten enthält nur eine Instanz Varianz wird Null infinite Werte der CU

Lösung Verwendung einer Mindestvarianz Acuity stellt die Messungenauigkeit dar


Erweiterungen des Incremental Conceptual Clustering Prinzips um nicht erwünschte Eigenschaften zu vermeiden

Cluster enthalten ein Blatt für jede Instanz

undurchschaubar große Hierarchie

Overfitting

Cutoff unterdrückt das Wachstum der Hierarchie Wenn sich Instanzen ausreichend ähneln werden

sie zusammengefasst

Experimentieren mit Parametern um zufriedenstellende Ergebnisse zu erhalten


„Incremental Conceptual Clustering“ am Beispiel von COBWEB

N=NodeI=New Instance

N=NodeI=New Instance

An example ofprobabalistic concepts

An example ofprobabalistic concepts

Inkrementelles Lernen - Online Data Mining

Entsprechend dem Vorgehen beim Inkrementellen Lernen ist ein Online Verfahren zu bestimmen, anhand dessen eine Synthese der beiden Ansätze geprüft wird

• Definition und Abgrenzung des Themengebiets• Vorstellung Verfahren• Anforderungen an Algorithmen• Auswahl eines potentiell inkrementell erweiterbaren Verfahrens

Präsentationsteil Online Data Mining:

• Erweiterung des COBWEB um Elemente mit Online Behavior

Fortführung der Ergebnisse Präsentationsteil Inkrementelles Lernen:

Online Data Mining

Wesentliche Arbeit von 2 Forschungsgruppen• Prof. J.M. Hellerstein (UC Berkeley): CONTROL• J. Han (Simon Fraser, B.C.): OLAM

Definition „Online“: System stellt dem Nutzer in Echtzeit Informationen

über sowie die Möglichkeit der Einflußnahme auf eine Query während ihrer Abarbeitung zur

Vefügung(Online Behavior vs. "Batch Mode")

Notwendigkeit ergibt sich aus „no one perfect query“-Problematik

zentrale Lösungsansätze...Interaktivität

Intuitivität

...stellen nicht-triviale Anforderungenbei Anwendung auf großen Datenmengen

Grundlagen des Themengebiets

Online Data Mining

Die Lösungsansätze definieren das Lastenheft für die Anpassung bestehender Datenbankverfahren an die Onlinemethodik

Intuivität:... die Systemumgebung soll ein Erarbeiten und Überprüfen von

Hypothesen vereinfachen• explorative Datenanalyse:

Browsing / "Eyeballing" auf unterschiedlichen Abstraktionsebenen

• fuzzy Queries• Möglichkeit externes Wissen unkompliziert einzubringen

Interaktivität:• Kontinuierliche Ausgabe von Zwischenergebnissen (early returns)• zusätzliche Angaben bzgl. Exaktheit (Konfidenzintervalle)• Einflußmöglichkeiten auf Funktionsparameter (Query Refinement)• Kontrolle über Trade-Off Exaktheit Bearbeitungszeit

...während

derBearbeitung

Online Data Mining

Hellerstein: CONTROL-Project(Continous Output and Navigation Technology with Refinement Online)

Online Data Mining: Online Association Rules implementiert (CARMA)Forschungsansätze auch für andere Methoden (Clustering)

Online Enumeration: explorative Datenanalyse via Spreadsheets auf großen Datenmengen (Tool: ABC)

Online Aggregation: ermöglicht Interaktion während SQL Aggregation Query(Feedback möglich durch UDFs)

Optimierung der Zeitkomplexität der gesamten Datenanalyse- Sitzung (i.G. zur Optimierung einer einzelnen Iteration des Analyseprozeß')

im weiteren: Online Datenvisualisierung (CLOUDs)

Online Data Mining

Assoziationsregeln: CARMA (Continous Association Rule Mining Algorithm)2 Scans über Datenmenge1. Scan: vorläufige Ergebnisse zu Support und Konfidenz (inkl.

Konfidenzintervall) werden online ausgegeben und Grenzwerte sind interaktiv anpaßbar2.Scan: Feststellen des exakten Supports , Pruning

CONTROL-Methoden umgehen einige grundlegende Schwachstellenherkömmlicher Datenanalyseverfahren

Spreadsheets: ABC• Größenbeschränkungen (Bsp. Excel) werden aufgehoben• Exploration der Daten: Scrolling, Filtern, Sortieren• Abstraktion der Daten: Gruppierung

Umstrukturierung (Pivotieren)• Interpretation der Position des Scrollbar als fuzzy Query / Nutzerpräferenz

(für Online Reordering)

...ohne explizitesStellen einer

Query

Online Data Mining

CARMA

1. Scan :

firstTrans(): Transaktion zu der Itemset in Menge der potentiell

großen Itemsets hinzugenommen wird

count(): Anzahl des Vorkommen des Itemset nach firstTrans

maxMissed:() obere Schranke für Vorkommen vor firstTrans (in Abh. von bearbeiteter Datenmenge und supportSequence)

supportSequence: dynamische Speicherung der nutzerspezifizierten

Supportgrenzwerte

Ermöglicht Angabe einer oberen und unteren Schranke für Support

Online Data Mining

Realisierung der Nutzer-Interaktion via GUI (Bsp. Online Aggregation)

• Verfahren zur Bestimmungdes Konfidenzintervalls an bereits bearbeitete Datenmenge angepaßt

• ähnlicher Ansatz :WangUser Defined Aggregatesermöglichen ebenfallsearly returns

wesentliche Unterstützung durch Methodik...Online Reordering

Selektion der Datensätze nach Grad der „Interessantheit“(Nutzerpräferenzen)

Online Data Mining

Online Reordering: (Prefetch & Spool) zwischen dem reinen Auslesen der Daten und der aufgesetzten Applikation wird ein Reorder-Operator eingefügt

theoretisches Ziel: Überführung des ursprünglichen Datenstroms in permutierten, der Nutzerpräferenz entsprechenden Strom

•Ausnutzen des Komplexitäts-Vorteils von Produce ggü. Process

•Operator wählt Daten mit höchster Präferenz aus

• Spooling nichtpräferierter Daten auf Sidedisk

•Verwendung von Feedbackqualitätsfunktion(als Auswahlmetrik)

Online Data Mining

Alternativen zu Ansatz Hellerstein arbeiten mit Precomputation, d.h. Aufbereitung der Daten zu Data Cube

Han: Data Mining + OLAP = OLAM (Online Analytical Mining)

• DBMiner ermöglicht interaktive Anwendung von Data Mining Methoden (Clustering, Aggregation, Assoziations Regeln)

• Parallele Anwendung mehrerer Data Mining Funktionen + Interaktion zwischen diesen möglich

• Tool ermöglicht Data Exploration (interaktiv, flexibel, intuitiv, auf unterschiedlichen Abstraktionsebenen)

• Aufsetzen der OLAM-Anwendungen auf bestehende OLAP-Tools

Kritik: Interaktivität nur auf aufbereiteten Daten, d.h. Probleme (kein echtes Online Behavior) bei noch nicht vorab definierten Analysedimensionen

Online Data Mining

Blocking Algorithms: Scan der gesamten Datenmenge vor Ergebnisausgabe notwendig (Bsp. Sortierung)

Methoden für die umfangreiches Preprocessing notwendig ist

Anforderungen an verwendete Algorithmen um Online Behavior zu ermöglichen:

Anytime Algorithmen (entspr. Hellerstein): sinnvolle Näherungsergebnisse (inkl. Gütefunktionen) sind ab Beginn der Anwendung vefügbar

Ablauforganisation: Pipeline Processing

repräsentiert über Kostenfunktion (Bsp.): K(toutput, tdead) = atoutput + ebtdead

... fordert evtl. aber auch die Päferenz herkömmlicher Methodik (Batch Mode) bei zu hohen "Online-Kosten" !

Pro

ble

m

Ausblick

weiteres Vorgehen

• Vergleich der Ansätze Inkrementelles Lernen und Online Data Mining und der Anforderungen an die dabei verwendeten Algorithmen

• Evaluierung der Möglichkeit einer Erweiterung des Conceptual Clusterings um Elemente mit Online Behavior

• Prüfung der Vereinbarkeit von Online Association Rules mit Methoden des Inkrementellen Lernens

... dies soll jeweils mit Bezug zur konkreten Problemstellung unserer Telekommunikationsdaten geschehen

Synthese beider Ansätze in Hinblick auf große DatenmengenZiel

Fragen

Documents

Vergleich der Ansätze des Inkrementellen Lernen mit den Ideen des Online Data Mining Einführungspräsentation Steffen Ciupke Jörg Hipp