Die Klassifizierung von Zeitreihen ist eine der häufigsten Aufgaben, bei denen maschinelle und Deep-Learning-Modelle angewendet werden. In diesem Artikel werden 8 Arten von Zeitreihenklassifizierungsmethoden behandelt. Dies reicht von einfachen distanz- oder margenbasierten Methoden bis hin zu Methoden, die tiefe neuronale Netze nutzen. Dieser Artikel soll als Referenzartikel für alle Zeitreihenklassifizierungsalgorithmen dienen.
Bevor wir verschiedene Arten von Zeitreihenklassifizierungsmethoden (TS) behandeln, vereinheitlichen wir zunächst das Konzept der Zeitreihen. TS kann als univariate oder multivariate TS klassifiziert werden.
Ein Datensatz einzelner oder multivariater TS enthält normalerweise einen geordneten Satz einzelner oder multivariater TS. Darüber hinaus enthalten Datensätze normalerweise einen durch eine einzelne Kodierung repräsentierten Label-Vektor, dessen Länge die Labels verschiedener Klassen repräsentiert.
Das Ziel der TS-Klassifizierung wird durch das Training eines beliebigen Klassifizierungsmodells anhand eines bestimmten Datensatzes definiert, damit das Modell die Wahrscheinlichkeitsverteilung des bereitgestellten Datensatzes lernen kann. Das heißt, das Modell sollte lernen, Klassenbezeichnungen korrekt zuzuweisen, wenn ein TS gegeben wird.
Entfernungs- oder nächster Nachbar-basierte TS-Klassifizierungsmethoden verwenden verschiedene entfernungsbasierte Metriken, um die gegebenen Daten zu klassifizieren. Es handelt sich um eine überwachte Lerntechnik, bei der das Vorhersageergebnis eines neuen TS von den Labelinformationen der bekannten Zeitreihe abhängt, der es am ähnlichsten ist.
Eine Distanzmetrik ist eine Funktion, die den Abstand zwischen zwei oder mehr Zeitreihen beschreibt und maßgebend ist. Typische Entfernungsmaße sind:
Nach der Entscheidung über die Metrik wird normalerweise der KNN-Algorithmus (k-Nearest Neighbor) verwendet angewendet, wobei der Algorithmus den Abstand zwischen dem neuen TS und allen TSs im Trainingsdatensatz misst. Nachdem Sie alle Entfernungen berechnet haben, wählen Sie die k nächstgelegenen aus. Abschließend wird der neue TS der Klasse zugeordnet, zu der die Mehrheit der k nächsten Nachbarn gehören.
Während die beliebtesten Normen definitiv p-Normen sind, insbesondere die euklidische Distanz, haben sie zwei Hauptnachteile, die sie für TS-Klassifizierungsaufgaben weniger geeignet machen. Da die Norm nur für zwei TS gleicher Länge definiert ist, ist es in der Praxis nicht immer möglich, Folgen gleicher Länge zu erhalten. Die Norm vergleicht nur zwei TS-Werte zu jedem Zeitpunkt unabhängig voneinander, die meisten TS-Werte sind jedoch miteinander korreliert.
Und DTW kann die beiden Einschränkungen der p-Norm lösen. Das klassische DTW minimiert den Abstand zwischen zwei Zeitreihenpunkten, deren Zeitstempel unterschiedlich sein können. Dies bedeutet, dass leicht verschobene oder verzerrte TS immer noch als ähnlich angesehen werden. Die folgende Abbildung veranschaulicht den Unterschied zwischen p-normbasierten Metriken und der Funktionsweise von DTW.
In Kombination mit KNN wird DTW als Basisalgorithmus für verschiedene Benchmark-Bewertungen der TS-Klassifizierung verwendet.
KNN kann auch mithilfe einer Entscheidungsbaummethode implementiert werden. Der Nachbarwaldalgorithmus modelliert beispielsweise einen Wald aus Entscheidungsbäumen, der Distanzmaße zur Partitionierung von TS-Daten verwendet.
Intervallbasierte Methoden teilen den TS normalerweise in mehrere verschiedene Intervalle auf. Jede Teilsequenz wird dann verwendet, um einen separaten Klassifikator für maschinelles Lernen (ML) zu trainieren. Es wird eine Reihe von Klassifikatoren generiert, wobei jeder Klassifikator auf sein eigenes Intervall einwirkt. Die Berechnung der häufigsten Klasse unter separat klassifizierten Teilreihen ergibt die endgültige Bezeichnung für die gesamte Zeitreihe.
Der bekannteste Vertreter des intervallbasierten Modells ist der Time Series Forest. Ein TSF ist eine Sammlung von Entscheidungsbäumen, die auf zufälligen Teilsequenzen des anfänglichen TS basieren. Jeder Baum ist für die Zuordnung einer Klasse zu einem Bereich verantwortlich.
Dies erfolgt durch die Berechnung zusammenfassender Merkmale (normalerweise Mittelwert, Standardabweichung und Steigung), um für jedes Intervall einen Merkmalsvektor zu erstellen. Entscheidungsbäume werden dann auf der Grundlage der berechneten Merkmale trainiert und Vorhersagen werden durch Mehrheitsabstimmung aller Bäume erhalten. Der Abstimmungsprozess ist notwendig, da jeder Baum nur eine bestimmte Teilsequenz des anfänglichen TS auswertet.
Neben TSF gibt es noch weitere intervallbasierte Modelle. Varianten von TSF nutzen zusätzliche Merkmale wie Median, Interquartilbereich, Minimal- und Maximalwerte der Unterreihen. Im Vergleich zum klassischen TSF-Algorithmus gibt es einen recht komplexen Algorithmus namens Random Interval Spectral Ensemble (RISE)-Algorithmus. Der
RISE-Algorithmus unterscheidet sich vom klassischen TS-Wald in zwei Aspekten.
Bei der RISE-Technik bauen alle Entscheidungsbäume auf ein anderer Satz von Fourier-, Autokorrelations-, autoregressiven und partiellen Autokorrelationsmerkmalen. Der Algorithmus funktioniert wie folgt:
Wählen Sie die ersten zufälligen Intervalle von TS aus und berechnen Sie die oben genannten Merkmale für diese Intervalle. Anschließend wird durch Kombinieren der extrahierten Features ein neuer Trainingssatz erstellt. Darauf aufbauend wird ein Entscheidungsbaumklassifikator trainiert. Diese Schritte werden schließlich mit unterschiedlichen Konfigurationen wiederholt, um ein Ensemblemodell zu erstellen, bei dem es sich um eine zufällige Gesamtstruktur eines einzelnen Entscheidungsbaumklassifikators handelt.
Der wörterbuchbasierte Algorithmus ist eine andere Art von TS-Klassifikator, der auf der Struktur des Wörterbuchs basiert. Sie decken eine Vielzahl verschiedener Klassifikatoren ab und können teilweise in Kombination mit den oben genannten Klassifikatoren verwendet werden. B OSS
Randomized BOSS
Symbolische Fourier-Approximation
Der bekannteste Algorithmus ist die Symbolische Fourier-Approximation (SFA), die in zwei Teile unterteilt werden kann.
Berechnen Sie die diskrete Fourier-Transformation von TS und behalten Sie dabei eine Teilmenge der berechneten Koeffizienten bei.
Überwacht: Die univariate Merkmalsauswahl wird verwendet, um höherrangige Koeffizienten basierend auf Statistiken (z. B. F-Statistik oder χ2-Statistik) auszuwählen.
Unüberwacht: Nimmt normalerweise eine Teilmenge des ersten Koeffizienten, die den Trend von TS darstellt
Überwachung: Berechnen Sie Binning-Kanten so, dass das Verunreinigungskriterium der Instanzentropie minimiert wird.
Unüberwacht: Berechnen Sie die Klassenkanten basierend auf den Extremwerten der Fourier-Koeffizienten (die Klassen sind einheitlich) oder basierend auf deren Quantilen (die gleiche Anzahl von Koeffizienten in jeder Klasse)
Basierend auf der Voreinstellung oben Verarbeitung: Zur weiteren Verarbeitung der Informationen können verschiedene Algorithmen verwendet werden, um Vorhersagen für TS zu erhalten.Extrahiert Teilsequenzen von TS durch einen Schiebefenstermechanismus.
Der Contractable BOSS (cBOSS)-Algorithmus ist rechnerisch viel schneller als die klassische BOSS-Methode.
Eine Beschleunigung wird dadurch erreicht, dass nicht eine Rastersuche für den gesamten Parameterraum, sondern für zufällig ausgewählte Stichproben daraus durchgeführt wird. cBOSS verwendet eine Teilstichprobe der Daten für jeden Basisklassifikator. cBOSS verbessert die Speichereffizienz, indem es nur eine feste Anzahl der besten Basisklassifikatoren berücksichtigt und nicht alle Klassifikatoren über einem bestimmten Leistungsschwellenwert.
Die nächste Variante des BOSS-Algorithmus ist Randomized BOSS (RBOSS). Diese Methode fügt einen stochastischen Prozess bei der Auswahl der Schiebefensterlänge hinzu und aggregiert geschickt die Vorhersagen einzelner BOSS-Klassifikatoren. Dies ähnelt der cBOSS-Variante und reduziert die Rechenzeit bei gleichzeitiger Beibehaltung der Grundleistung.
Der TS Classifier Extraction (WEASEL)-Algorithmus kann die Leistung der Standard-BOSS-Methode verbessern, indem er Schiebefenster unterschiedlicher Länge in der SFA-Transformation verwendet. Ähnlich wie andere BOSS-Varianten verwendet es Fenstergrößen unterschiedlicher Länge, um TS in Merkmalsvektoren umzuwandeln, die dann von einem KNN-Klassifikator ausgewertet werden.
WEASEL verwendet eine spezielle Methode zur Merkmalsableitung, bei der nur nicht überlappende Teilsequenzen jedes Schiebefensters verwendet werden, indem ein χ2-Test angewendet und die relevantesten Merkmale herausgefiltert werden.
Kombinieren Sie WEASEL mit Multivariate Unsupervised Symbols (WEASEL+MUSE), um multivariate Features aus TS zu extrahieren und zu filtern, indem Sie Kontextinformationen in jedes Feature kodieren.
Die Shapelet-basierte Methode nutzt die Idee von Teilsequenzen der anfänglichen Zeitreihe (d. h. Shapelets). Shapelets werden ausgewählt, um sie als Repräsentanten von Klassen zu verwenden, was bedeutet, dass Shapelets die Hauptmerkmale einer Klasse enthalten, die zur Unterscheidung verschiedener Klassen verwendet werden können. Im optimalen Fall können sie lokale Ähnlichkeiten zwischen TS innerhalb derselben Klasse erkennen.
Die Abbildung unten zeigt ein Beispiel für ein Shapelet. Es ist nur eine Teilsequenz des gesamten TS.
Die Verwendung von Shapelets-basierten Algorithmen erfordert das Problem, zu bestimmen, welche Shapelets verwendet werden sollen. Es ist möglich, von Hand einen Satz Shapelets auszuwählen, dies kann jedoch sehr schwierig sein. Shapelets können mithilfe verschiedener Algorithmen auch automatisch ausgewählt werden.
Shapelet Transform ist ein Algorithmus, der auf der Shapelet-Extraktion basiert und von Lines et al. vorgeschlagen wurde. Es ist einer der derzeit am häufigsten verwendeten Algorithmen. Bei einem TS von n reellwertigen Beobachtungen wird ein Shapelet durch eine Teilmenge von TS der Länge l definiert.
Der Mindestabstand zwischen einem Shapelet und dem gesamten TS kann mithilfe des euklidischen Abstands – oder einer anderen Abstandsmetrik – als Abstand zwischen dem Shapelet selbst und allen Shapelets der Länge l ausgehend vom TS gemessen werden.
Dann wählt der Algorithmus die k besten Shapelets aus, deren Längen in einem bestimmten Bereich liegen. Dieser Schritt kann als eine Art univariate Merkmalsextraktion betrachtet werden, wobei jedes Merkmal durch den Abstand zwischen dem Shapelet und allen TS im gegebenen Datensatz definiert wird. Die Shapelets werden dann anhand einiger Statistiken eingestuft. Dabei handelt es sich in der Regel um F-Statistiken oder χ²-Statistiken, die Shapelets nach ihrer Fähigkeit zur Klassenunterscheidung einordnen.
Nach Abschluss der oben genannten Schritte kann jede Art von ML-Algorithmus angewendet werden, um den neuen Datensatz zu klassifizieren. Zum Beispiel knn-basierte Klassifikatoren, Support-Vektor-Maschinen oder Random Forests usw.
Ein weiteres Problem bei der Suche nach idealen Shapelets ist die schreckliche Zeitkomplexität, die mit der Anzahl der Trainingsbeispiele exponentiell zunimmt.
Shapelet-lernbasierter Algorithmus versucht, die Einschränkungen von Algorithmen zu überwinden, die auf Shapelet-Extraktion basieren. Die Idee besteht darin, eine Reihe von Shapelets zu erlernen, die in der Lage sind, Klassen zu unterscheiden, anstatt sie direkt aus einem bestimmten Datensatz zu extrahieren.
Dies hat zwei Hauptvorteile:
Aber dieser Ansatz weist auch einige Nachteile auf, die durch die Verwendung einer differenzierbaren Minimierungsfunktion und des gewählten Klassifikators verursacht werden.
Um den euklidischen Abstand zu ersetzen, müssen wir uns auf differenzierbare Funktionen verlassen, sodass Shapelets über Gradientenabstiegs- oder Backpropagation-Algorithmen gelernt werden können. Am gebräuchlichsten ist die Funktion LogSumExp, die das Maximum durch Logarithmusbildung der Summe der Exponenten ihrer Argumente sanft annähert. Da die LogSumExp-Funktion nicht streng konvex ist, konvergiert der Optimierungsalgorithmus möglicherweise nicht korrekt, was zu schlechten lokalen Minima führen kann.
Und da der Optimierungsprozess selbst die Hauptkomponente des Algorithmus ist, müssen zur Optimierung mehrere Hyperparameter hinzugefügt werden.
Aber diese Methode ist in der Praxis sehr nützlich und kann einige neue Erkenntnisse über die Daten generieren.
Eine leichte Variation des Shapelet-basierten Algorithmus ist der Kernel-basierte Algorithmus. Lernen und verwenden Sie zufällige Faltungskerne (den gebräuchlichsten Computer-Vision-Algorithmus), die Merkmale aus einem bestimmten TS extrahieren.
Der ROCKET-Algorithmus (Random Convolution Kernel Transform) wurde speziell für diesen Zweck entwickelt. . Es verwendet eine große Anzahl von Kerneln, die sich in Länge, Gewicht, Bias, Dilatation und Padding unterscheiden und zufällig aus einer festen Verteilung erstellt werden.
Nach der Auswahl des Kernels benötigen Sie außerdem einen Klassifikator, der die relevantesten Merkmale zur Unterscheidung von Klassen auswählen kann. In der Originalarbeit wurde die Ridge-Regression (eine L2-regulierte Variante der linearen Regression) verwendet, um Vorhersagen zu treffen. Die Verwendung bietet zwei Vorteile: erstens die Recheneffizienz, selbst bei Klassifizierungsproblemen mit mehreren Klassen, und zweitens die Einfachheit der Feinabstimmung einzigartiger Regularisierungshyperparameter mithilfe der Kreuzvalidierung.
Einer der Hauptvorteile der Verwendung von Kernel-basierten Algorithmen oder ROCKET-Algorithmen besteht darin, dass der Rechenaufwand für deren Verwendung recht gering ist.
Merkmalsbasierte Methoden können im Allgemeinen die meisten Algorithmen abdecken, die eine Art Merkmalsextraktion für eine bestimmte Zeitreihe verwenden, und Vorhersagen werden dann von einem Klassifizierungsalgorithmus durchgeführt.
Über Features, von einfachen statistischen Features bis hin zu komplexeren Fourier-basierten Features. Eine große Anzahl solcher Funktionen ist in hctsa (https://github.com/benfulcher/hctsa) zu finden, aber das Ausprobieren und Vergleichen der einzelnen Funktionen kann eine unmögliche Aufgabe sein, insbesondere bei größeren Datensätzen. Daher wurde der typische Algorithmus für Zeitreihenmerkmale (catch22) vorgeschlagen.
Diese Methode zielt darauf ab, einen kleinen TS-Funktionssatz abzuleiten, der nicht nur eine starke Klassifizierungsleistung erfordert, sondern auch die Redundanz weiter minimiert. Catch22 hat insgesamt 22 Features aus der hctsa-Bibliothek ausgewählt (die Bibliothek bietet mehr als 4000 Features).
Die Entwickler dieser Methode erhielten 22 Funktionen, indem sie verschiedene Modelle auf 93 verschiedenen Datensätzen trainierten und die leistungsstärksten TS-Funktionen darauf bewerteten, was zu einer kleinen Teilmenge führte, die immer noch eine hervorragende Leistung beibehielt. Der darauf befindliche Klassifikator kann frei gewählt werden, was ihn zu einem weiteren zu optimierenden Hyperparameter macht.
Ein weiterer funktionsbasierter Ansatz ist der Matrix Profile (MP)-Klassifikator, ein MP-basierter interpretierbarer TS-Klassifikator, der interpretierbare Ergebnisse liefern und gleichzeitig die Basisleistung beibehalten kann.
Die Designer extrahierten ein Modell namens Matrix Profile aus einem Shapelet-basierten Klassifikator. Das Modell repräsentiert alle Abstände zwischen einer Teilsequenz eines TS und seinen nächsten Nachbarn. Auf diese Weise kann MP die Merkmale von TS wie Motive und Zwietracht effektiv extrahieren. Motive sind Untersequenzen von TS, die einander sehr ähnlich sind, während Zwietracht Sequenzen beschreibt, die sich voneinander unterscheiden.
Als theoretisches Klassifizierungsmodell kann jedes Modell verwendet werden. Die Entwickler dieser Methode haben sich für Entscheidungsbaumklassifikatoren entschieden.
Zusätzlich zu den beiden genannten Methoden bietet sktime auch einige weitere funktionsbasierte TS-Klassifikatoren.
Model Ensemble selbst ist kein unabhängiger Algorithmus, sondern eine Technik, die verschiedene TS-Klassifikatoren kombiniert, um bessere kombinierte Vorhersagen zu erstellen. Modellensembles reduzieren die Varianz durch die Kombination mehrerer Einzelmodelle, ähnlich einem Zufallswald mit einer großen Anzahl von Entscheidungsbäumen. Und die Verwendung verschiedener Arten unterschiedlicher Lernalgorithmen führt zu einem breiteren und vielfältigeren Satz erlernter Merkmale, was wiederum zu einer besseren Klassendiskriminierung führt.
Das beliebteste Modellensemble ist das Hierarchical Vote Collective of Transformation-based Ensembles (HIVE-COTE). Es gibt viele verschiedene Arten ähnlicher Versionen, aber allen gemeinsam ist die Kombination von Informationen aus verschiedenen Klassifikatoren, d. h. Vorhersagen, durch die Verwendung eines gewichteten Durchschnitts für jeden Klassifikator.
Sktime verwendet zwei verschiedene HIVE-COTE-Algorithmen, von denen der erste Wahrscheinlichkeiten pro Schätzer kombiniert, einschließlich eines Shapelet Transform Classifier (STC), eines TS Forest, eines RISE und eines cBOSS. Der zweite wird durch eine Kombination aus STC, Diverse Canonical Interval Forest Classifier (DrCIF, eine Variante von TS Forest), Arsenal (eine Sammlung von ROCKET-Modellen) und TDE (eine Variante des BOSS-Algorithmus) definiert.
Die endgültige Vorhersage wird durch den CAWPE-Algorithmus erhalten, der jedem Klassifikator Gewichte zuweist, die anhand der relativen geschätzten Qualität der im Trainingsdatensatz gefundenen Klassifikatoren ermittelt werden.
Die folgende Abbildung ist ein häufig verwendetes Diagramm zur Visualisierung der Arbeitsstruktur des HIVE-COTE-Algorithmus:
Über den Deep-Learning-basierten Algorithmus können Sie einen langen Artikel zur Erläuterung schreiben es selbst Alle Details für jede Architektur. In diesem Artikel werden jedoch nur einige häufig verwendete Benchmark-Modelle und -Techniken für die TS-Klassifizierung vorgestellt.
Während auf Deep Learning basierende Algorithmen in Bereichen wie Computer Vision und NLP sehr beliebt sind und umfassend untersucht werden, sind sie im Bereich der TS-Klassifizierung weniger verbreitet. Fawaz et al. Eine umfassende Untersuchung aktuell vorhandener Methoden in ihrem Artikel über Deep Learning für die TS-Klassifizierung: Zusammenfassung untersuchte mehr als 60 Modelle neuronaler Netzwerke (NN) mit sechs Architekturen:
Die meisten der oben genannten Modelle wurden ursprünglich für verschiedene Anwendungsfälle entwickelt. Daher muss es für verschiedene Anwendungsfälle getestet werden.
Außerdem wurde 2020 das InceptionTime-Netzwerk ins Leben gerufen. InceptionTime ist ein Ensemble aus fünf Deep-Learning-Modellen, von denen jedes von InceptionTime erstellt wurde, das zuerst von Szegedy et al. vorgeschlagen wurde. Diese ersten Module wenden mehrere Filter unterschiedlicher Länge gleichzeitig auf den TS an und extrahieren gleichzeitig relevante Merkmale und Informationen aus kürzeren und längeren Teilsequenzen des TS. Das folgende Bild zeigt das InceptionTime-Modul.
Es besteht aus mehreren Anfangsmodulen, die im Feed-Forward-Verfahren gestapelt und mit den Residuen verbunden sind. Schließlich generieren globale Durchschnittspools und vollständig verbundene neuronale Netze Vorhersageergebnisse.
Das Bild unten zeigt die Funktionsweise eines einzelnen Anfangsmoduls.
Die große Liste der in diesem Artikel zusammengefassten Algorithmen, Modelle und Techniken kann nicht nur zum Verständnis des weiten Bereichs der Zeitreihenklassifizierungsmethoden beitragen, ich hoffe auch, dass sie Ihnen hilfreich sein wird
Das obige ist der detaillierte Inhalt vonZusammenfassung von acht Zeitreihenklassifizierungsmethoden. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!
Algorithmus zum Ersetzen von Seiten
Passende Zeichenfolge für einen regulären Java-Ausdruck
Ist Huaweis Hongmeng-Betriebssystem Android?
Verwendung der Wertfunktion
So verwenden Sie Oracleparameter
So beheben Sie die Zeitüberschreitung des Vorgangs
Warum kann Swoole im Speicher verbleiben?
Wie viel kostet ein Bitcoin in RMB?
