ELKI ( Environment for Developing KDD-Applications Supported by Index-Structures ) ist ein Software-Framework für Data Mining (Knowledge Discovery in Databases, KDD), das für Forschung und Lehre entwickelt wurde. Es entstand ursprünglich an der Forschungsgruppe Datenbanksysteme der LMU München unter der Leitung von Professor Hans-Peter Kriegel und wird nun an der Technischen Universität Dortmund fortgeführt . Ziel ist die Entwicklung und Evaluierung fortgeschrittener Data-Mining-Algorithmen sowie deren Interaktion mit Datenbankindexstrukturen .

Beschreibung

Das ELKI-Framework ist in Java geschrieben und basiert auf einer modularen Architektur. Die meisten der aktuell enthaltenen Algorithmen führen Clustering , Ausreißererkennung [ 1 ] und Datenbankindizes durch . Die objektorientierte Architektur ermöglicht die Kombination beliebiger Algorithmen, Datentypen, Distanzfunktionen , Indizes und Bewertungsmaße. Der Java- Just -in-Time-Compiler optimiert alle Kombinationen in ähnlichem Maße, wodurch Benchmark-Ergebnisse besser vergleichbar werden, wenn große Teile des Codes gemeinsam genutzt werden. Bei der Entwicklung neuer Algorithmen oder Indexstrukturen lassen sich die vorhandenen Komponenten problemlos wiederverwenden, und die Typsicherheit von Java erkennt viele Programmierfehler bereits zur Kompilierzeit.

ELKI ist ein kostenloses Tool zur Datenanalyse, das sich hauptsächlich auf das Auffinden von Mustern und ungewöhnlichen Datenpunkten ohne Beschriftungen konzentriert. Es ist in Java geschrieben und zielt darauf ab, schnell zu sein und mithilfe spezieller Strukturen große Datensätze verarbeiten zu können. Es wurde für Forscher und Studierende entwickelt, um eigene Methoden hinzuzufügen und verschiedene Algorithmen einfach zu vergleichen. [ 2 ]

ELKI wurde in der Datenwissenschaft zur Clusterung von Pottwal- Codas [ 3 ] , zur Phonem- Clusterung [ 4 ] , zur Anomalieerkennung bei Raumfahrtoperationen [ 5 ] , zur Umverteilung von Fahrradverleihsystemen [ 6 ] und zur Verkehrsprognose [ 7 ] eingesetzt.

Ziele

Das Universitätsprojekt wurde für Lehre und Forschung entwickelt . Der Quellcode ist auf Erweiterbarkeit und Wiederverwendbarkeit ausgelegt, aber auch leistungsoptimiert. Die experimentelle Evaluierung von Algorithmen hängt von vielen Umgebungsfaktoren ab, und Implementierungsdetails können die Laufzeit erheblich beeinflussen. [ 8 ] ELKI zielt darauf ab, eine gemeinsame Codebasis mit vergleichbaren Implementierungen vieler Algorithmen bereitzustellen.

Als Forschungsprojekt bietet es derzeit keine Integration mit Business-Intelligence -Anwendungen oder eine Schnittstelle zu gängigen Datenbankmanagementsystemen via SQL . Die Copyleft- Lizenz ( AGPL ) kann die Integration in kommerzielle Produkte ebenfalls erschweren; dennoch eignet sie sich zur Evaluierung von Algorithmen vor der Entwicklung einer eigenen Implementierung für ein kommerzielles Produkt. Darüber hinaus erfordert die Anwendung der Algorithmen Kenntnisse über deren Verwendung, Parameter und die Lektüre der Originalliteratur. Die Zielgruppe umfasst Studierende , Forschende , Data Scientists und Softwareentwickler .

Architektur

ELKI basiert auf einem datenbankinspirierten Kern, der ein vertikales Datenlayout verwendet und Daten in Spaltengruppen speichert (ähnlich den Spaltenfamilien in NoSQL-Datenbanken ). Dieser Datenbankkern bietet Funktionen für die Suche nach dem nächsten Nachbarn , die Bereichs-/Radiussuche und Distanzabfragen mit Indexbeschleunigung für eine Vielzahl von Unähnlichkeitsmaßen . Algorithmen, die auf solchen Abfragen basieren (z. B. der k-Nächste-Nachbarn-Algorithmus , der Local Outlier Factor und DBSCAN ), lassen sich einfach implementieren und profitieren von der Indexbeschleunigung. Der Datenbankkern bietet außerdem schnelle und speichereffiziente Sammlungen für Objektsammlungen und assoziative Strukturen wie Nächste-Nachbarn-Listen.

