Klausursprechstunde

Moderator: Data Mining und Maschinelles Lernen

Sulzmann
Mausschubser
Mausschubser
Beiträge: 45
Registriert: 13. Nov 2006 16:02

Klausursprechstunde

Beitrag von Sulzmann » 23. Feb 2011 10:28

Sammeln Sie hier bitte Ihre Fragen, die Sie in der Klausursprechstunde klären möchten.

Solberg
Windoof-User
Windoof-User
Beiträge: 30
Registriert: 5. Okt 2007 13:56
Wohnort: Darmstadt

Lift vs. Leverage

Beitrag von Solberg » 25. Feb 2011 13:17

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

Sulzmann
Mausschubser
Mausschubser
Beiträge: 45
Registriert: 13. Nov 2006 16:02

Re: Klausursprechstunde

Beitrag von Sulzmann » 25. Feb 2011 14:25

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\)

Solberg
Windoof-User
Windoof-User
Beiträge: 30
Registriert: 5. Okt 2007 13:56
Wohnort: Darmstadt

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

Beitrag von Solberg » 25. Feb 2011 15:06

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

Sulzmann
Mausschubser
Mausschubser
Beiträge: 45
Registriert: 13. Nov 2006 16:02

Re: Klausursprechstunde

Beitrag von Sulzmann » 25. Feb 2011 17:52

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.)

Benutzeravatar
marlic
Computerversteher
Computerversteher
Beiträge: 365
Registriert: 5. Okt 2006 11:09
Wohnort: Dietesheim

Re: Klausursprechstunde

Beitrag von marlic » 25. Feb 2011 18:59

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?
"Copy & Passed"

Wahlspruch der Plagiatoren

Sulzmann
Mausschubser
Mausschubser
Beiträge: 45
Registriert: 13. Nov 2006 16:02

Re: Klausursprechstunde

Beitrag von Sulzmann » 25. Feb 2011 19:31

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.

Benutzeravatar
marlic
Computerversteher
Computerversteher
Beiträge: 365
Registriert: 5. Okt 2006 11:09
Wohnort: Dietesheim

Re: Klausursprechstunde

Beitrag von marlic » 25. Feb 2011 20:02

Assistenten sind auch nur Menschen, manchmal denkt man, die Aufgabenstellung verstehen auch andere so wie man selbst.
Da stimme ich hundertprozentig zu :D
"Copy & Passed"

Wahlspruch der Plagiatoren

Benutzeravatar
Maradatscha
Computerversteher
Computerversteher
Beiträge: 353
Registriert: 2. Okt 2006 18:53

Re: Klausursprechstunde

Beitrag von Maradatscha » 26. Feb 2011 10:48

Nur eine Kleinigkeit:

Foliensatz 8, Folie 24: Entropy Split

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

Solberg
Windoof-User
Windoof-User
Beiträge: 30
Registriert: 5. Okt 2007 13:56
Wohnort: Darmstadt

Klausur WS 06/07 Aufgabe 4e

Beitrag von Solberg » 26. Feb 2011 12:02

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?

Sulzmann
Mausschubser
Mausschubser
Beiträge: 45
Registriert: 13. Nov 2006 16:02

Re: Klausursprechstunde

Beitrag von Sulzmann » 27. Feb 2011 17:29

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
...

Sulzmann
Mausschubser
Mausschubser
Beiträge: 45
Registriert: 13. Nov 2006 16:02

Re: Klausur WS 06/07 Aufgabe 4e

Beitrag von Sulzmann » 27. Feb 2011 18:35

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.

Benutzeravatar
Maradatscha
Computerversteher
Computerversteher
Beiträge: 353
Registriert: 2. Okt 2006 18:53

Re: Klausursprechstunde

Beitrag von Maradatscha » 28. Feb 2011 09:37

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.

Antworten

Zurück zu „Data Mining und Maschinelles Lernen“