« Clustering et classification hiérarchique en text mining » : différence entre les versions

De EduTech Wiki
Aller à la navigation Aller à la recherche
Ligne 93 : Ligne 93 :
# fusionner les deux clusters qui sont les plus similaires.
# fusionner les deux clusters qui sont les plus similaires.


'''Présentation des résultats'''
====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
Les résultats du regroupement sont en général présentés sous forme de dendogram :
[[Image:Dendogram.jpg |thumb|none|300px|Dendogram - source [http://upload.wikimedia.org/wikipedia/commons/4/4c/EM-density-data.svg wikimedia] ]]
[[Image:Dendogram.jpg |thumb|none|350px|Dendogram - source [http://upload.wikimedia.org/wikipedia/commons/4/4c/EM-density-data.svg wikimedia] ]]
* sur un axe de coordonnées les documents analysés (ici en vertical) ;
* sur l'autre le degré de similarité (ici en horizontal) ;
* chaque document et cluster est représenté par une ligne (ici horizontale) ;
* lorsque deux lignes sont reliées, c'est que les documents (ou les clusters) correspondant sont fusionnés dans un nouveau cluster.


Plus la ligne horizontale est courte et plus les clusters sont similaires. Cela permet d'avoir une visualisation claire des liens et similitudes entre les éléments.
''Remarque'' : cette représentation n'est pas limitée à l'analyse de texte et se trouve très souvent utilisée, notamment en génétique et biologie pour représenter le degré de similitudes entre les espèces ([http://fr.wikipedia.org/wiki/Arbre_phylog%C3%A9n%C3%A9tique arbre phylogénétique]).
====Choix de méthode de regroupement====
La difficulté revient alors a bien choisir la façon de calculer le degré de similitude entre deux clusters.  
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.  
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.
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====
=====Single linkage=====
La méthode du single linkage correspond au choix du "meilleur des cas".
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.
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.
Ligne 109 : Ligne 118 :
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...
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====
=====Complete linkage=====
La méthode du complete linkage est l'opposée du single linkage et correspond au choix du "pire des cas".  
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.
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.
Ligne 116 : Ligne 125 :
Cette méthode permet d'éviter l'effet de "chaîne" mais en contrepartie est très conservatrice  
Cette méthode permet d'éviter l'effet de "chaîne" mais en contrepartie est très conservatrice  


====Average linkage====
=====Average linkage=====
 


===Regroupement basés sur la distance ===
===Regroupement basés sur la distance ===

Version du 31 octobre 2014 à 12:05

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 :

Dendogram - source wikimedia
  • sur un axe de coordonnées les documents analysés (ici en vertical) ;
  • sur l'autre le degré de similarité (ici en horizontal) ;
  • chaque document et cluster est représenté par une ligne (ici horizontale) ;
  • lorsque deux lignes sont reliées, c'est que les documents (ou les clusters) correspondant sont fusionnés dans un nouveau cluster.

Plus la ligne horizontale est courte et plus les clusters sont similaires. Cela permet d'avoir une visualisation claire des liens et similitudes entre les éléments.

Remarque : cette représentation n'est pas limitée à l'analyse de texte et se trouve très souvent utilisée, notamment en génétique et biologie pour représenter le degré de similitudes entre les espèces (arbre phylogénétique).

Choix de méthode de regroupement

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