ELKI nutzt Java-Schnittstellen umfassend, um eine einfache Erweiterung an vielen Stellen zu ermöglichen. So lassen sich beispielsweise benutzerdefinierte Datentypen, Distanzfunktionen, Indexstrukturen, Algorithmen, Eingabeparser und Ausgabemodule hinzufügen und kombinieren, ohne den bestehenden Code zu verändern. Dies schließt die Möglichkeit ein, eine eigene Distanzfunktion zu definieren und vorhandene Indizes zur Beschleunigung zu nutzen.

ELKI verwendet eine Service-Loader -Architektur, um die Veröffentlichung von Erweiterungen als separate JAR-Dateien zu ermöglichen .

ELKI verwendet für eine bessere Performance optimierte Sammlungen anstelle der Standard-Java-API. [ 9 ] For-Schleifen werden beispielsweise ähnlich wie C++-Iteratoren geschrieben : 

for ( DBIDIter iter = ids.iter ( ); iter.valid (); iter.advance ( )) { relation.get ( iter ) ; // Beispiel : Das referenzierte Objekt abrufen idcollection.add ( iter ) ; // Beispiel : Die Referenz zu einer DBID- Collection hinzufügen }

Im Gegensatz zu typischen Java-Iteratoren (die nur Objekte durchlaufen können) spart dies Speicher, da der Iterator intern primitive Datentypen zur Datenspeicherung verwenden kann. Die reduzierte Speicherbereinigung verbessert die Laufzeit. Optimierte Sammlungsbibliotheken wie GNU Trove3 und Koloboke nutzen fastutilähnliche Optimierungen. ELKI verwendet solche Optimierungen auch für Datenstrukturen wie Objektsammlungen und Heaps (z. B. für die Nächste-Nachbarn-Suche ).

Visualisierung

Das Visualisierungsmodul verwendet SVG für skalierbare Grafiken und Apache Batik für die Darstellung der Benutzeroberfläche sowie den verlustfreien Export nach PostScript und PDF zur einfachen Einbindung in wissenschaftliche Publikationen in LaTeX . Exportierte Dateien können mit SVG-Editoren wie Inkscape bearbeitet werden . Dank der Verwendung von Cascading Style Sheets lässt sich das Grafikdesign problemlos anpassen. Leider ist Batik relativ langsam und speicherintensiv, weshalb die Visualisierungen für große Datensätze nur bedingt skalierbar sind (bei größeren Datensätzen wird standardmäßig nur eine Teilmenge visualisiert).

Auszeichnungen

Version 0.4, die auf dem „Symposium on Spatial and Temporal Databases“ 2011 vorgestellt wurde und verschiedene Methoden zur Erkennung räumlicher Ausreißer enthielt, [ 10 ] gewann den „Best Demonstration Paper Award“ der Konferenz.

Eingeschlossene Algorithmen

Ausgewählte Algorithmen: [ 11 ]

Versionsverlauf

Version 0.1 (Juli 2008) enthielt mehrere Algorithmen zur Clusteranalyse und Anomalieerkennung sowie einige Indexstrukturen wie den R*-Baum . Der Schwerpunkt der ersten Version lag auf Subspace-Clustering- und Korrelationsclustering -Algorithmen. [ 12 ]

Version 0.2 (Juli 2009) fügte Funktionen für die Zeitreihenanalyse hinzu , insbesondere Distanzfunktionen für Zeitreihen. [ 13 ]

Version 0.3 (März 2010) erweiterte die Auswahl an Anomalieerkennungsalgorithmen und Visualisierungsmodulen. [ 14 ]

Version 0.4 (September 2011) fügte Algorithmen für Geodaten-Mining und Unterstützung für multirelationale Datenbank- und Indexstrukturen hinzu. [ 10 ]

Version 0.5 (April 2012) konzentriert sich auf die Auswertung von Clusteranalyseergebnissen und fügt neue Visualisierungen sowie einige neue Algorithmen hinzu. [ 15 ]

Version 0.6 (Juni 2013) führt neben den üblichen Ergänzungen von Algorithmen und Indexstrukturen eine neue 3D-Adaption paralleler Koordinaten zur Datenvisualisierung ein. [ 16 ]

Version 0.7 (August 2015) bietet Unterstützung für unsichere Datentypen sowie Algorithmen zur Analyse unsicherer Daten. [ 17 ]

Version 0.7.5 (Februar 2019) fügt zusätzliche Clustering-Algorithmen, Anomalieerkennungsalgorithmen, Bewertungsmaße und Indexierungsstrukturen hinzu. [ 18 ]

Version 0.8 (Oktober 2022) bietet die automatische Indexerstellung, Speicherbereinigung und inkrementelle Prioritätssuche sowie viele weitere Algorithmen wie BIRCH . [ 19 ]

Ähnliche Anwendungen

Siehe auch

Referenzen

  1. ^ Hans-Peter Kriegel , Peer Kröger, Arthur Zimek (2009). „Outlier Detection Techniques (Tutorial)“ (PDF) . 13. Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD 2009) . Bangkok, Thailand . Abgerufen am 26.03.2010 .{{cite journal}}: CS1 Wartung: Mehrere Namen: Autorenliste ( Link )
  2. ^ „ELKI Data Mining Framework“ . elki-project.github.io . Abgerufen am 30.05.2024 .
  3. ^ Gero, Shane; Whitehead, Hal; Rendell, Luke (2016). „Individuelle, gruppen- und clanbezogene Identitätsmerkmale in den Coda-Rufen von Pottwalen“ . Royal Society Open Science . 3 (1) 150372. Bibcode : 2016RSOS....350372G . doi : 10.1098/rsos.150372 . ISSN 2054-5703 . PMC 4736920. PMID 26909165 .   
  4. Stahlberg, Felix; Schlippe, Tim; Vogel, Stephan; Schultz, Tanja (2013). „Ausspracheextraktion aus Phonemsequenzen durch sprachübergreifende Wort-Phonem-Zuordnung“. Statistical Language and Speech Processing . Lecture Notes in Computer Science. Band 7978. S.  260–272 . doi : 10.1007/978-3-642-39593-2_23 . ISBN 978-3-642-39592-5ISSN  0302-9743 .​
  5. ^ Verzola, Ivano; Donati, Alessandro ; Martinez, Jose; Schubert, Matthias; Somodi, Laszlo (2016). „Projekt Sibyl: Ein System zur Erkennung von Neuheiten für bemannte Raumfahrtoperationen“. Konferenz Space Ops 2016. doi : 10.2514/6.2016-2405 . ISBN 978-1-62410-426-8Die
  6. ^ Adham, Manal T.; Bentley, Peter J. (2016). „Evaluierung von Clustering-Methoden im Rahmen des Artificial Ecosystem Algorithm und deren Anwendung auf die Fahrradverteilung in London“. Biosystems . 146 : 43–59 . Bibcode : 2016BiSys.146...43A . doi : 10.1016/j.biosystems.2016.04.008 . ISSN 0303-2647 . PMID 27178785 .  
  7. ^ Wisely, Michael; Hurson, Ali; Sarvestani, Sahra Sedigh (2015). „Ein erweiterbares Simulationsframework zur Evaluierung zentralisierter Verkehrsprognosealgorithmen“. 2015 International Conference on Connected Vehicles and Expo (ICCVE) . S.  391–396 . doi : 10.1109/ICCVE.2015.86 . ISBN 978-1-5090-0264-1. S2CID  1297145 .
  8. Kriegel, Hans-Peter ; Schubert, Erich; Zimek, Arthur (2016). „ Die (schwarze) Kunst der Laufzeitbewertung: Vergleichen wir Algorithmen oder Implementierungen?“ Knowledge and Information Systems . 52 (2): 341–378 . doi : 10.1007/s10115-016-1004-2 . ISSN 0219-1377 . S2CID 40772241 .  
  9. ^ „DBIDs“ . ELKI-Homepage . Abgerufen am 13. Dezember 2016 .
  10. ^ a b Elke Achtert, Achmed Hettab, Hans-Peter Kriegel , Erich Schubert, Arthur Zimek (2011). Räumliche Ausreißererkennung: Daten, Algorithmen, Visualisierungen . 12. Internationales Symposium über räumliche und zeitliche Datenbanken (SSTD 2011). Minneapolis, MN: Springer. doi : 10.1007/978-3-642-22922-0_41 .{{cite conference}}: CS1 Wartung: Mehrere Namen: Autorenliste ( Link )
  11. ^ Auszug aus „Data Mining Algorithms in ELKI“ . Abgerufen am 17. Oktober 2019 .
  12. ^ Elke Achtert, Hans-Peter Kriegel , Arthur Zimek (2008). ELKI: Ein Softwaresystem zur Evaluierung von Subspace-Clustering-Algorithmen (PDF) . Proceedings der 20. internationalen Konferenz über wissenschaftliches und statistisches Datenbankmanagement (SSDBM 08). Hongkong, China: Springer. doi : 10.1007/978-3-540-69497-7_41 .{{cite conference}}: CS1 Wartung: Mehrere Namen: Autorenliste ( Link )
  13. ^ Elke Achtert, Thomas Bernecker, Hans-Peter Kriegel , Erich Schubert, Arthur Zimek (2009). ELKI in time: ELKI 0.2 for the performance evaluation of distance measures for time series (PDF) . Proceedings of the 11th International Symposium on Advances in Spatial and Temporal Databases (SSTD 2010). Aalborg, Dänemark: Springer. doi : 10.1007/978-3-642-02982-0_35 .{{cite conference}}: CS1 Wartung: Mehrere Namen: Autorenliste ( Link )
  14. ^ Elke Achtert, Hans-Peter Kriegel , Lisa Reichert, Erich Schubert, Remigius Wojdanowski, Arthur Zimek (2010). Visuelle Evaluierung von Ausreißererkennungsmodellen . 15. Internationale Konferenz über Datenbanksysteme für fortgeschrittene Anwendungen (DASFAA 2010). Tsukuba, Japan: Springer. doi : 10.1007/978-3-642-12098-5_34 .{{cite conference}}: CS1 Wartung: Mehrere Namen: Autorenliste ( Link )
  15. ^ Elke Achtert, Sascha Goldhofer, Hans-Peter Kriegel , Erich Schubert, Arthur Zimek (2012). Evaluation of Clusterings Metrics and Visual Support . 28. Internationale Konferenz für Daten-Engineering (ICDE). Washington, DC. doi : 10.1109/ICDE.2012.128 .{{cite conference}}: CS1 Wartung: Mehrere Namen: Autorenliste ( Link )
  16. ^ Elke Achtert, Hans-Peter Kriegel , Erich Schubert, Arthur Zimek (2013). Interaktives Data Mining mit 3D-Parallelkoordinatenbäumen . Proceedings der ACM International Conference on Management of Data ( SIGMOD ). New York City, NY. doi : 10.1145/2463676.2463696 .{{cite conference}}: CS1 Wartung: Mehrere Namen: Autorenliste ( Link )
  17. ^ Erich Schubert; Alexander Koos; Tobias Emrich; Andreas Züfle; Klaus Arthur Schmid; Arthur Zimek (2015). „Ein Rahmenwerk für das Clustering unsicherer Daten“ (PDF) . Proceedings of the VLDB Endowment . 8 (12): 1976–1987 . doi : 10.14778/2824032.2824115 .
  18. ^ Schubert, Erich; Zimek, Arthur (10.02.2019). „ELKI: Eine große Open-Source-Bibliothek für Datenanalyse – ELKI Version 0.7.5 „Heidelberg“". arXiv : 1902.03616 [ cs.LG ].
  19. ^ Schubert, Erich (2022). Automatische Indexierung für die Ähnlichkeitssuche in ELKI . Similarity Search and Applications. S.  205–213 . doi : 10.1007/978-3-031-17849-8_16 .