KDD (Kap 3: Klassische Data-Mining Verfahren)
Lernkarteien zur "Knowledge Discovery in Databases (KDD)" Vorlesung bei Herrn Prof. Sattler, WS 2012/13 - TU Ilmenau. Dies ist Kapitel 3: Klassische Data-Mining Verfahren.
Lernkarteien zur "Knowledge Discovery in Databases (KDD)" Vorlesung bei Herrn Prof. Sattler, WS 2012/13 - TU Ilmenau. Dies ist Kapitel 3: Klassische Data-Mining Verfahren.
Fichier Détails
| Cartes-fiches | 53 |
|---|---|
| Langue | Deutsch |
| Catégorie | Informatique |
| Niveau | Université |
| Crée / Actualisé | 26.02.2013 / 01.02.2018 |
| Lien de web |
https://card2brain.ch/box/kdd_kap_3_klassische_datamining_verfahren
|
| Intégrer |
<iframe src="https://card2brain.ch/box/kdd_kap_3_klassische_datamining_verfahren/embed" width="780" height="150" scrolling="no" frameborder="0"></iframe>
|
(3.5) Wozu gibt es quantitative Assoziationsregeln? Erläutern Sie diese.
Das Finden von einfachen und auch von hierarchischen Assoziationsregeln in Transaktionsdatenbanken kann konzeptuell angesehen werden als das Finden von Assoziationen zwischen "1"-Werten in einer relationalen Tabelle, in der alle Attribute nur boolesche Werte annehmen können.
In vielen Bereichen der Wirtschaft und Wissenschaft haben die interessanten Daten, anders als einfache Transaktionen, Attribute mit numerischem (z.B. Alter, Ein- kommen) oder kategorischem Datentyp (z.B. Name, Wohnort). Boolesche Attribute können für diese Anwendungen als Spezialfälle von kategorischen Attributen angesehen werden.
Man möchte nun das Verfahren zum Finden von Assoziationsregeln in booleschen Datenbanken so anpassen, daß auch in Datenbanken mit reicheren Datentypen sogenannte "quantitative" Assoziationsregeln gefunden werden können. Regeln, die in solchen Datenbanken gelten, sind im allgemeinen inhaltlich sehr viel reicher als Assoziationsregeln in booleschen Datenbanken, wie beispielsweise die folgende Regel:
"<Alter: 30..39> und <Familienstand: verheiratet>=> <#Autos: 2>. (s. Abb)
Die Idee des hier vorgestellten Verfahrens beruht darauf, eine Datenbank mit numerischen und kategorischen Attributen so zu transformieren, daß ein ähnliches Verfahren wie für boolesche Datenbanken angewendet werden kann. Dazu werden die numerischen und kategorischen Attribute zunächst in einerneuen Tabelle auf boolesche Attribute abgebildet. Anschließend wird jeder Datensatz d der ursprünglichen Tabelle in einen Datensatz d' der booleschen Tabelle umgewandelt.
------
Lösungsansätze:
- Statische Diskretisierung
- Diskretisierung aller Attribute vor dem Bestimmen von Assoziationsregeln, z.B. mit Hilfe einer Konzepthierarchie pro Attribut
- Ersetzung numerischer Attributwerte durch Bereiche / Intervalle
- Dynamische Diskretisierung
- Diskretisierung der Attribute beim Bestimmen von Assoziationsregeln, Ziel z.B. Maximierung der Konfidenz
- Zusammenfassen „benachbarter“ Assoziationsregeln zu einer verallgemeinerten Regel
(3.5) Welche Probleme bestehen bei der Partionierung numerischer Attribute und welche Lösungen gibt es?
Probleme
- Minimaler Support: zu viele Intervalle -> zu kleiner Support für jedes einzelne Intervall
- Minimale Konfidenz: zu wenig Intervalle -> zu kleine Konfidenz der Regeln
Lösung
- Zerlegung des Wertebereichs in viele Intervalle
- Zusätzliche Berücksichtigung aller Bereiche, die durch Verschmelzen benachbarter Intervalle entstehen
- durchschnittlich O(n2) viele Bereiche, die einen bestimmten Wert enthalten
(3.5) Welche verschiedenen Assoziatsregeln gibt es und wie unterscheiden sie sich? (Zusammenfassung)
- einfache, hierarchische und quantitative Assoziationsregeln.
- Einfache Assoziationsregeln repräsentieren häufiges gemeinsames Auftreten von Elementen in Transaktionen wie beispielsweise oft gemeinsam gekaufte Waren in einer Menge von Warenkörben.
- Hierarchische Assoziationsregeln erweitern die einfachen Assoziationsregeln so, daß Beziehungen zwischen Kategorien von Elementen der Transaktionen, etwa zwischen Warengruppen, ausgedrückt werden können.
- Quantitative Assoziationsregeln übertragen die Idee der Assoziationen auf Datenbanken mit kategorischen und numerischen Attributen. Dort stellt eine Assoziationsregel Zusammenhänge zwischen Werten oder Wertintervallen verschiedener Attribute dar.
- Bei den Algorithmen zum Finden von Assoziationsregeln haben wir uns auf die wichtigsten Grundtypen beschränkt. Alle vorgestellten Algorithmen basieren auf dem sogenannten "Apriori-Algorithmus" zum Finden von Mengen häufig gemeinsam auftretender Items, der solche Mengen nach wachsender Größe konstruiert.
(3.6) Welche Verfahren ohne Kandidatengenerierung kennen Sie?
- Repräsentation der Transaktions-DB in einer komprimierten Form -> Frequent Pattern Tree (FP-Tree)
- komprimiert, aber vollständig
- vermeidet teure DB-Scans
- Algorithmen für Frequent-Pattern-Mining auf Basis des FP-Trees
- Divide-and-Conquer-Ansatz: Mining-Verfahren aus kleineren Teilschritten
- Vermeidung der Kandidatengenerierung
- (-> FP-Growth!)
(3.6) Erläutern Sie kurz die Konstuktion eines FP-Trees.
- DB-Scan: Suche häufige 1-Itemsets
- Sortiere Items nach absteigender Häufigkeit
- Erneuter DB-Scan: Aufbau des FP-Trees
(3.6) Was ist ein FP-Tree und welche Vorteile bietet es?
Ein FP-Baum ist eine kompakte Datenstruktur, die die Daten in Form eines Baums darstellt. Jede Transaktion wird gelesen und dann abgebildet auf einen Pfad im FP-Baum. Dies geschieht bis alle Transaktionen gelesen wurden. Verschiedene Transaktionen, die gemeinsame Untergruppen haben, erlauben es dass der Baum kompakt bleibt, weil sich ihre Wege überschneiden.
Vorteile:
- Vollständigkeit
- erhält vollständige Informationen für FP-Mining
- Kompaktheit
- reduziert irrrelevante Informationen (nichthäufige Items)
- geordnet nach absteigender Häufigkeit: häufige Items können im Baum oft gemeinsam repräsentiert werden
- kleiner als Original-DB (ohne Zeiger und Zähler)
- teilweise Komprimierungsfaktor bis 100
(3.6) Nach welchem Prinzip funktioniert Frequent Pattern Mining mit dem FP-Tree? Erläutern Sie die Methode kurz.
- Prinzip: Divide and Conquer
- rekursives Erweitern von Frequent-Pattern-Pfaden mit Hilfe des FP-Trees
- Methode
- für jedes Item: konstruiere zunächst Konditionale Musterbasis und anschließend konditionalen FP-Tree
- wiederhole Prozess für jeden neu erzeugten konditionalen FP-Tree
- bis resultierender FP-Tree leer ist oder nur einen Pfad enthält
(3.6) Erläutern Sie den FP-Growth Algorithmus.
Der FP-Growth-Algorithmus ist ein alternativer Algorithmus, welches verwendet wird um häufige Itemsets zu finden. Es ist unterscheidet sich vom Apriori Algorithmus dahingehend, als dass es einen FP-Baum verwendet (es geht in die Tiefe, nicht Breite), um den Datensatz zu kodieren und und die frequent Itemsets vom Baum zu extrahieren. FP-Growth ist schneller als Apriori, da
- keine Kandidatengenerierung, keine Kandidatentests
- kompakte Datenstruktur
- Vermeidung von wiederholten Datenbank-Scans
- Basisoperationen: Zählen und FP-Tree-Aufbau
(3.7) Was ist der Unterschied zwischen Clustering und Klassifikation? Welche Aufgabe hat Klassifikation?
Während beim Clustering die Klassen (Cluster) a priori unbekannt sind, sind bei der Klassifikation die in der Datenbank auftretenden Klassen schon bekannt.
Aufgabe der Klassifikation ist es, Objekte aufgrund ihrer Attributwerte einer der vorgegebenen Klassen zuzuordnen. Gegeben ist dazu eine Menge von Trainingsobjekten mit Attributwerten, die bereits einer Klasse zugeordnet sind. Mit Hilfe der Trainingsdaten soll eine Funktion gelernt werden, die andere Objekte mit unbekannter Klassenzugehörigkeit aufgrund ihrer Attributwerte einer der Klassen zuweist.
(3.7) In welche zwei Teilaufgaben lässt sich die Aufgabe der Klassifikation zerlegen?
- Zuordnung von Objekten zu einer Klasse
Hier geht es um die Fähigkeit, Objekteaufgrund ihrer Attributwerte irgendwie einer der Klassen zuzuordnen. Diese Teilaufgabe kann auch mit Hilfe von implizitem Wissen gelöst werden, d.h. mit den unverarbeiteten Trainingsdaten.
- Generierung von Klassifikationswissen
Im Unterschied zur ersten Teilaufgabe geht es hier um die Gewinnung von Erkenntnis, d.h. um die Generierung von explizitem Wissen über die Klassen. Streng genommen kann man eigentlich nur bei Erfüllung dieser zweiten Teilaufgabe von Knowledge Discovery reden.
(3.7) Welche drei wichtigen Ansätze/Verfahren zur Klassifikation kennen Sie?
- Bays-Klassifikatoren
- Nächste-Nachbarn Klassifikatoren
- Entscheidungsbaumklassifikatoren
(3.7) Was ist das besondere an Entscheidungsbaum-Klassifikatoren?
Nächste-Nachbarn-Klassifikatoren sind in vielen Anwendungen sehr effektiv und noch dazu effizient, liefern aber kein explizites Wissen über die Klassen. Entscheidungsbaum-Klassifikatoren dagegen finden solches explizites Wissen in der Form von Entscheidungsbäumen.
(3.7) Was ist ein Entscheiudungsbaum?
Ein Entscheidungsbaum ist ein Baum mit folgenden Eigenschaften:
- ein innerer Knoten repräsentiert ein Attribut,
- ein Blatt repräsentiert eine der Klassen,
- eine Kante repräsentiert einen Test auf dem Attribut des Vaterknotens.
Von den Tests, die sich auf ein gegebenes Attribut beziehen, ist immer genau einer erfolgreich. Der Entscheidungsbaum wird anband der Trainingsmenge konstruiert. Für zukünftige Objekte durchläuft man den Entscheidungsbaum von der Wurzel zu einem der Blätter entsprechend dem Ergebnis der den Kanten zugeordneten Tests und ordnet das Objekt der Klasse des erreichten Blatts zu.
