TD3: Classification hiérarchique ascendante

Table des matières

woman_soccer_bet.png

Figure 1 : A woman datascientist performing machine learning to bet on soccer teams, manga style (générée par DALL-E)

woman_soccer_bet_2.png

Figure 2 : A woman datascientist performing machine learning to bet on soccer teams, manga style (générée par MidJourney)

Introduction

Dans ce dernier TD, nous mettrons en pratique la méthode de classification ascendante hiérarchique (CAH) sur différents jeux de données afin d'en évaluer les propriétés.

Ce TD aura également pour objectif de comparer les approches de classification non supervisées vues en cours dans le cadre d'applications pratiques.

Enfin, une activité de programmation de distances entre classes est proposée afin de monter en compétence sur le langage Python.

Modules Python utilisés dans ce TD

Dans ce TD, nous utiliserons les modules Python suivants :

  • pandas, pour la manipulation des données ;
  • plotly, pour les représentations graphiques ;
  • numpy, pour utiliser des fonctions de calculs numériques "bas niveau", e.g. génération de nombres aléatoires ;
  • scipy, pour utiliser d'autres fonctions de calculs numériques plus "haut niveau", e.g. calcul de distances ;
  • sklearn, pour les algorithmes de machine learning (k-Means, mélange gaussien, ou autres).

Ces modules ne sont pas forcément installés dans votre environnement local ou distant. Vous pouvez donc utiliser la commande !pip install <nom_module> pour les installer : 

#!pip install pandas
#!pip install plotly
#!pip install scipy
#!pip install scikit-learn

Rappel : code d'import des modules : 

for k in range(2, 9):
    km = skc.KMeans(n_init=1, random_state=56000, n_clusters=k)
    km.fit(data_df)
    IB = IT - km.inertia_
    print(k, IB)

import pandas as pd                   # Manipulation des données
import numpy as np                    # Calcul numérique
import plotly as pl                   # Librairie principale pour avoir le n° de version
import plotly.express as px           # Package plotly pour utiliser les visualisations de haut niveau
import plotly.figure_factory as pff   # Package plotly pour utiliser d'autres visualisations de haut niveau plus exotiques (e.g. dendrogramme)
import plotly.io as pio               # Nécessaire avec Spyder
pio.renderers.default = 'browser'     # Nécessaire avec Spyder
import sklearn as sk                  # Librairie principale pour avoir le n° de version
import sklearn.cluster as skc         # Package sklearn dédié au clustering
import scipy as sc                    # Librairie principale de calcul numérique avancée
import scipy.cluster.hierarchy as sch # Package scipy dédié au clustering hiérarchique
import scipy.spatial.distance as scd  # Package scipy dédié au clacul de distance

# Vérification des versions des librairies utilisées
{"plotly": pl.__version__, 
 "pandas": pd.__version__, 
 "numpy": np.__version__,
 "sklearn": sk.__version__,
 "scipy": sc.__version__}

Exercice 1 : CAH et données wine

Dans cet exercice, nous reprenons les données wine afin d'y appliquer différentes CAH dans le but d'identifier des profils de vignobles.

Chargement des données

  1. Chargez les données Wine dans un DataFrame nommé wine_ori_df (ori pour originales). 

    wine_path = "https://roland-donat.github.io/cours-class-non-sup/td/td1/wine.csv"
wine_ori_df = pd.read_csv(wine_path, sep=",")

  2. Centrer et réduire les données afin d'obtenir un nouveau DataFrame wine_cr_df (cr pour centré-réduit). 

    wine_cr_df = (wine_ori_df - wine_ori_df.mean())/wine_ori_df.std()

CAH avec paramètres par défaut

