Qu'est-ce qu'un moyen robuste d'ajuster des données linéaires mais bruyantes par morceaux?
Je mesure un signal, qui se compose de plusieurs segments presque linéaires. Je voudrais ajuster automatiquement plusieurs lignes aux données pour détecter les transitions.
L'ensemble de données se compose de quelques milliers de points, avec 1-10 segments et je connais le nombre de segments.
Ceci est un exemple de ce que j'aimerais faire automatiquement.
algorithms
P3trus
la source
la source
Réponses:
J'ai essayé deux approches, naïvement (en utilisant seulement 3 segments). Il y aurait sûrement des méthodes plus sophistiquées.
RANSAC, censé être un mécanisme d'ajustement robuste. Il est facile d'arrêter l'algorithme après un certain nombre de segments. Cependant, il peut être difficile d'imposer la continuité entre les segments - comme cela semble requis dans votre application - au moins avec une implémentation simple. Comme preuve de concept, j'ai créé une image à partir des points de données pour pouvoir utiliser le moteur RANSAC disponible dans , la fonction de détection de ligne de Mathematica.jem a ge L i n e s
Ajustez un modèle linéaire par morceaux à l'aide d'un minimiseur à usage général. Il est facile d'imposer la continuité des segments. Fait intéressant, les tests de résidus et d'autres propriétés peuvent fournir suffisamment d'informations pour déterminer automatiquement le nombre de segments - je ne l'ai pas essayé cependant. Voilà à quoi ça ressemble dans Mathematica:
la source
la source
(Des années plus tard), les fonctions linéaires par morceaux sont des splines de degré 1, ce qu'on peut dire à la plupart des ajusteurs de splines. scipy.interpolate.UnivariateSpline par exemple peut être exécuté avec
k=1
et un paramètre de lissages
, avec lequel vous devrez jouer - voir scipy-interpolation-with-univariate-splines .Dans Matlab, voir comment choisir les nœuds .
Ajouté: trouver des nœuds optimaux n'est pas facile, car il peut y avoir de nombreux optima locaux. Au lieu de cela, vous donnez à UnivariateSpline une cible
s
, la somme de l'erreur ^ 2, et le laissez déterminer le nombre de nœuds. Après l'ajustement,get_residual()
obtiendra la somme réelle de l'erreur ^ 2 etget_knots()
les nœuds. Un petit changements
peut changer beaucoup les nœuds, en particulier en cas de bruit élevé - ymmv.Le graphique montre les ajustements à une fonction linéaire aléatoire par morceaux + bruit pour divers
s
.Pour ajuster des constantes par morceaux, voir Détection d'étape . Peut-on l'utiliser pour pw linear? Je ne sais pas; commencer par différencier les données bruyantes augmentera le bruit, mal.
D'autres fonctions de test et / ou des liens vers des articles ou du code seraient les bienvenus. Quelques liens:
Les splines linéaires sont très sensibles à l'endroit où sont placés les
Il s'agit d'un problème délicat et la plupart des gens sélectionnent simplement les nœuds par essais et erreurs.
Une approche qui gagne en popularité est d'utiliser à la place des splines de régression pénalisées.
régression linéaire par morceaux avec des nœuds en tant que paramètres
nœuds. Sélection de nœuds pour les splines de régression cubique
Ajouté en mars 2014: la programmation dynamique est une méthode générale pour les problèmes avec des sous-problèmes imbriqués comme celui-ci:
La programmation dynamique est très intelligente, mais peut-elle battre la force brute + l'heuristique pour cette tâche?
Voir les excellentes notes de cours par Erik Demaine sous MIT 6.006 Introduction aux algorithmes
également régression linéaire segmentée google
également syndrome de John Henry.
la source
Prenez la dérivée et recherchez des zones de valeur presque constante. Vous auriez besoin de créer l'algorithme pour rechercher ces zones avec idéalement un certain niveau de pente +/- et cela vous donnerait la pente de la ligne pour cette section. Vous voudrez peut-être effectuer un certain lissage, comme une moyenne glissante, avant de procéder à la classification en coupe. La prochaine étape serait d'obtenir l'intersection y, qui devrait être triviale à ce point.
la source
Utiliser un filtre de tendance l1 est une autre idée:
Papier
Exemple en ligne
la source