Clustering et classification hiérarchique en text mining

De EduTech Wiki
Aller à la navigation Aller à la recherche

Cet article est une ébauche à compléter. Une ébauche est une entrée ayant un contenu (très) maigre et qui a donc besoin d'un auteur.

Le Clustering

Le partitionnement de données (data clustering en anglais) est une des méthodes statistiques d'analyse des données. Elle vise à diviser un ensemble de données en différents « paquets » homogènes, en ce sens que les données de chaque sous-ensemble partagent des caractéristiques communes, qui correspondent le plus souvent à des critères de proximité (similarité). (source: Wikipedia). En clair, le clustering cherche à faire des classes telle que

  • les différences intra-classe soient minimales pour obtenir des clusters
  • les différences inter-classe soient maximales afin d'obtenir des sous-ensembles bien différenciés.

En général, le résultat d'une classification prends soit la forme d'un graphique de points ou d'un dendogramme

Définition d'une distance

Voir la page Text mining pour un survol.

Distance du cosinus

La distance la plus couramment utilisée est la distance du cosinus ou cosine qui est définie comme dénote le produit scalaire et la norme associée.

Dans la norme euclidienne, cela s'écrit

représente le nombre d'occurrences du terme k dans le document i (tirés par exemple de la matrice termes-documents).


Cosine généralisée

On peut généraliser la mesure du cosinus en introduisant une fonction de "damping" qui aura pour effet de rendre plus clair les différences (parfois minimes) entre les documents. Par exemple, souvent on remplace et par le logarithme ou la racine carrée de la fréquence d'apparition du terme k. C'est-à-dire, si dénote le nombre totale d'occurrences du terme k dans l'ensemble du corpus, on remplace dans la formule par ou par (et de même pour ).


Trois termes et trois documents - distance entre documents


La distance du cosinus est toujours comprise entre -1 et +1 et peut être reliée intuitivement avec la notion de corrélation de la manière suivante :

  • plus deux documents sont similaires et plus ils auront tendance à utiliser les mêmes termes. Les termes seront alors corrélés, ce qui se traduit géométriquement par être "colinéaires", c'est à dire par un angle faible entre eux et donc un cosinus proche de +1 ou -1 ;
  • inversement, deux documents non similaires auront tendance a avoir des termes décorrélées. Autrement dit, ils seront "orthogonaux" géométriquement et leur cosinus sera proche de 0.

Limitations de la distance du cosinus

Cette distance est parmi les plus utilisées, cependant elle présente tout de même quelques limitations.

Une des limites de la distance du cosinus est qu'elle ne tient pas compte de la possibilité d'utiliser des synonymes lors de la rédaction du corpus. Si un texte n'utilise que le mot "chien" et un autre que le mot "canidé", leur distance sera considérée comme grande. Ce point peut être résolu en faisant appel à des modifications du corpus comme avec la méthode LSI.

Une limitation plus importante de cette méthode, comme mentionné par Senellart et Blondel est que le modèle mathématique sous-jacent repose sur l'hypothèse d'un espace orthogonal, ce qui implique les termes soient globalement répartis uniformément les uns par rapport aux autres dans le corpus, ce qui est rarement le cas puisque le corpus est en principe une collection de document partageant des caractéristiques communes (et donc des similarités).

Autres distances possibles

Il est également possible de définir d'autre distances comme

  • la distance de cluster proposée par Chen et Lynch (1972) qui est une distance asymétrique (si i et similaire à j cela ne veut pas dire que j est similaire à i) et définie par

désigne la norme de i, c'est-à-dire la somme de la valeur absolue des coordonnées de i.


  • les mesures de Jaccard définies par

par exemple, on peut définir une mesure qui soit le quotient du nombre de fois où i et j apparaissent dans la même phrase divisé par le nombre de fois où i et j apparaissent (ensemble ou non).

Autres bases possibles pour la classification

D'autres bases existent pour la classification que la définition d'une distance pour définir la similarité entre deux termes. On peut voir à ce sujet Aggarwal & Zhai qui distinguent

  • la méthode LSI (Latent Semantic Indexing) qui cherche a grouper les termes synonymes avant la classification. A ce sujet, voir Senellart & Blondel in Berry & Castellanos (2007), p25
  • la méthode NMF (Non-negative Matrix Factorisation) dont le but est d'extraire de la matrice termes-documents un ensemble plus restreint de caractéristiques sur lesquelles seront appliqué la classification.
  • les méthodes basées sur l'entropie

