Wissensentdeckung ist das Auffinden von interessanten und potenziell nützlichen Mustern in (sehr) großen Datenbeständen [8]. Das Gebiet hat seine Wurzeln im Bereich des maschinellen Lernens, der Datenbanken und in der Statistik. Der Prozess, der die gewünschten Ergebnisse liefert, besteht aus Dateninspektion, Datenbereinigung, Merkmalsextraktion, Merkmalsgenerierung, Merkmalsauswahl, Datentransformationen und Datenauswahl, bevor die Daten füur ein ausgewähltes Lernverfahren (data mining) geeignet sind. Die Analyseergebnisse werden nach verschiedenen Kriterien (z.B. recall und precision) bewertet. Wissensentdeckung wird sehr vielseitig eingesetzt, beispielsweise im customer relationship management, für das Filtern von spam mails, für die Analyse von Gen-Daten oder auch für Verkaufsprognosen. Die Nachfrage nach in diesem Bereich ausgebildeten Menschen ist besonders hoch.
Seit einigen Jahren gibt es einen internationalen Wettbewerb, den KDD-Cup, bei dem ein Datensatz und eine Analyseaufgabe publiziert werden. Aus den eingegangenen Lösungen werden die drei besten ausgewählt und bei der internationalen KDD-Tagung vorgestellt.
In der Projektgruppe sollen die Techniken zur Wissensentdeckung anhand der vergangenen preisgekrönten Arbeiten studiert werden. Es sind Meisterlösungen, an denen nicht nur die Verfahren, sondern auch ihre geschickte Anwendung studiert werden kann. Die Aufgabe des KDD-Cups wird alljährlich im Frühjahr veröffentlicht. Nach einer angemessenen Einarbeitungsphase wird die PG im Sommersemester 2004 einen eigenen Beitrag ausarbeiten und vielleicht den KDD-Cup 2004 gewinnen.
Der Wissensentdeckungsprozess
Die allgemeinen Schritte eines Wissensentdeckungsprozesses sind im cross
industrial standard dargelegt [5], aber beispielsweise auch in [3].
Bei der Wissensentdeckung spielen verschiedene Aufgabenstellungen eine Rolle. Werden aus Daten Modelle induziert, um damit Aussagen über noch unbekannte Fälle ableiten zu können, so spricht man bei einer Zuordnung zu Klassen von einem Klassifikationsproblem, bei der Vorhersage quantitativer Eigenschaften von einem Regressionsproblem. Ein Beispiel für eine Klassifikationsaufgabe ist die Erkennung von spam mails, ein Vorhersagemodell für Verkaufszahlen zu erstellen, stellt eine Regressionsaufgabe dar.
Neben Vorhersagemodellen ist man hier auch an einer Beschreibung der gegebenen Daten interessiert, um deren Eigenschaften besser verstehen zu können. Für Marketingzwecke ist etwa eine Segmentierung der Kunden in homogene Gruppen interessant. Das Finden solch homogenener Gruppen fällt unter den Begriff des Clustering. Bei der Subgruppenentdeckung geht es darum, in den Daten Gruppen (z.B. von Kunden oder Patienten) zu identifizieren, die sich gegenüber der Gesamtheit statistisch auffällig verhalten.
Schließlich stellt die Analyse von Zeitreihen und Sequenzen noch wichtige eigenständige Aufgaben dar.
Verfahren zur Wissensentdeckung
Für jede der oben genannten Analyseaufgaben gibt es eine Fülle bekannter Data Mining Verfahren. Bekannte Verfahren zur Klassifikation und Regression sind die Support Vector Machine [4] und Entscheidungsbaumlerner, z.B. C4.5 [18]. Ein einfaches, statistisches Verfahren zur Klassifikation ist Naive Bayes [15]. Eine Vielzahl auf Prädikatenlogik basierender Lernverfahren werden unter dem Begriff Induktive Logische Programmierung subsumiert. Häfig in einem Datensatz gemeinsam auftretende Attributwerte (z.B. Warenkorbanalyse) können mit Hilfe von Verfahren wie APRIORI [1, 10] gefunden werden. Varianten dieses Verfahrens dienen auch dem Erkennen häufig auftretender sequentieller Muster [2]. Eine gute Übersicht über klassische Lernverfahren bietet [15].
Vorverarbeitung der Daten ist eine wesentliche Voraussetzung des erfolgreichen Einsatzes von Data Mining Algorithmen. Unter Merkmalsextraktion und -generierung fällt die Gewinnung von zunächst nur implizit in den Daten enthaltenen Informationen. Merkmalsauswahl bezeichnet die manuelle oder automatische Entfernung von für den Data Mining Schritt irrelevanten Merkmalen. [14] gibt eine Übersicht über bekannte Verfahren.
Werkzeuge für die Wissensentdeckung
Es sind inzwischen einige Werkzeuge zur Unterstützung der Wissensentdeckung verüfgbar. Für den data mining Schritt gibt es die Sammlung von in JAVA implementierten Verfahren weka [21]. Für die Vorverarbeitung gibt es das System MiningMart, das unterschiedliche Verfahren integriert und direkt auf Datenbanken (z.B. Oracle) zugreifen kann [16]. Ein weiteres Werkzeug zur prädikatenlogischen Subgruppenentdeckung, das Merkmalsgenerierung verwendet, ist RSD.
Fallstudien:
Als Beispiele für gelöste Aufgaben im Bereich der Wissenssentdeckung stehen die besten Lösungen der KDD cups vergangener Jahre zur Verfügung, siehe beispielsweise [9, 7, 13, 19, 17, 12, 11, 20, 6].
Darüber hinaus bietet der Lehrstuhl Informatik VIII eine öffentlich über das Internet zugreifbare Sammlung erfolgreich gelöster KDD Fälle an 1 , die im Rahmen des europäischen Projektes MiningMart erstellt wurden. Dabei handelt es sich um ein Fallbeispiel zur Verkaufsprognose und zwei weitere aus dem Bereich des Marketing von Telekommunikationsfirmen, die sich jedoch auf eine Vielzahl von Anwendungen übertragen lassen.
Ziele und Vorgehen der Projektgruppe: Ziel der Projektgruppe ist es, Verfahren zur Wissensentdeckung für den gesamten Prozess kennen- und anwenden zu lernen. Dazu werden im ersten Semester zunächst in einer Seminarphase die Verfahren und Aufgaben vorgestellt. Ein umfangreiches Literaturstudium wird dann durch praktische Übungen vertieft. Eine gute Vertrautheit mit SQL-Programmen zur Datentransformation gehört ebenso dazu wie theoretische Eigenschaften von Verfahren, die deren Anwendbarkeit bestimmen. Schließlich werden die bekannten KDD-Cup-Lösungen nachvollzogen. Das Ergebnis des ersten Semesters wird durch einen Bericht dokumentiert, der den Stand der Kunst darstellt.
Im zweiten Semester wird dann vermutlich der KDD-Cup 2004 publiziert und die PG wird versuchen, eine der Aufgaben erfolgreich zu lösen. Die Dokumentation der Lösung vervollständigt den PG-Abschlussbericht.
| [1] | R. Agrawal and R. Srikant. Fast algorithms for mining association rules in large data bases. In Proceedings of the 20th International Conference on Very Large Data Bases (VLDB `94), pages 478--499, Santiago, Chile, Sep. 1994. |
| [2] | Rakesh Agrawal and Ramakrishnan Srikant. Mining sequential patterns. In International Conference on Data Engineering, pages 3--14, Taipei, Taiwan, mar 1995. IEEE Computer Society,. |
| [3] | Ronald J. Brachman and Tej Anand. The process of knowledge discovery in databases: A human-centered approach. In Usama M. Fayyad, Gregory Piatetsky-Shapiro, Padhraic Smyth, and Ramasamy Uthurusamy, editors, Advances in Knowledge Discovery and Data Mining, AAAI Press Series in Computer Science. A Bradford Book, The MIT Press, Cambridge Massachusetts, London England, 1996. |
| [4] | C. Burges. A tutorial on support vector machines for pattern recognition. Data Mining and Knowledge Discovery, 2(2):121--167, 1998. |
| [5] | Pete Chapman, Julian Clinton, Randy Kerber, Thomas Khabaza, Thomas Reinartz, Colin Shearer, and Rüdiger Wirth. Crisp - dm 1.0. Technical report, The CRISP-DM Consortium, August 2000. |
| [6] | Jie Cheng, Christos Hatzis, Hisashi Hayashi, Mark-A. Krogel, Shinichi Morishita, David Page, and Jun Sese. Kdd cup 2001 report. ACM SIGKDD Explorations Newsletter, 3(2):47--64, 2002. |
| [7] | Charles Elkan. Kdd'99 knowledge discovery contest. ACM SIGKDD Explorations Newsletter, 1(2):78, 2000. |
| [8] | Usama M. Fayyad, Gregory Piatetsky-Shapiro, Padhraic Smyth, and Ramasamy Uthurusamy, editors. Advances in Knowledge Discovery and Data Mining. AAAI Press Series in Computer Science. A Bradford Book, The MIT Press, Cambridge Massachusetts, London England, 1996. |
| [9] | Jim Georges and Anne H. Milley. Kdd'99 competition: Knowledge discovery contest. ACM SIGKDD Explorations Newsletter, 1(2):79{84, 2000. |
| [10] | Bart Goethals. Efficient Frequent Pattern Mining. PhD thesis, transnational University of Limburg, Diepenbeek, Belgium, December 2002. |
| [11] | Aron Inger, Nurit Vatnik, Saharon Rosset, and Einat Neumann. Kdd-cup 2000: question 1 winner's report. ACM SIGKDD Explorations Newsletter, 2(2):94, 2000. |
| [12] | Ron Kohavi, Carla Brodley, Brian Frasca, Llew Mason, and Zijian Zheng. KDD-Cup 2000 organizers' report: Peeling the onion. ACM SIGKDD Explorations Newsletter, 2(2):86--98, 2000. |
| [13] | Itzhak Levin. Kdd-99 classifier learning contest llsofts results overview. ACM SIGKDD Explorations Newsletter, 1(2):67{75, 2000. |
| [14] | H. Liu and H. Motoda. Feature Extraction, Construction, and Selection: A Data Mining Perspective. Kluwer, 1998. |
| [15] | Tom M. Mitchell. Machine Learning. McGraw Hill, New York, 1997. |
| [16] | Katharina Morik and Martin Scholz. The MiningMart Approach. In Workshop Management des Wandels der 32. GI Jahrestagung, 2002. |
| [17] | Bernhard Pfahringer. Winning the kdd99 classification cup: Bagged boosting. ACM SIGKDD Explorations Newsletter, 1(2):65--66, 2000. |
| [18] | John Ross Quinlan. C4.5: Programs for Machine Learning. Machine Learning. Morgan Kaufmann, San Mateo, CA, 1993. |
| [19] | Saharon Rosset and Aron Inger. Kdd-cup 99: Knowledge discovery in a charitable organization's donor database. ACM SIGKDD Explorations Newsletter, 1(2):85--90, 2000. |
| [20] | Dan Steinberg, N. Scott Cardell, and Mykhaylo Goloynya. Kdd-cup 2000: question 2 winner's report salford sytems. ACM SIGKDD Explorations Newsletter, 2(2):95, 2000. |
| [21] | Ian H. Witten and Eibe Frank. Data Mining - Praktische Werkzeuge und Techniken für das maschinelle Lernen. Hanser, 2000. |
Weitere Literatur:
[04.08.2003:]Ausgabe der Seminarthemen
Die Semesterferien sind PG-frei.
[13.10.2003:] Beginn der Vorlesungszeit (WS 2003/2004)
[14.10.2003-16.10.2003 (3 Tage):] Seminar