WikiDer > A-priori-Algorithmus

Im Data-Mining ist der a-priori-Algorithmus ein Algorithmus zu Vereinsregeln von a lernen Datenbank mit Transaktionen, wie zum Beispiel in einem Supermarkt gekaufte Produkte oder besuchte Seiten einer Website. Der Algorithmus versucht, Assoziationsregeln zu lernen, indem er Muster in den Daten findet. Formaler ausgedrückt versucht der Algorithmus, Sammlungen von Elementen zu finden, die in den Daten eine minimale Anzahl von Malen vorkommen.

Hintergrund

Nehmen Sie die folgende Datenbank als Beispiel ${Anzeigestil D}$ mit zehn Trades in diesem Artikel:

1	{ 1, 2, 3 }
2	{ 1, 2, 4, 5 }
3	{ 2, 5 }
4	{ 3, 4, 5 }
5	{ 1, 4, 5 }
6	{ 3, 4 }
7	{ 2, 4, 5 }
8	{ 2, 4, 5 }
9	{ 1, 3, 5 }
10	{ 2, 4 }

In der Praxis kann dies Teil der Datenbank eines Supermarkts sein, in der festgehalten wird, welche Produkte pro Transaktion gekauft wurden.

Unterstützung einer Artikelsammlung

Das Unterstützung einer Artikelsammlung ${Anzeigestil X}$ in einer Datenbank ${Anzeigestil D}$ mit Transaktionen ist definiert als:

${displaystyle mathrm {support} (X)={frac {|{tin D | Xsubsetq t}|}{|D|}}}$

Mit anderen Worten, die Unterstützung einer Artikelsammlung ist die Anzahl der Transaktionen, die die Artikel von ${Anzeigestil X}$ im Auftreten dividiert durch die Anzahl der Transaktionen in der Datenbank.

Für die obige Datenbank gilt ${displaystyle mathrm {support} ({2,5})=0{,}4}$, da es vier von zehn Transaktionen gibt, die sowohl Position 2 als auch Position 5 enthalten.

Algorithmus

Die Eingabe des Algorithmus besteht aus einer Datenbank ${Anzeigestil D}$ und eine Zahl, die die Mindestunterstützung angibt (diese kann vom Benutzer gewählt werden). Ziel des Algorithmus ist es nun, möglichst große Itemsammlungen zu finden, die die gewünschte minimale Unterstützung aufweisen. Der Algorithmus beginnt mit Elementsammlungen der Größe 1 und fügt ein Element nach dem anderen hinzu, um zu sehen, ob größere Sammlungen auch die Mindestunterstützung erfüllen.

Der Algorithmus besteht aus zwei Stufen:

• Generieren von Sammlungen, die möglicherweise die minimale Unterstützung haben; diese werden Kandidaten genannt.
• Überprüfung der Kandidaten, welche von ihnen die minimale Unterstützung haben

Diese Stufen werden stufenweise durchgeführt, dh für Elementsammlungen der Größe 1, mit der Größe 2 usw.

Eine Kollektion mit Länge ${displaystyle n}$ ist eine Kandidatenmenge, wenn eine der Teilmengen der Länge ${Anzeigestil n-1}$ die minimale Unterstützung haben.

Der Algorithmus stoppt, wenn keine Kandidaten mehr gefunden werden können.

Beispiel

Ausführen des a-priori-Algorithmus auf der obigen Datenbank ${Anzeigestil D}$ und minimale Unterstützung = 0,3 ergibt das folgende Ergebnis.

Zunächst betrachtet der Algorithmus die folgenden Sammlungen der Größe 1:

Jede der Elementsammlungen hat eine Mindestunterstützung von 0,3, sodass jedes Element verwendet werden kann, um Kandidaten zu generieren:

Nur die Kollektionen { 1, 5 }, { 2, 4 }, { 2, 5 } und { 4, 5 } haben die Mindestunterstützung von 0,3. Der Algorithmus generiert nun Kandidaten mit drei Items. Eine Bedingung für eine Kandidatenmenge ist, dass jede der Teilmengen auch die minimale Unterstützung hat. Aus diesem Grund ist die Kollektion { 1, 2, 5 } nicht als Kandidat generiert werden, da obwohl { 1, 5 } und { 2, 5 } haben die minimale Unterstützung, die Sammlung hat { 1, 2 } nicht das. Fallen aus dem gleichen Grund { 1, 4, 5 } aus (wegen { 1, 4 }). Die Artikelsammlung { 2, 4, 5 } ist ausreichend, weil beide { 2, 4 }, { 2, 5 } wenn { 4, 5 } haben eine Unterstützung von mindestens 0,3. Die Kandidaten der Größe 3 sind:

Der Algorithmus endet hier, da keine Kandidaten der Größe vier generiert werden können.

Jede der minimal unterstützten Mengen, die während der Konstruktion angetroffen werden, kann zum Konstruieren von Assoziationsregeln verwendet werden.

Assoziationsregeln erstellen

Eine Assoziationsregel basierend auf einer Elementsammlung ${Anzeigestil S}$ hat die form ${displaystyle XRechtspfeil Y}$ bei welchem ${Anzeigestil X, YTeilmenge S}$ und ${displaystyle Y=S Schrägstrich X}$ bedeutet, dass wenn die Menge ${Anzeigestil X}$ auftritt, dann kommt auch die sammlung ${Anzeigestil Y}$ vor dem.

Die erhaltene Objektmenge { 1, 5 } gibt beispielsweise die folgenden Zeilen:

${displaystyle {1}Rechtspfeil {5}}$ (Regel ein)

${displaystyle {5}Pfeil nach rechts {1}}$ (Regel B)

Diese Assoziationsregeln repräsentieren die Muster in den Daten. Es gibt beispielsweise vier Transaktionen, die Artikel 1 enthalten, und Artikel 5 kommt auch in drei dieser Transaktionen vor. Regel ein ist in 3 von 4 Fällen richtig. Regel B stimmt in 3 von 7 Fällen. Hier können Sie auch eine Mindestgrenze festlegen, die eine Regel erfüllen muss, beispielsweise eine Regel, die in mindestens 50 % der Fälle richtig ist.

Im Beispiel Supermarkt bedeutet eine solche Regel, dass wenn jemand Produkt 1 kauft, er (meist) auch Produkt 5 kauft. Die große Menge an Daten, die ein Supermarkt über das Kaufverhalten der Kunden hat, kann nun analysiert werden, um Muster zu erkennen. Darauf kann ein Supermarkt dann beispielsweise mit Angeboten reagieren.