Aperçu de l’état de l’art de la segmentation

 

La segmentation est un exercice répandu, et qui présente un intérêt dans de nombreuses disciplines. Elle peut être appliquée dans des domaines et des secteurs d’activité très divers tels que la santé, l’industrie, les sciences humaines ou dans les directions d’entreprise,  dans les départements marketing ou financier par exemple. Dans cet article,  nous allons nous focaliser sur une méthodologie générique s’accommandant à l’hétérogénéité de la plupart des cas d’utilisation. La première partie sera consacrée à la description du processus et la seconde à son implémentation.

 

Exemple de segmentation de ville Américaines basée sur des données sociaux économique vue interactive ici (graphique élaboré en d3.js)

 

La segmentation est, par définition,  le regroupement et la caractérisation d’observations dans des ensembles homogènes appelés communément « clusters ». Les recherches et travaux sur la question montrent néanmoins que la segmentation reste un exercice difficile : en raison notamment de sa nature qui peut se révéler arbitraire. Il existe une très grande panoplie d’algorithme permettant de séparer et regrouper des observations (classification non supervisée), et le choix de l’un par rapport à un autre n’est pas forcément évident. C’est également le cas du choix des variables à sélectionner, en quoi une variable représente et/ou est pertinente pour répondre au besoin de l’analyse ? Ces interrogations légitimes n’empêchent pas de produire une segmentation de qualité. Il est néanmoins nécessaire d’avoir conscience de ces nombreux biais afin d’exclure toute interprétation ou analyse  erronées.

Dans le cadre d’une première approche, nous allons nous inspirer de la méthodologie proposée par le livre  « Statistique exploratoire multidimensionnelle »  (Dunod, Paris, 1995 ISBN 2100028863).

Elle est effectuée en plusieurs étapes :

  • Réduction de dimension

La réduction de dimension est l’exercice qui consiste à compresser l’information des données de grande dimension, en un nombre de dimension réduite. Il existe différentes méthodes de réduction, chacune d’entre elles présentent des avantages et des inconvénients. L’Analyse en Composante Principale (ACP) est ici la méthode employée. Cet algorithme utilise le paradigme de la corrélation pour réduire en dimensions un dataset. L’utilisation de la corrélation présente l’avantage de rendre l’interprétation des résultats plus aisée et intelligible. Bien que cette méthode soit assez élémentaire, elle est particulièrement recommandée et efficace pour visualiser des données multidimensionnelles, tout en ayant une perte d’informations quantifiable et contrôlée.

  • Classification non-supervisée

Les algorithmes non-supervisés peuvent se baser sur différentes métriques : entropie, distance, densité. L’objectif recherché reste néanmoins toujours le même : Séparer des observations en des ensembles homogènes.

La classification Ascendante Hiérarchique (CAH) ici utilisée, consiste dans un premier temps à affecter une classe par observations et par la suite à regrouper progressivement les classes entre elles selon le critère de dissimilarité choisie. Elle est appliquée directement sur les coordonnées de L’ACP précédemment générées.

Le choix du nombre de clusters

La détermination du nombre optimal de clusters dans un dataset est un problème fondamental pour le clustering. Il n’existe pas de théorie qui résout de manière définitive et absolue cette problématique. Le nombre optimal de clusters garde une part   de subjectivité. En effet l’évaluation des similarités, varie avec plus ou moins d’intensité en fonction de la méthode utilisée. Néanmoins, certaines de ces méthodes sont aujourd’hui consensuellement acceptées et couramment utilisées.

La Méthode d’Elbow est sans doute la méthode la plus utilisée pour la simplicité de son implémentation et pour son caractère accessible.

La technique consiste à exécuter l’algorithme de clustering  plusieurs fois avec une valeur « k » du nombre de clusters différentes à chaque fois {2, 3, 4, etc…}. Pour chaque exécution est calculée l’inertie intra cluster, pour chaque cluster :

 

Représentation de l’inertie inter et intra cluster

 

