KDD (Kap 3: Klassische Data-Mining Verfahren)

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

Cluster können auch als Gebiete im d-dimensionalen Raum angesehen werden in denen die Objekte dicht beieinander liegen, getrennt durch Gebiete, in denen die Objekte weniger dicht liegen. Dichtebasierte Clusteringverfahren versuchen solche dichten Gebiete im Raum zu identifizieren.

Grundidee für einen dichtebasierten Cluster ist, daß die lokale Punktdichte bei jedem Objekt innerhalb des Clusters einen gegebenen Grenzwert überschreitet. Die lokale Punktdichte eines Objekts o ist dabei gegeben durch die Anzahl der Objekte in einer festgelegten Umgebung um das Objekt o. Ferner ist die Menge von Punkten, die den Cluster ausmacht, auch räumlich zusammenhängend.

Diese Grundidee für dichtebasierte Cluster kann formal präzisiert werden. Dazu werden zunächst die Begriffe Kernpunkt, Dichte-Erreichbarkeif und Dichte-Verbundenheit definiert.

Kernobjekt

Ein Objekt o ist also Kernobjekt, wenn in seiner epsilon-Umgebung mindestens MinPts viele Objekte liegen. Die Werte epsilon und MinPts sind dabei Parameter, die einen minimalen Dichtegrenzwert spezifizieren.

Objekte, die keine Kernobjekte sind, können zu einem Cluster gehören oder auch nicht. Im ersten Fall heißen sie Randobjekte, im zweiten Fall gehören sie zum sogenannten Rauschen.

(Direkt-) Dichte-Erreichbarkeit

Alle Objekte, die in der epsilon-Umgebung eines Kernobjekts p liegen, sind direkt dichte-erreichbar von p.

Ein Objekt p ist dichte-erreichbar von q, wenn es anschaulich gesprochen eine Kette von direkt erreichbaren Objekten zwischen q und p gibt (siehe Abb.). Alle Objekte in dieser Kette außer eventuell p sind dabei notwendigerweise Kernobjekte.

Ketten von dichte-erreichbaren Objekten sind anschaulich Teile von Clustern, einschließlich der Randpunkte. Um die Zusammengehörigkeit verschiedener solcher Ketten formal zu fassen, benötigt man den Begriff der Dichte-Verbundenheit.

Dichte-Verbundenheit

Grob gesagt sind zwei Objekte p und q dichte-verbunden, wenn sie beide von einem dritten Objekt o aus dichte-erreichbar sind (bezüglich der gleichen Dichteparameter). S.Abb. Man kann auch sagen, daß p und q dann über o dichte-verbunden sind.

Das verbindende Objekt o muß natürlich nicht in jedem Fall verschieden von p oder q sein. Wie man leicht einsieht, gilt beispielsweise auch, daß zwei direkt dichte-erreichbare Objekte p und q miteinander dichte-verbunden sind (etwa über q).

Vereinfacht gesagt ist ein Cluster C eine Menge von Objekten, die alle miteinander dichte-verbunden sind, und alle Objekte, die überhaupt von irgendeinem Kernpunkt des Clusters aus dichte-erreichbar sind, gehören auch schon zum Cluster.

Für dichte-basierte Cluster gilt eine wichtige Eigenschaft, die einen einfachen Algorithmus zur Bestimmung aller dichte-basierten Cluster in der Menge von Objekten 0 rechtfertigt: Lemma1.

Lemma 1 besagt, daß man einen Cluster C dadurch finden kann, daß man ausgehend von einem beliebigen Kernobjekt aus C alle dichte-erreichbaren Objekte aufsammelt. Die Menge dieser Objekte ist schon gleich dem gesamten Cluster C.

DBScan (Dichtebasierte räumliche Clusteranalyse mit Rauschen) ist ein Data-Mining-Algorithmus zur Clusteranalyse. Der Algorithmus arbeitet dichtebasiert und ist in der Lage, mehrere Cluster zu erkennen. Rauschpunkte werden dabei ignoriert und separat zurückgeliefert.

