Fachrat Informatik - Forum

Quoted

Original von MAX
Hallo!
Es geht um Apriori-Algorithm. Eine Frage zum Beispiel mit der Kleidung. Kann es sein, dass hier im ersten Durchlauf ein Fehler aufgetreten ist? Und zwar gehört doch Item "Shorts" nicht zu der Menge der Frequent Itemsets, da support(Shorts) = 25% und die obere Schranke s = 30% ist. Ich habe insgesamt 5 Mal Shorts gezählt und es gibt 20 Transaktionen. Also 5/20 = 0,25 also 25 %. Warum wurde dieses Item trotzdem in die Menge aufgenommen? Habe ich was übersehen oder ist es ein Fehler im Skript?

Ein Fehler. Bei dem im Skript vorgemachten Rechenweg haut so einiges nicht hin. Einfach ignorieren, so schwer ist der Algorithmus ja nicht.

Mal was anderes: Ich war nicht in allen Übungen. In einer Übung wurde laut Skript ein Algorithmus für das hierarchische Clustern vorgestellt. Könnte den bitte mal jemand posten?

Dürfen wir das Skript in der Prüfung eigentlich benutzen?

mfg Jens

Nein. Nur einen nicht-programmierbaren Taschenrechner. hier

Quoted

Original von Joachim
Mal was anderes: Ich war nicht in allen Übungen. In einer Übung wurde laut Skript ein Algorithmus für das hierarchische Clustern vorgestellt. Könnte den bitte mal jemand posten?

Alg. müsste eigentlich folgender sein:


Input:
D = {t1,...,tn} (Menge der Elemente, die geclustert werden sollen)
A: Adjazenzmatrix
Output:
DE

Single Link: kürzester Abstand zwischen zwei Clustern
Complete Link: größter Abstand

Hoffe, das hilft weiter ..


P.S.: Hat zufällig jemand sich eine Zusammenfassung des Scripts zum kompakten Lernen geschrieben? Wäre nett, wenn jemand soetwas mal posten könnte

Quoted

Original von dfex
Complete Link: größter Abstand

über diese formulierung bin ich auch gestoßen, sie ist aber doch etwas verwirrend. denn es werden nicht immer die elemente geclustert, die den größten abstand haben. hierbei ist die vorgegebene schranke d zu beachten. der abstand der elemente (oder ggf. cluster) muss kleiner oder gleich dieser schranke sein.

in einer übungsaufgabe war das so:
...
d = 3

distance({A,B}, {C,D}) = 4
distance({C,D}, {E}) = 5
distance({A,B}, {E}) = 3

{A,B}, {E} wurden geclustert.
ich könnte mir vorstellen dass min(max(distance)) immer geclustert wird, habe es aber bisher nicht versucht zu beweisen

für belehrungen diesbezüglich bin ich natürlich offen, da das material es einem nicht immer einfach macht, den stoff zu verstehen

Quoted

Original von dfex

Quoted

Original von Joachim
Mal was anderes: Ich war nicht in allen Übungen. In einer Übung wurde laut Skript ein Algorithmus für das hierarchische Clustern vorgestellt. Könnte den bitte mal jemand posten?

Alg. müsste eigentlich folgender sein:

	Source code
1 2 3 4 5 6 7 8 9 10 11 12 13	d = 0; k = n; K = { {t1},...,{tn} }; DE = { <d,k,K> } repeat oldk = k; d = d + 1; // Hierachiestufe um eine Einheit erhöhen Ad; // Adjazenzmatrix für die Distanz d <k,K> = new Cluster(Ad,d); if (oldk != k ) DE = DE U <d,k,K> until k = 1;

Input:
D = {t1,...,tn} (Menge der Elemente, die geclustert werden sollen)
A: Adjazenzmatrix
Output:
DE

Danke. Was genau ist hier unter Adjazenzmatrix zu verstehen? Was macht new Cluster(...)?

Quoted

P.S.: Hat zufällig jemand sich eine Zusammenfassung des Scripts zum kompakten Lernen geschrieben? Wäre nett, wenn jemand soetwas mal posten könnte

Das nicht, aber ich habe die Herleitung zum probabilistischen Modell mal sauber mathematisch aufgeschrieben, den Kram auf den Folien fand ich völlig unverständlich. Falls Du also daran Interesse haben solltest ...

Quoted

Original von Ray-D
ich könnte mir vorstellen dass min(max(distance)) immer geclustert wird, habe es aber bisher nicht versucht zu beweisen

fast. natürlich muss man immer die vorgegebene schranke d berücksichtigen. und damit ergibt sich dann:
max(distance) <= d wird (bei complete link)

Quoted

Original von Joachim
Danke. Was genau ist hier unter Adjazenzmatrix zu verstehen? Was macht new Cluster(...)?

Also, so wie ich das verstanden hab (meine Aufzeichnungen sind auch nich so besonders ):

Die Adjazenzmatrix beinhaltet die Distanzen zwischen den Elementen nach der jeweiligen gewählten Methode. Z.B. bei Single Link immer die kleinste Distanz. Als Element gilt auch ein im vorherigen Schritt erstellter Cluster. Deswegen muss die Ad in jedem Schritt neu berechnet werden.
edit: stimmt nicht so ganz, weil natürlich die gegeben Distanzen zwischen den ursprünglichen Elementen sich nicht ändert. Es sind jeweils nur die neuen Distanzen für neuen Cluster zu berechnen. Dabei geht man in einem Cluster einfach die einzelnen Elemente durch und vergleicht deren Distanz mit dem "distanzierten Element".

new Cluster(Ad,d) erstellt dann einen neuen Cluster mit den Elementen aus Ad, deren Distanz <= d ist.

hoffe man kanns verstehen ..

Quoted

Original von dfex

Quoted

Original von Joachim
Danke. Was genau ist hier unter Adjazenzmatrix zu verstehen? Was macht new Cluster(...)?

Also, so wie ich das verstanden hab (meine Aufzeichnungen sind auch nich so besonders ):

Die Adjazenzmatrix beinhaltet die Distanzen zwischen den Elementen nach der jeweiligen gewählten Methode. Z.B. bei Single Link immer die kleinste Distanz. Als Element gilt auch ein im vorherigen Schritt erstellter Cluster. Deswegen muss die Ad in jedem Schritt neu berechnet werden.
edit: stimmt nicht so ganz, weil natürlich die gegeben Distanzen zwischen den ursprünglichen Elementen sich nicht ändert. Es sind jeweils nur die neuen Distanzen für neuen Cluster zu berechnen. Dabei geht man in einem Cluster einfach die einzelnen Elemente durch und vergleicht deren Distanz mit dem "distanzierten Element".

new Cluster(Ad,d) erstellt dann einen neuen Cluster mit den Elementen aus Ad, deren Distanz <= d ist.

hoffe man kanns verstehen ..

Ja, ist klar. Danke.

Kennt jemand eigentlich schon Klausuren von Frau Henze und kann einmal über Erfahrungen berichten?
Also Umfang, Schwierigkeit, wieviel Wert auf Genauigkeit legt sie .. etc.


Denn ihre Themenangabe ist ja doch recht umfangreich für 60 Min.

Quoted

Original von MAX
Hallo!
Hat jemand die Aufgabe vom 12 Januar mitgeschrieben(selbst gemacht)? Und kann vielleicht hier erklären, worum es geht? Irgendwie verstehe ich nicht, was da gerade zu machen ist. Es geht um Sequential Patterns.
MAX

Jo, ich hab hier was. Is aber nen bisschen viel, um das mal eben abzutippen.

Generell geht es darum, dass mit Hilfe von Sequential Patterns Reihenfolge-Muster pro User sitzungsübergreifend betrachtet werden.
Dabei wird eine Variante des Apriori-Algs verwendet.

Auf deutsch:
Du guckst erst nach ein-Elementigen Kandidaten. Also A;B;C,... usw.
Danach zwei-Elementige Mengen: A,B ; A,C ; ... usw.
.
.
.
und stellst halt fest, ob es diese Reihenfolge-Muster gibt.

Das Ende ist dann bei fünf-Elementigen Kandidaten erreicht, da es diese nicht existieren.





So, und abschliessend darf ich nochmal anmerken:
Ich hab mir zu wenig Zeit zum lernen genommen. Hab gerade ne Antwort von Frau Henze bekommen:

Quoted

Ja, es gibt Rechenaufgaben, die sich nicht auf die bereitgestellten
Formeln beziehen [In den Hilfen zur Klausur, auf die sie sich beziehen,
stehen nur die Berechnungsvorschriften für GINI, Entropy, und die
Ansätze zum prob. Modell im Information Retrieval.]

