Ajuster des données linéaires par morceaux

18

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.

entrez la description de l'image ici

P3trus
la source
Je ne pense pas que l'on puisse répondre raisonnablement à cette question, à moins que vous ne nous disiez avec quelle précision vous souhaitez connaître les emplacements des points d'arrêt, quelle est votre estimation pour la plus courte longueur d'un segment linéaire et combien d'échantillons il y a dans un échantillon typique. région de transition. Si les étiquettes des axes horizontaux de votre figure sont des nombres d'échantillons, alors, avec deux transitions dans la plage de à x [ 0 ] , la tâche est plus difficile que si les segments linéaires étaient de plus longue durée (en échantillons). X[-5]X[0]
Dilip Sarwate
@DilipSarwate J'ai mis à jour la question avec les exigences (à savoir que le xaxis est le champ magnétique de tesla)
P3trus
Vous pouvez essayer cette boîte à outils si vous travaillez avec la boîte à outils d'ajustement de courbe
Rhei

Réponses:

12

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.jemunegeLjenes

entrez la description de l'image ici

    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:

entrez la description de l'image ici

Matthias Odisio
la source
On dirait une excellente réponse. Merci d'avoir contribué.
Jason R
7

X[n]

  • X[n]y[n]

    y[n]={1,si |(X[n+1]-X[n])-(X[n]-X[n-1])|<ϵ,0,autrement.
    ϵx[n1],x[n],x[n+1](n1,x[n1])(n,x[n])(n,x[n])(n+1,x[n+1])
  • y[n]1011ϵ

  • y[n]x[3]x[88]x[94]x[120]x[129], etc. Étendez A vers la droite et B vers la gauche pour savoir où ils se croisent; étendez B vers la droite et C vers la gauche pour savoir où ils se croisent, etc. Félicitations, vous disposez maintenant d'un modèle linéaire continu et par morceaux pour vos données.

Dilip Sarwate
la source
J'ai totalement volé ma réponse! =)
Phonon
Idée intéressante mais malheureusement à cause du bruit sur le signal je n'obtiens pas de bons résultats.
P3trus
1
Cette expression dont la magnitude est comparée à epsilon est en fait une approximation de la dérivée seconde des données. Il existe d'autres façons de calculer cela en utilisant plus de trois points qui ne répondent pas autant au bruit. Recherchez Savitzky-Golay.
DarenW
4

(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 lissage s, 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 et get_knots()les nœuds. Un petit changement speut 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:
régression linéaire par morceaux avec des nœuds en tant que paramètres
Les splines linéaires sont très sensibles à l'endroit où sont placés les
nœuds. Sélection de nœuds pour les splines de régression cubique
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.


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:

optimal k lines
    = optimal k - 1 lines up to some x
    + cost of the last line x to the end
over x  (all x in theory, nearby x in practice)

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.


entrez la description de l'image ici

denis
la source
Le problème, au moins avec scipy, est le positionnement des nœuds. scipy utilise des nœuds équidistants.
P3trus
@ P3trus, oui pour commencer, mais ensuite ils peuvent se déplacer - voir l'intrigue. Quoi qu'il en soit, il cible l'erreur totale, pas les nœuds.
denis
@ P3trus Avez-vous essayé d'utiliser la méthode des splines de régression multivariée qui sélectionne automatiquement les points d'arrêt de manière itérative? cs.rtu.lv/jekabsons/regression.html
Atul Ingle
@Atul Ingle, la sélection de point d'arrêt / noeud afaik est le même problème, quel que soit le monteur de spline. Si vous connaissez différents algorithmes pour cela des gens de R / régression, pourriez-vous poster un lien s'il vous plaît?
denis
Cherchez-vous des packages dans R / Matlab qui font des splines de régression adaptative? Ici: cran.r-project.org/web/packages/earth/index.html cran.r-project.org/web/packages/mda/index.html et aussi ARESLab dans Matlab pour lequel j'ai déjà posté le lien.
Atul Ingle
0

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.

porten
la source
dérivé pourrait être offul bruyant. je ne pense pas que je recommanderais cela.
robert bristow-johnson
0

Utiliser un filtre de tendance l1 est une autre idée:

Papier

Exemple en ligne

SeanVN
la source
1
Votre réponse est un peu trop courte pour être constructive! Veuillez envisager de faire un effort pour l'étendre de manière pédagogique.
sansuiso