Seite 1 von 1

Klausursprechstunde

Verfasst: 23. Feb 2011 10:28
von Sulzmann
Sammeln Sie hier bitte Ihre Fragen, die Sie in der Klausursprechstunde klären möchten.

Lift vs. Leverage

Verfasst: 25. Feb 2011 13:17
von Solberg
Hallo,

ich habe mir ein Beispiel ausgedacht, bei dem ich Leverage und Lift berechne. Die Ergebnisse stimmen aber nicht überein. Lift ( > 1) sagt mir, dass Body und Head häufiger gemeinsam vorkommen und Leverage ( < 0) sagt mir den Gegenteil.

Das Beispiel:
n = 1000
n(A) = 200
n(B) = 100
n(C) = 600

n(A, B) = 80
n(B, C) = 50
n(A, B, C) = 50

Code: Alles auswählen

lift(A->B,C) = [ n(A, B, C) / n(A) ] / [ n(B, C) / n ]  = [ 50 / 200 ] / [ 50 / 1000 ] =  0.25 / 0.05 =  5 > 1

Code: Alles auswählen

leverage(A->B,C) = [ n(A, B, C) / n ] - [ (n(A) / n) * (n(B, C) / n)  ]  = [ 50 / 1000 ] - [ (200 / 1000) * (50 / 1000)] =  0.05 - 0.1 =  -0.05 < 0
Berechne ich es falsch, oder sagt es mir einfach, dass laut Lift die Regel "interessant" ist und laut Leverage nicht?

Gruß,
Galin

Re: Klausursprechstunde

Verfasst: 25. Feb 2011 14:25
von Sulzmann
Es liegt ein Rechenfehler vor:

leverage(A->B,C) = [ n(A, B, C) / n ] - [ (n(A) / n) * (n(B, C) / n) ] = [ 50 / 1000 ] - [ (200 / 1000) * (50 / 1000)] = 0.05 - 0.1 = -0.05 < 0

\(\frac{200}{1000}\cdot\frac{50}{1000} = 0,001 \neq 0,1\) also wäre leverage(A->B,C)=0,05-0,001=0,049>0

I.A. gilt:
\(lift(A \rightarrow B) = \frac{sup(A \rightarrow B)}{sup(A)sup(B)} > 1\)
\(\Leftrightarrow sup(A \rightarrow B) > sup(A)sup(B)\)
\(\Leftrightarrow leverage(A \rightarrow B) = sup(A \rightarrow B) - sup(A)sup(B) > 0\)

Klausur WS 05/06 Aufgabe 5b - positive/negative Border

Verfasst: 25. Feb 2011 15:06
von Solberg
Hallo,

in der Aufgabe 5b von der Klausur WS 05/06 soll man die positive und die negative Border angeben.
In der Musterlösung steht:

Positive Border = { beatles, stones, dylan, cohen }
Negative Border = { beatles, dylan, young, stones } da aufgrund der Regel auch {beatles, dylan, stones} frequent sein muss.


Wir haben als 3-stellige Regeln

{ beatles, dylan, young } { beatles, young, stones } { young, dylan, stones } {beatles, dylan, stones} - laut Aufgabestellung nicht frequent, da sie nicht von Apriori gefunden wurde

FRAGE 1 Positive Border: Die ersten drei Regeln und keine ihrer Obermengen sind frequent. Diese Regeln sind dann die letzten, die an der Border liegen und frequent sind. Sie müssen dann zu der positiven Border gehören, oder?

FRAGE 2 Negative Border:
Ich nehme an, dass die 4-stellige Regel { beatles, dylan, young, stones } durch alle vier 3-stelligen Regeln generiert wurde. Das würde aber heißen, dass diese Regeln gar nicht an der Border liegt, da die vierte Regel {beatles, dylan, stones} nicht frequent* ist. Wie kann dann diese Regel die negative Border bilden?

* The border are all itemsets for which
- all subsets are frequent
- no superset is frequent

Gruß,
Galin

Re: Klausursprechstunde

Verfasst: 25. Feb 2011 17:52
von Sulzmann
Der Aufgabenstellung zufolge sind die folgenden Itemsets frequent

{beatles, dylan, young }
{beatles, young, stones }
{young, dylan, stones }

und ihre Obermengen infrequent (ausgegebene Klausur und Musterlösung unterscheiden sich in der Aufgabenstellung).
Weiterhin wissen wir, daß die Regel

beatles, stones → dylan, cohen

gefunden wurde, also ist auch

{beatles, stones, dylan, cohen}

frequent und seine Obermengen sind auch infrequent (Aufgabenstellung ist in diesem Punkt etwas mißverständlich) .

Demnach sind
{beatles, dylan, young, stones } und {beatles, stones, dylan, cohen} beide in der Border (alle Teilmengen sind frequent, alle Obermengen sind infrequent):

{beatles, dylan, young, stones } gehört zur negative Border:
- selbst infrequent (alle Obermengen v. {beatles, dylan, young }, {beatles, young, stones } und {young, dylan, stones } sind infrequent), damit auch alle Supersets infrequent.
- Alle Subsets sind frequent ({beatles, dylan, young }, {beatles, young, stones } und {young, dylan, stones } siehe Aufgabenstellung, {beatles, stones, dylan) ist Subset des frequent Itemsets {beatles, stones, dylan, cohen} und deshalb auch frequent)

{beatles, stones, dylan, cohen} gehört zur positive Border:
- Alle Subsets sind frequent (folgt aus Aufgabenstellung)
- Keine Supersets sind frequent (etwas mißverständlich, sollte der Aufgabenstellung entnommen werden, s.o.)

Re: Klausursprechstunde

Verfasst: 25. Feb 2011 18:59
von marlic
Gut, nur um nochmal sicherzugehen: Die korrekte Lösung zur Aufgabenstellung aus der Klausur wären dann aber auch alle drei dreielementigen Itemsets die angegeben wurden {b,d,y}, {b,y,s}, {y,d,s} im positive Border enthalten.

Das sieht man recht einfach:

Laut Aufgabenstellung selbst frequent und Monotonie -> Alle Teilmengen frequent
Laut Aufgabenstellung keine Obermenge frequent.

[EDIT]

Und zu dem Missverständlichen, das könnte man jetzt gerade vielleicht auch nochmal klären. Ihr meintet also, dass Apriori nur die Itemsets zu Regeln weiterverarbeitet, die nicht mehr erweitert werden können ohne infrequent zu werden, verstehe ich das richtig?

Re: Klausursprechstunde

Verfasst: 25. Feb 2011 19:31
von Sulzmann
marlic hat geschrieben:Gut, nur um nochmal sicherzugehen: Die korrekte Lösung zur Aufgabenstellung aus der Klausur wären dann aber auch alle drei dreielementigen Itemsets die angegeben wurden {b,d,y}, {b,y,s}, {y,d,s} im positive Border enthalten.

Das sieht man recht einfach:

Laut Aufgabenstellung selbst frequent und Monotonie -> Alle Teilmengen frequent
Laut Aufgabenstellung keine Obermenge frequent.
Richtig.
marlic hat geschrieben: Und zu dem Missverständlichen, das könnte man jetzt gerade vielleicht auch nochmal klären. Ihr meintet also, dass Apriori nur die Itemsets zu Regeln weiterverarbeitet, die nicht mehr erweitert werden können ohne infrequent zu werden, verstehe ich das richtig?
Nein, ich gehe davon aus, daß die Aufgabenstellung so gemeint war, daß die Obermengen der angegebenen 3 Itemsets UND das Itemset der gefundenen Regel infrequent sein sollen und nicht nur die Obermengen der 3 Itemsets (wie es wortwörtlich in der Aufgabenstellung steht), da ansonsten die Aufgabe nur teilweise lösbar wäre. Für das Itemset der Regel bzw. die positive Border könnte man ansonsten keine Aussage treffen.

Assistenten sind auch nur Menschen, manchmal denkt man, die Aufgabenstellung verstehen auch andere so wie man selbst. Vermutlich wurde in der dermaligen Klausur noch etwas Ergänzendes angekündigt bzw. angeschrieben.

Re: Klausursprechstunde

Verfasst: 25. Feb 2011 20:02
von marlic
Assistenten sind auch nur Menschen, manchmal denkt man, die Aufgabenstellung verstehen auch andere so wie man selbst.
Da stimme ich hundertprozentig zu :D

Re: Klausursprechstunde

Verfasst: 26. Feb 2011 10:48
von Maradatscha
Nur eine Kleinigkeit:

Foliensatz 8, Folie 24: Entropy Split

Warum heisst der Splitpoint T_max und dann sucht man nach einem arg min ?

Klausur WS 06/07 Aufgabe 4e

