Übung 4 - Web Mining

Ab­gabe: bis Son­ntag, den 17.6.2012

1. Daten be­sor­gen und auf­bere­it­en (1 P)

1. Wählen Sie einen beliebigen multiclass -Datensatz z.B. aus der unten angegebenen Liste aus. Sie können je­doch auch be­liebige an­dere Doku­mentsamm­lun­gen, selb­ster­stellt oder bere­its ex­istierende Text-Klas­si­fika­tions-Samm­lun­gen, mit min­destens fünf Klassen ver­wen­den. Reduzieren Sie, falls es Ihnen nötig er­scheint, die An­zahl der Klassen durch sin­nvolles Zusam­men­le­gen oder Aus­lassen von Kategorien.
2. Teilen Sie wie bei der let­zten Übung den Daten­satz in einen Train­ings- und einen Test­daten­satz ein. Teilen Sie die Doku­mente möglichst so auf, dass jede Klasse in etwa die gle­iche An­zahl Train­ings- wie Test­beispiele be­sitzt.
3. Er­stellen Sie für jedes Doku­ment den TF-Vektor mit absoluten (für Naive Bayes) und relativen Häufigkeiten (für Rocchio) und spe­ich­ern Sie diese sowie die Labe­lin­for­ma­tion ab.
   Definieren Sie die Ter­mmenge als alle Terme, die in der Train­ings­menge vorkom­men.

2. Sim­ple Naive Bayes (1,5 P)

Im­ple­men­tieren Sie einen ein­fachen Naive-Bayes-Klassifizierer. Verwen­den Sie bei der Schätzung der Termwahrschein­lichkeit­en die Laplace-Ko­r­rek­tur und die Log­a­rith­mierung zur Ver­mei­dung von nu­merischen Schwierigkeit­en.

Zwar läuft auf den Folien zur Bes­tim­mung von p(D|c) das Pro­dukt (bzw. die Summe) über die Se­quenz der To­kens t von D, aber es ist hier sin­voller, es wie bei der Formel zu dem Full Multi­no­mi­al Model über die Terme w im Vok­ab­u­lar laufen zu lassen, da Sie so die TF-Vek­toren di­rekt an­wen­den können. Lassen Sie aber den Multi­no­mi­alko­ef­fizien­ten, der beim Full Multi­no­mi­al Model einge­set­zt wird, weg.

3. Rocchio Algorithmus (1,5 P)

Implementieren Sie den einfachen Rocchio Algorithmus. Verwenden Sie dafür die Formel in den Folien mit einer Iteration (i=1..1), alpha=0, beta=1/|R|, gamma=0,1/|I| und die normalisierten Vektoren. Sie finden eine ausführlichere Beschreibung des Algorithmus auch in Abschnitt 6.7 in Machine learning in automated text categorization (hier mit beta=1 und gamma=0,1). Führen Sie den Vergleich einer Test-Instanz zu den Klassenprototypen anhand der Kosinus-Similarität durch.

 

4. Eval­u­a­tion (6 P)

1. Wen­den Sie den Naive Bayes auf die Test­dat­en an und geben Sie die Multiclass-Konfusionsmatrix an.
   In­ter­pretieren Sie die Konfusionmatrix.
2. Berech­nen Sie an­hand der Kon­fu­sion­ma­trix die Per­for­mance-Maße Ac­curacy, Pre­ci­sion und Re­call unter Ver­wen­dung von jeweils Mi­cro- und Macro-Av­er­ag­ing und stellen diese Werte tabel­lar­isch dar.
3. Wenden Sie den Rocchio-Algorithmus auf den Testdaten an und berechnen Sie ebenfalls die in der vorherigen Aufgabe aufgezählten Maße und die Konfusionsmatrix. Bewerten Sie beide Algorithmen, welche sind ihre Stärken und Schwächen, welcher ist für welche Anforderung geeigneter? Vergessen Sie dabei nicht die Laufzeit.
4. Wählen Sie aufgrund Ihrer Erfahrungen mit Naive Bayes und Rocchio einen der beiden Algorithmen aus und wenden Sie den in Teilaufgabe 1 oder 3 gelernten Klassifizierer auf die in Übung 2 gecrawlten Dokumente an. D.h. trainieren Sie z.B. auf dem 20 newsgroup Datensatz, klassifizieren aber auf den heruntergeladenen Seiten.
   Betrachten Sie die 10 Seiten mit den konfidentesten Vorhersagen, d.h. mit der höchsten Wahrscheinlichkeit bei Naive Bayes bzw. der höchsten Kosinus-Similarität bei Rocchio, und zeigen Sie einige Beispiele auf.
   Wie gut passen die Vorhersagen? Wie geeignet schätzen Sie dieses Vorgehen z.B. für Information Retrieval ein?
5. Angenommen, der gamma-parameter bei Rocchio ist auf 0 gesetzt und sie verwenden Feature-Vektoren mit absoluten Häufigkeiten. Vergleichen Sie das resultierende Modell mit dem von Naive Bayes. Was fällt Ihnen auf?

 

Mögliche Datensätze

• (mini) 20 news­groups Datensatz: Einige der Post­ing sind in mehreren Ord­ner unter ver­schiede­nen Namen vertreten. Das be­deutet, daß es Doku­mente gle­ichen In­halts aber mit ver­schiede­nen La­bels gibt. Es be­deut­ed auch, dass die Eval­u­a­tion etwas zu pes­simistisch ist, da ein Train­ings­doku­ment beim Testen erneut auf­tauchen kann, dann aber zwin­gend mit einen an­deren Label als im Train­ing.
  Die Doku­mente en­thal­ten einen Head­er inklu­sive der Label-Information. Diesen Head­er sollte man nicht in den Fea­ture-Vek­tor ein­fließen lassen, da er Daten enthält, die man in der Prax­is nicht zu Verfügung hätte.
• We­bKB-Daten­satz
• telegraph-Datensatz: Der Datensatz enthält viele leere Datensätze. Bereinigen Sie zunächst die Dokumente. Auch indem Sie Links (Text zwischen eckigen Klammern) und nur den Text mit zur Share Überschrift verwenden. Im Kopf jedes Dokumentes stehen die hierarchischen Kategorien. Schauen Sie sich die Klassenstruktur zunächst an und wählen Sie nach Belieben aus.
• reuters-21578: Dieser Datensatz enthält etwa 100 Klassen, einige von ihnen kommen nur sehr selten vor. Ignorieren Sie Dokumente, die keinen oder mehr als einen =TOPICS=- Eintrag haben.

 

Hin­weise

• Alle notwendi­gen Def­i­ni­tio­nen für Naive Bayes find­en Sie im Folien­satz text clas­si­fi­ca­tion.
• Auf­gabe 1: Um die Aufteilung in Test- und Train­ings­menge ein wenig zu vere­in­fachen, können Sie die Gesamtheit der Doku­mente durch eine zufällige Auswahl aufteilen. Zwar we­ichen dann die Größen­verhält­nisse von Train­ing- zu Test­menge der einzel­nen Klassen etwas von einan­der ab, aber bei 100 oder mehr Doku­menten pro Klasse sind größere Abwe­ichun­gen sehr un­wahrschein­lich.
• Aufgabe 4.4: Falls Sie Übung 2 nicht bearbeitet haben, starten sie z.B. einfach wget mit wget -nd -nc -r -l0 http://startseite.ihrer.wahl und brechen ab, sobald Sie ausreichend viele HTML-Seiten heruntergeladen haben.