Nous allons utiliser l'algorithme CAH afin de construire une hiérarchie sur nos vins à partir de leurs caractéristiques physico-chimiques. Pour ce faire, le package sklearn.cluster (ou skc pour nous) de la librairie sklearn propose une implémentation de l'algorithme CAH dans la classe skc.AgglomerativeClustering.

  1. Construire un modèle CAH avec la classe skc.AgglomerativeClustering en utilisant les paramètres par défaut. 

    cah_cr_def = skc.AgglomerativeClustering()

  2. Utiliser ensuite la méthode fit pour construire la hiérarchie sur les données wine_cr_df : 

    cah_cr_def.fit(wine_cr_df)

  3. Explorer l'objet cah_cr_def et déterminer la signification des attributs suivants : 

    cah_cr_def.n_clusters_

    cah_cr_def.labels_

    cah_cr_def.n_leaves_

  4. Décrire les profils obtenus avec la partition du modèle cah_cr_def (diagramme en paires, boxplot, profils statistiques détaillés). 

    px.scatter_matrix(wine_ori_df,
                  color=cah_cr_def.labels_.astype(str), 
                  title="Partition cah_cr_def").show()
px.box(wine_ori_df, color=cah_cr_def.labels_.astype(str),
       title="Profils des groupes obtenus par la classification cah_cr_def").show()
cah_def_ori_prof = \
    wine_ori_df.groupby(cah_cr_def.labels_).describe()
  5. Que peut-on dire du comportement par défaut de la classe skc.AgglomerativeClustering en termes, de partitionnement réalisé, de distance entre individus et entre groupes utilisée ?

  6. Calculer l'inertie expliquée par la partition cah_cr_def. Aide : Utiliser la fonction eval_partition du TD2. 

    def eval_partition(data_df, partition):
    """
    Entrées :
    - data_df (pandas.DataFrame) : Données quantitatives
    - partition (list, numpy.array ou pandas.Series) : partition des données
    Sortie :
    - inertie_intra : inertie intra-classe de la partition
    - inertie_score : Inertie expliquée par la partition entre 0 et 1
    """

    # Calcul de l'inertie totale des données (cf. TD1)
    mu_data = data_df.mean()
    d2_data_mu = ((data_df - mu_data)**2).sum(axis=1)
    inertie_totale = d2_data_mu.sum()

    # Calcul de l'inertie interne aux classes (cf. TD1)
    inertie_intra = 0
    for cls, data_cls_df in data_df.groupby(partition):
        # Centre de gravité de la classe cls
        mu_cls = data_cls_df.mean()
        # Distances au carré entre les données de la classe et le centre de la classe
        d2_data_cls = ((data_cls_df - mu_cls)**2).sum(axis=1)
        # Sommation pour obtenir l'inertie interne à la classe
        inertie_intra += d2_data_cls.sum()
  
    # Inertie expliquée par la partition
    inertie_score = 1 - inertie_intra/inertie_totale

    return inertie_intra, inertie_score

cah_cr_def_iw, cah_cr_def_ie = eval_partition(wine_cr_df, cah_cr_def.labels_)
  7. Étudier l'aide de la classe AgglomerativeClustering afin de comprendre le rôle des principaux paramètres de la classe, à savoir n_clusters, metric et linkage.

  8. Construire une nouvelle hiérarchie cah_cr_ward sur les données wine_cr_df afin de produire une partition en 3 groupes en utilisant la distance de Ward. 

    # SOLUTION
# --------
cah_cr_ward = skc.AgglomerativeClustering(
    n_clusters=3,
    linkage="ward").fit(wine_cr_df)

  9. Décrire les profils obtenus avec la partition du modèle cah_cr_ward (diagramme en paires, boxplot, profils statistiques détaillés). 

    # SOLUTION
# --------
px.scatter_matrix(wine_ori_df,
                  color=cah_cr_ward.labels_.astype(str), 
                  title="Partition cah_cr_ward").show()
px.box(wine_ori_df, color=cah_cr_ward.labels_.astype(str),
       title="Profils des groupes obtenus par la classification cah_cr_ward").show()
cah_ward_ori_prof = \
    wine_ori_df.groupby(cah_cr_ward.labels_).describe()

  10. Construire le dendrogramme de la CAH sur les données wine_cr_df réalisée en utilisant la distance de Ward. Pour ce faire, utiliser la fonction create_dendrogram du package plotly.figure_factory (ou plf pour nous). 

    cah_cr_ward_dendro_fig = \
    pff.create_dendrogram(wine_cr_df,
                          labels=wine_cr_df.index,
                          color_threshold=26,
                          linkagefun=lambda x: sch.linkage(x, "ward"))

cah_cr_ward_dendro_fig.update_layout(
    title_text="CAH avec distance d'aggrégation Ward et distance entre individus euclidienne",
    width=1600, height=900)

cah_cr_ward_dendro_fig.show()

Influence de la distance entre groupe

Dans cette section, nous allons observer l'influence de la distance entre groupe dans le processus de construction de la CAH.

  1. Construire une CAH cah_cr_single sur les données wine_cr afin de produire une partition en 3 groupes en utilisant la distance du lien minimum (single link). 

    cah_cr_single = skc.AgglomerativeClustering(
    n_clusters=3,
    linkage="single").fit(wine_cr_df)

  2. Calculer l'inertie expliquée par la partition cah_cr_single. 

    # SOLUTION
# --------
cah_cr_single_iw, cah_cr_single_ie = eval_partition(wine_cr_df, cah_cr_single.labels_)

  3. Décrire les profils obtenus avec la partition du modèle cah_cr_single (diagramme en paires, boxplot, profils statistiques détaillés). 

    # SOLUTION
# --------
px.scatter_matrix(wine_ori_df,
                  color=cah_cr_single.labels_.astype(str), 
                  title="Partition cah_cr_single").show()
px.box(wine_ori_df, color=cah_cr_single.labels_.astype(str),
       title="Profils des groupes obtenus par la classification cah_cr_single").show()
cah_single_ori_prof = \
    wine_ori_df.groupby(cah_cr_single.labels_).describe()

  4. Construire le dendrogramme de la CAH sur les données wine_cr_df réalisée en utilisant la distance du lien minimum. 

    # SOLUTION
# --------
cah_cr_single_dendro_fig = \
    pff.create_dendrogram(wine_cr_df,
                          labels=wine_cr_df.index,
                          color_threshold=3,
                          linkagefun=lambda x: sch.linkage(x, "single"))

cah_cr_single_dendro_fig.update_layout(
    title_text="CAH avec distance d'aggrégation du lien minimum",
    width=1600, height=900)
cah_cr_single_dendro_fig.show()
  5. Interpréter les résultats obtenus.

  6. Faire une CAH sur les données wine_cr_df en réalisant les mêmes analyses que précédemment mais en utilisant la distance du lien maximum (complete link). Le modèle CAH sera nommé cah_cr_complete. Comparer les résultats obtenus avec les CAH précédentes. 

    # SOLUTION
# --------
cah_cr_complete = skc.AgglomerativeClustering(
    n_clusters=3,
    linkage="complete").fit(wine_cr_df)
cah_cr_complete_iw, cah_cr_complete_ie = eval_partition(wine_cr_df, cah_cr_complete.labels_)

px.scatter_matrix(wine_ori_df,
                  color=cah_cr_complete.labels_.astype(str), 
                  title="Partition cah_cr_complete")
px.box(wine_ori_df, color=cah_cr_complete.labels_.astype(str),
       title="Profils des groupes obtenus par la classification cah_cr_complete").show()
cah_complete_ori_prof = \
    wine_ori_df.groupby(cah_cr_complete.labels_).describe()

cah_cr_complete_dendro_fig = \
    pff.create_dendrogram(wine_cr_df,
                          labels=wine_cr_df.index,
                          color_threshold=15,
                          linkagefun=lambda x: sch.linkage(x, "complete"))

cah_cr_complete_dendro_fig.update_layout(
    title_text="CAH avec distance d'aggrégation du lien maximum",
    width=1600, height=900)

  7. Faire une CAH sur les données wine_cr_df en réalisant les mêmes analyses que précédemment mais en utilisant la distance du lien moyen (average link). Le modèle CAH sera nommé cah_cr_average. Comparer les résultats obtenus avec les CAH précédentes. 

    # SOLUTION