Verfasst: 26. Feb 2011 12:02
von Solberg
Aufgabestellung:
Weiters gibt Ihr Auftraggeber an, daß er maximal 10% false positives akzeptieren kann. Wie konstruieren
Sie aus den gelernten Regeln einen
für dieses Szenario passenden Klassifizierer?
d.h FPR muss <= 10% sein oder anders gesagt FP <= 20, da N = 200 ist.

Theorie
R1 fp 100
R2 fp 80
R3 fp 20

In diesem Fall ist die einzige Regel, die die Bedingung erfüllt R3. Man braucht doch keine neue Regel konstruiren, oder?
Reicht das als Antwort in der Klausur, oder wird für die Aufgabe auch bestimmte Vorgehensweise nachgefragt?

Re: Klausursprechstunde

Verfasst: 27. Feb 2011 17:29
von Sulzmann
Maradatscha hat geschrieben:Nur eine Kleinigkeit:

Foliensatz 8, Folie 24: Entropy Split

Warum heisst der Splitpoint T_max und dann sucht man nach einem arg min ?
Gesucht wird der Splitpoint mit minimaler gewichteter Entropy. Warum dieser Splitpoint mit T_max bezeichnet wurde, ist mir im Augenblick auch nicht einleuchtend, wobei das ja auch nur eine Bezeichnung ist und keinen Einfluß auf den Algorithmus hat...

Mögliche Gründe dafür gibt es mehrere:
- T_max := Splitpoint, der den maximalen Nutzen bringt
- Copy & Paste aus einem (ähnlichen) Algorithmus
...

Re: Klausur WS 06/07 Aufgabe 4e

Verfasst: 27. Feb 2011 18:35
von Sulzmann
Solberg hat geschrieben:Aufgabestellung:
Weiters gibt Ihr Auftraggeber an, daß er maximal 10% false positives akzeptieren kann. Wie konstruieren
Sie aus den gelernten Regeln einen
für dieses Szenario passenden Klassifizierer?
d.h FPR muss <= 10% sein oder anders gesagt FP <= 20, da N = 200 ist.

Theorie
R1 fp 100
R2 fp 80
R3 fp 20
Vermutlich haben Sie fn und fp verwechselt, die oben berechneten Werte entsprechen nämlich den fn-Werten der jeweiligen Theorie (R1, R1+R2, R1+R2+R3) und nicht denen einzelner Regeln. Streng genommen können Sie letztere Werte nicht exakt aus der Aufgabenstellung entnehmen bzw. berechnen, was auch nicht Sinn der Aufgabenstellung gewesen ist. Nur eine Angabe von Intervalle für den jeweiligen Wert (für R2 und R3) sind möglich:

Aus der Aufgabenstellung wissen Sie:
Theorie tp fp
{R1} 100 40
{R1,R2} 120 80
{R1,R2,R3} 180 120

Hieraus können Sie keinen exakten Werte (wie oben) für R2 und R3 berechnen, nur Intervalle angeben, z.B. R2:
R2: \(tp \in [20 : 120]\) und \(fp \in [40:80]\),
da Regeln (hier R1 und R2) überlappen können.
Solberg hat geschrieben: In diesem Fall ist die einzige Regel, die die Bedingung erfüllt R3. Man braucht doch keine neue Regel konstruiren, oder?
Reicht das als Antwort in der Klausur, oder wird für die Aufgabe auch bestimmte Vorgehensweise nachgefragt?
Aus den 5 gegebenen Theorien (R1, R1+R2, R1+R2+R3, leere und universelle Theorie) sollte ein Klassifizierer konstruiert werden. Eine optimale Lösung erhält man, indem man die leere Theorie und R1 (im Verhältnis 1:1) interpoliert. Die resultierende Theorie hätte dann eine fpr von 0.1 (0.5*0.2) und tpr von 0.25 (0.5*0.5). Diese Werte hat man bereits in der Teilaufgabe 4a) berechnet und müssen nur abgelesen werden.

Re: Klausursprechstunde

Verfasst: 28. Feb 2011 09:37
von Maradatscha
Vielleicht ein bisschen knapp, aber es wäre schön wenn wir noch einmal die AUC (Area under ROC) berechnen könnten vielleicht am Beispiel von A4 aus der Klausur 06/07. Vielleicht auch einfach nochmal die Metric besprechen die auf Folie 47 von Foliensatz Evaluation beschrieben ist.

Dann wäre es nett wenn wir die hier schon besprochene Aufgabe 5 von der Klausur 05/06 nochmal durchrechnen könnten, falls noch Zeit ist.