Web Min­ing - Data Min­ing im In­ter­net

LVA 20.0101.1 und 20.0101.2 im Vor­lesungsverze­ich­nis der TU Darm­stadt, SS 08.​ Zur Übungs­seite

Die Klausurergeb­nisse hängen an der Pin­nwand neben Raum S202/E306 aus und sind auch über das We­bReg-Sys­tem aufrufbar.​ Die Klausurein­sicht find­et am Mittwoch, den 3.9.08 von 10-12 Uhr in E302 statt.

Forum

Für diese Ve­r­anstal­tung wurde bei der Fach­schaft ein Forum ein­gerichtet.

An­rech­nung

Diese Vor­lesung ist im Diplom­studi­um In­for­matik dem Bere­ich 3 (An­wen­dung­sori­en­tierte In­for­matik) bzw.​ im Mas­ter­studi­um In­for­matik dem Bere­ich Data and Knowl­edge En­gi­neer­ing zugeordnet.​ Sollten Sie die Vor­lesung In­for­ma­tion Re­trieval bei Thomas Hof­mann be­sucht haben, er­hal­ten Sie auf­grund der großen stof­flichen Überlap­pung für beide Vor­lesun­gen zusam­men nur 5 SWS.

Übersicht

Das World-Wide Web ver­schafft jedem In­ter­net-Us­er Zu­gang zu einer stetig wach­senden In­for­ma­tionsfülle, die ohne entsprechende Un­ter­stützung nicht mehr zu überschauen ist.​ Web Min­ing ist eine junge Forschungsrich­tung, die ver­sucht, das Prob­lem mit Hilfe von Tech­niken des Maschinellen Ler­nens und Data Min­ings in den Griff zu bekommen.​ In dieser Vor­lesung wer­den sowohl Grund­la­gen von In­for­ma­tion Re­trieval und Text Clas­si­fi­ca­tion ver­mit­telt, als auch auf die Aus­nutzung der Beson­der­heit­en von Web-Doku­menten (d.​h.,​ ihre Struk­turierung und ihre Ver­net­zung) einge­gan­gen.

Übun­gen

In den Übun­gen wer­den die Stu­den­ten prak­tis­che Im­ple­men­tierun­gen einiger der in der Vor­lesung be­han­del­ten Tech­niken er­stellen bzw.​ mit ex­istieren­den Sys­te­men arbeiten.​ Die Teil­nahme an den Übun­gen ist op­tion­al, es können aber Bonus­punk­te für die Klausur er­wor­ben wer­den, allerd­ings nur bei Beste­hen der Klausur.

All­ge­meine In­for­ma­tio­nen zu den Übun­gen und die ak­tuellen Übungsauf­gaben find­en Sie hier. Alles weit­ere wird in den Ve­r­anstal­tun­gen mit­geteilt oder an dieser Stelle bekan­nt gegeben.

Zeit­plan

• Do 03.04. Vor­lesung
• Di 08.04. Vor­lesung
• Do 10.04. Vor­lesung
• Di 15.04. Vor­lesung
• Do 17.04. Vor­lesung
• Di 22.04. 1.​ Übung
• Do 24.04. Keine Vor­lesung
• Di 29.04. Vor­lesung
• Do 01.05. Feiertag
• Di 06.05. 2.​ Übung
• Do 8.5. Vor­lesung
• Do 15.5. Vor­lesung
• Di 20.5. Übung
• Do 22.5. Feiertag
• Do 29.5. Vor­lesung
• Di 3.6. Übung
• Do 5.6. Vor­lesung
• Do 12.6. Vor­lesung
• Di 17.6. Übung
• Do 19.6. keine Vor­lesung
• Do 26.6. Vor­lesung
• Di 1.7. Übung
• Do 3.7. keine Vor­lesung

Klausur

Die Klausur aus diesem Semester:

• SS-08

Alte Klausuren:

• SS-04
• SS-05
• SS-06

Top­ics & Slides:

Mo­men­tan ver­linkt sind die Folien der let­zten Ve­r­anstal­tung, die auch dieses Jahr die Basis der Vor­lesung bilden werden.​ Gegen­falls wer­den die Folien je­doch im eini­gen Punk­ten angepaßt oder ergänzt werden.​ Die mod­i­fizierten Ver­sion wer­den dann die alten Ver­sio­nen er­set­zen (spätestens nach der jew­eili­gen Vor­lesung).

• In­tro­duc­tion
  • Web Min­ing Overview
  • The Web, HTTP, HTML, DOM, XPath
  • Data Min­ing Overview
  • Struc­tured, Se­mi-Struc­tured and Un­struc­tured Data
  • Sam­ple Web Min­ing Tasks
• In­for­ma­tion Re­trieval on the Web (Last Up­date: 11.​4.​)
  • search en­gines & web crawlers
  • doc­u­ment in­dex­ing
  • the vec­tor space model
  • in­vert­ed index
  • per­for­mance mea­sures (re­call & pre­ci­sion)
  • rel­e­vance feed­back
  • es­ti­mat­ing the size of the web
• Text Min­ing
  • text clas­si­fi­ca­tion (Last Up­date: 8.​5.​)
    • doc­u­ment rep­re­sen­ta­tion
    • in­duc­tion of clas­si­fiers (k-NN, Naive Bayes, SVMs, Rule Learn­ers)
    • Over­fit­ting Avoid­ance
    • Eval­u­a­tion of Clas­si­fiers
  • fea­ture en­gi­neer­ing (Last Up­date: 8.​5.​)
    • stop words
    • fea­ture sub­set se­lec­tion
    • n-grams
    • stem­ming
    • phras­es
    • la­tent se­man­tic in­dex­ing
  • semi- and un­su­per­vised learn­ing (Last up­date: 28.​5.​)
    • clus­ter­ing (k-means, bot­tom-up ag­glom­er­a­tive)
    • se­mi-su­per­vised learn­ing (ac­tive learn­ing, self-train­ing, co-train­ing)
• Struc­ture min­ing
  • the Web as a graph
  • hy­per­link-based rel­e­vance rank­ing (hubs and au­thor­i­ties, page rank)
  • hy­per­text clas­si­fi­ca­tion (Naive Method, Hy­per­Class, hy­per­link en­sem­bles)
• In­for­ma­tion Ex­trac­tion & Wrap­per In­duc­tion
  • con­ven­tion­al in­for­ma­tion ex­trac­tion (Au­toSlog)
  • struc­tured text (LR-Wrap­pers)
  • se­mi-struc­tured text (Soft­Mealy, WHISK, SRV, RAPI­ER)
• Rec­om­mender Sys­tems (Last Up­date: 1.​7.​)
  • mem­o­ry-based col­lab­o­ra­tive fil­ter­ing
  • mod­el-based col­lab­o­ra­tive fil­ter­ing

Text Books

Ein Großteil des Ma­te­ri­als, das in der Vor­lesung be­han­delt wird (und viel mehr), wird in diesem Buch abgedeckt: Soumen Chakrabar­ti: Min­ing the Web - Dis­cov­er­ing Knowl­edge from Hy­per­text Data. Mor­gan Kauf­mann Pub­lish­ers, 2003. Das Buch kann bei google books einge­se­hen wer­den. Folien zu dem Buch gibt es hier.
Einige Teile der Vor­lesung wer­den sich auch an diesem Buch ori­en­tieren: Christo­pher D.​ Manning, P.​ Raghavan and H.​ Schütze, In­tro­duc­tion to In­for­ma­tion Re­trieval, Cam­bridge Uni­ver­si­ty Press. 2008.​ Sowohl das Buch selb­st als auch Folien zu dem Buch können auf der Buch-Home­page run­terge­laden wer­den.

Ad­di­tion­al Read­ings

Zusätzliche In­for­ma­tio­nen find­en sich in fol­gen­den Re­sourcen:

• Gen­er­al Overviews:
  • Soumen Chakrabar­ti, Data Min­ing for Hy­per­text: A Tu­to­ri­al Sur­vey. ACM SIGKDD ex­plo­rations 1(2):1-11, Jan­uary 2000.
  • Jo­hannes Fürnkranz, Web Min­ing, Draft book chap­ter, 2004.
• Graph Prop­er­ties of the Web:
  • A.​ Broder, F.​ Maghoul, R.​ Kumar, P.​ Raghavan, S.​ Rajagopalan, R.​ Stata, A.​ Tomkins, and J.​ Wiener. Graph struc­ture in the Web. Com­put­er Net­works, 33(1-6):309--320, 2000.​ Special Issue Pro­ceed­ings 9th In­ter­na­tion­al World Wide Web Con­fer­ence (WWW9)
• Search En­gines:
  • http://​www.​searchenginewatch.​com/​re­sources/
• Text Min­ing:
  • Fab­rizio Se­bas­tiani, Ma­chine learn­ing in au­to­mat­ed text cat­e­go­riza­tion. ACM Com­put­ing Sur­veys, 34(1):1-47, 2002.
• Fea­ture En­gi­neer­ing
  • Yim­ing Yang, Jan O.​ Pedersen: A Com­par­a­tive Study on Fea­ture Se­lec­tion in Text Cat­e­go­riza­tion. Pro­ceed­ings of the In­ter­na­tion­al Con­fer­ence on Ma­chine Learn­ing (ICML-97), pp. 412-420, 1997.
• Hy­per­text Cat­e­go­riza­tion
• Soumen Chakrabar­ti, Byron E.​ Dom, and Piotr Indyk. En­hanced Hy­per­text Cat­e­go­riza­tion using Hy­per­links. In Pro­ceed­ings of ACM SIG­MOD-98, 1998.
• Jo­hannes Fürnkranz: Hy­per­link En­sem­bles: A Case Study in Hy­per­text Clas­si­fi­ca­tion. In­for­ma­tion Fu­sion 3(4):299-312, De­cem­ber 2002, Spe­cial Issue on Fu­sion of Mul­ti­ple Clas­si­fiers.
• In­for­ma­tion Ex­trac­tion:
  • Line Eikvil, In­for­ma­tion Ex­trac­tion from World Wide Web - A Sur­vey. Tech­ni­cal Re­port 945, Nor­we­gian Com­put­ing Cen­ter, July 1999.
• Web Usage Min­ing:
  • J.​ Srivas­ta­va, R.​ Cooley, M.​Deshpande, P.​Tan,​ Web usage min­ing: dis­cov­ery and ap­pli­ca­tions of web usage pat­terns from web data. ACM SIGKDD ex­plo­rations 1(2):12-23, Jan­uary 2000.
• Rec­om­mender Sys­tems:
  • John S.​ Breese and David Heck­er­man and Carl Kadie, Em­pir­i­cal Anal­y­sis of Pre­dic­tive Al­go­rithms for Col­lab­o­ra­tive Fil­ter­ing, Pro­ceed­ings of the 14th Con­fer­ence on Un­cer­tain­ty in Ar­ti­fi­cial In­tel­li­gence (UAI-98), pp. 43-52, 1998.
• Soft­ware:
  • Rain­bow (text clas­si­fi­ca­tion sys­tem)

Kon­takt

Jo­hannes Fürnkranz, Enel­do Loza Mencía, Lorenz Weizsäcker