# --------
cah_cr_average = skc.AgglomerativeClustering(
    n_clusters=3,
    linkage="average").fit(wine_cr_df)
cah_cr_average_iw, cah_cr_average_ie = eval_partition(wine_cr_df, cah_cr_average.labels_)
px.scatter_matrix(wine_cr_df,
                  color=cah_cr_average.labels_.astype(str), 
                  title="Partition cah_cr_average")

px.box(wine_cr_df, color=cah_cr_average.labels_.astype(str),
       title="Profils de la partition cah_cr_average")


cah_cr_average_dendro_fig = \
    pff.create_dendrogram(wine_cr_df,
                          labels=wine_cr_df.index,
                          color_threshold=15,
                          linkagefun=lambda x: sch.linkage(x, "average"))

cah_cr_average_dendro_fig.update_layout(
    title_text="CAH avec distance d'aggrégation du lien moyen",
    width=1600, height=900)

Exercice 2 : Analyse de profils d'équipes de football

Dans cet exercice, nous allons travailler sur des données historiques de matchs de football. Les données couvrent les deux premières divisions de différents championnats européens.

Le Tableau 1 donne une description des variables du jeu de données.

Tableau 1 : Définition des variables des du jeu de données.
Colonne Description
league_id Identifiant du championnat
season_id Identifiant de la saison
Date Date du match au format %Y-%m-%d
HomeTeam Équipe à domicile (ED)
AwayTeam Équipe à l'exterieur (EE)
FTHG Nombre de buts de l'ED à la fin du match
FTAG Nombre de buts de l'EE à la fin du match
FTR Résultat à la fin du match (H = ED gagne, D = match nul, A = EE gagne)
HTHG Nombre de buts de l'ED à la mi-temps
HTAG Nombre de buts de l'EE à la mi-temps
HTR Résultat à la mi-temps (H = ED gagne, D = match nul, A = EE gagne)
HS Nombre de tirs tentés par l'ED
AS Nombre de tirs tentés par l'EE
HST Nombre de tirs cadrés par l'ED
AST Nombre de tirs cadrés par l'EE
HC Nombre de corners pour l'ED
AC Nombre de corners pour l'EE
HF Nombre de fautes commises par l'ED
AF Nombre de fautes commises par l'EE
HY Nombre de cartons jaunes reçus par l'ED
AY Nombre de cartons jaunes reçus par l'EE
HR Nombre de cartons rouges reçus par l'ED
AR Nombre de cartons rouges reçus par l'EE

L'objectif est d'identifier des profils d'équipes à partir des méthodes de classification non supervisées vues en cours.

Préparation des données

  1. Charger les données à partir de l'adresse suivante : https://roland-donat.github.io/cours-class-non-sup/td/td3/data_soccer_fixtures.csv. Le séparateur est ";". 

    soccer_path = "https://roland-donat.github.io/cours-class-non-sup/td/td3/data_soccer_fixtures.csv"
soccer_df = pd.read_csv(soccer_path, sep=";")
soccer_df.head()

  2. Faire une extraction des données de la division 1 française (league_id = fra_l1) sur la saison 2018-2019. 

    idx_selection = (soccer_df["league_id"] == "fra_l1") & (soccer_df["season_id"] == "2018-2019")
soccer_sel_df = soccer_df.loc[idx_selection]
soccer_sel_df.head()

  3. Sélectionner les données des équipes à domicile, i.e. ['HomeTeam', 'FTHG', 'HTHG', 'HS', 'HST', 'HC', 'HF', 'HY', 'HR']. 

    col_selection = ['HomeTeam', 'FTHG', 'HTHG', 'HS', 'HST', 'HC', 'HF', 'HY', 'HR']
soccer_sel_df = soccer_sel_df[col_selection]
soccer_sel_df.head()

  4. Regrouper les données par équipe et calculer la moyenne des faits de jeu par équipe. 

    soccer_mean_df = soccer_sel_df.groupby("HomeTeam").mean()
