Seminar aus maschinellem Lernen - WS 08/09

Im Rahmen dieses Seminars werden wir neue Forschungsergebnisse aus dem Bereich maschinelles Lernen diskutieren. Ausgewählt werden neuere Publikationen aus den relevanten Journalen des Gebiets, insbesondere aus Machine Learning und dem Journal of Machine Learning Research, sowie aus den wichtigsten Konferenzen.

Der diesjährige Themenschwerpunkt ist Graph Mining. Während konventionelle Lernalgorithmen davon ausgehen, daß Objekte in einer einfachen Attribut/Wert-Repräsentation vorliegen, versuchen Graph Mining Methoden Muster oder Regelmäßkeiten in komplexeren Datenstrukturen wie z.B. Graphen zu finden. Data Mining- und Lern-Methoden, die sich diesen Gegebenheiten anpassen, bilden den Schwerpunkt dieses Seminars.

Zeit und Ort

Ablauf

Jede/r Student/in erhält einen oder mehrere Fachartikel zur Ausarbeitung, deren wesentliche Aspekte dann in einem ca. 30-minütigen Vortrag vorgestellt und im Anschluß von allen diskutiert werden sollen. Die Vorträge und/oder Folien können wahlweise auf Deutsch oder Englisch gehalten werden.

Vorkenntnisse

Da diese Artikel dem letzten Stand der Forschung entsprechen, wird einerseits erwartet, dass entsprechende Grundkenntnisse (und Interesse!) in maschinellem Lernen und Data Mining mitgebracht werden, dass man sich aber andererseits im Zuge der Vorbereitung auch selbständig mit der Thematik weiter vertraut macht und ggf. auch weiterführende bzw. grundlegende Literatur zu Rate zieht (bitte Quellen nennen).

Benotung

In die Gesamtnote fließen die Ausarbeitung des Vortrags (Folien), die Präsentation, die Beantwortung von Fragen zum Vortrag, sowie die aktive Teilnahme an der Diskussion bei den Vorträgen anderer ein. Eine schriftliche Ausarbeitung ist nicht notwendig.

Im Vordergrund der Gesamtbenotung steht jedoch die selbständige Auseinandersetzung mit dem Problem. Für eine sehr gute (1.x) Beurteilung muß klar sein, dass Sie die fraglichen Arbeiten verstanden haben und von den vorliegenden Papers abstrahieren können. Eine exakte Wiedergabe des Inhalts der Papiere führt nur zu einer Beurteilung mit 2.x, außerordentlich schwache Leistungen in einem der genannten Punkte zu 3.x oder schlechter.

Themen

Mining Frequent Closed Graph Patterns

• Xifeng Yan, Jiawei Han: gSpan: Graph-Based Substructure Pattern Mining. ICDM 2002: 721-724
• Xifeng Yan, Jiawei Han: CloseGraph: mining closed frequent graph patterns. KDD 2003: 286-295

Graph-Based Induction

• Kenichi Yoshida, Hiroshi Motoda, Nitin Indurkhya: Graph-based induction as a unified learning framework. Applied Intelligence 4(3): 297-316 (1994)
• Takashi Matsuda, Tadashi Horiuchi, Hiroshi Motoda, Takashi Washio: Extension of Graph-Based Induction for General Graph Structured Data. Knowl. Disc. and Data Mining. Cur. Iss. and New Appl. : 420-431 (2000)
• Takashi Matsuda, Hiroshi Motoda, Tetsuya Yoshida, Takashi Washio: Knowledge Discovery from Structured Data by Beam-Wise Graph-Based Induction PRICAI 2002: 123-141 (2002)

Frequent Tree Mining - PathJoin

• Wang, K., Liu, H.: Discovering Typical Structures of Documents: A Road Map Approach, 21st Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, 1998.
• Xiao, Y., Yao, J.-F., Li, Z., Dunham, M.: Efficient Data Mining for Maximal Frequent Subtrees, Proceedings of the 2003 IEEE International Conference on Data Mining (ICDM’03), November 2003.

Frequent Tree Mining - TreeMiner and SLEUTH

• Mohammed Javeed Zaki: Efficiently Mining Frequent Trees in a Forest: Algorithms and Applications. IEEE Trans. Knowl. Data Eng. 17(8): 1021-1035 (2005)
• Mohammed Javeed Zaki: Efficiently Mining Frequent Embedded Unordered Trees. Fundam. Inform. 66(1-2): 33-52 (2005)

Frequent Tree Mining - Freqt, Unot, uFreqt

• Asai, T., Abe, K., Kawasoe, S., Arimura, H., Satamoto, H., Arikawa, S.: Efficient Substructure Discovery from Large Semi-Structured Data, 2nd SIAM Int. Conf. on Data Mining, April 2002.
• Asai, T., Arimura, H., Uno, T., Nakano, S.: Discovering Frequent Substructures in Large Unordered Trees, The 6th International Conference on Discovery Science, October 2003.
• Nijssen, S., Kok, J. N.: Efficient Discovery of Frequent Unordered Trees, First International Workshop on Mining Graphs, Trees and Sequences, 2003.

Frequent Tree Mining - Mining Free Trees

• Yun Chi, Yirong Yang, Richard R. Muntz. Canonical Forms for Labeled Trees and Their Applications in Frequent Subtree Mining. Knowledge and Information Systems, vol. 8, no. 2, pp. 203-234, 2005.
• RÃŒckert, U., Kramer, S.: Frequent Free Tree Discovery in Graph Data, Special Track on Data Mining, ACM Symposium on Applied Computing (SAC’04), 2004.

Frequent Tree Mining - Closed and Maximal Sets (1 Person)

• Yun Chi, Yi Xia, Yirong Yang, Richard R. Muntz. Mining Closed and Maximal Frequent Subtrees from Databases of Labeled Rooted Trees. IEEE Transactions on Knowledge and Data Engineering, Vol. 17, No. 2, pp. 190-202, 2005.

Mining of Frequent Graphs and Frequent geometric Graphs

• Michihiro Kuramochi, George Karypis: An Efficient Algorithm for Discovering Frequent Subgraphs. IEEE Trans. Knowl. Data Eng. 16(9): 1038-1051 (2004)
• Michihiro Kuramochi, George Karypis: Discovering frequent geometric subgraphs. Inf. Syst. 32(8): 1101-1120 (2007)

Mining Frequent Labeled Graphs

• Akihiro Inokuchi, Takashi Washio, Hiroshi Motoda: Complete Mining of Frequent Patterns from Graphs: Mining Graph Data. Machine Learning (ML) 50(3):321-354 (2003)
• Akihiro Inokuchi, Takashi Washio, Hiroshi Motoda: A General Framework for Mining Frequent Subgraphs from Labeled Graphs. Fundam. Inform. (FUIN) 66(1-2):53-82 (2005)

MDL-Based Substructure Discovery - SubDue

• Diane J. Cook, Lawrence B. Holder. Substructure Discovery Using Minimum Description Length and Background Knowledge. J. Artif. Intell. Res. (JAIR) 1: 231-255 (1994)
• Istvan Jonyer, Diane J. Cook, Lawrence B. Holder: Graph-Based Hierarchical Conceptual Clustering. Journal of Machine Learning Research 2: 19-43 (2001)