fr en

Accuracy: de la classification supervisée à non supervisée (clustering)

Posté le Tue 04 June 2019 dans machine learning • 4 min de lecture

Cet article est le numéro 7 de la série "clustering" :

L'accuracy est souvent utilisée comme mesure de qualité pour la classification supervisée. Elle est aussi utilisée pour la classification non supervisée. Cependant, la fonction accuracy_score de scikit-learn ne fournit qu'une borne inférieure de l'accuracy pour le clustering. Cet article explique comment cette mesure peut être calculée pour la classification non supervisée.

Commençons par rappeler ce qu'est l'accuracy pour une tâche de classification supervisée.

Accuracy pour la classification supervisée

Pour \(n\) individus dans un jeu de données, notons \(y_i\) l'étiquette de classe pour le \(i\)-ème individu et \(\hat{y}_i\) la valeur prédite. L'accuracy entre les étiquettes de classes \(y\) et les valeurs prédites \(\hat{y}\) est définie par :

\begin{equation*} accuracy(y, \hat{y}) = \frac{1}{n} \sum_{i=0}^{n-1} 1(\hat{y}_i = y_i) \end{equation*}

où \(x \rightarrow 1(x)\) est la fonction indicatrice : \(1(\hat{y}_i = y_i) = 1\) si \(\hat{y}_i = y_i\) et \(0\) sinon.

Elle est calculée comme la somme des éléments diagonaux de la matrice de confusion, divisée par le nombre d'individus afin d'avoir une valeur entre 0 et 1.

Pour la classification non supervisée, il n'y a cependant pas d'association procurée par l'algorithme de clustering entre les étiquettes de classes et les étiquettes prédites pour les clusters. Nous avons donc besoin de changer un peu la formule.

Accuracy pour la classification non supervisée

Pour le clustering, nous devons trouver la meilleure correspondance entre les étiquettes de classes et les étiquettes de clusters, de sorte que l'accuracy soit définie par :

\begin{equation*} accuracy(y, \hat{y}) = \max_{perm \in P} \frac{1}{n} \sum_{i=0}^{n-1} 1(perm(\hat{y}_i) = y_i) \end{equation*}

où \(P\) est l'ensemble de toutes les permutations dans \([1; K]\) où \(K\) est le nombre de clusters.

Il est important de noter qu'il y a \(K !\) permutations dans \(P\) ce qui est très grand et le calcul de l'accuracy est donc prohibitif si on applique aveuglément cette formule. L'algorithme hongrois peut nous aider à la calculer en \(O(K^3)\) ce qui est significativement plus rapide.

Voyons concrètement comment calculer l'accuracy pour la classification non supervisée en un temps polynomial.

Mise en pratique

Dans cette partie, nous allons d'abord obtenir des données textuelles à traiter, puis regrouper les documents et calculer l'accuracy entre les résultats du clustering et les classes connues.

Récupérer des données

Récupérons quelques documents d'un jeu de données de listes de diffusions. Nous récupérons seulement cinq classes de ce jeu de données :

from sklearn.datasets import fetch_20newsgroups

categories = [
    'rec.motorcycles',
    'rec.sport.baseball',
    'comp.graphics',
    'sci.space',
    'talk.politics.mideast'
]

ng5 = fetch_20newsgroups(categories=categories, shuffle=True)

labels = ng5.target
documents = ng5.data

L'analyse sémantique latente est une méthode bien connue pour transformer des documents en vecteurs de faible dimension (faible par rapport à la taille du vocabulaire, c'est-à-dire le nombre de mots uniques dans l'ensemble des documents) :

from sklearn.pipeline import Pipeline
from sklearn.feature_extraction.text import CountVectorizer
from sklearn.feature_extraction.text import TfidfTransformer
from sklearn.decomposition import TruncatedSVD
from sklearn.preprocessing import Normalizer

pipeline = Pipeline([
    ('vect', CountVectorizer()),
    ('tfidf', TfidfTransformer()),
    ('svd', TruncatedSVD()),
    ('normalizer', Normalizer())
])
pipeline.set_params(svd__n_components=300)
A = pipeline.fit_transform(documents)

Chaque ligne de la matrice A est un document représenté par un vecteur. On peut donc appliquer un algorithme de clustering sur cette matrice.

Clustering

Spherical k-means est un bon algorithme pour segmenter des données textuelles. Une implémentation est donnée par la bibliothèque Python Coclust:

from coclust.clustering import SphericalKmeans

skm = SphericalKmeans(n_clusters=5)
skm.fit(A)
predicted_labels = skm.labels_

Nous sommes maintenant prêts à calculer l'accuracy entre labels et predicted_labels. Comme décrit précédemment, nous pouvons le faire en calculant d'abord la matrice de confusion.

Matrice de confusion

La bibliothèque scikit-learn fournit une fonction appelée confusion_matrix pour créer un tableau Numpy contenant les valeurs de la matrice de confusion :

from sklearn.metrics import confusion_matrix

cm = confusion_matrix(labels, predicted_labels)

Visualisons la avec la bibliothèque de visualisation Seaborn:

import seaborn as sns; sns.set()

ax = sns.heatmap(cm, annot=True, fmt="d", cmap="Blues")

Pour calculer l'accuracy, il faut additionner les valeurs sur la diagonale, mais pour la classification non supervisée, les lignes (ou les colonnes) de la matrice de confusion doivent être permutées pour obtenir la valeur maximale de la somme. Ce n'est pas le cas ici. Voyons comment trouver la meilleure permutation.

Permutation maximisant la somme des éléments diagonaux

Scikit-learn a une fonction linear_assignment pour appliquer l'algorithme hongrois. Nous pouvons l'utiliser pour créer une matrice de confusion réordonnée cm2 :

from sklearn.utils.linear_assignment_ import linear_assignment
import numpy as np

def _make_cost_m(cm):
    s = np.max(cm)
    return (- cm + s)

indexes = linear_assignment(_make_cost_m(cm))
js = [e[1] for e in sorted(indexes, key=lambda x: x[0])]
cm2 = cm[:, js]

Puisque linear_assigment minimise un coût qui doit être positif, nous définissons la fonction _make_cost_m pour transformer la matrice de confusion en une matrice de coût. La matrice de confusion réordonnée cm2 peut être visualisée :

Calculons désormais l'accuracy.

Calcul de l'accuracy

L'accuracy est la somme des éléments diagonaux divisée par le nombre d'individus :

np.trace(cm2) / np.sum(cm2)

Au lieu d'implémenter tout cela nous-mêmes, nous pouvons simplement utiliser la fonction accuracy fournie par Coclust :

from coclust.evaluation.external import accuracy

accuracy(labels, predicted_labels)

Notons que la fonction accuracy_score de scikit-learn ne donne pas l'accuracy pour le clustering car elle ne permute pas les lignes de la matrice de confusion :

from sklearn.metrics.classification import accuracy_score

accuracy_score(labels, predicted_labels)

donne la même valeur que :

np.trace(cm) / np.sum(cm)

Ce qu'il faut retenir

Voici un résumé des éléments clés de cet article :

accuracy_score fournie par scikit-learn est conçue pour traiter des résultats de classification supervisée et non pas de clustering.
Le calcul de l'accuracy pour la classification non supervisée peut être fait en réordonnant les lignes (ou les colonnes) de la matrice de confusion tel que la somme des éléments diagonaux soit maximale.
Le problème d'affectation linéaire peut être résolu en \(O(n^3)\) au lieu de \(O(n!)\).
La bibliothèque Coclust fournit une implémentation de l'accuracy pour de la classification non supervisée.

Previous Post Next Post