Problème difficile

**Nemerle** · 28/07/2005, 15h52

Je dispose de 10 000 vecteurs ayant 10 000 composantes chacuns.

Le but du jeu est d'essayer de les regrouper en paquets de vecteurs "proches". Par exemple, si j'ai 6 vecteurs à une dimension, par xemple 1,2, 11,12,13, 33 j'aimerai avoir 3 paquets [1,2], [11,12,13] et [33].

La première idée qui vient est d'utiliser la norme quadratique: si V et W sont deux tels vecteurs, N(V,W)=racine_carrée(somme((Vi-Wi)^2)).

Avec cette norme, on pourrait essayer de recouvrir l'espace R^10000 de sphères englobant nos 10000 vecteurs de façon "intelligentes". Mais attention au temps de calcul...

Quelqu'un a-t-il déjà travaillé sur un problème similaire??

**Médiat** · 28/07/2005, 16h17

Analyse en clusters (en Composantes principales)

**Nemerle** · 28/07/2005, 16h44

tu peux développer?

**mathieu_t** · 28/07/2005, 18h35

Le principe est de se placer dans l'espace à 10 000 paramètres (cad tes 10 000 composantes), et de voir là où il y a des amas de points...

Le clustering permet de repérer ces groupements...
Pour ça plusieurs méthodes, dont l'une des plus efficaces est l'algorithme des k-moyennes : c'est un algo qui récursivement scinde l'espace en K régions...

On en a déjà parlé il y plusieurs mois sur ce forum, fais une recherche...

Sinon les mots clés pour Google sont clustering et K-means...

A+

**Matthieu Brucher** · 31/07/2005, 14h05

L'ACP te permettra de trouver un espace où tes points "évoluent le plus".
Autre solution, l'algorithme du mean-shift. C'est un peu comme le K-mean, mais pas vraiment non plus