Algorithmes de clustering - Présentation

Introduction au clustering

Les méthodes de clustering sont l'une des méthodes ML non supervisées les plus utiles. Ces méthodes sont utilisées pour trouver la similitude ainsi que les modèles de relation entre les échantillons de données, puis regrouper ces échantillons en groupes ayant une similitude basée sur des caractéristiques.

Le regroupement est important car il détermine le regroupement intrinsèque parmi les données non étiquetées actuelles. Ils font essentiellement des hypothèses sur les points de données pour constituer leur similitude. Chaque hypothèse construira des clusters différents mais tout aussi valides.

Par exemple, ci-dessous est le diagramme qui montre le système de clustering regroupé le même type de données dans différents clusters -

Méthodes de formation de cluster

Il n'est pas nécessaire que les grappes soient formées sous forme sphérique. Voici quelques autres méthodes de formation de cluster -

Basé sur la densité

Dans ces méthodes, les grappes sont formées comme la région dense. L'avantage de ces méthodes est qu'elles ont une bonne précision ainsi qu'une bonne capacité à fusionner deux clusters. Ex. Clustering spatial basé sur la densité d'applications avec bruit (DBSCAN), points de commande pour identifier la structure de clustering (OPTICS), etc.

Basé sur la hiérarchie

Dans ces méthodes, les clusters sont formés comme une structure de type arborescente basée sur la hiérarchie. Ils ont deux catégories à savoir, agglomérative (approche ascendante) et divisive (approche descendante). Ex. Clustering à l'aide de représentants (CURE), Clustering itératif équilibré de réduction à l'aide de hiérarchies (BIRCH), etc.

Partitionnement

Dans ces méthodes, les clusters sont formés en divisant les objets en k clusters. Le nombre de clusters sera égal au nombre de partitions. Ex. K-means, regroupement de grandes applications basées sur une recherche aléatoire (CLARANS).

la grille

Dans ces méthodes, les clusters sont formés comme une structure en forme de grille. L'avantage de ces méthodes est que toutes les opérations de clustering effectuées sur ces grilles sont rapides et indépendantes du nombre d'objets de données. Ex. Grille d'information statistique (STING), Clustering in Quest (CLIQUE).

Mesurer les performances du clustering

L'une des considérations les plus importantes concernant le modèle ML est d'évaluer ses performances ou vous pouvez dire la qualité du modèle. Dans le cas d'algorithmes d'apprentissage supervisé, évaluer la qualité de notre modèle est facile car nous avons déjà des étiquettes pour chaque exemple.

D'un autre côté, dans le cas d'algorithmes d'apprentissage non supervisés, nous ne sommes pas très chanceux car nous traitons des données non étiquetées. Mais nous avons quand même quelques métriques qui donnent au praticien un aperçu de la survenance du changement dans les clusters en fonction de l'algorithme.

Avant de plonger dans de telles métriques, nous devons comprendre que ces métriques évaluent uniquement les performances comparatives des modèles les uns par rapport aux autres plutôt que de mesurer la validité de la prédiction du modèle. Voici quelques-unes des métriques que nous pouvons déployer sur des algorithmes de clustering pour mesurer la qualité du modèle -

Analyse de la silhouette

Analyse de silhouette utilisée pour vérifier la qualité du modèle de clustering en mesurant la distance entre les clusters. Il nous fournit essentiellement un moyen d'évaluer les paramètres tels que le nombre de clusters à l'aide deSilhouette score. Ce score mesure la proximité de chaque point d'un cluster par rapport aux points des clusters voisins.

Analyse du score de silhouette

La plage de score Silhouette est [-1, 1]. Son analyse est la suivante -

+1 Score - Près de +1 Silhouette score indique que l'échantillon est loin de son cluster voisin.
0 Score - 0 Silhouette score indique que l'échantillon est sur ou très proche de la frontière de décision séparant deux clusters voisins.
-1 Score & moins -1 Silhouette score indique que les échantillons ont été affectés aux mauvais clusters.

Le calcul du score Silhouette peut être effectué en utilisant la formule suivante -

= (-) / (,)

Ici, = distance moyenne aux points du cluster le plus proche

Et, = distance moyenne intra-cluster à tous les points.

Indice Davis-Bouldin

L'index DB est une autre bonne métrique pour effectuer l'analyse des algorithmes de clustering. Avec l'aide de DB index, nous pouvons comprendre les points suivants sur le modèle de clustering -

Si les grappes sont bien espacées les unes des autres ou non?
Quelle est la densité des grappes?

Nous pouvons calculer l'indice DB à l'aide de la formule suivante -

$$ DB = \ frac {1} {n} \ displaystyle \ sum \ limits_ {i = 1} ^ n max_ {j \ neq {i}} \ left (\ frac {\ sigma_ {i} + \ sigma_ {j }} {d (c_ {i}, c_ {j})} \ right) $$

Ici, = nombre de clusters

σ _i = distance moyenne de tous les points du cluster par rapport au centre de gravité du cluster.

Moins l'index DB, meilleur est le modèle de clustering.

Index Dunn

Cela fonctionne de la même manière que l'index DB mais il y a des points suivants dans lesquels les deux diffèrent -

L'indice de Dunn ne considère que le pire des cas, c'est-à-dire les clusters qui sont proches les uns des autres, tandis que l'indice DB considère la dispersion et la séparation de tous les clusters dans le modèle de clustering.
L'indice Dunn augmente à mesure que les performances augmentent, tandis que l'indice DB s'améliore lorsque les clusters sont bien espacés et denses.

Nous pouvons calculer l'indice de Dunn à l'aide de la formule suivante -

$$ D = \ frac {min_ {1 \ leq i <{j} \ leq {n}} P (i, j)} {mix_ {1 \ leq i <k \ leq n} q (k)} $$

Ici, ,, = chaque index pour les clusters

= distance inter-cluster

q = distance intra-cluster

Types d'algorithmes de clustering ML

Voici les algorithmes de clustering ML les plus importants et les plus utiles -

Clustering K-means

Cet algorithme de clustering calcule les centroïdes et itère jusqu'à ce que nous trouvions le centroïde optimal. Il suppose que le nombre de clusters est déjà connu. Il est également appelé algorithme de clustering plat. Le nombre de clusters identifiés à partir des données par algorithme est représenté par «K» dans K-means.

Algorithme de décalage moyen

C'est un autre algorithme de clustering puissant utilisé dans l'apprentissage non supervisé. Contrairement au clustering K-means, il ne fait aucune hypothèse, il s'agit donc d'un algorithme non paramétrique.

Classification hiérarchique

C'est un autre algorithme d'apprentissage non supervisé qui est utilisé pour regrouper les points de données non étiquetés ayant des caractéristiques similaires.

Nous discuterons de tous ces algorithmes en détail dans les prochains chapitres.

Applications du clustering

Nous pouvons trouver le clustering utile dans les domaines suivants -

Data summarization and compression- Le clustering est largement utilisé dans les domaines où nous avons également besoin de la synthèse, de la compression et de la réduction des données. Les exemples sont le traitement d'image et la quantification vectorielle.

Collaborative systems and customer segmentation - Le clustering pouvant être utilisé pour trouver des produits similaires ou le même type d'utilisateurs, il peut être utilisé dans le domaine des systèmes collaboratifs et de la segmentation client.

Serve as a key intermediate step for other data mining tasks- L'analyse de cluster peut générer un résumé compact des données pour la classification, le test, la génération d'hypothèses; par conséquent, il sert également d'étape intermédiaire clé pour d'autres tâches d'exploration de données.

Trend detection in dynamic data - Le regroupement peut également être utilisé pour la détection de tendances dans les données dynamiques en créant divers groupes de tendances similaires.

Social network analysis- Le clustering peut être utilisé dans l'analyse des réseaux sociaux. Les exemples génèrent des séquences en images, vidéos ou audios.

Biological data analysis - Le regroupement peut également être utilisé pour créer des grappes d'images, de vidéos, par conséquent, il peut être utilisé avec succès dans l'analyse de données biologiques.