Qu'est-ce que le partitionnement ?

Il existe de nombreuses façons d’utiliser le partitionnement dans le machine learning, depuis les explorations initiales d’un jeu de données jusqu’au suivi des processus en cours. Vous pouvez l’utiliser dans le cadre d’une analyse exploratoire des données avec un nouveau jeu de données afin de comprendre les tendances sous-jacentes, les modèles et les données aberrantes. Il se peut également que vous disposiez d’un jeu de données plus important qui doit être divisé en plusieurs jeux de données ou réduit à l’aide de la réduction de dimensionnalité. Dans ce cas, le partitionnement peut être une étape du prétraitement.

Les clusters peuvent inclure des genres musicaux, différents groupes d’utilisateurs, des segments clés d’une segmentation de marché, des types de trafic réseau sur un cluster de serveurs, des groupes d’amis dans un réseau social ou de nombreux autres types de catégories. Le processus de clustering peut utiliser une seule caractéristique des données ou toutes les caractéristiques présentes dans les données.

Il est utile de considérer le clustering comme la tentative de trouver des groupements naturels dans les données afin de voir quelles catégories peuvent exister et ce qui définit ces catégories. Les clusters peuvent vous aider à trouver des relations sous-jacentes entre les points de données pour voir quelles fonctionnalités ou caractéristiques sont partagées entre les catégories. En fonction de l’algorithme de clustering utilisé, vous pourrez peut-être supprimer les données aberrantes ou les marquer comme telles. Le clustering peut également aider à détecter les anomalies en identifiant les points de données qui ne sont pas contenus dans un cluster ou qui ne sont que faiblement associés à un cluster et qui peuvent donc constituer une anomalie dans le processus de génération de données.

Le clustering peut également être utilisé pour réduire la complexité des jeux de données volumineux en réduisant le nombre de dimensions des données. Si vous constatez que les catégories ne sont définies que par deux ou trois caractéristiques, vous pouvez supprimer les caractéristiques superflues ou utiliser des techniques de réduction de la dimensionnalité telles que l’ACP. Le clustering est également très utile pour créer des visualisations des jeux de données afin de voir les propriétés émergentes des données ainsi que la densité et les relations entre les clusters.

Les algorithmes de clustering sont parfois distingués selon qu'ils effectuent un clustering dur, où chaque point de données n'appartient qu'à un seul cluster et a une valeur binaire d'appartenance ou de non-appartenance à un cluster, ou qu'ils effectuent un clustering doux où chaque point de données se voit attribuer une probabilité d'appartenance à chaque cluster identifié. Il n'existe pas de processus de clustering unique et optimal. Vous devez choisir l'approche la plus adaptée à vos besoins et aux données sur lesquelles vous travaillez.

Il existe de nombreux algorithmes de clustering et il existe plusieurs façons de définir un cluster. Différentes approches fonctionneront bien pour différents types de modèles en fonction de la taille des données d’entrée, de la dimensionnalité des données, de la rigidité des catégories et du nombre de clusters dans le jeu de données. Il convient de noter qu’un algorithme peut très bien fonctionner pour un jeu de données et très mal fonctionner pour un autre. Cette section aborde cinq des approches de clustering les plus couramment utilisées. Il existe d'autres techniques, telles que le clustering spectral ou le clustering Mean-Shift, qui ne relèvent pas du champ d'application de cet article.

Le clustering basé sur les centroïdes est un type de méthode de clustering qui partitionne ou divise un jeu de données en groupes similaires en fonction de la distance entre leurs centroïdes. Le centroïde de chaque cluster est la moyenne ou la médiane de tous les points du cluster en fonction des données.

L’une des techniques de clustering basées sur les centroïdes les plus couramment utilisées est l’algorithme de clustering k-means. K-means suppose que le centre de chaque cluster définit le cluster à l'aide d'une mesure de distance, généralement la distance euclidienne, au centroïde. Pour initialiser le clustering, vous fournissez un certain nombre de clusters attendus, qui représente le « K » dans K-means, et l'algorithme tente de trouver des clusters raisonnables dans les données pour correspondre à ce nombre. Les k clusters optimaux dans un jeu de données donné sont identifiés en minimisant de manière itérative la distance totale entre chaque point et son centroïde de cluster attribué.

