Un problème algorithmique

Bonjour à tous,

Je sais que ce salon n'est peut-être pas le plus adapté pour ce type de question mais je n'ai pas trouvé ailleurs :) .

Voilà mon problème, j'ai besoin d'un algorithme performant car j'en ai trouvé quelques uns mais l'ordre de calcul minimum que j'ai trouvé au minimum est de O[(2^n)-1]. Bref c'est plutôt couteux sachant que j'ai 11 000 données à étudier.

Je vous explique la situation, j'ai un type de donnée de la sorte:

element:

nom1: valmin , valmax
nom2: valmin, valmax
....
nomN: valmin, valmax

Mon algorithme prend en entrée un ensemble d'élement ayant un ensemble de valeur avec valMin = valMax.

Par exemple:

e1:
a 1 1
b 2 2
c 2 2

e2:
a 2 2
b 4 4
c 5 5

e2:
a 3 3
b 3 3
c 6 6

Le but de mon algorithme est de définir les intervalles reliant ces types, dans cet exemple, le résultat obtenu serait:

e1:
a 1 1
b 2 2
c 2 2

e2:
a 2 2
b 4 4
c 5 5

e2:
a 3 3
b 3 3
c 6 6

t1:
a 1 3
b 2 4

t2 :
b 3 4
c 5 6



La jointure entre un element A et un element B se fait de cette facon:

admettons que nous ayons:

a1:
a 2 2
b 3 3
c 6 6

et

a2:
a 3 3
b 10 10
c 5 5

alors la jointure entre ces deux éléments sera:

t :
a 2 3
c 5 6
(pas de b car il n'y a pas de lien entre 3 et 10)

ça c'est simple à obtenir.

Le but de l'algorithme est de calculer un ensemble d'intervalles sans "trou".


Admettons que nous ayons :

e1:
a 1 1
b 2 2
c 2 2

e2:
a 3 3
b 3 3
c 6 6

Nous ne pouvons obtenir que

b 2 3

en revanche pour obtenir

a 1 3
b 2 3
c 2 6

il faut qu'il y ai au préalable (dans une liste temporaire, c'est comme ça que j'ai fait)

a 2 2 ou a 1 2 ou a 2 3 ou a 13
b 2 2 ou b 3 3 ou b 2 3
c 2 5 ou c 3 6 ou c 2 5 ou c 26

Bref c'est un peu compliqué, je ne sais pas si j'ai bien exprimé mon problème mais j'ai besoin d'aide car je n'arrive pas à avoir quelque chose de performant...

Merci beaucoup!

Si j'ai bien compris, tu as des données qu'on peut représenter ainsi

   1  2  3  4  5  6
-------------------- - -
a|e1 e2 e3  .  .  . 
b| . e1 e3 e2  .  .
c| . e1  .  . e2 e3

ce qui permet de construire un graphe d'accessibilité (via tes "jointures")

a1--a2--a3
|___    |
|   |   |
|   b2--b3--b4
|___        |__  
    |          |
    c2         c5--c6

et tu cherches le chemin le plus long (horizontalement) ?

Citation:

---

Si j'ai bien compris, tu as des données qu'on peut représenter ainsi

1 2 3 4 5 6
-------------------- - -
a|e1 e2 e3 . . .
b| . e1 e3 e2 . .
c| . e1 . . e2 e3
ce qui permet de construire un graphe d'accessibilité (via tes "jointures")

---

Pour toi les a,b,c sont les éléments et e1 e2 e3... sont l'ensemble des intervalles de ces éléments? C'est bien ça? Histoire qu'on soit d'accord lol!

En fait ce que je veux c'est un ensemble d'élément représentant tous les intervalles sans "trou" possibles .

Citation:

---

e1 -->[a1 1 , b2 2, c 3 3 ]
e2 -->[a3 3 , b4 4, c 6 6 ]
e3 -->[a4 4 , b5 5, c 4 4 ]

---

résultats:

Citation:

---

e1 -->[a1 1 , b2 2, c 3 3 ]
e2 -->[a3 3 , b4 4, c 6 6 ]
e3 -->[a4 4 , b5 5, c 4 4 ]
r1 --> [a3 4, b4 5]
r2 --> [c3 4]

---

Je ne sais pas si ça correspond à ce que tu disais, je n'ai pas très bien compris ton graphe

J'ai compris ta structure de données, mais je ne sais pas si c'est bon, en effet, dans ton exemple on obtient:

Citation:

---

a1--a2--a3
|___ |
| | |
| b2--b3--b4
|___ |__
| |
c2 c5--c6

t --> [a 1 3 ,b 2 4 ,c 5 6]

---

alors qu'on devrai obtenir ceci

t1 -->[a 1 3,b 2 4]
t2 --> [b 3 4, c 5 6]

Citation:

---

Envoyé par van noctar

J'ai compris ta structure de données, mais je ne sais pas si c'est bon, en effet, dans ton exemple on obtient:

t --> [a 1 3 ,b 2 4 ,c 5 6]

alors qu'on devrai obtenir ceci

t1 -->[a 1 3,b 2 4]
t2 --> [b 3 4, c 5 6]

---

Je ne comprend pas trop ta définition de ce qu'est une jointure valide.

J'avais cru comprendre qu'une jointure entre des éléments est l'ensemble des intervalles de taille >= 2 pour chaque composante (a,b,c) :

join(e1,e2) = { a[1:2] }
join(e1,e3) = { b[2:3] }
join(e2,e3) = { a[2:3] , b[3:4] , c[5:6] }
join(e1,e2,e3) = { a[1:3] , b[2:4] , c[5:6] }

Visiblement, ce n'est pas ca. Est-ce que tu pourrais nous expliquer la situation de départ qui t'as amené à ce problème d'intervalle/jointure ?

Prenons par exemple juste un intervalle:

P(a b) et Q(a b)

une jointure s'effectue de la sorte:

Citation:

---

Si( abs(P.a - Q.a) <= 1
|| abs(P.a - Q.b) <= 1
|| abs(P.b - Q.a) <= 1
|| abs(P.b - Q.b) <= 1
|| Q est inclu dans P )
alors jointure.
Sinon pas jointure.

---

Donc si on a un element A (composé bien sûr de n intervalles ) et un element B (idem), la jointure(A,B) = l'ensemble des jointures des intervalles de A et de B.

exemple:

Citation:

---

A-->[a(1 1); b(2 2) ; c(3 3)]
B-->[a(3 3); b(3 3) ; c(2 2)]
Jointure(A,B)-->[ b(2 3) ; c(2 3)]

---

Autre exemple, admettons que l'on ai ceci:

Citation:

---

A-->[a(1 3); b(2 4) ; c(3 7)]
B-->[a(3 3); b(6 6) ; c(2 2)]
Jointure(A,B)--> [ a(1 3); c(2 7) ]

---

J'espere que c'est plus clair...

La situation de départ est celle-ci:

J'ai un ensemble d'élément avec des caractéristiques(dans ce cas là des intervalles), je prend tous les éléments qui correspondent à un état H. De là j'obtiens mes élément:

A1 ---> [p1(x y);p2(x y);....;pn(x y)]
....
An ---> [p1(x y);p2(x y);....;pn(x y)]

et de là je veux obtenir plusieurs "modèles" ou filtre d'élements, de manière à ce que dès qu'on lance ce filtre à un ensemble d'élément, on ait de forte chance de tomber sur des élément qui correspondent à un état H.

Dans mon cas, j'ai plus de 300 000 élément, sur ces 300 000 j'en ai 11 000 qui correspondent à un état Q.


Admettons qu'on ai un ensemble de canapé ayant les propriétés suivantes:

Canapé --> [ prix, niveauQualité, Age ]

On veut un ensemble de canapé ayant niveauQualité = 1.

Bien sûr niveauQualité pour la recherche d'intervalle n'est pas pris en compte.

Donc pour la recherche nous aurions seulement les intervalles suivantes:

Canapé --> [ prix , Age ]

Le but est de trouver des filtres, de manière à ce que dès qu'on filtre des éléments "anciens ou nouveau" (car le filtre sera général aux canapés ), on trouve des canapé ayant de fortes chance d'avoir niveauQualité=1 au résultat.

J'espere avoir été plus clair, d'où ma demande d'un algorithme puissant pour trouver des intervalles, car j'ai enormement de données à traiter et mes algo à moi sont vraiment très très long.

Hum... Si j'ai bien compris, tu veux construire un crible à partir de données multi-dimensionnelles existantes (=base d'apprentissage). Le but étant de passer de nouvelles données dans ce crible pour les classifier.

Ca ressemble grandement à un sujet d'intelligence artificielle de classification de données. :D


J'ai du mal a voir si ton système de jointure est pertinent pour ce problème. Ca demande réflexion. Pour ma part, j'aurais plutôt opté pour des approches plus classiques : par exemple, commencer par regrouper tes données en classes, et ensuite travailler sur les classes.

Qu'entend tu par regrouper mes données en classe?

Citation:

---

Envoyé par van noctar

Qu'entend tu par regrouper mes données en classe?

---

Il s'agit de regrouper les éléments qui sont "proches" les uns de autres (suivant une fonction de distance basée sur ta définition de jointure).

Ou, au contraire, de séparer des éléments qui sont "éloignés".

Le but est d'avoir au final moins de données a gérer. Au lieu de comparer un nouveau candidat avec tous les éléments, on le compare avec les classes. Ca permet d'éliminer rapidement des classes (et donc des éléments) qui sont trop éloignés du nouveau candidat.

Je reprend mon exemple des canapé, admettons que l'on ait cet ensemble:

Dans le passé nous avons:

Citation:

---

Canape1 --> [ Age( 2 2); prix(45 45) ; niveauQualite(1 1)]
Canape2 --> [ Age( 8 8); prix(30 30) ; niveauQualite(3 3)]
Canape3 --> [ Age( 3 3); prix(35 35) ; niveauQualite(1 1)]
Canape4 --> [ Age( 7 7); prix(34 34) ; niveauQualite(1 1)]
Canape5 --> [ Age( 9 9); prix(20 20) ; niveauQualite(3 3)]
Canape6 --> [ Age( 8 8); prix(44 44) ; niveauQualite(1 1)]

---

Nous prenons notre sous-ensemble de canapé correspondant à :

Citation:

---

ModeleCanapé --> [niveauQualite(1 1)]

---

Nous obtenons (en enlevant les champs de modeleCanapé:
(tous les canapés de cet ensemble ont pour valeurs "niveauQualité = 1")

Citation:

---

Canape1 --> [ Age( 2 2); prix(45 45) ]
Canape3 --> [ Age( 3 3); prix(35 35) ]
Canape4 --> [ Age( 7 7); prix(34 34) ]
Canape6 --> [ Age( 8 8); prix(44 44) ]

---

Nous cherchons nos ensembles de modeles(filtres ou intervalles :) ) et nous trouvons:

Citation:

---

Canape1 --> [ Age( 2 2); prix(45 45) ]
Canape3 --> [ Age( 3 3); prix(35 35) ]
Canape4 --> [ Age( 7 7); prix(34 34) ]
Canape6 --> [ Age( 8 8); prix(44 44) ]
Result1 --> [ Age(2 3) ]
Result2 --> [ Prix(34 35) ]
Result3 --> [ Age( 7 8 ) ]
Result4 --> [ Prix(44 45) ]

---

Ensuite pour chacun de ces filtres nous étudions le nombre de fois que l'on trouve niveauQualité = 1 sur notre ensemble de départ.

Par exemple pour:

Result1 --> [ Age(2 3) ]

On obtient:

Citation:

---

Canape1 --> [ Age( 2 2); prix(45 45) ; niveauQualite(1 1)]
Canape3 --> [ Age( 3 3); prix(35 35) ; niveauQualite(1 1)]

Soit 100% d'appartition de niveauQualité(1 1).

---

Pour:

Result3 --> [ Age(7 8) ]

On obtient:

Citation:

---

Canape2 --> [ Age( 8 8); prix(30 30) ; niveauQualite(3 3)]
Canape4 --> [ Age( 7 7); prix(34 34) ; niveauQualite(1 1)]
Canape6 --> [ Age( 8 8); prix(44 44) ; niveauQualite(1 1)]

Soit 66% d'apparition de niveauQualite(1 1).

---

C'est pour cela qu'il faut que je trouve des filtres (ensembles d'intervalle). Tu as compris? Je ne sais pas si c'est un crible ce que je cherche, mais je ne vois pas comment je pourrais être plus clair :s

Je vois ce que tu veux dire... Assez compliqués de mettre ça en place car un élément peut appartenir à plusieurs classes, puis comment savoir d'avance quelles sont les classes à éliminer? enfin c'est assez chaud.

Citation:

---

Envoyé par van noctar

C'est pour cela qu'il faut que je trouve des filtres (ensembles d'intervalle). Tu as compris? Je ne sais pas si c'est un crible ce que je cherche, mais je ne vois pas comment je pourrais être plus clair :s

---

Class Q1 :
Canape1 --> [ Age( 2 2); prix(45 45) ; niveauQualite(1 1)]
Canape3 --> [ Age( 3 3); prix(35 35) ; niveauQualite(1 1)]
Canape4 --> [ Age( 7 7); prix(34 34) ; niveauQualite(1 1)]
Canape6 --> [ Age( 8 8); prix(44 44) ; niveauQualite(1 1)]

Class Q3 :
Canape2 --> [ Age( 8 8); prix(30 30) ; niveauQualite(3 3)]
Canape5 --> [ Age( 9 9); prix(20 20) ; niveauQualite(3 3)]

Séparateur des classes Q1/Q3:
- si (age<8) & (prix < 32) --> Q1
- si (age>8) & (prix > 32) --> Q3
- autrement : on ne sait pas

Évidement, c'est un exemple très simpliste de séparateur. On peut en construire de beaucoup mieux. Mais ca permet déjà d'accélérer la recherche des classes candidates, et de faire une comparaison plus poussée sur un plus petit nombre d'éléments.

J'ai lu l'article, c'est un peu brumeux encore mais bon j'ai compris le principe, le seul problème réside à ce que mes données ne sont pas des simples valeur mais un ensemble de valeur, qui plus est des intervalles... Alors comment calculer la separatrice(ou hyperplan), et encore plus, la distance entre cet hyper plan et mes données?

Citation:

---

Envoyé par van noctar

J'ai lu l'article, c'est un peu brumeux encore mais bon j'ai compris le principe, le seul problème réside à ce que mes données ne sont pas des simples valeur mais un ensemble de valeur, qui plus est des intervalles... Alors comment calculer la separatrice(ou hyperplan), et encore plus, la distance entre cet hyper plan et mes données?

---

J'ai mis un lien vers les SVM juste pour te montrer qu'il existe des outils mathématiques pour faire ce genre de chose. Cela dit, les SVM ne sont peut-être pas la méthode la plus adaptée pour ton problème. Et dans tous les cas, je te conseille d'utiliser un logiciel/librairie existant pour jouer avec les SVM, et de ne pas réinventer la roue.

Sinon, tu as d'autres méthodes de clustering qui seront peut être plus adaptées ou simples à implémenter.

D'accord! et bien merci c'est super! je vais me diriger vers ces deux voies!

Merci en tout cas pour t'être interéssé à mon cas et ton aide a été précieuse :)