Die Grundidee des Algorithmus ist der Begriff der „Dichteverbundenheit“. Zwei Objekte gelten als dichte-verbunden, wenn es eine Kette von dichten Objekten („Kernobjekte“, mit mehr als minPts Nachbarn) gibt, die diese Punkte miteinander verbinden. Die durch dieselben Kernobjekte miteinander verbundenen Objekte bilden einen „Cluster“. Objekte, die nicht Teil eines dichte-verbundenen Clusters sind, werden als „Rauschen“ (Noise) bezeichnet.
In DBSCAN gibt es drei Arten von Punkten:

• Kernobjekte, welche selbst dicht sind.
• Dichte-erreichbare Objekte. Dies sind Objekte, die zwar von einem Kernobjekt des Clusters erreicht werden können, selbst aber nicht dicht sind. Anschaulich bilden diese den Rand eines Clusters.
• Rauschpunkte, die weder dicht, noch dichte-erreichbar sind.

Der Algorithmus verfügt über zwei Parameter: epsilon und "minPts". Dabei definiert epsilon die Nachbarschaftslänge eines Punktes: Von einem Punkt erreichbar ist ein zweiter Punkt genau dann, wenn sein Abstand kleiner als epsilon ist. "minPts" definiert dagegen, wann ein Objekt dicht (d.h. ein Kernobjekt) ist: wenn es mindestens minPts epsilon-erreichbare Nachbarn hat.

Dichte-erreichbare Punkte können von mehr als einem Cluster dichte-erreichbar sein. Diese Punkte werden von dem Algorithmus nicht-deterministisch einem der möglichen Cluster zugeordnet. Dies impliziert auch, dass Dichteverbundenheit nicht transitiv ist; Dichte-Erreichbarkeit ist nicht symmetrisch.

DBSCAN ist exakt in Bezug auf die Definition von dichte-verbunden und Noise. Das bedeutet, zwei dichte-verbundene Objekte sind garantiert im selben Cluster, während Rauschobjekte sicher in Noise sind. Nicht exakt ist der Algorithmus bei nur dichte-erreichbaren Clustern, diese werden nur einem Cluster zugeordnet, nicht allen möglichen.

Im Gegensatz beispielsweise zum K-Means-Algorithmus, muss nicht im vornherein bekannt sein, wie viele Cluster existieren.

Der Algorithmus kann Cluster beliebiger Form (z.B. nicht nur kugelförmige) erkennen.

DBSCAN ist weitgehend deterministisch und reihenfolgeunabhängig: Unabhängig davon, in welcher Reihenfolge Objekte in der Datenbank abgelegt oder verarbeitet werden, entstehen dieselben Cluster (mit der Ausnahme der nur dichte-erreichbaren Nicht-Kern-Objekte und der Cluster-Nummerierung).

Der Algorithmus kann mit beliebigen Distanzfunktionen und Ähnlichkeitsmaßen verwendet werden. Im Gegensatz zum K-Means-Algorithmus ist kein geometrischer Raum notwendig, da kein Mittelpunkt berechnet werden muss.

DBSCAN selbst ist von linearer Komplexität. Jedes Objekt wird im Wesentlichen nur ein mal besucht. Jedoch ist die Berechnung der epsilon-Nachbarschaft im Regelfall nicht in konstanter Zeit möglich (ohne entsprechende Vorberechnungen). Ohne die Verwendung von vorberechneten Daten oder einer geeigneten Indexstruktur ist der Algorithmus also von quadratischer Komplexität.

Dichte-basiertes Clustering kann zwar- im Gegensatz zu den bisher dargestellten partitiouierenden Verfahren - Cluster beliebiger Form finden, und das, ohne die Anzahl der Cluster im Voraus zu kennen. Jedoch gibt es auch hier viele mögliche Charakteristika in den Daten, bei denen ein sinnvolle dichte-basiertes Clustering schwierig oder sogar unmöglich ist. Problemati eh sind insbesondere die folgenden Fälle, die auch gemeinsam auftreten können:

• hierarchische Cluster,
• stark unterschiedliche Dichte in verschiedenen Bereichen des Raumes,
• Cluster und Rauschen sind nicht gut getrennt.

