Übung 3 - Web Min­ing

Binäre Klas­si­fika­tion von In­ter­net-Seit­en

1.​ Daten be­sor­gen, Klassen definieren (1 P)

Be­sor­gen Se sich eine Samm­lung aus In­ter­net-Seit­en, die jew­eils einer von zwei Klassen zu­ge­ord­net sind.​ Z.​B. können Sie den course vs.​ non-course -Daten­satz von WebKB herun­ter­laden und davon die Dateien aus dem Ord­ner full­text ver­wen­den, oder Sie ver­wen­den zwei Klassen aus dem 4 Uni­ver­si­ties Data Set. Aber wir er­muti­gen Sie auch, an­dere Datensätze zu suchen oder selb­st einen in­ter­es­san­ten Daten­satz zu er­stellen, indem Sie Seit­en sam­meln (z.​B.​ von einer On­line-Zeitung) und diese binär klas­si­fizieren (z.​B.​ zwei bere­its ex­istierende Kat­e­gorien be­nutzen). 

Teilen Sie den Daten­satz ran­domisiert in Train­ings- und Test­menge im Verhältnis 1:1 auf.​ Wenn Sie wenig Daten haben, können Sie das Verhältnis auch zu­gun­sten der Train­ings­menge verschieben.​ Für das Train­ing soll­ten Sie wenig­stens auf 160 und für das Testen auf wenig­stens 80 Seit­en zurück­greifen können.

Beschreiben Sie Ihr Vorge­hen. 

2.​ Aufbere­itung der Daten (2 P)

Für Auf­gabe 3 ist es notwendig, ver­schiedene Datensätze zu produzieren.​ Die meis­ten der dafür notwendi­gen Ve­r­ar­beitungss­chritte haben Sie bere­its in vorheri­gen Übun­gen ken­nen­gel­ernt und angewandt.​ Sie soll­ten dabei in der Lage sein, die fol­gen­den Schritte durchzuführen.
  1. Doku­ment zu Wort-Liste
    Ex­trahieren Sie den In­halt der HTML-Seit­en und zer­legen Sie diesen Text in eine Liste von Wörtern.​ Was Wort hier be­deutet, legen Sie wieder selb­st fest.​ Geben Sie dies kurz an, d.​h.​ erklären Sie, was aus dem Orig­i­nal­doku­ment er­hal­ten bleibt und was wie re­duziert wird.
  2. Stop­p­wort-Fil­terung und Stem­ming
    Wen­den Sie auf die Liste von Wörtern Stop­p­wort-Fil­terung und Stem­ming an.​ Beachten Sie zu Stem­ming die Hin­weise am Ende.
  3. Wort-Liste zu TF-IDF-Vek­tor
    Wählen Sie als Menge der Terme alle Wörter, die in den Wort-Lis­ten des Train­ings­sets auftauchen.​ Bilden Sie für jedes Doku­ment den TF-IDF-Vek­tor, indem Sie für jeden Term seine rel­a­tive Häufigkeit in­ner­halb des Doku­ments (TF) mit sein­er log­a­rith­mierten in­versen Doc­u­ment Fre­quen­cy (IDF) mul­ti­plizieren (siehe Folien).
    Hin­weis: Sowohl die Def­i­ni­tion der Ter­mmenge als auch die IDF-Werte wer­den allein an­hand des Train­ings­sets er­stellt und beim Testen wiederverwendet.​ Denn abge­se­hen von der konkreten Testin­stanz sollen keine In­for­ma­tio­nen aus dem Test­set in die Klas­si­fika­tion ein­fließen.
  4. Ein­fache Fea­ture-Se­lec­tion
    Ihr Pro­gramm sollte in der Lage sein, die rel­e­van­testen N Wörter (Fea­tures) zu selektieren.​ Sortieren sie dabei ein­fach die Wörter nach ihrer Doku­menthäufigkeit im Train­ings­set und be­hal­ten sie die N häufig­sten.
  5. Sparse-Repräsen­ta­tion
    Überführen sie die Fea­ture-Vek­toren in eine Sparse-Repräsentation.​ Das Pro­gramm sollte diese zusam­men mit den Klass­en­in­for­ma­tio­nen im SVM­light/lib­svm-For­mat ab­spe­ich­ern können (siehe weit­er unten).

Wählen Sie ein geeignetes Doku­ment aus Ihrem Train­ings­daten­satz aus und geben Sie repräsen­ta­tiv für dieses das Ergeb­nis der einzel­nen Trans­for­ma­tions-Schritte an.​ Zeigen Sie ins­beson­dere das Sparse-For­mat, wenn Sie nur die 10 häufig­sten Wörter (Doku­menthäufigkeit) ver­wen­den sollen.​ Geben Sie auch an, wie viel Wörter vor und nach Stopp-Wort-Fil­terung und Stem­ming übrig geblieben sind.

 

3.​ Training und Eval­u­a­tion (7 P)