soccer_mean_df

Détection de profils

  1. Réaliser une CAH sur les données soccer_mean_df avec la distance de Ward afin de partitionner les équipes en 4 groupes. Essayer d'interpréter les groupes obtenus. 

    # SOLUTION
# --------
cah_soccer_ward = skc.AgglomerativeClustering(
    n_clusters=4,
    linkage="ward").fit(soccer_mean_df)
cah_soccer_ward_iw, cah_soccer_ward_ie = eval_partition(soccer_mean_df, cah_soccer_ward.labels_)

var_num = ['FTHG', 'HTHG', 'HS', 'HST', 'HC', 'HF', 'HY', 'HR']
px.scatter_matrix(soccer_mean_df,
                  dimensions=var_num,
                  hover_name=soccer_mean_df.index,
                  color=cah_soccer_ward.labels_.astype(str), 
                  title="Partition en 4 groupes des équipes de football obtenue par CAH.").show()
px.box(soccer_mean_df[var_num], color=cah_soccer_ward.labels_.astype(str),
       title="Profils des groupes obtenus par la classification cah_soccer_ward").show()
cah_soccer_ward_prof = \
    soccer_mean_df.groupby(cah_soccer_ward.labels_)[var_num].describe()

cah_soccer_ward_dendro_fig = \
    pff.create_dendrogram(soccer_mean_df,
                          labels=soccer_mean_df.index,
                          color_threshold=6,
                          linkagefun=lambda x: sch.linkage(x, "ward"))

cah_soccer_ward_dendro_fig.update_layout(
    title_text="Dendrogramme de la CAH sur les équipes de football avec la distance de Ward",
    width=1600, height=900)
cah_soccer_ward_dendro_fig.show()

  2. Appliquer la méthode du coude afin d'évaluer un compromis entre nombre de classes et inertie expliquée. 

    # SOLUTION
# --------
cah_soccer_ie = []

link_dist = "ward"

K_list = range(2, 10)
for k in K_list:

    cah_soccer_k = skc.AgglomerativeClustering(
        n_clusters=k,
        linkage=link_dist).fit(soccer_mean_df)
    iintra, iscore = eval_partition(soccer_mean_df, cah_soccer_k.labels_)
    cah_soccer_ie.append(iscore)

px.line(x=K_list, y=cah_soccer_ie,
        title="CAH : Inertie expliquée vs nb de classes",
        markers=True)

  3. Refaire les traitements précédents en utilisant la méthode des moyennes mobiles. Comparer les résultats obtenus. 

    # SOLUTION
# --------
km_soccer = skc.KMeans(
    n_clusters=4,
    n_init="auto").fit(soccer_mean_df)
km_soccer_iw, km_soccer_ie = eval_partition(soccer_mean_df, km_soccer.labels_)

var_num = ['FTHG', 'HTHG', 'HS', 'HST', 'HC', 'HF', 'HY', 'HR']
px.scatter_matrix(soccer_mean_df,
                  dimensions=var_num,
                  hover_name=soccer_mean_df.index,
                  color=cah_soccer_ward.labels_.astype(str),
                  title="Partition en 4 groupes des équipes de football obtenue par moyenne mobile.")

px.box(soccer_mean_df[var_num], color=km_soccer.labels_.astype(str),
       title="Profils des groupes obtenus par la classification km_soccer").show()
km_soccer_ward_prof = \
    soccer_mean_df.groupby(km_soccer.labels_)[var_num].describe()

    # SOLUTION
# --------
km_soccer_ie = []

K_list = range(2, 10)
for k in K_list:

    km_soccer_k = skc.KMeans(
        n_clusters=k,
        n_init="auto").fit(soccer_mean_df)
    iintra, iscore = eval_partition(soccer_mean_df, km_soccer_k.labels_)
    km_soccer_ie.append(iscore)

px.line(x=K_list, y=km_soccer_ie,
        title="KM : Inertie expliquée vs nb de classes",
        markers=True)