Die Abb. zeigt ein Beispiel einer Datenmenge mit all diesen Charakteristika. In ei- nem Fall wie diesem ist es nicht nur "schwierig", die Parameter zu bestimmen, sondern die "richtigen" Parameter existieren gar nicht. Wie der 3-Distanz-Graph zeigt, gibt es auch so etwas wie "das erste Tal" im Graphen gar nicht. Wegen der hierarchischen Struktur der Daten gibt es aber auch keine globalen Dichteparameter, bei denen alle vorhandenen Cluster gefunden werden können. Abhängig davon, welchen Wert man für epsilon wählt, erhält man unterschiedliche Teilmengen der Cluster als Ergebnis. Verschiedene Werte und die resultierenden Ergebnisse sind in der Graphik durch unterschiedlich beschriftete Pfeile dargestellt.

Im Gegensatz zu partitionierenden Verfahren erzeugen hierarchische Clusteringverfahren keine einfache Zerlegung der Datenmenge, sondern eine hierarchische Repräsentation der Daten, aus der man eine Clusterstruktur ableiten kann.

Assoziationsregeln sind ein Mittel zur sogenannten Warenkorbanalyse. Gegeben ist dabei eine Datenbank von "Warenkörben", die gewisse Kundentransaktionen repräsentieren. Ein einzelner Warenkorb ist im weitesten Sinn eine Menge von zusammen eingekauften oder angeforderten Artikeln, Dienstleistungen oder Informationen eines Anbieters.

Assoziationsregeln drücken Zusammenhänge innerhalb der Transaktionen aus, die in der gesamten Datenmenge häufig vorkommen. Im Supermarkt-Beispiel könnten Zusammenhänge zwischen häufig gemeinsam gekauften Artikeln etwa durch Regeln der folgenden Art ausgedrückt werden: "{Mehl, Eier} -> {Butter}". Diese Regel "gilt", wenn in allen Warenkörben, die schon Mehl und Eier enthalten, häufig auch noch Butter enthalten ist. Diese Regel wäre natürlich nur dann interessant, wenn genügend viele Warenkörbe sowohl Mehl und Eier als auch Butter enthalten.

Das Wissen um solche Zusammenhänge kann auf vielfaltige Weise angewendet werden, beispielsweise für effizienteres Cross Marketing, für gezieltere Attached Mailings.Add-on Sales, für verbessertes Katalog-Design und Laden-Layout, oder etwa auch für eine automatische Kundensegmentierung anhand von gemeinsamem, durch Assoziationsregeln ausgedrücktem Einkaufsverhalten.

Für eine Menge von Items ist der Support der Menge X in D definiert als der Anteil der Transaktionen in D, die X enthalten. Der Support einer Menge X ist also die relative Häufigkeit, mit der die in X vorkommenden Waren zusammen gekauft wurden.

Der Support s einer Assoziationsregel X -> Y in D ist der Support der Vereinigung X u Y in D, das heißt die relative Häufigkeit des gemeinsamen Auftretens aller Items oder Waren, die in der Assoziationsregel vorkommen.

Die Konfidenz c einer Assoziationsregel X -> Y in D ist definiert als der Anteil der Transaktionen, die die Menge Y enthalten, in der Teilmenge aller Transaktionen aus D, welche die Menge X enthalten.

Man kann auch sagen, eine Assoziationsregel X->Y gilt mit der Konfidenz c in der Menge D von Transaktionen, wenn c% aller Transaktionen in D, die X enthalten, auch Y enthalten.

Noch anders gesagt ist die Konfidenz einer Regel die bedingte Wahrscheinlichkeit dafür, daß eine Transaktion T alle ltems der Menge Y enthält, unter der Bedingung, dass T schon alle Items aus der Menge X enthält.