K-means est une méthode de clustering stricte, ce qui signifie que chaque point de données est assigné à un cluster distinct et qu'aucune probabilité n'est associée à l'appartenance à un cluster. La méthode K-means fonctionne bien lorsque les clusters sont de taille à peu près équivalente et qu'il n'y a pas de données aberrantes ou de changements de densité significatifs dans les données. La méthode K-means est souvent peu performante lorsque les données sont de grande dimension ou lorsque les clusters ont des tailles ou des densités sensiblement différentes. Elle est également particulièrement sensible aux données aberrantes car elle essaie d'établir des centroïdes sur la base des valeurs moyennes de toutes les valeurs du cluster et est donc susceptible d'être sur-ajustée pour inclure ces données aberrantes.

Une autre approche basée sur les centroïdes pour les K-moyennes est celle des K-médoïdes. Les médoïdes sont des objets représentatifs d'un jeu de données ou d'un cluster au sein d'un ensemble de données dont la somme des distances par rapport aux autres objets du cluster est minimale. Au lieu d'avoir un centroïde arbitraire comme centre du graphique, l'algorithme crée des clusters en utilisant des points de données individuels comme médoïde ou centre du cluster. Étant donné que l’algorithme K-medoids utilise des points de données existants plutôt que des centroïdes arbitraires, il est moins sensible aux données aberrantes.

Le clustering hiérarchique, parfois appelé clustering basé sur la connectivité, regroupe les points de données en fonction de la proximité et de la connectivité de leurs attributs. Cette méthode détermine les clusters en fonction de la proximité des points de données les uns par rapport aux autres dans toutes les dimensions. L'idée est que les objets les plus proches sont plus étroitement liés que ceux qui sont éloignés les uns des autres. Contrairement à la méthode k-means, il n'est pas nécessaire de spécifier à l'avance le nombre de clusters. Au lieu de cela, l'algorithme de clustering crée un réseau graphique des clusters à chaque niveau hiérarchique. Ce réseau est hiérarchique, ce qui signifie qu'un nœud donné n'a qu'un seul nœud parent mais peut avoir plusieurs nœuds enfants. Les clusters hiérarchiques peuvent être représentés sur un graphique à l'aide d'un dendrogramme pour aider à résumer et à organiser visuellement les clusters découverts et la hiérarchie qu'ils peuvent présenter.

Il existe deux approches pour effectuer une analyse hiérarchique des clusters :

Agglomératif : dans le cas du partitionnement agglomératif, une approche ascendante part de points de données individuels et fusionne successivement les clusters en calculant la matrice de proximité de tous les clusters au niveau actuel de la hiérarchie afin de créer une structure arborescente. Une fois qu’un niveau de clusters a été créé où tous les clusters n’ont pas ou peu de similarité entre eux, l’algorithme passe à l’ensemble des clusters nouvellement créés et répète le processus jusqu’à ce qu’il y ait un nœud racine au sommet du graphe hiérarchique. Différents choix sont possibles quant à la manière dont ces clusters doivent être fusionnés les uns avec les autres, avec des compromis en matière de qualité et d’efficacité du partitionnement. Dans le cas d’une classification par liaison simple, la distance la plus courte entre une paire de points de données dans deux clusters est utilisée comme mesure de similarité. Dans le couplage de toutes les paires, c’est la moyenne de toutes les paires de points de données qui est utilisée, tandis que dans le couplage d’échantillons, un échantillon des points de données dans les deux clusters est utilisé pour calculer la distance moyenne. Dans le cas des liens entre centroïdes, c’est la distance entre les centroïdes qui est utilisée. L’un des défis des méthodes agrégatives est qu’elles peuvent présenter un chaînage, où les clusters plus grands sont naturellement biaisés vers des distances plus proches par rapport à d’autres points et continuent donc de s’agrandir et d’attirer plus de points de données dans leur cluster. Un autre inconvénient est que les méthodes agglomératives peuvent être beaucoup plus lentes que les méthodes de division dans la construction de la hiérarchie.

Divisé : dans les méthodes de partitionnement hiérarchique, une approche descendante partitionne successivement les points de données dans une structure arborescente. La première étape consiste à fractionner le jeu de données en clusters à l’aide d’une méthode de partitionnement plate comme K-means. Les clusters dont la somme des erreurs quadratiques (SSE) est la plus élevée sont ensuite partitionnés davantage à l’aide d’une méthode de partitionnement plat. L’algorithme s’arrête lorsqu’il atteint des nœuds individuels ou un SSE minimum. Le partitionnement divisé permet une plus grande flexibilité en matière de structure hiérarchique de l’arbre et de niveau d’équilibre dans les différents clusters. Il n’est pas nécessaire d’avoir un arbre parfaitement équilibré en matière de profondeur des différents nœuds ou un arbre dans lequel le degré de chaque branche est exactement égal à deux. Cela permet la construction d’une structure d’arbre qui permet différents compromis dans l’équilibrage des profondeurs de nœuds et des pondérations de nœuds (nombre de points de données dans le nœud). Le partitionnement hiérarchique divisé peut être plus rapide que le partitionnement hiérarchique agglomératif, en particulier lorsque les données ne nécessitent pas la création de l’arbre jusqu’aux points de données individuels.

Le partitionnement basé sur une distribution, parfois appelé partitionnement probabiliste, regroupe les points de données en fonction de leur distribution de probabilités. Cette approche suppose qu’il existe un processus générant des distributions normales pour chaque dimension des données qui créent les centres de cluster. Elle diffère du clustering basé sur le centroïde dans la mesure où elle n’utilise pas d'indicateur de distance telle qu’une distance euclidienne ou une distance de Manhattan. Au lieu de cela, les approches basées sur la distribution recherchent une distribution bien définie qui apparaît sur chaque dimension. Les moyennes de cluster sont les moyennes de la distribution gaussienne sur chaque dimension. Le clustering basé sur la distribution est une approche de clustering basée sur des modèles, car elle nécessite d'ajuster une distribution plusieurs fois sur chaque dimension pour trouver des clusters, ce qui signifie qu'elle peut être coûteuse en termes de calcul lorsque vous travaillez avec de grands jeux de données.

Une approche couramment utilisée pour le clustering basé sur la distribution consiste à créer un modèle de mélange gaussien (GMM) par le biais de l'espérance-maximisation. Un GMM est nommé en raison de l'hypothèse que chaque cluster est défini par une distribution gaussienne, souvent appelée distribution normale.

Considérez un jeu de données avec deux clusters distincts, A et B, qui sont tous deux définis par deux distributions normales différentes : l’une le long de l’axe des x et l’autre le long de l’axe des y. L’espérance-maximisation commence par une estimation aléatoire de ces deux distributions le long de chaque axe, puis procède à une amélioration itérative en alternant deux étapes :

Espérance : attribuez chaque point de données à chacun des clusters et calculez la probabilité qu’il provienne du cluster A et du cluster B.

Maximisation : mettez à jour les paramètres qui définissent chaque cluster, un emplacement moyen pondéré et une matrice de variance-covariance, en fonction de la probabilité que chaque point de données se trouve dans le cluster. Répétez ensuite l’étape d’espérance jusqu’à ce que l’équation converge sur les distributions observées pour chaque cluster.

Chaque point de données a une probabilité d’être associé à un cluster. Cela signifie que le clustering via l'espérance-maximisation est une approche de clustering douce et qu’un point donné peut être associé de manière probabiliste à plus d’un cluster. Cela a du sens dans certains scénarios, une chanson peut être un peu folk et un peu rock ou un utilisateur peut préférer les émissions de télévision en espagnol mais parfois aussi regarder des émissions en anglais.

Le clustering basé sur la densité fonctionne en détectant les zones où les points sont concentrés et où ils sont séparés par des zones vides ou éparses. Contrairement aux approches basées sur les centroïdes, comme K-means, ou sur les approches basées sur les distributions, comme l'espérance-maximisation, le clustering basé sur la densité peut détecter des clusters de forme arbitraire. Cela peut être extrêmement utile lorsque les clusters ne sont pas définis autour d'un emplacement ou d'une distribution spécifique. Contrairement à d’autres algorithmes de clustering, comme les J-means et le clustering hiérarchique, un algorithme basé sur la densité peut découvrir des clusters de n’importe quelle forme, taille ou densité dans vos données. Le clustering basé sur la densité permet également de faire la distinction entre les points de données qui font partie d’un cluster et ceux qui devraient être considérés comme bruit. Le clustering basé sur la densité est particulièrement utile lorsque vous travaillez avec des jeux de données contenant du bruit ou des données aberrantes, ou lorsque nous n’avons pas de connaissances préalables sur le nombre de clusters dans les données.

DBSCAN est un exemple d’algorithme de clustering qui adopte une approche de clustering basée sur la densité. Il utilise une approche de clustering spatial basée sur la densité pour créer des clusters avec une densité transmise par l'utilisateur qui s'articule autour d'un centroïde spatial. La zone immédiatement autour du centroïde est appelée quartier et DBSCAN tente de définir les quartiers de clusters qui ont la densité spécifiée. Pour chaque cluster, DBSCAN définira trois types de points de données :