Bei der Klausur sollten Sie in der Lage sein, sowohl Textaufgaben /
Fragen als auch Rechenaufgaben zu den Punkten, die auf der Seite

http://www.kbs.uni-hannover.de/%7Ehenze/…Management.html

gelisted sind, zu beantworten.

Ich bin dann für dieses Jahr mal RAUS!

Viel Glück noch ..

Quoted

Original von MAX
Ok! Danke. Das hilft zuerst weiter.

Es ist wirklich sehr viel, was Frau Henze in 60 min durchnehmen will, wenn tatsächlich alles dran kommen sollte, was auf ihrer HP steht.

Ich habe noch keine Klausur, in der wirklich der gesamte Stoff angefragt wurde. Es wäre ja auch taktisch unklug vom Prüfer vorher zu sagen, welche Themen in der Klausur behandelt werden.

Quoted

Original von MAX
Hallo!
Hat jemand die Aufgabe vom 12 Januar mitgeschrieben(selbst gemacht)? Und kann vielleicht hier erklären, worum es geht? Irgendwie verstehe ich nicht, was da gerade zu machen ist. Es geht um Sequential Patterns.

Hier meine Lösung:

Die Transaktionen:
U1: ABCBCE
U2: AC
U3: ACDCE

Zuerst die Sequenzen der Länge 1:
Kandidaten: A, B, C, D, E

Alle davon sind häufig, da sie den geforderten Support-Level erfüllen.

Nun die Sequenzen der Länge 2:
Kandidaten: AB, AC, AD, AE, BA, BC, BD, BE, CA, CB, CD, CE, DA, DB, DC, DE, EA, EB, EC, ED

Nur die Sequenzen AB, AC, BC, BA, CB, CD, CE und DC sind häufig.

Demzufolge müssen häufig Sequenzen der Länge 3 eine häufig Sequenz der Länge 2 enthalten (und aus diesen zusammengesetzt sein).
Kandidaten: ABC, ACB, ACD, ACE, BCD, BCE, BAC, CBA, DCE

Nur die Sequenzen ABC, ACD und DCE sind häufig.

Sequenzen der Länge 4 lassen sich aus diesen Sequenzen nicht mehr bilden. Damit sind wir fertig.

Da sequential patterns maximal sein sollen, besteht das Ergebnis nur aus den Sequenzen, die nicht Teil einer anderen häufigen Sequenz sind.

Es bleiben also ABC, ACD, DCE, BA, CB und DC übrig.


Ich denke, daß das so korrekt sein sollte. Über Kommentare freue ich mich trotzdem, insbesondere bezüglich des Umgangs mit Duplikaten, die ja laut Skript bei sequential patterns nicht erlaubt sind.

Quoted

Original von Joachim
Nur die Sequenzen AB, AC, BC, BA, CB, CD, CE und DC sind häufig.
.
.
Ich denke, daß das so korrekt sein sollte. Über Kommentare freue ich mich trotzdem, insbesondere bezüglich des Umgangs mit Duplikaten, die ja laut Skript bei sequential patterns nicht erlaubt sind.

Also, bei den Sequenzen der Länge 2 sind noch ein Paar mehr häufig. Ich hab hier:
AB, AC, AD, AE, BC, BE, CB, CD, CE, DC, DE

Denn:
Bei Sequential Patterns wird zwar die Reihenfolge beachtet, die Elemente müssen aber nich direkt aufeinanderfolgend sein.
Somit ist die 3er Menge auch etwas größer und es existieren sogar Sequenzen der Länge 4.

Moin!

Mal ne andere Frage zum gleichen Thema:

Warum legt sie mehrere Sessions vom selben User bei Sequential Patterns zusammen, bei den Association Rules for Pattern Discovery werden sie aber als unabhängige Transactions betrachtet? Die Eigenschaften ordered, duplicates, consecutive und maximal sagen darüber ja eigentlich nichts aus.

Ralf.

Quoted

Original von dfex
Bei Sequential Patterns wird zwar die Reihenfolge beachtet, die Elemente müssen aber nich direkt aufeinanderfolgend sein.

OK, sehe ich auch gerade im Paper "Mining Sequential Patterns" (zu finden über Citeseer). Das wird im Skript überhaupt nicht klar.