Die Aufgabenstellung bezüglich einer gegebenen Menge von Transaktionen D besteht nun darin, alle Assoziationsregeln zu finden, die einen Support und eine Konfidenz in D haben, welche größer sind als benutzerspezifizierte Werte minsup beziehungsweise minconf. Diese Aufgabe kann in zwei Teilaufgaben zerlegt werden:
1. Finde alle Mengen von Items (d.h. alle Itemsets), die einen Support über dem benutzerspezifizierten minimalen Support haben. Diese ltemsets werden häufig auftretende ltemsets oder auch Frequent ltemsets genannt.
Ein "naiver" Algorithmus müsste dazu die Häufigkeit aller k-elementigen Teilmengen von I (der Menge aller Items) in der Transaktionsdatenbank D zählen.
Ein solches Vorgehen ist aber im allgemeinen zu aufwendig, da es 2^m solcher Teilmengen gibt und m in praktischen Anwendungen sehr groß sein kann.

Der Apriori-Algorithmus basiert jedoch auf einer Monotonie-Eigenschaft für häufig auftretende Itemsets, durch die die Anzahl der zu zählenden Teilmengen von I stark eingeschränkt werden kann.
2. Verwende die häufig auftretenden Itemsets, um Assoziationsregeln zu bilden und diejenigen Regeln auszuwählen, die die minimale Konfidenz haben. Wenn ein Itemset X häufig auftritt, dann ergibt jede Teilmenge A von X eine Regel der Form A -> ( X - A), die minimalen Support hat. Man muß dann noch feststellen, ob eine solche Regel zusätzlich die minimale Konfidenz hat.

Der Apriori-Algorithmus zum Finden der häufig auftretenden ltemsets basiert auf der folgenden Monotonie-Eigenschaft für häufig auftretende Itemsets:

Jede Teilmenge eines häufig auftretenden Itemsets muß selbst auch häufig sein.

Um diese Eigenschaft auszunutzen, müssen die häufig auftretenden Itemsets der Größe nach bestimmt werden, das heißt es müssen zuerst die einelementigen Frequent ltemsets bestimmt werden, dann die zweielementigen und so weiter.
Die häufig auftretenden einelementigen Itemsets können durch einfaches Zählen der Vorkommnisse jedes ltems in der Datenbank bestimmt werden. Im nächsten Schritt brauchen dann nicht mehr alle möglichen zweielementigen Teilmengen von I durchgezählt werden, sondern nur solche, die durch Kombination von zwei häufig auftretenden Items gebildet werden können.

Allgemein werden zum Finden von k+1-elementigen Frequent Itemsets nur solche k+1-elementigen Teilmengen gezählt, die durch einen "Join" (vgl. Abschnitt 2.1.3, relationale Datenbanksprachen) von k-elementigen Itemsets gebildet werden können, von denen man schon weiß, daß sie häufig in der Datenbank vorkommen.

Der Algorithmus durchläuft mehrmals die Datenmenge, solange bis bei einer bestimmten Länge keine Frequent Itemsets mehr gefunden werden können. Lk bezeichnet dabei die Menge aller häufig vorkommenden Itemsets der Länge k, und Ck bezeichnet die zu zählenden Kandidaten-ltemsets der Länge k.
Im ersten Schritt werden die einelementigen Itemsets bestimmt, die minimalen Support haben. In allen folgenden Durchläufen werden aus den im jeweils vorhergehenden Durchlauf bestimmten häufig auftretenden Itemsets (mit k-1 Elementen) neue Kandidaten-Iternsets (mit k Elementen) gebildet.
Der Support dieser Kandidaten wird gezählt, indem für jede Transaktion Tin der Datenbank (mit Hilfe der Subset-Funktion) geprüft wird, welche der aktuellen Kandidaten in Tenthalten sind. Für diese Kandidaten-Itemsets c wird der Zähler c.count, der den Support für c zählt, um eins erhöht.

Anschließend werden aus den Kandidaten diejenigen Itemsets für den nächsten Durchlauf ausgewählt, die minimalen Support haben. Dies sind gleichzeitig die Frequent ltemsets der Länge k.

Die Kandidatengenerierung ist das Kernstück des Apriori-Algorithmus. Die Menge der in einem Durchlauf gebildeten Kandidaten-Itemsets der Länge k muß erstens eine Obermenge zur Menge aller häufig auftretenden lte1nsets mit k Elementen sein, und zweitens sollte sie im allgemeinen wesentlich kleiner als die Menge aller k-elementigen Teilmengen von I sein.
Die Kandidaten der Länge k+1 werden in zwei Schritten gebildet, wobei vorausgesetzt wird, daß die ltems in den Itemsets lexikographisch sortiert sind.

Im ersten Schritt ("Join") wird ein Join der k-elementigen Frequent Itemsets mit sich selbst durchgeführt. Anschaulich wird dabei jedes k-elementige Frequent Itemset p jeweils um das letzte ltem aller k-elementigen Frequent Itemsets q verlängert, welche mit p in den ersten k-1 ltems übereinstimmen. Die Abb. illustriert diesen Schritt anhand eines Beispiels.

Im zweiten Schritt ("Pruning") werden aus der Menge der im Join-Schritt generierten Kandidaten alle Itemsets entfernt, welche eine k-1-elementige Teilmenge enthalten, die nicht auch in der Menge der k-1-elementigen Frequent Itemsets vorkommt.

s.Abb.

Die Subset-Funktion im Apriori-Algorithmus muß für jede Transaktion T in der Datenbank und jede Kandidatenmenge Ck alle diejenigen Kandidaten in Ck finden, die in T enthalten sind. Um diese Operation effizient durchzuführen, werden die Kandidaten aus Ck in einem Hash-Baum mit folgender Struktur organisiert.
Voraussetzung ist wieder, daß die Items sowohl in den Kandidaten-ltemsets des Hash-Baums als auch in den Transaktionen der Datenbank lexikographisch sortiert sind.

Struktur des Hash-Baums:

Ein innerer Knoten besteht aus einer Hasbtabelle bezüglich einer Hashfunktion h, in der jedes Bucket einen Verweis auf einen Sohnknoten enthält. Ein Blattknoten enthält eine Liste von ltemsets. Die Wurzel des Hash-Baums befindet sich auf Level 1. Ein innerer Knoten auf Level d verweist auf Knoten des Levels d+1.

Zählen des Supports mit Hashtabelle [Park, Chen & Yu 1995]

• Hashtabelle statt Hashbaum zum Bestimmen des Supports
• k-Itemset, dessen Bucket einen Zähler < minsup hat, kann nicht häufig auftreten

-> effizienterer Zugriff auf Kandidaten, aber ungenaue Zählung

Reduktion der Transaktionen [Agrawal & Srikant 1994]

• eine Transaktion, die keinen Frequent k-Itemset enthält, wird nicht mehr benötigt
• entferne solche Transaktionen für weitere Phasen aus der Datenbank

-> effizienterer Datenbank-Scan, aber vorher neues Schreiben der Datenbank

Partitionierung der Datenbank [Savasere, Omiecinski & Navathe 1995]

• ein Itemset ist nur dann häufig, wenn er in mindestens einer Partition häufig ist
• bilde hauptspeicherresidente Partitionen der Datenbank

-> viel effizienter auf Partitionen, aber aufwändige Kombination der Teilergebnisse

Sampling [Toivonen 1996]

• Anwendung des gesamten Algorithmus auf ein Sample
• Zählen der gefundenen häufigen Itemsets auf der gesamten Datenbank
• Festellen evtl. weiterer Kandidaten und Zählen auf der gesamten Datenbank

• Traversierung des Itemset-Gitters: vom Allgemeinen zum Spezifischen bzw. umgekehrt
• Traversierung des Itemset-Gitters: Breitensuche vs. Tiefensuche
• Repräsentation der Datenbank: horizontal vs. vertikal
  • Eclat: vertikale Repräsentation der Transaktionslisten -> weniger DB-Scans.

?

Aufgrund der Monotonie-Eigenschaft:

• "Jede Teilmenge eines häufig auftretenden Itemsets ist selbst auch häufig."

• Es gibt zu viele Frequent Itemsets -> Effizienzproblem (durch große Datenmengen)
• Es gibt zu viele Assoziationsregeln -> Evaluationsproblem

