“ Tout le monde peut calculer un K-Means, est-ce pour autant que l’on maîtrise l’art subtil du clustering? “

Nous présentons ici un article thématique sur le clustering (ou segmentation). Parce que son approche est intuitive et visuelle, le clustering est très souvent présenté en premier dans un cursus de formation ou sensibilisation à la data science.
Mais au-delà de son apparente simplicité se cachent de nombreuses subtilités que nous voulons partager avec vous.”

La définition du clustering (ou segmentation) en 10 secondes ?

Le clustering (appelé classification non supervisée, segmentation ou partitionnement) a pour objectif de séparer un ensemble d’observations en groupes homogènes. Il est attendu d’un clustering de générer des groupes où les observations appartenant au même groupe sont plus similaires que les observations appartenant à des groupes différents.

Pour quelles raisons fait-on du clustering ?

Le plus souvent, un clustering est effectué dans la phase exploratoire d’une analyse de données.

Son objectif initial est de décrire les données à partir des groupes qui les constituent. On cherche ainsi à faire émerger des groupes qui ont une signification, ex: les clientes préférant un type de produit, les groupes virulents, les mauvais payeurs, etc). Ces méthodes de classification automatique peuvent traiter une quantité importante de données qu’on ne peut analyser manuellement. Une analyse manuelle peut être effectuée sur les résultats de clusterings pour en sélectionner un groupe, en combiner plusieurs, ou y apporter des modifications.

Un clustering peut également servir à réduire la taille d’un jeu de données.

Dans un contexte de très grande volumétrie de données, il est souvent judicieux de séparer le jeu de données en groupes, pour ensuite effectuer des analyses plus poussées et des visualisations. Il est possible de mettre en évidence un sous-ensemble de ces groupes.

Des analyses par cluster sont ensuite réalisées pour comprendre les usages et comportements dans chaque groupe. Une analyse différenciée pour chacun de ces groupes permet de mettre en évidence leurs caractéristiques : groupe qui adopte les nouveautés, groupe traditionnel, groupe à haut risque de churn etc…

petit apparté Ordre de Grandeurs

Pour une tâche classique comme la détection de K plus proches voisins, qui est d’une complexité de O(n^2), un clustering peut être effectué en amont regroupant les éléments les plus similaires dans des paniers. Souvent, le clustering effectué ne dépasse pas O(n.log(n)) ou peut même être linéaire (ex: propagation de labels). Les K-plus proches voisins peuvent ensuite être détectés dans chaque cluster réduisant quadratiquement le temps d’exécution. Si la taille maximale d’un cluster est dans l’ordre de √n, le calcul des K-plus proches voisins peut devenir une tâche exécutée en O(n) au lieu de O(n^2), rendant cette tâche possible même dans le cadre d’un grand volume de données.

Une segmentation peut également aider à une indexation intelligente des données.

En effet, certains groupes constituant les données peuvent être sollicités par des clients différents pour des besoins spécifiques. Un clustering peut faciliter le stockage et le requêtage des données en plaçant des sous-groupes dans des bases de données différentes. On peut, par exemple, créer autant de moteurs de recherche que de familles d’articles réunies (crawlées) : Sport, finance, Mode… en évitant les mélanges de champs sémantiques.

Le clustering est également utilisé comme un prétraitement dans une tâche de régression ou de pattern mining.

Les données contenant des groupes sont souvent non-équilibrées vis-à-vis du nombre d’observations par groupe. Ainsi, dans une tâche de régression, on choisira d’effectuer une régression pour chaque groupe. Cela est encore plus évident pour le pattern mining, où le nombre de patterns peut grimper exponentiellement avec la taille des données. Un groupe majoritaire dans un jeu de données peut générer la majorité des patterns réduisant ainsi sa capacité de description.

Avant de se lancer, deux points à bien prendre en considération :

1. Le clustering est souvent décrit en opposition à la classification.

Un des premiers aspects qui résonne quand on évoque le clustering est sa nature non supervisée. L’idée est de pouvoir apprendre la structure des données uniquement à partir de la distribution de celles-ci, sans connaissance a priori des groupes, par opposition à la classification qui accepte des exemples de groupes en entrée.

Il est souvent difficile de décrire à l’avance les groupes qui forment une base de données client à cause de l’hétérogénéité de leurs comportements, ni même de connaître le nombre de groupes dans cette base.

