Sem­i­nar aus maschinellem Ler­nen - WS 08/09

Im Rah­men dieses Sem­i­nars wer­den wir neue Forschungsergeb­nisse aus dem Bere­ich maschinelles Ler­nen diskutieren.​ Ausgewählt wer­den neuere Pub­lika­tio­nen aus den rel­e­van­ten Jour­nalen des Ge­bi­ets, ins­beson­dere aus Ma­chine Learn­ing und dem Jour­nal of Ma­chine Learn­ing Re­search, sowie aus den wichtig­sten Kon­feren­zen.

Der diesjährige The­men­schw­er­punkt ist Graph Mining.​ Während kon­ven­tionelle Ler­nal­go­rith­men davon aus­ge­hen, daß Ob­jek­te in einer ein­fachen At­tribut/Wert-Repräsen­ta­tion vor­liegen, ver­suchen Graph Min­ing Meth­o­d­en Muster oder Regelmäßkeit­en in kom­plex­eren Daten­struk­turen wie z.​B.​ Graphen zu finden.​ Data Min­ing- und Lern-Meth­o­d­en, die sich diesen Gegeben­heit­en an­passen, bilden den Schw­er­punkt dieses Sem­i­nars.

Zeit und Ort

Ablauf

Jede/r Stu­dent/in erhält einen oder mehrere Fachar­tikel zur Ausar­beitung, deren wesentliche As­pek­te dann in einem ca. 30-minütigen Vor­trag vorgestellt und im An­schluß von allen disku­tiert wer­den sollen.​ Die Vorträge und/oder Folien können wahlweise auf Deutsch oder En­glisch gehal­ten wer­den.

Vorken­nt­nisse

Da diese Ar­tikel dem let­zten Stand der Forschung entsprechen, wird ein­er­seits er­wartet, dass entsprechende Grund­ken­nt­nisse (und In­ter­esse!) in maschinellem Ler­nen und Data Min­ing mit­ge­bracht wer­den, dass man sich aber an­der­er­seits im Zuge der Vor­bere­itung auch selb­ständig mit der The­matik weit­er ver­traut macht und ggf.​ auch weit­erführende bzw.​ grundle­gende Lit­er­atur zu Rate zieht (bitte Quellen nen­nen).

Beno­tung

In die Gesamt­note fließen die Ausar­beitung des Vor­trags (Folien), die Präsen­ta­tion, die Beant­wor­tung von Fra­gen zum Vor­trag, sowie die ak­tive Teil­nahme an der Diskus­sion bei den Vorträgen an­der­er ein.​ Eine schriftliche Ausar­beitung ist nicht notwendig.

Im Vorder­grund der Gesamt­beno­tung steht je­doch die selb­ständige Au­seinan­der­set­zung mit dem Problem.​ Für eine sehr gute (1.​x) Beu­rteilung muß klar sein, dass Sie die fraglichen Ar­beit­en ver­standen haben und von den vor­liegen­den Pa­pers ab­strahieren können.​ Eine ex­ak­te Wieder­gabe des In­halts der Pa­piere führt nur zu einer Beurteilung mit 2.​x,​ außeror­dentlich schwache Leis­tun­gen in einem der genan­nten Punk­te zu 3.​x oder schlechter.

The­men

Min­ing Fre­quent Closed Graph Pat­terns

• Xifeng Yan, Ji­awei Han: gSpan: Graph-Based Sub­struc­ture Pat­tern Min­ing. ICDM 2002: 721-724
• Xifeng Yan, Ji­awei Han: Close­G­raph: min­ing closed fre­quent graph pat­terns. KDD 2003: 286-295

Graph-Based In­duc­tion

• Kenichi Yoshi­da, Hi­roshi Mo­to­da, Nitin In­durkhya: Graph-based in­duc­tion as a uni­fied learn­ing frame­work. Ap­plied In­tel­li­gence 4(3): 297-316 (1994)
• Takashi Mat­su­da, Tadashi Ho­ri­uchi, Hi­roshi Mo­to­da, Takashi Washio: Ex­ten­sion of Graph-Based In­duc­tion for Gen­er­al Graph Struc­tured Data. Knowl.​ Disc.​ and Data Mining.​ Cur. Iss.​ and New Appl.​ :​ 420-431 (2000)
• Takashi Mat­su­da, Hi­roshi Mo­to­da, Tet­suya Yoshi­da, Takashi Washio: Knowl­edge Dis­cov­ery from Struc­tured Data by Beam-Wise Graph-Based In­duc­tion PRI­CAI 2002: 123-141 (2002)

Fre­quent Tree Min­ing - PathJoin

• Wang, K.,​ Liu, H.:​ Dis­cov­er­ing Typ­i­cal Struc­tures of Doc­u­ments: A Road Map Ap­proach, 21st An­nu­al In­ter­na­tion­al ACM SIGIR Con­fer­ence on Re­search and De­vel­op­ment in In­for­ma­tion Re­trieval, 1998.
• Xiao, Y.,​ Yao, J.​-F.,​ Li, Z.,​ Dunham, M.:​ Ef­fi­cient Data Min­ing for Max­i­mal Fre­quent Sub­trees, Pro­ceed­ings of the 2003 IEEE In­ter­na­tion­al Con­fer­ence on Data Min­ing (ICDM’03), Novem­ber 2003.

Fre­quent Tree Min­ing - TreeM­iner and SLEUTH

• Mo­hammed Javeed Zaki: Ef­fi­cient­ly Min­ing Fre­quent Trees in a For­est: Al­go­rithms and Ap­pli­ca­tions. IEEE Trans.​ Knowl.​ Data Eng. 17(8): 1021-1035 (2005)
• Mo­hammed Javeed Zaki: Ef­fi­cient­ly Min­ing Fre­quent Em­bed­ded Un­ordered Trees. Fundam.​ Inform. 66(1-2): 33-52 (2005)

Fre­quent Tree Min­ing - Freqt, Unot, uFre­qt

• Asai, T.,​ Abe, K.,​ Kawasoe, S.,​ Arimura, H.,​ Sata­mo­to, H.,​ Arikawa, S.:​ Ef­fi­cient Sub­struc­ture Dis­cov­ery from Large Se­mi-Struc­tured Data, 2nd SIAM Int.​ Conf.​ on Data Min­ing, April 2002.
• Asai, T.,​ Arimura, H.,​ Uno, T.,​ Nakano, S.:​ Dis­cov­er­ing Fre­quent Sub­struc­tures in Large Un­ordered Trees, The 6th In­ter­na­tion­al Con­fer­ence on Dis­cov­ery Sci­ence, Oc­to­ber 2003.
• Ni­jssen, S.,​ Kok, J.​ N.:​ Ef­fi­cient Dis­cov­ery of Fre­quent Un­ordered Trees, First In­ter­na­tion­al Work­shop on Min­ing Graphs, Trees and Se­quences, 2003.

Fre­quent Tree Min­ing - Min­ing Free Trees

• Yun Chi, Yirong Yang, Richard R.​ Muntz. Canon­i­cal Forms for La­beled Trees and Their Ap­pli­ca­tions in Fre­quent Sub­tree Min­ing. Knowl­edge and In­for­ma­tion Sys­tems, vol. 8, no. 2, pp. 203-234, 2005.​
• RÃŒckert, U.,​ Kramer, S.:​ Fre­quent Free Tree Dis­cov­ery in Graph Data, Spe­cial Track on Data Min­ing, ACM Sym­po­sium on Ap­plied Com­put­ing (SAC’04), 2004.

Fre­quent Tree Min­ing - Closed and Max­i­mal Sets (1 Per­son)

• Yun Chi, Yi Xia, Yirong Yang, Richard R.​ Muntz. Min­ing Closed and Max­i­mal Fre­quent Sub­trees from Databas­es of La­beled Root­ed Trees. IEEE Trans­ac­tions on Knowl­edge and Data En­gi­neer­ing, Vol. 17, No. 2, pp. 190-202, 2005.​

Min­ing of Fre­quent Graphs and Fre­quent ge­o­met­ric Graphs

• Michi­hi­ro Ku­ramochi, George Karyp­is: An Ef­fi­cient Al­go­rithm for Dis­cov­er­ing Fre­quent Sub­graphs. IEEE Trans.​ Knowl.​ Data Eng. 16(9): 1038-1051 (2004)
• Michi­hi­ro Ku­ramochi, George Karyp­is: Dis­cov­er­ing fre­quent ge­o­met­ric sub­graphs. Inf.​ Syst. 32(8): 1101-1120 (2007)

Min­ing Fre­quent La­beled Graphs

• Ak­i­hi­ro Inokuchi, Takashi Washio, Hi­roshi Mo­to­da: Com­plete Min­ing of Fre­quent Pat­terns from Graphs: Min­ing Graph Data. Ma­chine Learn­ing (ML) 50(3):321-354 (2003)
• Ak­i­hi­ro Inokuchi, Takashi Washio, Hi­roshi Mo­to­da: A Gen­er­al Frame­work for Min­ing Fre­quent Sub­graphs from La­beled Graphs.​ Fundam. Inform.​ (FUIN) 66(1-2):53-82 (2005)

MDL-Based Sub­struc­ture Dis­cov­ery - Sub­Due

• Diane J.​ Cook, Lawrence B.​ Holder. Sub­struc­ture Dis­cov­ery Using Min­i­mum De­scrip­tion Length and Back­ground Knowl­edge. J.​ Artif.​ Intell.​ Res. (JAIR) 1: 231-255 (1994)
• Ist­van Jony­er, Diane J.​ Cook, Lawrence B.​ Holder: Graph-Based Hi­er­ar­chi­cal Con­cep­tu­al Clus­ter­ing. Jour­nal of Ma­chine Learn­ing Re­search 2: 19-43 (2001)