Comment faire quand la CAH est dépassée?

lovely analytics CAH.png

La CAH permet de créer des groupes d’individus homogènes, c’est une méthode de clustering et elle donne vraiment de bons résultats. L’inconvénient de cette méthode c’est que les temps de calcul peuvent être très longs lorsque le nombre de clients à segmenter augmente. Certains outils refusent même de calculer une CAH à partir d’un certain seuil.

Problème : Comment faire un clustering efficace quand le nombre d’individus devient tellement important qu’on ne peut plus utiliser la CAH?

Solution n°1 : Changer de méthode et utiliser un k-means

La méthode la plus simple ce serait de ne pas utiliser une CAH mais de faire un k-means. Il n’y a pas de limite de taille et les calculs sont très rapides. En revanche les résultats sont moins bons en général. Cela s’explique par les contraintes du k-means :

  • Le nombre de groupes doit être déterminé avant
  • Les centres initiaux des groupes sont tirés aléatoirement

k-means

Solution n°2 : Calculer la CAH sur un échantillon

Une autre méthode consiste à calculer la CAH sur un échantillon de données. Vous obtiendrez ainsi le segment pour chaque individus de l’échantillon. Pour ensuite avoir un résultat sur le dataset en entier, il suffit de construire un arbre de décision (ou un autre modèle d’ailleurs mais en évitant le surrapprentissage). On calcule ce modèle sur l’échantillon pour prédire le segment puis on l’applique sur le dataset complet.

Cette méthode est à privilégier dans le cas où vous voulez expliquer simplement la segmentation. Avec l’arbre vous aurez déjà les règles permettant de comprendre chaque segment et vous gagnez ainsi une étape.

Decision tree

Solution n°3 : Utiliser la classification mixte

La méthode mixte a été créée justement pour ce genre de problèmes, c’est en fait une combinaison entre le k-means et la CAH.

On commence par créer un grand nombre de clusters avec la méthode des k-means. Puis on utilise les barycentres de ces clusters comme nouveaux individus pour lancer une CAH. On réduit donc la taille des données qui vont permettre de calculer la CAH et on gagne en temps de calculs.

Classification mixte

Le volume de données n’est pas un vrai problème 🙂

