K-Spectral Centroïd : efficient implementation

Autor: Conan-Guez, Brieuc, Gély, Alain, Boudjeloud-Assala, Lydia, Blansché, Alexandre
Přispěvatelé: Laboratoire d'Informatique Théorique et Appliquée (LITA), Université de Lorraine (UL), CONAN-GUEZ, Brieuc
Jazyk: francouzština
Rok vydání: 2017
Předmět:
Zdroj: Actes Conférence EGC 2017
17ième Conférence d'Extraction et de Gestion des Connaissances (EGC 2017)
17ième Conférence d'Extraction et de Gestion des Connaissances (EGC 2017), Jan 2017, Grenoble, France
Popis: We introduce a K-Spectral Centroïd algorithm, a variant of K-Means to cluster large time series.K-Spectral Centroïd uses a dissimilarity between time series, which is invariant regarding translation and scaling.This algorithm is relatively expensive in computation time.Indeed, during the assignment phase, it requires testing all possible translations to identify the best solution.During the representation phase, the calculation of the new barycenter requires the extraction of the smallest eigenvalue of a matrix. We propose in this work to improve these two points.We measure subsequently the impact of these improvements on various experiments.
Nous nous intéressons à la classification non supervisée de séries chronologiques. Pour ce faire, nous utilisons l'algorithme K-Spectral Centroïd (K-SC), une variante des K-Means. K-Spectral Centroïd utilise une mesure de dissimilarité entre séries chronologiques, invariante par translation et par changement d'échelle. Cet algorithme est coûteux en temps de calcul : lors de la phase d'affectation, il nécessite de tester toutes les translations possibles pour identifier la meilleure ; lors de la phase de représentation, le calcul du nouveau barycentre nécessite l'extraction de la plus petite valeur propre d'une matrice. Nous proposons dans ce travail trois optimisations de K-SC. L'identification de la meilleure translation peut être réalisée efficacement en utilisant la transformée de Fourier discrète. Chaque matrice peut être calculée incrémentalement. Le calcul du nouveau barycentre peut s'effectuer à moindre coût grâce à la méthode de la puissance itérée. Ces trois optimisations fournissent exactement la même classification que K-SC.
Databáze: OpenAIRE
Externí odkaz: