Algorithme de classification

**youmew** · 04/03/2013, 13h16

Bonjour
Dans le cadre d'un projet personnel je suis amené à trouver un algorithme de classification sur une population d'environ 10 000 individus suivant environ 20 critères pour former des groupes homogènes d'environ 50 individus .

J'ai donc crée ma fonction "distance" dont il s'agit en fait d'une norme euclidienne "pondérée" ( certains critères sont plus importants que d'autres) et je m'en vais essayer l'algorithme CAH ( classification ascendante hiérarchique ) qui d'après mes recherches semble assez utilisé mais avant de me prendre la tête sur la chose j'aimerais savoir si vous avez une estimation sur la durée d’exécution sur un ordinateur "normal" car j'ai besoin de pouvoir jouer sur mes coefficients de pondération pour trouver la classification que je souhaite (2/3h max donc par test ) et de plus j'aimerais savoir si il existerai un algorithme de "triangularisation" en dimension 2 pour que je puisse représenter spatialement la segmentation (sa m'aiderai beaucoup ) - j'ai pensé projeter sur x les 10 premiers critères (toujours pondéré) puis sur y les 10 autres . Qu'en pensez vous ?
Connaissez vous d'autres algorithmes plus efficace ? Pensez vous que ma fonction distance convienne ?

Je n'ai absolument aucune connaissance en algorithmique approfondie je suis étudiant en électronique merci d'avance pour votre aide .

**sologne** · 05/03/2013, 09h33

Bonjour,

l'algorithme de classification ascendante implique deux boucles imbriquées, ainsi,il est d'ordre n^2. Néanmoins en l'optimisant comme cela est proposé ici, tu arrives à un ordre de n^2/2, ce qui avec une population n = 10000 individus va te conduire à produire (10000)^2/2 = 50 millions d'appels à ta fonction de distance.

Ainsi j'opterais pour l'utilisation d'un langage compilé type C ou C++

Pour que tu te fasses une idée tu temps que cela va prendre, lance une boucle de calcul simple sur 10000 puis 100000 individus, puis tu interpoles le temps.

Pour le choix de ta distance, je l'adapterais en fonction du temps d'exécution ... en effet la norme euclidienne est gourmande en calcul, notamment avec l'ajout de la racine carrée qui peut être évitée (le carré de la distance euclidienne est toujours une distance).

Fais quelques tests et tient nous au courant.

Bon courage

**Alikendarfen** · 16/03/2013, 20h23

J'ai utilisé récemment (voir discussion ici : http://www.developpez.net/forums/d13...ces-positions/) un réseau de Kohonen pour un problème qui semble assez similaire au tien.

La complexité est moindre à ce qui est évoqué ici (surtout si on limite la portée de la modif d'un neurone sur ses voisins, ce qui est très raisonnable).

Pour info, lors de mes tests :
- Environ 6 600 données (10 000 pour toi)
- 6 600 critères (car je compare les données entre elles), alors que tu en as 20
- 400 "groupes" (ou en l'occurrence neurones en sortie), et tu en aurais 200 (200 x 50= 10 000)

Une très bonne convergence est obtenue en deux ou trois itérations (pour mon problème).
A chaque itération il y a :
- 6 600 x 400 calculs de distance (trouver le meilleur neurone en sortie)
- et au plus 400 (car on peut limiter la portée) calculs d'impact de l'affectation d'un neurone d'entrée à sa sortie

Par contre, rien ne garantit d'avoir des groupes de 50 en sortie exactement. Mais j'ai cependant eu des résultats assez répartis (groupes relativement homogènes).

Coté temps de calcul (sur un portable, implémentation en c#) : environ 20 minutes.

De plus, la "grille" de neurones de sortie peut directement constituer ta représentation 2D.

Quelques liens :
http://en.wikipedia.org/wiki/Self-organizing_map
http://www.codeproject.com/Articles/...s-Kohonen-maps

Je me suis inspiré de l'implémentation du dernier lien pour faire la mienne. Mais attention, celle du lien est super approximative (erreurs de cast, mélanges de variables membres, calculs inutiles dans des boucles imbriquées)... mais néanmoins elle est assez claire.

**Alexis.M** · 18/03/2013, 13h42

Pour la partie classification (clustering), tu as plusieurs possibilités outre celle que tu envisages:

- l'algorithme des K-moyennes (k-means)
- des algos basés sur des arbres de projection (PCA-trees)

Pour la visualisation, suivant la complexité des données tu peux envisager l'analyse en composante principale (ACP ou PCA en anglais). Il s'agit d'une méthode purement linéaire donc il n'est pas garantie qu'elle permette de projeter correctement les groupes.

Parmis les méthodes non-linéaires:
- les cartes de Kohonen comme l'indique Alikendarfen, ou peut-être plus adaptées les cartes de Sammon.
- l'analyse en composante principale à noyau ( Kernel-PCA ) avec un noyau local.

Au moins pour les K-means, la PCA ou KPCA tu trouveras des bibliothèques dans la plupart des langages de programmation courants.