ou encore Pons & Latapy au sujet des marches aléatoires.

Méthodes de regroupement

Le principe général est de regrouper les documents par similarité afin de dégager des classes qui soit au maximum

  • homogènes, c'est-à-dire dont les éléments soient similaires entre eux ;
  • différenciées, c'est-à-dire que les éléments de classes différentes soient non similaires (en tout cas moins similaires que les éléments internes à leur classe).

Pour ce faire, il existe plusieurs stratégies, chacune avec avantages et inconvénients.

Regroupement Hiérarchique

Le concept de base du regroupement hiérarchique est de fusionner successivement les documents en clusters (groupes) puis les clusters entre eux selon leur degré de similarité. Elle se décompose donc en deux étapes répétées en boucle (jusqu'à ce qu'il ne reste qu'un seul cluster unique) :

  1. calculer la similarité (distance) entre toutes les paires de cluster existant à l'étape en cours ;
  2. fusionner les deux clusters qui sont les plus similaires.

Présentation des résultats Les résultats du regroupement sont en général présentés sous forme de dendogram, qui présente

La difficulté revient alors a bien choisir la façon de calculer le degré de similitude entre deux clusters. Par exemple, on peut choisir soit le meilleur cas possible, le pire cas possible ou une forme de moyenne. En général, il s'agit de choisir un ou plusieurs représentants du groupe (cluster) et de calculer la similarité en se basant sur ces représentants.

Single linkage

La méthode du single linkage correspond au choix du "meilleur des cas". Dans cette méthode, on choisit comme représentant du groupe le document qui est le plus similaire avec les documents de l'autre groupe. Ainsi la similarité entre les cluster est le maximum de la similarité entre les documents des clusters.

Le problème principal de cette méthode est que cela peut créer un effet de "chaîne" qui finira par regrouper des éléments qui ne sont pas similaires entre eux. Si A et B sont similaires et B et C sont similiaire, cela ne veut pas dire que A et C sont similaire. Par exemple, un texte sur la voltige à cheval peut être similaire à un texte sur les chevaux de courses lui-même similaire à un texte sur les courses de vélo qui pourra être similaire à un texte sur l'utilisation du vélo en milieu urbain...

Complete linkage

La méthode du complete linkage est l'opposée du single linkage et correspond au choix du "pire des cas". Dans cette méthode, on choisit comme représentant du groupe le document qui est le moins similaire avec les documents de l'autre groupe. Ainsi la similarité entre les cluster est le minimum de la similarité entre les documents des clusters.

Cette méthode permet d'éviter l'effet de "chaîne" mais en contrepartie est très conservatrice

Average linkage

Regroupement basés sur la distance

k-mean

k-medoid

Autres méthodes

Méthodes hybrides : Eclater et regrouper (Scatter-Gather)

D'autres méthodes existent dont la mise en oeuvre peut être plus complexe comme

  • le Buckshot qui cherche à améliorer les algorithmes de type k-means en sélectionnant graines au lieu de puis les fusionnent en k graines ;
  • la Fractionalisation qui répartit le corpus en sous-corpus de tailles réduites, réalise une agglomération des corpus pour en réduire le nombre puis classifie le corpus réduit.

Méthodes basées sur la fréquence des termes

D'autres méthodes existent encore, basées entre autres sur la fréquence de présence des termes dans les documents.

Pour de plus amples informations sur ces méthodes, voir Aggarwal et Zhai (2012)

Références

  • Berry, M. & Castellanos, M. (2007) Survey of Text Mining: Clustering, Classification, and Retrieval, Second Edition PDF
  • Aggarwal, C. & Zhai C. (2012). A Survey of Clustering Algorithms, in Mining Text Data, Springer. ch4 PDF
  • Feinerer, I., Hornik, K. & Meyer, D. (2008). Text Mining Infrastructure in R. Journal of Statistical Software, 25. PDF
  • Pons, P. & Latapy, M. (2005) Computing communities in large networks using random walks PDF
  • Chen and Lynch (1992). Automatic construction of networks of concepts characterizing document databases. IEEE Transactions on Systems, Man and Cybernetics, 22(5):885–902.

Manuel R

Références informelles