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

De EduTech Wiki
Aller à la navigation Aller à la recherche
Ligne 30 : Ligne 30 :
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 a j, cela ne veut pas dire que j est similaire à i) et définie par
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 a j, cela ne veut pas dire que j est similaire à i) et définie par
<math>
<math>
 
\text{clusterdist}(i,j) = \frac{i\cdot j}{\lVert i \rVert_1}
</math>
</math>
où <math>\lVert i \rVert_1</math> désigne la norme <math>l_1</math> de i, c'est-à-dire la somme de la valeur absolue des coordonnées de i (<math>\lVert i \rVert_1=\sum_k \lvert i_K\rvert</math>


== Autres bases possibles pour la classification ==
== Autres bases possibles pour la classification ==

Version du 30 octobre 2014 à 17:37

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.

clustering basé sur une distance

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.

Trois terms 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 termes sont similaires et plus ils leur apparence dans un même document est corrélée. Ceci 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 termes non similaires ont tendance a avoir des apparitions décorrélées. Autrement dit, ils sont "orthogonaux" géométriquement et leur cosinus sera proche de 0.

Notons cependant que "similaire" ici ne veux pas dire que leur sens est proche mais que leur occurences est corrélés. Les termes eux-mêmes pouvant être synonymes, antonymes ou encore aller de paire dans le corpus considéré (ex. "chien" peut être similaire à "alarme" dans un contexte de sûreté et similaire à "compagnion" dans un corpus sur les animaux domestiques). Il faut garder à l'esprit que cette démarche vise moins à établir des synonymes entre les termes qu'à déterminer si deux documents peuvent être considérés comme "proches" d'un point de vue sémantique.

Limitations de la distance du cosinus

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 a 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 (Échec de l’analyse (fonction inconnue « \lvert »): {\displaystyle \lVert i \rVert_1=\sum_k \lvert i_K\rvert}

Autres bases possibles pour la classification

D'autres bases existent pour la classification que la définition d'une distance poiur 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

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