# ELKI

ELKI (Environment for Developing KDD-Applications Supported by Index-Structures) és un marc de programari de mineria de dades (KDD, descobriment de coneixement en bases de dades) desenvolupat per al seu ús en recerca i ensenyament. Originalment estava a la unitat de recerca de sistemes de bases de dades del professor Hans-Peter Kriegel a la Universitat Ludwig Maximilian de Munic, Alemanya, i ara continua a la Universitat Tècnica de Dortmund, Alemanya. Pretén permetre el desenvolupament i l'avaluació d'algoritmes avançats de mineria de dades i la seva interacció amb estructures d'índex de bases de dades.

## Descripció

El marc ELKI està escrit en Java i construït al voltant d'una arquitectura modular. La majoria dels algorismes inclosos actualment pertanyen a l'agrupació, la detecció de valors atípics, i els índexs de bases de dades. L'arquitectura orientada a objectes permet la combinació d'algorismes arbitraris, tipus de dades, funcions de distància, índexs i mesures d'avaluació. El compilador just-in-time de Java optimitza totes les combinacions en una mesura similar, fent que els resultats de l'anàlisi comparativa siguin més comparables si comparteixen grans parts del codi. Quan es desenvolupen nous algorismes o estructures d'índex, els components existents es poden reutilitzar fàcilment, i el tipus de seguretat de Java detecta molts errors de programació en temps de compilació.
ELKI s'ha utilitzat en ciències de dades, per exemple, per agrupar codis de catxalot, agrupació de fonemes, per a la detecció d'anomalies en operacions de vols espacials, per a la redistribució de bicicletes compartides, i predicció del trànsit.

## Objectius

El projecte universitari està desenvolupat per utilitzar-lo en la docència i la recerca . El codi font està escrit tenint en compte l'extensibilitat i la reutilització, però també està optimitzat per al rendiment. L'avaluació experimental dels algorismes depèn de molts factors ambientals i els detalls de la implementació poden tenir un gran impacte en el temps d'execució. ELKI té com a objectiu proporcionar una base de codi compartida amb implementacions comparables de molts algorismes.

## Arquitectura

ELKI es modela al voltant d'un nucli inspirat en bases de dades, que utilitza un disseny de dades vertical que emmagatzema dades en grups de columnes (similar a les famílies de columnes a les bases de dades NoSQL). Aquest nucli de la base de dades proporciona la cerca de veí més proper, la cerca per rang/radi i la consulta de distància amb acceleració d'índex per a una àmplia gamma de mesures de dissimilaritat. Els algorismes basats en aquestes consultes (per exemple, l'algoritme k-nearest-neighbor, el factor atípic local i DBSCAN) es poden implementar fàcilment i beneficiar-se de l'acceleració de l'índex. El nucli de la base de dades també proporciona col·leccions ràpides i eficients de memòria per a col·leccions d'objectes i estructures associatives com ara llistes de veïns més propers.

## Visualització

El mòdul de visualització utilitza SVG per a la sortida de gràfics escalables i Apache Batik per a la representació de la interfície d'usuari, així com l'exportació sense pèrdues a PostScript i PDF per incloure'ls fàcilment en publicacions científiques a LaTeX. Els fitxers exportats es poden editar amb editors SVG com ara Inkscape. Com que s'utilitzen fulls d'estil en cascada, el disseny gràfic es pot redissenyar fàcilment. Malauradament, el Batik és bastant lent i requereix molta memòria, de manera que les visualitzacions no són molt escalables per a grans conjunts de dades (per a conjunts de dades més grans, només es visualitza una submostra de les dades per defecte).

## Algorismes inclosos

* Anàlisi de clústers:
** Agrupació de K-means (inclosos algorismes ràpids com ara Elkan, Hamerly, Annulus i Exponion k-Means, i variants robustes com k-means--)
** Agrupació de K-medianes
** Agrupació de K-medoids (PAM) (incloent FastPAM i aproximacions com CLARA, CLARANS)
** Algorisme de maximització d'expectatives per al modelatge de mescles gaussianes
** Clúster jeràrquic (inclosos els algorismes ràpids SLINK, CLINK, NNChain i Anderberg)
** Clúster d'enllaç únic
** Agrupació de líders
** DBSCAN (agrupació espacial d'aplicacions amb soroll basada en densitat, amb acceleració d'índex total per a funcions de distància arbitràries)
** OPTICS (Punts de comanda per identificar l'estructura de clúster), incloses les extensions OPTICS-OF, DeLi-Clu, HiSC, HiCO i DiSH
** HDBSCAN
** Agrupació de canvi mitjà
** Agrupació de bedolls
** SUBCLU (agrupació subespai connectada a densitat per a dades d'alta dimensionalitat)
** Agrupació CLIQUE
** Clúster ORCLUS i PROCLUS
** Clúster COPAC, ERiC i 4C
** Clúster CASH
** Agrupació subespai DOC i FastDOC
** Clúster P3C
** Algorisme d'agrupació de canopy
* Detecció d'anomalies:
** k-Detecció de valors atípics del veí més proper
** LOF (Factor atípic local)
** LoOP (probabilitats atípiques locals)
** ÒPTICA -DE
** DB-Outlier (outliers basats en la distància)
** LOCI (integral de correlació local)
** LDOF (Factor atípic basat en la distància local)
** EM -Outlier
** SOD (Grau atípic del subespai)
** COP (Correlation Outlier Probabilities)
* Conjunt d'elements freqüents Aprenentatge de regles d'associació i mineria
** Algorisme a priori
** Eclat
** FP-creixement
* Reducció de la dimensionalitat
** Anàlisi de components principals
** Escalat multidimensional
** Incrustació de veïnes estocàstiques distribuïdes en T (t-SNE)
* Estructures d'índex espacial i altres índexs de cerca:
** R-arbre
** R*-arbre
** M-arbre
** kd arbre
** X-arbre
** Arbre cobert
** iDistance
** NN baixada
** Hashing sensible a la localitat (LSH)
* Avaluació:
** Precisió i record, puntuació F1, precisió mitjana
** Característica de funcionament del receptor (corba ROC)
** Guany acumulat descomptat (inclòs NDCG)
** Índex de siluetes
** Índex de Davies-Bouldin
** índex de Dunn
** Validació de clúster basada en la densitat (DBCV)
* Visualització
** Gràfiques de dispersió
** Histogrames
** Coordenades paral·leles (també en 3D, utilitzant OpenGL)
* Altres:
** Distribucions estadístiques i molts estimadors de paràmetres, inclosos estimadors robusts basats en MAD i L-moments
** Deformació temporal dinàmica
** Detecció de punts de canvi en sèries temporals
** Estimadors de dimensionalitat intrínseca

## Referències

* ↑ Hans-Peter Kriegel, Peer Kröger, Arthur Zimek 13th Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD 2009) [Bangkok, Thailand], 2009 [Consulta: 26 març 2010].
* ↑ Gero, Shane; Whitehead, Hal; Rendell, Luke Royal Society Open Science, 3, 1, 2016, pàg. 150372. Bibcode: 2016RSOS....350372G. DOI: 10.1098/rsos.150372. ISSN: 2054-5703. PMC: 4736920. PMID: 26909165.
* ↑ Stahlberg, Felix. «Pronunciation Extraction from Phoneme Sequences through Cross-Lingual Word-to-Phoneme Alignment». A: Statistical Language and Speech Processing (en anglès). 7978, 2013, p. 260–272 (Lecture Notes in Computer Science). DOI 10.1007/978-3-642-39593-2_23. ISBN 978-3-642-39592-5.
* ↑ Verzola, Ivano. «Project Sibyl: A Novelty Detection System for Human Spaceflight Operations». A: Space Ops 2016 Conference (en anglès), 2016. DOI 10.2514/6.2016-2405. ISBN 978-1-62410-426-8.
* ↑ Adham, Manal T.; Bentley, Peter J. Biosystems, 146, 2016, pàg. 43–59. DOI: 10.1016/j.biosystems.2016.04.008. ISSN: 0303-2647. PMID: 27178785.
* ↑ Wisely, Michael. «An extensible simulation framework for evaluating centralized traffic prediction algorithms». A: 2015 International Conference on Connected Vehicles and Expo (ICCVE) (en anglès), 2015, p. 391–396. DOI 10.1109/ICCVE.2015.86. ISBN 978-1-5090-0264-1.
* ↑ Kriegel, Hans-Peter; Schubert, Erich; Zimek, Arthur Knowledge and Information Systems, 52, 2, 2016, pàg. 341–378. DOI: 10.1007/s10115-016-1004-2. ISSN: 0219-1377.