Qu'est-ce que l'analyse de partitionnement de données ?

L'analyse de partitionnement de données est une technique d'analyse des données qui explore les groupes qui se forment naturellement au sein d'un ensemble de données, appelés partitionnements ou clusters. L'analyse par partitionnement n'a pas besoin de regrouper les points de données dans des groupes prédéfinis, ce qui signifie qu'il s'agit d'une méthode d'unsupervised learning. Dans l'unsupervised learning, les idées sont dérivées des données sans étiquettes ou classes prédéfinies. Un bon algorithme de partitionnement de données garantit une forte similarité intra-cluster et une faible similarité inter-cluster.

Un exemple de problème de partitionnement de données

Le regroupement des points de vente au détail en fonction de leurs ventes est un cas d'utilisation simple de l'analyse de partitionnement de données. Supposons qu'un café possède huit points de vente dans la ville. Le tableau ci-dessous indique les ventes de cappuccino et de café glacé par jour.

Le graphique ci-dessous montre les mêmes données où les ventes de cappuccino et de café glacé pour chaque point de vente sont représentées sur les axes X et Y, respectivement. Dans cet exemple, comme les points de données étaient peu nombreux, il a été facile de tracer les deux groupes qui se sont formés naturellement sur un graphique et de les visualiser manuellement.

Cependant, lorsqu'il s'agit de milliers de points de données, il faut utiliser des algorithmes d'analyse de partitionnement de données pour répartir les points de données en différents groupes.

Quelles sont les applications de l'analyse de partitionnement de données ?

L'analyse de partitionnement de données est souvent utilisée de deux manières principales :

• En tant qu'outil autonome pour résoudre les problèmes liés au regroupement des données.
• Comme étape de prétraitement pour divers algorithmes de machine learning.

L'analyse de partitionnement de données comme outil autonome

• Marketing : en marketing, l'analyse de partitionnement de données peut être utilisée pour répartir les clients dans différents groupes en fonction de leurs habitudes d'achat ou de leurs intérêts. C'est ce qu'on appelle les personas clients. Les organisations utilisent ensuite différentes stratégies de marketing en fonction des différents groupes de clients.
• Analyse du risque en finance: Les organismes financiers utilisent divers algorithmes de partitionnement de données pour classer leurs clients dans diverses catégories de risque en fonction de leur solde bancaire et de leurs dettes. Lors de l'approbation de prêts, d'assurances ou de cartes de crédit, ces partitionnements sont utilisés pour contribuer à la prise de décision.
• Immobilier : les spécialistes de l'infrastructure utilisent le clustering pour regrouper les maisons en fonction de leur taille, de leur emplacement et de leur valeur marchande. Ces informations sont utilisées pour évaluer le potentiel immobilier des différentes parties d'une ville.

L'analyse de partitionnement de données comme étape de prétraitement pour le machine learning

L'analyse de partitionnement de données est souvent utilisée comme étape de prétraitement pour divers algorithmes de machine learning.

Les algorithmes de classification effectuent une analyse de partitionnement de données sur un vaste ensemble de données afin de filtrer les données qui appartiennent à des groupes évidents. Des techniques avancées de classification des données peuvent alors être utilisées sur les points de données réduits et non évidents. Comme l'ensemble de données devient plus petit, le temps de calcul est fortement réduit. La même méthode peut être utilisée à l'inverse, lorsqu'un algorithme d'analyse de partitionnement de données est utilisé pour filtrer le bruit ou les données aberrantes.

Avant d'exécuter un algorithme de supervised learning, il est possible d'effectuer d'abord une analyse de partitionnement sur les données d'entrée afin de trouver les groupes naturels dans les données.

Quels sont les principaux algorithmes de partitionnement de données ?

Les algorithmes d'analyse de partitionnement de données appartiennent souvent aux catégories suivantes :

• Algorithmes basés sur les partitions
• Algorithmes hiérarchiques
• Algorithmes basés sur la densité
• Algorithmes basés sur une grille
• Algorithmes basés sur des modèles
• Algorithmes basés sur des contraintes
• Algorithmes d'analyse des valeurs aberrantes

Chaque algorithme est complexe en soi et peut convenir à certaines analyses, mais pas à toutes.

Algorithmes basés sur les partitions pour le partitionnement de données

Dans cette méthode, un algorithme commence avec plusieurs groupes initiaux. Ensuite, il déplace itérativement les points de données vers différents groupes jusqu'à ce qu'une partition optimale soit atteinte. L'algorithme de partitionnement K-means est l'un des algorithmes de partitionnement les plus populaires.

L'exemple de partitionnement K-means ci-dessous illustre son fonctionnement.

Étape 1 : décider des partitionnements

Décidez du nombre de groupes, « K » pour l'algorithme, par exemple, K=3. L'algorithme répartira les douze points de données ci-dessus en 3 groupes. Le nombre K peut avoir n'importe quelle valeur. En fonction de cela, l'exactitude du partitionnement peut varier. Il existe également des méthodes algorithmiques qui peuvent être utilisées pour déterminer la valeur optimale de K.

Étape 2 : choisir les points de données

Comme K=3, prenez trois points de données quelconques comme moyenne initiale. Dans cet exemple, les points C, D et E sont choisis comme moyennes initiales. Notez que l'algorithme K-means peut prendre n'importe quel point comme moyenne (means) initiale.

Étape 3 : calculer les distances

Calculez la distance entre chaque point de l'ensemble de données et la moyenne de chaque groupe initial. Trois moyennes de partitionnements C, D et E ont été choisies au hasard. Pour chaque point de données de l'échantillon, calculez la distance qui le sépare de ces trois moyennes. La distance euclidienne entre deux points (X1, Y1) et (X2, Y2) est utilisée comme suit :

Après l'étape 3, un tableau montrerait la distance de chaque point de données par rapport aux moyennes initiales C, D et E.

Un point de données est ajouté à un partitionnement en fonction de sa distance minimale. Par exemple, le point A a une distance minimale par rapport à une moyenne initiale C. Cela signifie que A est dans le partitionnement dont la moyenne est C. Après la première étape, les partitionnements sont obtenus.

Étape 4 : réitération - calcul des nouvelles moyennes

Il est maintenant facile de voir les partitionnements initiaux. L'étape suivante consiste à calculer trois nouvelles moyennes de partitionnement. Pour cela, chaque point de données dans un partitionnement particulier est utilisé pour calculer une moyenne.

Nouvelle moyenne de partitionnement pour le partitionnement « C » = (5+2+6+1+4+3+6/7, 21+11+22+10+23+14+12/7) = (3,85, 16,14), Appelons ce point X.

Nouvelle moyenne de partitionnement pour le partitionnement « D » = (1+2+5/3, 6+8+4/3) = (2,66, 6), appelons ce point Y.

Nouvelle moyenne de partitionnement pour le partitionnement « E » = (4+5/2, 10+11/2) = (4,5, 10,5). Appelons ce point Z.

Étape 5 : réitération - calculer la distance de chaque point de données par rapport aux nouvelles moyennes

Répétez l'étape 3 pour déterminer la distance de tous les points de données par rapport aux moyennes de partitionnement nouvellement calculées, X, Y et Z. Dans cette nouvelle itération, il est facile de voir que la distance minimale des points de données C, D, I et L a changé. Ils appartiennent maintenant à un nouveau partitionnement, comme indiqué ci-dessous.

Ensuite, l'itération K-means doit se poursuivre, car certains points de données ont changé de partitionnements.

Étape 6 : réitération - calcul des nouvelles moyennes et des nouveaux partitionnements

Comme les points de données C, D, I, L ont changé de partitionnement, de nouvelles moyennes de partitionnement doivent être calculées comme à l'étape 4. Pour cela, chaque point de données d'un partitionnement particulier est utilisé pour calculer une moyenne. Ensuite, comme à l'étape 5, la distance entre chaque point de données et la nouvelle moyenne de partitionnement est calculée. Sur la base de cette distance, les points de données sont affectés à un partitionnement pour lequel la distance est minimale.

Quand l'algorithme K-means se termine-t-il ?

K-means est un algorithme de partition itératif :

• Décidez du nombre de partitionnements (K) pour commencer. Dans l'exemple ci-dessus, K=3.
• Attribuez aléatoirement un nombre K de points de données comme moyenne initiale des partitionnements.
• Répétez les étapes ci-dessous jusqu'à ce qu'aucun point de données ne change de partitionnement.
• Calculez la distance moyenne entre le point de données et la moyenne du partitionnement.
• Attribuez un point de données au partitionnement dont la distance est la plus faible.
• Vérifiez si un point de données a changé de partitionnement.

Lors d'une nouvelle itération, si chaque point de données reste dans son partitionnement précédent, l'algorithme K-means se termine. Cela signifie qu'une solution localement optimale a été obtenue.

Algorithme de partitionnement basé sur la partition K-médoïde

L'algorithme K-médoïdes est un autre algorithme de partitionnement basé sur les groupes. Les algorithmes K-médoïdes choisissent les médoïdes comme objet représentatif d'un partitionnement. L'algorithme K-médoïdes essaie de trouver les points de données qui ont une dissimilarité minimale avec tous les autres points de données d'un partitionnement particulier. Jusqu'à ce que la dissimilarité soit minimisée, l'algorithme K-médoïdes partitionne l'ensemble de données de manière itérative. L'algorithme K-means utilise souvent la distance d'erreur au carré (distance euclidienne), et les algorithmes K-médoïdes utilisent souvent la distance en valeur absolue comme la distance de Manhattan pour mesurer la dissimilarité entre deux points de données.

L'algorithme PAM (Partition Around Medoids) est une implémentation standard de l'algorithme K-médoïdes. Voici les étapes de base de l'algorithme PAM.

1. Choisissez une valeur pour K, où K est le nombre de partitionnements dans lesquels les points de données seront divisés.
2. Choisissez un nombre K de points de données de manière aléatoire comme médoïdes.
3. Pour chaque point de données (Xi, Yi) dans l'ensemble de données, mesurez la dissimilarité entre le point et les médoïdes sélectionnés ci-dessus. Une mesure de dissimilarité souvent utilisée est la distance de Manhattan :
   • | Xi - Ci| + | Yi - Cj|, où (Ci, Cj) représente un médoïde.
4. Chaque point de données (Xi, Yi) est affecté à un partitionnement où la dissimilarité est minimale.
5. Pour chacun des partitionnements ci-dessus, calculez le coût total : la somme des dissimilarités de chacun des points de données dans ce partitionnement.
6. Maintenant, sélectionnez aléatoirement un point médoïde qui sera le nouveau médoïde et répétez les étapes 3 à 5.
7. Arrêtez-vous lorsqu'il n'y a plus de changements dans les partitionnements.

Comparaison des algorithmes K-means et K-médoïdes

Bien que l'algorithme K-means soit simple, il ne donne pas de bons résultats lorsque les données comportent beaucoup de bruit et de valeurs aberrantes. La méthode K-médoïdes est plus robuste dans de tels cas. Cependant, les algorithmes K-médoïdes comme PAM ne sont utiles que lorsque l'ensemble de données est petit. Lorsque la taille de l'ensemble des données augmente, le temps de calcul de l'algorithme K-médoïdes augmente de manière exponentielle.

Algorithmes de division

Comme leur nom l'indique, les algorithmes de division assignent tous les points de données à un seul partitionnement au départ. Ils divisent ensuite le partitionnement en groupes moins similaires. L'algorithme divise ensuite ces partitionnements de manière récursive jusqu'à ce qu'une solution optimale soit atteinte. Les algorithmes de division sont également connus comme une méthode de partitionnement descendante.

