Merkmalsgenerierung fuer die Wissensentdeckung

044261 D0 10.00 - 12.00 GB IV/SR113, Prof. Dr. Morik

Beginn: 15.10.2003

Inhalt: Das maschinelle Lernen hat sich von der Analyse vorbereiteter Beispielsätze zur Wissensentdeckung in sehr großen Datenmengen, die nicht eigens für das Lernen erhoben wurden, weiterentwickelt.
Dabei werden nun auch Bilddaten, Zeitreihen, Volltexte und Audiodaten einbezogen. Für die klassischen Lernverfahren stellt dies eine Herausforderung dar, denn diese Daten sind hochdimensional (sehr viele Merkmale), komplex (z.B. zeitliche Struktur) und enthalten oft nicht einzeln aussagekräftige Merkmale (z.B. sind Wörter für sich allein genommen nicht charakteristisch für einen Text). Statt nun neue Verfahren zu entwickeln, werden statt dessen die gegebenen Daten in solche überführt, die erfolgreich analysiert werden können.

Merkmalsauswahl: Man wählt aus den vielen Merkmalen die besten aus, man reduziert den hochdimensionalen Raum auf einen Raum mit weniger Dimensionen, in dem sich Wissen leichter entdecken lässt (Merkmalsselektion, Dimensionsreduktion).

• Allgemein:
  
  

  Bi/etal/2003a	Bi, Jinbo and Bennett, Kristin and Embrechts, Mark and Breneman, Curt and Song, Minghu (2003). Dimensionality Reduction via Sparse Support Vector Machines. JMLR Special Issue on Variable and Feature Selection, pages 1229--1243. 3. [.pdf]
  Globerson/Tishby/2003a	Globerson, Amir and Tishby, Naftali (2003). Sufficient Dimensionality Reduction. JMLR Special Issue on Variable and Feature Selection, (3):1307--1331. [.pdf]
  Blum/Langley/97a	Blum, Avrim L. and Langley, Pat (1997). Selection of Relevant Features and Examples in Machine Learning. Artificial Intelligence, pages 245--271. [.pdf]
  Devaney/Ram/97a	Devaney, M. and Ram, A. (1997). Efficient Feature Selection in Conceptual Clustering. In The Proceedings of the Fourteenth International Conference on Machine Learning. . [.pdf]
  Kohave/John/97a	Kohavi, R. and John, G.H. (1997). Wrappers for Feature Subset Selection. Artificial Intelligence, Special Issue on Relevance, 1--2 pages 273--324. [.pdf]
  Aha/Bankert/96a	Aha, David W. and Bankert Richard L. (1996). A Comparative Evaluation of Sequential Feature Selection Algorithms. In Learning from Data, chapter 4, pages 199--206. Springer. [.pdf]

  
  
  
• Text:
  
  

  Bekkerman/etal/2003a	Bekkerman, Ron and El-Yaniv, Ran and Tishby, Naftali and Winter, Yoad (2003). Distributional Word Clusters vs. Words for Text Categorization. JMLR Special Issue on Variable and Feature Selection, (3):1183--1208. [.pdf]
  Dhillon/etal/2003a	Dhillon, Inderji S. and Subramanyam, Mallela and Kumar, Rahul (2003). A Divisive Information-Theoretic Feature Clustering Algorithm for Text Classification. JMLR Special Issue on Variable and Feature Selection, (3):1265--1287. [.pdf]
  Forman/2003a	Forman, George (2003). An Extensive Empirical Study of Feature Selection Metrics for Text Classification. JMLR Special Issue on Variable and Feature Selection, (3):1289--1305. [.pdf]
  Joachims/97b	T. Joachims (1997). Text Categorization with Support Vector Machines: Learning with Many Relevant Features. Technical report, Universität Dortmund, LS VIII-Report. [.ps.gz] [.pdf]

  
  
  
• Zeit:
  
  

  Keogh/etal/2001b

  Keogh, Eamonn and Chakrabarti, Kaushik and Pazzani, Michael and Mehrotra, Sharad (2001). Dimensionality Reduction for Fast Similarity Search in Large Time Series Databases. Knowledge and Information Systems, (3(3)):263--286. [.pdf]

  
  
  

Merkmalsextraktion: Man erzeugt (mit einem Lernverfahren) aus den Rohdaten Muster, die als Merkmal in ein (anderes) Lernverfahren eingehen oder zum Retrieval verwendet werden.

Torkkola/2003a

Torkkola, Kari (2003). Feature Extraction by Non-Parametric Mutual Information Maximization. JMLR Special Issue on Variable and Feature Selection, pages 1415--1438. [.pdf]

