+ Répondre à la discussion
Affichage des résultats 1 à 4 sur 4
  1. #1
    Membre régulier Avatar de M.Max
    Homme Profil pro
    Inscrit en
    décembre 2009
    Messages
    90
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Paris (Île de France)

    Informations forums :
    Inscription : décembre 2009
    Messages : 90
    Points : 99
    Points
    99

    Par défaut Quel algo pour cette problématqiue ?

    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

  2. #2
    Expert Confirmé Sénior Avatar de Graffito
    Inscrit en
    janvier 2006
    Messages
    5 842
    Détails du profil
    Informations forums :
    Inscription : janvier 2006
    Messages : 5 842
    Points : 7 555
    Points
    7 555

    Par défaut

    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.
    " Le croquemitaine ! Aaaaaah ! Où ça ? " ©Homer Simpson

  3. #3
    Membre régulier Avatar de M.Max
    Homme Profil pro
    Inscrit en
    décembre 2009
    Messages
    90
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Paris (Île de France)

    Informations forums :
    Inscription : décembre 2009
    Messages : 90
    Points : 99
    Points
    99

    Par défaut

    Citation Envoyé par Graffito Voir le message
    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 ?

  4. #4
    Membre Expert
    Homme Profil pro
    Chercheur
    Inscrit en
    mars 2010
    Messages
    1 204
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Chercheur

    Informations forums :
    Inscription : mars 2010
    Messages : 1 204
    Points : 1 645
    Points
    1 645

    Par défaut

    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.

Liens sociaux

Règles de messages

  • Vous ne pouvez pas créer de nouvelles discussions
  • Vous ne pouvez pas envoyer des réponses
  • Vous ne pouvez pas envoyer des pièces jointes
  • Vous ne pouvez pas modifier vos messages
  •