Environment for DeveLoping KDD-Applications Supported by Index-Structures

Environment for DeveLoping KDD-Applications Supported by Index-Structures
ELKI 0.4 visualisiert OPTICS-Ergebnis
Basisdaten
Maintainer	Ludwig-Maximilians-Universität München, Institut für Informatik, LFE Datenbanksysteme
Aktuelle Version	0.4.0 (20. September, 2011)
Betriebssystem	Plattformunabhängig
Programmier­sprache	Java
Kategorie	Data-Mining, Forschung, Mathematik, Statistik
Lizenz	AGPL (ab Version 0.4.0)
http://elki.dbs.ifi.lmu.de/

Environment for DeveLoping KDD-Applications Supported by Index-Structures (ELKI), auf Deutsch etwa „Umgebung zur Entwicklung von Wissensentdeckung-Anwendungen mit Indexstruktur-Unterstützung“, ist ein Forschungsprojekt des Datenbanken-Lehrstuhls von Professor Hans-Peter Kriegel an der Ludwig-Maximilians-Universität München.

Es handelt sich um ein in Java geschriebenes, modulares Softwarepaket („Framework“) zur Knowledge Discovery in Databases. Der Fokus liegt auf Verfahren zur Clusteranalyse, Ausreißer-Erkennung^[1] sowie der Verwendung von Indexstrukturen in solchen Verfahren. Als Forschungsprojekt einer Universität liegt der Fokus auf einer einfachen Erweiterbarkeit, Lesbarkeit und in der Verwendung in Forschung und Lehre an der Universität, nicht in maximaler Geschwindigkeit oder in der Integration mit bestehenden Business-Intelligence-Anwendungen. So verfügt bisher beispielsweise keine der freigegebenen Versionen über eine Datenbankschnittstelle zu bestehenden industriellen Datenbank-Systemen, und eine Verwendung der Software setzt Vorwissen und ein Lesen der Dokumentation voraus. Die Zielgruppe für das Projekt sind Forscher, Studenten und Software-Entwickler.

Die modulare Architektur der Software erlaubt zahlreiche Kombinationen der enthaltenen Algorithmen, Datentypen, Distanzmaßen und Indexstrukturen. Bei der Entwicklung neuer Verfahren oder Distanzen kann daher das neue Modul einfach mit den bestehenden Modulen kombiniert und evaluiert werden. Die Visualisierungs-Module erlauben es dabei oft, die Ergebnisse einfach darzustellen und so zu vergleichen. Der Entwicklungsaufwand und die Entwicklungszeit solcher Module wird durch die Wiederverwendung bestehenden Programmcodes erheblich vereinfacht, so dass die Software gut als Basis für Seminar-, Diplom- und Master-Arbeiten verwendet werden kann.

Lizenz

Auf der Webseite wird keine Lizenz für die Software angegeben. Eine Verwendung ist daher nur nach expliziter Lizenzierung bei den Autoren möglich. Da es sich um ein universitäres Projekt handelt, ist eine Verwendung und Weiterentwicklung in der Forschung (insbesondere auch in Seminar-, Diplom- und Masterarbeiten) nicht an monetäre Forderungen gekoppelt; in jedem Falle sollte man die Autoren jedoch kontaktieren und geeignet zitieren. Die Webseite enthält auch den Quelltext, was zum Studium und der Erweiterung der enthaltenen Algorithmen einlädt.

Enthaltene Algorithmen

In ELKI enthalten sind unter anderem folgende Algorithmen^[2][3] (Auszug):

• K-Means Clustering
• EM-Algorithmus - Expectation-Maximization-Algorithmus
• Apriori-Algorithmus
• Single-linkage clustering
• DBSCAN (Density-Based Spatial Clustering of Applications with Noise)
• OPTICS (Ordering Points To Identify the Clustering Structure), inklusive der Weiterentwicklungen OPTICS-OF, DeLiClu, HiSC, HiCO und DiSH
• Local Outlier Factor (LOF)
• R-Baum, R*-Baum und M-Baum

Versionsgeschichte

Version 0.1 (Juli 2008) enthielt bereits zahlreiche Algorithmen aus den Bereichen Clusteranalyse und Ausreißer-Erkennung, sowie einige Indexstrukturen wie den R*-Baum. Der Fokus des ersten Releases war auf Subspace-Clustering-Verfahren. ^[4]

Version 0.2 (Juli 2009) fügte Funktionen zur Zeitreihenanalyse hinzu, insbesondere Distanzfunktionen hierfür. ^[5]

Version 0.3 (März 2010) erweiterte die Auswahl an Outlier-Detection-Algorithmen und Visualisierungsmodulen. ^[6]