Zur au­toma­tis­chen Klas­si­fika­tion von In­ter­net-Seit­en soll nun eine Sup­port Vec­tor Ma­chine (SVM) trainiert werden.​ Verwen­den Sie hierfür nach Be­lieben en­twed­er das SVM­light- oder das lib­svm-Frame­work (oder ein an­deres ver­gle­ich­bares SVM-Paket, wenn Sie hi­er­mit bess­er ver­traut sind oder es in der von Ihnen präferierten Pro­gram­mier­sprache bess­er verfügbar ist). Als Per­for­manz-Maß soll hier im All­ge­meinen Ac­cu­ra­cy ver­wen­det wer­den.
  1. Machen Sie sich mit dem Frame­work und der von Ihnen gewählten Schnittstelle ver­traut, indem Sie eine Klas­si­fika­tions-SVM (clas­si­fi­ca­tion svm bzw. C-SVC) mit lin­earem Ker­nel (Pa­ram­e­ter -t 0), einem C-Pa­ram­e­ter von 50 (-C 50)  mit den in Auf­gabe 2 vor­bere­it­eten Daten trainieren und auf den vor­bere­it­eten Test­dat­en evaluieren.​ Verwen­den Sie dabei nur die häufig­sten z.​B.​ 1000 Wörter für das Trainieren und Testen.
    Geben Sie die Kon­fu­sion­s­ma­trix, die er­langte Ac­cu­ra­cy und die benötigte Train­ings- und Testzeit an.​ Vergle­ichen Sie die Ac­cu­ra­cy mit der eines Klas­si­fizier­ers, der immer die häufig­ste Klasse in den Train­ings­dat­en vorher­sagt (Base­line).
    Testen Sie mit höheren C-Pa­ram­e­tern, falls Sie ungewöhn­liche Re­sul­tate bekom­men (siehe auch Hin­weise am Ende).
    Fügen Sie wenig­stens für diese Teilauf­gabe auch die ver­wen­de­ten Train­ings- und Test­dateien im Sparse-For­mat Ihrer Ab­gabe bei.​ (1 P)
  2. Lassen Sie sich auf den Test­dat­en aus der er­sten Teilauf­gabe die Vorher­sage-"Wahrschein­lichkeit­en" oder Kon­fi­den­zen aus­geben (z.​B.​ Parame­ter -b 1 bei Lib­SVM) und er­stellen Sie hi­er­mit eine Re­call-Pre­ci­sion-Kurve.
    Dies er­re­ichen Sie, indem Sie statt der Ver­wen­dung der üblichen Schranke (üblicher­weise 0 bei Scores oder 0,5 bei Wahrschein­lichkeit­en) diese variieren.​  Sortieren Sie hierfür die Vorher­sagen nach ihrem Score und wählen Sie nacheinan­der jeden Score als Schranke.​ Ermit­teln Sie für diese Schranken Re­call und Pre­ci­sion und tra­gen Sie diese Werte-Paare in den Graphen ein.
    Beschreiben Sie die Kurve.​ Bestim­men sie aus der Kurve den Break-Even-Point (1,5 P).
  3. Zeigen Sie nun die Per­for­manz der SVM in Abhängigkeit der An­zahl der be­nutzten Features.​ Variieren Sie die An­zahl der rel­e­van­testen Fea­tures N und ze­ich­nen Sie die er­hal­te­nen Ac­cu­ra­cy-Werte in einem Lin­ien-Di­a­gramm in Abhängigkeit von N. Wählen Sie dabei an­fangs z.​B.​ für N einen Wert von 5 und erhöhen Sie diesen beim nächsten Schritt auf das Dop­pelte (also um 100%) bis Sie an die Gesam­tan­zahl der Fea­tures stoßen.​ Fügen Sie dabei zusätzliche Evaluierun­gen ein für Bere­iche mit einer hohen Stei­gung oder mit möglichen Wen­depunk­ten, d.​h.​ Punkte, an denen die Ac­cu­ra­cy plötzlich abfällt oder ansteigt.​ Zeichnen Sie in das gle­iche oder in ein zusätzlich­es Di­a­gramm die entsprechen­den Trainings-Laufzeiten.​ Inter­pretieren Sie die er­hal­te­nen Leis­tungskur­ven. 
    Hin­weis: Die Laufzeitmes­sung bei­der Pro­gramme ist nicht sehr präzise, we­shalb es sich emp­fiehlt, hierfür ex­terne Pro­gramme wie time für Linux oder Ähn­lich­es für Win­dows zu verwenden.​ (2 P)
  4. Denken Sie sich einen weit­eren As­pekt aus, den Sie für in­ter­es­sant hal­ten und den Sie gerne un­ter­suchen möchten, und stellen Sie ähn­liche Ver­gle­iche an.​ Dies kann z.​B.​ die Eval­u­a­tion in Abhängigkeit einer an­deren Größe N (z.​B.​ Anzahl Train­ings­beispiele), einer un­ter­schiedlichen Fea­ture-Gener­ierung (n-Gramme, Buch­staben­paare, Buch­staben, ...​) oder Gewich­tung (TF, an­dere), Veränderun­gen der SVM-Pa­ram­e­ter (Ker­nel-Typ, Fehler­tol­er­anz C), oder was Ihnen sonst noch einfällt.​ Versuchen Sie dabei, die Per­for­manz-Werte aus den vorheri­gen Auf­gaben zu schla­gen.
    Was kon­nten Sie in Ihren Ex­per­i­menten beobacht­en und was sind Ihre Schlussfol­gerun­gen? (1,5 P)
  5. Sie nehmen an einem Da­ta-Min­ing-Wet­tbe­werb teil, in dem es um binäre Klas­si­fizierung geht.​ Sie er­hal­ten vom Ve­r­anstal­ter eine Train­ings­menge, in denen die wahren Klassen bekan­nt sind und auf denen Sie Ihren Al­go­rith­mus trainieren können.​ Außerdem er­hal­ten Sie eine Evaluierungs­menge, auf der Sie nicht die Klassen kennen.​ Sie können aber dem Ve­r­anstal­ter eine Vorher­sage auf dieser Menge zuschick­en und er­hal­ten eine Rück­mel­dung über die Accuracy.​ Gewinner ist dann der­jenige mit der höchsten Ac­cu­ra­cy.
    Warum ist dieses Set­ting vom Ve­r­anstal­ter prob­lema­tisch? Wie kann man sich diese Schwach­stelle zu Nutze machen? Wie könnte man das Prob­lem lösen? (1 P)

 

Hin­weise zur Tex­tex­trak­tion aus HTML-Doku­menten

Soll­ten Sie Prob­leme mit HTML-Parsern in Ihrer Pro­gram­mier­sprache wie z.​B.​ mit Beau­ti­ful­Soup, htm­l2­text (Python), HTMLDocument.​getText(), html pars­er, html2text.​pl (perl) oder mit selb­st er­stell­ten Parsern haben, so könnten Sie auch ein etwas ro­bus­teres ex­ternes Pro­gramm aufrufen wie htm­l2­text oder die textbasierten Web­brows­er links, w3m und linx zum Ren­dern ver­wen­den und an­schließend die gener­ierte rohe Tex­taus­gabe parsen.

 

Hin­weise zu Stem­ming

Es ex­istiert eine Vielzahl an Stem­ming-Al­go­rith­men und Im­ple­men­tierung für die ver­schieden­sten Pro­gram­mi­er- und natürlichen Sprachen.​ Der bekan­nteste Al­go­rith­mus ist hi­er­bei der Porter Stem­mer Filter.​ Sie können aber auch jedes be­liebige an­dere verwenden.​ Hier eine kleine Auswahl:

 

Hin­weise zu den SVMs

  • Pa­ram­e­ter: Ver­wen­den Sie jew­eils die Stan­dard-Ein­stel­lun­gen der Pro­gramme falls nicht an­ders angegeben.​ Stellen Sie allerd­ings ins­beson­dere bei Ver­wen­dung von Wrap­pern sich­er, dass auch die ko­r­rek­ten Stan­dard­e­in­stel­lun­gen ver­wen­det werden.​ So gab es z.​B.​ in vorheri­gen Jahren Fälle, bei denen der gamma Wert des Ker­nels von Lib­SVM fälschlicher­weise auf Null geset­zt wurde.
  • Wrap­per: Sie können beide Frame­works jew­eils über geeignete Schnittstellen für Ihre Pro­gram­mier­sprache aufrufen (Ref­eren­zen auf den Home­pages), oder Sie rufen die Pro­gramme ein­fach ex­tern auf und ver­mei­den dabei auch gle­ich mögliche Prob­leme mit den Wrap­pern.
  • Daten­for­mat: Beide For­mate soll­ten kom­pat­i­bel zueinan­der sein, eine Spez­i­fizierung find­en Sie unter http://​svmlight.​joachims.​org/​ im How to use  Kapi­tel und geeignete Beispiele find­en sich unter http://​www.​csie.​ntu.​edu.​tw/​~cjlin/lib­svm­tools/datasets/binary.​html.
  • Falls Sie Auf­gabe 1 und 2 nicht lösen können, wählen Sie einen geeigneten Daten­satz (binäre Klassen, möglichst Text) aus http://​www.​csie.​ntu.​edu.​tw/​~cjlin/lib­svm­tools/datasets/ aus und ver­wen­den Sie diesen in Auf­gabe 3.
  • Je nach Vorver­ar­beitung der Daten kann es passieren, daß das Re­sul­tat der SVMs stets auf dem­sel­ben Niveau bleibt.​ Exper­i­men­tieren Sie in diesem Fall mit höheren oder auch niedrigeren C Parameter.​ Der C Pa­ram­e­ter kann hi­er­bei sogar in die Tausende gehen oder auch sehr nahe an Null sein.
Kontakt

small ke-icon

Knowledge Engineering Group

Fachbereich Informatik
TU Darmstadt

S2|02 D203
Hochschulstrasse 10

D-64289 Darmstadt

Sekretariat:
Telefon-Symbol+49 6151 16-21811
Fax-Symbol +49 6151 16-21812
E-Mail-Symbol info@ke.tu-darmstadt.de

 
A A A | Drucken | Impressum | Sitemap | Suche | Mobile Version
zum Seitenanfangzum Seitenanfang