Méthodes de classification en text mining

A l'inverse de la classification où les catégories n'étaient pas connues par avance, la classification essaie de classer les documents du corpus dans un certain nombre de catégories prédéfinies. Elle peut se rapprocher d'une analyse de thématique "Topic modelling", mais, à l'inverse de ce dernier, elle ne permet pas l'attribution de plusieurs catégorie à un même document. Un exemple concret de catégorisation serait de différencier le emails de spam (pourriels) des emails légitimes.

Préparation du corpus

Ces méthodes demandent la préparation habituelle du corpus, stop-words, lemmatisation et construction de la matrice terme-document (voir Text mining).

Elles reposent sur plusieurs hypothèses, les plus essentielles étant :

• Les catégories constituent une base ou un corpus d'apprentissage (pour l'algorithme)
• Les documents présentés pour être classés sont représentés par des vecteurs de termes pondérés (ceci est tiré de la matrice terme-documents qui compte le nombre d'occurrences de chaque terme dans chaque document). En clair, chaque document est représenté par une liste de mots-clés avec le nombre d'occurrence du mot dans le document).
• Pour pondérer les occurrences des mots, on a souvent recours à la méthode TfIdf, qui améliore les contraste entre les documents par un passage au logarithme.

  $p_{i,j}=f_{i,j}\log \left({\frac {N}{n_{i}}}\right)$

  où $p_{i,j}$ désigne le poids du mot i dans le document j, $f_{i,j}$ la fréquence du mot i dans le document j (tirée de la matrice terme-document), N le nombre de documents considérés et $n_{i}$ le nombre total d'occurrence du mot i dans l'ensemble des documents.

• Notons enfin que ces méthodes reposent sur le choix d'une distance entre document, comme par exemple la distance du cosinus (voir aussi Clustering).

Catégorisation linéaire Rocchio

Cette méthode est la plus simple. Elle classe un document dans la catégorie dont il est le plus proche du barycentre (selon la distance que l'on a choisie, voir plus haut la distance du cosinus).

Phase d'apprentissage

Cette méthode est basée sur une phase d'apprentissage, où certains documents servent à établir une base contre laquelle les autres documents seront classés. Un ensemble de documents bien choisi est donc fourni au départ comme représentatif des catégories voulues.

Algorithme de la méthode

1. On commence par construire des vecteurs "de base" des catégories considérées. En clair il s'agit pour chaque catégorie d'avoir un vecteur pondéré associant à chaque mot clé son poids dans la catégorie (ex: si on a comme catégorie "animaux" et "lieu", alors "chien" aura un poids fort dans "animaux" et faible dans "lieux", "Paris" aura un poids fort dans "lieux", alors que "chenil" pourra avoir un poids moyen dans les deux).

   Le vecteur de base de la catégorie k se calcule comme suit :

   1. Pour chaque mot clé on tire de la matrice terme-document pondérée l'ensemble de ces poids dans les documents de la catégorie k.
   2. On calcule le poids du mot dans la catégorie k en faisant la différence entre la moyenne des poids du mot dans les documents appartenant à la catégorie k et la moyenne du poids du mot dans les documents n'appartenant pas à la catégorie k.

   On obtient ainsi un ensemble de vecteurs de poids pour chaque catégorie.

2. Pour chaque document à classer, il suffit de calculer la distance avec chacun des vecteurs "de base" et d'associer le document à la catégorie dont il est le plus proche.

Dans l'exemple ci-dessous, les catégorie sont représentées en bleu et le document à classer en vert.

Le document A va être classé avec la catégorie $C_{1}$

Le document A en vert va être classé avec la catégorie $C_{1}$ car c'est la plus proche, mais il aurait peut-être pu également appartenir à la catégorie $C_{2}$. Ce problème peut être éviter en faisant appel à des techniques d'analyse de thèmatique Topic modelling.

Catégorisation par les k plus proches voisins

Dans cette méthode, on classe un document dans la même catégorie que la majorité (pondérée) de ses k plus proches voisins (selon la distance que l'on a choisie, voir plus haut la distance du cosinus).

Phase d'entraînement

Cette méthode est basée sur des instances (ou exemples) de document de chaque catégorie. Ainsi, comme pour la catégorisation linéaire, plus on fourni d'exemples en phase d'entraînement, meilleur sera le résultat. Un ensemble de documents bien choisidoit donc être fourni au départ comme représentatif des catégories voulues.

Algorithme de la méthode

A la différence de la catégorisation linéaire, aucune phase préliminaire n'est requise. Les étapes se déroulent comme suit :

1. Calculer quels sont les K documents les plus proches (K plus proches voisins selon la distance choisie), ainsi que leur catégorie d'appartenance
2. Affecter le document courant à la catégorie qui avait le plus de représentant parmi les K plus proches voisins (système de vote)

Le résultat change pour K=1 ou K=5

Ici, pour K=1 le document (point rouge) est classé avec les "+" mais pour K=5 il serait classé avec les "-". Ainsi le choix de K est très important.

Pour éviter les problèmes d'égalité, pour les tâches de classification en deux catégories, on utilise uniquement des valeurs de K impaires.

Prise en compte de la distance effective

Dans la version simple que nous venons de voir, seul le nombre de voisins dans chaque catégorie était pris en compte, indépendamment de la distance avec le document courant. Cependant, il est sensé de donner plus de poids aux documents les plus proches qu'au plus éloignés. Pour remédier à cela, on utilise en général une pondération exponentielle (issue de la même idée que la pondération en logarithme de la matrice terme-document). On calcule la moyenne pondérée des distances entre le document courant $x$ et ses $K$ plus proches voisins $d_{i}$

$W_{x,d_{i}}={\frac {\exp(-d(x,d_{i}))}{\sum _{i=1}^{K}\exp(-d(x,d_{i}))}}$

où $d(x,d_{i})$ désigne la distance entre le document $x$ et $d_{i}$

k-nearest neighbors avec R

Il est possible d'implémenter cet algorithme sous R avec la fonction "knn" (voir Feinerer, Hornik et Meyer (2008) et knn.html). La syntaxe générale étant

knn(train, test, cl, k = 1, l = 0, prob = FALSE, use.all = TRUE)

Références

• Brown, S. (s.d.) K nearest neighbor ([www.cs.uvm.edu/~xwu/kdd/kNN-11.ppt support de cours ppt])
• Ghosh, S, Roy, S et Bandyopadhyay, S. (2012). A tutorial review on Text Mining Algorithms. International Journal of Advanced Research in Computer and Communication Engineering, 1(4) (pdf)
• Grivel, L. (s.d.) Outils de classification et de catégorisation pour la fouille de textes (pdf)
• Gupta, V. et Lehal, G. (2009) A Survey of Text Mining Techniques and Applications. Journal of Emerging Technologies in Web Intelligence, 1(1) (pdf)
• Grimal, C. et Bisson, G. (s.d.) Amélioration de la co-similarité pour la classification de documents (pdf)
• Radovanovic, M. et Ivanovic, M. (2008) Text Mining: approaches and applications. Novi Sad Journal of Mathematics, 38(3).
• Tellier, I. (s.d.) Introduction à la fouille de textes. (pdf)

Références R

• Feinerer, I. Hornik, K et Meyer, D. (2008) Text mining infrastructures in R (pdf)
• Knn tutorial for R : knn.html

Autres références

• Page Wikipedia TfIdf