Identifier l'inconnu avec les métriques de clustering

Le clustering est une méthode d'apprentissage automatique non supervisée pour diviser des données données en groupes basés uniquement sur les caractéristiques de chaque échantillon. Le tri des données en grappes peut aider à identifier des similitudes inconnues entre des échantillons ou à révéler des valeurs aberrantes dans l'ensemble de données. Dans le monde réel, le clustering a une importance dans divers domaines, du marketing à la biologie : les applications de clustering incluent la segmentation du marché, l'analyse des réseaux sociaux et l'imagerie médicale diagnostique.

Étant donné que ce processus n'est pas supervisé, plusieurs résultats de clustering peuvent se former autour de différentes fonctionnalités. Par exemple, imaginez que vous disposez d'un ensemble de données composé de diverses images de pantalons rouges, de pantalons noirs, de chemises rouges et de chemises noires. Un algorithme peut trouver des clusters en fonction de la forme des vêtements, tandis qu'un autre peut créer des groupes en fonction de la couleur.

Lors de l'analyse d'un ensemble de données, nous avons besoin d'un moyen de mesurer avec précision les performances de différents algorithmes de clustering ; nous pouvons vouloir comparer les solutions de deux algorithmes, ou voir à quel point un résultat de clustering est proche d'une solution attendue. Dans cet article, nous allons explorer certaines des métriques qui peuvent être utilisées pour comparer différents résultats de clustering obtenus à partir des mêmes données.

Comprendre le clustering : un bref exemple

Définissons un exemple d'ensemble de données que nous utiliserons pour expliquer divers concepts de métrique de clustering et examinons les types de clusters qu'il pourrait produire.

Tout d'abord, quelques notations et termes courants :

• $D$ : le jeu de données
• $A$, $B$ : deux clusters qui sont des sous-ensembles de notre ensemble de données
• $C$ : le clustering de vérité terrain de $D$ auquel nous comparerons un autre cluster
  • Le clustering $C$ a des clusters $K$, $C = {C_1, …, C_k}$
• $C'$ : un deuxième regroupement de $D$
  • Le clustering $C'$ a $K'$ clusters, $C' = {C^\prime_1, …, C^\prime_{k^\prime}}$

Les résultats du clustering peuvent varier en fonction non seulement des fonctionnalités de tri, mais également du nombre total de clusters. Le résultat dépend de l'algorithme, de sa sensibilité aux petites perturbations, des paramètres du modèle et des caractéristiques des données. En utilisant notre ensemble de données de pantalons et de chemises noirs et rouges mentionné précédemment, il existe une variété de résultats de regroupement qui pourraient être produits à partir de différents algorithmes.

Pour faire la distinction entre le clustering général $C$ et nos exemples de clustering, nous utiliserons un $c$ minuscule pour décrire nos exemples de clustering :

• $c$, avec des clusters basés sur la forme : $c = {c_1, c_2}$, où $c_1$ représente un pantalon et $c_2$ représente une chemise
• $c'$, avec des clusters basés sur la couleur : $c' = {c'_1, c'_2}$, où $c'_1$ représente des vêtements rouges et $c'_2$ représente des vêtements noirs
• $c''$, avec des clusters basés sur la forme et la couleur : $c'' = {{c^{\prime \prime}}_1, {c^{\prime \prime}}_2, {c^{\prime \prime}}_3, {c^{\prime \prime}}_4}$, où ${c^{\prime \prime}}_1$ représente un pantalon rouge, ${c^{\prime \prime}}_2 $ représente un pantalon noir, ${c^{\prime \prime}}_3$ représente des chemises rouges et ${c^{\prime \prime}}_4$ représente des chemises noires

Des clusters supplémentaires peuvent inclure plus de quatre clusters basés sur différentes caractéristiques, par exemple si une chemise est sans manches ou à manches.

Comme on le voit dans notre exemple, une méthode de clustering divise tous les échantillons d'un ensemble de données en sous-ensembles disjoints non vides. Dans le cluster $c$, aucune image n'appartient à la fois au sous-ensemble pantalon et au sous-ensemble chemise : $c_1 \cap c_2 = \emptyset$. Ce concept peut être étendu ; deux sous-ensembles d'un cluster n'ont pas le même échantillon.

Présentation des métriques de comparaison de clustering