Points centraux : un point de données est considéré comme un point central si le quartier autour de ce point de données contient au moins autant de points que le nombre minimum de points spécifié par l’utilisateur.

Points frontière : un point de données est un point frontière si le quartier autour de ce point de données contient moins que le nombre minimum de points de données, mais que le quartier autour de ce point contient un point central.

Donnée aberrante : un point de données est une valeur aberrante s’il ne s’agit ni d’un point de base ni d’un point frontière. Il s’agit essentiellement de la catégorie « Autre ».

HDBSCAN est une variante de DBSCAN qui ne nécessite aucun paramètre ; cela peut le rendre encore plus flexible que l'original. HDBSCAN est moins sensible au bruit et aux données aberrantes. En outre, DBSCAN peut parfois avoir du mal à identifier les clusters dont la densité n’est pas uniforme. Il s'agissait là d'une motivation première pour HDBSCAN, qui lui permet de gérer des clusters de densité variable beaucoup plus efficacement.

Les algorithmes de clustering basés sur une grille ne sont pas utilisés aussi souvent que les quatre approches précédentes, mais peuvent être utiles dans le clustering à haute dimension où d'autres algorithmes de clustering peuvent ne pas être aussi performants. Dans cette approche, l’algorithme partitionne un ensemble de données de grande dimension en cellules. À chaque cellule est attribué un identifiant unique appelé ID de cellule, et tous les points de données appartenant à une cellule sont considérés comme faisant partie du même cluster.

Le clustering basé sur des grilles est un algorithme efficace pour analyser de grands jeux de données multidimensionnelles, car il réduit le temps nécessaire à la recherche des plus proches voisins, ce qui est une étape courante dans de nombreuses méthodes de clustering.

Un algorithme de clustering populaire basé sur une grille est appelé Sting, qui signifie STatistical INformation Grid. Dans Sting, la zone spatiale est divisée en cellules rectangulaires et en plusieurs niveaux de cellules à différents niveaux de résolution. Les cellules de haut niveau sont divisées en plusieurs cellules de bas niveau. Sting peut être très efficace pour calculer des clusters dans des scénarios de big data où les jeux de données sont extrêmement volumineux, car il partitionne simplement le jeu de données de manière itérative en grilles plus fines et évalue le nombre de points dans cette grille. L'un des inconvénients de Sting est que les limites des clusters doivent être définies horizontalement ou verticalement, l'algorithme ne peut pas détecter les limites de cluster non rectangulaires.

Un autre algorithme basé sur une grille qui est particulièrement puissant avec des données de grande dimension est le Clustering In Quest ou CLIQUE. CLIQUE combine une approche de clustering basée sur une grille et une approche basée sur la densité. Dans cet algorithme, l'espace de données est divisé en une grille, la densité relative des points dans les cellules de la grille est comparée et les sous-espaces qui ont des densités similaires sont fusionnés. Cette approche permet de trouver des unités denses dans tous les sous-espaces d’intérêt, puis de déterminer si des clusters similaires doivent être connectés entre eux. Cela signifie que CLIQUE peut détecter des clusters de formes arbitraires dans des données à haute dimension.

Il existe plusieurs indicateurs d'évaluation pour l'analyse de clusters et la sélection de l'indicateur approprié dépend du type d'algorithme de clustering et du jeu de données correspondant. Les indicateurs d'évaluation peuvent généralement être divisés en deux catégories principales : extrinsèque et intrinsèque.

Les mesures intrinsèques sont des indicateurs d'évaluation pour l'analyse des clusters qui utilisent uniquement les informations contenues dans le jeu de données. Ils peuvent être utiles lorsque vous travaillez avec des données non étiquetées. La qualité de l’analyse repose entièrement sur les relations entre les points de données. Ils peuvent être utilisés lorsque l'on a aucune connaissance préalable ou étiquette sur les données. Les mesures intrinsèques courantes comprennent :

Score de silhouette : cet indicateur mesure la similarité et la dissimilarité de chaque point de données par rapport à son propre cluster et à tous les autres clusters. Les valeurs des indicateurs varient de −1 à +1. Une valeur élevée indique que l’objet correspond bien à son propre cluster et mal aux clusters voisins.

Indice Davies-Bouldin : cet indicateur calcule le rapport entre la distance au sein du cluster et la distance entre les clusters. Plus le score de l’indice est bas, meilleures sont les performances de partitionnement.

Indice de Calinski-Harabasz : également connu sous le nom de critère du ratio de variance, il mesure le rapport de la variance entre les clusters et de la variance au sein du cluster. Plus il est élevé, mieux un cluster est défini.

Ces indicateurs d’évaluation peuvent nous aider à comparer les performances de différents algorithmes et modèles de partitionnement, à optimiser les paramètres de partitionnement et à valider la précision et la qualité des résultats du partitionnement.

Les indicateurs extrinsèques utilisent la vérité de terrain ou des informations externes pour évaluer la validité des performances de l'algorithme de clustering. Cela nécessite une certaine forme de données d'étiquetage qui confirme la classe ou le groupe auquel appartient chaque point de données. Dans ce cas, vous pouvez comparer la précision de votre analyse de clustering à des indicateurs souvent utilisés pour la précision de la classification. Les indicateurs extrinsèques les plus courants sont les suivants :

Score F (également appelé mesure F) : cet indicateur détermine la précision de l’algorithme de partitionnement en tenant compte de la précision et de la mémorisation lorsque l’on compare un partitionnement proposé à une réalité de base. Dans le cas d’un score F, plus le score est élevé, mieux c’est.

Pureté : cet indicateur mesure la fraction de points de données qui sont correctement attribués à la même classe ou au même cluster auquel ils appartiennent. Dans le cas d’une mesure de pureté, plus la valeur est élevée, mieux c’est.

Indice de Rand : il s’agit d’un indicateur de la similarité entre les étiquettes vraies et prédites de l’algorithme de partitionnement, allant de 0 à 1. Une valeur plus élevée indique une meilleure performance de partitionnement.

Variation de l’information (également appelée distance d’information partagée) : elle mesure la quantité d’informations perdues et gagnées entre deux partitionnements. Il peut s’agir d’une différence entre un partitionnement de vérité terrain et un partitionnement généré par un algorithme, ou entre deux partitionnements différents. Un nombre inférieur est préférable, car il indique une distance plus faible entre deux résultats de partitionnement.

Il existe de nombreux domaines d’application où le clustering est un outil précieux pour le data mining ou l’analyse exploratoire des données ; nous ne pouvons énumérer qu’un petit échantillon des domaines d’application ici pour donner une idée de l’importance de ce type d’analyse.

Le clustering peut aider à découvrir des anomalies en mesurant quels points de données ne sont pas inclus dans la structure de clustering définie par l'analyse des clusters. Les points de données qui appartiennent à des clusters petits ou très clairsemés ou qui sont éloignés du cluster qui leur a été attribué peuvent être considérés comme des anomalies. Des méthodes basées sur la densité, comme l'espérance-maximisation, sont utilisées pour identifier les points de données dans les régions denses comme d'habitude et ceux des régions à faible densité comme des anomalies.

Lorsque vous essayez de comprendre quels sont les personas de clients ou les sous-ensembles de marchés qui pourraient exister, le clustering peut être un outil puissant pour vous aider à effectuer la segmentation de la clientèle. Vous pouvez combiner des données démographiques avec des données sur le comportement des clients pour trouver quels types de caractéristiques et de modèles d’achat sont le plus souvent corrélés.

Les pixels des images peuvent être regroupés de différentes manières, ce qui permet de découper l'image en différentes sections pour séparer un premier plan d'un arrière-plan, de détecter des objets en utilisant des similitudes de couleur et de luminosité, ou de diviser les images en régions d'intérêt en vue d'un traitement ultérieur. Pour les images, les méthodes de clustering traitent les pixels de l'image et définissent des zones dans l'image qui représentent le cluster.

L’analyse de clustering peut être utile pour traiter les documents de plusieurs façons. Les documents peuvent être regroupés par similarité pour montrer lesquels sont les plus similaires les uns aux autres. Ces données peuvent être basées sur la longueur du document, la distribution de la fréquence des mots ou d’autres moyens de quantifier les caractéristiques clés du document. Un autre cas d’utilisation courant consiste à analyser des groupes de sections d’un document en fonction de la fréquence des mots clés, de la longueur des phrases ou de la distribution des termes. Cela peut aider à résumer les documents ou à diviser les documents plus volumineux en jeux de données plus petits pour une analyse plus approfondie.