WWS : Within cluster Sum of Squares – inertie intra cluster
SSB : Sum of Squares Between cluster – inertie inter cluster
d(xi,gi: Distance entre les points xi et les centres de gravité gi

L’objectif étant  de minimiser l’inertie intra cluster (wws), cela revient également à maximiser l’inertie inter cluster (ssb) car inertie total du nuage de point étant la somme Totalinertie = wws + ssb

La valeur k du nombre de clusters à retenir est lorsque  la décroissance de l’inertie  entre deux valeurs  successives de k  se stabilise.

Intérêt d’appliquer la classification non-supervisée sur les résultats de l’ACP.

Il peut paraitre à première vue assez déconcertant d’appliquer la méthode de clustering directement sur les résultats de l’ACP et non sur les données brutes elles-mêmes.  Pourtant cette façon de faire,  possède aussi bien un intérêt pratique que théorique.

La combinaison des analyses procurent une visualisation indisponible. Dans le cas contraire, on peut ainsi avoir une idée des positions relatives des observations et des classes les unes par rapport autre mais également de leur dispersion et de leur silhouette.

Autre avantage, la possibilité de sélectionner un nombre restreint de dimensions générées par l’ACP. Cela afin de prendre en considération uniquement les dimensions qui possèdent un taux de variance expliqué élevées et délaisser les dimensions résiduelles, se préservant ainsi de potentielles fluctuations aléatoires indésirables. En se focalisant sur l’information la plus pertinente, nous améliorons de facto la qualité des partitions.

Du point de vue théorique,  la stabilité des résultats reste garantie du fait que la somme des valeurs propres (inertie totale des dimensions sélectionnées) de L’ACP est égale à la somme des indices de niveau de la classification ascendante hiérarchique CAH (méthode de  Ward).

Cet enchaînement vient également pallier un phénomène  qui a cours en grande dimension : the Curse of Dimensionality (fléau de la dimension). Le concept est développé par Richard Bellman dans les années 60, dont l’idée consiste à dire qu’à nombre d’observations égales, plus on ajoute de dimensions, plus nous générons, et ce de manière exponentielle, du vide dans l’espace multidimensionnel. La manipulation de données en grande dimension rend alors le concept de distance (au sens euclidien du terme) progressivement dénuée de sens. Par conséquent, toute technique de regroupement basée sur la distance peut conduire à des résultats sous-optimaux.

  • Caractérisation des clusters

Etape souvent négligée, dans ce genre d’exercice, la caractérisation des clusters représente pourtant, dans bien des cas, la valeur ajoutée du procédé.

La phase de clusterisation permet de regrouper des individus homogènes entre eux, mais elle n’indique en rien en quoi ces ensembles se ressemblent ou au contraire se distingue.

De nouveau, il existe plusieurs méthodes pour comparer les clusters les uns par rapport aux autres. Les tests statistiques utilisés sont souvent des tests de comparaison de moyennes basées sur des hypothèses de distribution des variables (Student, Normal…)  D’autres utilisent la densité ou en encore des calculs plus sophistiqués.

 

Implémentation

 

Afin d’illustrer ce mécanisme, nous allons nous intéresser à segmenter certaines grandes villes américaines sur plusieurs critères : sociaux, économiques, démographique etc… dans le but de caractériser la notion de  « bien-être » dans ces villes.

La procédure précédemment décrite a été codée en R et en JavaScript « D3.js » pour une meilleure visualisation. Le dataset et le code complet sont disponible ici.

Première etape:

Installation et importation des libraires et chargement des données.

library(FactoMineR)
library(factoextra)
library(ggplot2)
library(ggrepel)
library(DT)
library(jsonlite)

df=read.csv("wellness.csv", sep=";",dec=",",
row.names = 1, header= TRUE,
check.names=FALSE)

 
Deuxième étape:
 
Réduction de dimension avec l’ACP, et visualisation des résultats.

res_acp = PCA(df, scale.unit=TRUE, ncp=ncol(df), graph=F)
df_acp=as.data.frame(res_acp$ind$coord)
fviz_pca(res_acp, col.var ="blue")

Afficher les résulats

 

Cliquez ici pour savoir comment interpréter ces résultats

 
 
Troisième étape:
 
Clusterisation  en utilisant l’algorithme de la  CAH. Elle est effectuée sur les données de l’ACP sur un nombre restreint de dimension tout en ayant precedement calculer le nombre de cluster optimal

alpha= 0.20
opt_calc=fviz_nbclust(df_acp[,c(1,4)], hcut, method = "wss")

for ( i in 1:10){
   
  if(opt_calc$data$y[i+1]/opt_calc$data$y[1]<alpha){
    nb_optimal=i+1
    break
  }
}

fviz_nbclust(df_acp[,c(1,4)], hcut, method = "wss")+geom_vline(xintercept = nb_optimal, linetype = 2)
cluster=cutree(CAH, nb_optimal)
cluster=as.data.frame(cluster)
df_cluster=cbind(df_acp,cluster)
Afficher les résulats

 
 
Quatrième étape:
 
Caractérisation des clusters avec un z-test (suppose que les variables sont  distribuées selon la loi normal)

z.test = function(k, g){
  
  n.k = length(k)
  n.g = length(g)
  Sk=((n.g-n.k)*var(g))/((n.g-1)*n.k)
  zeta = (mean(k) - mean(g)) / sqrt(Sk)
  
  return(zeta)
}

threshold=0.975
threshold.val=qnorm(threshold)

cluster_info <- data.frame(matrix(nrow=ncol(df)))
temp=data.frame()
df_c=cbind(df,cluster) 



for ( j in 1:nrow(unique(cluster))){ 
  cat("\n","cluster ", j, "\n", "\n", "\n" )
  for (i in 1:ncol(df)) {
    statistic=z.test(subset(df_c[,i], cluster==j),df_c[,i]) 
    
    temp=rbind(temp,statistic) 
    
    if (statistic >=threshold.val || statistic <= -threshold.val) {
      
      cat(colnames(df)[i],":",statistic[1],"\n")
      
    } 
    
  }
  colnames(temp)=paste("cluster",toString(j[1]) , sep=" ")  
  cluster_info=cbind(cluster_info,temp)
  temp=data.frame()
  
}

Afficher les résulats
cluster 1 
 
 
% Environmental disease : 2.971881 
Infant mortality rate : 2.332093 
Air pollution index : 1.992268 
Number of theft : 2.574825

cluster 2 
 
 
Per capita income : 2.288678 
Unemployment rate : 3.111431 
Infant mortality rate : -2.092907 
Number of suicides : 2.704074 
Number of road fatalities : 2.496167

cluster 3 
 
 
% Low household income : -2.045789 
Cost of housing per year : 2.021008 
% Environmental disease : -1.979993 
Number of theft : -2.022158

cluster 4 
 
 
% Low household income : 2.336857 
Cost of housing per year : -2.544205
 
 
Dernière étape:
 
Génération du json, pour la visualisation en D3.js

path_json="viz/outfile.json"
 
if (file.exists(path_json)) file.remove(path_json)

cat("{",'"features":',"[",file=path_json,append=TRUE)
for(i in 1:ncol(cluster_info)){
  
  cat('{\n"cluster":','"',i,'",','\n','"vars"',": [",'\n',file=path_json,append=TRUE)
  cluster_info=cluster_info[order(cluster_info[,i],decreasing = TRUE), , drop = FALSE]
  for(z in 1:nrow(cluster_info)){
    
    
    if(abs(cluster_info[z,i])>=threshold.val){
      cat('{','\n','"label" :','"',rownames(cluster_info)[z],'",','\n','"value":',round(cluster_info[z,i],digit=2),'\n }',file=path_json,append=TRUE)
      if(max(which(abs(cluster_info[,i])>=threshold.val))!=z) { cat(",",file=path_json,append=TRUE) }
      cat('\n',file=path_json,append=TRUE)
    }
  }
  
  cat("] \n } ",file=path_json,append=TRUE)
  if(ncol(cluster_info)!=i) { cat(",",file=path_json,append=TRUE) }
  cat("\n"  ,file=path_json,append=TRUE)
}
cat("],",'"observations": [',file=path_json,append=TRUE)
res1=df_cluster[, c(1,2,length(df_cluster))]
res1=cbind(ENTRY=rownames(df_cluster),df_cluster[, c(1,2,length(df_cluster))])
colnames(res1) <- c("name","Dim_1","Dim_2","cluster")
row.names(res1)<- NULL
x <- toJSON(unname(split(res1, 1:nrow(res1))))
x=gsub("[[]", "", x)
x=gsub("[]]", "", x)
cat(x,file=path_json,append=TRUE)
cat("\n ] \n }",file=path_json,append=TRUE)

 

 

L’approche non-linéaire

 

Que cela soit pour l’ACP ou bien la CAH, la compression ou séparation des données est effectuée toujours de la même manière : linéairement. Il existe une autre catégorie d’algorithme qui permet de compresser l’information d’un dataset avec une approche différente.

L’un des plus célèbre, le T-SNE, proposé par  Geoffrey Hinton et Laurens van der Maaten, utilise des métriques issus de la théorie de l’information, en ayant notamment recours à  une vision probabiliste des distances entre les observations. Il est aujourd’hui très utilisé et peut s’avérer salutaire pour distinguer des patterns locaux pouvant être dissimulés par des caractéristiques particulières de densité et de dispersions d’un dataset.

Du fait de son approche non linéaire, l’algorithme ne conserve ni les distances, ni la densité, mais la proximité entre les observations est en revanche maintenu.

Essentiellement élaboré pour des datasets de grande dimension, il reste néanmoins gourmand en temps de calcul et possède un paramètre clé : la perplexité qui nécessite d’être correctement calibré.

Le T-sne est un algorithme non déterministe en le ré exécutant plusieurs fois, il est possible d’avoir des différences sur la silhouette globale ainsi que sur les positions relatives des clusters.

En revanche les observations affectées à un cluster ne changeront pas de manière radicale.

Afin d’illustrer la différence des résultats des réductions de dimension de l’ACP et du  T-SNE. Nous allons appuyer sur un dataset représentant le comportement des clients dans une enseigne de la grande distribution.

Code R comparant les résultats du tnse avec l’acp

data=read.csv2("customers-data.csv",row.names = 1,header = TRUE)
data=data[,1:8]

res.pca = PCA(data, scale.unit=TRUE, ncp=ncol(df), graph=F)
res.tsne=tsne(scale(data),k = 2,max_iter = 500,epoch = 100,perplexity = 60)

km.tsne=kmeans(res.tsne,3)

par(mfrow=c(1,2))
plot(res.tsne,col=km.tsne$cluster,main="tsne")
plot(res.pca$ind$coord[,1:2],main="pca")

L’exécution  de ce code  nous montre comment en fonction de la méthode de réduction de dimension utilisé  les résultats varient. Cela permet dans le cas présent de  détecter des ensembles indiscernables  autrement.

 

Différences de résultats  entre le tsne et l’acp

Conclusion 

La démarche présentée ici, nous montre une méthode pouvant être appliquée dans de nombreuses circonstances. Elle peut être ajuster en fonction des caractéristiques du dataset et présente l’intérêt d’une interprétation facilité par un ensemble d’indicateurs. Cela ne nous épargne pas en revanche, d’une  vigilance particulière, au vu des écueils auxquelles  nous pouvons être confronter dans ce genre d’exercice.

 

Réferences

[1] BellmanReferences, Richard. Dynamic programming. Courier Corporation, 2013.

[2] Benzécri, Jean-Paul. L’analyse des données. Vol. 2. Paris: Dunod, 1973.

[3] Maaten, Laurens van der, and Geoffrey Hinton. « Visualizing data using t-SNE. » Journal of machine learning research 9.Nov (2008): 2579-2605.

 

Laisser un commentaire

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