2. Un deuxième aspect important du clustering résulte de son appartenance au domaine de l’apprentissage automatique. Les enseignements proviennent directement des données, très partiellement d’une connaissance métier préexistante.

Ces deux aspects régissent la majorité des méthodes de clustering. Ils doivent néanmoins rejoindre une attente exprimée par les décideurs métiers : la nécessité d’injection de connaissance, voire même de génération de clusters acceptables.

Voici deux exemples qui illustrent que l’algorithme peut dégager des clusters selon des critères qui ne satisfont pas l’attente métier.

Exemple #1 : La demande de clustering où le métier attend qu’au moins un des clusters soit composé d’observations dans le littoral atlantique en france (parce qu’on veut réaliser des ciblages géographiques). Or un clustering effectué avec un algorithme classique qui n’apprend que des données, peut partitionner ces derniers sur d’autres dimensions que leur position géographique.

Exemple #2 : Clustering de données sociales (ex: Twitter) qui a pour objectif de faire ressortir des groupes selon les thèmes qui les intéressent, mais qui génère des clusters géographiques (On interagit souvent avec des personnes à faible proximité géographique).

Répondre à la problématique Métier, Quelle est la bonne démarche ?

Afin de prendre en compte les besoins métiers, il faut effectuer plusieurs étapes en amont et en aval d’un clustering :

1.

Recueillir la vision du métier sur ce que constituerait un bon clustering. Alors que l’objectif d’un clustering n’est pas de présenter aux représentants du métier ce qu’ils connaissent déjà, un échange avec ces derniers facilite la génération et la validation d’un ‘bon’ clustering.

2.

Nettoyer et sélectionner les données à segmenter. Plusieurs algorithmes de clustering sont sensibles aux outliers (ex K-Means) et la majorité d’entre eux ne tolère pas de données manquantes. Il faut sélectionner les dimensions qui semblent pertinentes en se reposant sur la première étape.

3.

Normaliser les données. Plusieurs méthodes de clustering utilisent des distances Euclidiennes, Manhattan ou autres qui sont sensibles à l’échelle des données.

4.

(Optionnel) Réduire les dimensions. En particulier lorsque l’on est en présence de dimensions corrélées, qui réduisent la qualité du clustering, il peut être judicieux d’effectuer une réduction de dimensionnalité.

5.

Sélectionner l’algorithme de clustering. Les algorithmes de clustering ont été développés avec des conceptions différentes de ce qu’est un cluster. Il faut d’abord s’assurer que la conception d’un cluster par l’algorithme sélectionné est compatible avec la vision du client. Le client peut rechercher des clusters définis par un sous ensemble d’attributs plutôt que par ‘un peu de chacun des attributs présents’

Exemple : nous voulons segmenter les clients par rapport à leurs appétence pour des produits (achetés, consultés,…). Dans ce cas, si l’on utilise un algorithme qui a tendance à utiliser tous les prédicteurs à disposition (ici le catalogue de produit) de manière peu discriminante, on sera en difficulté pour bien caractériser chaque cluster. On choisira plutôt un algorithme qui fera émerger des clusters regroupés autour d’une poignée distincte de prédicteurs (produits).

Dans ce cadre là, un clustering de sous-espace (subspace clustering), ou du co-clustering va à la fois générer des groupes de produits achetés souvent ensemble et des clusters constitués à partir de ces groupes. Les clusters seront ainsi définis par les groupes de produits.

6.

Modification de l’algorithme de clustering. Afin d’injecter des connaissances métiers dans un algorithme de clustering, il faut parfois le modifier. Par exemple, il peut être nécessaire de fixer/favoriser des centroïdes si l’algorithme utilisé est un K-means/medoide/medians, ou de fixer/favoriser des groupes d’attributs si on utilise du subspace clustering.

7.

Validation. La discussion avec le client doit mettre en évidence des méthodes de validation de cluster. Les méthodes classiques de validations (ex: Coude/ Davis boulding, Modularité) peuvent ne pas être comprises par le client. On pourra y ajouter des méthodes qui illustrent les données clients impliquées; ex: proximité géographique des utilisateurs par cluster, âge moyen de ce derniers, comportement d’achat, etc..

Quels sont les pièges à éviter ?

erreur #1:

Commencer un clustering sans avoir défini en amont ce que le client considère comme étant un cluster.
Le risque est de créer une partition qui ne soit pas interprétable par le client. Donc inutilisable.

erreur #2:

Effectuer un clustering sans avoir clairement défini les attributs ou dimensions à utiliser. Parmi l’ensemble de données disponibles, souvent un sous-ensemble restreint intéresse le client.

erreur #3:

Le troisième piège est d’effectuer un clustering sans suppression d’anomalies. Les anomalies (outliers) peuvent avoir un effet néfaste sur plusieurs méthodes de clustering, en particulier les méthodes basées sur les distances comme le K Means.

erreur #4:

persister sur du clustering alors que les données sont non “segmentables” : en particulier quand elles correspondent à un continuum.

erreur #5:

Utiliser une distance qui ne correspond pas… : Une distance euclidienne en haute dimension amoindrit les chances de convergence alors qu’une proximité cosinus permettrait de faire ressortir les différences.

erreur #6:

Essayer d’effectuer un clustering global qui comprend la majorité des dimensions qui intéressent le client, alors qu’il est souvent plus judicieux d’effectuer des clustering par famille de dimensions.

Ex: le client veut regrouper des utilisateurs en fonction de leurs fréquence d’achat et du type de produit acheté. Chacune de ces dimensions peut comprendre plusieurs attributs (marge par client, trafic du client, nombre de produits achetés, couleurs des produits, etc.). Il peut être plus pertinent d’effectuer un clustering pour la fréquence d’achat et un second clustering pour le type de produit et ensuite de croiser ces derniers, au lieu d’effectuer un seul clustering global qui peut ne pas être interprétable par le client.

Quels sont les algorithmes ?

Ci-dessous, quelques algorithmes populaires :

K Means :

Algorithme basé sur les distances. Considère qu’un cluster est formé d’un groupe d’éléments ayant une faible distance au centre de masse du cluster comparé à leur distance avec le centre de masse des autres clusters. Cet algorithme est basé sur une heuristique qui peut être piégée dans un optimum local, et nécessite ainsi plusieurs réinitialisations.

K-médoïdes (PAM):

Similaire au k-means, mais utilise des éléments existants comme centre des clusters. Cela augmente légèrement sa robustesse face aux anomalies.

DB Scan :

Clustering basé sur la densité. Sa vision d’une partition est similaire à la partition des animaux dans la taxonomie des groupes biologiques. Ainsi, un mammifère X n’est pas nécessairement proche de tous les mammifères, mais il est très proche d’un ou plusieurs mammifères Y. Similairement pour Y, ces derniers sont proches d’autres mammifères Z et ainsi de suite. Ces proximités permettent de former une chaîne ou un cycle qui définissent un cluster. Néanmoins, l’algorithme DB-SCAN nécessite des paramètres qui ne sont pas intuitifs à sélectionner.

OPTICS :

Similaire à DBScan, mais ne nécessite qu’un paramètre de voisinage. Il sélectionne le second paramètre de DBSCAN qui est un paramètre de distance en utilisant les K-plus proches voisins des éléments à clusteriser.

CLIQUE :

Méthode de clustering de sous-espaces. Cette méthode basée sur l’optimisation de l’entropie permet à la fois de générer des clusters et des sous-espaces qui permettent de définir ces cluster. Ainsi, cet algorithme est utilisé si les données sont affligées par la malédiction de la haute dimensionnalité, et que les distances entre les éléments sont très similaires.

Comment analyse-t-on les clusters générés ?

Les méthodes de visualisation sont souvent utilisées pour sélectionner le nombre optimal de clusters. Cette pratique a ses limites:

  • On peut souvent identifier un nombre différent de clusters selon la méthode de visualisation utilisée (PCA, TSNE, SOM, etc.)
  • En haute dimension, une projection en 2 ou 3 dimensions peut ne pas être suffisante pour distinguer les clusters, conduisant à une sous-estimation des clusters.
  • La compression de données utilisées pour la visualisation affecte les distances entre les éléments. On en arrive parfois à sous-estimer ou surestimer le nombre de clusters à cause d’une variation de distance liée à la compression.
  • Dans le cadre du subspace clustering, un PCA ou TSNE ne permet pas de détecter un nombre de clusters optimal, étant donné que des membres du même cluster peuvent être très différents, mais similaires sur un petit sous-ensemble d’attributs (ex: groupe science +droit)

Il est souvent plus judicieux d’utiliser des indicateurs comme Davies Boulding ainsi que des indicateurs métiers (proximité, age moyen, etc.).

Des exemples d’application de la vraie vie ?