• Zeitdaten:
  
  

  Lin/etal/2002a	Jessica Lin and Eamonn Keough and Stefano Lonardi and Pranav Patel (2002). Finding Motifs in Time Series. In Procs. of the 2nd Workshop on Temporal Data Mining. . [.pdf]
  Keogh/etal/2001a	Keogh, Eamonn and Chu, Selina and Hart, David and Pazzani, Michael (2001). An Online Algorithm for Segmenting Time Series. In Cercone, Nick and Lin, T.Y. and Wu, Xindong, editor(s), Proceedings of the 2001 IEEE International Conference on Data Mining, pages 289--296. . [.pdf]
  Keogh/Pazzani/2000a	Keogh, Eamonn and Pazzani, Michael (2000). Scaling up Dynamic Time Warping for Datamining Applications. In Proceedings of the 6th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 285--289. ACM Press. [.pdf]
  Das/etal/98a	Gautam Das and King-Ip Lin and Heikki Mannila and Gopal Renganathan and Padhraic Smyth (1998). Rule Discovery from Time Series. In Rakesh Agrawal and Paul E. Stolorz and Gregory Piatetsky-Shapiro, editor(s), Proceedings of the Fourth International Conference on Knowledge Discovery and Data Mining (KDD-98), pages 16 -- 22. AAAI Press. [.pdf]

  
  
  
• Bilddaten:
  
  

  Ng/Martin/2001a	Chee Un Ng and Graham R. Martin (2001). Content-Description Interfaces for Medical Imaging. Technical report, University of Warwick, U.K.. [.pdf]
  Mokhtarian/etal/96a	Farzin Mokhtarian and Sadegh Abbasi and Josef Kittler (1996). Efficient and robust retrieval by shape content through curvature scale space. In Procs. Int. Workshop on Image Databases and MultiMedia Search, pages 35--42. . [.pdf]
  Fua/Hanson/91a	P. Fua and A. J. Hanson (1991). An Optimization Framework for Feature Extraction. Machine Vision and Applications, 4 pages 59--87. [.pdf]
  Mokhtarian/Mackworth/86a	Farzin Mokhtarian and Alan Mackworth (1986). Scale-based description and recognition of planar curves and two-dimensional shapes. IEEE Transactions on Pattern Analysis and Machine Intelligence, pages 34--43.

  
  
  
• Musikdaten:
  
  

  Kurth/Clausen/2001a

  Frank Kurth and Michael Clausen (2001). Full-Text Indexing of Very-Large Audio Data Bases. In 110th Convention of the Audio Engineering Society. . [.pdf]

  
  
  

Merkmalserzeugung: Aus den gegebenen Merkmalen werden andere, besser für das Lernen geeignete Merkmale erzeugt z.B. durch Aggregation, Diskretisierung oder Einbeziehung von Hintergrundwissen.

Ritthoff/etal/2002b	Ritthoff, Oliver and Klinkenberg, Ralf and Fischer, Simon and Mierswa, Ingo (2002). A Hybrid Approach to Feature Selection and Generation Using an Evolutionary Algorithm. In Bullinaria, John A., editor(s), Proceedings of the 2002 U.K. Workshop on Computational Intelligence (UKCI-02), pages 147--154. University of Birmingham. [.ps]
Chen/Petrounias/99a	Chen, Xiaodong and Petrounias, Ilias (1999). Mining Temporal Features in Association Rules. In Proceedings of the 3rd European Conference on the Principles of Data Mining and Knowledge Discovery in series Lectures Notes in Computer Science, pages 295--300. Springer.
Bloedorn/Michalski/98a	Eric Bloedorn and Ryszard Michalski (1998). Data-driven Constructive Induction: Methodology and Applications. In Feature Extraction, Construction, and Selection -- A Data Mining Perpective, chapter 4, pages 51 -- 68. Kluwer. [.pdf]
Utgoff/Precup/98a	Utgoff, P. and Precup, D. (1998). Constructive Function Approximation. In H.Liu and H. Motoda, editor(s), Feature Extraction Construction and Selection, A Data Mining Perspective, pages 219 -- 235. Kluwer Academic Publishers. [.pdf]
Dougherty/etal/95a	James Dougherty and Ron Kohavi and Mehran Sahami (1995). Supervised and Unsupervised Discretization of Continuous Features. In Armand Prieditis and Stuart J. Russell, editor(s), Proceedings of the Twelfth International Conference on Machine Learning. Morgan Kaufmann. [.pdf]
Srinivasan/etal/95b	Srinivasan, A. and Muggleton, S.H. and Sternberg, M.J.E. and King, R.D. (1995). Theories for Mutagenicity: A Study in First--Order and Feature--Based Induction. Artificial Intelligence, . [.pdf]

In dem Seminar sollen die Ansätze und Methoden der Merkmalsgenerierung gemeinsam erarbeitet werden in Hinblick auf die Aufgabenstellungen

• Textkategorisierung
• Bild- oder Musik-Retrieval
• Erkennen zeitlicher Zusammenhänge.

Die Lernverfahren reichen von der numerischen Stützvektormethode bis hin zu (conceptual) clustering und induktiver logischer Programmierung.

Folien