Wird FPGrowth im häufigen Musterabbau immer noch als „Stand der Technik“ angesehen?

Question

Soweit ich die Entwicklung von Algorithmen zur Lösung des FPM -Problems (Häufigen Muster -Mining) kenne, hat der Weg der Verbesserungen einige Hauptkontrollpunkte. Erstens die Apriori Algorithmus wurde 1993 von vorgeschlagen von Agrawal et al., zusammen mit der Formalisierung des Problems. Der Algorithmus war in der Lage ausziehen einige Sets aus dem 2^n - 1 Sets (PowerSet), indem ein Gitter verwendet wird, um die Daten zu erhalten. Ein Nachteil des Ansatzes war die Notwendigkeit, die Datenbank erneut zu lesen, um die Frequenz jedes erweiterten Satzes zu berechnen.

Später, im Jahr 1997,, Zaki et al. schlug den Algorithmus vor Eklat, die eingefügt Die resultierende Frequenz jedes Satzes im Gitter. Dies geschah, indem an jedem Knoten des Gitters der Satz von Transaktions-IDs hinzugefügt wurde, die die Elemente von der Wurzel zum verwiesenen Knoten hatten. Der Hauptbeitrag besteht darin, dass man den gesamten Datensatz nicht erneut lesen muss, um die Häufigkeit jedes Satzes zu kennen, aber der Speicher, der für die Aufrechterhaltung solcher Datenstruktur erforderlich ist, kann die Größe des Datensatzes selbst überschreiten.

In 2000, Han et al. schlug einen Algorithmus namens vor FPGrowth, zusammen mit einer Präfix-Tree-Datenstruktur mit dem Namen FPTree. Der Algorithmus war in der Lage, eine signifikante Datenkomprimierung bereitzustellen und gleichzeitig zu gewähren, dass nur häufige Itemsets ergeben würden (ohne Kandidaten -Elemente -Erzeugung). Dies geschah hauptsächlich durch Sortieren der Elemente jeder Transaktion in abnehmender Reihenfolge, so dass die häufigsten Elemente diejenigen sind, die die geringsten Wiederholungen in der Baumdatenstruktur sind. Da die Frequenz nur beim Durchqueren des Baums ausführlich abfällt, kann der Algorithmus in der Lage sein ausziehen Nicht-frequente Gegenstände.

Bearbeiten:

Soweit ich weiß, kann dies als hochmoderner Algorithmus angesehen werden, aber ich würde gerne über andere vorgeschlagene Lösungen wissen. Welche anderen Algorithmen für FPM gelten als "hochmodern"? Was ist der Intuition/Hauptkontribution von solchen Algorithmen?

Wird der FPGrowth -Algorithmus im häufigen Musterabbau immer noch als "Stand der Technik" angesehen? Wenn nicht, welche Algorithmus kann häufige Elements aus großen Datensätzen effizienter extrahieren?

Answer 1

Stand der Technik wie in: in der Praxis verwendet oder theoretisch daran gearbeitet?

Apriori wird überall verwendet, außer bei der Entwicklung neuer häufiger Elementset -Algorithmen. Es ist einfach zu implementieren und leicht in sehr unterschiedlichen Bereichen wiederzuverwenden. Sie finden Hunderte von Apriori -Implementierungen unterschiedlicher Qualität. Und es ist einfach, Apriori falsch zu verstehen.

FPGrowth ist viel schwieriger zu implementieren, aber auch viel interessanter. Aus akademischer Sicht versucht jeder, FPGrowth zu verbessern. Die Arbeit auf der Grundlage von Apriori akzeptiert wird inzwischen sehr schwierig.

Wenn Sie eine gute Implementierung haben, hat jeder Algorithmus gut und es sind meiner Meinung nach schlechte Situationen. Eine gute apriori -Implementierung wird nur müssen die Datenbank scannen k Zeiten, um alle häufigen Länge zu finden k. Insbesondere wenn Ihre Daten in den Hauptspeicher passt, ist dies billig. Was apriori töten kann, sind zu viele häufig 2-Itemsets (insbesondere wenn Sie keine Tries und ähnliche Beschleunigungstechniken usw. verwenden). Es funktioniert am besten bei großen Daten mit einer geringen Anzahl von häufigen Elementen.

Eclat funktioniert auf Spalten; Aber es muss jede Spalte viel öfter lesen. Es gibt einige Arbeit an Diffsets, um diese Arbeit zu reduzieren. Wenn Ihre Daten nicht in den Hauptspeicher passen, leidet Eclat wahrscheinlich mehr als apriori. Durch die erste Tiefe kann es auch ein erstes interessantes Ergebnis viel früher als Apriori zurückgeben, und Sie können diese Ergebnisse verwenden, um die Parameter anzupassen. Sie benötigen also weniger Iterationen, um gute Parameter zu finden. Aber bei Design kann es das Beschneiden nicht so ordentlich ausnutzen wie Apriori.

FPGrowth komprimiert den Datensatz in den Baum. Dies funktioniert am besten, wenn Sie viele doppelte Datensätze haben. Sie könnten wahrscheinlich auch einige Gewinne für Aprriori und Eclat erzielen, wenn Sie Ihre Daten vorantreiben und Duplikate in gewichtete Vektoren zusammenführen können. FPGrowth macht dies auf extremer Ebene. Der Nachteil ist, dass die Implementierung viel schwieriger ist. Und sobald dieser Baum nicht mehr in das Gedächtnis passt, hat er ein Chaos zu implementieren.

Vertrauen Sie ihnen nicht. Es gibt so viele Dinge zu implementieren. Probieren Sie 10 verschiedene Implementierungen aus und Sie erhalten 10 sehr unterschiedliche Leistungsergebnisse. Insbesondere für Apriori habe ich den Eindruck, dass die meisten Implementierungen im Sinne des Fehlenden einiger der Hauptbeiträge von Aprriori gebrochen sind ... und von denen, die diese Teile richtig haben, variiert die Qualität der Optimierungen sehr.

Es gibt tatsächlich sogar Artikel darüber, wie diese Algorithmen effizient implementiert werden können:

Effiziente Implementierungen von Apriori und Eclat.
Christian Borgelt
Workshop von häufigen Elementen -Mining -Implementierungen (FIMI 2003, Melbourne, FL, USA).

Möglicherweise möchten Sie diese Umfragen auch zu dieser Domäne lesen:

• Goethals, Bart. "Umfrage zum häufigen Musterabbau." Univ. von Helsinki (2003).

• Ferenc Bodon, eine Umfrage zum häufigen Powerset -Bergbau, zum technischen Bericht, der Budapest University of Technology and Economic, 2006,,

• Häufiger Gegenstandsabbau
  Christian Borgelt
  Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery 2 (6): 437-456. 2012

Answer 2

Die meisten der jüngsten häufigen Musteransätze, die ich in der Literatur gesehen habe, basieren auf der Optimierung von FPGrowth. Ich muss zugeben, ich habe seit vielen Jahren nicht viele Entwicklungen innerhalb der Literatur in FPM gesehen.

Dieses Wikibook Markiert viele der Varianten auf FPGrowth, die da draußen sind.