Voici quelques exemples de clustering appliqués sur des domaines variés :

1. Analyses de groupe de clients selon leurs comportements d’achats

a. L’un des objectifs de ce clustering était de pouvoir décrire des clusters de clients par les produits qui caractérisent leurs achats.

b. Les données étant en haute dimension, un clustering basé sur les distances (ex: K-means) souffre du problème de la malédiction de la dimensionnalité (les distances deviennent similaire). Ce type de clustering peut générer des cluster avec certaines différences statistiques, mais sans qu’on puisses les décrire par un comportement d’achats. L’utilisation d’une compression n’a pas amélioré la qualité des clusters retournés.

c. Nous avons utilisé une méthode de clustering de sous-espace, qui génère des clusters avec des membres similaires dans un sous-espace restreint d’attributs, répondant au problème de haute dimensionnalité.

d. Les clusters générés sont similaires dans un petit sous-espace (vis à vis de leurs achats de certains produits), mais peuvent être très différents dans d’autres dimensions, ce qui est à l’opposé de clusters retournés par un K-means.

e. Le clustering retourné était facile à interpréter, et beaucoup plus utile dans sa capacité à expliquer le comportement des clients.

2. Regrouper par comportements communs des magasins franchisés pour mieux détecter ceux qui vont présenter des difficultés.

3. Regroupement d’articles, de pages web, selon des thématiques similaires.

a. C’est une étape fondatrice pour une chaîne de traitement naturel du langage appliquée à l’analyse des tendances.

b. Cette segmentation nous sert à constituer des corpus mobilisables selon des problématiques ciblées : tendance de mode, analyse de bad buzz,…

4. Regrouper les pièces de rechange automobile par leur courbe de consommation

Pour savoir quand et dans quel volume on doit lancer la production de certaines pièces après la sortie d’un nouveau modèle. il s’agit de regrouper des séries temporelles en les structurant sous forme de features (Cf. Dynamic Time Wrapping)

5. Plus généralement la segmentation pour l’assurance, la banque, la grande distribution où l’on cherche à réunir les comportements similaires pour anticiper les départs, les pulsions d’achat, …

6. Regrouper les retours clients par thématiques (et faire émerger par la suite des classes: question, mécontentement, proposition, …).

Cette étape facilitera le tri de messages avant une réponse humaine spécifique.

Quelques considérations complémentaires :

Est-ce qu’il faut avoir beaucoup de données ?

Pas nécessairement, mais il faut que chaque cluster soit représenté par un nombre significatifs d’exemples. Sinon, les représentants d’un cluster peuvent être considérés comme du bruit.

Est-ce que des données massives posent problèmes ? en convergence… en temps de calcul ?

Oui, les données massives peuvent rendre l’utilisation de plusieurs méthodes de clustering impossible. Aussi, il faut s’assurer que les méthodes de clustering “scalables” sont implémentées en utilisant des structures de données adaptées au big data (ex: sparse matrix, hashsets, etc.)

Comment aborde-t-on la temporalité dans le clustering?

Est-ce qu’on mesure la déformation dans le temps des clusters, ou bien le fait qu’une observation (ex: client) passe d’un cluster à l’autre pour en retirer une information?

Il n’existe pas de compromis sur le clustering intégrant la dimension temporelle, étant donnée la diversité des usages.

Une méthode est de considérer le temps comme une dimension qui s’additionne à la distance. Ainsi, des observations sont regroupées en fonction de leur distance pour chaque fenêtre temporelle. Ces clusters ont pour objectif de représenter des thématiques qui apparaissent et disparaissent dans le temps.

Une autre méthode est de regrouper les individus selon les horaires auxquels ils apparaissent. Facebook a utilisé ce clustering pour détecter des comptes malicieux. L’idée étant que des campagnes de spams peuvent être détectées en regroupant des comptes qui publient des contenus similaires au même moment.

Pour aller plus loin :

 

On vous partage quelques articles et présentations qui dévoilent des aspects techniques avancés :
https://datawookie.netlify.com/blog/2017/04/clustering-time-series-data/
https://www.slideshare.net/salahecom/11-clusadvanced

 

Une belle illustration des algorithmes à connaître, leurs avantages et limites :
https://towardsdatascience.com/the-5-clustering-algorithms-data-scientists-need-to-know-a36d136ef68

 

Un besoin métier à mûrir et explorer par la Data Science, des données à découvrir et à valoriser : contactez-nous @Novagen !