Moin.

Hat vielleicht einer der diesjähirgen DIS Teilnehmer bereits das 8te Blatt bearbeitet? Oder vielleicht erinnern sich auch einpaar ältere Hasen daran?!?

Kann es sein, dass der im Titel erwähnte Algorithmus unfassbar viel Zeit braucht oder habe ich ihn (bzw. den ersten Schritt) so dermaßen schlecht implementiert?

Im ersten Schritt bilde ich quasi einelementige Tupel für jeden Artikel und zähle ihr vorkommen in den Transaktionen. Es gibt 866 verschiedene Artikel und 10000 Transaktionen die jeweils (im Schnitt) 6 Artikel beherbergen.

Um jetzt die Anzahl der Tupel zu ermitteln muss ich ja für jeden Artikel/jedes Tupel alle 10000 Transaktionen a 6 Artikel überprüfen. Das sind ca 866*10000*6 Abfragen - was schon über eine halbe Stunde braucht.

Im zweiten Schritt muss ich dann zweielementige Tupel bilden und nach diesen in allen Transaktionen suchen - was pro Transaktion hier mehr Rechenaufwand erfordert und ergo noch länger dauert. Es werden zwar einpaar von denen durch minsupp fallen, aber kA wieviele das sind.

Kann das alles denn überhaupt sein oder tappe ich immer weiter in die Dunkelheit hinaus?

Danke im Vorraus.

Hallo,

die Komplexität von L1 (dem einelementigen Frequent-Item-Set) klingt nachvollziehbar. Aber wenn die Daten im Speicher sind, geht das doch raz-faz.
Für L2 gebe ich Dir vom Gedanken her recht, aber Du zählst ja nur für die 2-elementigen Kandidaten in den Transaktionen, die Du durch das in der Übung beschriebene generateCandidates()- Verfahren generiert hast (und dabei ist auch schon ein pruning enthalten). Folglich sollte auch das in Menschenzeit machbar sein. ;-) Nicht entmutigen lassen, solange das Programm unter 10 Minuten terminiert, sollte es gut sein. :D
Sonst frag gern, falls Du an einer Stelle nicht weiter kommst.

Moin rhobit, danke für deine Antwort/Reaktion.

Was du schreibst ist mir bewusst denke ich, mein algorithmus ist dennoch extrem zu langsam.
Inzwischen ist es so weit, dass die erste Runde mit den einelementigen Tupeln recht fix durchläuft. Sobald es aber zu den zweielementigen kommt wird das ganze zu langsam.

Vielleicht ist meine Idee von der überprüfung der zweielementigen Tupel zu straightforward?

Ich habe LinkedListen mit den zwei Elementen darin(entstanden durch die Artikel nach dem erste pruning). Um zu schauen, ob beide in einer bestimmten Transaktion vorkommen schaue ich zuerst ob das eine vorkommt, dann ob das zweite vorkommt.

Also (866-x)*2*10000*6 Abfragen, wenn x die Anzahl der einelementigen Artikel ist, die in der ersten Runde rausgeflogen sind.

Inzwischen weiss ich, dass man soetwas unter zwei Minuten hinbekommen kann. Aber ich weiss echt nicht mehr wie ich noch optimieren soll. Sind vllcht LinkedListen so langsam? Habe es auch schon mit einem HashSet versucht, was aber definitiv langsamer war.

Ich hab mal ne Frage zur Korrektheit.

Meine Lösung:
- für k=2 gibt es 71631 Kandidaten und 11Frequent Item Sets
- für k=3 gibt es 1 Kandidaten und 1 Frequent Item Sets
- für k=4 gibt es 0 Kandidaten und 0 Frequent Item Sets

Kann das jemand bestätigen? Danke.

Ich hab mal ne Frage zur Korrektheit.

Meine Lösung:
- für k=2 gibt es 71631 Kandidaten und 11Frequent Item Sets
- für k=3 gibt es 1 Kandidaten und 1 Frequent Item Sets
- für k=4 gibt es 0 Kandidaten und 0 Frequent Item Sets

Kann das jemand bestätigen? Danke.

Mein Algorithmus ist zwar einbisschen langsam, aber er findet bei k=2 deutlich mehr Frequent Item Sets. Mir scheint die Zahl deiner Kandidaten auch einbisschen klein zu sein. Wieviele kommen bei dir denn durch die erste Runde?

Der minsup liegt bei 10000 Transaktionen ja bei 100, nicht wahr?

Ich hab mal ne Frage zur Korrektheit.

Meine Lösung:
- für k=2 gibt es 71631 Kandidaten und 11Frequent Item Sets
- für k=3 gibt es 1 Kandidaten und 1 Frequent Item Sets
- für k=4 gibt es 0 Kandidaten und 0 Frequent Item Sets

Kann das jemand bestätigen? Danke.

Mein Algorithmus ist  zwar einbisschen langsam, aber er findet bei k=2 deutlich mehr Frequent Item Sets. Mir scheint die Zahl deiner Kandidaten auch einbisschen klein zu sein. Wieviele kommen bei dir denn durch die erste Runde?

Der minsup liegt bei 10000 Transaktionen ja bei 100, nicht wahr?

Stopp, Kommando zurück. Ich habe gerade bemerkt, dass er manche Sets doppelt findet. Das heisst bei meiner Mengenbildung geht etwas schief.

Wenn ich doppelte entferne lande ich aber bei:
k=2 –> 10 Frequent Itemsets
k=3 –> 1 Frequent Itemset
k=4 –> 0,terminiert

Schätze deine Ergebnisse sind richtig und bei meinen Mengen noch einiges falsch.

k=2 => 11 Tupel, sonst richtig.