Exercice 3 : Programmation des distances entre classes

Cet exercice a pour objectif de vous faire programmer les différentes distances entre classes vues en cours. Vous développerez ainsi des fonctions ayant la forme suivante : 

def calcul_<nom distance>(data_df1, data_df2):
    
    # Votre code à mettre ici

    return dist

Remarques :

  • <nom_distance> est à remplacer par le nom de la distance programmée.
  • data_df1 et data_df2 sont deux DataFrame contenant les individus de deux classes disjointes.
  • La fonction retourne la valeur de la distance calculée.
  • Vous supposerez que la distance entre individus est la distance euclidienne.

Le travail consiste alors à créer les quatre fonctions suivantes :

  1. calcul_single qui calcule la distance du lien minimum.
  2. calcul_complete qui calcule la distance du lien maximum.
  3. calcul_average qui calcule la distance moyenne.
  4. calcul_ward qui calcule la distance de Ward.

Aide : vous pouvez utiliser la fonction cdist du package scipy.spatial.distance. 

# SOLUTION
# --------
import scipy.spatial.distance as scd  # Package scipy dédié au clacul de distance

# Distance du lien minimum
def calcul_single(data_df1, data_df2):
    """Calcul du lien minimum (single in english)

    data_df1 : DataFrame contenant les données du premier groupe
    data_df2 : DataFrame contenant les données du second groupe

    Résultat : Distance du lien minimum
    """
    # scd.cdist calcule les distances entre chaque pair d'individus des groupes 1 et 2
    data_dist = scd.cdist(data_df1, data_df2)
    # Transformation en DataFrame pour avoir une jolie matrice de distance entre individus
    dist_mat_df = pd.DataFrame(data_dist,
                               index=data_df1.index,
                               columns=data_df2.index)

    # Conversion en vecteur pour préparer le calcul de la valeur min
    dist_s = dist_mat_df.stack()
    # Recherche de l'indice (pair d'individus) qui correspond à la distance min 
    # entre individus des deux groupes
    idx_min = dist_s.idxmin()
    # Retour de la distance min
    return dist_s.loc[idx_min]

# Distance de Ward
def calcul_ward(data_df1, data_df2):
    """Calcul de la distance de Ward

    data_df1 : DataFrame contenant les données du premier groupe
    data_df2 : DataFrame contenant les données du second groupe

    Résultat : Distance de Ward
    """

    mu_df1 = data_df1.mean()    
    mu_df2 = data_df2.mean()    
    d2 = ((mu_df1 - mu_df2)**2).sum()
    n1 = len(data_df1) 
    n2 = len(data_df2) 
    dist = (n1*n2/(n1 + n2))*d2
    return dist

Données de test : 

data_dict = {'life_expec': {'France': 81.4,
  'Mozambique': 54.5,
  'Guatemala': 71.3,
  'Brazil': 74.2,
  'Japan': 82.8,
  'Argentina': 75.8,
  'Senegal': 64.0},
 'total_fer': {'France': 2.03,
  'Mozambique': 5.56,
  'Guatemala': 3.38,
  'Brazil': 1.8,
  'Japan': 1.39,
  'Argentina': 2.37,
  'Senegal': 5.06}}
data_df = pd.DataFrame(data_dict)
data_df.head()


ds = calcul_single(data_df.loc[["France", "Japan"]], data_df.loc[["Mozambique"]])
print(f"distance single : {ds}") # => 27.130626605369812

# On retrouve le résultat de la slide 25/39 du cours sur la CAH
dw = calcul_ward(data_df.loc[["France", "Japan"]], data_df.loc[["Mozambique"]])
print(f"distance ward : {dw}") # => 517.7216666666664


dc = calcul_complete(data_df.loc[["France", "Japan"]], data_df.loc[["Mozambique"]])
print(f"distance complete : {dc}") # => 28.60557463152943

da = calcul_average(data_df.loc[["France", "Japan"]], data_df.loc[["Mozambique"]])
print(f"distance average : {da}") # => 27.86810061844962