La plupart des critères de comparaison des regroupements peuvent être décrits à l'aide de la matrice de confusion du couple $C, C'$. La matrice de confusion serait une matrice $K \times K'$ dont $kk'$th élément (l'élément de la $k$th ligne et $k'$th colonne) est le nombre d'échantillons à l'intersection des clusters $ C_k$ de $C$ et $C'_{k'}$ de $C'$ :

\[n_{kk'} = |C_k \cap C'_{k'}|\]

Nous allons décomposer cela en utilisant notre exemple simplifié de pantalons et chemises noirs et rouges, en supposant que l'ensemble de données $D$ contient 100 pantalons rouges, 200 pantalons noirs, 200 chemises rouges et 300 chemises noires. Examinons la matrice de confusion de $c$ et $c''$ :

Puisque $K = 2$ et $K'' = 4$, c'est une matrice $2 \time 4$. Choisissons $k = 2$ et $k'' = 3$. Nous voyons cet élément $n_{kk'} = n_{23} = 200$. Cela signifie que l'intersection de $c_2$ (chemises) et ${c^{\prime\prime}}_3$ (chemises rouges) est 200, ce qui est correct puisque $c_2 \cap {c^{\prime\prime} }_3$ serait simplement l'ensemble des chemises rouges.

Les métriques de clustering peuvent être globalement classées en trois groupes en fonction de la méthode de comparaison de cluster sous-jacente :

Dans cet article, nous n'abordons que quelques-unes des nombreuses métriques disponibles, mais nos exemples serviront à définir les trois groupes de métriques de clustering.

Comptage de paires

Le comptage de paires nécessite d'examiner toutes les paires d'échantillons, puis de compter les paires où les regroupements sont en accord et en désaccord. Chaque paire d'échantillons peut appartenir à l'un des quatre ensembles, où les nombres d'éléments d'ensemble ($N_{ij}$) sont obtenus à partir de la matrice de confusion :

• $S_{11}$, avec des éléments $N_{11}$ : les éléments de la paire se trouvent dans le même cluster sous $C$ et $C'$
  • Une paire de deux chemises rouges tomberait sous $S_{11}$ en comparant $c$ et $c''$
• $S_{00}$, avec des éléments $N_{00}$ : les éléments de la paire se trouvent dans des clusters différents sous $C$ et $C'$
  • Une paire composée d'une chemise rouge et d'un pantalon noir tomberait sous $S_{00}$ si l'on compare $c$ et $c''$
• $S_{10}$, avec des éléments $N_{10}$ : les éléments de la paire se trouvent dans le même cluster dans $C$ et dans des clusters différents dans $C'$
  • Une paire composée d'une chemise rouge et d'une chemise noire tomberait sous $S_{10}$ si l'on compare $c$ et $c''$
• $S_{01}$, avec des éléments $N_{01}$ : les éléments de la paire se trouvent dans des clusters différents dans $C$ et dans le même cluster dans $C'$
  • $S_{01}$ n'a aucun élément ($N_{01} = 0$) lors de la comparaison de $c$ et $c''$

L' indice Rand est défini comme $(N_{00} + N_{11})/(n(n-1)/2)$, où $n$ représente le nombre d'échantillons ; il peut également être lu comme (nombre de paires traitées de manière similaire)/(nombre total de paires). Bien que théoriquement sa valeur soit comprise entre 0 et 1, sa plage est souvent beaucoup plus étroite en pratique. Une valeur plus élevée signifie plus de similarité entre les regroupements. (Un indice Rand de 1 représenterait une correspondance parfaite où deux clusters ont des clusters identiques.)

Une limitation de l'indice Rand est son comportement lorsque le nombre de clusters augmente pour se rapprocher du nombre d'éléments ; dans ce cas, il converge vers 1, ce qui crée des difficultés pour mesurer avec précision la similarité des clusters. Plusieurs versions améliorées ou modifiées de l'indice Rand ont été introduites pour résoudre ce problème. Une variation est l' indice Rand ajusté ; cependant, il suppose que deux clusters sont tirés au hasard avec un nombre fixe de clusters et d'éléments de cluster.

Théorie de l'information

Ces métriques sont basées sur des notions génériques de la théorie de l'information. Nous en aborderons deux : l'entropie et l'information mutuelle (IM).

L'entropie décrit la quantité d'informations contenues dans un clustering. Si l'entropie associée à un regroupement est de 0, alors il n'y a pas d'incertitude sur le groupe d'un échantillon choisi au hasard, ce qui est vrai lorsqu'il n'y a qu'un seul groupe.

MI décrit la quantité d'informations qu'un clustering donne sur l'autre. MI peut indiquer dans quelle mesure le fait de connaître la grappe d'un échantillon en $C$ réduit l'incertitude sur la grappe de l'échantillon en $C'$.

L'information mutuelle normalisée est MI qui est normalisée par la moyenne géométrique ou arithmétique des entropies des regroupements. L'IM standard n'est pas lié par une valeur constante, de sorte que les informations mutuelles normalisées fournissent une métrique de regroupement plus interprétable.

Une autre métrique populaire dans cette catégorie est la variation de l'information (VI) qui dépend à la fois de l'entropie et de l'IM des regroupements. Soit $H(C)$ l'entropie d'un clustering et $I(C, C')$ le MI entre deux clusterings. VI entre deux regroupements peut être défini comme $VI(C,C') = H(C)+H(C')-2I(C,C')$. Un VI de 0 représente une correspondance parfaite entre deux regroupements.

Définir le chevauchement

Définir les métriques de chevauchement implique de déterminer la meilleure correspondance pour les clusters dans $C$ avec les clusters dans $C'$ en fonction du chevauchement maximal entre les clusters. Pour toutes les métriques de cette catégorie, un 1 signifie que les regroupements sont identiques.

La mesure de correspondance maximale parcourt la matrice de confusion dans l'ordre décroissant et correspond en premier à la plus grande entrée de la matrice de confusion. Il supprime ensuite les clusters correspondants et répète le processus de manière séquentielle jusqu'à épuisement des clusters.

La mesure F est une autre métrique de chevauchement définie. Contrairement à la mesure de correspondance maximale, la mesure F est fréquemment utilisée pour comparer un regroupement à une solution optimale, au lieu de comparer deux regroupements.

Application de métriques de clustering avec F-measure

En raison de l'utilisation courante de la mesure F dans les modèles d'apprentissage automatique et des applications importantes telles que les moteurs de recherche, nous allons explorer la mesure F plus en détail avec un exemple.

Définition de la mesure F

Supposons que $C$ est notre vérité terrain, ou solution optimale. Pour tout $k$ième cluster dans $C$, où $k \in [1, K]$, nous calculerons une F-mesure individuelle avec chaque cluster dans le résultat de clustering $C'$. Cette mesure F individuelle indique dans quelle mesure le cluster $C^\prime_{k'}$ décrit le cluster $C_k$ et peut être déterminée par la précision et le rappel (deux mesures d'évaluation du modèle) pour ces clusters. Définissons $I_{kk'}$ comme l'intersection des éléments du $k$th cluster de $C$ et du $k'$th cluster de $C'$, et $\lvert C_k \rvert$ comme nombre d'éléments dans le $k$ième cluster.

• Précision $p = \frac{I_{kk'}}{\lvert C'_{k'} \rvert}$

• Rappel $r = \frac{I_{kk'}}{\lvert C_{k} \rvert}$

Ensuite, la mesure F individuelle des $k$th et $k'$th cluster peut être calculée comme la moyenne harmonique de la précision et du rappel pour ces clusters :

\[F_{kk'} = \frac{2rp}{r+p} = \frac{2I_{kk'}}{|C_k|+|C'_{k'}|}\]

Maintenant, pour comparer $C$ et $C'$, regardons la F-mesure globale. Tout d'abord, nous allons créer une matrice similaire à un tableau de contingence dont les valeurs sont les F-mesures individuelles des clusters. Supposons que nous ayons mappé les clusters de $C$ en tant que lignes d'une table et les clusters de $C'$ en tant que colonnes, avec des valeurs de table correspondant à des F-mesures individuelles. Identifiez la paire de clusters avec la mesure F individuelle maximale et supprimez la ligne et la colonne correspondant à ces clusters. Répétez cette opération jusqu'à ce que les grappes soient épuisées. Enfin, nous pouvons définir la F-mesure globale :

\[F(C, C') = \frac{1}{n} \sum_{i=1}^K n_imax(F(C_i, C'_j)) \forall j \in {1, K'}\ ]

Comme vous pouvez le voir, la mesure F globale est la somme pondérée de nos mesures F individuelles maximales pour les clusters.

Configuration des données et résultats attendus

Tout bloc-notes Python adapté à l'apprentissage automatique, tel qu'un bloc-notes Jupyter, fonctionnera comme notre environnement. Avant de commencer, vous voudrez peut-être examiner le fichier README de mon référentiel GitHub, le fichier d'exemple étendu readme_help_example.ipynb et le fichier requirements.txt (les bibliothèques requises).

Nous utiliserons les exemples de données du référentiel GitHub, composé d'articles d'actualité. Les données sont organisées avec des informations telles que la category , le headline , la date et short_description :

Nous pouvons utiliser des pandas pour lire, analyser et manipuler les données. Nous allons trier les données par date et sélectionner un petit échantillon (10 000 titres d'actualité) pour notre démonstration, car l'ensemble de données complet est volumineux :

 import pandas as pd df = pd.read_json("./sample_data/example_news_data.json", lines=True) df.sort_values(by='date', inplace=True) df = df[:10000] len(df['category'].unique())

Lors de l'exécution, vous devriez voir le bloc-notes afficher le résultat 30, car il y a 30 catégories dans cet échantillon de données. Vous pouvez également exécuter df.head(4) pour voir comment les données sont stockées. (Il doit correspondre au tableau affiché dans cette section.)

Optimisation des fonctionnalités de clustering

Avant d'appliquer le clustering, nous devons d'abord prétraiter le texte pour réduire les fonctionnalités redondantes de notre modèle, notamment :

• Mise à jour du texte pour avoir une casse uniforme.
• Suppression de caractères numériques ou spéciaux.
• Effectuer la lemmatisation.
• Suppression des mots vides.

 import re import nltk from nltk.corpus import stopwords from nltk.stem import WordNetLemmatizer wordnet_lemmatizer = WordNetLemmatizer() nltk.download('stopwords') stop_words = stopwords.words('english') nltk.download('wordnet') nltk.download('omw-1.4') def preprocess(text: str) -> str: text = text.lower() text = re.sub('[^az]',' ',text) text = re.sub('\s+', ' ', text) text = text.split(" ") words = [wordnet_lemmatizer.lemmatize(word, 'v') for word in text if word not in stop_words] return " ".join(words) df['processed_input'] = df['headline'].apply(preprocess)

Les titres prétraités résultants sont affichés en tant que processed_input , que vous pouvez observer en exécutant à nouveau df.head(4) :

Maintenant, nous devons représenter chaque titre comme un vecteur numérique pour pouvoir lui appliquer n'importe quel modèle d'apprentissage automatique. Il existe différentes techniques d'extraction de caractéristiques pour y parvenir; nous utiliserons TF-IDF (terme fréquence-fréquence de document inverse). Cette technique réduit l'effet des mots apparaissant à une fréquence élevée dans les documents (dans notre exemple, les titres de l'actualité), car ceux-ci ne devraient clairement pas être les caractéristiques déterminantes pour les regrouper ou les classer.

 from sklearn.cluster import AgglomerativeClustering, KMeans from sklearn.feature_extraction.text import TfidfVectorizer vectorizer = TfidfVectorizer(max_features=300, tokenizer=lambda x: x.split(' ')) tfidf_mat = vectorizer.fit_transform(df['processed_input']) X = tfidf_mat.todense() X[X==0]=0.00001

Ensuite, nous allons tester notre première méthode de clustering, le clustering agglomératif, sur ces vecteurs de caractéristiques.

Méthode de clustering 1 : clustering agglomératif

Considérant les catégories d'actualités données comme la solution optimale, comparons ces résultats à ceux du clustering agglomératif (avec le nombre souhaité de clusters de 30 puisqu'il y a 30 catégories dans l'ensemble de données) :

 clusters_agg = AgglomerativeClustering(n_clusters=30).fit_predict(X) df['class_prd'] = clusters_agg.astype(int)

Nous identifierons les clusters résultants par des étiquettes entières ; les titres appartenant au même cluster se voient attribuer la même étiquette entière. La fonction cluster_measure du module compare_clusters de notre référentiel GitHub renvoie la mesure F agrégée et le nombre de clusters parfaitement correspondants afin que nous puissions voir à quel point notre résultat de clustering était précis :

 from clustering.compare_clusters import cluster_measure # 'cluster_measure` requires given text categories to be in the column 'text_category` df['text_category'] = df['category'] res_df, fmeasure_aggregate, true_matches = cluster_measure(df, gt_column='class_gt') fmeasure_aggregate, len(true_matches) # Outputs: (0.19858339749319176, 0)

En comparant ces résultats de cluster avec la solution optimale, nous obtenons une faible mesure F de 0,198 et 0 clusters correspondant aux groupes de classe réels, ce qui montre que les clusters agglomératifs ne correspondent pas aux catégories principales que nous avons choisies. Examinons un cluster dans le résultat pour voir à quoi il ressemble.

 df[df['class_prd'] == 0]['category'].value_counts()

En examinant les résultats, nous constatons que ce groupe contient des titres de toutes les catégories :

 POLITICS 1268 ENTERTAINMENT 712 THE WORLDPOST 373 HEALTHY LIVING 272 QUEER VOICES 251 PARENTS 212 BLACK VOICES 211 ... FIFTY 24 EDUCATION 23 COLLEGE 14 ARTS 13

Ainsi, notre faible F-mesure a du sens étant donné que les clusters de nos résultats ne s'alignent pas sur la solution optimale. Cependant, il est important de rappeler que la classification de catégorie donnée que nous avons choisie ne reflète qu'une seule division possible de l'ensemble de données. Une mesure F faible ici n'implique pas que le résultat du clustering est erroné, mais que le résultat du clustering ne correspond pas à la méthode souhaitée de partitionnement des données.

Méthode de regroupement 2 : K-means

Essayons un autre algorithme de clustering populaire sur le même ensemble de données : le clustering k-means. Nous allons créer un nouveau dataframe et utiliser à nouveau la fonction cluster_measure :

 kmeans = KMeans(n_clusters=30, random_state=0).fit(X) df2 = df.copy() df2['class_prd'] = kmeans.predict(X).astype(int) res_df, fmeasure_aggregate, true_matches = cluster_measure(df2) fmeasure_aggregate, len(true_matches) # Outputs: (0.18332960871141976, 0)

Comme le résultat de clustering agglomératif, notre résultat de clustering k-means a formé des clusters qui sont différents de nos catégories données : il a une mesure F de 0,18 par rapport à la solution optimale. Étant donné que les deux résultats de regroupement ont des F-mesures similaires, il serait intéressant de les comparer les uns aux autres. Nous avons déjà les regroupements, il nous suffit donc de calculer la F-mesure. Tout d'abord, nous allons mettre les deux résultats dans une colonne, avec class_gt ayant la sortie de clustering agglomératif et class_prd ayant la sortie de clustering k-means :

 df1 = df2.copy() df1['class_gt'] = df['class_prd'] res_df, fmeasure_aggregate, true_matches = cluster_measure(df1, gt_column='class_gt') fmeasure_aggregate, len(true_matches) # Outputs: (0.4030316435020922, 0)

Avec une mesure F plus élevée de 0,4, nous pouvons observer que les regroupements des deux algorithmes sont plus similaires entre eux qu'ils ne le sont avec la solution optimale.

En savoir plus sur les résultats de clustering améliorés

Une compréhension des métriques de comparaison de clustering disponibles élargira l'analyse de votre modèle d'apprentissage automatique. Nous avons vu la métrique de clustering F-measure en action et vous avons donné les bases dont vous avez besoin pour appliquer ces apprentissages à votre prochain résultat de clustering. Pour en savoir encore plus, voici mes meilleurs choix pour une lecture plus approfondie :

• Comparaison des regroupements - Un aperçu par Dorothea Wagner et Silke Wagner
• Comparaison des regroupements - une distance basée sur l'information par Marina Meila
• Mesures théoriques de l'information pour la comparaison des regroupements : variantes, propriétés, normalisation et correction du hasard par Nguyen Xuan Vinh, Julien Epps et James Bailey

---

Lectures complémentaires sur le blog Toptal Engineering :

• Graphique Data Science avec Python/NetworkX
• Classification d'images semi-supervisée avec des données non étiquetées
• Intégrations dans l'apprentissage automatique : simplifier les données complexes

Le blog Toptal Engineering exprime sa gratitude à Luis Bronchal pour avoir examiné les exemples de code présentés dans cet article.