Version 0.4 (August 2011) fügt zahlreiche Verfahren zum Erkennen von räumlichen Ausreißern in Geodaten hinzu. ^[7]

Auszeichnungen

ELKI begann als Implementation^[8] der Doktorarbeit von Dr. Arthur Zimek,^[9] die den "SIGKDD Doctoral Dissertation Award 2009 Runner-up"^[10] der Association for Computing Machinery für ihre Beiträge zum "Correlation Clustering" gewann. Die im Zuge der Dissertation publizierten Algorithmen (4C, COPAC, HiCO, ERiC, CASH) zusammen mit ein paar Vorläufern und Vergleichsverfahren sind in ELKI verfügbar.^[8]

Die Demonstration der Version 0.4 auf der Konferenz "Symposium on Spatial and Temporal Databases 2011" mit den Geo-Outlier-Erweiterungen für ELKI^[7] gewann den "Best Demonstration Paper Award" der Konferenz.

Verwandte Anwendungen

• WEKA Ein ähnliches Projekt der Universität Waikato, mit einem Schwerpunkt auf Klassifizierungs-Algorithmen.
• RapidMiner eine frei und kommerziell verfügbare Anwendung mit dem Schwerpunkt maschinelles Lernen.
• KNIME (Konstanz Information Miner) Projekt der Universität Konstanz zur interaktiven Datenanalyse in Eclipse.

Weblinks

Offizielle Webseite von ELKI

Einzelnachweise

1. ↑ Hans-Peter Kriegel, Peer Kröger, Arthur Zimek: Outlier Detection Techniques. Tutorial. In: 13th Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD 2009). Bangkok, Thailand 2009 (http://www.dbs.ifi.lmu.de/Publikationen/Papers/tutorial_slides.pdf (PDF-Datei; 1 MB), abgerufen am 26. März 2010).
2. ↑ Literatur-Referenzen zu Algorithmen in ELKI. Abgerufen am 17. August 2011. 
3. ↑ ELKI Wiki: Liste der enthaltenen Data-Mining-Algorithmen. Abgerufen am 17. August 2011. 
4. ↑ Elke Achtert, Hans-Peter Kriegel, Arthur Zimek: ELKI: A Software System for Evaluation of Subspace Clustering Algorithms. In: Proceedings of the 20th international conference on Scientific and Statistical Database Management (SSDBM 08). Springer-Verlag, Hong Kong, China 2008, doi:10.1007/978-3-540-69497-7_41 (http://www.dbs.ifi.lmu.de/~zimek/publications/SSDBM2008/elkipaper.pdf (PDF-Datei; 80 kB)).
5. ↑ Elke Achtert, Thomas Bernecker, Hans-Peter Kriegel, Erich Schubert, Arthur Zimek: ELKI in time: ELKI 0.2 for the performance evaluation of distance measures for time series. In: Proceedings of the 11th International Symposium on Advances in Spatial and Temporal Databases (SSTD 2010). Springer-Verlag, Aalborg, Dänemark 2009, doi:10.1007/978-3-642-02982-0_35 (http://www.dbs.ifi.lmu.de/~zimek/publications/SSTD2009/sstd09-elki-paper.pdf (PDF-Datei; 230 kB)).
6. ↑ Elke Achtert, Hans-Peter Kriegel, Lisa Reichert, Erich Schubert, Remigius Wojdanowski, Arthur Zimek: Visual Evaluation of Outlier Detection Models. In: 15th International Conference on Database Systems for Advanced Applications (DASFAA 2010). Springer-Verlag, Tsukuba, Japan 2010, doi:10.1007/978-3-642-12098-5_34.
7. ↑ ^{a b} Elke Achtert, Achmed Hettab, Hans-Peter Kriegel, Erich Schubert, Arthur Zimek: Spatial Outlier Detection: Data, Algorithms, Visualizations. In: 12th International Symposium on Spatial and Temporal Databases (SSTD 2011). Minneapolis, MN, USA 2011, doi:10.1007/978-3-642-22922-0_41.
8. ↑ ^{a b} Arthur Zimek: Correlation clustering. In: ACM SIGKDD (Hrsg.): ACM SIGKDD Explorations Newsletter. 11, Nr. 1, 2009, S. 53–54, doi:10.1145/1656274.1656286.
9. ↑ Arthur Zimek: Correlation Clustering. Doktorarbeit. Ludwig-Maximilians-Universität München, München, Deutschland 2008 (urn:nbn:de:bvb:19-87361, http://edoc.ub.uni-muenchen.de/8736/1/Zimek_Arthur.pdf).
10. ↑ SIGKDD Doctoral Dissertation Award. ACM SIGKDD, abgerufen am 16. April 2011 (html, englisch).