KDD (Kap 3: Klassische Data-Mining Verfahren)

Ja. Stratifikation.

Dieses Schema basiert auf einer Stratifikation ("Schichtenbildung") der Mengen von Itemsets. Dabei werden nicht mehr alle ltemsets einer bestimmten Länge k (wie beim Algorithmus Cumulate) auf einmal gezählt. Stattdessen wird, sozusagen in "Schichten", zuerst für die allgemeineren und nach und nach für die spezielleren Itemsets, sofern das dann noch nötig ist, der Support bestimmt.

Beispiel:

• Ck={{Kleidung,Schuhe},{Oberkleidung,Schuhe}, {Jacken, Schuhe}}
• zuerst den Support für {Kleidung,Schuhe} bestimmen
• nur dann den Support für {Oberkleidung,Schuhe} bestimmen, wenn {Kleidung,Schuhe} minimalen Support hat

Problem mit stratify:

-> falls sehr viele Itemsets mit kleiner Tiefe den minimalen Support haben: Ausschluss nur weniger Itemsets größerer Tiefe

Die Optimierungen von Cumulate bringen eine starke Effizienzverbesserung. Startifikation bringt nur noch einen kleinen zusätzlichen Vorteil. Die Optimierungen von Cumulate und Stratifikation können kombiniert werden.

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

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

• 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.

• 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!)

1. DB-Scan: Suche häufige 1-Itemsets
2. Sortiere Items nach absteigender Häufigkeit
3. Erneuter DB-Scan: Aufbau des FP-Trees

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

• 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
     

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

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.

• 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.

1. Bays-Klassifikatoren
2. Nächste-Nachbarn Klassifikatoren
3. Entscheidungsbaumklassifikatoren

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.

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.

Unter Clusteranalyse (Clustering-Algorithmus, gelegentlich auch: Ballungsanalyse) versteht man Verfahren zur Entdeckung von Ähnlichkeitsstrukturen in (großen) Datenbeständen. (-> Häufungspunkt von Objekten im multidimenstionalen Raum)

Die so gefundenen Gruppen von „ähnlichen“ Objekten werden als Cluster bezeichnet, die Gruppenzuordnung als Clustering. Die gefundenen Ähnlichkeitsgruppen können hierarchisch oder agglomerativ (dichtebasiert) sein, also Untergruppen oder Teilgruppen in Gruppen kennzeichnen.

Die Clusteranalyse ist eine wichtige Disziplin des Data-Mining, dem Analyseschritt des Knowledge Discovery in Databases Prozesses.

Clusterverfahren unterscheiden sich in

• dichtebasierte Verfahren
• hierarschische Verfahren

Identifikation einer endlichen Menge von Kategorien/Klassen (Clustern) um Daten so zu beschreiben, dass

(a) Objekte im gleichen Cluster möglichst ähnlich und

(b) Objekte aus verschiedenen Clustern möglichst unähnlich zueinander

sind

• Ähnlichkeitsbegriff
• Cluster unterschiedlicher Größe, Form und Dichte
• Cluster können hierarchisch ineinander verschachtelt sein

• Kundensegmentierung
  • Clustering der Kundentransaktionen
• Bestimmung von Benutzergruppen auf dem Web
  • Clustering der Web-Logs
• Strukturierung von großen Mengen von Textdokumenten
  • Hierarchisches Clustering der Textdokumente
• Erstellung von thematischen Karten aus Satellitenbildern
  • Clustering der aus den Rasterbildern gewonnenen Featurevektoren

Ähnlichkeit

Ein Maß für die „Nähe“ von Paaren von Objekten o1, o2 wird durch eine Distanzfunktion dist modelliert, die sich auf direkte oder abgeleitete Eigenschaften der Objekte stützt.

• kleine Distanzen = ähnliche Objekte
• große Distanzen = unähnliche Objekte

Clusteranalyse wird manchmal auch als „Distanzgruppierung“ bezeichnet

Die Güte einer Clusteranalyse hängt stark von der Adäquatheit der Distanzfunktion dist ab

• L-Metrik (Minkowski-Distanz)
• Euklidische Distanz
• Manhattan Distanz
• Maximums-Metrik

s. Abb.

Partitionierende Verfahren zerlegen eine Datenmenge in k Cluster, wobei gilt:

• jeder Cluster enthält mindestens ein Objekt
• jedes Objekt gehört genau zu einem Cluster

Voraussetzung ist, dass die Objekte Punkte in einem d-dimensionalen euklidischen Vektorraum sind. -> Verwendung der euklidischen Distanz für die Ähnlichkeit.

Zentroide:

Jeder Cluster wird durch seinen Zentroid repräsentiert. Zentroid eines Clusters ist anschaulich der Mittelwert aller Punkte des Clusters.

Das Ziel ist es, die Cluster so kompakt wie möglich zu bilden (s.Abb.). Die k Klassen werden so gebildet, dass die Varianz bezüglich der gegebenen Mittewerte minimal wird („Varianz minimierende Techniken“).

Der Algorithmus beginnt mit einer "initialen" Zerlegung der Datenmenge, üblicher- weise mit einer zufälligen Einteilung der Daten in k Klassen. Dann werden die Centroide dieser Klassen berechnet. Diese Einteilung ist im allgemeinen nicht optimal in dem Sinn, daß für einige Punkte der Abstand zum Centraid ihres Clusters größer ist als der Abstand zum Centraid eines anderen Clusters. Daher werden nun in einem ersten Schritt neue Klassen gebildet, indem jeder Punkt dem nächstliegenden Centroid zugeordnet wird. In einem zweiten Schritt werden dann die Centroide wieder- um neu berechnet. Auch diese Einteilung muss noch nicht "optimal" sein. Die beiden genannten Schritte werden daher solange wiederholt, bis sich die Cluster nicht mehr verändern. Abb. zeigt dieses Verfahren anband eines Beispiels.

Eigenschaften des Algorithmus:

• Konvergiert gegen ein (möglicherweise nur lokales) Minimum.
• Aufwand: O(k*n) für eine Iteration.
• Anzahl der Iterationen ist im allgemeinen klein (- 5 - 10).
• Anfälligkeit ggü. Rauschen/Ausreißern
• konvexe Form der Cluster
• Ergebnis und Laufzeit hängen stark von der initialen Zerlegung ab.

Die k-Means Methode ist eine Variante der Basismethode. SIe ist die bekannteste und am häufigsten angewendete partitionierende Clustering-Methode. Sie hat im Wesentlichen die gleichen Eigenschaften wie die obige Basismethode, ist aber zusätzlich noch stark reihenfolgeabhängig.

Der wesentliche Unterschied der k-means Methode zur Basismethode ist, daß in der Iteration des Algorithmus bei der Neuzuordnung der Punkte zu den Centroiden diese Centroide direkt aktualisiert werden, wenn ein Punkt seine Clusterzugehörigkeit ändert. Damit erübrigt sich der zweite Schritt, d.h. die separate, anschließende Neuberechnung der Centroide.

Wenn ein Punkt p vom Cluster C1 zum Cluster C2 wechselt, werden die Koordinaten der zugehörigen Centroide inkrementeil angepaßt.

Es gibt Methoden, die auf k-means aufsetzen (z.B. ISODATA) und die versuchen das Ergebnis zu verbessern. Dazu wird k-means mit Operationen wie Elimination sehr kleiner Cluster, Verschmelzung von Clustern und Split von Clustern in einem komplexen iterativen Prozeß kombiniert, bei dem der Benutzer allerdings sehr viele zusätzliche Parameter angeben muss (Nachteil).

Voraussetzung: Gegeben seien beliebige Objekte und eine beliebige Distanzfunktion zur Modellie- rung der Ähnlichkeit. Im einfachsten Fall genügt eine Distanzmatrix.

Medoide

Jeder Cluster C wird durch einen Medoid mc E C repräsentiert, welcher anschaulich das zentralste Objekt des Clusters darstellt. Ein Medoid ist, anders als ein Centroid, immer ein Objekt, welches auch in der Datenmenge vorkommt. Durch eine Menge von Medoiden M ist genau ein Clustering einer Datenmenge D dadurch gegeben, daß jedes Objekt demjenigen Medoid zugeordnet wird, zu dem es den geringsten Abstand hat.

Die Clustering-Verfahren, die auf der Auswahl repräsentativer Punkte zur Bestimmung eines Clustering beruhen, heißen auch "k-medoid-Verfahren".

Die Maße für die Kompaktheit von einzelnen Clustern und für die Kompaktheit eines gesamten Clustering sind ähnlich wie für das Clustering durch Varianzminimierung definiert. Üblicherweise wird jedoch bei k-medoid-Verfahren nicht die quadrierte Distanz zugrundegelegt, sondern nur die einfache Distanz zwischen Ob- jekten und dem Repräsentanten ihres Clusters.

Ziel:

Bestimmung von k Medoiden so, daß TD (Summe der Distanzen jedes Punktes zum Medoid bzw. zum Medoid seines Clusters) minimal ist. Anschaulich heißt dies, daß die durchschnittliche Distanz der Objekte zu ihren Repräsentanten minimiert wird.

Die Abb. veranschaulicht für die dargestellte Punktmenge eine schlechte und die optimale Auswahl von 3 Medoiden. Die Abstände zwischen den Punkten und dem Repräsentanten ihres Cluster sind als Strecken eingezeichnet. Damit wird der Wert TD für beide Clusterings anschaulich direkt durch die Summe der eingezeichneten Streckenlängen repräsentiert.

-------------------

Anders als beim k-means Clustering können Repräsentanten der Cluster nicht berechnet werden, sonden müssen geeignet aus der Datenmenge ausgewählt werden. Die k-medoid-Verfahren implementieren deshalb mehr oder weniger vollständige Suchverfahren, bei denen eine initiale Menge von Medoiden iterativ, durch Austauschen von Medoiden verbessert wird. Eine sehr umfangreiche Suche wird durch den Algorithmus PAM ("Partitioning Around Medoids") realisiert.

Anders als beim k-means Clustering können Repräsentanten der Cluster bei k-medoid Verfahren nicht berechnet werden, sonden müssen geeignet aus der Datenmenge ausgewählt werden. Die k-medoid-Verfahren implementieren deshalb mehr oder weniger vollständige Suchverfahren, bei denen eine initiale Menge von Medoiden iterativ, durch Austauschen von Medoiden verbessert wird. Eine sehr umfangreiche Suche wird durch den Algorithmus PAM ("Partitioning Around Medoids") realisiert.

Zu Beginn wählt der Algorithmus eine initiale Menge von Medoiden aus. Dazu wird als erster Medoid das zentralste Objekt in der gesamten Datenmenge D bestimmt, d.h. das Objekt, welches den Wert TD(D) minimiert. Nun werden nacheinander noch k-1 Medoide bestimmt. Dazu wird als nächster Medoid immer dasjenige Objekt o ausgewählt, bei dem der Wert für TD, bezüglich o und den schon vorher ausgewählten Medoiden, minimal ist.

Nach der Initialisierung wird nun der TD-Wert für jede mögliche Vertauschung eines Medoids mit einem anderen Objekt der Datenmenge (bis auf die gerade ausgewählten Medoide) berechnet. Wenn der kleinste der so entstehenden TD-Werte besser ist als der TD-Wert des aktuellen Clustering, dann wird die durch die entsprechende Vertauschung entstehende Menge von Medoiden zum aktuellen Clustering. Diese Schritte werden nun solange iteriert, bis sich der TD-Wert des aktuellen Clustering nicht mehr verbessern läßt.

Eigenschaften des Algorithmus:

• Greedy-Verfahren: Konvergiert gegen ein (möglicherweise nur lokales) Minimum
• Ergebnis und Laufzeit hängen nicht von der Reihenfolge, in der die Objekte gespeichert sind, ab (in Gegensatz zu K-Means).

Der Algorithmus PAM hat eine sehr hohe Laufzeit und ist daher nur für sehr kleine Datenmengen geeignet. Ng & Han schlagen deshalb den Algorithmus CLARANS ("Clusteling Large Applications based on RANdomized Search") vor, der wesentlich effizienter ist, dafür aber eine weniger gründliche Suche durchführt.

Der Algorithmus CLARANS hat gegenüber PAM zwei weitere Parameter: numlocal und maxneighbor, deren Werte vom Benutzer vorgegeben werden. Zum Ausgleich für eine weniger breite Suche wiederholt CLARANS die Suche nach "optimalen" Medoiden, ausgehend von verschiedenen Anfangskonfigurationen, numlocal mal und behält die jeweils beste Lösung. Diese Anfangskonfigurationen, d.h. die initialen Mengen von Medoiden werden, anders als bei PAM, zufällig bestimmt.

In der inneren while-Schleife wird dann versucht das aktuelle Clustering durch Vertauschen eines Medoids mit einem Nicht-Medoid zu verbessern. Im Gegensatz zu PAM wird dabei nicht nach dem Paar (Medoid, Nicht-Medoid) gesucht, das die größte Reduzierung von TD bewirkt. Stattdessen werden für ein aktuelles Clustering höchstens maxneighbor viele von zufällig ausgewählten Paaren (Medoid, Nicht- Medoid) betrachtet, und die erste Ersetzung, die überhaupt eine Reduzierung des TD-Wertes bewirkt, wird auch durchgeführt.
Mit der resultierenden, nun "aktuellen" Menge von Medoiden wird dann iterativ genauso verfahren, bis keine weitere Verbesserung des TD-Wertes mehr erzielt werden kann.

Eigenschaften des Algorithmus:

- Konvergiert gegen ein i.d.R. nur lokales Minimum

Zusammenfassend läßt sich sagen, daß CLARANS gegenüber PAM zu einer drastische Reduktion der Laufzeit bei einem vergleichsweise geringen Verlust an Qualität führt. Allerdings ist die Laufzeit von CLARANS in der Praxis immer noch nahezu quadratisch in der Anzahl der Objekte.

Bei den bisher vorgestellten Verfahren ist der Wert k für die Anzahl der Cluster vom Benutzer vorgegeben. In vielen Anwendungen ist jedoch die "richtige" Anzahl der Cluster unbekannt. Um ein gutes Clustering zu erhalten, ist also eine Methode erforderlich, mit der auch k richtig bestimmt werden kann. Eine oft angewendete Vorgehensweise ist die folgende:

1. Bestimme für k=2, ..., n-1 jeweils eine Partitionierung gemäß dem angewendeten Clusteringverfahren.
2. Wähle danach aus der Menge der Ergebnisse das "beste" Clustering aus.

Dazu benötigen wir allerdings ein Maß für die Güte eines Clusterings, da unabhängig von der Anzahl k der Cluster ist.

Der Wert für die Kompaktheit eines Clusterings, d.h. TD² bzw. TD beim k-means respektive beim k-medoid-Clustering, ist zum Vergleich von Clusterergebnissen bezüglich verschiedener Werte von k ungeeignet. Die Werte TD² und TD werden zwangsläufig kleiner, je größer der Wert von k ist. Das liegt daran, dass die Abstände von Objekten zu ihren Clusterrepräsentanten um so kleiner werden, je mehr Repräsentanten bestimmt werden.

Ein geeignetes Maß für die k-means- und k-medoid-Verfahren ist der sogenannte Silhouetten-Koeffizient eines Clustering.

Der Silhouetten-Koeffizient ist ein Maß für die Güte eines Clustering, das unabhängig von der Anzahl k der Cluster ist. Je größer also der Wert s(CM), desto besser ist das Clustering. Kaufman & Rousseeuw schlagen folgende Interpretation des Silhouetten-Koeffizienten vor:

• 0,70 < s(CM) ~ 1,00: starke Struktur,
• 0,50 < s( CM) ~ 0,70: brauchbare Struktur,
• 0,25 < s( CM) ~ 0,50: schwache Struktur,
• s( CM) ~ 0, 25 : keine Struktur.