Quel algo pour cette problématqiue ?

[M.Max]

Hello everybody,

Je bosse sur une problématique de pattern matching (série temporelle), j'ai développé un algo qui a chaque nouveau signal renvoi une distance entre un pattern et un ensemble des x-derniers signaux. Cette fenêtre peut aller de 1000 à 4000 points.

Disons qu'à chaque nouvelle donnée x, je peux calculer une distance z pour l'ensemble des fenêtres (y) possibles (y E [1000;4000]).
Pour une fenêtre de 1000 points, l'ensemble que je vais comparer au pattern sera de X(n-1000) à Xn où Xn est le dernier signal que j'ai reçu.
Donc j'ai pour chaque x, 3000 couples (y,z).

Sur le papier tout va bien, je peux calculer tous mes (x,y,z). Lorsque z est sous un seuil déterminé, je peux sans trop de difficultés (c'est un autre sujet..) trouver les minimums locaux. J'obtiens ainsi à quels points x et pour quelles fenêtres y la distance est minimale entre mon pattern et mes données.

En pratique c'est plus compliqué, la quantité de calcul est telle qu'il me faudrait des mois pour obtenir cette matrice (x,y,z). Le code est optimisé et multithreadé.
Je veux donc rajouter une logique qui détermine quels sont les couples (x,y) pour lesquels z doit être calculé. Il me faut quadriller la matrice en diminuant le pas d'autant que z diminue pour obtenir plus de précision sur les minimums locaux. Il faut aussi prendre en compte que z varie d'autant plus vite que y est petit, et inversement...
Quelle direction dois-je prendre ? Connaissez-vous des algos/méthodes numériques qui me permettent de faire ça efficacement ?

Merci pour vos lumières

Modif : Je viens de me rendre compte que j'ai posté sous le forum IA, peut être que la racine du forum algo serait plus pertinente pour ce post

[Graffito]

une logique qui détermine quels sont les couples (x,y) pour lesquels z doit être calcul

On ne pourra envisager une telle logique que si les signaux traités ont des caractéristiques spécifiques.

Par exemple si le signal présente des minima ou des maxima en terme d'intensité ou de fréquence, il serait possible de réduire la(les) plage(s) des y traités en déduisant le décalage en y depuis la position de ces minima et maxima.

Ou alors, si on peut classer le signal dans des catégories distinctes on ne comparera que 2 signaux de la même catégorie ou de catégorie proche.

[M.Max]

Envoyé par Graffito

On ne pourra envisager une telle logique que si les signaux traités ont des caractéristiques spécifiques.

Par exemple si le signal présente des minima ou des maxima en terme d'intensité ou de fréquence, il serait possible de réduire la(les) plage(s) des y traités en déduisant le décalage en y depuis la position de ces minima et maxima.

Ou alors, si on peut classer le signal dans des catégories distinctes on ne comparera que 2 signaux de la même catégorie ou de catégorie proche.

Merci de ta réponse. C'est pertinent mais je ne me suis pas tres bien exprimé.

En fait il s'agit seulement de réduire la quantité de calcul.

Donc ça peut être une règle qui dit :

1. tester un pas de 50 pour les fenêtres y. Soit on calcul pour y € {1000, 1050, 1100, ... , 3950, 4000}

2. Si le résultat z est inférieur à un seuil alors on affine. Donc si, par exemple, pour y =2550, z est inférieur à ce seuil, au lieu de passer à y=3000, je vais plutot calculer avec un pas de 10 soit pour 2560,2570,... jusqu'à ce que le résultat repasse au dessus de ce seuil, et là je reprends mon pas de 50. Ainsi j'aurais eu plus de finesse pour les minimums locaux.

Il s'agit de rendre plus dynamiques les règles ci-dessus. D'autant que des règles linéaires sont insuffisantes car le pas doit être plus fin lorsque y est petit (variance de z élevée) et inversement.

Des idées ?

[Aleph69]

Bonjour,

si j'ai bien compris, ton problème revient à chercher des extrema d'une fonction f(x,y) à partir d'une grille (x,y) et tu te demandes comment raffiner intelligemment ta grille pour approcher ces extrema sans faire trop de calculs. A mon avis, l'approche n'est pas la bonne et il n'y a pas de méthode robuste pour faire cela car il faut d'abord être sûr que ta grille initiale est suffisamment fine pour capter tous les extrema, ce qui est particulièrement difficile à vérifier. De plus, dans beaucoup de cas, cette grille initiale est souvent déjà trop fine et les calculs correspondants lourds. Il faut voir si une autre approche est possible à partir des des données de ton problème. A l'aide d'une analyse, on peut peut-être deviner où sont ces extrema, ou les situer grossièrement à l'aide d'une méthode numérique de recherche de zéro.