13 réflexions sur “Comment faire quand la CAH est dépassée?”

  1. Ping : Classification ascendante hiérarchique (CAH) comment ça marche? – Lovely Analytics

  2. Trop nul comme article : ce n’est que du temps perdu.

    On présente le problème mais on ne donne pas d’exemple de solution : par exemple, une implémentation Python.

    1. Bonjour,
      Cet article n’est pas un tutoriel Python, il présente 3 solutions à mettre en place quand le volume de données ne permet pas d’utiliser une CAH seule.
      Libre à vous de choisir la solution qui convient le mieux à votre cas et de l’implémenter sous Python.

  3. Bonsoir,
    J’ai fait une classification mixte kmeans puis CAH. Comment faire à la fin pour réaffecter automatiquement les individus à leur cluster final (partie 4 dans votre démo) ?J’ai d’un côté les individus associés à leurs clusters intermédiaires (après kmeans) et de l’autre côté les clusters intermédaires affectés aux clusters finaux (après CAH). La 1ère liste des individus-clust intermédiaires est évidemment plus longue que la 2ème cluster intermédiaires-clusters finaux.
    En vous remerciant par avance pour votre réponse car je me tourne les méninges dans tous les sens et n’arrive pas à résoudre ce problème, n’étant pas une pro dans la programmation dans R

    1. Bonjour,
      Vous avez fait le plus dur 🙂
      Maintenant il faut faire une jointure entre les 2 tables en utilisant les clusters intermédiaires comme clé de jointure. Vous pourrez de cette manière là avoir les clusters finaux pour vos individus initiaux.
      Pour faire une jointure sur R vous pouvez utiliser la librairie dplyr et la fonction left_join
      Voici un site qui détaille la procédure des jointures :https://delladata.fr/fusionner-deux-tableaux-de-donnees-par-leurs-colonnes-les-jointures/

      1. Bonjour,
        Merci beaucoup pour votre aide. Par contre, c’est sûrement simple mais je ne sais pas comment nommer la 1ère colonne qui correspond à la colonne 0 dans un tableau en général, celle où sont indiqués nos individus complètement à gauche et qui ne porte pas d’entête. Car dans mon cas, après avoir fait la CAH, sur mon 2ème tableau, il faut que je nomme la colonne complètement à gauche en clustint (à côté de clustfin à droite) pour qu’elle soit commune aux 2 tableaux.
        En vous remerciant par avance,
        Bien cordialement

        1. Tu parles peut être de rownames, la colonne qui contient les identifiants des lignes.
          Pour créer une « vraie » colonne contenant les noms des lignes et pouvoir les utiliser ensuite comme n’importe quelle autre colonne :
          setDT(df, keep.rownames = « nouvelle_colonne »)
          df= le nom de ton dataset
          nouvelle_colonne = le nom que tu veux donner à ta nouvelle colonne
          Ou alors tu peux créer directement une nouvelle colonne de cette manière :
          df$nouvelle_colonne<- rownames(df)

          1. Merci beaucoup pour ta réponse, tu m’as à nouveau permis d’avancer. J’ai utilisé la 2ème solution et mon problème est réglé, j’ai pu aller jusqu’au bout !
            Je lis avec grand intérêt tes différents articles qui sont pédagogiques et explicites.
            Merci encore de nous faire partager tes connaissances.
            Bien cordialement

  4. Bonjour,

    Pour la méthode mixte je ne vois pas comment on détermine ensuite les nouveaux centroïdes en faisant le centre de gravité des anciens centroïdes selon leur label dans le CAH ?

    J’ai fait ça :

    #KMEANS
    clf=KMeans(n_clusters=50)
    clf.fit(sv_data_scaled)
    labels = clf.labels_
    centroids = clf.cluster_centers_

    #Dendrogramme des centres de gravité
    plt.figure(figsize=(40, 15))

    from scipy.cluster.hierarchy import linkage,dendrogram

    Z = linkage(centroids, method = ‘ward’, metric = ‘euclidean’)

    dendrogram(Z, leaf_rotation = 90., color_threshold = 0);

    #CAH
    clf_2= AgglomerativeClustering(n_clusters = 3)
    clf_2.fit(centroids)

    clf_2.labels_

    et ensuite il me faudrait déterminer les nouveaux centroïdes en faisant le centre de gravité des anciens centroïdes (la partie ou je bloque) puis appliquer un K-Means (sur ces centres de gravité via l’argument init) avec le nb de cluster déterminé grâce au dendrogramme (ici K=3)

    Merci,

    1. Bonjour,

      Je ne suis pas sure de bien comprendre…
      Vous faites d’abord un k-means avec un nombre important de groupes (50 dans votre exemple) et vous calculez les centres de chaque groupe.
      Ensuite vous réalisez une CAH en utilisant les centres des groupes calculés par le k-means (au lieu de prendre les données initiales). Le résultat donné par la CAH est le résultat final, il n’est pas nécessaire de recalculer un autre k-means par la suite.

      Ensuite pour avoir les résultats au niveau des individus il faut refaire une jointure entre les résultats de la CAH et les résultats du k-means en utilisant les centres des groupes comme clé de jointure.

      Est ce que vous vous posez cette question par rapport au choix du nombre de groupes ?

    2. Ahmed ROUISSI

      Bonjour;
      Vous avez pas une idée comment faire les deux points qui restent :
      -déterminer les nouveaux centroïdes en faisant le centre de gravité des anciens centroïdes
      -appliquer un K-Means (sur ces centres de gravité via l’argument init)

      Je suis aussi bloqué a ce niveau.

      1. Bonjour Ahmed,

        Il faut calculer les centroïdes des clusters obtenus à partir du k-means. Par exemple avec Python on peut utiliser cluster_centers_
        Ensuite on fait une CAH en utilisant comme individus les centroïdes des clusters créés par le k-means.

        1. Bonjour Marie-Jeanne,

          Les questions ci dessus sont en fait issues d’un examen d’une formation de Data Analyst, examen qui n’est pas très compréhensible. En cherchant des réponses je suis moi-même arrivé ici…

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *