Soweit ich die Entwicklung von Algorithmen zur Lösung des FPM-Problems (Frequent Pattern Mining) kenne, gibt es auf dem Weg der Verbesserungen einige Hauptkontrollpunkte. Erstens wurde der Apriori- Algorithmus 1993 von Agrawal et al. zusammen mit der Formalisierung des Problems. Der Algorithmus konnte Strip-Off einige Sätze aus den 2^n - 1Sätzen (Powerset) durch ein Gitter unter Verwendung der Daten zu erhalten. Ein Nachteil des Ansatzes war die Notwendigkeit, die Datenbank erneut zu lesen, um die Häufigkeit jedes erweiterten Satzes zu berechnen.
Später, im Jahr 1997, stellten Zaki et al. schlug den Algorithmus Eclat vor , der die resultierende Frequenz jedes Satzes in das Gitter einfügte . Dazu wurde an jedem Knoten des Gitters der Satz von Transaktions-IDs hinzugefügt, die die Elemente vom Stamm zum verwiesenen Knoten enthielten. Der Hauptbeitrag besteht darin, dass nicht der gesamte Datensatz erneut gelesen werden muss, um die Häufigkeit jedes Satzes zu ermitteln. Der für die Erstellung einer solchen Datenstruktur erforderliche Speicher kann jedoch die Größe des Datensatzes selbst überschreiten.
Im Jahr 2000 haben Han et al. schlugen einen Algorithmus namens FPGrowth zusammen mit einer Präfixbaum -Datenstruktur namens FPTree vor. Der Algorithmus war in der Lage, eine signifikante Datenkomprimierung bereitzustellen und gleichzeitig zu gewährleisten, dass nur häufige Elementmengen (ohne Generierung von Kandidatenelementmengen) erhalten werden. Dies erfolgte hauptsächlich durch Sortieren der Elemente jeder Transaktion in absteigender Reihenfolge, so dass die häufigsten Elemente diejenigen mit den geringsten Wiederholungen in der Baumdatenstruktur sind. Da nur die Frequenz steigt , während den Baum in der Tiefe durchquert, ist der Algorithmus in der Lage zu strippen-off nicht-häufige itemsets.
Bearbeiten :
Soweit ich weiß, kann dies als ein Algorithmus auf dem neuesten Stand der Technik angesehen werden, aber ich würde gerne mehr über andere vorgeschlagene Lösungen erfahren. Welche anderen Algorithmen für FPM gelten als "State-of-the-Art"? Was ist die Intuition / der Hauptbeitrag solcher Algorithmen?
Wird der FPGrowth-Algorithmus beim häufigen Pattern-Mining immer noch als "Stand der Technik" angesehen? Wenn nicht, welche Algorithmen können häufige Objektmengen effizienter aus großen Datenmengen extrahieren?
Antworten:
Stand der Technik wie in: in der Praxis eingesetzt oder theoretisch bearbeitet?
APRIORI wird überall verwendet, außer bei der Entwicklung neuer Algorithmen für häufige Objektgruppen. Es ist einfach zu implementieren und in sehr unterschiedlichen Bereichen wiederzuverwenden. Sie finden Hunderte von APRIORI-Implementierungen unterschiedlicher Qualität. Und es ist eigentlich leicht, APRIORI falsch zu verstehen.
FPgrowth ist viel schwieriger zu implementieren, aber auch viel interessanter. Aus akademischer Sicht versuchen alle, das FP-Wachstum zu verbessern - es wird mittlerweile sehr schwierig sein, Arbeit auf der Grundlage von APRIORI zu akzeptieren.
Wenn Sie eine gute Implementierung haben, hat jeder Algorithmus gute und meiner Meinung nach schlechte Situationen. Eine gute APRIORI Implementierung wird nur benötigen , um die Datenbank zu scannen k mal alle häufigen Itemsets der Länge finden k . Insbesondere wenn Ihre Daten in den Hauptspeicher passen, ist dies billig. Was APRIORI töten kann, sind zu viele häufige 2-Itemsets (insbesondere, wenn Sie keinen Trie und ähnliche Beschleunigungstechniken usw. verwenden). Es funktioniert am besten bei großen Datenmengen mit einer geringen Anzahl häufiger Objektgruppen.
Eclat arbeitet an Spalten; Aber es muss jede Spalte viel öfter lesen. Es gibt einige Arbeiten an Diffsets, um diese Arbeit zu reduzieren. Wenn Ihre Daten nicht in den Hauptspeicher passen, leidet Eclat wahrscheinlich mehr als Apriori. Wenn Sie zuerst in die Tiefe gehen, können Sie auch viel früher als Apriori ein erstes interessantes Ergebnis zurückgeben. Mit diesen Ergebnissen können Sie die Parameter anpassen. Sie benötigen also weniger Iterationen, um gute Parameter zu finden. Aber von Natur aus kann es das Beschneiden nicht so sauber 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 für Apriori und Eclat einige Gewinne erzielen, wenn Sie Ihre Daten vorsortieren und Duplikate zu gewichteten Vektoren zusammenführen können. FPGrowth tut dies auf extremem Niveau. Der Nachteil ist, dass die Implementierung viel schwieriger ist; und sobald dieser Baum nicht mehr in den Speicher passt, muss er implementiert werden.
Leistungsergebnisse und Benchmarks - vertrauen Sie ihnen nicht. Es gibt so viele Dinge, die falsch implementiert werden müssen. 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 in dem Sinne fehlerhaft sind, dass einige der Hauptbeiträge von APRIORI fehlen ... und von denen, die diese Teile richtig haben, variiert die Qualität der Optimierungen stark.
Es gibt sogar Artikel darüber, wie diese Algorithmen effizient implementiert werden können:
Möglicherweise möchten Sie auch diese Umfragen in dieser Domain lesen:
quelle
Die meisten der jüngsten Frequent Pattern-Ansätze, die ich in der Literatur gesehen habe, basieren auf der Optimierung von FPGrowth. Ich muss zugeben, ich habe in FPM seit vielen Jahren nicht mehr viele Entwicklungen in der Literatur gesehen.
Dieses Wikibook zeigt viele der Varianten von FPGrowth, die es gibt.
quelle