Algorithmes d'agglomération

Ces algorithmes commencent par affecter chaque point de données à un partitionnement différent. Ensuite, l'algorithme joint récursivement les partitionnements les plus similaires jusqu'à ce qu'une solution optimale soit atteinte. Les algorithmes d'agglomération sont également connus sous le nom de méthode de partitionnement ascendante.

Exemple d'un algorithme d'agglomération pour partitionnement

Vous trouverez ci-dessous une matrice de distance pour cinq points de données. La distance entre les points peut être calculée sur la base de la distance euclidienne, de la distance de Manhattan ou de toute autre formule de distance. La matrice de distance est toujours une matrice symétrique, car la distance entre les points X et Y est la même que celle entre Y et X. Sur la base de cette matrice de distance, voici un exemple d'algorithme d'agglomération (ascendant) pour partitionnement.

Étape 1 : dans la matrice de distance, trouvez les deux points dont la distance est la plus petite. Dans l'exemple ci-dessus, il s'agit des points 3 et 5. La distance entre eux est de 2. Mettez-les dans un seul groupe.

Étape 2 : supprimez les points 3 et 5 et remplacez-les par un partitionnement « 35 » et créez une nouvelle matrice de distance. Pour cela, il faut calculer la distance entre tous les points de données et le partitionnement « 35 ». Il existe plusieurs façons de déterminer cette distance.

Dans cet exemple, la méthode suivante a été utilisée pour mesurer la distance :

Distance du point X du partitionnement « 35 » = minimum (distance (X,3), distance(X,5)). La matrice de distance actualisée basée sur cette méthode est la suivante :

Étape 3 : répétez l'étape 2 jusqu'à ce que tous les points de données soient regroupés en un seul partitionnement. Dans l'exemple actuel, cela prend six itérations. Le schéma ci-dessous montre la formation des partitionnements. Ce type de représentation est connu sous le nom de dendrogramme. Dans cette représentation, l'axe Y représente la distance entre deux points de données. Par exemple, la distance entre les points 3 et 5 est 2.

Étape 4 : une fois que tous les points de données sont regroupés, comme indiqué ci-dessus, décidez du nombre de partitionnements à conserver. Il s'agit d'une décision difficile, car chaque algorithme de partitionnement hiérarchique produit finalement un seul partitionnement. Il existe plusieurs méthodes pour décider du nombre optimal de groupes après qu'un algorithme de partitionnement hiérarchique ait divisé les données.

Algorithmes de regroupement basés sur la densité

Ces algorithmes sont basés sur l'idée que les partitionnements sont toujours plus denses que l'espace de données qui les entoure. Les algorithmes basés sur la densité commencent avec un seul point de données et explorent les points de données dans son voisinage. Les points situés dans le voisinage du point initial sont inclus dans un seul partitionnement. La définition du voisinage varie en fonction de l'implémentation de l'algorithme. Le partitionnement spatial d'applications avec bruit basé sur la densité (DBSCAN) est un algorithme de partitionnement populaire dans cette catégorie.

Algorithmes de regroupement basés sur une grille

Les algorithmes de partitionnement basés sur une grille sont similaires à ceux basés sur la densité. L'espace de données est divisé en plusieurs unités plus petites appelées grilles. Chaque point de données est attribué à une cellule de grille particulière. L'algorithme calcule ensuite la densité de chaque grille. Les grilles dont la densité est inférieure à un seuil sont éliminées. Ensuite, l'algorithme forme des partitionnements à partir de groupes adjacents de grilles denses. Les statistical information grid (STING) et clustering in quest (CLIQUE) sont deux algorithmes populaires basés sur une grille.

En plus des algorithmes décrits ci-dessus, l'analyse de partitionnement de données comprend un groupe d'algorithmes de regroupement basés sur des modèles, de partitionnement basés sur des contraintes et d'analyse des aberrations.

Avantages et inconvénients des algorithmes d'analyse de partitionnement de données