Manchmal sind diese Constraints (an die Frequent Itemsets) a priori bekannt, z.B.:

• "nur Assoziationsregeln mit Produkt A aber ohne Produkt B"
• "nur Assoziationsregeln mit Gesamtpreis > 100 der enthaltenen Produkte"

• Domain Constraint
• Aggregations Constraint

• bei der Bestimmung der Assoziationsregeln
  • löst das Evaluationsproblem
  • nicht aber das Effiienzproblem
• bei der Bestimmung der häufig auftretenden Itemsets
  • löst evtl. auch das Effizienzproblem
  • Frage bei der Kandidatengenerierung: welche Itemsets kann man mit Hilfe der Contraints ausschließen?

In praktischen Anwendungen von einfachen Assoziationsregeln entsprechen die ltems in den Transaktionen meist einzelnen Waren auf Bar-Code-Level. Im Allgemeinen haben jedoch Assoziationsregeln mit mehreren Items auf Bar-Code-Level nur einen sehr geringen Support, so daß in diesen Anwendungen keine wirklich nützlichen Ergebnisse gefunden werden können. Das heißt:

• Mit hohem minimalem Support findet der Apriori-Algorithmus nur sehr wenige einfache Assoziationsregeln.
• Mit niedrigerem minimalem Support findet der Apriori-Algorithmus eine sehr große und daher unüberschaubare Menge von Regeln.

Oftmals stehen in solchen praktischen Anwendungen jedoch zusätzlich ltem-Taxonomien (is-a Hierarchien) zur Verfügung, welche die Items hierarchisch in Warengruppen zusammenfassen. Diese Taxonomien möchte man nun verwenden, um auch Assoziationen zwischen abstrakteren Items, d.h. zwischen Warengruppen, zu finden. Solche Regeln sind meist nicht nur interessanter, sondern umfassen auch eine größere Anzahl von Items, da Itemsets auf Warengruppen-Ebene im allgemeinen einen höheren Support haben. Die Abb. zeigt beispielhaft eine Item-Taxonomie für Bekleidungsartikel; die Pfeile auf dem untersten Level verweisen dabei auf konkrete Artikel, die in der Abbildung nicht mehr angegeben sind.

Grundidee für einen Basisalgorithmus

Die häufig auftretenden Itemsets für hierarchische Assoziationsregeln werden im Prinzip wie die Frequent ltemsets für einfache Assoziationsregeln gefunden, d.h. mit einem dem Apriori-Algorithmus sehr ähnlichen Verfahren.

Die einfachste Möglichkeit besteht darin, die Transaktionen der Datenbank um alle Vorfahren von enthaltenen ltems zu erweitern. Dazu wird jedes Item in einer Transaktion T zusammen mit all seinen Vorfahren bezüglich H in eine neue Transaktion T' eingefügt, ohne Duplikate zuzulassen. Damit gilt dann, dass eine ursprüngliche Transaktion T eine Menge von Items X unterstützt, wenn die erweiterte Transaktion T die Menge X enthält. Auf diese Weise hat man die Aufgabe auf das Finden von Frequent Itemsets für einfache Assoziationsregeln reduziert. Entsprechend weicht der folgende Basisalgorithmus nur durch die Erweiterung der Transaktionen vor der Zählung von Kandidaten-Itemsets vom Apriori-Algorithmus ab.

Der naive Algorithmus Basic kann durch die folgenden Techniken noch wesentlich verbessert werden:

• Vorberechnung von Vorfahren
• Filtern der Vorfahren, die zu einer Transaktion hinzugefügt werden
• Ausschließen von Itemsets, die ein Item und einen seiner Vorfahren enthalten

Der Algorithmus "Cumulate" realisiert die obigen Optimierungen. Der Name "Cumulate" kommt daher, daß alle Kandidaten einer bestimmten Länge in einem einzigen Durchlauf gezählt werden. Dies ist zwar genauso wie beim Basisalgorithmus (und dem Apriori-Algorithmus), aber anders als bei den noch folgenden Varianten.

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.