Publicité
+ Répondre à la discussion
Affichage des résultats 1 à 6 sur 6
  1. #1
    Invité de passage
    Inscrit en
    août 2008
    Messages
    10
    Détails du profil
    Informations forums :
    Inscription : août 2008
    Messages : 10
    Points : 0
    Points
    0

    Par défaut Algorithme de classification

    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 .

  2. #2
    Membre habitué Avatar de sologne
    Homme Profil pro
    Chargé de missions
    Inscrit en
    mai 2011
    Messages
    67
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Loir et Cher (Centre)

    Informations professionnelles :
    Activité : Chargé de missions
    Secteur : Service public

    Informations forums :
    Inscription : mai 2011
    Messages : 67
    Points : 108
    Points
    108

    Par défaut

    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

  3. #3
    Membre éprouvé
    Inscrit en
    avril 2008
    Messages
    405
    Détails du profil
    Informations personnelles :
    Âge : 48

    Informations forums :
    Inscription : avril 2008
    Messages : 405
    Points : 418
    Points
    418

    Par défaut

    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.

  4. #4
    Membre chevronné
    Profil pro Alexis
    Ingénieur de recherche en informatique
    Inscrit en
    juin 2009
    Messages
    435
    Détails du profil
    Informations personnelles :
    Nom : Alexis
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur de recherche en informatique

    Informations forums :
    Inscription : juin 2009
    Messages : 435
    Points : 650
    Points
    650

    Par défaut

    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.

  5. #5
    Invité de passage
    Homme Profil pro idir ait hammi
    Étudiant
    Inscrit en
    novembre 2013
    Messages
    4
    Détails du profil
    Informations personnelles :
    Nom : Homme idir ait hammi
    Localisation : Algérie

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : novembre 2013
    Messages : 4
    Points : 2
    Points
    2

    Par défaut code

    Tu peux utiliser le logiciel R (RStudio)
    un bout de code sur le lien suivant :http://idir.olympe.in/

  6. #6
    Membre éprouvé
    Inscrit en
    avril 2008
    Messages
    405
    Détails du profil
    Informations personnelles :
    Âge : 48

    Informations forums :
    Inscription : avril 2008
    Messages : 405
    Points : 418
    Points
    418

    Par défaut

    Citation Envoyé par idir.ait Voir le message
    Tu peux utiliser le logiciel R (RStudio)
    un bout de code sur le lien suivant :http://idir.olympe.in/
    Merci Idir. Tout ça commence à être un peu vieux (posts de début 2013), mais je vais regarder le lien que tu indiques.

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
  •